K-INFO
HU
EN
Login
Subject » BMEVIAUAV13
Older versions Download TAD (PDF)

Algorithms and Data Structures in Multi-core Environment

Algoritmusok és adatstruktúrák többmagos környezetben
A tantárgyleírás hatályossága
Hatályosság kezdete:
—
Hatályosság vége:
—
Subject name (Hungarian, English)
Algoritmusok és adatstruktúrák többmagos környezetben
Algorithms and Data Structures in Multi-core Environment
Subject code BMEVIAUAV13
Subject type —
Training Level —
Course types and hours (weekly/semester)
Course type lecture tutorial laboratory
hours (weekly) 2 0 0
type (linked/independent) — — —
Assessment type félévközi érdemjegy
Credits 2
Subject coordinator
Dr. Dudás Ákos
Responsible department
—
Faculty
Subject website —
Primary curriculum type —
Direct prerequisites – Strong prerequisite none
Direct prerequisites – Weak prerequisite none
Direct prerequisites – Parallel prerequisite none
Direct prerequisites – Milestone prerequisite none
Direct prerequisites – Exclusion none

Objectives

Programme

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.
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.

Learning outcomes

Ez a tantárgy a KKK rendeletben meghatározott, következő kompetenciák fejlesztését szolgálja:

Knowledge

No learning outcomes recorded.

Skills

No learning outcomes recorded.

Attitudes

No learning outcomes recorded.

Autonomy and responsibility

No learning outcomes recorded.

Oktatási módszertan

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

Tanulástámogató anyagok

Not provided.

Recommended preliminary knowledge for completing the subject

Knowledge type competencies
(azon előzetes ismeretek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
Programozási és számítógép-architektúra alapismeretek.
Skill type competencies
(azon előzetes képességek és készségek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Recommended (non-compulsory) preliminary competencies
(azon ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák összessége, amelyek jelentősen hozzájárulnak a tantárgy eredményes teljesítéséhez)
Programozási és számítógép-architektúra alapismeretek.
General rules
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. 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.  
Assessment methods
In-term assessments

No detailed assessments provided.

Weight of in-term assessments

No weights provided.

Exam-period assessments

No detailed assessments provided.

Weight of exam elements

No weights provided.

Grade calculation

No grade thresholds provided.

Attendance requirements

No attendance requirements provided.

Rules for retake and resubmission

Not provided.

Short description

Not provided.

Detailed description

Not provided.

Recommended courses
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
Workload to complete the subject

No workload breakdown provided.

Validity of subject requirements
Requirements valid from:
—
Requirements valid until:
—
Curriculum placement

No curriculum placements recorded for this subject version.