Szimplex algoritmus GPU-s megvalósítása IP hálózat forgalmi mátrixának becsléséhez

Jelenleg egy videokártya körülbelül 50-100-szor akkora számítási kapacitással rendelkezik, mint egy hasonló kategóriás CPU. A közeljövőben ennek az aránynak a videokártyák javára történő további eltolódása várható, mivel a hagyományos processzorok sebességének növekedése az utóbbi években gyakorlatilag megállt (a processzormagok számának növekedésétől eltekintve), a videokártyák esetén viszont a processzorok számának és ezzel együtt a számítási kapacitásnak további növekedése várható. A videokártyákban rejlő teljes számítási kapacitás kiaknázásához többek között arra van szükség, hogy egy probléma megoldása megvalósítható legyen nagyon erősen párhuzamosan (sok ezer szálon) és a felhasznált adatok mennyiségéhez képest sok, de egyszerű műveletet kelljen végrehajtani. Egy lineáris egyenlőtlenség rendszer megoldására szolgáló szimplex algoritmus teljesíti ezeket a feltételeket, ezért GPU alapú megvalósítással jelentős teljesítménynövekedés érhető el a CPU alapú megvalósításhoz képest.

Dolgozatomban a szimplex algoritmus GPU-ra történő implementálását mutatom be CUDA használatával. A GPU-s implementációt használva a futásidőt körülbelül 1 nagyságrenddel tudtam csökkenteni egy saját CPU-s referencia implementációhoz képest. Ez a sebességkülönbség már komoly jelentőséggel bírhat olyan gyakorlati alkalmazásokban, mint például az IP hálózatok forgalmi mátrixának meghatározása.

Egy IP hálózat forgalmi mátrixa megadja, hogy az egyes végpontok között mennyi adat áramlik. Ez az információ jól használható a hálózat fejlesztéséhez, de a közvetlen megmérésére széles körűen alkalmazható gyakorlati megoldás nem áll rendelkezésre. Egyszerű mérési adatokra és a hálózati állapotra vonatkozó információk alapján ugyanakkor a forgalom mennyisége és megoszlása becsülhető. Dolgozatomban a GPU-s környezetben megvalósított szimplex algoritmus teljesítőképességére alapozottan IP hálózatok forgalmi mátrixának becslésére mutatok be egy megoldást. A megoldásom (erősen alulhatározott) lineáris egyenlet- és egyenlőtlenség rendszereket felhasználva a hálózatot használó kliensek forgalmi profiljának ismeretéből adódó forgalmi feltételezésekre és a mért adatok feldolgozására épül.

A rendelkezésre álló adatok és információk feldolgozása során iteratív módon fokozatosan javítom az eredményt, kihasználva a GPU sebességét. A probléma méretének növekedése esetén a GPU-s algoritmus jobban skálázódik, mivel a probléma méretének növekedésével a megoldás párhuzamosíthatósága is nő. A GPU-s algoritmus skálázódását a videokártyán elérhető memória mérete (általában 1GB) limitálja, mivel ha a teljes probléma nem fér el a videokártya memóriájában az a futási időt drasztikusan növeli.

A megvalósított algoritmust kipróbáltam egy, a gyakorlatban előforduló hálózatokhoz hasonló méretű és felépítésű hálózaton. A futásidő tekintetében a GPU-s implementáció ebben az esetben is körülbelül 1 nagyságrenddel jobban teljesített mint a CPU-s referencia implementáció.

szerző

• 
  Berghammer Tamás
  villamosmérnöki
  nappali

konzulens

• 
  Jakab Tivadar István
  címzetes docens, Hálózati Rendszerek és Szolgáltatások Tanszék

helyezés