Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással
    vissza a tantárgylistához   nyomtatható verzió    

    Algoritmusok és adatstruktúrák többmagos környezetben

    A tantárgy angol neve: Algorithms and Data Structures in Multi-core Environment

    Adatlap utolsó módosítása: 2015. április 2.

    Tantárgy lejárati dátuma: 2020. december 31.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar

    Mérnökinformatikus Szak

    Villamosmérnök Szak

    Szabadon választható tantárgy
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VIAUAV13   2/0/0/f 2  
    3. A tantárgyfelelős személy és tanszék Dr. Dudás Ákos,
    4. A tantárgy előadója

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Juhász Sándor

    docens

    Automatizálási és Alkalmazott Informatikai Tanszék

    Dr. Dudás Ákos

    adjunktus

    Automatizálási és Alkalmazott Informatikai Tanszék
    5. A tantárgy az alábbi témakörök ismeretére épít

    Programozási és számítógép-architektúra alapismeretek.

    6. Előtanulmányi rend
    Ajánlott:

    Mérnökinformatikus szakon:

    VIMIAB00 Operációs rendszerek és VIHIAA00 Számítógép-architektúrák

     

    Villamosmérnöki szakon:

    VIIIAB04 Informatika 1

    7. A tantárgy célkitűzése

    A tárgy célja, hogy megismertesse a hallgatókat azokkal az alapvető alacsonyszintű módszerekkel, melyek segítségével alkalmazásokban kihasználhatóvá válik a modern többmagos processzorokban rejlő teljesítmény potenciál. A tantárgy keretében elsősorban alapvető adatszerkezetek (hash táblák, láncolt listák, pufferek és vermek) párhuzamos használatának teljesítmény kérdéseire fókuszálunk, különös tekintettel a cache memóriák optimális kihasználására, valamit a kölcsönös kizárási módszerek helyes megválasztására. Megmutatjuk a zárak használatának teljesítmény vonzatait, valamint foglalkozunk a zárak használatát mellőző (CAS, pre-execution, illetve szabály szerinti kooperáló) megoldások teljesítményviszonyaival is. A fentiek mellett bevezetést nyújtunk a grafikus processzorok kihasználásának lehetőségeiről az adatfeldolgozás területén.

    8. A tantárgy részletes tematikája

    Hét

     

    Előadás anyaga

     

    1.

     

    Algoritmusok teljesítmény vizsgálata, hotspot fogalma, skálázhatóság, gyorsulás, költség függvények, algoritmikus komplexitás.

    2.

     

    Szoros és laza csatolás, a szoftver és hardver rétegek szerepe a teljesítményben. Párhuzamos architektúrák bemutatása (SMP, masszívan párhuzamos rendszerek). 

    3.

     

    Nagyteljesítményű számítógépek megvalósítási problémái. Tér- és időbeli lokalitás, cache áttekintés, prefetch, cache konzisztencia. UMA, NUMA és klaszter architektúrák. Elosztott memóriára épülő párhuzamos környezetek.

    4.

     

    A szuperskalár CPU architektúrától (tipikus pipeline működése, utasítás szintű párhuzamosság, elágazás előrejelzés) a mai modern processzorok működésén át (pl. HyperThreading technológia) a many-core architektúrákig.

    5.

     

    Teljesítmény mérés eszközei és módszerei, Intel VTune Amplifier XE bemutatása, nagyfelbontású időmérés. Mátrix összeadás példája.

    6.

     

    Cache-barát adatstruktúrák, láncolt lista és tömb, hash tábla tervezése.

    7.

     

    Párhuzamos programozás, szál-objektum modell, zárak, szinkronizációs megoldások gyakorlati alkalmazása Windows API és .NET segítségével, spin lock-ok megvalósítása és teljesítmény tesztjük.

    8.

     

    Szálak és zárolás Windows API használatával és .NET környezetben. Zárolási módszerek teljesítmény tesztjei.

    9.

     

    Zármentes módszerek: pre-execution, CAS, interlocked műveletek.

    10.

     

    Párhuzamosítási módszerek, párhuzamos adatstruktúrák többmagos környezetben. Láncolt listával megvalósított verem, sor, hash tábla.

    11.

     

    .NET Task Parallel Library, csoport kommunikációs primitívek (MPI), broadcast algoritmusok, Intel Threading Building Blocks.

    12.

     

    Grafikus kártyák általános célú programozása, masszívan párhuzamos architektúrák, általános GPGPU architektúra. CUDA architektúra és programozási nyelv, OpenCL programozási nyelv.

    13.

     

    CUDA és OpenCL alkalmazás fejlesztése, fejlesztői környezetek, program készítése GPU-ra lineáris algebrai műveletek példáján keresztül.

    14.

     

    Félévközi zárthelyi dolgozat.
    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

    Előadás és számítógépes demonstráció.

    10. Követelmények

    A szorgalmi időszakban:

    (1) Az ismeretek átfogó és részletes áttekintését a szorgalmi időszak alatt 1 alkalommal, az évfolyam terhelési táblázata szerinti időpontban íratott zárthelyivel mérjük, valamint

    (2) A gyakorlást a nagy házi feladat biztosítja, amelynek beadási határideje a szorgalmi időszak vége.

    A félév elismerését jelentő félév végi jegy megszerzésére akkor van lehetőség, ha a hallgató a házi feladatot futtatható állapotban, dokumentációval ellátva, forráskód mellékelésével, határidőre beadta, vagy ezt a pótlási héten pótolta.

    A jegy megszerzésének feltétele a nagy ZH és a nagy házi feladat együttes teljesítése. A házi feladatot 50 %-ban számít be a félévközi jegybe.

    11. Pótlási lehetőségek

    A házi (otthoni) feladatot a szorgalmi időszak végéig be kell adni, annak pótlása a pótlási időszakban lehetséges. A pótlási időszak a kétciklusú képzésben az ún. pótlási hét (a szorgalmi időszak vége és a vizsgaidőszak kezdete közötti hét), az ötéves képzésben a vizsgaidőszak első 3 hete (ld. TVSZ 16. § (2)).A zárthelyi pótlására lehetőség van egyszer a szorgalmi időszakban, illetve egyszer a pótlási időszakban.

     

    12. Konzultációs lehetőségek

    Igény szerint előadókkal egyeztetve.

    13. Jegyzet, tankönyv, felhasználható irodalom

    Pfister, Gregory F., In search of clusters, Upper Saddle River, NJ: Prentice Hall PTR, ISBN 978-0138997090, 1998.

    M. Herlihy and N. Shavit, The Art of Multiprocessor Programming. Burlington, MA: Morgan Kaufman Publishers, 2008.

    Jason Sanders, Edward Kandrot, CUDA by Example, Addision-Wesley, ISBN 978-0131387683, 2010.

    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra28
    Félévközi készülés órákra 0
    Felkészülés zárthelyire 12
    Házi feladat elkészítése 20
    Kijelölt írásos tananyag elsajátítása 0
    Vizsgafelkészülés 0
    Összesen 60
    15. A tantárgy tematikáját kidolgozta

    Név:

    Beosztás:

    Tanszék, Int.:

    Dr. Juhász Sándor

    docens

    Automatizálási és Alkalmazott Informatikai Tanszék

    Dr. Dudás Ákos

    adjunktus

    Automatizálási és Alkalmazott Informatikai Tanszék