Osztott rendszerek specifikációja és implementációja

Leírás

A tárgy célja párhuzamos és elosztott rendszerek alkalmazási lehetőségeinek megismerése, elemi párhuzamos programozási készségek megszerzése. Programozási feladatokat fogalmazunk meg párhuzamos programok relációs programozási modelljében. A megoldást a specifikáció lépésenkénti finomításával állítjuk elő. Nevezetes feladatokat oldunk meg (asszociatív művelet eredménye, atadcsatorna tétele, párhuzamos elemenkénti feldolgozás, stb.). A kapott absztrakt programokat párhuzamos és elosztott programozást támogató magas szintű nyelvi eszközök felhasználásával implementáljuk. Megvizsgáljuk a különböző implementációk hatékonyságát.

Tematika

1. Párhuzamos programok reláció alapú modellje: feladat, specifikációs feltételek.
2. Folyamat, absztrakt program, pártatlan ütemezés, összefésüléses szemantika.
3. Absztrakt program viselkedési relációja. A leggyengébb előfeltétel általánosításai.
4. Elérhető állapotok. A megoldás definíciója.
5. Levezetési szabályok: haladási tulajdonságokra vonatkozó tételek, variánsfüggvény alkalmazása. Struktúrális indukció,csoda kizárásának elve.
6. Asszociatív művelet eredményének kiszámítása, maximumkeresés, párhuzamos bináris összeadás.
7. Programkonstrukciók: unió, szuperpozíció, szekvencia. Programkonstrukciós tételek. Lokalitás tétel.
8. Kommunikáció (aszinkron,szinkron). Üzenettovábbítás. Csatornaváltozók.
9. Elágazás (fork), multiplexer, Adatcsatorna.

Tantárgyi adatok

Előfeltétel:

• IP-08bPROGEG : Programozás
• IP-08bPNY1EG : Programozási nyelvek C++

Előadás:

• Tárgy kódja: IP-08bORSIE
• Kredit: 3
• Heti óraszám: 2
• Követelmények:
  • Az előadás látogatása kötelező, 3-nál több hiányzás esetén a vizsgázás lehetősége megtagadható.
  • Vizsgát tenni a félév végén a Neptunban meghirdetett időpontokban lehet. Mivel a tárgy indul keresztfélévben is, így egy félévben maximum kétszer lehet vizsgát tenni.

Gyakorlat:

• Tárgy kódja: IP-08bORSIG
• Kredit: 2
• Heti óraszám: 2
• Követelmények:
  • A gyakorlat látogatása kötelező, 3-nál több hiányzás esetén a jegy megtagadható.
  • zárthelyi dolgozatok: A tárgyból a félév során két zárthelyi dolgozat lesz. Az első zárhelyi a gyakorlat első részéből az őszi szünet utáni hetekben, a második pedig második részből a szorgalmi időszak utolsó hetén. A zárthelyik az előadás időpontjában és helyszínén lesznek megtartva és 90 perc áll rendelkezésre a megírásához. Mindkét zárthelyiből legalább elégséges eredményt kell elérni. A zárthelyik javítására/pótlására a pótzárthelyi alkalmával nyílik lehetőség (akár mindkét zárthelyi javítható, de ebben az esetben is csak 90 perc áll rendelkezésre). A pótzárthelyi a vizsgaidőszak első hetében lesz megtartva.
  • +/- feladatok: Az órán tanult definíciókból, tételekből és egyszerűbb feladatokból +/- dolgozatok lesznek. Az értékelése helyes válasz esetén +1, helytelen válasz esetén értelemszerűen -1. A félév végén az összesített eredménynek legalább 0-nak kell lennie.
  • beadandók: A félév során a tárgyól három beadandó kerül kiírásra. A beadandók értékelése százalékosan történik (0-100%). Mindegyik beadandóból külön-külön legalább 50% a minimális követelmény, de a három beadandó átlagának legalább 60%-nak kell lennie. Az első két beadandó egyszerűbb párhuzamos programozási feladatok megvalósítása lesz, a harmadik beadandót a gyakorlaton és előadáson tárgyalt párhuzamosítási mintával (adatcsatorna/pipeline) kell megoldani. A beadandókhoz rövid dokumentációt kell készíteni.
  • géptermi zárthelyi: A szorgalmi időszak utolsó hetében géptermi zárthelyit kell írni, ahol a harmadik beadandóhoz hasonló feladatot (adatcsatorna tételére visszavezethető) kell megoldani. A géptermin 120 perc áll rendelkezésre. Amennyiben a géptermi zárthelyi sikertelen, úgy pót géptermi zárthelyit kell sikeresen teljesíteni, amely a vizsgaidőszak első hetében lesz. A beadandóknál kiemelkedő eredményt elérő diákoknak nem kell géptermi zárthelyit írniuk.

Segédanyagok:

• [ChaMis 88] : Chandy,K.M.-Misra,J.: Parallel program design: a foundation, Addison-Wesley, 1988, (1989).
• [And 91] : Andrews,G.R.: Concurrent Programming, Principles and Practice, Benjamin/Cummings, 1991.
• [Hor 94] : Horváth Z.: Párhuzamos programozás reláció alapú modellje, 1996. jegyzet .... C++ példaprogram .... nem ellenõrzött gyak
• [Fáb 1994] : Fábián G.: Párhuzamos algoritmusok specifikációja osztott objektumokat használó rendszerek esetén UNITY módszerrel (1. rész). Szakdolgozat. 1994.
• [Gyor 95] : Gyorffy L.: Párhuzamos algoritmusok specifikációja osztott objektumokat használó rendszerek esetén UNITY módszerrel (2. rész). Szakdolgozat. 1995.
• [Fót Hor Kozs 95] : Fóthi Á. - Horváth Z. - Kozsik T.: Parallel Elementwise Processing - A Novel Version. in: Proceedings of the Fourth Symposium on Programming Languages and Software Tools, Visegrád, Hungary, June 8-14, 1995 (1995).
• [Gei 94] : Geist, ...: PVM 3 User's Guide and Reference Manual. (Postscript file, ftp://augusta.inf.elte.hu/pub/pvm/ug.ps)
• [Fro 94] : Frohner Ákos: Ada taszkok és randevúk a PVM 3.1-es üzenetküldő rendszerben, 1994.
• [Fro 96] : Frohner Ákos: Párhuzamos programok írását támogató nyelvi eszközök összehasonlítása. Szakdolgozat, 1996. (HTML, augusta.inf.elte.hu)
• [Parsytec] : Parix 1.3.1-PPC Software Documentation. May 1995.
• [PVM 93] : IBM: PVM/6000 User's Guide and Subroutine Reference, Relase 2.0, 1993.
• [Motorola] : Optimizing C Compilation System User's Guide.