IA039: Architektura superpočítačů a náročné výpočty Message Passing Interface Luděk Matýska Fakulta informatiky MU Jaro 2013 Luděk Matýska (Fl MU) Jaro 2013 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) • SPMD • Není synchronizován na úrovni jednotlivých instrukcí • Ekvivalentní MIMD • Message passing určeno pro SPMD/MIMD Luděk Matýska (Fl MU) Jaro 2013 2 / 42 Message Passing Interface • Komunikační rozhraní pro paralelní programy • Definováno API • Standardizováno • 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) Jaro 2013 3 / 42 Vývoj MPI a 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 o Přechodá verze (před MPI-2) • Rozšíření standardu MPI-1 Luděk Matýska (Fl MU) Jaro 2013 4 / 42 MPI-2.0 • Experimentální implementace plného standardu • Rozšíření • Paralelní 1/0 • Jednosměrné operace (put, get) • Manipulace s procesy • Vazba na C++ i Fortran 90 Luděk Matýska (Fl MU) Jaro 2013 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/ • 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) Jaro 2013 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 • Knihovny, možnost výměny algoritmů • Např. nové verze kolektivních algoritmů • Funkcionalita • Snaha pokrýt všechny aspekty meziprocesorové komunikace Luděk Matýska (Fl MU) Jaro 2013 7 / 42 Cíle II • Specifikace knihovny pro podporu předávání zpráv • 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) Jaro 2013 8 / 42 Core MPI MPIJnit MPLComm_Size MPLComm.Rank MPLSend MPLRecv MPLFinalize Inicializace MPI Zjištění počtu procesů Zjištění vlastní identifikace Zaslání zprávy Přijetí zprávy Ukončeni MPI Luděk Matýska (Fl MU) Jaro 2013 9 / 42 Inicializace MPI • Vytvoření prostředí • Definuje, že program bude používat MPI knihovny • Nemanipuluje explicitně s procesy Luděk Matýska (Fl MU) Jaro 2013 10 / 42 Identifikace prostředí • 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 M P LCO M M .WORLD (viz dále) • MPLComm_rank(MPLCOMM_WORLD, &rank) • Vrací číslo procesu Luděk Matýska (Fl MU) Jaro 2013 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? o Jak poznáme (úspěšné) dokončení těchto operací? Luděk Matýska (Fl MU) Jaro 2013 12 / 42 Klasický 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 9 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) Jaro 2013 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ěfové 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í a Když se dokončí Send, data byla přijata odpovídajícím Receive (synchronizace) Luděk Matýska (Fl MU) Jaro 2013 20 / 42 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) Jaro 2013 21 / 42 Základní send operace • Blokující send • MPLSEND(start, count, datatype, dest, tag, comm) • Trojice (start, count, datatype) definuje zprávu • 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) Jaro 2013 22 / 42 Základní receive operace • Blokující operace • MPLRECV(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.S0URCE • status obsahuje informace o výsledku operace • Obsahuje jaké příznak zprávy a identifikátor procesu při použití specifikací MPLANY.TAG a MPLANY_S0URCE) o Pokud přijímaná zpráva obsahuje méně než count bloků, není to identifikováno jako chyba (je poznačeno v status) • Přijetí více jak count bloků je chyba Luděk Matýska (Fl MU) Jaro 2013 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 reevtype, int source, int reevtag, MPI_Comm comm, MPI_Status *status) Luděk Matýska (Fl MU) Jaro 2013 24 / 42 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) Jaro 2013 25 / 42 Asynchronní operace II • (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) Jaro 2013 26 / 42 Asynchronní operace III • 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) Jaro 2013 27 / 42 Trvalé (persistentní) komunikační kanály • Neblokující • Spojeny ze dvou „půl"-kanálů • Životní cyklus • Create (Start Complete)* Free o Vytvořeny, pak opakovaně používány, následně zrušeny Luděk Matýska (Fl MU) Jaro 2013 28 / 42 Persistentní kanál - vytvoření int MPI_Send_init(void *buf, int cnt, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm, 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) Jaro 2013 29 / 42 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) o Jako u asynchronních (wait, test, probe) Luděk Matýska (Fl MU) Jaro 2013 30 / 42 Zrušení kanálu • Ekvivalentní zrušení odpovídajícího požadavku int MPI_Cancel(MPI_Request *request) Luděk Matýska (Fl MU) Jaro 2013 31 / 42 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 • Vyšší efektivita (bcast/reduce optimalizováno pro daný hardware) Luděk Matýska (Fl MU) Jaro 2013 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) Jaro 2013 33 / 42 Virtuální topologie a 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) Jaro 2013 34 / 42 Datové typy • Mapa typu • Typemap — {(type0, disp0),..., (typen_i, dispn_i)} • Signatura typu • Typesig = {type0,..., typen_i)} • Příklad: • MPLINT == {(int.O)} Rozsah a velikost • MPLType_extent(MPLDatatype Type, MPLAint *extent) • MPLType_size(MPLDatatype Type, int *size) • Príklad: • Type = {(double,0),(char,8)} • extent — 16 • size — 9 Luděk Matýska (Fl MU) Jaro 2013 36 / 42 Konstrukce datatypů • Souvislý datový typ • int MPI_Type_contiguous(int count, MPIJDatatype 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) Jaro 2013 37 / 42 Konstrukce datatypů II • Indexovaný datový typ o 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) Jaro 2013 38 / 42 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" • Může ale také poslat celý vektor a druhá strana vybere jen specifikované typy Luděk Matýska (Fl MU) Jaro 2013 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) Jaro 2013 40 / 42 Operace nad soubory II Umístění Synch Koordinace nekolektivní kolektivní explicitní offset blokující MPLFile_read_at MPLFile_write_at MPLFile_read_at_all MPLFile_write_at_all neblokující & split collect. MPLFile_iread_at MPLFile_iwrite_at MPLFile_read_at_alLbegin MPLFile_read_at_alLend M PLFi le_write_at_a 1 Lbegi n MPLFile_write_at_alLend individuální file ptrs blokující MPLFile.read MPLFile.write MPLFile.read_all MPLFile_write_all neblokující & split collect. MPLFileJread MPLFileJwrite MPLFile.read_all.begin MPLFile_read_alLend MPLFile_write_alLbegin MPLFile_write_alLend sdílený file ptr. blokující MPLFile_read_shared MPLFile_write_shared MPLFile_read_ordered MPLFile_write_ordered neblokující & split collect. split collect. MPLFile_iread_shared MPLFile_iwrite_shared MPLFile_read_ordered_begin MPLFile_read_ordered_end M PLFile_write_ordered_begi n MPLFile_write_ordered_end Luděk Matýska (Fl MU) Jaro 2013 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 • 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) Jaro 2013 42 / 42