SZAKDOLGOZAT
Több processzoros ütemezés változtatható méret¶ feladatokkal
Szilágyi Dániel
Témavezet®:
Kis Tamás egyetemi adjunktus ELTE Matematika Intézet, Operációkutatási Tanszék
ELTE 2013
Tartalomjegyzék
1. Bevezet®
2
2. Minimális végrehajtási id® keresése
4
2.1. Eddigi eredmények . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. A minimális végrehajtási id® de níciója . . . . . . . . . . . . . . . . .
5 7
3. Konvex sebességfüggvények
9
4. Konkáv sebességfüggvények
12
4.1. Approximációs algoritmusok . . . . . . . . . . . . . . 4.2. Az optimális ütemezés . . . . . . . . . . . . . . . . . 4.2.1. A P-CNTN eset . . . . . . . . . . . . . . . . . 4.2.2. A P-DSCR eset . . . . . . . . . . . . . . . . . 4.2.3. Példa a P-DSCR eset megoldására n=3 esetén
5. Nyitott problémák
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
12 22 22 24 26
28
1
1.
Bevezet®
A hétköznapi életben gyakran találkozunk olyan feladatokkal, amelyek elvégzéséhez mi dönthetjük el, hogy miként osztjuk be a munka elvégzéséhez szükséges er®forrásainkat, azaz gépeinket, energiánkat. Gondoljunk például egy költözésre. A bútorok és más ingóságok mozgatása összetett feladat, általában minél többen segítenek, annál könnyebben és gyorsabban folyik a munka. Leegyszer¶sítve minden tárgyhoz hozzárendelhetünk különböz® értékeket, annak függvényében, hogy milyen er®forrás használattal milyen gyorsan lehet mozgatni. Ezalatt azt értem, hogy egy bútor milyen sebességgel szállítható a kell® helyre, ha 1, 2, 3, ... ember mozgatja. Ez minden bútorra más és más értékeket adhat, a függvény azonban értelemszer¶en csak egész helyeken értelmezett. Nem mindegy azonban, hogy a leegyszer¶sített függvény konvex vagy konkáv. Például egy hatalmas ruhásszekrény cipelése egy embernek gyakorlatilag lehetetlen, kett®nek épp hogy lehetséges, hárman már jól haladnak vele, de 4 ember már mindenre elegend®, és ennyi a legalkalmasabb a munkára. Ebben az esetben a függvényünk konvex, érdemes tehát minél több (maximum 4) embert mozgósítani a feladathoz. Viszont mondjuk egy kisebb éjjeliszekrény cipelése már egy embernek is megoldható, 2 már kicsit felesleges. 3 vagy annál több pedig csak minimális segítséget nyújthat, így az ezt leíró er®forrás felhasználó függvény konkáv, minél kevesebb ember dolgozik, annál hatékonyabb a munkavégzésük.A dolgozat egy fontos témája a csak konvex és a csak konkáv végrehajtási idej¶ feladatok megoldása. A feladatokat végz® er®források legyenek processzorok. A processzorok száma legyen m, az elvégzend® feladatoké n, és minden feladatra van egy fels® határa annak, hogy hány processzor dolgozhat rajta egyidej¶leg. Minden id®pillanatban változtatható, hogy a feladatokon hány processzor fusson, de egyszerre maximum m darab m¶ködhet az összes feladaton, azaz egy processzor sem dolgozhat több feladaton. Ezt hívjuk változtatható processzorszámú feladatnak, röviden MPTS-nek. Ehhez képest az NPTS modellnél a feladatokhoz rendelt processzorszám, és ebb®l következ®en a feladatok végrehajtási ideje is el®re adott. Párhuzamos ütemezést készítünk, azaz mind az n feladat egymástól független, nincsenek el®feltételeik. A feladatokat elkezdhetjük a nulladik pillanatban. A feladatokat végz® m azonos processzor szintén független, és n ≤ m; n, m ∈ R [4]. A processzorrendszeren párhuzamosan végzett feladatok lehet® legjobb ütemezése, ahol semmilyen más tényez® nem számít, mesterkélt probléma, a kapott eredmények azonban tökéletesen használhatóak a gyakorlatban, például számítógépes rendszerek m¶ködtetésénél. A processzorszám monoton csökken® függvénye a végrehajtási id® nagysága . Az MPTS egy kiterjesztése az egyik legalapvet®bb ütemezési problémakörnek, a P|| Cmax -nak. A P|| Cmax -ban a P a párhuzamosan m¶köd® er®források ütemezését jelöli, a Cmax pe2
dig azt, hogy a cél az összes feladat elvégzése során eltelt id® minimalizálása. Az egyetlen különbség az, hogy míg a P|| Cmax -nál egy feladaton csak egy er®forrás dolgozhat, addig az MPTS-nél minden feladat egyszerre végezhet® több er®forráson. Mindenféle rugalmasság, egyszer¶sítés nagyban csökkentheti a végrehajtási id®t, de jelent®sen növeli a probléma megoldásának nehézségét. Néhány MPTS algoritmust megvizsgálva, mindegyik m¶ködött speciális esetekben is, de egyik sem kell®en hatékonyan. Ilyen meg gyelésekre alapozva vizsgálunk meg néhány optimalizációs algoritmust és javító módszert az MPTS feladatokra. A célunk hozzárendelni a feladatokhoz a processzorokat olyan módon, hogy a végrehajtási id® minimális legyen. A processzorszám nagyságától függ® végrehajtási id®ket konvexitásuk szerint bonthatjuk különböz® esetekre. A kizárólag konvex végrehajtási idej¶ függvényekkel leírt feladatokat O(n) id® alatt ütemezhetjük, a kés®bbiekben ehhez adunk algoritmust. A konkáv esetben, amennyiben az elvégzend® feladatok száma konstans, és a felhasznált processzorszám mindig egész minden feladatnál, akkor a probléma megoldható polinomiális id®ben. Összetettebb a helyzet, ha egy feladat végrehajtáshoz használt processzorok száma nem kell, hogy egész legyen (P-CNTN). A kés®bbiek˙ 2 m)) id® alatt ütemezhet®. Bizonyított, ben bizonyítjuk, hogy ez O(n max(m, nlog hogy a legjobb ütemezés az eredeti, egész érték¶ (P-DSCR), és a nem egész érték¶ problémára összefügg egymással. Érdekes még a P-FIX eset, ami a P-DSCR azon lesz¶kítése, amikor egy feladatot végz® processzorszám id® közben nem változhat. Azt is vizsgáljuk a kés®bbiekben, hogy n = 2 és n = 3 esetben egy optimális ütemezés a nem egész érték¶ feladatra konstans id® alatt átalakítható az eredeti feladat megoldására.
3
2.
Minimális végreha jtási id® keresése
A konvexitás szerint szeparált feladatok megoldási módszereinek részletezése el®tt vezessünk be néhány alapfogalmat. Minden j feladathoz tartozik egy pj > 0 munkamennyiség, ami a végrehajtásához szükséges, ez a feladat hossza. Amennyiben r darab processzor t id®n át végzi a j feladatot, akkor az ezen id® alatt elvégzett munka nagysága a feladaton gj (r) · t, ahol gj (r) ≥ 0 monoton növ® végrehajtási sebesség függvény, ∀r ∈ {0, 1, . . . m}, gj (0) = 0. Az összes j -n elvégzett munka nagysága meg kell, hogy egyezzen pj -vel ∀j ∈ {1, 2, . . . n}. Legyen Cj a kezdést®l számított azon id®pont, amikor befejezzük j feladatot. Minden feladatra egy ütemtervet kell adnunk, hogy melyik id®intervallumban hány processzor dolgozik rajta. A célunk egy olyan ütemezés készítése a lehet® leggyorsabban, ami teljesíti az eddigi feltételeket, és a legkés®bb befejezett feladat befejezési idejét, azaz a Cmax futásid®t minimalizálja. Jelölje ezt a minimumot, azaz az optimális megoldásnál kapott végrehajtási ∗ id®t Cmax . A folytatásban a problémát a P-DSCR és P-CNTN esetekben vizsgáljuk. A P-CNTN esetén a P-DSCR-ben használt gj (r) függvényt lineáris szakaszokkal kell kiegészítenünk az egészek között. A P-FIX feladat NP-nehéz, ezt 1989-ben Du és Leng bizonyították [10]. Ha minden feladat 1 vagy k processzort használhat, akkor a probléma polinom id®ben megoldható. A P-FIX problémaköre hasonlít a ládapakolási feladatokéra, ahol az alapprobléma esetén 2 dimenzióban kell elhelyeznünk azonos méret¶ ládákba különböz® méret¶, téglalap alakú tárgyakat, ehhez minél kevesebb ládát használva. Az a feladat is NP-nehéz, de ismert, hogy a ládapakolási feladat bármely λ-approximációs algoritmusa polinomiális id®ben átalakítható a P-FIX feladat λ-approximációs algoritmusára. A λ-approximációs algoritmus azt ∗ ∗ jelenti, hogy az optimális Cmax végrehajtási id®höz képest λ · Cmax id® alatt végzünk a feladatokkal.
4
2.1. Eddigi eredmények A P-FIX problémakör eseteit többen vizsgálták. Chen és Lee [6] polinomiális idej¶ approximációs algoritmusa után Bªa»ewicz, Drabowski és W¦glarz [5] belátták, hogy ha minden feladat 1 vagy k processzort használhat, akkor a probléma megoldható polinomiális id® alatt. Turek, Wolf és Yu [24] a ládapakolási feladatra alapozva fejlesztettek ki λ-approximációs algoritmust a P-FIX feladatra. Belátták, hogy bármely λ-approximációs két dimenziós ládapakolási feladat polinomiális id® alatt átalakítható egy λ-approximációs algoritmusává a P-FIX feladatnak. A ládapakolási feladat egyik dimenziója az id®nek, a másik a processzoroknak felel meg az ütemezési feladatoknál [20]. Ezt felhasználva Ludwig [18] megalkotott egy 2-approximációs algoritmust a P-FIX feladatra. Ugyanezt a problémát az NPTS feladatra is vizsgálhatjuk. Az NPTS feladatnál azonban elvárás, hogy a processzorok sorszámai egy adott feladatnál folytonosak legyenek. Ezt nevezzük sorba állított NPTS ütemezésnek. Többen foglalkoztak ezzel a problémával, például Coman és társai [7], akik kidolgozták az NFDH (a következ® beill®, csökken® nagyság szerint rendezve) módszert, valamint FFDH (az els® beill®, csökken® nagyság szerint rendezve) módszert. Ett®l eltér®en Lodi [17] a BFDH (leginkább odaill®, csökken® nagyság szerint rendezve) módszert vizsgálta. Mindegyik módszer szintekre osztotta a feladatokat, és a szinteken belüli végrehajtási id® minimalizásásra törekedett [3]. Ezekhez hasonló a bal-alsó algoritmus, melyet Baker és társai [1] mutattak be a ládapakolási feadat azon esetére, amikor 1-szélesség¶ ládákba pakolunk. Az algoritmusuk 3-approximációs volt erre a feladatra. Ezt az eredményt Sleator [22] 2, 5-approximációsra javította. Végül Steinberg tovább tökéletesítte a módszert, és 2-approximációs eljárást adott a problémára. Az MPTS esetet Krishnamurti és Ma tanulmányozták [16], de azzal a kikötéssel, hogy minden feladatnak a 0 id®pillanatban el kell kezd®dnie. Ehhez persze szükséges az a feltétel, hogy több a rendelkezésre álló processzorok száma, mint a feladatoké. Ez leegyszer¶síti a problémát arra, hogy egy párosítást találjunk a processzorok és a feladatok között. Prasanna és Musicus [21] olyan P-FIX problémákat vizsgáltak, ahol a feladatokra megel®zési feltételek vannak. Abban a speciális esetben, ha a végrehajtási id® függvény minden feladatra pα , ahol p a feladaton dolgozó processzorok száma, 0 < α < 1, akkor zárt formulát kapunk a párhuzamosan futó feladatok optimális ütemezésére. 1996-ban Drozdowski [9] publikált egy terjedelmes áttekintést a többprocesszoros feladatok ütemezésének összetettségér®l és algoritmusairól. A párhuzamosan futó feladatokkal való modellezést a nehezen kezelhet®en nagy mátrixoknál is használhatjuk. Dongarra és társai [8] azon mátrixok Choleskyfaktorizációjához használták a párhuzamos ütemezést, ahol a mátrix egésze nem 5
fért el a memóriában, ezzel lelassította a rajta futó processzor m¶ködését. Azonban ha blokkonként már elfér több memóriakártyán, akkor a számítások sebessége fontosabbá válik, mint a késések, amit a több processzoros rendszer okozhat. Ezzel a módszerrel a processzorszámnak a lineárisnál is jobb függvénye lehet a végrehajtási sebesség. Fontos része még az ütemezéselméletnek az on-line ütemezés, ami azt jelenti, hogy egyes feladatokról csak az el®tte elvégzett feladatok befejezése után kapunk információkat, lehetetlenné téve ezáltal az el®re teljesen eltervezett ütemezés kialakítását, egy változó feladathalmaz végrehajtását megoldó algoritmust kell alkalmaznunk. Az egymástól független on-line feladatok esetét Feldmann, Sgall és Teng [12] elemezték. Kaoval kiegészülve [11] azt az esetet is kutatták, amikor a feladatok között megel®zési feltételek is lehetnek. Mindkét esetben feltették, hogy a feladatok hossza végig állandó, de ahogy eddig is, a rajtuk dolgozó processzorszám növelésével csökken a végrehajtási idejük.
6
2.2. A minimális végrehajtási id® de níciója El®ször a P-CNTN esetet vizsgálva vezessünk be fontos fogalmakat. Ekkor lényeges, hogy úgy válasszuk meg az egész r processzorszámok közötti nem egész értékekre a végrehajtási sebesség függvényt, hogy megmaradjanak a P-DSCR probléma alaptulajdonságai, úgy, mint a monotonitás vagy a konvexitás. Ez teljesül, ha a gj végrehajtási sebesség függvényt egy olyan fj függvénnyé terjesztjük ki, ami az eredeti függvény egész pontjai közötti értékei között lineárisan változik. Így (1)
fj (r) = αr gj (brc) + ((1 − αr ) · gj (dre)),
ahol αr = dre − r, 0 ≤ r ≤ m. Így de niálva fj -t, az egész pontokban valóban megegyezik a megfelel® gj értékekkel, közöttük pedig egyenletesen változik. Ezeket a szakaszokat nem csak a két végpontjuk felvett értékének konvex kombinációjaként írhatjuk fel, hanem linearitásuk miatt az r változó els®fokú függvényeként is. Ehhez csak a megfelel® bj,s és dj,s együtthatókat kell megtalálnunk, amikre (2)
fj (r) = bj,s r + dj,s ,
∀r ∈ [s − 1, s], s ∈ {1, 2, ...m}, j ∈ {1, 2, ...n} és bj,0 = dj,0 = 0. A bj,s és dj,s
együtthatók adott gj (r)-re O(mn) id® alatt kiszámolhatóak, mivel ezek m · n adott pontpáron átmen® egyenesek egyenletei. Mivel egy feladatra két azonos egészrész¶ r-re a bj,s és dj,s értékek külön-külön megegyeznek, ezért fj (r)-t dre-szel is megadhatjuk: (3)
fj (r) = bj,dre r + dj,dre .
Mivel fj (r) = gj (r), ezért a P-DSCR probléma fj és gj függvényekkel megegyezik. 0 Újra a P-CNTN problémát tekintve az fj függvényekkel, legyen Cmax a P-CNTN ∗ feladat minimális Cmax értéke, azaz a megoldása. Mivel Cmax a P-DSCR megoldása 0 ∗ volt, aminek kiterjesztése a P-CNTN, ezért Cmax ≤ Cmax . Az összes lehetséges er®forrás felosztást jelölje R, amire így: ( R=
r = (r1 , r2 , ...rn ) | rj ≥ 0,
n X
) rj ≤ m ,
(4)
j=1
valamint U = {u = (u1 , u2 , ...un ) | uj = fj (rj ), ∀j ∈ {1, 2, ...n} , r ∈ R}
(5)
jelölje az összes feladaton egyszerre végzett munkák sebességvektorát. Legyen p = (p1 , p2 , . . . pn ) a munkamennyiség vektor. 7
[25], [26] Legyen n ≤ m, convU az U halmaz konvex burka, azaz U elemeinek összes konvex kombinációja. u := egy n-dimenzióbeli egyenes, amelynek koordinátáit az u = paraméteres egyenletb®l kapjuk, ahol j ∈ {1, 2, . . . n}. Ekkor a minimális végrehajtási idejét a P-CNTN problémának a követez® képlet írja le: 2.1. Tétel.
p C
j
pj C
o n p 0 Cmax = min C | C > 0, ∈ convU . C
Bizonyítás: Amennyiben találunk olyan C -t, amire igaz, hogy
(6) p C
∈ convU , akkor
az ütemezés biztosan el®állítható U -beli elemek konvex kombinációjaként. Ez pedig akkor lesz a leghasznosabb, ha a kombináció a konvex burok peremén van, hiszen ekkor szorozhatjuk a legnagyobb C1 -vel, azaz a legkisebb C -vel p-t, hogy még éppen a konvex burkon belül maradhassunk. Így a lehetséges r processzorszétosztások közül néhány konvex kombinációjaként megkaptuk a lehet® leggyorsabb ütemezést, mivel nagyobb C esetén lassabb megoldást kapunk, kisebb esetén pedig nem lennénk már a konvex burokban, azaz nem megengedett processzorszétosztást kéne alkalmaznunk. p 0 = uj0 , ∀j ∈ A bizonyításban említett konvex kombinációt jelölje u0 . Ekkor Cmax j {1, 2, ...n}. Speciális esetben ezt az u0 konvex kombinációt az U elemeinek több konvex kombinációjaként is el®állíthatjuk, ezért jelölje r0 azt az optimális er®forrás P szétosztást, amire nj=1 rj0 = m és fj (rj0 ) = u0j , j ∈ {1, 2, . . . n}. A továbbiakban el®ször azt az esetet vizsgáljuk, amikor minden fj függvény konvex, majd amikor mindegyik konkáv.
8
3.
Konvex sebességfüggvények
Minden fj függvény lehet konvex, konkáv, esetleg egyik sem. Ez utóbbi függvényeket nevezhetjük semlegesnek. Ezt szemlélteti a 3.1. ábra.
végrehajtási sebesség 9 8 7 6 5 4 3 2 1
6
s semleges s s s s konkáv s s konvex s s
1
2
3
-
processzorszám
3.1. Szakaszonként lineáris függvények konvexitása
Az els® esetben legyen minden fj függvény konvex, és mivel szakaszonként lineáris függvényekr®l beszélünk, ezért a maximum m töréspont miatt O(mn) id® alatt ellen®rizhet® is a konvexitás. Mivel a függvény konvex, ezért a bevezetett U halmaz (5) valódi részhalmaza a convU halmaznak, azaz a convU halmaz b®vebb. Vezessük be a v i pontokat a következ® módon, koordinátáiknak megadásával: vjj = fj (m), és vji = 0, ha i 6= j ∀i ∈ {1, 2, . . . n}, j ∈ {1, 2, . . . n}. Könnyen látható, hogy a v 1 , v 2 , ...v n pontok a convU konvex burok egy lapjának csúcsai, és az u0 pont is ezen a lapon helyezkedik el. Így u0 el®áll a v 1 , v 2 , . . . v n pontok konvex kombinációjaként, P P azaz u0 = ni=1 λi v i , ahol λi ≥ 0 ∀ i ∈ {1, 2, . . . n} és ni=1 λi = 1. Ezeket láthatjuk a 3.2. ábrán, n = 2 esetén. A koordinátarendszerben a két feladat végrehajtási sebességét ábrázoljuk egymáshoz képest, attól függ®en, hogy az m = 4 processzorból melyik feladaton hány dolgozik. Az így kapott gra kon egy konvex törött vonal, az ez alatti terület lesz U . A nem egész processzorszámokra a fent említett lineáris függvényeket használjuk, így jön létre a törött vonal. A terület konvex burkát, azaz convU -t a törött vonal két végpontját összeköt® szakasz és a koordinátatengelyek határolják, mivel ezek a szakaszok még megkaphatóak a v i pontok konvex kombinációjaként, de ezen a területen kívül semmilyen más pont nem. 9
f (r2 )
9 8 7 6 5 4 3 2 1
62 sv = (0, f2 (4)) D@ p D @ u= C D @ @ D D @ @ s u0 = (u0 , u0 ) D 2 1 D @ D @ @ @ @ @ convU @ @ @ H @ HH U HX XX @ v 1 = (f (4), 0) XXX 1 @ @s X
1 2 3 4 5 6 7 8 9
f (r1 )
3.2. Konvex függvények minimális végrehajtási ideje
A törött vonal el®állításához a 3.3. táblázat nyújt segítséget, ahol leolvasható a két feladat végrehajtási sebessége a processzorszám függvényeként. A processzorszám soronként növekszik, a két oszlop a két feladatnak felel meg. Miután kiszámoljuk az u = Cp egyenes egyenletét, ábrázoljuk is, majd a keletkezett egyenes, és a (v 1 , v 2 ) szakasz metszéspontja adja a keresett u0 pontot. P P pj 0 · vji . LeTudjuk, hogy u0j = Cmax = ni=1 λi vji , ami átírva pj = ni=1 λi Cmax 0 P pj p 0 0 = vjj = fj (m) gyen ∆j = λj Cmax és , ∀j ∈ {1, 2, ...n}. Mivel nj=1 ∆j = Cmax j pj = ∆j fj (m) ∀j ∈ {1, 2, ...n}, ezért optimális ütemezést kapunk, ha ∀j -re ∆j id®n keresztül a j feladaton mind az m processzort használjuk, hiszen ennyi id® alatt elvégzik azokat, az el®bbiek miatt a leggyorsabb módon. A 3.4. ábrán láthatunk egy optimális ütemezést tetsz®leges feladat- és processzorszámra, a kiszámított ∆j értékek segítségével. Ezek alapján látszik, hogy ha minden fj függvény konvex, akkor az optimális ütemezést O(n) id® alatt megtalálhatjuk a P-CNTN esetben. Mivel a megoldásban kapott processzorszétosztás egész érték¶ volt, ezért ez az optimális ütemezés a P-DSCR esetben is. Ha az fj végrehajtási sebesség függvény nem konvex, akkor jóval nehezebb megtalálni az optimális ütemezést. Ezek közül most azt az esetet vizsgáljuk meg, amikor a függvényeink mind konkávok.
10
0
0
0
1
1
1
2
2
3
3
4
5
4
9
9
f1
f2
3.3. Végrehajtási sebességek a processzorszám alapján
processzorok 6
m
1
···
2
n
-
∆1
∆2
···
∆n
3.4. Az optimális ütemezés a konvex feladatra
11
id®
4.
Konkáv sebességfüggvények
4.1. Approximációs algoritmusok Ebben a részben azt az esetet tárgyaljuk, amikor az összes fj függvényünk konkáv. Mivel ez lényegesebben összetettebb és nagyobb futásidej¶ probléma, ezért különböz® approximációs algoritmus tárgyalásával kezdjük, amik kell®en jól közelítik az optimális processzorszétosztást, és lényegesen rövidebb a futásidejük az optimális megoldást megtaláló leggyorsabb algoritmusoknál. A végrehajtási sebesség függvények konkávok, ebb®l következik, hogy fjr(r) ≥ fj (r+1) ∀r ∈ {1, 2, ...m − 1}, azaz egy feladathoz több processzort használva romlik r+1 azok egyenkénti hatékonysága. Természetesen az fj (r) ≤ fj (r + 1) összefüggés továbbra is fennáll ∀r ∈ {1, 2, . . . m − 1} esetén. Az els® approximációs algoritmus a P-FIX azon speciális esetében ad ütemezést, amikor nemcsak hogy nem változhat id® közben a megkezdett feladatokon a processzorszám, de ez az érték mindegyik feladatra 1. Azaz egy feladaton egyszerre csak egy processzor dolgozhat. Már ez a feladat is N P -nehéz m ≥ 2 esetén. Ez egyúttal a ládapakolási feladat egy speciális esete is, az els® megoldás listás ütemezést használ, azaz a feladatokat tetsz®leges sorrendben olvassa be egy listáról, majd ezeket a megfelel® processzorokhoz rendeli. Ez 2 − m1 -approximációs megoldást nyújt a speciális P-FIX feladatra (a kés®bbi 4.1. Állítás). Fr az r processzor aktuális feladatbefejezési idejét mutatja. Az algoritmus a következ®:
Listás algoritmus 1. i := 1, Fr = 0 ∀r ∈ {1, 2, . . . m}. 2. Válasszuk ki a legkisebb Fr érték¶ (egyenl®ségnél egy tetsz®leges, az egyenl®ségben szerepl®) r processzort a processzorok közül. i 3. Rendeljük az i. feladathoz az r processzort, és Fr -t frissítsük: Fr = Fr + fip(1) .
4. Ha i 6= n, akkor növeljük: i = i + 1, és térjünk vissza a 2.-es lépéshez. Ha i = n, akkor befejez®dött az algoritmus, és a végrahajtási id® megegyezik a kapott Fr értékek legnagyobbikával. Az algoritmus tehát listaszer¶en olvassa be a feladatokat, és mindig az aktuálisan leghamarabb végz® processzorhoz rendeli ®ket. A processzorok feladatbefejezési idejeit a 3. lépésben a kell® futási id®kkel növeli. Végül ha már minden feladatot beolvastunk, akkor már csak azt kell megnéznünk, hogy melyik fejez®dik be legkés®bb, ez adja meg a végrehajtási id®t. 12
Ez az algoritmus 2− -approximációs, ha egy feladaton egyszerre csak egy processzor dolgozhat [14]. Bizonyítás: El®ször tegyünk két triviálisnak t¶n® alsó becslést C -ra: 4.1. Állítás.
1 m
∗ max
∗ ≥ 1. Cmax
pj j=1 m
Pn
.
∗ 2. Cmax ≥ max pj .
Az els® állítás teljesül, mivel nem végezhetünk hamarabb, mint az összes feladat össz∗ -ig hossza, leosztva a processzorok számával. Az egyenl®ség akkor teljesül, ha Cmax minden processzor folyamatosan dolgozik. A második állítás pedig még kézenfekv®bb, hiszen nem végezhetünk hamarabb az összes feladattal, mint bármelyik®jük (itt a leghosszabb) hossza. Legyen l az utoljára befejez®dött feladat. Az l elkezdéséig minden processzor folyamatosan dolgozik, különben már korábban is elkezdhettük volna l-et. Vagyis ha Tl jelöli l kezdési idejét, akkor:
Cmax = Cl = Tl + pl ≤
n n X X pj pj 1 1 ∗ + pl = + (1 − ) · pl ≤ (2 − ) · Cmax m m m m j=1 j=1,j6=l
ahol az els® egyenl®tlenség azért teljesül, mert az utoljára befejezett feladat elkezdéséig minden processzor folyamatosan dolgozik, a második pedig a fenti 1. és 2. triviális alsóbecslés következménye. Ezzel az állítást igazoltuk.
Az egyszer¶ listás ütemezés egy hatékonyabb továbbfejlesztése az LPT (a feladat hossza szerint nem növekv® sorrendbe rendez®) algoritmus, aminél így a listáról épp beolvasott feladat az addig be nem olvasottak közül a leghosszabb. Az LPT 1 algoritmus O(n · log n + n · log m) id® alatt elvégezhet®. Bizonyítottan 43 − 3m approximációs algoritmus a lesz¶kített P-FIX problémára, ami "nagy" m esetén 4 1 -hoz tartó approximációt eredményez. A 43 − 3m approximációnál könnyebben 3 bizonyítható, de kicsit gyengébb állítás a következ®:
A P-FIX azon esetében, amikor minden feladaton csak egy processzor dolgozhat, az LPT szerinti listás ütemez® algoritmus -approximációs. [14] Bizonyítás: Feltehet®, hogy az utoljára végz®d® feladat kezd®dik utoljára, ha nem 4.2. Állítás.
4 3
így lenne, akkor az összes kés®bb kezd®d® feladatot vegyük ki a feladatok közül, ∗ ezáltal Cmax nem változik, de Cmax csökkenhet, ez tehát csak ronthat a közelítésünkön. Legyen az említett feladat hossza pj . Mivel az összes többi feladat már el®bb kezd®dik mint j , ezért ® a legrövidebb. Vizsgáljunk két esetet: 13
1. pj ≤
∗ Cmax 3
.
A processzorok Cmax − pj -ig biztosan mind dolgoznak, mert csak akkor szaba∗ dul fel egy j -nek. Azaz ennél az értéknél Cmax sem lehet kisebb, és ezután pj ∗ ∗ 4·Cmax ∗ ∗ + Cmax hosszal befejez®dik Cmax . Azaz Cmax ≤ Cmax + pj ≤ Cmax = , 3 3 ezzel az állítást erre az esetre beláttuk. 2. pj >
∗ Cmax 3
. ∗
. Ekkor Mivel j a legrövidebb feladat, ezért minden i feladatra pi > Cmax 3 minden processzor maximum 2 feladaton dolgozhat az optimális ütemezéskor, így 2 · m ≥ n. Az els® m feladatot LPT sorrendben kezdjük el a 0 id®ben végrehajtani a processzorokon, majd amikor egy processzor felszabadul, akkor rendeljük az LPT sorrendben következ® feladathoz. Ezzel a leghosszabb feladatoknak nem lesz csak párja, ami ugyanazon a processzoron futna, a rövidebbeket pedig a lehet® leghatékonyabban, a kisebbeket a nagyobbakkal párosítva ütemeztük, így ennél gyorsabb ütemezés nincs is ebben az esetben, így ∗ , természetesen erre is teljesül a fenti egyenl®tlenség. Cmax = Cmax
Ezek után nézzük az algoritmus hatékonyságát az eredeti, egy feladaton több processzor együttes munkáját is megenged® problémára. Az optimális ütemezés megtalálása továbbra is N P -nehéz. Az algoritmus alapgondolata az, hogy az LPT algoritmus elkészítése után iterálva módosítsuk azt úgy, hogy a feladatokhoz több processzort rendelünk, ezzel csökkentve a végrehajtási id®t. Ehhez minden i feladathoz vezessünk be egy si értéket, ami az i-n aktuálisan dolgozó processzorszámot jelöli. Az algoritmus során folyamatosan növeljük a processzorszámot bizonyos feladatokon. Azonban csak akkor engedünk meg egy processzorszám növelést, ha az azonnali csökkenést okoz a végrehajtási id®ben. Az algoritmus a következ®:
Javított LPT algoritmus 1. si := 1, ∀ 1 ≤ i ≤ n. Valamint a := m, ahol a az m − si >1 si értéket veszi majd fel az algoritmus során. A feladatokra végezzük el az LPT ütemezést. P
2. Ha a = 0, akkor térjünk az 5. lépésre. Különben válasszunk ki egy olyan i feladatot, amelyre fip(si i ) ≥ fjp(sj j ) , ∀j 1 ≤ j ≤ n. h := fip(si i ) . 3. Ha a = 1 és si = 1, vagy Cmax 6= h, akkor térjünk az 5. lépésre. Különben folytassuk a 4.-kel. 14
4. Ha si = 1, akkor a := a − 2, különben a := a − 1. si := si + 1. Készítsük el a következ® C 0 ütemezést: el®ször határozzuk meg azokat a j feladatokat, melyekre sj > 1, és ezekhez a megfelel® sj darabszámú processzort rendeljük (az összdarabszám nem nagyobb m-nél). Majd a maradék feladatokra végez0 zük el az LPT algoritmust. Ha Cmax > h, akkor si := si − 1 és térjünk az 5. lépésre. Különben C := C 0 és térjünk vissza a 2. lépésre. 5. A kapott ütemezés lesz a Javított LPT algoritmus végs® ütemezése, ezt nevezzük A-nak. A célunk az, hogy belássuk, hogy a Javított LPT algoritmus 1+2 1 approximációs m algoritmus erre a problémára. Ennek bizonyításához belátunk több lemmát, de el®ször vezessünk be néhány új jelölést és kifejezést. Legyen S egy ütemezés. Jelölje ki (S) az i feladatot végz® processzorok számát S -ben. Ha egy i feladaton ki (S) > 1 processzor dolgozik, akkor azt úgy is kezelhetjük, mintha ki (S) darab részfeladat lenne, mindegyik fi (kpii(S)) végrehajtási id®vel, mindegyiken egy processzort dolgoztatva. Ezeket a részfeladatokat nevezzük hasított feladatoknak. A többi esetben, amikor ki (S) = 1, azon i feladatokat hasítatlan feladatoknak hívjuk. Ezen két fajta feladat ütemezése esetén gyelni kell arra, hogy a hasított feladatok mindig egy id®ben kezd®djenek. Az aktuális megoldásunkban , azaz a Javított LPT algoritmusban el®ször a hasított feladatokhoz rendeljünk processzorokat, majd a hasítatlan feladatokhoz az LPT sorrendjüket alkalmazva. Az algoritmusban használt a változó garantálja, hogy maximum m hasított feladat lesz. Így az, hogy egyszerre kezd®dnek nem sérti meg az ütemezési feltételeket. A lemmáink el®tt pedig két de níció:
Legyen AV G(S) az S ütemezésben az m darab P processzor átlagos munkavégzési ideje az egész folyamat alatt. Azaz AV G(S) := · 4.3. De níció.
1 m
m pi ·ki (S) i=1 fi (ki (S))
Legyennh(S) a maximális végrehajtási idej¶ feladat az S ütemezéso ben. Azaz h(S) := max . 4.4. De níció.
pi fi (ki (S))
Most pedig következzen az algoritmus hatékonyságáról korábban feltetteket igazoló lemmasor:
4.5. Lemma. Smax ≥ max {h(S), AV G(S)}.
Bizonyítás: A befejezési id® nem lehet kevesebb sem az átlagos processzor mun-
kavégzési id®nél, sem a leghosszabb feladat hosszánál, így ez triviális.
15
Ha A 6= A , akkor k (A) ≤ k (OP T ), ∀1 ≤ i ≤ n, ahol A a Javított LPT algoritmus által kapott ütemezés, OP T pedig az optimális ütemezés.
4.6. Lemma.
max
∗ max
i
i
Bizonyítás: Bizonyítsuk az állítást indirekten.
Tegyük fel, hogy ∃i: ki (A) > ki (OP T ). Mivel a Javított LPT algoritmus során folyamatosan 1-esével növeltük az i feladatnál használt processzorok számát, ezért volt egy pillanat, amikor si = ki (OP T ) teljesült. Majd az i feladat kapott még egy processzort az algoritmus ugyanezen szakaszán, mivel a 3. lépés állítása igaz rá. Ez azt is jelenti egyúttal, hogy pi az aktuális ütemezés befejezési ideje ebben a szakaszban fi (ki (OP . Mivel az aktuáT )) pi lis befejezési id® az algoritmus során végig csak csökkenhet, ezért Amax ≤ fi (ki (OP . T )) A 4.5. Lemma szerint mivel az i feladaton ki (OP T ) darab processzor dolgozik az pi optimális megoldásban, ezért Amax ∗ ≥ fi (ki (OP . Azaz Amax ≤ A∗max , amivel elT )) lentmondáshoz jutottunk, ezzel bizonyítva a lemmát.
4.7. Lemma.
Ha A
max
6= A∗max
, akkor AV G(A) ≤ AV G(OP T )
Bizonyítás: Az f
függvények konkáv tulajdonsága miatt, a bevezetésben leírtak miatt ≥ , ∀r ∈ {1, 2, ...m − 1}, így a reciprokaikra pozitív értékek lévén megfordul az egyenl®tlenség: fjr(r) ≤ fjr+1 . Mivel a 4.6. Lemma szerint (r+1) ki (OP T ) ki (A) ki (A) ≤ ki (OP T ), ezért fi (ki (A)) ≤ fi (ki (OP T )) ∀i feladatra. Az egyenl®tlenségek mindkét oldalát pi -vel megszorozva, majd ezeket átlagolva kapjuk a lemma állítását. fj (r) r
i fj (r+1) r+1
Legyen S egy olyan ütemezés, ahol a hasított és hasítatlan feladatok az algoritmus 4. lépésében leírtak alapján követik egymást. A hasított feladatok száma, x nem nagyobb m-nél. Legyen y a végrehajtási ideje az m − x + 1. legnagyobb hasítatlan feladatnak (ha nincs ennyi hasítatlan feladat, akkor y := 0). Ekkor
4.8. Lemma.
Smax
1 ≤ max h(S), AV G(S) + y · (1 − ) m
. Bizonyítás: Az S ütemezés befejezési ideje egybeesik egy 0 id®pontban elkezdett
i feladat befejezési idejével, vagy egy kés®bb elkezdett befejezési idejével. Az el®bbi
esetben Smax = h(S), ahol h(S)-ben az i feladat szerepel, így igaz a lemma. Az i utóbbi esetben pedig i egy hasítatlan feladat, amire fip(1) ≤ y . Ez azért van, mert a legnagyobb m − x hasítatlan feladatot a 0 id®pontban kezdjük el. Az i feladat az i Smax − fip(1) id®pontban kezd®dik. Az LPT algoritmus nem engedi, hogy bármelyik 16
i processzor is leálljon ez el®tt az id®pont el®tt. Ezért Smax − fip(1) ≤ AV G0 , ahol AV G0 pi , az ekkor épp futó feladatok átlagos befejezési ideje. De AV G0 ≤ AV G(S) − fi (1)·m mert az AV G0 -ben vett feladatokat végz® processzorok nem állhatnak le, miel®tt i elvégeznék a feladatokat, valamint az i feladaton dolgozó processzor i-n fip(1) ideig pi dolgozik, ezzel fi (1)·m -mel növelve a processzorok átlagos munkavégzési idejét. A két i egyenl®tlenséget összevonva: Smax ≤ AV G(S)+ fip(1) ·(1− m1 ) ≤ AV G(S)+y·(1− m1 ), ezzel beláttuk a lemmát.
Legyen C a Javított LPT algoritmus során kialakuló ütemezések közül egy. Legyen z a végrehajtási ideje egy hasított feladatnak C -ben. Ekkor C ≤ 2 · z. 4.9. Lemma.
max
Bizonyítás: Legyen i a z végrehajtási id®höz tartozó feladat. Ekkor z =
. Az algoritmus 3. lépése miatt egyértelm¶, hogy Cmax ≤ , mivel valamikor hozzáadtak még egy processzort az i feladat elvégzéséhez, hogy az akkori Cmax tovább csökkenhessen. Az f függvények konkávsága miatt tetsz®leges j processzorj számot egy feladaton j + 1-re növelve, a végrehajtási id® maximum a j+1 -szeresére csökkenhet, és mivel j ≥ 1, ezért ez maximálisan 2-szeres gyorsítást jelent. Azaz pi i ≤ fi (k2·p = 2 · z . A két egyenl®tlenséget összevonva kapjuk a lemma fi (ki (C)−1) i (C)) állítását. pi fi (ki (C))
pi fi (ki (C)−1)
Legyen C a Javított LPT algoritmus során kialakuló ütemezések közül egy. Legyen x a hasított feladatok száma, y pedig az m − x + 1. legnagyobb hasítatlan feladat végrehajtási ideje. Ekkor: 1. y ≤ , ∀i | k (C) > 1. n o 2. C ≤ max h(C), . 4.10. Lemma.
pi fi (ki (C))
max
i
2·AV G(C) 1 1+ m
Bizonyítás: Az 1. állításhoz azt kell belátnunk, hogy y kisebb az összes hasí-
tott feladat végrehajtási idejénél. Legyen i a legkisebb végrehajtási idej¶ feladat a hasított feladatok közül. Legyen z ennek végrehajtási ideje, azaz fi (kpii(C)) . A 4.9. Lemmából következik, hogy Cmax ≤ 2 · z . Ha indirekten feltesszük, hogy z < y , akkor Cmax ≥ y + z egyenl®tlenség teljesülni fog, mivel az y végrehajtási id®höz tartozó hasítatlan feladat egy legalább z végrehajtási idej¶ hasított feladat befejezése után kezd®dik, vagy egy legalább y végrehajtási idej¶ hasítalan feladat után. Ebb®l azt kapjuk, hogy 2 · z ≥ z + y , azaz z ≥ y , amivel ellentmondáshoz jutottunk, ezzel belátva az 1. állítást. Azt 1. állítás következményeként az y -hoz tartozó feladat 17
végrehajtási ideje maximum akkora, mint az x hasított feladat bármelyikének végrehajtási ideje. Szintén tudjuk, hogy y nem nagyobb az m − x legnagyobb hasítatlan feladat bármelyikének végrehajtási idejénél a de níció szerint. Összességében így van m + 1 feladatunk legalább y végrehajtási id®vel, így a processzorok munkavégzési idejére AV G(C) ≥ y + my , átrendezve y ≤ AV1+G(C) . Ebb®l és a 4.8. Lemmából 1 m
n
következik, hogy Smax ≤ max h(S), AV G(S) + zik a 2. állítás.
4.11. Tétel.
AV G(C) 1 1+ m
· (1 −
o
1 ) m
, amib®l követke
Legyen A a Javított LPT algoritmus által kapott ütemezés. Ekkor: Amax ≤
. Bizonyítás: Feltehet®, hogy C
max
2 ∗ 1 · Amax 1+ m
∗ , különben az állítás triviálisan igaz. 6= Cmax
Ekkor h(A) mérete szerint vizsgáljunk két f® esetet: 1. Cmax 6= h(A). A 4.5. Lemma alapján Amax ≥ max {h(A), AV G(A)}. Ebben az esetben ez azt jelenti, hogy Amax > h(A). A 4.10. Lemma 2. állítása miatt Amax ≤ 2·AV G(A) . A 4.7. Lemma szerint AV G(A) ≤ AV G(OP T ), és a 4.3. Lemma 1 1+ m ∗ miatt az optimális ütemezésre AV G(OP T ) ≤ Cmax . Ezeket összevonva kapjuk a Amax ≤ 1+2 1 · A∗max egyenl®tlenséget, ami a bizonyítandó állítás volt. m
2. Cmax = h(A). Ebben az esetben vizsgáljuk meg azt, hogy az algoritmus melyik lépéséb®l érkeztünk az 5. lépésre, azaz miért fejez®dött be az algoritmus. Legyen b egy h(A) végrehajtási idej¶ feladat, ilyen a feltétel miatt van. Ekkor h(A) = pb . Legyen az A ütemezésben lév® hasított feladatok száma x. fb (kb (A)) (a) Az algoritmus azért állt le, mert a = 0 lett a 2. lépésben vagy a = 1 és kb (A) = 1 (azaz b egy hasítatlan feladat). Az els® esetben m, a másodikban m − 1 a hasított feladatok száma. Legyen z a minimális l végrehajtási idej¶ l hasított feladat végrehajtási ideje, azaz z = fl (kpl (A)) . Mivel legalább m − 1 hasított feladatunk van legalább z végrehajtási id®vel, valamint még egy feladat h(A) végrehajtási id®vel, ezért AV G(A) ≥ z · (1 − m1 ) + h(A) . Mivel Amax = h(A), ezért átírhatjuk az egyenm AV G(A)− Amax m l®tlenséget z -re rendezve: z ≤ . A 4.9. Lemma alapján 1 1− m 2 · z ≥ Amax . Ezt felhasználva Amax -ra rendezve az egyel®tlenséget: 18
2·A∗max 1 1+ m
, ahol az els® egyenl®tlenség a 4.5. Lemmából, a második a 4.7. Lemmából következik, ezzel beláttuk a tétel állítását ebben az esetben is. Amax ≤
2·AV G(A) 1 1+ m
≤
(b) Az algoritmus azért állt le, mert a 3. lépésében Cmax 6= h(A). Ezt már vizsgáltuk az 1. f® esetnél. (c) Az algoritmus azért állt le, mert a 4. lépésben kapott C 0 ütemezésre 0 > h(A). A hasított feladatok száma C 0 -ben a 4. lépés növelése miCmax att: x0 = x + 1. Legyen y a m − x0 + 1. legnagyobb végrehajtási idej¶ hasítatlan feladat. A 4.6. Lemmából: kb (OP T ) ≥ kb (A). Ha ez egyenl®séggel teljesül, akkor a 4.5. Lemma miatt A∗max ≥ fb (kpbb(A)) = h(A) = Amax , azaz A∗max = Amax , azaz teljesül a tétel egyenl®tlensége. Ha pedig kb (OP T ) > kb (A), akkor kb (OP T ) ≥ kb (A) + 1 = kb (C 0 ). Ebb®l és a 4.7. Lemma alapján AV G(C 0 ) ≤ AV G(OP T ) ≤ A∗max . Az y nagysága alapján tekintsünk két alesetet: i. Az y érték nem nagyobb, mint bármely C 0 -beli hasított feladat végrehajtási ideje. n o G(C 0 ) 0 ≤ max h(C 0 ), 2·AV A 4.10. Lemma 2. állítása alapján Cmax . 1 1+ m 0 Mivel Cmax > h(A) ≥ h(C 0 ), ezért az el®bbi egyenl®tlenség csak G(C 0 ) 2·A∗max 0 úgy teljesülhet, ha Cmax ≤ 2·AV ≤ 1 1 . Ugyanakkor Amax = 1+ m 1+ m 0 , így ezen két egyenl®tlenség összevonásával kapjuk a h(A) < Cmax bizonyítandó állítást. ii. Van olyan hasított feladat, melynek végrehajtási ideje kisebb, mint az y érték. Legyen z a minimális hasított feladat végrehajtási id® C 0 -ban, és a hozzá tartozó feladat l. Ekkor y > z , valamint z nem nagyobb, mint x0 hasított, és m − x0 hasítatlan feladat végrehajtási ideje. Ezeken kívül van még az y végrehajtási id®höz tartozó feladat, így a processzorok átlagos munkavégzése alulról becsülhet®: AV G(C 0 ) ≥ y ≥ z+ m ≥ z ·(1+ m1 ). Ha b 6= l, akkor az l feladathoz az A és a C 0 ütemezésben azonos processzorszám tartozik. Emiatt ha alkalmazzuk a 4.9. Lemmát az A ütemezésre, azt kapjuk, hogy Amax ≤ 2 · z . Ha b b = l, akkor Amax = fb (kpbb(A)) ≤ fb (kbp(A)+1) , mivel kb (C 0 ) = kb (A) + 1. Így mindkét esetben azt kaptuk, hogy Amax ≤ 2 · z . A fenti egyenl®t0) ∗ max lenségekb®l következik, hogy Amax ≤ 2·AV1+G(C ≤ 2·C 1 1 , amivel az 1+ m m utolsó esetre is beláttuk a tétel állítását.
19
4.12. Tétel.
[14].
A Javított LPT algoritmus futásideje O(n · log n + n · m · log m) [13],
Bizonyítás: A Javított LPT algoritmus a listás algoritmuson alapul, melynek
futásideje O(n · log n + n · log m). Ehhez képest az új algoritmus az 1. lépésben elkészíti a listás ütemezést, a 2. lépésében O(log n) id® alatt megtalálja a leghosszabb futásidej¶ feladatot, és végül a 4. lépés miatt az egész folyamatot maximum m-szer a 2. lépést®l újrakezdi, ami így az eredeti listás ütemezés O(n · log n) tagját nem változtatja, a 4. lépés miatt pedig az összes feladat közül meg kell keresni az aktuálisan leghamarabb végz® processzort, maximum m-szer, amihez O(n · m · log m) id®re van még szükség, azaz összesen O(n · log n + n · m · log m) a futásid®, ezt kellett bizonyítanunk. Nézzünk egy példát az algoritmus m¶ködésére, konkáv sebességfüggvények esetén. Legyen m = n = 5. Az egyes feladatok végrehajtási idejeit aszerint, hogy j hány processzor dolgozik rajtuk (azaz a fjp(r) hányadosokat) mutatja a 4.1. táblázat. A kezdeti LPT ütemezés a 4.2. ábra szerint alakul, minden feladat az aktuálisan legel®ször felszabaduló processzorhoz kerül, most m = n esetén ez azt jelenti, hogy minden feladat a 0 id®pontban kezd®dik. Az algoritmus lépésein végighaladva el®ször kiválasztjuk a 2. lépésben az 1. feladatot, és h-t 12-re állítjuk. A 3. lépésben leellen®rizzük, hogy az aktuális befejezési id® egybeesik h-val, majd az 1. feladat processzorszámát 1-r®l 2-re növeljük. A többi feladat új LPT ütemezésével az új befejezési id® 10 (4.3. ábra), ami jobb az eddiginél, visszatérhetünk a 2. lépésre. Innent®l pedig az eddigi m¶veletsort ismételjük: a 2. feladat fog egy helyett két processzoron végrehajtódni, az új befejezési id® 8, ami ismét javulást jelent (4.4. ábra). Ezután ismét az 1. feladat processzorszámát növeljük, mely által kapott ütemezés 7, 5 ideig tart, ami újra jobb az el®z®nél (4.5. ábra). Azonban ekkor a 2. lépés a 2. feladatot választja ki, mivel ennek a legnagyobb az aktuális végrehajtási ideje, azonban ez 7, míg h = 7, 5, így a folyamat a 3. lépésr®l az 5.-re ugrik, és ott a 4.5 ábrán látható ütemezéssel leáll, így ez lesz az algoritmus által kapott processzorszétosztás.
20
id®
processzorok
12 11 10 9 8 7 6 5 4 3 2 1
1
12
10
2
8
7
1
1,5
1
3
6
6
1
1,5
1
4
5
6
1
1,5
1
5
5
6
1
1,5
1
1.
2.
3.
4.
5. f eladatok
1,5 1,5 1,5
12 11 10 9 8 7 6 5 4 3 2 1
1
1
2
12 11 10 9 8 7 6 5 4 3 2 1
2
3
5 3 4
4 5 processzorok
4.3. Az ütemezés 2. állapota
id®
12 11 10 9 8 7 6 5 4 3 2 1
2
2
3 3
4 4
5 5 processzorok
4.2. Kezdeti LPT ütemezés
id®
6
1
1
1
4.1. Végrehajtási id®k a processzorszám szerint
id®
6
6
1
1
2
2
1
2
3
4
5 4 3 5 processzorok
4.4. Az ütemezés 3. állapota
6
3
4
5
1
1
1
2
2
1
2
3
4
5 processzorok
4.5. A végs® ütemezés
21
-
4.2. Az optimális ütemezés A konkáv tulajdonságukat O(mn) lépésben ellen®rizhetjük, ahogy a konvex esetben is tettük. Mivel az fj -k konkávok és szakaszonként lineárisak, ezért az U halmaz egy n-dimenziós konvex poliéder. Így convU = U ebben az esetben.
4.2.1. A P-CNTN eset Jelölje fˆj (r) a szigorúan monoton növ® részét az fj (r) függvénynek. Mivel fj (r) konkáv, ezért ∃mj ∈ {1, 2, . . . m}, amire fˆj (r) = fj (r), ha 0 ≤ r ≤ mj , és fj (r) = fj (m), ha mj ≤ r ≤ m. Valamint az fj függvénynek nincs szakadási pontja az (ˆrj0 , m) intervallumon. Legyen r0 a már de niált optimális er®forrás szétosztás. X jelölje azoknak a j feladatoknak a halmazát, melyekre rj0 > mj . Könnyen belátható, hogy a következ® rˆ0 processzorszétosztás is optimális: rˆj0 = rj0 , ha j ∈/ X , és rˆj0 = mj , ha j ∈ X . Mivel az fˆj függvény már injektív, ezért vehetjük az fˆj−1 inverz függvényét. Legyenek az fˆ(r) = u és az fˆ−1 (u) = r egyenletekben szerepl® u és v vektorok azok, melyekre fˆj (rj ) = uj , ∀j ∈ {1, 2, . . . n}. Az optimális megoldás elkészítéséhez a 2.1. tételt használjuk. Az u = Cp egyenes és a U konvex burkának határának metszéspontja (u0 ) és a hozzá tartozó optimális processzorszétosztás (r0 ) az alább leírtak alapján található meg. Legyen I azon pontok halmaza, melyek az uj = fj (rj ) | j ∈ {1, 2, . . . n} , rj ∈ {1, 2, . . . mj } síkok és az u = Cp | C > 0 min egyenes metszeteként állnak el®. Legyen az a pont, melyre a C érték minin o u pj mális. Ha min fj (mj ) | j ∈ {1, 2, . . . n} érték a j = j ∗ feladathoz tartozik, akkor ez az uj = fj ∗ (mj ∗ ) síknak és az u = Cp egyenesnek a metszéspontja. Továbbá P fˆ−1 (umin = rmin ) és nj=1 rjmin ≤ m, azaz rmin egy optimális ütemezés, ahonnan könnyen megkaphatjuk az r0 keresett ütemezést. P A megoldás további részében így feltehet®, hogy nj=1 rjmin > m. Legyen u egy P olyan I -beli pont, melyre fˆ−1 (u) = r, valamint nj=1 rj ≥ m, és nincs másik I -beli P u pont, amelyre u1 < u1 és nj=1 rj ≥ m, ahol r = fˆ−1 (u). Mivel u0 és u ugyanazon az u = Cp egyenesen fekszenek, és mivel u0 közelebb van az origóhoz, mint u, ezért ∀n-re: u0j ≤ uj , valamint rˆj0 ≤ rj . Ráadásul mivel nincs más u ∈ I pont az u0 és az u pontok között, ezért egyik fj függvénynek sincs töréspontja az rˆj0 , rj intervallumon, ezért az rj0 , rj intervallumon sem. Ezért, és a régebben tárgyalt (3) egyenlet miatt u0j = fj (rj0 ) = bj,drj e rj0 + dj,drj e =
pj , 0 Cmax
(7)
∀j ∈ {1, 2, ...n}. Ezt az egyenletet átrendezve kapjuk, hogy rj0 =
dj,drj e pj − , 0 bj,drj e · Cmax bj,drj e
22
(8)
∀j ∈ {1, 2, . . . n}. Mivel az u0 pont U konvex burkának határán fekszik, ezért Pn 0 j=1 rj = m, ezt hozzávéve a (8) egyenlethez: pj
Pn
j=1 b
d e
j, r j
0 Cmax =
d
m+
Pn
j=1
d e b j,dr j e
(9)
,
j, r j
valamint az u0 és r0 értékeket a (7) és (8) egyenletekb®l számolhatjuk. Mivel pj = P 0 ∀j ∈ {1, 2, . . . n} és nj=1 rj0 = m, ezért ezzel egy olyan optimális ütemezést u0j Cmax 0 kapunk a P-CNTN problémára, ahol minden feladat a (0, Cmax ) intervallumon belül fut, és a j feladat rj0 processzort használ ∀j ∈ {1, 2, . . . n}. Az eddigiekb®l látszik, hogy ahhoz, hogy kiszámoljuk az r0 és u0 vektorokat, ahhoz meg kell találni az r processzorszétosztást. Ehhez el®ször minden j feladathoz végezzük el a következ® felezéses keres® algoritmust uj := Φ, l = 0 és t = mj kezd®értékekkel:
BS felezéses keres® algoritmus
1. Az algoritmus els® iterációjában r = mj -re, minden további iterációjában r = l+t (j) (j) -re számoljuk ki az u(j) = u(j) 1 , u2 , . . . un metszéspontját az uj = fj (r) 2 (j) pi ·fj (r) , ahol i 6= j . síknak és az u = Cp egyenesnek, ahol u(j) j = fj (r) és ui = pj 2. Számoljuk ki az r(j) = fˆ−1 (u (j)) értékeket a következ® módon: el®ször rj(j) := r. Minden i 6= j -re keressük meg az si ∈ {1, 2, . . . mj } töréspontot, melyre (j) fi (si − 1) < ui ≤ fi (si ). 3. Ha
(j) ≥ i=1 ri Pn (j) i=1 ri < m
Pn
m, akkor u(j) := u(j) , t := r, és l-et hagyjuk változatlanul. Ha
, akkor l := r és t-t hagyjuk változatlanul.
4. Ha t − l < 1, akkor ugorjunk az 5. lépésre. Ha nem, akkor lépjünk vissza az 1. lépésre. ˆ−1 5. A keresett r ütemezést n a következ® módon kapjuk: ro= f (u), ahol u koor(j) dinátáit az ul = min u(j) 6= Φ, ∀j ∈ {1, 2, . . . n} egyenl®ségb®l kapjuk. l | u
4.13. Tétel.
A P-CNTN feladat O(n·max m, n log
2
m )
id® alatt megoldható [23].
Bizonyítás: A BS felezéses keres® algoritmus iterációszáma nem haladja meg
O(log m)-et, mert az r érték mindig az l és t értékek átlaga, amelyek különbsége
a 3. lépés szabálya szerint így minden lépésben felez®dik, 1 O(log mj ) lépés alatt lesz. Az 1. lépés O(n) id® alatt megvalósítható, a 2. lépésnél rj(j) megtalálásához felez® algoritmust használva a {0, 1, . . . mj } értékeken O(n · log m) id® szükséges. 23
Nem konstans lépésszámot az 5. lépés végrehajtása igényel, mivel a keresett r kiszámításához mind az n koordinátájára el kell végeznünk az algoritmust, ezzel eddig összesen O(n2 · log2 m) id®nél tartunk. Valamint szükségünk van O(m · n) id®re a szakaszonként lineáris fj függvények együtthatóinak kiszámolásához, így a két id® közül a nagyobbikra van szükségünk az algoritmus elvégzéséhez, ezzel beláttuk a tételt.
4.2.2. A P-DSCR eset Ebben az esetben a feladatokon csak egész számú processzor dolgozhat. Bizonyított, ∗ 0 hogy ekkor Cmax = Cmax , azaz a megoldás összefügg a P-CNTN eset megoldásával. Ez n = 2 és n = 3 esetekben azt jelenti, hogy konstans id® alatt megkaphatjuk a P0 DSCR feladat optimális ütemezését a P-CNTN feladat megoldásának (r0 , u0 , Cmax ) ismeretében.
Az n=2 eset:
Ha r0 egész koordinátájú, akkor meg is van az ütemezés, egész id® alatt r10 processzort dolgoztatunk az els®, és r20 processzort a második feladaton. Ha r0 nem egész koordinátájú, akkor legyen r(1) = (br10 c , dr20 e) és legyen r(2) = (dr10 e , br20 c). Ekkor r0 az (r(1) , r(2) ) szakaszon van P-CNTN szakaszos linearitása miatt. Ebben az esetben r0 = λ · r(1) + (1 − λ) · r(2) , ahol λ = dr10 e − r10 = r20 − br20 c. Mivel se az f1 , se az f2 függvénynek nincs töréspontja r(1) és r(2) között, ezért u0 = λ · f (r(1) ) + (1 − λ) · f (r(2) ). P-DSCR esetén az optimális ütemezésnek két futási 0 0 . A ∆1 intervallum alatt és ∆2 = (1 − λ) · Cmax intervallumhossza van, ∆1 = λ · Cmax az els® és második feladathoz rendelt processzorszám így rendre br10 c és dr20 e, a ∆2 intervallumon pedig dr10 e és br20 c
Az n=3 eset:
Ekkor 3 esetet különböztetünk meg: 1. r0 ∀ koordinátája egész, 2. r0 egyik koordinátája egész, a másik kett® nem, 3. r0 egyik koordinátája sem egész. Fontos megjegyezni, hogy olyan eset nincs, amikor r0 pontosan két koordinátája egész, mert ha van két egész koordinátája, abból következik, hogy a harmadik is az. 0 Az 1. eset triviális, hiszen ekkor a [0, Cmax ] futási intervallumon kell végrehajtanunk mindhárom feladatot, rj0 processzort használva a j feladathoz, j ∈ {1, 2, 3}. 24
A 2. esetben feltehetjük, hogy csak rj0 egész. Ekkor könnyen látható, hogy r0 az (r(1) , r(2) ) intervallumon van, ahol r(1) = (r10 , br20 c , m − r10 − br20 c) és r(2) = (r10 , dr20 e , m − r10 − dr20 e). Azaz r0 = λ · r(1) + (1 − λ) · r(2) , ahol λ = dr20 e − r20 . 0 Az optimális ütemezésnél 2 futási intervallumot kapunk ∆1 = λ · Cmax és ∆2 = 0 (1−λ)·Cmax hosszokkal. Az els® feladathoz tartozó processzorszám mindkét esetben r10 . A ∆1 intervallumban a 2. feladat processzorszáma br20 c, a 3. feladaté m−r10 −br20 c, a ∆2 intervallumban pedig dr20 e illetve m − r10 − dr20 e. A 3. esetben r0 egy r(1) , r(2) , r(3) csúcsokkal rendelkez® háromszög belsejében van, ahol a csúcsok minden koordinátája egész, és az eddigi egészrészek által határolt, valamint a processzor kihasználás maximális, azaz: 1. rj(i) ∈ { rj0 , rj0 } i, j ∈ {1, 2, 3} és
2. r1(i) + r2(i) + r3(i) = m, i ∈ {1, 2, 3}. Ezt a két feltételt egyszerre a következ® négy pont teljesítheti: a = ( r10 , r20 , m − r10 − r20 ), b = ( r10 , r20 , m − r10 − r20 ), c = ( r10 , r20 , m − r10 − r20 ), d = ( r10 , r20 , m − r10 − r20 ).
Viszont a és b közül egyszerre csak az egyik elégítheti ki a feltételeket, mert ha mindkett® igaz lenne, akkor r30 alsó és fels® egészrésze között 2 lenne a különbség, ami nem lehetséges. Így ha dr10 e+dr20 e+br30 c = m, akkor r(1) := a, ellenkez® esetben r(1) := b. Az r0 -t tartalmazó háromszög másik két pontja pedig r(2) = c és r(3) = d. P Emiatt ∃ λ1 > 0, λ2 > 0, λ3 > 0, melyekre 3i=1 λi = 1 és rj0 = λ1 ·rj(1) +λ2 ·rj(2) +λ3 · (3) rj , j ∈ {1, 2, 3}. Ez a három ismeretlent tartalmazó, három lineáris egyenletb®l álló egyenletrendszer konstans id® alatt megoldható. Így végeredményként három futási 0 intervallumot kaptunk, melyek ∆i = λi · Cmax , i ∈ {1, 2, 3}, és ∆i intervallumban (i) a j feladathoz tartozó processzorszám rj , ahol i, j ∈ {1, 2, 3}. Ezzel konstans id® alatt megoldottuk a P-DSCR problémát n = 3 esetben is.
25
4.2.3. Példa a P-DSCR eset megoldására n=3 esetén Nézzük meg a gyakorlatban egy konkrét feladaton n = 3 esetén a megoldás menetét! A három feladatra p1 := 7, p2 := 5, p3 := 2. A processzorszám legyen 5. A √ végrehajtási sebesség függvény minden feladatra legyen gj (r) = r, amely valóban konkáv. Ekkor az algoritmusunk: 1. Számítsuk ki a szakaszonként lineáris fj (r) függvények együtthatóit az fj (r) = f (r) = bdre · r + ddre egyenletekb®l, ahol 0 ≤ r ≤ m, j ∈ {1, 2, . . . n}. Ezek a √ √ √ (0, 0), (1, 1), (2, 2), (3, 3), (4, 2), (5, 5) pontok közötti szakaszok egyenle√ √ teinek együtthatóit jelentik, azaz b1 = 1, d1 = 0, b2 = 2 − 1, d2 = 2 − 2, √ √ √ √ √ √ √ b3 = 3 − 2, d3 = 3 2 − 2 3, b4 = 2 − 3, d4 = 4 3 − 6, b5 = 5 − 2, √ d5 = 10 − 4 5. 2. Keressük meg azt az r processzorszétosztást, melyre f (r) ∈ I , nj=1 rj ≥ m P és @u ∈ I\{f (r)}, amire u1 < u1 és nj=1 rj ≥ m, ahol r = f −1 (u). A kapott érték: r = (3, 1.57, 0.49). P
∗ 3. Számoljuk ki Cmax -ot: pj
Pn
j=1 b
∗ 0 Cmax = Cmax =
dr j e d
m+
Pn
j=1
dr j e b dr j e
= 4, 07.
Az r0 kiszámolására használjuk a (8) formulát, ezzel r0 = (2.96, 1.55, 0.49). 4. Mivel r0 egyik koordinátája sem egész, ezért a 3. eset egyenleteit kielégít® r(i) pontokat kell kiszámolnunk, amik: r(1) = (2, 2, 1), r(1) = (3, 1, 1) és r(1) = (3, 2, 0). 5. Az ezekkel az együtthatókkal kapott lineáris egyenletrendszer: 2.96 = 2λ1 + 3λ2 + 3λ3 , 1.55 = 2λ1 + λ2 + 2λ3 , 0.49 = λ1 + λ2 ,
amib®l λ1 = 0.04, λ2 = 0.45 és λ3 = 0.51. 0 6. Végül számoljuk ki a keresett ∆i értékeket: ∆1 = λ1 Cmax = 0.17, ∆2 = 0 0 λ2 Cmax = 1.83, ∆3 = λ3 Cmax = 2.07. Ezt az optimális ütemezést ábrázolja a 4.6. gra kon.
26
id® ∗ Cmax
∆3
1. feladat
∆2
1. feladat
∆1
1
1. feladat
2
2. feladat
2. feladat
3
2. feladat
4
3. feladat 3. feladat 5 processzorok
4.6. Az optimális ütemezés a P-DSCR esetben
27
5.
Nyitott problémák
Akár az MPTS, akár az NPTS esetre csak a független feladatokra vizsgáltunk megoldási módszereket. A probléma kiterjeszthet® egymástól függ® feladatokra is. Ekkor minden feladathoz megadhatunk más feladatokat, melyek ennek a feladatnak el®feltételei, csak ezek elvégzése után kezdhetjük el a feladatot (természetesen ezt megoldani csak az el®feltételek körmentes megadása esetén lehetséges). Ennek további nehezítése az ún. on-line megel®zési feltételes modell. Ekkor bizonyos feladatok hosszáról, és egyáltalán létezésér®l csak akkor szerzünk tudomást, amikor már az összes el®feltételét elvégeztük. Mint korábban említettük Feldmann, Sgall, Teng és Kao foglalkozott behatóan ezzel az esettel, de b®ven találhatunk még megoldatlan problémákat ebben a témakörben. Az összes problémánál csak egy fajta er®forrást használtunk, a processzorokat. Ennek egy kiterjesztése az az eset, ha más er®forrásokat is igénybe vehetünk, vagy megszorításokat alkalmazunk rájuk, például változtatható memória követelményekkel. Végezetül szeretném megköszönni témavezet®mnek, Kis Tamásnak a segítségét és hasznos tanácsait, amik nélkül nem készülhetett volna el a dolgozatom ebben a formájában.
28
Hivatkozások
[1] [2]
: Orthogonal packing in two dimensions, SIAM journal on computing 9(4), 846-855., 1980. B. Baker, E. Coffman and R. Rivest
Approximate algorithms for the partitionable independent task scheduling problem, Proceedings of the 1990 InternaK. P. Belkhale and P. Banerjee
:
tional conference on parallel processing vol. I, 72-75., 1990.
: A parallel algorithm for hierarchical circuit extraction, International Conference on computer aided design, 236-239., 1990.
[3]
K. P. Belkhale and P. Banerjee
[4]
J. Bªa»ewicz, M. Machowiak, J. W¦glarz, M. Kovalyov and D.
:
Trystram
Scheduling malleable tasks on parallel processors to minimize
the makespan, Annals of Operations Research, Kluwer Academic Publishers 129(16), 65-80., 2004. [5]
: Scheduling multiprocessor lenght, IEEE Transactions on computing 35, 389-
J. Bªa»ewicz, M. Drabowski and J. W¦glarz
tasks to minimize schedule
393., 1986.
: General arch logistics 46(1), 57-74., 1999.
multiprocessor task scheduling, Naval rese-
[6]
J. Chen and C. Y. Lee
[7]
E. G. Coffman Jr., M. R. Garey, D. S. Johnson and R. E. Tar-
:
jan
Performance bounds for level-oriented two-dimensional packing algo-
rithms, SIAM journal on computing 9(4), 808-826., 1980. [8]
[9] [10] [11]
: Numerical linearalgebra for high performance computers, Philadelphia, Society for Industrial and Applied Mathematics, 1999. J. Dongarra, L. Duff, D. Danny, C. Sorensen and H. van der Vorst
: Scheduling multiprocessor tasks journal of operational research 94, 215-230., 1996.
M. Drozdowski
- an overview, European
: Complexity of scheduling parallel journal on discrete mathematics 2(4), 473-487., 1989. J. Du and J. Leung
task systems, SIAM
: Optimal online scheduling of parallel jobs with dependencies, Proceedings of the twenty- fth annual ACM symposium on the theory of computing, 642-651., 1993. A. Feldmann, M.-Y. Kao, J. Sgall and S.-H. Teng
29
[12]
[13] [14] [15]
: Dynamic scheduling on parallel machines, 32nd annual symposium on foundations of computer science, 111120-, 1991. A. Feldmann, J. Sgall and S.-H. Teng
: Computers and intractability, A guide to the theory of NP-completeness, New York, W. H. Freeman and Company, 1979.
M. R. Garey and D. S. Johnson
: Bounds of multiprocessing timing on applied mathematics vol. 17, 263-269., 1969. R. L. Graham
anomalies, SIAM journal
R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy
Optimalization and approximation in deterministic sequencing and scheduling: A survey, Annals of discrete mathematics vol. 5, 287-326., 1979. [16] : The processor partitioning problem in specialpurpose partitionable systems, Proceedings of the 1988 International conference :
Kan
R. Krishnamurti and E. Ma
on parallel processing vol. I, 434-443., 1988.
[17]
:
A. Lodi, S. Martello and M. Monaci
Two-dimensional packing problems:
a survey, European journal of operational research 141(2), 241-252., 2002. [18] : Algorithms for scheduling malleable and nonmalleable parallel tasks, PhD. thesis, University of Wisconsin-Madison, Department of Computer W. T. Ludwig
Science, 1995.
[19]
: Scheduling Malleable and Nonmalleable Parallel Tasks, Proceedings of the fth annual ACM-SIAM symposium on Discrete algorithms, 167-176., 1994. W. T. Ludwig, and P. Tiwari
: E cent approximation algorithms for scheduling malleable tasks, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, 23-32., 1999.
[20]
G. Mounie, C. Rapine and D. Trystram
[21]
G. N. S. Prasanna and B. R. Musicus
: The optimal scheduling, Algorithmica, 1995.
control approach to
generalized multiprocessor [22] : A 2,5 times optimal algorithm for packing in two dimensions, D. Sleator
Information processing letters 10(1), 37-40., 1980.
[23]
: Discrete science, Englewood Clis, Prentice-Hall, 1977.
D. F. Stanat and D. F. McAllister
30
mathematics in computer
: Approximate algorithms for scheduling parallelizable tasks, 4th Annual ACM symposium on parallel algorithms and architectures, 323-332., 1992.
[24]
J. Turek, J. Wolf and P. Yu
[25]
J. W¦glarz
[26]
: Project scheduling with continously-divisible, doubly constrained resources, Management Science 27, 1040-1052., 1981.
Modelling and controll of dynamic resource allocation project scheduling systems, S. G. Tzafestas, Optimization and control of dynamic opeJ. W¦glarz
:
rational research models, Amstredam: North-Holland, 1982.
31
