Az alábbi témákhoz keresek vállalkozó kedvű és kimagasló képességű hallgatókat. A témákat - a feldolgozás mélységétől függően - egyaránt ajánlom önálló laborhoz, tudományos diákköri munkához, diplomamunkához vagy doktori kutatási tevékenységhez.
Valamennyi téma eredményes kidolgozásához szükség van a következőkre: algoritmikus gondolkodás, programozási ismeretek, angol nyelvtudás, igényesség, kitartás.

1. CPU - GPU OPTIMALIZÁLÁS

A grafikus processzorok (GPU) ugrásszerű fejlődése révén manapság minden modern PC-ben olyan GPU van, melynek hatékonysága vetekszik a CPU-éval. Mivel a GPU kapacitásának jelentős része általában nincs kihasználva, kínálkozik a lehetőség, hogy a GPU átvegye a CPU terhelésének egy részét (GPGPU: General-Purpose computing on the GPU). Ez egy még gyerekcipőben járó kutatási terület, mely azonban egyre szélesebb körben kelt érdeklődést.

A cél a CPU és GPU közötti optimális munkamegosztás kialakítása. Ennek alapja, hogy bizonyos típusú műveletcsoportokat (melyeknél ugyanazt a műveletet kell nagy mennyiségű adaton végrehajtani) a GPU hatékonyabban tud megvalósítani, míg más műveletcsoportok esetében a CPU a hatékonyabb. Azt is figyelembe kell venni, hogy a CPU és GPU közötti adatmozgatás időveszteséggel jár. Vizsgálhatók olyan modellek, amikor előre, statikusan kell eldönteni, hogy mi kerüljön a CPU-ra és mi a GPU-ra, valamint olyanok is, amikor ezeket a döntéseket futási időben, dinamikusan kell meghozni.

Konkrét feladatok:

• A kapcsolódó szakirodalom áttanulmányozása
• A probléma különböző matematikai modelljeinek definiálása, az egyes optimalizálási problémák komplexitásának vizsgálata
• Algoritmusok kidolgozása a definiált optimalizálási problémákra
• A hardver/szoftver particionálási algoritmusok alkalmazhatóságának vizsgálata
• Az algoritmusok implementálása
• Tesztkörnyezet kialakítása az algoritmusok teszteléséhez
• Az algoritmusok tesztelése, empirikus kiértékelése és összevetése
• Az eredmények publikálása

2. ÜTEMEZÉS TÖBBMAGOS PROCESSZOROKON

A félvezetőipar aktuális trendjei ahhoz vezetnek, hogy a mikroprocesszorok órajele már nem gyorsul tovább, ugyanakkor a processzorban több párhuzamos feldolgozó egység (mag) kerül kialakításra, ilyen módon téve lehetővé a további gyorsítást. Azonban egyáltalán nem nyilvánvaló, hogy a processzoron futó szoftver mennyire tudja kihasználni ezt a párhuzamosságot. A magok közötti kommunikáció pedig ronthatja a teljes rendszer hatásfokát.

A kutatás célja olyan algoritmusok kifejlesztése, melyek automatikusan rendelik hozzá egy program vagy programhalmaz részeit (pl. threadeket, objektumokat vagy akár egyes utasításokat) a rendelkezésre álló magokhoz, olyan módon, hogy a teljes rendszer működése optimális legyen. Az optimalitáshoz részben a futási időt, részben pedig az energiafelhasználást érdemes minimalizálni. A programrészek magokhoz allokálásakor figyelembe kell venni a programrészek közötti függőségeket (pl. ha az egyik mindenképp meg kell, hogy előzze a másikat, akkor hiába allokáljuk őket külön magra, nem tudnak párhuzamosan futni, így nem érünk el gyorsulást) és kommunikációt is.

Konkrét feladatok:

• A kapcsolódó szakirodalom áttanulmányozása
• A probléma különböző matematikai modelljeinek definiálása, az egyes optimalizálási problémák komplexitásának vizsgálata
• Algoritmusok kidolgozása a definiált optimalizálási problémákra
• Ismert ütemezési algoritmusok alkalmazhatóságának vizsgálata
• Az algoritmusok implementálása
• Tesztkörnyezet kialakítása az algoritmusok teszteléséhez
• Az algoritmusok tesztelése, empirikus kiértékelése és összevetése
• Az eredmények publikálása

3. MEMÓRIA OPTIMALIZÁLÁS

A mikroprocesszorok gyors fejlődése révén a programok futtatása során egyre inkább a memóriahasználat lett a szűk keresztmetszet: mind futási idő, mind energiafelhasználás szempontjából igen költséges a memóriából való olvasás és a memóriába való írás. Ez két fontos kutatási terület kialakulásához vezetett: egyrészt a memóriaelérések átlagos költségét csökkentő hardver- és mikroarchitektúra megoldások (pl. különböző cache-ek), másrészt pedig a memóriaelérések számát csökkentő és lokalitásukat növelő program-optimalizáló technikák.

A kutatás célja kettős. Egyrészt azt kívánjuk vizsgálni, hogy a két fent említett terület eredményei mennyiben kombinálhatóak. Ennek elsősorban beágyazott rendszerek esetén van létjogosultsága, ahol lehetőség van a hardver és a szoftver együttes optimalizálására. A másik cél annak vizsgálata, hogy a modern többmagú processzorok esetében milyen optimalizációs módszerek a célravezetőek. Ezek jellemzően elosztott cache-rendszert tartalmaznak, mely újabb kihívást jelent.

Konkrét feladatok:

• A kapcsolódó szakirodalom áttanulmányozása
• A probléma különböző matematikai modelljeinek definiálása, az egyes optimalizálási problémák komplexitásának vizsgálata
• Algoritmusok kidolgozása a definiált optimalizálási problémákra
• Az algoritmusok implementálása
• Tesztkörnyezet kialakítása az algoritmusok teszteléséhez
• Az algoritmusok tesztelése, empirikus kiértékelése és összevetése
• Az eredmények publikálása

4. OPTIMALIZÁLÓ ALGORITMUSOK EMPIRIKUS VIZSGÁLATA

A bonyolultság klasszikus elmélete arra a kérdésre koncentrál, hogy egy adott problémára van-e olyan algoritmus, melynek lépésszáma legrosszabb esetben is felülről becsülhető az input hosszának polinomjával. Ennek a gyakorlati alkalmazása számos kihívást rejt. Először is, a legtöbb gyakorlatban előforduló probléma NP-nehéz, ezekre nem ismerünk a fenti tulajdonságokkal rendelkező algoritmust. Ennek ellenére a gyakorlatban fontos minél hatékonyabb megoldó algoritmusokat kifejlesztenünk ezekre a nehéz problémákra. Másrészt gyakorlati szempontból általában konkrét probléma példányok bonyolultsága az érdekes, nem pedig az adott probléma worst-case bonyolultsága.

Az utóbbi években kialakult egy új kutatási terület, mely NP-nehéz problémák konkrét példányainak bonyolultságát vizsgálja, elsősorban mérésekkel, másodsorban pedig a mérési eredményeket megmagyarázó modellek felállításával. Az egyik legfontosabb eredmény, hogy a legrosszabb esetben reménytelenül nehéz problémák konkrét példányait sok esetben hatékonyan meg tudjuk oldani. Továbbá, e bonyolultsági vizsgálatokból számos olyan felismerés született, amely jelentősen hozzájárult a megoldó algoritmusok fejlődéséhez is.

A kutatás célja az ilyen típusú vizsgálatok folytatása. A következő kérdésekre keressük a választ: Mi tesz egy probléma példányt könnyűvé illetve nehézzé? Hogy lehet gyorsan felismerni egy probléma példányról, hogy mennyire nehéz? A bonyolultság mennyire a probléma példány sajátossága, illetve mennyire függ a megoldó algoritmustól? Hogyan lehet eldönteni egy probléma példányról, hogy milyen algoritmussal oldható meg a leggyorsabban? Mennyire tér el a valós és a véletlenszerűen generált probléma példányok bonyolultsága?

Konkrét feladatok:

• A kapcsolódó szakirodalom áttanulmányozása
• Keretrendszer kialakítása optimalizáló algoritmusok implementálásához és vizsgálatához
• Néhány benchmark algoritmus implementálása
• Az algoritmusok empirikus kiértékelése véletlen és valós probléma példányokon
• Az eredmények publikálása

Vissza a főoldalra
© Mann Zoltán, 2009.
E-mail: x.y@gmail.com, ahol x=zoltan, y=mann