IA039 Message Passing Interface, MPI Paralelní programování ■ 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 Prostředí/Systémy ■ Parallel Virtual Machine, PVM ■ Primárně určen pro distribuované prostředí ■ Message Passing Interface, MPI ■ Především podpora meziprocesorové komunikace ■ Linda (Koordinační jazyk) Expliciní task parallelismus ■ Komunikace přes sdílenou plochu IA039 3 Message Passing Interface ■ Komunikační rozhraní pro paralelní programy ■ Definováno API ■ Standardizováno ■ Řada nezávislých implementací * Možnost optimalizace pro konkrétní hardware * Určité problémy se skutečnou interoperabilitou IA039 4 Vývoj MPI ■ 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 MPI-1 IA039 5 Jaro 2012 MPI-2.0 ■ Experimentální implementace plného standardu ■ Rozšíření ■ Paralelní l/O ■ Jednosměrné operace (put, get) ■ Manipulace s procesy ■ Vazba na C++ i Fortran 90 ■ Aktuální standard má verzi 2.2 IA039 6 Jaro 2012 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 1A039 ■ Persistency 7 jam 2012 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 IA039 8 Jaro 2012 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í IA039 9 Core MPI MPLInit Inicializace MPI MPLComm_Size Zjištění počtu procesů MPLComm_Rank Zjištění vlastní identifikace MPLSend Zaslání zprávy MPLRecv Přijetí zprávy MPLFinalize Ukončeni MPI IA039 10 Inicializace MPI ■ Vytvoření prostředí ■ Definuje, že program bude používat MPI knihovny ■ Nemanipuluje explicitně s procesy IA039 11 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 MPLCOMIVLWORLD (viz dále) ■ MPLComm_rank(MPLCOMM_WORLD, &rank) ■ Vrací číslo procesu IA039 12 Jaro 2012 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í? IA039 13 Jaro 2012 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 ■ 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 IA039 14 Jaro 2012 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) IA039 21 Jaro 2012 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 IA039 22 Jaro 2012 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 IA039 23 Jaro 2012 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_SOURCE * 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_SOURCE) * 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 IA039 24 Jaro 2012 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) IA039 25 Jaro 2012 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_I send (void *t>uf, 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) IA039 26 Jaro 2012 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) 27 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.request int *flag, int *index, MPI_Status *status) int MPI_Testall(int cnt, MPI_Request *array_of.request int *flag, MPI_Status *array_of.statuses) Uvolnění požadavku int MPI_Request_free(MPI_Request *request) IA039 28 Trvalé (persistentní) komunikační kanály ■ Neblokující ■ Spojeny ze dvou „půT-kanálů ■ Životní cyklus ■ Create (Start Complete)* Free ■ Vytvořeny, pak opakovaně používány, následně zrušeny IA039 29 Jaro 2012 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) IA039 30 Jaro 2012 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) IA039 31 Jaro 2012 Zrušení kanálu ■ Ekvivalentní zrušení odpovídajícího požadavku int MPI_Cancel(MPI_Request *request) IA039 32 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) IA039 33 Jaro 2012 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 IA039 34 Jaro 2012 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 IA039 35 Jaro 2012 Datové typy ■ Mapa typu ■ Typemap = {(type0, disp0),..., (typen_u dispn_i)} ■ Signatura typu ■ Typesig = {type0,..., type^)} ■ Příklad: ■ MPLINT =={(int,0)} IA039 36 Jaro 2012 Rozsah a velikost ■ MPLType_extent(MPLDatatype Type, MPI_Aint *extent) ■ MPLType_size(MPLDatatype Type, int *size) ■ Příklad: - Type = {(double,0),(char,8)} ■ extent = 16 ■ size = 9 IA039 37 Jaro 2012 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) IA039 38 Jaro 2012 Konstrukce datatypů II ■ 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) IA039 39 Jaro 2012 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 IA039 40 Jaro 2012 Operace nad soubory Podpora až od MPI-2 „Paralelizace" souborů Základní pojmy file etype ■ view file size file handle displacement f i lety pe offset file pointer IA039 41 Jaro 2012 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 MPI_File_read_at_all_begin MPLFile_read_at_all_end MPLFile_write_at_all_begin MPLFile_write_at_all_end individuální file ptrs blokující MPLFile_read MPLFile_write MPLFile_read_all MPLFile_write_all neblokující & split collect. MPLFileJread MPLFileJwrite M P1 _Fi le_read_al Lbeg i n MPLFile_read_all_end MPLFile_write_all_begin MPLFile_write_all_end 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 MPLFile_write_ordered_begin MPLFile_write_ordered_end IA039 42 Jaro 2012 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 IA039 43 Jaro 2012 Další rozvoj ■ MPI-1 standard neobsahuje ■ Explicitní operace nad sdílenou pamětí ■ Specifickou podporu ze strany operačního systému (aktivní zprávy, příjem zpráv řízený událostmi, ...) ■ Ladicí nástroje ■ Explicitní podporu vláken (základy jsou ve verzi 2.0) je však thread-safe ■ Podporu správy úloh (je ve verzi 2.0) ■ I/O (je ve verzi 2.0) IA039 44 Jaro 2012