IA039: Architektura superpočítačů a náročné výpočty Message Passing Interface Luděk Matýska Fakulta informatiky MU Jaro 2016 Luděk Matýska (Fl MU) MPI Jaro 2016 1/42 Paralelní programovaní • Data paralelismus • Stejné instrukce na různých pocesorech zpracovávaj různá data • V podstatě odpovídá SIMD modelu (Single Instruction Multiple Data) • Např. paralelizace cyklu • Task paralelismus • MIMD model (Multiple Instruction Multiple Data) • Paralelně prováděné nezávislé bloky (funkce, procedury, programy) o SPMD • Není synchronizován na úrovni jednotlivých instrukcí • Ekvivalentní MIMD • Message passing určeno pro SPMD/MIMD Luděk Matýska (Fl MU) MPI Jaro 2016 2 / 42 Message Passing Interface Komunikační rozhraní pro paralelní programy Definováno API • Standardizováno 9 Rada nezávislých implementací • Možnost optimalizace pro konkrétní hardware • Určité problémy se skutečnou interoperabilitou Luděk Matýska (Fl MU) MPI Jaro 2016 3 / 42 Vývoj M PI • Postupné uvádění verzí • Verze 1.0 • Základní, nebyla implementována • Vazba na jayzky C a Fortran • Verze 1.1 • Oprava nějvětších nedostatků • Implementována • Verze 1.2 • Přechodá verze (před MPI-2) • Rozšíření standardu M P1-1 Luděk Matýska (Fl MU) MPI MPI-2.0 • Experimentální implementace plného standardu • Rozšírení • Paralelní 1/0 • Jednosměrné operace (put, get) • Manipulace s procesy • Vazba na C++ i Fortran 90 MPI Jaro 2016 5 / 42 MPI-3.0 • Snaha odstranit nedostatky předchozích verzí a reagovat na vývoj v oblasti hardware (zejména multicore procesory), viz http://www.mpi-forum.org/ o Pracovní skupiny • Collective Operations and Topologies • Backward Compatibility • Fault Tolerance • Fortran Bindings • Remote Memory Access • Tools Support • Hybrid Programming • Persistency • Aktuální standard Luděk Matýska (Fl MU) MPI Jaro 2016 6 / 42 Cíle návrhu MPI Přenositelnost • Definice standardu (API) • Vazba na různé programovací jazyky • Nezávislé implementace Výkon • Nezávislá optimalizace pro konkrétní hardware 9 Knihovny, možnost výměny algoritmů • Např. nové verze kolektivních algoritmů Funkcionalita • Snaha pokrýt všechny aspekty mezi procesorové komunikace Luděk Matýska (Fl MU) MPI Jaro 2016 7 / 42 Cíle II • Specifikace knihovny pro podporu předávání zpráv o Určena pro paralelní počítače, clustery i Gridy • Zpřístupnění paralelního hardware pro • Uživatele • Autory knihoven • Vývojáře nástrojů a aplikací Luděk Matýska (Fl MU) MPI Jaro 2016 8/42 Core MPI MPLInit MPLComm_Size MPLComm_Rank MPLSend MPLRecv MPLFinalize Inicializace MPI Zjištění počtu procesů Zjištění vlastní identifika Zaslání zprávy Přijetí zprávy Ukončeni MPI Luděk Matýska (Fl MU) MPI Inicializace MPI • Vytvoření prostředí • Definuje, že program bude používat MPI knihovny • Nemanipuluje explicitně s procesy Identifikace prostredí • Paralelní (distribuovaný) program potřebuje znát • Kolik procesů se účastní výpočtu • Jaká je „moje" identifikace • MPLComm_size(MPLCOMM_WORLD, &size) • Vrací počet procesů sdílejících komunikátor MPLCOMIVLWORLD (viz dále) • MPLComm_rank(MPLCOMM_WORLD, &rank) o Vrací číslo procesu Luděk Matýska (Fl MU) MPI Jaro 2016 11 / 42 Práce se zprávami • Primitivní model: • Proces A posílá zprávu: operace send • Proces B přijímá zprávu: operace receive • Celá řada otázek: • Jak vhodně popsat data? • Jak specifikovat proces (kterému jsou data určena) • Jak přijímající pozná, že data patří jemu? • Jak poznáme (úspěšné) dokončení těchto operací? Luděk Matýska (Fl MU) MPI asický přístup • Data posíláme jako proud bytů • Je úkolem posílajícího a přijímajícího data správně nastavit a rozpoznat • Každý proces má jedinečný identifikátor • Musíme znát identifkátor příjemce/vysílajícího • Broadcast operace • Můžeme specifikovat příznak (tag) zprávy pro snazší rozpoznání (např. pořadové číslo zprávy) • Synchronizace • Explicitní spolupráce vysílajícího a přijímajícího • Definuje pořadí zpráv Luděk Matýska (Fl MU) MPI Jaro 2016 13 / 42 Klasický přístup II send(buffer, len, destination, tag) • buffer obsahuje data, jeho délka je len • Zpráva je zaslána procesu s identifikací 'destination • Zpráva má příznak tag recv(buffer, maxlen, source, tag, actlen) • Zpráva bude přijata do pamětové oblasti specifikované položkou buffer jehož délka je maxlen Skutečná délka přijaté zprávy je actlen (actlen► Send skončí když jsou všechna data v bufferu • nepoužije se —>► Send skončí když jsou data přijata odpovídajícím Receive • Synchronní mod • Blokující volání • Když se dokončí Send, data byla přijata odpovídajícím Receive (synchronizace) Luděk Matýska (Fl MU) MPI Jaro 2016 Komunikační mody II Bufferovaný mod • Buffer na straně aplikace (programátora) • Blokující i neblokující - po dokončení jsou data v user bufferu Ready mod • Receive musí předcházet send (připraví cílový buffer) • Jinak chyba Luděk Matýska (Fl MU) MPI Jaro 2016 21 / 42 Základní send operace • Blokující send • MPI_SEND(start, count, datatype, dest, tag, comm) • Trojice (start, count, datatype) definuje zprávu 9 dest definuje cílový proces, a to relativně vzhledem ke komunikátoru comm • Když operace skončí, znamená to • Všechna data byla systémem akceptována • Buffer je možné okamžitě znovu použít • Příjemce nemusel ještě data dostat Luděk Matýska (Fl MU) MPI Jaro 2016 22 / 42 Základní receive operace • Blokující operace • MPI_RECV(start, count, datatype, source, tag, comm, status) • Operace čeká dokud nedorazí zpráva s odpovídající dvojicí (source, tag) • source je identifikátor odesílatele (relativně vůči komunikátoru comm) nebo MPLANY_SOURCE • status obsahuje informace o výsledku operace • Obsahuje jaké příznak zprávy a identifikátor procesu při použití specifikací MPI_ANY_TAG a M P LA N Y_S O URČE) • Pokud přijímaná zpráva obsahuje méně než count bloků, není to identifikováno jako chyba (je poznačeno v status) 9 Přijetí více jak count bloků je chyba Luděk Matýska (Fl MU) MPI Jaro 2016 23 / 42 Krátký Send/Receive protokol • Plně duplexní komunikace • Každá zasílaná zpráva odpovídá přijímané zprávě • int MPI_Sendrecv(void *sendbuf, int sendcnt, MPI_Datatype sendtype, int dest, int sendtag, void *recbuf, int recent, MPI_Datatype reevtyp int source, int reevtag, MPI.Comm comm, MPI.Status *status) Luděk Matýska (Fl MU) MPI Jaro 2016 Asynchronní komunikace • Neblokující operace send • Buffer k dipozici až po úplném dokončení operace • Operace send i receive vytvoří požadavek • Následně lze zjištovat stav požadavku • Volání • int MPI_Isend(void *buf, int cnt, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm, MPI_Request *request) int MPI_Irecv(void *buf, int cnt, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Request *request) Luděk Matýska (Fl MU) MPI Jaro 2016 25 / 42 Asynchronní operace II a (Blokující) čekání na výsledek operace • int MPI.Wait(MPI.Request *request, MPI.Status *status) int MPI_Waitany(int cnt, MPI_Request *array_of.requests, int *index, MPI.Status *status)I int MPI_Waitall(int cnt, MPI_Request *array_of.requests, MPI_Status *array_of.statuses) Luděk Matýska (Fl MU) MPI Jaro 2016 26 / Asynchronní operace III 9 Neblokující zjištění stavu • int MPI.Test (MPI.Request *request, int *flag, MPI.Status *status) int MPI_Testany(int cnt, MPI_Request *array_of.requests, int *flag, int *index, MPI_Status *status) int MPI_Testall(int cnt, MPI_Request *array_of.requests, int *flag, MPI_Status *array_of.statuses) • Uvolnění požadavku int MPI_Request_free(MPI_Request *request) Luděk Matýska (Fl MU) MPI Jaro 2016 27 / Trvalé (persistentní) komunikační kanály o Neblokující • Spojeny ze dvou „půl "-kanálů ■v • Životní cyklus • Create (Start Complete)* Free • Vytvořeny, pak opakovaně používány následně zrušeny Luděk Matýska (Fl MU) MPI Jaro 2016 28 / 42 Persistentní kanál - vytvorení int MPI_Send_init(void *t>uf, int cnt, MPI_Datatype datatype int dest, int tag, MPI_Comm coram, MPI_Request *request) int MPI_Recv_init(void *buf, int cnt, MPI_Datatype datatype int dest, int tag, MPI_Comm comm, MPI_Request *request) Luděk Matýska (Fl MU) MPI Jaro 2016 29 / Přenos Zahájení přenosu (Start) • int MPI.Start (MPI.Request *request) int MPI_Startall(int cnt, MPI_Request *array_of.request) Zakončení přenosu (Complete) • Jako u asynchronních (wait, test, probe) Luděk Matýska (Fl MU) MPI Jaro 2016 30 / 42 Zrušení kanálu • Ekvivalentní zrušení odpovídajícího požadavku int MPI_Cancel(MPI_Request *request) Kolektivní operace • Operace provedené současně všemi procesy v rámci skupiny • Brodcast: MPI.BCAST • Jeden proces (root) pošle data všem ostatním procesům • Redukce: MPI_REDUCE • Spojí data ode všech procesů ve skupině (komnikátoru) a vrátí jednomu procesu • Často je možné skupinu příkazů send/receive nahradit bcast/reduce o Vyšší efektivita (bcast/reduce optimalizováno pro daný hardware) Luděk Matýska (Fl MU) MPI Jaro 2016 32 / 42 Kolektivní operace II Další operace • alltoall: výměna zpráv mezi všemi • bcast/reduce realizuje tzv. scatter/gather model Speciální redukce • min, max, sum, . . . • Uživatelsky definované kolektivní operace Luděk Matýska (Fl MU) MPI Jaro 2016 33 / 42 Virtuální topologie • MPI umožňuje definovat komunikační vzory odpovídající požadavkům aplikace • Ty jsou v dalším kroku mapovány na konkrétní komunikační možnosti použitého hardware • Transparentní • Vyšší efektivita při psaní programů • Přenositelnost • Program není svázán s konkrétní topologií použitého hardware • Možnost nezávislé optimalizace Luděk Matýska (Fl MU) MPI Jaro 2016 34 / 42 Datové typy • Mapa typu • Typemap = {(type0, disp0),..., (typen_i, dispn_i)} • Signatura typu • Typesig = {type0,..., typen_i)} • Příklad: • MPLINT == {(int.O)} Luděk Matýska (Fl MU) MPI Jaro 2016 35 / 42 Rozsah a velikost • MPLType_extent(MPLDatatype Type, MPLAint *extent) • MPLType_size(MPLDatatype Type, int *size) • Příklad: • Type = {(double,0),(char,8)} 9 extent = 16 • size = 9 Luděk Matýska (Fl MU) MPI Jaro 2016 36 / 42 Konstrukce datatypů • Souvislý datový typ • int MPI_Type_contiguous(int count, MPI_Datatype oldtype, MPI_Datatype *newtype) • Vektor • int MPI_Type_vector(int count int blocklength, int stride, MPI_Datatype oldtype, MPI_Datatype *newtype) int MPI_Type_hvector(int count int blocklength, int stride, MPI_Datatype oldtype, MPI_Datatype *newtype) Luděk Matýska (Fl MU) MPI Jaro 2016 37 / 42 Konstrukce datatypů II 9 Indexovaný datový typ • MPI_Type_indexed(int count, int *array_of_blocklengths, int *array_of.displacements, MPI_Datatype oldtype MPI_Datatype *newtype) MPI_Type_hindexed(int count, int *array_of_blocklength, int *array_of.displacements, MPI_Datatype oldtype MPI_Datatype *newtype) • Struktura • MPI_Type_struct(int count, int *array_of_blocklengths, MPI_Aint *array_of.displacements, MPI_Datatype *array_of_types, MPI_Datatype *newtype) Luděk Matýska (Fl MU) MPI Jaro 2016 38 / Konstrukce datatypů III Potvrzení definice datového typu • int MPI_Type_commit(MPI_Datatype *datatype) Krokové (strided) datové typy • Mohou obsahovat „díry" • Implementace může optimalizovat způsob práce • Příklad: Každý druhý prvek vektoru • Může skutečně složit" o Může ale také poslat celý vektor a druhá strana vybere jen specifikované typy Luděk Matýska (Fl MU) MPI Jaro 2016 39 / 42 Operace nad soubory • Podpora až od MPI-2 • „Paralelizace" souborů • Základní pojmy file etype • view file size file handle displacement filetype offset file pointer Luděk Matýska (Fl MU) MPI Jaro 2016 40 / 42 Operace nad soubory II Umístění Synch Koordinace nekolektivní kolektivní explicitní blokující MPLFile_read_at MPLFi e_read_at_all offset MPLFile_write_at MPLFi e_write_at_all neblokující & MPLFile_iread_at MPLFi e_read_at_all_begin split collect. MPLFi e_read_at_all_end MPLFile_iwrite_at MPLFi MPLFi e_write_at_a 1 Lbegi n e_write_at_a 1 Lend individuální blokující MPLFile_read MPLFi e_read_all file ptrs MPLFile.write MPLFi e_write_all neblokující & split collect. MPLFileJread MPLFi MPLFi e_read_all_begin e_read_all_end MPLFileJwrite MPLFi MPLFi e_write_all_begin e_write_all_end sd ílený blokující MPLFile_read_shared MPLFi e_read_ordered file ptr. MPLFile_write_shared MPLFi e_write_ordered neblokující & MPLFile_iread_shared MPLFi e_read_ordered_begin split collect. MPLFi e_read_ordered_end M PI_File_iwrite_shared MPLFi e_write_ordered_begin split collect. MPLFi e_write_ordered_end Luděk Matýska (Fl MU) MPI Jaro 2016 41 / 42 MPI a optimalizující překladače • Při asynchronním použití se mění hodnoty polí, o nichž překladač nemusí vědět • Kopírování parametrů způsobí ztrátu dat call user(a, rq) call MPI_WAIT(rq, status, ierr) write (*,*) a subroutine user(buf, request) call MPI_IRECV(buf,...,request,...) end o V tomto případě se v hlavním programu vypíše nesmyslná hodnota ,,a", protože se při návratu z ,,user" zkopíruje aktuální hodnota; přitom operace receive ještě nebyla dokončena Luděk Matýska (Fl MU) MPI Jaro 2016 42 / 42