A kutatás célkitűzései

A kutatás elsődleges célja komplex modellezési és optimalizálási feladatok hatékony elosztott megoldása. A kutatás során egyfelől foglakoznánk hálózattervezéshez és adatbányászathoz kapcsolódó nagy számításigényű problémák hatékony megoldási lehetőségeivel. Másfelől vizsgálnánk, hogyan lehet általános optimalizálási módszereket masszívan párhuzamosítani.

A kutatási projekt alatt az új és már működő hálózati technológiákhoz kapcsolódó releváns hálózattervezési és konfigurálási nagy számításigényű problémákat vizsgálnánk. Célunk a hálózatok költség és energia hatékony működtetése. A költséghatékonyság jelentkezhet egyenletesebb és jobb sávszélesség kihasználtságban. Ilyenkor a feladat a hálózat adat forgalmának hatékony elosztott irányítása. A hálózat költséghatékonysága a szolgáltatás minőségének javításaként is megvalósulhat. A szolgáltatás minőségét elsősorban a megbízhatóságon keresztül vizsgáljuk az optikai rétegében. Ehhez csoportteszteléshez kapcsolódó kombinatorikus optimalizálási feladatokat kell megoldanunk. IP hálózatok esetén vizsgálnánk a routerek hatékony konfigurációját egyszeres linkhiba védelmére. A jelenlegi OSPF protokoll megtartása mellett ez az adminisztratív költségek újra optimalizálásával lehetséges.

Valamint célunk, olyan elosztott rendszeren működtethető adatbányászati algoritmusok implementációja, amely az optimális modell keresése során nem heurisztikus úton választ az egyes modellek közt, hanem a teljes keresési tér bejárásával találja meg az optimális algoritmus paramétereit, így pontosabb eredményt adhat az adatbányászati problémára. Továbbá, a több millió dokumentumot számláló orvosbiológiai szakirodalomban rejlő információk kinyerését, optimális módszerek és beállítások kiválasztását valósítanánk meg szükségszerűen magas szinten párhuzamosított architektúrával. Valamint, az implicit feedback alapú ajánlási probléma, mint komplex optimalizálási probléma vizsgálata, és fejlett, skálázható algoritmusok tervezése a probléma megoldására.

Végül, az elosztott ILP megoldók teljesítményét vizsgálnánk a számításban résztvevő számítógépek számának növekedése mellett. Célunk olyan eltoszott rendszer tervezése, amelyben nagy méretű ILP feladatokat rengeteg számítógép (például desktop grid) együttes munkájával oldana meg. Ilyen rendszerben fontos a kutatandó kérdés a kommunikáció skálázhatóságon és módszerek kidolgozása a rendszer hibatűrő működésére.

Projekt előrehaladási jelentés

Nagy méretű egészértékű lineáris programok (ILP) megoldása gyakran merül fel egy mérnök élete során. És habár sok kereskedelmi forgalomban kapható programcsomag létezik ezen problémák gyors megoldására (pl. Gurobi, CPLEX, stb.), ezek költsége nagy. Így felmerül a kérdés, hogy ingyenes könyvtárakkal elérhető-e a kereskedelmi forgalomban kapható programcsomagok sebessége. A kérdés vizsgálatára egy elosztott módon, a hálózaton keresztül működő ILP megoldó megírása volt a cél. A program a SETI@home mintájára a megoldandó feladatokat összegyűjti, majd azokat jól meghatározott darabokra bontja, és később a létrehozott részproblémákat szétosztja a hálózatban elérhető kliensek között.

 A probléma megoldása során három feladatot azonosítottam. Ezek közül az első volt az egészértékű lineáris programok darabolását végző modul megírása, második a hálózati kommunikációs modul, míg a harmadik a hálózatban részt vevő csomópontok nyilvántartásáért felelő modul lekódolása volt.

 A feladat ingyenesen elérhető szoftver létrehozását tűzte ki célul, így a program magját a GLPK könyvtárcsomag alkotja. Sajnos a GLPK önmagában nem felelt meg teljesen a célnak, mert nem támogatta kellőképp a nagy feladatok darabolását. Ezért első feladatként módosítottam a glpk könyvtárat, hogy lehetővé váljon a "branch and bound" külső nyomkövetése, azaz kívülről meg lehessen adni a módszer során létrehozott (és ebben a pontban nem megoldott) alproblémák számát és az alproblémák meghatározása során alkalmazott algoritmus típusát.

 A nyilvántartásért felelős modul egy webes alapú központi elem, amely php-ban a Yii keretrendszer felhasználásával készült el. Működését tekintve teljes egészében a Bittorrent tracker "klónja", olyannyira, hogy pontosan az előbbi protokolját használja (A tesztverzió elérhető a http://opti.tmit.bme.hu/~nemeth/silp2p/tracker címen).

 A csomag harmadik modulja lényegében maga a solver. Ez magában foglalja a feladatok darabolásáért felelős modult, a csomópontok kommunikációjáért felelős modult és a csomópont-tracker kommunikációért felelős modult. Ez a modul teljes egészében C++ nyelven íródott a Boost könyvtárcsomag felhasználásával. A szoftver első verziója tesztelés alatt áll.