Lineáris egyenletrendszerek megoldása GPU segítségével

OData támogatás
Konzulens:
Dr. Horváth Gábor
Hálózati Rendszerek és Szolgáltatások Tanszék

Számos műszaki probléma vezethető vissza lineáris egyenletrendszerek megoldására, melyek akár gigantikus méreteket is ölthetnek. Ilyen alapvető problémák: a sztochasztikus rendszerek egyensúlyi viselkedése, a szabályozástechnika állapotegyenletei, a közönséges vagy a parciális differenciál egyenletek.

A numerikus megoldás gyakran diszkretizációs metódusokon alapul, amik lineáris egyenletrendszerhez vezetnek. Egy konkrét példa, amit az emberek többsége nap, mint nap használ az a Google találatrendezési (page ranking) algoritmusa, de ez valójában nem valósidejű.

Mivel egy Google page ranking algoritmus során gigantikus lineáris egyenletrendszerekről van szó, ezek megoldására hatékonyan működhetnek az iterációs eljárások melyekkel közelítjük a megoldást.

A GPGPU (általános célú algoritmusok grafikus kártyára ültetése) programozás egy viszonylag új technológia, mivel eredetileg nem ilyen célra tervezték a grafikus kártyákat. Ezek a hardverek ma sokkal nagyobb teljesítményre képesek, mint a központi feldolgozó egységek, tehát érdemes felhasználni ezeket lineáris egyenletrendszerek megoldására. A nagy teljesítmény a rengeteg kisebb teljesítményű feldolgozó egység mögött rejlik, ezért az algoritmusok, akkor lesznek gyorsak, ha hatékonyan lehet párhuzamosítani.

A szakdolgozat célja megismerni a nagy lineáris egyenletrendszerek megoldására szolgáló három fő iterációs eljárás (Jacobi, Gauss-Seidel, Successive over-Relaxation) előnyeit, hátrányait, valamint a CPU és GPU architektúrális illetve programozási különbségeit. E tudás alapján az iterációs eljárások implementálása CPU-ra és GPU-ra mind sűrű és mind ritka lineáris egyenletrendszerek esetén, majd az egyes eljárások gyorsaságának összevetése.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.