Optimalizáló algoritmusok számítógépes rendszerek hatékonyságának növelésére

Témakiírás


A mai modern számítógépes rendszerek bonyolultságuk folytán számos olyan optimalizálási problémát vetnek fel, melyek megoldása nagyban befolyásolja a rendszer hatékonyságát. Ugyanakkor e problémák optimális megoldása számítógépes támogatás nélkül tipikusan elképzelhetetlen, sőt - a keresési tér mérete vagy a célfüggvény kiszámításának bonyolultsága folytán - sok esetben számítógéppel is igen nehéz feladat. Néhány ilyen aktuális probléma:

- CPU-GPU optimalizálás: általános célú processzor (CPU) és általános számításra is alkalmas grafikus processzor (GPU) közötti optimális munkamegosztás kialakítása, annak figyelembe vételével, hogy bizonyos műveletcsoportokat a GPU tud hatékonyabban megvalósítani, míg másokat a CPU, valamint, hogy a CPU és GPU közötti adatmozgatás jelentős időveszteséggel jár.

- Ütemezés többmagos (multicore) processzorokon: egy program vagy programhalmaz részeinek (threadek, objektumok, utasítások) a rendelkezésre álló processzor magokhoz történő optimális hozzárendelése olyan módon, hogy a teljes rendszer működése optimális legyen futási idő illetve energiafelhasználás szempontjából, figyelembe véve a programrészek közötti függőségeket és kommunikációt is.

- Memória optimalizálás: a memória-elérések átlagos költségét csökkentő hardvermegoldások (pl. különböző cache-ek) és a memória-elérések számát csökkentő és lokalitásukat növelő program-optimalizáló technikák kombinálása többmagos, elosztott cache rendszerű környezetben.

A feladat ilyen problémák különböző matematikai modelljeinek megfogalmazása, a modellek számítási bonyolultságának vizsgálata és megfelelő optimalizáló algoritmusok kidolgozása. Mivel e problémák tipikusan NP-nehezek, az egzakt algoritmusok mellett approximációs algoritmusok és heurisztikák is szóba jönnek. Kiemelten fontos az algoritmusok hatékonyságának empirikus vizsgálata valós és random probléma példányokon. Ilyen módon egyrészt meggyőződhetünk az algoritmusok gyakorlati alkalmazhatóságáról, másrészt adatokat kaphatunk arról, hogy mi tesz egy probléma példányt könnyűvé illetve nehézzé, amely eredmények további ötleteket adhatnak hatékonyabb algoritmusok kifejlesztésére.


További információk: http://www.cs.bme.hu/~manusz/edu/temak.html