Диссертация (1150610), страница 11
Текст из файла (страница 11)
Îáîçíà÷èì V0 (x) = {i ∈ V \ {s, t} | [B 0T x +B 0T b]i = 0}, V− (x) = {i ∈ V \ {s, t} | [B 0T x + B 0T b]i < 0}, V+ (x) ={i ∈ V \ {s, t} | [B 0T x + B 0T b]i > 0}. Êëþ÷åâûì â ñâåäåíèè çàäà÷è îìàêñèìàëüíîì ïîòîêå ê çàäà÷å (2.16) ÿâëÿåòñÿ ñëåäóþùàÿ òåîðåìà:Ò å î ð å ì à2.7.Åñëè x∗ ðåøåíèå çàäà÷è (2.16), òî1. Ìíîæåñòâà A = {s} ∪ V+ (x∗ ) ∪ V0 (x∗ ) è V \ A îáðàçóþò ìèíèìàëüíûé st-ðàçðåç ãðàôà G.2. Äëÿ ïîëó÷åíèÿ ìàêñèìàëüíîãî ïîòîêà äîñòàòî÷íî ïðîâåñòè ÷àñòè÷íóþ äåêîìïîçèöèþ ïîòîêà x∗ .Äîêàçàòåëüñòâî.
Âî-ïåðâûõ, ïðèìåíÿÿ óñëîâèÿ Êàðóøà-Êóíà-Òàêåðà êçàäà÷å (2.16) ïîëó÷àåì0 ∗0 ∗ [B x + b]j − [B x + b]i + µe − se = 0,µ, s ≥ 0m ,0 = µe (ce − xe ) = se xe ,ãäå e = (i, j), µe ìíîæèòåëü Ëàãðàíæà, ñîîòâåòñòâóþùèé îãðàíè÷åíèþxe ≤ ce , à se ìíîæèòåëü Ëàãðàíæà, ñîîòâåòñòâóþùèé 0 ≤ xe .  äàííîìñëó÷àå êàê se , òàê è µe èãðàåò âñïîìîãàòåëüíóþ ðîëü, è îò íèõ ìîæíîèçáàâèòüñÿ ñëåäóþùèì îáðàçîì: ïóñòü Ex = {e = (i, j) ∈ E 0 | ce − xe >0}∪{(j, i) | e = (i, j) ∈ E 0 , xe > 0}, òîãäà óñëîâèÿ ÊÊÒ äëÿ (2.16) ìîæíîïåðåïèñàòü â âèäå(2.17)[B 0 x∗ + b]i ≤ [B 0 x∗ + b]j , (i, j) ∈ Ex∗ .Ïðîùå ãîâîðÿ, åñëè èçáûòîê âåðøèíû i (âåëè÷èíà [B 0 x + b]i ) áîëüøå èçáûòêà âåðøèíû j , òî (i, j) ∈/ Ex∗ .
Òåïåðü âåðíåìñÿ ê èñõîäíîìó ãðàôó" G#.Èçáûòîê ïîòîêà äëÿ âåðøèí èç â ãðàôå G çàäàåòñÿ âåêòîðîì B78x∗,c00ïî ïîñòðîåíèþ äëÿ âåðøèí, îòëè÷íûõ îò s, t, îí ñîâïàäàåò ñ B 0 x + b,äëÿ èñòîêà s ýòî âåëè÷èíà (−≤ 0, äëÿ ñòîêà âåëè÷èíà(i,t)∈E ce ≥ 0. Èç òåîðåìû î äåêîìïîçèöèè ïîòîêà ñóùåñòâóåò êîíå÷íûé íàáîð ïóòåé, êàæäûé èç êîòîðûõ âåäåò èç âåðøèíû ñ îòðèöàòåëüíûì èçáûòêîì â âåðøèíó ñ ïîëîæèòåëüíûì èçáûòêîì è ïðîõîäèò òîëüêîïî äóãàì ñ ïîëîæèòåëüíûì ïîòîêîì.
 ñèëó (2.17) äëÿ âåðøèí ñ ïîëîæèòåëüíûì èçáûòêîì êðîìå t òàêîé ïóòü ïîëíîñòüþ ïðîõîäèò òîëüêîïî âåðøèíàì èç A, à çíà÷èò íà÷èíàåòñÿ â s, äëÿ âåðøèí ñ îòðèöàòåëüíûì èçáûòêîì êðîìå s òàêîé ïóòü ïîëíîñòüþ ïðîõäèò òîëüêî ïî âåðøèíàì èç V \ A, à çíà÷èò çàêàí÷èâàåòñÿ â t. Ïóñòü, y ïîòîê, ïîëó÷èâøèéñÿ â ðåçóëüòàòå óäàëåíèÿ ïîòîêà ïî ñîîòâåòñòâóþùèì ïóòÿì èçs â V+ (x∗ ) è ïóòÿì èç V− (x∗ ) â t. Ïî ïîñòðîåíèþ y ÿâëÿåòñÿ äîïóñòèìîéòî÷êîé çàäà÷è î ìàêñèìàëüíîì ïîòîêå (2.9), ïðè ýòîì íå ñóùåñòâóåò äóã(i, j) ∈ Ey , i ∈ A, j ∈ V \ A, à çíà÷èò èç òåîðåìû Ôîðäà-Ôàëêåðñîíà y ìàêñèìàëüíûé ïîòîê, à A, V \ A ìèíèìàëüíûé st-ðàçðåç.P(s,i)∈E ce )PÇàìå÷àíèå.  ýòîé òåîðåìå òàêæå ìîæíî áûëî âçÿòü A = {s}∪V+ (x∗ ). ðàáîòå [102] òàêæå îòìå÷åíî, ÷òî ïîñëå òîãî, êàê â îáùåé ïðîöåäóðåáàëàíñèðîâàíèÿ äóã íè îäíà èç îïåðàöèé M ove íå äàåò èçìåíåíèå ïîòîêà áîëüøå, ÷åì íà 1/n2 , âîçìîæíî òî÷íîå èçâëå÷åíèå ìàêñèìàëüíîãî ïîòîêà / ìèíèìàëüíîãî ðàçðåçà, ÷òî äàåò âîçìîæíîñòü èñïîëüçîâàòüïðèáëèæåííîå ðåøåíèå (2.16), à íå òî÷íîå.2.2.6Ðåàëèçàöèÿ àëãîðèòìîâ â ìóëüòèàãåíòíûõñèñòåìàõÎáà àëãîðèòìà ConcurrentArcBalancing è RandomizedArcBalancing äîïóñêàþò ðàñïðåäåëåííóþ ðåàëèçàöèþ â ñåòè, åñëè òîïîëîãèÿ ýòîé ñåòèçàäàíà òåì æå ãðàôîì, ÷òî è çàäà÷à î ìàêñèìàëüíîì ïîòîêå.
Òàêæå ìîæíî ñ÷èòàòü, ÷òî âû÷èñëèòåëüíûå óçëû ñîîòâåòñòâóþò íå âñåì âåðøèíàì,à òîëüêî V \ {s, t}. Äëÿ óñêîðåíèÿ âû÷èñëåíèé èìååò ñìûñë íåïîñðåä-ñòâåííûì îáðàçîì âû÷èñëÿòü èçáûòîê âåðøèíû. Äëÿ îáîèõ àëãîðèòìîâìû áóäåì ïðåäïîëàãàòü ñëåäóþùåå79• Àëãîðèòìû îïåðèðóþò ñ âåëè÷èíàìè xe , e ∈ E 0 , yi , i ∈ V \ {s, t}.• Óçåë i õðàíèò â ëîêàëüíîé ïàìÿòè âåëè÷èíû xe è ce , ãäå e = (i, j) ∈E 0.•  ñèíõðîííîé âåðñèè èñïîëüçóþòñÿ äîïîëíèòåëüíûå ïðîìåæóòî÷íûå ïåðåìåííûå y1 , . . . , yn , â ðàíäîìèçèðîâííîé âåðñèè êàæäûéóçåë õðàíèò äîïîëíèòåëüíî ÷åòûðå ïåðåìåííûõ äëÿ ïðîìåæóòî÷íûõ âû÷èñëåíèé zi+ , zj+ , zi− , zj− .Äàëåå ïðåäñòàâëåíû ðàñïðåäåëåííûå âåðñèè àëãîðèòìîâConcurrentArcBalancing è RandomizedArcBalancing.
Ôàêòè÷åñêè, îíè íè÷åì íå îòëè÷àþòñÿ îò ïðåäñòàâëåííûõ ðàíåå, íî èìåþò áîëåå ÿâíóþ ôîðìó.  àëãîðèòìå ConcurrentArcBalancing ïðåäïîëàãàåì, ÷òî â ñåòè åñòüñèíõðîíèçàöèÿ âðåìåíè, âñå îïåðàöèè äâóõ âíóòðåííèõ öèêëîâ f or ïðîèñõîäÿò îäíîâðåìåííî ïî òàêòàì ñèñòåìû.  ýòîì ñëó÷àå, íà êàæäîéèòåðàöèè äîñòàòî÷íî õðàíèòü òîëüêî çíà÷åíèÿ xk , xk+1 , yk , yk+1 .  îáîèõ àëãîðèòìàõ ïðåäïîëàãàåòñÿ, ÷òî óçåë i äîëæåí èìåòü âîçìîæíîñòüçàïðîñèòü èíôîðìàöèþ ñîñåäíèõ óçëîâ, ò.å.
òàêèõ j , ÷òî (i, j) ∈ E è ïðèýòîì ïåðåäàòü èíôîðìàöèþ íà ýòîò óçåë. Äðóãèìè ñëîâàìè, óñëîâèå äâóñòîðîííåãî âçàèìîäåéñòâèÿ íåîáõîäèìî äëÿ ðåàëèçàöèè ýòîãî àëãîðèòìà(îäíàêî, ýòî åùå íå çíà÷èò, ÷òî äëÿ ñîîòâåòñòâóþùåé çàäà÷è î ìàêñèìàëüíîì ïîòîêå ïðîïóñêíûå ñïîñîáíîñòè äîëæíû áûòü äâóñòîðîííèìè). ðàíäîìèçèðîâàííîì àëãîðèòìå ïðåäïîëàãàåòñÿ, ÷òî â ñèñòåìå íåòóñèíõðîíèçàöèè, êàæäûé èç óçëîâ ñîâåðøàåò M ove îòíîñèòåëüíî ñëó÷àéíîé èñõîäÿùåé äóãè.
Òàêèì îáðàçîì ìîæíî ñ÷èòàòü, ÷òî ñíà÷àëà ñëó÷àéíûì îáðàçîì âûáèðàåòñÿ óçåë, êîòîðûé ñîâåðøàåò äåéñòâèå, ïîñëå ÷åãîñëó÷àéíî âûáèðàåòñÿ èñõîäÿùàÿ äóãà, ÷òî äàåò âåðîÿòíîñòü âûáîðà äóãèe = (i, j): pe = nd1− . Èç ëåììû 2.5 ñëåäóåò, ÷òî òàêîé âûáîð âåðîÿòíîñòèiãàðàíòèðóåò âûïîëíåíèÿ ||A|| ≤ 2 â ñîîòâåòñòâóþùèõ òåîðåìàõ ñõîäèìîñòè. Ðåçóëüòàòîì îáîèõ àëãîðèòìîâ ÿâëÿåòñÿ ðåøåíèå (2.16), èçâëå÷åíèåðåøåíèÿ çàäà÷è î ìàêñèìàëüíîì ïîòîêå áûëî îáñóæäåíî â ïðåäûäóùåì80Algorithm3:criterion)Distributed ConcurrentArcBalancing(G, c, stoppingx0 ← 0m , k ← 0;for e = (s, i) ∈ Ex0e ← ce ;dofordofore = (i, t) ∈ Ex0e ← ce ;i ∈ VP\ {s, t} do P0yi ← (j,i)∈E x0e − (i,j)∈E x0e ;/* End of initializationwhile stopping criterion is not satised0for e = (i, j) ∈ E doy k −y k← xke − j 2 i ;xk+1ek+1if xe> ce thenk+1xe ← ce .if xe < 0 thenxk+1← 0.efori ∈ V \P{s, t} doPk+1yi ← (j,i)∈E xke − (i,j)∈E xke ;k ← k + 1;return x;81*/doðàçäåëå, îíî çàêëþ÷àåòñÿ â ÷àñòè÷íîé äåêîìïîçèöèè ïîòîêà è ïðåäñòàâëÿåò ñîáîé ãîðàçäî ìåíåå ñëîæíóþ çàäà÷ó, íåæåëè ñàìà çàäà÷à î ìàêñèìàëüíîì ïîòîêå.
Èçâëå÷åíèå ìèíèìàëüíîãî ðàçðåçà âîçìîæíî â ðàñïðåäåëåííîì âèäå: åñëè yi > 0, òî óçåë i íàõîäèòñÿ â îäíîé ÷àñòè ðàçðåçà,åñëè æå yi ≤ 0, òî â äðóãîé.Algorithm 4:criterion)Distributed RandomizedArcBalancing(G, c, stoppingx ← 0m ; while stopping criterion is not satised dopick random node i uniformly;pick random outcoming arc e = (i, j) ∈ E 0 of i uniformly;let ∆ ←P±1 w.
p. 1/2P;PP+zi ← ( (k,i)∈E 0 xe − (i,k)∈E 0 xe + (s,i)∈E ce − (i,t)∈E 0 xe + α∆);PPPPzj+ ← ( (k,j)∈E 0 xe − (j,k)∈E 0 xe + (s,j)∈E ce − (j,t)∈E 0 xe + α∆);PPPPzi− ← ( (k,i)∈E 0 xe − (i,k)∈E 0 xe + (s,i)∈E ce − (i,t)∈E 0 xe − α∆);PPPPzj− ← ( (k,j)∈E 0 xe − (j,k)∈E 0 xe + (s,j)∈E ce − (j,t)∈E 0 xe − α∆);(z + )2+(zi+ )2 −(zi− )2 −(zi− )2;8αxe ← xe − ∆ jif xe > ce thenx e ← ce .if xe < 0 thenx e ← 0.return x;82Ãëàâà 3Ýêñïåðèìåíòàëüíûåðåçóëüòàòû3.1Ïàêåò ïðèêëàäíûõ ïðîãðàììäëÿ ñèìóëÿöèè ïðîöåññàðàñïðåäåëåíèÿ çàãðóçêèÐàçðàáîòàííûé ïàêåò ïðåäñòàâëÿåò ñîáîé ñèñòåìó, ïîçâîëÿþùóþ:• Ðåøàòü îïòèìèçàöèîííûå çàäà÷è, îïèñàííûå â ãëàâå 1.• Ñèìóëèðîâàòü ïîâåäåíèå âû÷èñëèòåëüíîé ñåòè, èñïîëüçóþùåé ïîòîêîâûå ìåòîäû îïòèìèçàöèè èëè ïðîòîêîëà ëîêàëüíîãî ãîëîñîâàíèÿ äëÿ ðàñïðåäåëåíèÿ çàãðóçêè.Îñíîâíîå çíà÷åíèå ïàêåòà ñèìóëÿöèÿ âû÷èñëèòåëüíîé ñåòè.
Èñõîäíûé êîä ïàêåòà íàõîäèòñÿ â îòêðûòîì äîñòóïå [38]. Ïàêåò ñîäåðæèò ñëåäóþùèå êëþ÷åâûå êëàññû, â êîòîðûõ ñîäåðæèòñÿ åãî ñòðóêòóðà:• processing unit êëàññ, îïèñûâàþùèé âû÷èñëèòåëüíûé óçåë.• channel êëàññ îïèñûâàþùèé êàíàë ñâÿçè.• task êëàññ, îïèñûâàþùèé çàäà÷ó íà èñïîëíåíèå.• Ñëóæåáíûå êëàññû: static ow graph êëàññ, ïðåäîñòàâëÿþùèé ìåòîäû ðàáîòû ñ ãðàôàìè è ðåøåíèÿ çàäà÷è î ïàðàìåòðè÷åñêîì ïîòîêå; scheduler êëàññ, âûïîëíÿþùèé ôóíêöèþ ëîêàëüíîãî ïëàíèðîâàíèÿ; delayer êëàññ, ýìóëèðóþùèé çàäåðæêó ïðè ïåðåäà÷åäàííûõ.83Ñèìóëÿòîð ðàáîòàåò ïî òàêòàì, ãëîáàëüíàÿ ôóíêöèÿðóåò îäèí òàêò è âûãëÿäèò ñëåäóþùèì îáðàçîì:tick()ñèìóëè-bool tick () {bool done = true ;for ( int i = 0; i < units . size () ; ++ i ) {tick ( units [ i ]) ;if ( units [ i ] - > status > 1) done = false ;}return done ;}Çäåñü units ìàññèâ âñåõ âû÷èñëèòåëüíûõ óçëîâ.
Âíóòðè öèêëà ïðîèçâîäèòñÿ ïðîâåðêà, åñòü ëè â ñåòè åùå çàäàíèÿ íà âûïîëíåíèå. Åñëèçàäàíèé íå îñòàëîñü, ñèìóëÿöèÿ çàâåðøàåòñÿ. Òàêèì îáðàçîì, èñïîëüçóÿðàçíûå ñòðàòåãèè ðàñïðåäåëåíèÿ çàãðóçêè ìîæíî ïîëó÷èòü ðàçëè÷íîåâðåìÿ ñèìóëÿöèè (÷åì ìåíüøå òåì ýôôåêòèâíåå ðàñïðåäåëåíèå). Äëÿðàñïðåäåëåíèÿ çàãðóçêè ñîîòâåòñòâóþùåìó ðåøåíèþ çàäà÷è î ïàðàìåòðè÷åñêîì ïîòîêå ñèìóëÿòîð òàêæå ïðåäîñòàâëÿåò îæèäàåìîå èäåàëüíîåâðåìÿ. Íà ïðàêòèêå ýòî çíà÷åíèå íåñêîëüêî ìåíüøå ðåàëüíîãî âðåìåíèðàáîòû èç-çà çàäåðæåê â êîììóíèêàöèè è íåñòàöèîíàðíîñòåé (ñì.
ãëàâó2).Çà êàæäûé òàêò ïðîèñõîäèò ñëåäóþùåå:• Êàæäûé âû÷èñëèòåëüíûé óçåë áåðåò èç ñâîåé î÷åðåäè íåñêîëüêîçàäàíèé è âûïîëíÿåò èõ. Êîëè÷åñòâî âûïîëíåííûõ çàäàíèé ñîîòâåòñòâóåò ïðîèçâîäèòåëüíîñòè óçëà. Åñëè â î÷åðåäè áîëüøå çàäàíèé, ÷åì óçåë ìîæåò âûïîëíèòü çà òàêò, òî óçåë âûïîëíÿåò ñòîëüêî çàäàíèé, ñêîëüêî ìîæåò, à òàêæå íà÷èíàåò âûïîëíÿòü åùå îäíî çàäàíèå (çà ýòî îòâå÷àþò ïîëÿ processing unit.current progressè processing unit.current task, â ïðîòèâíîì ñëó÷àå óçåë âûïîëíÿåòâñå èìåþùèåñÿ çàäàíèÿ. Òàêîå ïîâåäåíèå óçëà ìîæíî ïðîñòî îïèñàòü è ñëåäóþùèì îáðàçîì: óçåë ïî î÷åðåäè âûïîëíÿåò çàäàíèÿ,ïî çàâåðøåíèè ðàáîòû íàä îäíèì çàäàíèåì óçåë áåðåò çàäàíèå èçî÷åðåäè è íà÷èíàåò ðàáîòàòü íàä íèì.
Åñëè æå î÷åðåäü ïóñòà, òîóçåë îñòàíàâëèâàåòñÿ äî ñëåäóþùåãî òàêòà.• Êàíàëû ñâÿçè ðàáîòàþò ïî ïîäîáíîé ñõåìå, îäíàêî æå îíè áåðóò çàäà÷è èç î÷åðåäè òîëüêî åñëè äëÿ íèõ çàïëàíèðîâàíà ïåðåäà÷à çàäàíèé (çà ýòî îòâå÷àþò scheduler.scheduled load è scheduler.transferredload ).• Ïðè ïåðåäà÷è ïî êàíàëàì ñâÿçè çàäàíèÿ ïîïàäàþò íå íàïðÿìóþ êäðóãîìó óçëó, à â ñîîòâåòñòâóþùèé delayer, êîòîðûé çàäåðæèâàåòýòè çàäàíèÿ íà íåñêîëüêî òàêòîâ.843.2Ýôôåêòèâíîå ðåøåíèå çàäà÷è îïàðàìåòðè÷åñêîì ïîòîêåÎäíà èç ñîñòàâíûõ ÷àñòåé ïàêåòà ðåàëèçàöèÿ ýôôåêòèâíîãî àëãîðèòìà ðåøåíèÿ çàäà÷è î ïàðàìåòðè÷åñêîì ïîòîêå.
Çàäà÷à î ïàðàìåòðè÷åñêîì ïîòîêå ÿâëÿåòñÿ äîñòàòî÷íî ðåäêîé, â ñåòè ïðàêòè÷åñêè îòñóòñòâóþò îòêðûòûå ðåàëèçàöèè àëãîðèòìîâ ðåøåíèÿ ýòîé çàäà÷è, ïîýòîìóñðàâíåíèå ïðîâîäèëîñü ëèøü ñ îäíîé áèáëèîòåêîé: [36] (Ãîëüäáåðã è Áàáåíêî, îïèñàíèå ðåàëèçàöèè è ðåçóëüòàòû òåñòèðîâàíèÿ [45]).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
