LXF168:Вы­чис­ления. MPI-про­грам­мы и Жизнь

Версия 22:07, 10 ноября 2018

Па­рал­лель­ные тех­но­ло­гии. Введение в актуальную тему

Вве­де­ние в MPI

Па­рал­лель­но по­здо­ро­вав­шись с ми­ром, Ми­ха­ил Ос­тап­ке­вич и Ев­ге­ний Бал­дин при­за­ду­ма­лись о Жиз­ни с боль­шой бу­к­вы.

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

Вре­ме­на боль­ших век­тор­ных су­пер­ком­пь­ю­те­ров про­шли, ну или по­ка не на­ста­ли. Что мы име­ем вза­мен? Мно­же­ст­во неза­ви­си­мых «пи­си­шек», да­же ес­ли они и уста­нов­ле­ны в стой­ки и управ­ля­ют­ся ква­ли­фи­ци­ро­ван­ны­ми ад­минист­ра­то­ра­ми! За­пустить на них пач­ку за­дач лег­ко, но как под­от­чет­ные про­цес­сы бу­дут об­щать­ся? Да с по­мо­щью MPI!

MPI или Message Passing Interface или, по-про­сто­му, ин­тер­фейс пе­ре­да­чи со­об­щений – это стан­дарт­ный про­грамм­ный ин­тер­фейс для пе­ре­да­чи ин­фор­ма­ции ме­ж­ду про­цес­са­ми, вы­пол­няю­щи­ми од­ну за­да­чу. Стан­дарт под­дер­жи­ва­ет­ся кон­сор­циу­мом MPI Forum, чле­на­ми ко­то­ро­го яв­ля­ют­ся прак­ти­че­­ски все круп­ные про­из­во­ди­те­ли вы­чис­ли­тель­ной техники и про­грамм­но­го обес­пе­чения. Пер­вый стан­дарт MPI 1.0 при­нят в 1994 го­ду. Фор­маль­но раз­ра­бот­ка на­ча­лась в 1991 го­ду, когда неболь­шая груп­па уче­ных-ин­фор­ма­ти­ков со­бра­лась в уе­ди­нен­ном ав­ст­рий­ском гор­ном пан­сио­на­те и на­ча­ла ак­тив­но об­менивать­ся мнениями. В сен­тяб­ре 2012 го­да вы­шла спе­ци­фи­ка­ция MPI 3.0.

Тех­но­ло­гия MPI ори­ен­ти­ро­ва­на в пер­вую оче­редь на кла­сте­ры и на мас­сив­но-па­рал­лель­ные сис­те­мы (MPP), но при­ме­ня­ет­ся так­же в сис­те­мах SMP и NUMA. Это оз­на­ча­ет, что MPI-про­грам­мы мож­но оп­ти­ми­зи­ро­вать как для са­мых мощ­ных ре­шений из TOP500, так и для до­машнего ком­пь­ю­те­ра. Поч­ти на ка­ж­дом со­вре­мен­ном де­ск­то­пе сей­час сто­ит бо­лее од­но­го вы­чис­ли­тель­но­го яд­ра. Да что де­ск­то­пы – те­ле­фо­ны то­же не от­ста­ют от этой мо­ды. И эти яд­ра про­сто необ­хо­ди­мо ис­поль­зо­вать!

Ис­полнение про­грам­мы про­из­во­дит­ся несколь­ки­ми па­рал­лель­но ис­пол­няе­мы­ми про­цес­са­ми, ко­то­рые пред­став­ля­ют со­бой раз­ные эк­зем­п­ля­ры од­ной и той же про­грам­мы. Ка­ж­дый про­цесс име­ет свой на­бор дан­ных. Ре­жим ра­бо­ты, когда од­на и та же про­грам­ма за­пу­ще­на на раз­ных уз­лах или про­цес­со­рах и об­ра­ба­ты­ва­ет раз­ные на­бо­ры дан­ных, на­зы­ва­ют SPMD (Single Program Multiple Data). Дан­ные дру­гих про­цес­сов про­цес­су не вид­ны, по­это­му для об­ме­на дан­ны­ми ме­ж­ду про­цес­са­ми тре­бу­ет­ся MPI, а имен­но по­сыл­ка со­об­щений ме­ж­ду ними. Ме­ханиз­мы MPI га­ран­ти­ру­ют достав­ку со­об­щений и со­от­вет­ст­вие по­ряд­ка, в ко­то­ром они по­сы­ла­лись, по­ряд­ку их прие­ма. Су­ще­ст­ву­ют и дру­гие биб­лио­те­ки для об­ме­на со­об­щения­ми ме­ж­ду уда­лен­ны­ми про­цес­са­ми (на­при­мер, PVM). Од­на­ко сре­ди всех биб­лио­тек, ре­шаю­щих по­хо­жие за­да­чи, имен­но MPI по­лу­чил наи­боль­шее рас­про­странение. С тех­но­ло­ги­че­­ской сто­ро­ны, по-ви­ди­мо­му, три при­чи­ны сыг­ра­ли в этом ре­шаю­щую роль:

» вы­со­кая эф­фек­тив­ность про­грамм на MPI;

» вы­со­кая пе­ре­но­си­мость про­грамм, на­пи­сан­ных на MPI;

» на­ли­чие сво­бод­ной реа­ли­за­ции.

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

Эф­фек­тив­ность в MPI дости­га­ет­ся в пер­вую оче­редь за счет ис­поль­зо­вания са­мо­го бы­ст­ро­го из доступ­ных средств достав­ки со­об­щений. В муль­ти­про­цес­со­ре ис­поль­зу­ют­ся ок­на раз­де­ляе­мой несколь­ки­ми про­цес­са­ми па­мя­ти. В муль­ти­ком­пь­ю­те­рах ис­поль­зу­ет­ся са­мая бы­ст­рая сеть (Infiniband, Myrinet). Ес­ли она недоступ­на, то ис­поль­зу­ет­ся ста­рый, до­б­рый и на­деж­ный TCP/IP.

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

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

Кро­ме пе­ре­но­си­мо­сти и эф­фек­тив­но­сти, дру­гим су­ще­ст­вен­ным свой­ст­вом MPI яв­ля­ет­ся язы­ко­вая ней­траль­ность. Реа­ли­за­ции биб­лио­те­ки MPI не при­вя­за­ны к ка­ко­му-ли­бо од­но­му язы­ку. Вме­сто это­го они опи­сы­ва­ют се­ман­ти­ку опе­ра­ций, доступ­ных MPI-про­грам­мам че­рез функ­цио­наль­ный ин­тер­фейс. Как пра­ви­ло, MPI-про­грам­мы пи­шут на C, Fortran или С++, но мож­но ис­поль­зо­вать и мно­гие дру­гие языки, на­при­мер, C#, Java, Python или R.

На­ли­чие сво­бод­ной реа­ли­за­ции по­зво­ля­ет лег­ко уста­но­вить MPI и на­чать обу­чать свои про­грам­мы сек­ре­там взаи­мо­дей­ст­вия:

> sudo aptitude install mpi-default-bin mpi-default-dev

До­ку­мен­та­ция для вдум­чи­во­го изу­че­ния то­же не по­ме­ша­ет:

> sudo aptitude install mpi-doc mpi-specs

mpi-doc, кро­ме html-спра­вочника, до­бав­ля­ет в сис­те­му man-странич­ки по мно­го­чис­лен­ным MPI-функ­ци­ям, очень удоб­ные для бы­ст­ро­го под­гля­ды­вания.

Здрав­ст­вуй, Мир!

Пред­по­ла­га­ет­ся, что вы пред­став­ляе­те, что та­кое про­грам­ми­ро­вание на C, ну или хо­тя бы на­пи­са­ли на этом язы­ке свой лич­ный HelloWorld. Вот так вы­гля­дит про­стей­шая MPI-про­грам­ма:

1. include <mpi.h>

1. include <stdio.h>

int main(int argc, char **argv) {

MPI_Init(&argc, &argv);

printf(“Здрав­ст­вуй, Мир!\n”);

MPI_Finalize();

return 0;

}

В от­ли­чие от клас­си­че­­ско­­го HelloWorld, для его MPI-реа­ли­за­ции необ­хо­ди­мо под­клю­чить mpi.h с оп­ре­де­ления­ми кон­стант, ти­пов и функ­ций MPI. Так­же в ко­де поя­ви­лись две спец­функ­ции:

» MPI_Init – инициа­ли­за­ция MPI;

» MPI_Finalize – обя­за­тель­ное кор­рект­ное за­вер­шение ра­бо­ты с MPI.

В этой про­стой про­грам­ме для ла­конич­но­сти мы не об­ра­ба­ты­ва­ем воз­вра­щае­мые ошиб­ки. В ре­аль­ной же про­грам­ме ошиб­ки иг­но­ри­ро­вать не сле­ду­ет. По­сле успеш­но­го вы­зо­ва MPI_Init (когда воз­вра­ща­ет­ся зна­чение MPI_SUCCESS) ин­фра­струк­ту­ра MPI при­ло­жения го­то­ва к ра­бо­те, и мы мо­жем поль­зо­вать­ся все­ми ин­тер­фейс­ны­ми функ­ция­ми MPI.

Ком­пи­ля­ция MPI-про­грам­мы де­ла­ет­ся с по­мо­щью стан­дар­ти­зо­ван­ной ути­ли­ты mpicc, ко­то­рая вхо­дит в со­став па­ке­та mpi-default-dev. Про­грам­ма mpicc пред­став­ля­ет со­бой оберт­ку по­верх ком­пи­ля­то­ра. Она скры­ва­ет от поль­зо­ва­те­ля от­ли­чия ме­ж­ду раз­ны­ми плат­фор­ма­ми. Ком­пи­ля­ция MPI-мо­ди­фи­ка­ции HelloWorld де­ла­ет­ся так:

> mpicc helloworld.c -o helloworld

Ес­ли эту про­грам­му те­перь за­пус­тить, то она сде­ла­ет то, что от нее ожи­да­ет­ся – а имен­но, ска­жет

> ./helloworld

Здрав­ст­вуй, Мир!

Нам же нуж­но боль­ше, по­это­му, вос­поль­зо­вав­шись ути­ли­той mpirun из па­ке­та mpi-default-bin, вы­пол­ним:

> mpirun -n 2 ./helloworld

Здрав­ст­вуй, Мир!

Здрав­ст­вуй, Мир!

Клю­чик -n за­да­ет чис­ло па­рал­лель­но ис­пол­няе­мых про­цес­сов. В на­шем слу­чае с ми­ром по­здо­ро­ва­лись две ко­пии про­грам­мы. Так­же вме­сто mpirun мож­но ис­поль­зо­вать mpiexec или orterun. Это си­нонимы.

Не­мно­го усложним учеб­ный код:

1. include <mpi.h>

1. include <stdio.h>

main(int argc, char **argv){

int rankNode, sizeCluster;

MPI_Init(&argc, &argv);

MPI_Comm_rank(MPI_COMM_WORLD, &rankNode);

MPI_Comm_size(MPI_COMM_WORLD, &sizeCluster);

printf(“Здрав­ст­вуй, Мир! от про­цес­са %d из %d\n”, rankNode, sizeCluster);

MPI_Finalize();

}

Функ­ция MPI_Comm_size воз­вра­ща­ет ко­ли­че­­ст­во за­пу­щен­ных для ис­полнения MPI-про­грам­мы про­цес­сов, функ­ция MPI_Comm_rank воз­вра­ща­ет но­мер про­цес­са, вы­звав­ше­го функ­цию:

> mpicc helloworld2.c -o helloworld2

> mpirun -n 2 ./helloworld2

Здрав­ст­вуй, Мир! от про­цес­са 1 из 2

Здрав­ст­вуй, Мир! от про­цес­са 0 из 2

Ес­ли за­пус­тить боль­ше про­цес­сов –

> mpirun -n 7 ./helloworld2

Здрав­ст­вуй, Мир! от про­цес­са 0 из 7

Здрав­ст­вуй, Мир! от про­цес­са 1 из 7

Здрав­ст­вуй, Мир! от про­цес­са 2 из 7

Здрав­ст­вуй, Мир! от про­цес­са 5 из 7

Здрав­ст­вуй, Мир! от про­цес­са 6 из 7

Здрав­ст­вуй, Мир! от про­цес­са 3 из 7

Здрав­ст­вуй, Мир! от про­цес­са 4 из 7

мож­но уви­деть, что вы­пол­ня­ют­ся они не обя­за­тель­но в по­ряд­ке за­пуска (по­следним вы­полнил­ся про­цесс 4, а не процесс 6).

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

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

Сле­ду­ет так­же учи­ты­вать, что, на­при­мер, на про­цес­со­ре Intel(R) Core(TM)2 Duo, как сле­ду­ет из на­звания, толь­ко два вы­чис­ли­тель­ных яд­ра, по­это­му до­воль­но бес­смыс­лен­но за­пускать боль­ше двух про­цес­сов од­но­вре­мен­но. Мож­но так­же по­тре­бо­вать, что­бы ка­ж­дый про­цесс при­вя­зал­ся к сво­ему яд­ру:

> mpiexec -n 2 -bind-to-core -report-bindings ./helloworld2

fork binding child [[7067,1],0] to cpus 0001

fork binding child [[7067,1],1] to cpus 0002

Здрав­ст­вуй, Мир! от про­цес­са 1 из 2

Здрав­ст­вуй, Мир! от про­цес­са 0 из 2

> mpiexec -n 7 -bind-to-core -report-bindings ./helloworld2

Not enough processors were found on the local host to meet the requested binding action

Иг­ра «Жизнь»

Кле­точ­ный ав­то­мат «Жизнь [Game of Life, или про­сто Life]» был пред­ло­жен анг­лий­ским ма­те­ма­ти­ком Джо­ном Кон­ве­ем [John Horton Conway] в 1979 го­ду. Вряд ли он стал бы так ши­ро­ко из­вес­тен, ес­ли бы не аме­ри­кан­ский ма­те­ма­тик и ис­клю­чи­тель­но энергичый по­пу­ля­ри­за­тор нау­ки Мар­тин Гарднер [Martin Gardner]. По иг­ре «Жизнь» есть мас­са по­пу­ляр­ной ли­те­ра­ту­ры, в том чис­ле и на русском язы­ке.

Иг­ра «Жизнь» про­во­дит­ся на бес­конеч­ной кле­точ­ной доске, где ка­ж­дой из кле­ток при­свое­на 1 (жи­вая клет­ка) или 0 (ниче­го нет). При пе­ре­хо­де из ну­ле­во­го в единич­ное со­стояние го­во­рят, что клет­ка ро­ж­да­ет­ся, а из единич­но­го в ну­ле­вое – уми­ра­ет. Но­вое зна­чение клет­ки оп­ре­де­ля­ет­ся ее прежним зна­чением и сум­мой зна­чений ее вось­ми со­се­дей. Клет­ка ро­ж­да­ет­ся при сум­ме три, а уми­ра­ет при сум­ме менее двух – от оди­но­че­­ст­ва и бо­лее трех – от пе­ре­на­се­лен­но­сти. При всех иных кон­фи­гу­ра­ци­ях зна­чений и сумм клет­ка со­хра­ня­ет свое со­стояние. Не­смот­ря на про­сто­ту фор­му­ли­ров­ки, эво­лю­ции раз­ных ком­би­на­ций жи­вых кле­ток мо­гут весь­ма от­ли­чать­ся, и мно­гие из них име­ют свои име­на. На­при­мер, на ри­сун­ке на следующей странице изо­бра­же­но глай­дер­ное ру­жье – при­мер бес­конеч­но рас­ту­щей ко­лонии.

Со­стояния всех кле­ток вме­сте об­ра­зу­ют со­стояние все­го кле­точ­но­го ав­то­ма­та. Со­стояние кле­точ­но­го ав­то­ма­та ме­ня­ет­ся по так­там, в дис­крет­ном вре­мени. При смене со­стояния кле­точ­но­го ав­то­ма­та со­стояния всех об­ра­зую­щих его кле­ток ме­ня­ют­ся од­но­вре­мен­но. Для ка­ж­дой клет­ки но­вое со­стояние вы­чис­ля­ет­ся по оди­на­ко­во­му для всех кле­ток пра­ви­лу. Вход­ные дан­ные для пра­ви­ла – со­стояния са­мой клет­ки и ее вось­ми со­се­дей на i-м так­те. Ре­зуль­та­том бу­дет со­стояние этой клет­ки на (i+1)-м так­те. По­доб­ные ал­го­рит­мы за­ме­ча­тель­но па­рал­ле­лят­ся. Так­же ин­те­рес­на их осо­бен­ность, со­стоя­щая в том, что вре­мя на од­ну ите­ра­цию не за­ви­сит от со­стояния ав­то­ма­та.

Сле­ду­ет понимать, что кле­точ­ный ав­то­мат – это аб­ст­ракт­ная мо­дель. В ней пред­по­ла­га­ет­ся бес­конеч­ное чис­ло кле­ток. Ре­аль­ные ком­пь­ю­те­ры об­ла­да­ют конеч­ны­ми ре­сур­са­ми па­мя­ти и вре­мени. По­это­му при мо­де­ли­ро­вании кле­точ­но­го ав­то­ма­та клет­ки раз­ме­ща­ют­ся в мас­си­ве конеч­ных раз­ме­ров. Для всех кле­ток, не ле­жа­щих на границах мас­си­ва, ра­бо­та­ют пра­ви­ла мо­де­ли­руе­мо­го кле­точ­но­го ав­то­ма­та без ка­ких-ли­бо из­менений. Об­ра­бот­ка же гранич­ных кле­ток про­из­во­дит­ся несколь­ко ина­че. Два наи­бо­лее рас­про­странен­ных спо­со­ба об­ра­бот­ки – за­мы­кание граней (из пря­мо­уголь­но­го мас­си­ва по­лу­ча­ет­ся трех­мер­ный тор) и ис­поль­зо­вание ну­ле­вых зна­чений для тех со­седних кле­ток из ок­ре­ст­но­сти клет­ки на границе, ко­то­рые ле­жат за пре­де­ла­ми мас­си­ва.

По­сле­до­ва­тель­ная про­грам­ма для «Жизни» (без про­це­дур за­дания на­чаль­ных зна­чений и пе­ча­ти или со­хранения ре­зуль­та­та) вы­гля­дит при­мер­но сле­дую­щим об­ра­зом:

1. define QTY_STEPS 8192

1. define SIZE_ARRAY 1024

char ar[2][SIZE_ARRAY][SIZE_ARRAY];

void computeCell(unsigned dir, unsigned x, unsigned y){

unsigned sum;

sum = ar[dir][y-1][x-1]+ar[dir][y-1][x]+ar[dir][y-1][x+1]+

ar[dir][y][x-1]+ar[dir][y][x+1]+

ar[dir][y+1][x-1]+ar[dir][y+1][x]+d ar[dir][y+1][x+1];

if((sum<2)||(sum>3))

ar[1-dir][y][x]=0;

else

ar[1-dir][y][x] = (sum==3) ? 1: ar[dir][y][x];

}

void simulateStep(unsigned layer){

unsigned x,y;

for(y=1;y<SIZE_ARRAY-1;y++)

for(x=1;x<SIZE_ARRAY-1;x++)

computeCell(layer,x,y);

}

void simulate(unsigned stepQty){

unsigned step;

for(step=0;step<stepQty;step++){

simulateStep(step & 1);

}

}

main(){

simulate(QTY_STEPS);

}

Функ­ция ComputeCell вы­чис­ля­ет но­вое со­стояние од­ной клет­ки. Функ­ция SimulateStep вы­чис­ля­ет но­вое со­стояние все­го кле­точ­но­го ав­то­ма­та, а Simulate ими­ти­ру­ет ра­бо­ту кле­точ­но­го ав­то­ма­та ука­зан­ное чис­ло ша­гов.

Об­ра­ти­те внимание, что в мас­си­ве ar вве­де­но 2 слоя. Это тре­бу­ет­ся для то­го, что­бы ими­ти­ро­вать од­но­вре­мен­ность за­дания но­вых зна­чений кле­ток. Что­бы ис­клю­чить ко­пи­ро­вание од­но­го слоя в дру­гой, на чет­ном ша­ге те­ку­щие зна­чения кле­ток бе­рут­ся из ну­ле­во­го слоя, но­вые пи­шут­ся в пер­вый; а на нечет­ных ша­гах, на­обо­рот, те­ку­щие зна­чения бе­рут­ся из пер­во­го слоя, но­вые пи­шут­ся в ну­ле­вой.

Для MPI-вер­сии про­грам­мы возь­мем за осно­ву по­сле­до­ва­тель­ную реа­ли­за­цию. Для про­сто­ты ог­раничим­ся дву­мя про­цес­са­ми. Раз­де­лим мас­сив, хра­ня­щий со­стояния кле­ток, по­ров­ну.

Раз­де­ление про­из­ве­дем по стро­кам. Пусть пер­вая по­ло­ви­на строк хранит­ся в мас­си­ве ar пер­во­го про­цес­са (rankNode ра­вен ну­лю), вто­рая – в этом же мас­си­ве ar у вто­ро­го про­цес­са (rankNode ра­вен 1).

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

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

Функ­ция ComputeCell не ме­ня­ет­ся, так что ниже мы ее не дуб­ли­ру­ем:

1. define QTY_STEPS 8192

1. define SIZE_ARRAY 1024

1. define SIZE_HALFARRAY (SIZE_ARRAY/2+1)

char ar[2][SIZE_HALFARRAY][SIZE_ARRAY];

1. define RES_OK 0

1. define RES_ERROR 1

int mytag=99;

void simulateStep(unsigned layer){

unsigned x,y;

for(y=1;y<SIZE_HALFARRAY-1;y++)

for(x=1;x<SIZE_ARRAY-1;x++)

computeCell(layer,x,y);

}

void simulate(unsigned stepQty,int rankNode){

unsigned step;

MPI_Status status;

for(step=0;step<stepQty;step++){

simulateStep(step & 1);

if(rankNode==0){

MPI_Send(ar[1 - step & 1][SIZE_ARRAY/2 - 1], SIZE_ARRAY, MPI_CHAR, rankNode + 1, mytag, MPI_COMM_WORLD);

MPI_Recv(ar[1 - step & 1][SIZE_ARRAY/2], SIZE_ARRAY, MPI_CHAR, rankNode + 1, mytag,MPI_COMM_WORLD, &status);

}

else if(rankNode==1){

MPI_Recv(ar[1 - step & 1][0], SIZE_ARRAY, MPI_CHAR, rankNode - 1, mytag, MPI_COMM_WORLD, &status);

MPI_Send(ar[1 - step & 1][1], SIZE_ARRAY, MPI_CHAR, rankNode - 1, mytag, MPI_COMM_WORLD);

}

}

}

main(int argc, char **argv){

int rankNode, sizeCluster;

MPI_Init(&argc, &argv);

MPI_Comm_rank(MPI_COMM_WORLD, &rankNode);

MPI_Comm_size(MPI_COMM_WORLD, &sizeCluster);

if (sizeCluster!=2) {

printf (“Толь­ко для двух ядер!”);

exit(1);

}

simulate(QTY_STEPS, rankNode);

MPI_Finalize();

}

А вот опе­ра­тор цик­ла в SimulateStep уже от­ли­ча­ет­ся от то­го, что был в по­сле­до­ва­тель­ной вер­сии, как и раз­мер мас­си­ва ar. Функ­ция main уже со­дер­жит в се­бе ко­ман­ды инициа­ли­за­ции и за­вер­шения MPI.

Наи­бо­лее силь­ным из­менениям под­вер­глась функ­ция simulate. Те­перь по­сле ка­ж­до­го ша­га тре­бу­ет­ся пе­ре­да­вать зна­чения кле­ток всех теневых граней ме­ж­ду со­седними уз­ла­ми.

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

Соб­ст­вен­но го­во­ря, все. Ка­жет­ся, ниче­го слож­но­го, но ес­ли хо­чет­ся уве­ли­чить чис­ло па­рал­лель­ных про­цес­сов, то при­дет­ся ак­ку­рат­но об­ра­ба­ты­вать боль­ше границ и сле­дить за со­гла­со­ванием прие­ма-пе­ре­да­чи ин­фор­ма­ции, то есть при­дет­ся ду­мать. Это и есть основ­ная слож­ность! Но за­то MPI-про­грам­ма на двух про­цес­сах вы­пол­ня­ет­ся при­мер­но за 110 се­кунд вме­сто 180 на сфе­ри­че­­ском в ва­куу­ме Intel(R) Core(TM)2 Duo од­но­вре­мен­но с на­бо­ром это­го тек­ста. Ус­ко­рение не в двой­ку, но доста­точ­но зна­чи­тель­ное, что­бы за него по­бо­роть­ся.

На при­ме­ре про­грам­мы мо­де­ли­ро­вания иг­ры «Жизнь» мы рас­смот­ре­ли са­мые ба­зо­вые воз­мож­но­сти MPI. Из со­тен функ­ций, опи­сан­ных в те­ку­щем стан­дар­те MPI 3.0, мы ис­поль­зо­ва­ли толь­ко шесть. Стан­дарт ори­ен­ти­ро­ван на ком­форт­ную ра­бо­ту при рас­па­рал­ле­ли­вании ши­ро­ко­го спек­тра за­дач, и для это­го в нем при­сут­ст­ву­ют раз­но­об­раз­ные груп­пы функ­ций для ком­муника­ций ме­ж­ду дву­мя про­цес­са­ми, ком­муника­ций внут­ри груп­пы про­цес­сов, ра­бо­ты с груп­па­ми про­цес­сов, кэ­ши­ро­вания дан­ных и мно­гого дру­го­го. |