BMDFM - BMDFM
A Binary Modular Dataflow Machine ( BMDFM ) olyan szoftver, amely lehetővé teszi egy alkalmazás párhuzamos futtatását megosztott memória- szimmetrikus többprocesszoros (SMP) számítógépeken, több processzor használatával, az egyes alkalmazások futtatásának felgyorsítása érdekében. A BMDFM automatikusan azonosítja és kihasználja a párhuzamosságot a korábban szekvenciális programból származtatott adatfolyam- utasítássorozatok statikus és főként dinamikus ütemezése miatt .
BMDFM dinamikus ütemezésének alrendszer végrehajt egy szimmetrikus többprocesszoros (SMP) emulációs egy címkézett-token adatfolyam gép , hogy az átlátszó adatfolyam szemantikája a kérelmeket. Nincs szükség párhuzamos végrehajtásra vonatkozó irányelvekre.
Háttér
Manapság a párhuzamos megosztott memória szimmetrikus multiprocesszorok (SMP) összetett gépek, amelyeknél a nagy teljesítmény elérése érdekében egyszerre számos építészeti szempontot kell kezelni. A legújabb számítástechnikai számítástechnikai árucikkek sok szorosan összekapcsolt maggal rendelkezhetnek (jó példa erre az Intel ( Pentium ) vagy az IBM ( POWER ) többmagos processzorain alapuló SMP gépek ). A számítógépgyártók közleményei szerint a SMP csomópontonkénti magok száma a tervek szerint évente megduplázódik.
A többmagos processzorok célja a szoftver által azonosított szálszintű párhuzamosság kihasználása. Ennélfogva a legnagyobb kihívást az jelenti, hogy hatékony megoldást találjunk a többmagos processzorok erejének kihasználására egy alkalmazás program párhuzamos feldolgozásához. A fork-join futásidejű könyvtárral történő statikus párhuzamosítás létező OpenMP paradigmája csak a hurokintenzív rendszeres tömbalapú számításoknál működik jól, ugyanakkor a fordítási idő párhuzamosítási módszerek általában gyengék, és szinte nem alkalmazhatók szabálytalan alkalmazásoknál:
- Sok olyan művelet van, amely nem determinisztikus időbe telik, és megnehezíti, hogy pontosan mikor válnak elérhetővé bizonyos adatok.
- A többszintű gyorsítótárakkal rendelkező memória-hierarchia kiszámíthatatlan memória-hozzáférési késleltetéssel rendelkezik.
- Többfelhasználós módban mások kódjai felhasználhatják az erőforrásokat vagy lelassíthatják a számítás egy részét oly módon, hogy a fordító nem tud elszámolni vele.
- A fordítási idejű eljárásközi és feltételközi optimalizálás nehéz (gyakran lehetetlen), mert a fordítók nem tudják kitalálni, hogy a feltételes melyik irányba halad, vagy nem képesek optimalizálni egy függvényhívás során.
A BMDFM átlátszó adatfolyam-szemantikája
Egy új BMDFM (Binary Modular Data-Flow Machine) technológia főként dinamikus ütemezést használ az alkalmazás párhuzamosságának kiaknázására, így a BMDFM elkerüli a fordítási idő módszerek említett hátrányait. A BMDFM egy párhuzamos programozási környezet a többmagos SMP számára, amely:
- A hagyományos programozási paradigma, amely nem igényel irányelveket a párhuzamos végrehajtáshoz.
- A párhuzamosság átlátható (implicit) kihasználása természetes és terhelés-kiegyensúlyozott módon, a rendszer összes elérhető többmagos processzorának automatikus felhasználásával.
A BMDFM az ismert építészeti elvek előnyeit egyetlen hibrid architektúrába ötvözi, amely képes kihasználni az alkalmazások implicit párhuzamosságát , amelyek elhanyagolható dinamikus ütemezéssel rendelkeznek és nincsenek szűk keresztmetszetek. Főként az alapvető adatfolyam elvét alkalmazzák. Az adatfolyam elv azt mondja: "Egy utasítás vagy egy függvény futtatható, amint az összes argumentuma készen áll. Egy adatfolyam-gép futás közben kezeli az egyes adatok címkéit. Az adatokat kész címkével jelölik, amikor az adatokat kiszámították. msgstr "kész argumentumokkal végrehajtják, és készen jelzik eredményeredményeiket".
A BMDFM fő jellemzője, hogy hagyományos programozási paradigmát biztosít a legfelső szinten, az úgynevezett átlátszó adatfolyam szemantikát. A felhasználó úgy értelmezi a BMDFM-et, mint egy virtuális gépet (VM), amely az alkalmazás összes utasítását párhuzamosan futtatja, az összes párhuzamosító és szinkronizáló mechanizmus teljesen átlátható. Egy alkalmazás program utasításai normál operátorok, amelyekből egyetlen szálú program állhat - tartalmaznak változó hozzárendeléseket, feltételes feldolgozást, ciklusokat, függvényhívásokat stb.
Tegyük fel, hogy megvan az alább látható kódrészlet:
(setq a (foo0 i)) # a = foo0(i);
(setq b (foo1 (+ i 1))) # b = foo1(i+1);
(setq b (++ b)) # b++;
(outf "a = %d\n" a) # printf("a = %d\n", a);
(outf "b = %d\n" b) # printf("b = %d\n", b);
A két első állítás független, ezért a BMDFM adatfolyam-motorja különböző processzorokon vagy processzormagokon futtathatja őket. A két utolsó állítás párhuzamosan is futhat, de csak az "a" és "b" kiszámítása után. Az adatfolyam-motor automatikusan felismeri a függőségeket, mivel képes futás közben dinamikusan felépíteni egy adatfolyam-grafikont. Ezenkívül az adatfolyam-motor helyesen elrendeli a kimeneti adatfolyamot, hogy az eredményeket egymás után adja ki. Így a nem rendelt feldolgozás után is természetes módon jelennek meg az eredmények.
Tegyük fel, hogy a fenti kódrészlet most be van ágyazva egy hurokba:
(for i 1 1 N (progn # for (i = 1; i <= N; i++) {
(setq a (foo0 i)) # a = foo0(i);
(setq b (foo1 (+ i 1))) # b = foo1(i + 1);
(setq b (++ b)) # b++;
(outf "a = %d\n" a) # printf("a = %d\n", a);
(outf "b = %d\n" b) # printf("b = %d\n", b);
)) # }
A BMDFM adatfolyam-motorja az "a" és a "b" változókat egyedi kontextusban fogja tartani minden iterációnál. Valójában ezek a változók különböző másolatai. A kontextusváltozó mindaddig létezik, amíg az utasításfogyasztók nem hivatkoznak rá. A későbbi, nem hivatkozott összefüggések futás közben gyűjtött szemétek lesznek. Ezért az adatfolyam-motor kihasználhatja az iteráción belüli lokális párhuzamosságot és a globális párhuzamosságot, valamint egyszerre több iterációt is futtathat.
A BMDFM építészete
A BMDFM alapkoncepcióját a következő ábra mutatja. A javasolt megközelítés az alapul szolgáló árupiaci SMP hardveren alapul, amely a piacon elérhető. Normális esetben az SMP gyártók saját SMP operációs rendszerüket (OS) biztosítják SVR4 / POSIX UNIX interfésszel (Linux, HP-UX, SunOS / Solaris, Tru64OSF1, IRIX, AIX, BSD, MacOS stb.). Az SMP operációs rendszer tetején a többszálú adatfolyam-futásidejű motor szoftveres emulációt hajt végre az adatfolyam-gépen. Egy ilyen virtuális gép rendelkezik interfészekkel a virtuális gép nyelvéhez és a C-hez, amely biztosítja az átlátszó adatáramlás szemantikáját a hagyományos programozáshoz.
Mint látható, a BMDFM több építészeti elv hibridjeként épül fel:
- MIMD (Multiple Instruction Stream, Multiple Data Streams), amelyet az áru SMP tart fenn.
- Az implicit párhuzamos végrehajtást az adatfolyam emuláció biztosítja.
- A Von-Neumann számítási elv jó a Front-end Control Virtual Machine megvalósításához.
A következő ábra részletesebb képet mutat a BMDFM architektúráról:
Egy alkalmazás programját (input input program) három szakaszban dolgozzák fel: előzetes kód-átszervezés (kód-átszervezés), az utasítások statikus ütemezése (statikus ütemező) és fordítás / betöltés (fordító, betöltő). A statikus ütemezési szakaszok utáni kimenet egy több fürtből álló folyamat, amely a többszálas motort táplálja a szűk keresztmetszetek elkerülése érdekében tervezett interfészen keresztül. A több klaszter áramlása úgy tekinthető, mint egy összeállított bemeneti program, amely felosztott klaszterekre oszlik, amelyben az összes címet feloldják és kontextus információkkal bővítik. Az osztott csoportokba bontás lehetővé teszi többszálas betöltést. A kontextus információ lehetővé teszi az iterációk párhuzamos feldolgozását. A figyelő szál megrendelés nélküli megrendelés után rendeli a kimeneti adatfolyamot.
A BMDFM dinamikus ütemezésű alrendszer a tagged-token adatfolyam-gép hatékony SMP-emulátora. A megosztott memóriakészlet három fő részre oszlik: bemeneti / kimeneti csengőpuffer port (IORBP), adatpuffer (DB) és működési sor (OQ). A kezelőfelület virtuális gépe statikusan ütemez egy bemeneti alkalmazásprogramot, és a bemeneti program fürtözött utasításait és adatait az IORBP-be helyezi. A gyűrűpuffer szolgáltatási folyamatok (IORBP PROC) az adatokat áthelyezik a DB-be, az utasításokat pedig az OQ-ba. A műveletsor szolgáltatási folyamatok (OQ PROC) az utasításokat végrehajtásra készként jelölik meg, ha a szükséges operandusok adatai hozzáférhetők. A végrehajtási folyamatok (CPU PROC) utasításokat hajtanak végre, amelyeket készként jelölnek meg, és kiszámított adatokat adnak ki a DB-be vagy az IORBP-be. Ezenkívül az IORBP PROC és az OQ PROC felelős a memória felszabadításáért a kontextusok feldolgozása után. A kontextus egy különleges egyedi azonosító, amely a különböző iterációs testekben lévő adatok másolatát jelöli a tagged-token adatfolyam-architektúrának megfelelően. Ez lehetővé teszi a dinamikus ütemező számára, hogy több iterációt párhuzamosan kezeljen.
Az SMP operációs rendszer alatt futó folyamatok elfoglalják az összes rendelkezésre álló valós gépi processzort és processzormagot. Annak érdekében, hogy több folyamat egyidejűleg férjen hozzá ugyanazokhoz az adatokhoz, a BMDFM dinamikus ütemező SVR4 / POSIX szemafor műveletekkel lezárja az objektumokat a megosztott memóriakészletben. A zárolási házirend több írásvédett hozzáférést és kizárólagos hozzáférést biztosít a módosításokhoz.
Támogatott platformok
Minden ANSI C és POSIX - UNIX System V (SVR4) támogató gépen futtatható a BMDFM.
A BMDFM teljes szálú verzióként áll rendelkezésre:
- x86 : Linux / 32, FreeBSD / 32, OpenBSD / 32, NetBSD / 32, MacOS / 32, SunOS / 32, UnixWare / 32, Minix / 32, Android / 32, Win-Cygwin / 32, Win-UWIN / 32, Win-SFU-SUA / 32;
- x86-64 : Linux / 64, FreeBSD / 64, OpenBSD / 64, NetBSD / 64, MacOS / 64, SunOS / 64, Android / 64, Win-Cygwin / 64;
- VAX : Ultrix / 32;
- Alpha : Tru64OSF1 / 64, Linux / 64, FreeBSD / 64, OpenBSD / 64;
- IA-64 : HP-UX / 32, HP-UX / 64, Linux / 64, FreeBSD / 64;
- XeonPhiMIC : Linux / 64;
- MCST-Elbrus : Linux / 32, Linux / 64;
- PA-RISC : HP-UX / 32, HP-UX / 64, Linux / 32;
- SPARC : SunOS / 32, SunOS / 64, Linux / 32, Linux / 64, FreeBSD / 64, OpenBSD / 64;
- MIPS : IRIX / 32, IRIX / 64, Linux / 32, Linux / 64;
- MIPSel : Linux / 32, Linux / 64, Android / 32, Android / 64;
- PowerPC : AIX / 32, AIX / 64, MacOS / 32, MacOS / 64, Linux / 32, Linux / 64, FreeBSD / 32, FreeBSD / 64;
- PowerPCle : Linux / 32, Linux / 64;
- S / 390 : Linux / 32, Linux / 64;
- M68000 : Linux / 32;
- ARM : Linux / 32, Linux / 64, FreeBSD / 64, Android / 32, Android / 64, MacOS / 64;
- ARMbe : Linux / 64;
- RISC-V : Linux / 32, Linux / 64;
- és egy korlátozott egyszálas verzió az x86-hoz : Win / 32.
Összegzés
Az adatfolyam-rendszereket valószínűleg érdemes még egyszer megnézni. A közösség megosztott, elosztott-megosztott hardveres megvalósítási cikluson ment keresztül, mióta az adatfolyam-tevékenység csúcspontja van, és megfelelőnek tűnik az az idő alatt tanultak egy része szoftveralapú rendszereken.
A BMDFM kényelmes párhuzamos programozási környezet és hatékony futásidejű motor a többmagos SMP-hez, több építészeti paradigma (von-Neumann, SMP és adatfolyam) MIMD-egységének köszönhetően:
- Eleinte ez egy hibrid adatfolyam-emulátor, amely többszálasan fut az áru SMP-n. Az SMP biztosítja a MIMD-t, míg az adatfolyam az implicit párhuzamosságot használja ki.
- Másodszor ez egy hibrid, többszálú adatfolyam-futásidejű motor, amelyet von-Neumann front-end virtuális gép vezérel. Az adatfolyam-futásidejű motor tagged-token kontextus szerinti párhuzamos utasításokat hajt végre (szemben a korlátozott villa-csatlakozási paradigmával), míg a von-Neumann front-end virtuális gép inicializálja a kontextusokat, és az adatfolyam-futásidejű motort rendezett utasításfürtökkel látja el.
- Harmadszor a statikus és a dinamikus párhuzamosítás hibridje. A von-Neumann front-end virtuális gép statikusan megpróbálja felosztani az alkalmazást párhuzamosan rendezett utasításfürtökre, miközben az adatfolyam-futásidejű motor dinamikusan kiegészíti a statikus párhuzamosítási módszereket.
A BMDFM-et a párhuzamos futásidejű motor (a hagyományos fork-join futásidejű könyvtár helyett) szerepében kívánják használni, amely képes szabálytalan alkalmazásokat párhuzamosan automatikusan futtatni. A tetején lévő átlátszó adatfolyam-szemantika miatt a BMDFM egyszerű párhuzamosítási technika az alkalmazás-programozók számára, ugyanakkor sokkal jobb párhuzamos programozási és fordítási technológia a többmagos SMP számítógépek számára.
