Locality and Load-Balancing in Heterogeneous Simulations and Architectures  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
124905
Type PD
Principal investigator Reguly, István Zoltán
Title in Hungarian Lokalitás és Munka-Elosztás Heterogén Szimulációkban és Architektúrákon
Title in English Locality and Load-Balancing in Heterogeneous Simulations and Architectures
Keywords in Hungarian Memória-lokalitás, Munka-Elosztás, CPU, GPU, Nem-Strukturált térhálók
Keywords in English Memory locality, Load-balancing, CPU, GPU, Unstructured meshes
Discipline
Information Technology (Council of Physical Sciences)100 %
Ortelius classification: Applied informatics
Panel Informatics and Electrical Engineering
Department or equivalent Faculty of Information Technology and Bionics (Pázmány Péter Catholic University)
Starting date 2017-09-01
Closing date 2020-12-31
Funding (in million HUF) 15.219
FTE (full time equivalent) 2.18
state closed project
Summary in Hungarian
A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.

Kutatásom a nem-strukturált térhálókon értelmezett problémák magasszintű megfogalmazását és azok modern számítógép-architektúrákra való hatékony, automatikus leképzését célozza meg, mely lehetővé teszi a szakterület művelőinek hogy a megoldandó problémára összpontosítsanak. A legfőbb kérdés az, hogy miként lehet ilyen absztrakciót megfogalmazni, és hogy hogyan lehet a problémaosztály ismeretében azt hatékonyan és automatikusan leképezni adott architektúrára. Ezek a számítások kifejezetten heterogénak, hiszen a különböző számíítási lépések nagyon eltérő számítási és memória-elérési karakterisztikákkal rendelkeznek, így aztán végrehajtásuk a mai heterogén számítógépeken (melyekben CPUk, videokártyák és egyéb gyorsítók találhatók) rendkívül komoly kihívás, különösen ha figyelembe vesszük a memória mozgatásának költségét. Az ilyen magas szintű absztrakciós rendszerek keretében helyezkedik el a kutatásom, ami a munka-elosztás kezelésével és optimalizálásával lehetővé teszi az egyes számítási lépések hatékony végrehajtását, majd az adatok lokalitásának maximalizálása mellett a számítási lépések közt újra-egyensúlyozza a munka-elosztást, így biztosítva a rendelkezésre álló hardverek folyamatos magas kihasználtságát. Kutatásomat a hagyományos statikus térhálók után ki fogom terjeszteni a több anyagot kezelő szimulációkra, ahol az adatszerkezetek is folyamatosan változnak (keletkező és eltűnő anyagok miatt).A kutatást során szoros együttműködésben tervezem folytatni az Warwicki Egyetem, az IBM, a Rolls-Royce és az AWE kutatóival, ezzel biztosítva az eredmények relevanciáját, és felhasználhatóságát.

Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.

Mára mind az alkalmazott tudományokban, mind az ipari kutatási és fejlesztési feladatokban a számítógépes szimulációk alapvető helyet foglalnak el, felgyorsítják a kísérletezést és a tervezési folyamatokat. Éppen ezért egyre nagyobb igény van a nagyobb és összetettebb szimulációk megvalósítására, ezt azonban alapvetően megnehezítik az elmúlt évek architektúrális trendjei: a frekvencia-skálázódás végével a sebességnövekedés csakis a nagyobb fokú párhuzamosságon keresztül érhető el. Ezzel egyidőben a memória mozgatás relatíve nagyon költséges lett - az adatok mozgatása akár 1000-szer drágább mint egy egyszerű számítás, mind késleltetésben, mind energiában. Ezekre a változásokra azonban sem a mai tudományos kódok, sem pedig a széleskörben használt programozási modellek nincsenek felkészülve. Így a legalapvetőbb kérdés az, hogy miként lehet olyan programozási absztrakciókat megfogalmazni, melyek segítségével komplex szimulációk valósíthatók meg egyszerűbben, a végrehajtást végző párhuzamos és heterogén rendszerek mély ismerete nélkül. Eddigi kutatásomat folyatva, meg szeretném vizsgálni, hogy miként lehet a következő évek alapvetően heterogén számítógép-architektúráit hatékonyan kihasználni, a párhuzamos implementáció komplexitásának a felhasználó elől való elfedéséve mellett, biztosítva a nagy teljesítményt, valamint a megbízható végrehajtást. Meg szeretném vizsgálni továbbá, hogy egy ilyen módszertannal hogyan lehet olyan problémákat kezelni, ahol nagymennyiségű dinamikusan változó feladat jön létre és fejeződik be, és hogy ezeket miként lehet megfelelően elosztani a mai heterogén rendszerekben – különös tekintettel a több, keveredő anyagokat leíró numerikus szimulációkra.

Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!

Ez a kutatás azt célozza meg, hogy elkülönítse a tudományos problémák magasszintű megfogalmazását azok párhuzamos implementációjától. Ez egy olyan alapvető módszertani váltást tesz lehetővé, mely segítségével az egyes szakterületek művelői (pl. fizikusok, mérnökök) a megoldandó problémára összpontosíthatnak, anélkül hogy a hatékony, sokszor architektúra-specifikus párhuzamos programozással kelljen az idejüket tölteni. Ezzel egyidőben az informatikai tudományok művelői egy jól definiált problémaosztályt leíró interfész segítségével automatizálni tudják azokat a folyamatokat, melyek az említett magasszintű leírásból alacsonyszintű, hatékony és skálázódó implementációt tudnak létrehozni. Ez lehetővé teszi azt, hogy a tudományos kódok fenntarthatók és könnyen átláthatók maradjanak, valamint magas teljesítményt érjenek el a mai és jövőbeni számítási erőforrásokon. A legújabb és a közeljövő szuperszámítógépei (Kínában a TaihuLight, az USA-ban a Titan, Summit és Sierra), de még legtöbbünk laptopjai is alapvetően heterogén számítógépek, ahol alacsony késleltetésű magok (hagyományos CPU) és nagy számítási kapacitású vektor architektúrák (mint a videokártyák) vannak egy rendszerbe integrálva - így hatékony kihasználtságuk a heterogén feladatok megoldása során kiemelkedő fontosságú, mint a feladat gyors megoldása, mind pedig az energia-hatékonyság szempontjából. Kutatásom során egy oldalról olyan hardvereket és programozási modelleket célzok meg, melyek kiemelkedő fontossággal fognak bírni az eljövendő években a tudományos számítások világában, valamint olyan probléma-osztályokkal fogok foglalkozni, melyek lehetővé teszik az összetett, több anyagot leíró akadémiai és ipari szimulálókat. Ennek a kutatásnak kiemelkedően fontos tulajdonsága, hogy szoros együttműködésben fog folyni az Warwicki Egyetem, az IBM, a Rolls-Royce és az AWE kutatóival, ezzel biztosítva a vizsgált problémák relevanciáját, valamint lehetővé téve azt, hogy az eredmények nemzetközi szinten megmérettessenek, mind kisebb, reprezentatív, mind pedig nagy, ipari alkalmazások példáin keresztül.

A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.

A mai világ minden területén jelen vannak a számítógépek, és a legtöbb hétköznapi eszköz, autó, repülő, vagy akár egy szék tervezésében is meghatározó szerepet játszottak – nem is beszélve az új gyógyszerek fejlesztéséről, vagy éppen a Higgs bozon megtalálásáról. Bár jogosan azt várhatjuk, hogy idővel egyre nagyobb és összetettebb problémákat tudunk majd számítógépek segítségével megoldani, a számító egységek már egy ideje nem képesek önmagukban gyorsulásra – ehelyett többet és többfélét teszünk belőlük egymás mellé: így egy mai okostelefonban sem ritka egy 4 magos processzor és egy pár száz magos grafikuskártya. Ezek hatékony használata azonban nehéz, főleg azok számára, akik magasabb szintű, pl. fizikai vagy tervezési problémákat akarnak megoldani, és nem szeretnének a hardverek részleteivel foglalkozni. Kutatásom ezért olyan programozási módszerek kidolgozásával foglalkozik, melyek lehetővé teszik, hogy ezen tudományterületek művelői könnyen megfogalmazhassák a problémáikat, majd utána ezek hatékonyan ki tudják használni a legújabb és legkülönbözőbb számítógép-rendszereket.
Summary
Summary of the research and its aims for experts
Describe the major aims of the research for experts.

My research targets the high-level abstraction of unstructured mesh computations, and their automatic mapping to modern computer architectures. This approach enables domain scientists to focus on the problem to be solved, rather than its parallel implementation. The main question is how such abstractions can be formulated, and how they can be efficiently and automatically mapped to a given architecture, achieving high performance. Given that such computations are inherently heterogeneous, since different computational steps involve widely variying computations and memory access patterns, their execution on today's heterogeneous systems (various CPUs, graphics cards, and other accelerators integrated together) is very challenging - particularly when one considers the cost of data movement. Within this high-level abstractions framework, my proposed research addresses the issue of efficient utilisation of various computational resources by load balancing individual computational steps, and then given the constraint on maximising data locality, re-balances across computational steps to achieve an overall high utilization of the hardware. After addressing this problem on conventional static mesh structures, I will expand my reserach to multi-material simulations, where data structures continuously change (as materials appear and disappear in various parts of the domain). I am going to conduct this research in close collaboration with researchers at the University of Warwick, IBM, Rolls-Royce, and AWE, ensuring the relevance and applicability of the results.

What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.

Computer simulations are fundamental in today’s research and development workflow; they accelerate experimentation and design processes. Thus, there is a growing demand for larger and more complex simulations, but this has been becoming increasingly challenging due to the architectural trends of the last few years; with the end of frequency scaling, it has become clear that increased computational capacity can only be achieved through increased parallelism. At the same time, the cost of data movement has become much more expensive in relative terms - up to a 1000 times compared to simple computations in terms of time latency and energy cost. However, most of today’s scientific codes, or the widely used programming methods are not well equipped to address this challenge. Therefore, one of the most fundamental questions is how to design programming abstractions that can help design complex but efficient simulations without deeply ingrained architecture-specific optimizations. Following my previous research, I would like to investigate how to take simulations written once at a high level and execute them efficiently on today's increasingly heterogeneous computers. I would like to show that it is possible to hide the complexities of parallel programming and data movement from the user, and at the same time to deliver high performance. Furthermore, I would like to study how highly complex problem classes can be handled with such a methodology, in the presence of a highly dynamic workload, where tasks are created and completed at a high rate – and how these can be mapped and scheduled in today’s heterogeneous systems – with particular focus on multi-material simulations.

What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.

My research aims to separate the abstract definition of computational problems from their parallel implementation. This brings about a fundamental methodological shift; it allows domains scientists to focus on the problem at hand, instead of spending time implementing low-level, often architecture-specific optimisations. At the same time computer scientists can base their research on a well defined domain-specific interface and automate the translation of the high-level description of computations to efficient, scalable low-level implementations for modern hardware architectures. This delivers readability and maintainability to scientific codes, as well as future-proofing them against upcoming changes to computing architectures. Almost all of the latest and upcoming supercomputers (China's TaihuLight, the US's Titan, Summit and Sierra machines), but even most people's laptops are fundamentally heterogeneous, integrating low-latency computational units (CPU cores) and high-throughput wide vector computational units (such as GPUs) in the same sytem - their efficient utilisation on heterogeneous computations is incredibly important for both time to solution and energy efficiency. During my research I will target next-generation hardware and programming models that are going to be of great importance to the scientific computing community, and I will target problem classes that enable the simulation of complex multi-material scenarios. One of the particularly strong aspects of the proposed research is that it will be conducted in close cooperation with researchers at the University of Warwick, IBM, Rolls-Royce and AWE, thereby ensuring that the work is rooted in highly relevant problems, and enabling the evaluation of results on an international level, through both smaller, representative applications as well as large-scale industrial codes.

Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.

Computers are everywhere in out world, indeed, most everyday items, such as our cars, airplanes or even chairs were designed using them – not to mention the development of new drugs, or the discovery of the Higgs boson. While we can justifiably expect to be able to solve larger and more complex problems with computers, processing units themselves have not been getting faster for a while now – instead we are bundling more of them, and different kinds of them together. Thus, a modern smartphone could easily contain a 4 core chip and a graphical processor with a few hundred processing units. Efficiently utilising these is very difficult, especially for those who just want to solve high-level scientific or design problems, and don’t want to get bogged down in the specifics of the hardware. My research aims to develop methods that lets domain experts to easily express their computational problems, and then to automatically and efficiently use the latest and greatest computing systems.





 

Final report

 
Results in Hungarian
Ma a legtöbb tervezési feladat alapvető eszköze a számítógép, és a szimulációk, melyek lehetővé teszik a tervezés tárgyának virtuális „kipróbálását”: mennyire leng ki a felhőkarcoló egy földrengés során, hogy áramlik a levegő az autó körül. Ezen szimulációk egyre összetettebb és részletesebb problémákba engednek bepillantást, ami a számítási igény növekedését jelenti. Az elmúlt tíz év számítási hardvereinek trendjei azonban egyre nagyobb diverzitást mutatnak – egyre nagyobb szakértelmet kíván hatékony használatuk. Kutatásom fő célja, hogy egy olyan eszközt adjak a szimulációkat készítők kezébe, ami lehetővé teszi, hogy a probléma leírására, nem pedig annak adott számítógépre való implementációjára koncentráljanak. Munkám során két probléma-osztályba tartozó algoritmusok (strukturált és nem-strukturált térhálók) automatikus párhuzamosításával foglalkoztam, megcélozva a legmodernebb párhuzamos architektúrákat: a videokártyáktól kezdve a több megawattot fogyasztó szuperszámítógépekig. Kutatásom különös figyelmet szentel az ezen eszközökben elérhető különböző méretű és sebességű memóriák optimális kihasználásának, azzal, hogy a számításokhoz legközelebb eső, leggyorsabb memóriában lévő adatok kihasználását növeli. Munkám során megmutattam, miként alkalmazhatók ezek az eredmények olyan számításokra, mint a cunamik mozgása, vagy a lökéshullámok terjedése, és miként bővíthető ki olyan problémaosztályokra, mint a keveredő anyagok szimulációja, vagy a pénzügyi eszközök árazása.
Results in English
Nowadays, most products are designed with the help of computers and simulations, which allow for virtually testing the product; how much a building will swing during an earthquake, or how the air flows around a car. These simulations offer insight into problems of increasing complexity, pushing computational requirements higher. The hardware trends of the last decade show growing diversity – they require increasingly specialized expertise to utilize efficiently. The goal of my research was to create tools for those developing simulations to focus on the description of the problem, rather than the implementation for a specific computer. My work addresses two problem domains, structured and unstructured mesh algorithms, and delivers automatic parallelization targeting platforms ranging from GPUs to national supercomputers. My research focuses on the efficient utilization of the many types of memories found in these systems, to try and improve locality: using data that is closest to the computations. My work demonstrates how these results can be used for acceleration simulations of tsunami propagation or shockwaves, and how they can be extended to cover problem domains such as simulations where multiple materials can mix, or the pricing of financial assets.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=124905
Decision
Yes





 

List of publications

 
Balogh G D, Reguly I Z, Mudalige G R: Comparison of Parallelisation Approaches, Languages, and Compilers for Unstructured Mesh Algorithms on GPUs, In: Jarvis Stephen, Wright Steven, Hammond Simon (szerk.) (szerk.) High Performance Computing Systems. Performance Modeling, Benchmarking, and Simulation: 8th International Workshop, PMBS 2017, Denver, CO, USA, November 13, 2017, Proceedings. New York: Springer International Publishing, 2017. pp. 22-43., 2017
I Z Reguly, G R Mudalige, M Giles: Loop Tiling in Large-Scale Stencil Codes at Run-time with OPS, IEEE T PARALL DISTR 29: (4) pp. 873-886., 2017
R O Kirk, G R Mudalige, I Z Reguly, S A Wright, M J Martineau, S A Jarvis: Achieving Performance Portability for a Heat Conduction Solver Mini-Application on Modern Multi-core Systems, In: 2017 IEEE International Conference on Cluster Computing (CLUSTER) . Honolulu (HI), Amerikai Egyesült Államok, 2017.09.05-2017.09.08. Kiadvány: Piscataway (NJ): IEEE, 2017. pp. 834-841., 2017
Reguly Istan Z, Mudalige Gihan R, Giles Michael B: Beyond 16GB: Out-of-Core Stencil Computations, In: Yonghong Yan (szerk.) (szerk.) Proceedings of the Workshop on Memory Centric Programming for HPC. New York: ACM Press, 2017. pp. 20-29., 2017
Mudalige G.R., Reguly I.Z., Jammy S.P., Jacobs C.T., Giles M.B., Sandham N.D.: Large-scale performance of a DSL-based multi-block structured-mesh application for Direct Numerical Simulation, JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 131: pp. 130-146., 2019
Reguly I.Z., Mudalige G.R., Giles M.B., Maheswaran S.: Improving resilience of scientific software through a domain-specific approach, JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 128: pp. 99-114., 2019
Reguly Istvan Z., Moore Branden, Schmielau Tim, du Toit Jacques, Mudalige Gihan R: Batch solution of small PDEs with the OPS DSL, -, 2019
Sulyok András Attila, Balogh Gábor Dániel, Reguly István Z, Mudalige Gihan R: Locality optimized unstructured mesh algorithms on GPUs, JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 134: pp. 50-64., 2019
Balint Siklosi, Istvan Reguly, Gihan Mudalige: Heterogeneous CPU-GPU Execution of Stencil Applications, In: Douglas, Doerfler; Rob, Neely; Kathryn, O’Brien; John, Pennycook (szerk.) International Workshop on Performance, Portability and Productivity in HPC (P3HPC), (2018) p. 1., 2018
Balogh G. D., Mudalige Gihan R., Reguly I. Z., Antao S. F., Bertolli C: OP2-Clang : a source-to-source translator using Clang/LLVM LibTooling, In: Hal, Finkel (szerk.) The Fifth Workshop on the LLVM Compiler Infrastructure in HPC, (2018) p. 1., 2018
Becker Daniel, Reguly István Zoltán, Mudalige Gihan: An abstraction for local computations on structured meshes and its extension to handling multiple materials, In: Zarándy, Á (szerk.) CNNA 2018.16th International Workshop on Cellular Nanoscale Networks and their Applications, VDE (2018) pp. 1-4., 2018
Reguly Istvan Z., Giles Daniel, Gopinathan Devaraj, Quivy Laure, Beck Joakim H., Giles Michael B., Guillas Serge, Dias Frederic: The VOLNA-OP2 tsunami code (version 1.5), GEOSCIENTIFIC MODEL DEVELOPMENT 11: (11) pp. 4621-4635., 2018
Reguly István Z., Mudalige Gihan R.: Productivity, performance, and portability for computational fluid dynamics applications, COMPUTERS AND FLUIDS 199: p. 104425., 2020
Szilniczky-Eross Botond, Reguly Istvan Z.: Performance Portability of the MG-CFD Mini-App with SYCL, In: IWOCL '20: Proceedings of the International Workshop on OpenCL, (2020) 21, 2020
D. Balogh G., Z. Reguly I.: Automatic parallel implementations of adjoint codes for structured mesh applications, IEEE, 2020
Siklósi B., Z. Reguly I., R. Mudalige G.: Bitwise Reproducible task execution on unstructured mesh applications, IEEE, 2020
Reguly Istvan, Mudalige Gihan: Modernising an Industrial CFD Application, In: Jacir, Bordim (szerk.) 2020 Eighth International Symposium on Computing and Networking Workshops (CANDARW), IEEE (2020) p. 1., 2020
Z. Reguly I.: Performance Portability of Multi-Material Kernels, IEEE, 2019
Kamalavasan Kamalakkannan, Gihan R. Mudalige, Istvan Z. Reguly, Suhaib A. Fahmy: High-Level FPGA Accelerator Design for Structured-Mesh-Based Explicit Numerical Solvers, közlésre elfogadva, 2021
Reguly Istvan Z, Powell Archie, Jarvis Steven A, Mudalige Gihan R, Owenson Andrew: Under the Hood of SYCL - An Initial Performance Analysis With an Unstructured-mesh CFD Application, Bírálat alatt, 2021




Back »