Журнал LinuxFormat - перейти на главную

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

Материал из Linuxformat
(Различия между версиями)
Перейти к: навигация, поиск
(Новая страница: «Категория: Учебники '''Па­рал­лель­ные тех­но­ло­гии. Введение в актуальную тему''' == В…»)
 
(Иг­ра «Жизнь»)
 
(не показаны 4 промежуточные версии 1 участника)
Строка 5: Строка 5:
 
[[Файл:Lxf168Exper.png |left |100px |thumb|'''Наш эксперт''' Ми­ха­ил Ос­тап­ке­вич романтик, очарованный компьютерами и создаваемыми в них идеальными мирами; верит, что сложнейшие новые технологии могут и должны служить во благо человечеству.]]  
 
[[Файл:Lxf168Exper.png |left |100px |thumb|'''Наш эксперт''' Ми­ха­ил Ос­тап­ке­вич романтик, очарованный компьютерами и создаваемыми в них идеальными мирами; верит, что сложнейшие новые технологии могут и должны служить во благо человечеству.]]  
 
Вре­ме­на боль­ших век­тор­ных су­пер­ком­пь­ю­те­ров про­шли, ну или по­ка не на­ста­ли. Что мы име­ем вза­мен? Мно­же­ст­во неза­ви­си­мых «пи­си­шек», да­же ес­ли они и уста­нов­ле­ны в стой­ки и управ­ля­ют­ся ква­ли­фи­ци­ро­ван­ны­ми ад­минист­ра­то­ра­ми! За­пустить на них пач­ку за­дач лег­ко, но как под­от­чет­ные про­цес­сы бу­дут об­щать­ся? Да с по­мо­щью MPI!
 
Вре­ме­на боль­ших век­тор­ных су­пер­ком­пь­ю­те­ров про­шли, ну или по­ка не на­ста­ли. Что мы име­ем вза­мен? Мно­же­ст­во неза­ви­си­мых «пи­си­шек», да­же ес­ли они и уста­нов­ле­ны в стой­ки и управ­ля­ют­ся ква­ли­фи­ци­ро­ван­ны­ми ад­минист­ра­то­ра­ми! За­пустить на них пач­ку за­дач лег­ко, но как под­от­чет­ные про­цес­сы бу­дут об­щать­ся? Да с по­мо­щью MPI!
 
+
[[Файл:Lxf168Expert2.png |left |100px |thumb|'''Наш эксперт''' Ев­ге­ний Бал­дин Физик, который действительно знает, что такое нехватка вычислительных ресурсов.]]
 
MPI или Message Passing Interface или, по-про­сто­му, ин­тер­фейс пе­ре­да­чи со­об­щений – это стан­дарт­ный про­грамм­ный ин­тер­фейс для пе­ре­да­чи ин­фор­ма­ции ме­ж­ду про­цес­са­ми, вы­пол­няю­щи­ми од­ну за­да­чу. Стан­дарт под­дер­жи­ва­ет­ся кон­сор­циу­мом MPI Forum, чле­на­ми ко­то­ро­го яв­ля­ют­ся прак­ти­че­­ски все круп­ные про­из­во­ди­те­ли вы­чис­ли­тель­ной техники и про­грамм­но­го обес­пе­чения. Пер­вый стан­дарт MPI 1.0 при­нят в 1994 го­ду. Фор­маль­но раз­ра­бот­ка на­ча­лась в 1991 го­ду, когда неболь­шая груп­па уче­ных-ин­фор­ма­ти­ков со­бра­лась в уе­ди­нен­ном ав­ст­рий­ском гор­ном пан­сио­на­те и на­ча­ла ак­тив­но об­менивать­ся мнениями. В сен­тяб­ре 2012 го­да вы­шла спе­ци­фи­ка­ция MPI 3.0.
 
MPI или Message Passing Interface или, по-про­сто­му, ин­тер­фейс пе­ре­да­чи со­об­щений – это стан­дарт­ный про­грамм­ный ин­тер­фейс для пе­ре­да­чи ин­фор­ма­ции ме­ж­ду про­цес­са­ми, вы­пол­няю­щи­ми од­ну за­да­чу. Стан­дарт под­дер­жи­ва­ет­ся кон­сор­циу­мом MPI Forum, чле­на­ми ко­то­ро­го яв­ля­ют­ся прак­ти­че­­ски все круп­ные про­из­во­ди­те­ли вы­чис­ли­тель­ной техники и про­грамм­но­го обес­пе­чения. Пер­вый стан­дарт MPI 1.0 при­нят в 1994 го­ду. Фор­маль­но раз­ра­бот­ка на­ча­лась в 1991 го­ду, когда неболь­шая груп­па уче­ных-ин­фор­ма­ти­ков со­бра­лась в уе­ди­нен­ном ав­ст­рий­ском гор­ном пан­сио­на­те и на­ча­ла ак­тив­но об­менивать­ся мнениями. В сен­тяб­ре 2012 го­да вы­шла спе­ци­фи­ка­ция MPI 3.0.
  
Строка 38: Строка 38:
 
mpi-doc, кро­ме html-спра­вочника, до­бав­ля­ет в сис­те­му man-странич­ки по мно­го­чис­лен­ным MPI-функ­ци­ям, очень удоб­ные для бы­ст­ро­го под­гля­ды­вания.
 
mpi-doc, кро­ме html-спра­вочника, до­бав­ля­ет в сис­те­му man-странич­ки по мно­го­чис­лен­ным MPI-функ­ци­ям, очень удоб­ные для бы­ст­ро­го под­гля­ды­вания.
  
Здрав­ст­вуй, Мир!
+
===Здрав­ст­вуй, Мир!===
  
 
Пред­по­ла­га­ет­ся, что вы пред­став­ляе­те, что та­кое про­грам­ми­ро­вание на C, ну или хо­тя бы на­пи­са­ли на этом язы­ке свой лич­ный HelloWorld. Вот так вы­гля­дит про­стей­шая MPI-про­грам­ма:
 
Пред­по­ла­га­ет­ся, что вы пред­став­ляе­те, что та­кое про­грам­ми­ро­вание на C, ну или хо­тя бы на­пи­са­ли на этом язы­ке свой лич­ный HelloWorld. Вот так вы­гля­дит про­стей­шая MPI-про­грам­ма:
Строка 158: Строка 158:
 
Not enough processors were found on the local host to meet the requested binding action
 
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]. По иг­ре «Жизнь» есть мас­са по­пу­ляр­ной ли­те­ра­ту­ры, в том чис­ле и на русском язы­ке.
 
Кле­точ­ный ав­то­мат «Жизнь [Game of Life, или про­сто Life]» был пред­ло­жен анг­лий­ским ма­те­ма­ти­ком Джо­ном Кон­ве­ем [John Horton Conway] в 1979 го­ду. Вряд ли он стал бы так ши­ро­ко из­вес­тен, ес­ли бы не аме­ри­кан­ский ма­те­ма­тик и ис­клю­чи­тель­но энергичый по­пу­ля­ри­за­тор нау­ки Мар­тин Гарднер [Martin Gardner]. По иг­ре «Жизнь» есть мас­са по­пу­ляр­ной ли­те­ра­ту­ры, в том чис­ле и на русском язы­ке.
Строка 165: Строка 165:
  
 
Со­стояния всех кле­ток вме­сте об­ра­зу­ют со­стояние все­го кле­точ­но­го ав­то­ма­та. Со­стояние кле­точ­но­го ав­то­ма­та ме­ня­ет­ся по так­там, в дис­крет­ном вре­мени. При смене со­стояния кле­точ­но­го ав­то­ма­та со­стояния всех об­ра­зую­щих его кле­ток ме­ня­ют­ся од­но­вре­мен­но. Для ка­ж­дой клет­ки но­вое со­стояние вы­чис­ля­ет­ся по оди­на­ко­во­му для всех кле­ток пра­ви­лу. Вход­ные дан­ные для пра­ви­ла – со­стояния са­мой клет­ки и ее вось­ми со­се­дей на i-м так­те. Ре­зуль­та­том бу­дет со­стояние этой клет­ки на (i+1)-м так­те. По­доб­ные ал­го­рит­мы за­ме­ча­тель­но па­рал­ле­лят­ся. Так­же ин­те­рес­на их осо­бен­ность, со­стоя­щая в том, что вре­мя на од­ну ите­ра­цию не за­ви­сит от со­стояния ав­то­ма­та.
 
Со­стояния всех кле­ток вме­сте об­ра­зу­ют со­стояние все­го кле­точ­но­го ав­то­ма­та. Со­стояние кле­точ­но­го ав­то­ма­та ме­ня­ет­ся по так­там, в дис­крет­ном вре­мени. При смене со­стояния кле­точ­но­го ав­то­ма­та со­стояния всех об­ра­зую­щих его кле­ток ме­ня­ют­ся од­но­вре­мен­но. Для ка­ж­дой клет­ки но­вое со­стояние вы­чис­ля­ет­ся по оди­на­ко­во­му для всех кле­ток пра­ви­лу. Вход­ные дан­ные для пра­ви­ла – со­стояния са­мой клет­ки и ее вось­ми со­се­дей на i-м так­те. Ре­зуль­та­том бу­дет со­стояние этой клет­ки на (i+1)-м так­те. По­доб­ные ал­го­рит­мы за­ме­ча­тель­но па­рал­ле­лят­ся. Так­же ин­те­рес­на их осо­бен­ность, со­стоя­щая в том, что вре­мя на од­ну ите­ра­цию не за­ви­сит от со­стояния ав­то­ма­та.
 +
{{Врезка|left|Заголовок= Клас­си­фи­ка­ция па­рал­лель­ных ком­пь­ю­те­ров|Ширина=98%|Содержание=Со­вре­мен­ные па­рал­лель­ные ком­пь­ю­те­ры мож­но раз­де­лить на: па­рал­лель­ные век­тор­ные сис­те­мы (PVP), сим­мет­рич­ные муль­ти­про­цес­сор­ные сис­те­мы (SMP), мас­сив­но-па­рал­лель­ные сис­те­мы (MPP), сис­те­мы с неод­но­род­ным досту­пом к па­мя­ти (NUMA) и кла­сте­ры.
  
 +
При­ме­ром па­рал­лель­ной век­тор­ной сис­те­мы (PVP) яв­ля­ет­ся пер­вый су­пер­ком­пь­ю­тер CRAY-I, ко­то­рый был соз­дан в 1975 го­ду. Од­но вре­мя по­ня­тия «па­рал­лель­ные век­тор­ные сис­те­мы» и «су­пер­ком­пь­ю­те­ры» бы­ли си­нонима­ми, но сей­час в TOP500 (http://www.top500.org/) клас­си­че­­ских PVP не оста­лось со­всем.
 +
 +
Сим­мет­рич­ные муль­ти­про­цес­сор­ные сис­те­мы (SMP) со­дер­жат несколь­ко оди­на­ко­вых про­цес­со­ров и об­щую па­мять. Все про­цес­со­ры име­ют оди­на­ко­вую ско­рость досту­па к об­щей па­мя­ти. Имея по­сле­до­ва­тель­ную реа­ли­за­цию неко­то­рой про­грам­мы, как пра­ви­ло, мож­но от­но­си­тель­но лег­ко по­стро­ить ее па­рал­лель­ную реа­ли­за­цию для SMP. Ос­нов­ной недоста­ток SMP – пло­хая мас­шта­би­руе­мость. Су­ще­ст­ву­ют доступ­ные SMP-сис­те­мы с де­сят­ка­ми про­цес­со­ров, но в спи­ске TOP500 нет ни од­ной из них.
 +
 +
Ком­пь­ю­те­ры клас­са MPP (мас­сив­но-па­рал­лель­ные сис­те­мы) со­сто­ят из уз­лов, объ­е­динен­ных вы­со­ко­ско­ро­ст­ным ком­му­та­то­ром. Узел со­дер­жит один или несколь­ко про­цес­со­ров и па­мять. Узел не име­ет досту­па к па­мя­ти дру­гих уз­лов. Та­кие сис­те­мы, в от­ли­чие от SMP, хо­ро­шо мас­шта­би­ру­ют­ся. Чис­ло уз­лов в са­мых боль­ших MPP-сис­те­мах дости­га­ет со­тен ты­сяч. За это при­хо­дит­ся пла­тить, так как па­рал­лель­ную про­грам­му для MPP-сис­те­мы, в от­ли­чие от SMP, по­стро­ить сложнее. Про­цес­сы, вы­пол­няю­щие­ся на раз­ных уз­лах, не име­ют об­щей па­мя­ти, и все взаи­мо­дей­ст­вие ме­ж­ду ними де­ла­ет­ся с по­мо­щью по­сыл­ки со­об­щений. На но­ябрь 2012 г. в TOP500 на­хо­дит­ся 89 клас­си­че­­ских MPP-су­пер­ком­пь­ю­те­ров, вклю­чая пер­вые две по­зи­ции.
 +
 +
Сис­те­мы с неод­но­род­ным досту­пом к па­мя­ти (NUMA) яв­ля­ют­ся гиб­ри­дом SMP и MPP. Фи­зи­че­­ски вся па­мять в NUMA рас­пре­де­ле­на ме­ж­ду уз­ла­ми, как в MPP. Но при этом под­дер­жи­ва­ет­ся еди­ное про­стран­ст­во па­мя­ти, как в SMP. То есть из уз­ла мож­но об­ра­тить­ся к па­мя­ти в лю­бом дру­гом уз­ле. Вре­мя досту­па к сво­ей, локаль­ной па­мя­ти мень­ше, чем к па­мя­ти дру­го­го уз­ла.
 +
 +
Кла­стер – это де­ше­вый ана­лог MPP-сис­те­мы. В нем вме­сто ско­ро­ст­но­го ком­му­та­то­ра ис­поль­зу­ет­ся обы­чая сеть; таковые ста­но­вят­ся все бы­ст­рее и бы­ст­рее. Ес­ли MPP по­ка еще вы­де­ля­ют­ся мо­щью, то кла­сте­ры бе­рут мас­со­во­стью, ибо 411 су­пер­ком­пь­ю­те­ров, остаю­щие­ся по­сле вы­чи­тания MPP из TOP500, яв­ля­ют­ся кла­стер­ны­ми ре­шения­ми.
 +
}}
 
Сле­ду­ет понимать, что кле­точ­ный ав­то­мат – это аб­ст­ракт­ная мо­дель. В ней пред­по­ла­га­ет­ся бес­конеч­ное чис­ло кле­ток. Ре­аль­ные ком­пь­ю­те­ры об­ла­да­ют конеч­ны­ми ре­сур­са­ми па­мя­ти и вре­мени. По­это­му при мо­де­ли­ро­вании кле­точ­но­го ав­то­ма­та клет­ки раз­ме­ща­ют­ся в мас­си­ве конеч­ных раз­ме­ров. Для всех кле­ток, не ле­жа­щих на границах мас­си­ва, ра­бо­та­ют пра­ви­ла мо­де­ли­руе­мо­го кле­точ­но­го ав­то­ма­та без ка­ких-ли­бо из­менений. Об­ра­бот­ка же гранич­ных кле­ток про­из­во­дит­ся несколь­ко ина­че. Два наи­бо­лее рас­про­странен­ных спо­со­ба об­ра­бот­ки – за­мы­кание граней (из пря­мо­уголь­но­го мас­си­ва по­лу­ча­ет­ся трех­мер­ный тор) и ис­поль­зо­вание ну­ле­вых зна­чений для тех со­седних кле­ток из ок­ре­ст­но­сти клет­ки на границе, ко­то­рые ле­жат за пре­де­ла­ми мас­си­ва.
 
Сле­ду­ет понимать, что кле­точ­ный ав­то­мат – это аб­ст­ракт­ная мо­дель. В ней пред­по­ла­га­ет­ся бес­конеч­ное чис­ло кле­ток. Ре­аль­ные ком­пь­ю­те­ры об­ла­да­ют конеч­ны­ми ре­сур­са­ми па­мя­ти и вре­мени. По­это­му при мо­де­ли­ро­вании кле­точ­но­го ав­то­ма­та клет­ки раз­ме­ща­ют­ся в мас­си­ве конеч­ных раз­ме­ров. Для всех кле­ток, не ле­жа­щих на границах мас­си­ва, ра­бо­та­ют пра­ви­ла мо­де­ли­руе­мо­го кле­точ­но­го ав­то­ма­та без ка­ких-ли­бо из­менений. Об­ра­бот­ка же гранич­ных кле­ток про­из­во­дит­ся несколь­ко ина­че. Два наи­бо­лее рас­про­странен­ных спо­со­ба об­ра­бот­ки – за­мы­кание граней (из пря­мо­уголь­но­го мас­си­ва по­лу­ча­ет­ся трех­мер­ный тор) и ис­поль­зо­вание ну­ле­вых зна­чений для тех со­седних кле­ток из ок­ре­ст­но­сти клет­ки на границе, ко­то­рые ле­жат за пре­де­ла­ми мас­си­ва.
  
 
По­сле­до­ва­тель­ная про­грам­ма для «Жизни» (без про­це­дур за­дания на­чаль­ных зна­чений и пе­ча­ти или со­хранения ре­зуль­та­та) вы­гля­дит при­мер­но сле­дую­щим об­ра­зом:
 
По­сле­до­ва­тель­ная про­грам­ма для «Жизни» (без про­це­дур за­дания на­чаль­ных зна­чений и пе­ча­ти или со­хранения ре­зуль­та­та) вы­гля­дит при­мер­но сле­дую­щим об­ра­зом:
  
#define QTY_STEPS 8192
+
#define QTY_STEPS 8192
  
#define SIZE_ARRAY 1024
+
#define SIZE_ARRAY 1024
  
 
char ar[2][SIZE_ARRAY][SIZE_ARRAY];
 
char ar[2][SIZE_ARRAY][SIZE_ARRAY];
Строка 240: Строка 251:
 
Функ­ция ComputeCell не ме­ня­ет­ся, так что ниже мы ее не дуб­ли­ру­ем:
 
Функ­ция ComputeCell не ме­ня­ет­ся, так что ниже мы ее не дуб­ли­ру­ем:
  
#define QTY_STEPS 8192
+
#define QTY_STEPS 8192
  
#define SIZE_ARRAY 1024
+
#define SIZE_ARRAY 1024
  
#define SIZE_HALFARRAY (SIZE_ARRAY/2+1)
+
#define SIZE_HALFARRAY (SIZE_ARRAY/2+1)
  
 
char ar[2][SIZE_HALFARRAY][SIZE_ARRAY];
 
char ar[2][SIZE_HALFARRAY][SIZE_ARRAY];
  
#define RES_OK 0
+
#define RES_OK 0
  
#define RES_ERROR 1
+
#define RES_ERROR 1
  
 
int mytag=99;
 
int mytag=99;
Строка 325: Строка 336:
  
 
Эту за­да­чу вы­пол­ня­ют опе­ра­то­ры пе­ре­да­чи MPI_Send и прие­ма MPI_Recv. Они долж­ны быть ком­пле­мен­тар­ны­ми, то есть ка­ж­дый опе­ра­тор пе­ре­да­чи дан­ных в од­ном про­цес­се обя­за­тель­но обя­зан иметь со­от­вет­ст­вую­щий ему опе­ра­тор прие­ма в дру­гом про­цес­се. В про­тив­ном слу­чае про­изой­дет ненор­маль­ное за­вер­шение ра­бо­ты MPI про­грам­мы. Под­роб­но­сти об ис­поль­зо­вании этих команд и опи­сание их ар­гу­мен­тов мож­но по­смот­реть с по­мо­щью ко­ман­ды man.
 
Эту за­да­чу вы­пол­ня­ют опе­ра­то­ры пе­ре­да­чи MPI_Send и прие­ма MPI_Recv. Они долж­ны быть ком­пле­мен­тар­ны­ми, то есть ка­ж­дый опе­ра­тор пе­ре­да­чи дан­ных в од­ном про­цес­се обя­за­тель­но обя­зан иметь со­от­вет­ст­вую­щий ему опе­ра­тор прие­ма в дру­гом про­цес­се. В про­тив­ном слу­чае про­изой­дет ненор­маль­ное за­вер­шение ра­бо­ты MPI про­грам­мы. Под­роб­но­сти об ис­поль­зо­вании этих команд и опи­сание их ар­гу­мен­тов мож­но по­смот­реть с по­мо­щью ко­ман­ды man.
 
+
{{Врезка|right|Заголовок= Об­рат­ная связь|Ширина=20%|Содержание=При­гла­ша­ем вы­ска­зать­ся по­тен­ци­аль­ных ав­то­ров ста­тей по па­рал­лель­ным вы­чис­лениям – цен­ные пред­ло­жения, кри­ти­ку и со­ве­ты при­сы­лай­те по элек­трон­ной поч­те: E.M.Baldin@inp.nsk.su, ostap@ssd.sscc.ru.
 +
}}
 
Соб­ст­вен­но го­во­ря, все. Ка­жет­ся, ниче­го слож­но­го, но ес­ли хо­чет­ся уве­ли­чить чис­ло па­рал­лель­ных про­цес­сов, то при­дет­ся ак­ку­рат­но об­ра­ба­ты­вать боль­ше границ и сле­дить за со­гла­со­ванием прие­ма-пе­ре­да­чи ин­фор­ма­ции, то есть при­дет­ся ду­мать. Это и есть основ­ная слож­ность! Но за­то MPI-про­грам­ма на двух про­цес­сах вы­пол­ня­ет­ся при­мер­но за 110 се­кунд вме­сто 180 на сфе­ри­че­­ском в ва­куу­ме Intel(R) Core(TM)2 Duo од­но­вре­мен­но с на­бо­ром это­го тек­ста. Ус­ко­рение не в двой­ку, но доста­точ­но зна­чи­тель­ное, что­бы за него по­бо­роть­ся.
 
Соб­ст­вен­но го­во­ря, все. Ка­жет­ся, ниче­го слож­но­го, но ес­ли хо­чет­ся уве­ли­чить чис­ло па­рал­лель­ных про­цес­сов, то при­дет­ся ак­ку­рат­но об­ра­ба­ты­вать боль­ше границ и сле­дить за со­гла­со­ванием прие­ма-пе­ре­да­чи ин­фор­ма­ции, то есть при­дет­ся ду­мать. Это и есть основ­ная слож­ность! Но за­то MPI-про­грам­ма на двух про­цес­сах вы­пол­ня­ет­ся при­мер­но за 110 се­кунд вме­сто 180 на сфе­ри­че­­ском в ва­куу­ме Intel(R) Core(TM)2 Duo од­но­вре­мен­но с на­бо­ром это­го тек­ста. Ус­ко­рение не в двой­ку, но доста­точ­но зна­чи­тель­ное, что­бы за него по­бо­роть­ся.
  
 
На при­ме­ре про­грам­мы мо­де­ли­ро­вания иг­ры «Жизнь» мы рас­смот­ре­ли са­мые ба­зо­вые воз­мож­но­сти MPI. Из со­тен функ­ций, опи­сан­ных в те­ку­щем стан­дар­те MPI 3.0, мы ис­поль­зо­ва­ли толь­ко шесть. Стан­дарт ори­ен­ти­ро­ван на ком­форт­ную ра­бо­ту при рас­па­рал­ле­ли­вании ши­ро­ко­го спек­тра за­дач, и для это­го в нем при­сут­ст­ву­ют раз­но­об­раз­ные груп­пы функ­ций для ком­муника­ций ме­ж­ду дву­мя про­цес­са­ми, ком­муника­ций внут­ри груп­пы про­цес­сов, ра­бо­ты с груп­па­ми про­цес­сов, кэ­ши­ро­вания дан­ных и мно­гого дру­го­го. |
 
На при­ме­ре про­грам­мы мо­де­ли­ро­вания иг­ры «Жизнь» мы рас­смот­ре­ли са­мые ба­зо­вые воз­мож­но­сти MPI. Из со­тен функ­ций, опи­сан­ных в те­ку­щем стан­дар­те MPI 3.0, мы ис­поль­зо­ва­ли толь­ко шесть. Стан­дарт ори­ен­ти­ро­ван на ком­форт­ную ра­бо­ту при рас­па­рал­ле­ли­вании ши­ро­ко­го спек­тра за­дач, и для это­го в нем при­сут­ст­ву­ют раз­но­об­раз­ные груп­пы функ­ций для ком­муника­ций ме­ж­ду дву­мя про­цес­са­ми, ком­муника­ций внут­ри груп­пы про­цес­сов, ра­бо­ты с груп­па­ми про­цес­сов, кэ­ши­ро­вания дан­ных и мно­гого дру­го­го. |

Текущая версия на 22:23, 10 ноября 2018

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

[править] Вве­де­ние в MPI

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

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

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

(thumbnail)
Наш эксперт Ев­ге­ний Бал­дин Физик, который действительно знает, что такое нехватка вычислительных ресурсов.

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)-м так­те. По­доб­ные ал­го­рит­мы за­ме­ча­тель­но па­рал­ле­лят­ся. Так­же ин­те­рес­на их осо­бен­ность, со­стоя­щая в том, что вре­мя на од­ну ите­ра­цию не за­ви­сит от со­стояния ав­то­ма­та.

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

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

#define QTY_STEPS 8192
#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 не ме­ня­ет­ся, так что ниже мы ее не дуб­ли­ру­ем:

#define QTY_STEPS 8192
#define SIZE_ARRAY 1024
#define SIZE_HALFARRAY (SIZE_ARRAY/2+1)

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

#define RES_OK 0
#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, мы ис­поль­зо­ва­ли толь­ко шесть. Стан­дарт ори­ен­ти­ро­ван на ком­форт­ную ра­бо­ту при рас­па­рал­ле­ли­вании ши­ро­ко­го спек­тра за­дач, и для это­го в нем при­сут­ст­ву­ют раз­но­об­раз­ные груп­пы функ­ций для ком­муника­ций ме­ж­ду дву­мя про­цес­са­ми, ком­муника­ций внут­ри груп­пы про­цес­сов, ра­бо­ты с груп­па­ми про­цес­сов, кэ­ши­ро­вания дан­ных и мно­гого дру­го­го. |

Персональные инструменты
купить
подписаться
Яндекс.Метрика