Image Processing

Что­бы уско­рить ре­ше­ние за­да­чи, не до­ста­точ­но иметь па­ра­л­лель­ную вы­чис­ли­тель­ную си­сте­му. Кро­ме это­го нуж­но ещё со­здать для та­кой си­сте­мы спе­ци­аль­ную (па­ра­л­лель­ную) про­грам­му. Для то­го что­бы ал­го­ритм мог быть эф­фек­тив­но реа­ли­зо­ван в ви­де па­ра­л­лель­ной про­грам­мы, он дол­жен об­ла­дать внут­рен­ним па­ра­л­ле­лиз­мом.

Граф вы­чис­ли­тель­но­го ал­го­рит­ма

Лю­бой ал­го­ритм при­ни­ма­ет ис­ход­ные дан­ные, про­де­лы­ва­ет над ни­ми опе­ра­ции, и вы­да­ёт ре­зуль­тат. Ес­ли рас­смат­ри­вать этот про­цесс с кон­ца, то мож­но за­ме­тить, что для по­лу­че­ния ре­зуль­та­та долж­ны быть го­то­вы преды­ду­щие дан­ные, ко­то­рые не­по­сред­ствен­но ис­поль­зу­ют­ся для его по­лу­че­ния. Эти дан­ные, в свою оче­редь, за­ви­сят от дру­гих дан­ных, и так да­лее до ис­ход­ных дан­ных.

Рас­смот­рим, на­при­мер, ал­го­ритм вы­чис­ле­ния вы­ра­же­ния:

(1)

Вна­ча­ле нуж­но вы­чис­лить про­из­ве­де­ния  и , за­тем из­влечь ко­рень, и, на­ко­нец, вы­пол­нить сло­же­ние. Мы не мо­жем вы­пол­нить сло­же­ние, по­ка не вы­чис­ле­ны оба его ар­гу­мен­та. Опи­сан­ный ал­го­ритм мож­но изоб­ра­зить сле­дую­щим об­ра­зом:

Мы ви­дим, что про­цесс об­ра­бот­ки дан­ных мо­жет быть вы­ра­жен в ви­де од­но­на­прав­лен­но­го гра­фа. Та­кой граф мож­но изоб­ра­зить на плос­ко­сти, при­чём каж­дую ариф­ме­ти­че­скую опе­ра­цию рас­по­ла­гать мак­си­маль­но вы­со­ко (ес­ли ось вре­ме­ни на­прав­ле­на вниз), но не вы­ше тех опе­ра­ций, ре­зуль­тат ко­то­рых ну­жен для её вы­чис­ле­ния. В та­ком слу­чае вы­со­та гра­фа бу­дет рав­на ми­ни­маль­но­му вре­ме­ни (чис­лу ша­гов/эта­пов) ре­ше­ния этой за­да­чи на иде­аль­ной па­ра­л­лель­ной вы­чис­ли­тель­ной си­сте­ме с не­огра­ни­чен­ным чис­лом вы­чис­ли­те­лей.

Сте­пень па­ра­л­ле­лиз­ма

Сте­пе­нью па­ра­л­ле­лиз­ма эта­па чис­лен­но­го ал­го­рит­ма на­зы­ва­ет­ся чис­ло опе­ра­ций, ко­то­рые на дан­ном эта­пе мож­но вы­пол­нять па­ра­л­лель­но (ши­ри­на гра­фа, по­стро­ен­но­го опи­сан­ным вы­ше спо­со­бом).

Про­ил­лю­стри­ру­ем это опре­де­ле­ние не­сколь­ки­ми при­ме­ра­ми. Нач­нём с за­да­чи сло­же­ния двух век­то­ров  и  раз­мер­но­сти n. Сло­же­ния  не­за­ви­си­мы и мо­гут вы­пол­нять­ся па­ра­л­лель­но:

Та­ким об­ра­зом, сте­пень па­ра­л­ле­лиз­ма это­го ал­го­рит­ма рав­на n. От­ме­тим, что по­ня­тие сте­пе­ни па­ра­л­ле­лиз­ма не свя­за­но с чис­лом про­цес­со­ров си­сте­мы, оно яв­ля­ет­ся ха­рак­те­ри­сти­кой, внут­рен­не при­су­щей ал­го­рит­му. От чис­ла про­цес­со­ров за­ви­сит вре­мя, не­об­хо­ди­мое для за­вер­ше­ния вы­чис­ле­ний. На­при­мер, ес­ли , и чис­ло про­цес­со­ров p так­же рав­но , то все сум­мы тео­ре­ти­че­ски мож­но вы­чис­лить за один вре­мен­ной шаг, од­на­ко при  по­тре­бу­ет­ся  временны́х ша­гов.

Рас­смот­рим те­перь за­да­чу сло­же­ния n чи­сел . Обыч­ный по­сле­до­ва­тель­ный ал­го­ритм

(2)

не­при­го­ден для па­ра­л­лель­ных вы­чис­ле­ний. Од­на­ко за­да­ча мо­жет быть ре­ше­на дру­гим ме­то­дом. На ри­сун­ке по­ка­за­но, как мож­но осу­ще­ствить сум­ми­ро­ва­ние вось­ми чи­сел в три эта­па при по­мо­щи ал­го­рит­ма сдваи­ва­ния:

За­да­ча сум­ми­ро­ва­ния раз­де­ле­на на мень­шие под­за­да­чи, ко­то­рые мо­гут ре­шать­ся не­за­ви­си­мо. Для  чи­сел ал­го­ритм сдваи­ва­ния со­сто­ит из эта­пов; на пер­вом эта­пе вы­пол­ня­ют­ся сло­же­ний, на вто­ром — , и так да­лее, по­ка на по­след­нем эта­пе не бу­дет вы­пол­не­но един­ствен­ное сло­же­ние. Об­щее чис­ло опе­ра­ций сло­же­ния рав­но : та­кое же, как в по­сле­до­ва­тель­ном ал­го­рит­ме (2).

Оче­вид­но, что на пер­вом эта­пе сте­пень па­ра­л­ле­лиз­ма рав­на , на вто­ром — , и так да­лее. По­доб­ный ал­го­ритм мо­жет быть при­ме­нён и для дру­гих це­лей, на­при­мер, для на­хож­де­ния мак­си­маль­но­го эле­мен­та в мас­си­ве и да­же для сор­ти­ров­ки (сор­ти­ров­ка слия­ни­ем).

Сло­же­ние ал­го­рит­мом сдваи­ва­ния име­ет ещё од­но пре­иму­ще­ство пе­ред по­сле­до­ва­тель­ным сло­же­ни­ем: он обес­пе­чи­ва­ет луч­шую (в сред­нем) точ­ность сум­ми­ро­ва­ния при ис­поль­зо­ва­нии чи­сел с пла­ваю­щей точ­кой.

Сред­ней сте­пе­нью па­ра­л­ле­лиз­ма чис­лен­но­го ал­го­рит­ма на­зы­ва­ет­ся от­но­ше­ние об­ще­го чис­ла опе­ра­ций ал­го­рит­ма к чис­лу его эта­пов. Оче­вид­но, для ал­го­рит­ма сдваи­ва­ния сред­няя сте­пень па­ра­л­ле­лиз­ма рав­на:

(3)

Со сте­пе­нью па­ра­л­ле­лиз­ма так­же свя­за­но по­ня­тие зер­ни­сто­сти. Круп­но­зер­ни­стость за­да­чи озна­ча­ет на­ли­чие в ней боль­ших не­за­ви­си­мых под­за­дач, ко­то­рые мож­но об­ра­ба­ты­вать па­ра­л­лель­но. При­ме­ром мо­жет слу­жить за­да­ча ре­ше­ния не­сколь­ких раз­лич­ных боль­ших си­стем ли­ней­ных урав­не­ний, ре­ше­ния ко­то­рых ком­би­ни­ру­ют­ся на бо­лее позд­них ста­ди­ях вы­чис­ли­тель­но­го про­цес­са. Мел­ко­зер­ни­стость со­от­вет­ству­ет воз­мож­но­сти па­ра­л­лель­но­го вы­пол­не­ния ма­лых под­за­дач. Так, для сло­же­ния двух век­то­ров под­за­да­чей яв­ля­ет­ся сло­же­ние ком­по­нент, имею­щих оди­на­ко­вый но­мер. Круп­но­зер­ни­стые ал­го­рит­мы слож­но рас­па­рал­ле­лить на боль­шом чис­ле про­цес­со­ров.

Уско­ре­ние и эф­фек­тив­ность па­ра­л­лель­но­го ал­го­рит­ма

Уско­ре­ни­ем па­ра­л­лель­но­го ал­го­рит­ма на­зы­ва­ет­ся от­но­ше­ние:

(4)

где  — вре­мя вы­чис­ле­ния за­да­чи на p про­цес­со­рах. За­ме­тим, что в опре­де­ле­нии под­ра­зу­ме­ва­ют­ся дей­стви­тель­ные вре­ме­на вы­чис­ле­ний. Это де­ла­ет опре­де­ле­ние бо­лее по­лез­ным на прак­ти­ке, но за­труд­ня­ет его ис­поль­зо­ва­ние в том слу­чае, ес­ли тре­буе­мые вре­ме­на не­из­ве­ст­ны. Для иде­аль­ной вы­чис­ли­тель­ной си­сте­мы и иде­аль­ной па­ра­л­лель­ной реа­ли­за­ции ал­го­рит­ма его уско­ре­ние рав­но сред­ней сте­пе­ни па­ра­л­ле­лиз­ма.

С уско­ре­ни­ем свя­за­на эф­фек­тив­ность па­ра­л­лель­но­го ал­го­рит­ма. Эф­фек­тив­но­стью па­ра­л­лель­но­го ал­го­рит­ма на­зы­ва­ет­ся ве­ли­чи­на:

(5)

По опре­де­ле­нию, . Тео­ре­ти­че­ски долж­но быть и . Ес­ли ал­го­ритм до­сти­га­ет мак­си­маль­но­го уско­ре­ния (), то . На прак­ти­ке эф­фек­тив­ность убы­ва­ет при уве­ли­че­нии чис­ла про­цес­со­ров.

Ино­гда бы­ва­ют слу­чаи, ко­гда  («су­пер­ли­ней­ное уско­ре­ние»). Эта ано­ма­лия вы­зва­на, ча­ще все­го, дву­мя при­чи­на­ми:

• В ка­че­стве по­сле­до­ва­тель­но­го ал­го­рит­ма был при­ме­нён не са­мый быст­рый ал­го­ритм из до­ступ­ных.
• С уве­ли­че­ни­ем ко­ли­че­ства вы­чис­ли­те­лей рас­тёт сум­мар­ный объ­ём их опе­ра­тив­ной и кэш па­мя­ти. По­это­му всё боль­шая часть дан­ных за­да­чи уме­ща­ет­ся в опе­ра­тив­ной па­мя­ти и не тре­бу­ет под­кач­ки с дис­ка, или (ча­ще все­го) уме­ща­ет­ся в кэ­ше («аг­г­ре­га­ция кэ­шей»). В та­ких слу­ча­ях для точ­но­го из­ме­ре­ния эф­фек­тив­но­сти реа­ли­зо­ван­но­го ал­го­рит­ма сле­ду­ет умень­шать объ­ём кэш па­мя­ти каж­до­го вы­чис­ли­те­ля об­рат­но про­пор­цио­наль­но чис­лу вы­чис­ли­те­лей.

За­кон Ам­да­ля

Ма­шин­ное вре­мя па­ра­л­лель­ной вы­чис­ли­тель­ной си­сте­мы сто́ит не­ко­то­рых де­нег, по­это­му од­ной из це­лей кон­струи­ро­ва­ния па­ра­л­лель­ных ал­го­рит­мов яв­ля­ет­ся до­сти­же­ние по воз­мож­но­сти боль­ших эф­фек­тив­но­сти и уско­ре­ния. Од­на­ко эта си­ту­а­ция не все­гда до­сти­жи­ма: на прак­ти­ке мак­си­маль­ное уско­ре­ние мож­но по­лу­чить лишь для три­ви­аль­ных за­дач. Глав­ные фак­то­ры, обу­слав­ли­ваю­щие от­кло­не­ние от мак­си­маль­но­го уско­ре­ния, та­ко­вы:

• От­сут­ствие мак­си­маль­но­го па­ра­л­ле­лиз­ма в ал­го­рит­ме и/или не­сба­лан­си­ро­ван­ность на­груз­ки про­цес­со­ров.
• Об­ме­ны, кон­флик­ты па­мя­ти и вре­мя син­хро­ни­за­ции.

Хо­тя за­держ­ки, свя­зан­ные с син­хро­ни­за­ци­ей, об­ме­на­ми и кон­флик­та­ми па­мя­ти, по сво­ей при­ро­де раз­лич­ны, их воз­дей­ствие на об­щий про­цесс вы­чис­ле­ния оди­на­ко­во: они за­мед­ля­ют его на вре­мя, не­об­хо­ди­мое для под­го­тов­ки дан­ных, нуж­ных для даль­ней­ше­го сче­та. По­это­му ино­гда сле­ду­ет объ­еди­нять все три фак­то­ра за­держ­ки, как это сде­ла­но в сле­дую­щем опре­де­ле­нии.

Вре­ме­нем под­го­тов­ки дан­ных на­зы­ва­ет­ся за­держ­ка, вы­зван­ная об­ме­на­ми, кон­флик­та­ми па­мя­ти или син­хро­ни­за­ци­ей и не­об­хо­ди­мая для то­го, что­бы раз­ме­стить дан­ные, тре­бую­щие­ся для про­дол­же­ния вы­чис­ле­ний, в со­от­вет­ствую­щих ячей­ках па­мя­ти.

Об­ра­тим­ся те­перь к фак­то­ру от­сут­ствия мак­си­маль­но­го па­ра­л­ле­лиз­ма. Он мо­жет про­яв­лять­ся по-раз­но­му. При сло­же­нии n чи­сел мы ви­де­ли, что на пер­вом эта­пе ал­го­рит­ма па­ра­л­ле­лизм мак­си­ма­лен, од­на­ко на каж­дом по­сле­дую­щем эта­пе сте­пень па­ра­л­ле­лиз­ма умень­ша­ет­ся вдвое. Та­ким об­ра­зом, в боль­шин­стве слу­ча­ев сред­няя сте­пень па­ра­л­ле­лиз­ма ал­го­рит­ма мень­ше n.

Рас­смот­рим про­стую мо­дель, ко­гда часть опе­ра­ций в ал­го­рит­ме вы­пол­ня­ет­ся од­ним вы­чис­ли­те­лем, а остав­шие­ся опе­ра­ции вы­пол­ня­ют­ся па­ра­л­лель­но все­ми вы­чис­ли­те­ля­ми, то­гда:

(6)

где  — вре­мя, за­тра­чи­ва­е­мое на реа­ли­за­цию ал­го­рит­ма на од­ном про­цес­со­ре,  — до­ля опе­ра­ций в ал­го­рит­ме, вы­пол­няе­мых од­ним про­цес­со­ром,  — до­ля опе­ра­ций, вы­пол­няе­мых все­ми p про­цес­со­ра­ми,  — об­щее вре­мя, тре­бу­е­мое для под­го­тов­ки дан­ных. В слу­чае ес­ли  и , уско­ре­ние мак­си­маль­но: . Пред­по­сыл­ки дан­но­го слу­чая за­клю­ча­ют­ся в том, что все опе­ра­ции вы­пол­ня­ют­ся с мак­си­маль­ным па­ра­л­ле­лиз­мом и от­сут­ству­ют за­держ­ки на под­го­тов­ку дан­ных. В слу­чае по­лу­ча­ем фор­му­лу, на­зы­ва­е­мую за­ко­ном Ам­да­ля:

(7)

За­кон Ам­да­ля, не­смот­ря на то, что он не учи­ты­ва­ет мно­гих фак­то­ров, на­кла­ды­ва­ет силь­ные огра­ни­че­ния на мак­си­маль­но до­сти­жи­мую эф­фек­тив­ность па­ра­л­лель­но­го ал­го­рит­ма.

Пред­по­ло­жим, на­при­мер, что , то есть две тре­ти опе­ра­ций в ал­го­рит­ме мо­гут вы­пол­нять­ся па­ра­л­лель­но, а треть — нет. То­гда уско­ре­ние . Та­ким об­ра­зом, не­за­ви­си­мо от ко­ли­че­ства про­цес­со­ров и да­же при иг­но­ри­ро­ва­нии всех за­трат на под­го­тов­ку дан­ных мы не смо­жем уско­рить ре­ше­ние за­да­чи бо­лее, чем в три ра­за. Гра­фи­ки за­ви­си­мо­сти уско­ре­ния и эф­фек­тив­но­сти от чис­ла про­цес­со­ров по­ка­за­ны на ри­сун­ке для :

Из гра­фи­ка вид­но, что ес­ли треть опе­ра­ций ал­го­рит­ма не уда­ёт­ся рас­па­рал­ле­лить, то для то­го, что­бы уско­рить ре­ше­ние за­да­чи в два ра­за, её нуж­но за­пу­стить на 4-х про­цес­со­рах, а для то­го, что­бы уско­рить в 2.5 ра­за — аж на 10-ти про­цес­со­рах. И это лишь тео­ре­ти­че­ская оцен­ка: на прак­ти­ке бу­дет ещё ху­же.

Для срав­не­ния на ри­сун­ке 5 по­ка­за­ны те же гра­фи­ки для :

Ви­дим, что в этом слу­чае си­ту­а­ция го­раз­до луч­ше.

Очень важ­но на ран­них ста­ди­ях раз­ра­бот­ки ал­го­рит­ма оце­нить его ха­рак­те­ри­сти­ки, что­бы опре­де­лить, бу­дет ли эта раз­ра­бот­ка це­ле­со­об­раз­ной. Ведь мо­жет ока­зать­ся так, что про­грам­му нуж­но бу­дет за­пу­стить все­го не­сколь­ко раз для по­лу­че­ния ре­зуль­та­тов. И ино­гда про­ще по­до­ждать не­де­лю, по­ка от­ра­бо­та­ет по­сле­до­ва­тель­ная про­грам­ма, чем на не­де­лю доль­ше со­зда­вать па­ра­л­лель­ную про­грам­му.

P.S.

Бо́льшая часть ма­те­ри­а­ла лек­ции взя­та от­сю­да: http://oldunesco.kemsu.ru/mps/ (па­ра­гра­фы 26–28).