-12 Лекция. Параллель программалау. Программалау тілдері

MPI параллель программалаудың алғашқы құралдарының бірі. MPI кітапханасын қолданғанда торап үлестірілген программалар процессі С және Fortran сияқты тізбекті программалар тілдерінде жазылады. Процесстердің өзара әрекеті және оларды синхрондау MPI кітапханасына процедураларын шақыру көмегімен беріледі.

MPI қосымшаларын программалау интерфейсін 90-жылдардың ортасында университеттер, үкімет және өндірі ұйымдарының жобалау топтары құрған. Мақсат- әртүрлі көппроцессорлы машиналарда тиімді жүзеге асыратын бірдей кітапхана жасау. Бүгінгі күні MPI стандартқа айналды.

MPI кітапханасын қолданушы программаның SPMD стилі болады. Ол алдыңғы тауарлара сипатталған. Берілген жағдайда әрбір процесс бір ғана программаның көшірмесін орындайды. Программаның әрбір экземпляры MPI кітапханасының функцияларын шақыру арқылы өзара әрекеттеседі, олар процесстер, топтар және қоршаған ортаның өзара әрекеттерін қамтамасыз етеді.

MPI функционалдық сұраулардың кейбіреулерін қарастырамыз.

MPI Init- MPI кітапханасын инициализациялайды және программаға беретін командалық жолдың аргументерінің көшірмесін қайтарады. Нәтижесінде жіберілген процесстер жиыны инициаланады.

MPI Comm size- жіберілетін процесстер санын анықтайды.

MPI Send- процестің процесс рангін(идентификатор) анықтайды.0-ден 1-ге дейінгі сандар бола алады.

MPI Recv- хабарды беруді бұғаттау. Басқа процесске хабар береді.

MPI Finalize- MPIкітапханасын «алып тастайды» және процессті аяқтайды.

MPI Send және MPI Recv кітапханаларын толығырақ қарастырайық:

Int MPI Send (void*buf, int count, MPI Datatype dataType, int dest, int tag, MPI Comm comm)

Мұндағы buf,-буфер адресінің басы, count-жіберілетін элементтер саны; dataType-әрбір элемент типі, мысалы: MPI Int, MPI Double, MPI Char, және т.б.; dest-адресат рангісі; tag-хабар тэгі; comm.-коммуникатор.
Int MPI Recv (void*buf, int count,

MPI Datatype dataType,

int source, int tag,

MPI Comm comm,

MPI Status*status)

Мұндағы status-қайтару күнін қайтарады, source-беретін процесс идентификаторы немесе «немқұрайлы»; tag- хабар белгісі; қалған аргументтер MPI Send процедурасында сипатталған сияқты.

MPI кітапханасының көмегімен екі процесс арасындағы мәндерді алмастыру программасының бірін келтіреміз.

#include

#include

main(int argc, char*argv[])

{

Int myid,otherid,size;

Int myvalue, othervalue;

MPI Status status;

MPI Int

MPI Comm

MPI Comm

• 
  BSP-жалпы синхронды параллелизм
  

BSP (BULK SYNCHRONOUS PARALLEL) Жалпы синхронды параллелизм моделі синхронды өзара әрекеттесуден бөліп алынған және жады иерерхиясының әсері және хабар алмасу ескерілген. BSP моделі уш компанненттен тұрады:

1. 
   Жергілікті жадысы бар және бірдей жыладмдықпен істейтін процессорлар
   

1. 
   Процессорлардың өзара әрекеттесуіне мүмкіншілік беретін байланыс желісі;
   

1. 
   Барлық процессорлардың белгілі уақыт аралықтары арқылы синхрондау механизмі;
   

BSP -дегі есептеу асақадамдар тізбегінен тұрады. әрбір жеке қадамда процессорлар есептеулерді орындайды, олар жергілікті жадыны шақырады және басқа процессорлерге хабар жібереді. Хабар көшірме алуға сұрау немесе қашықтағы деректерді жаңартуға сұрау болады. Асақадам соңында процессорлар барьерлік синхрондауды орындайды және одан кейін осы асақадам бойындағы сұрауды өңдейді. Ары қарай процессорлар келесі асақадамды орындай бастайды.

BSP моделінің параметрі:

p- процессорлар саны;

l- синхрондау периодтылығы, синхрондау амалдары арасындағы уақыт бойынша қадамдарыны” минималды саны;

g- байланыс бағасы;

s- секуындына қадам санымен өлшенетін процессор жылдамдығы.

Байланыс бағасы һ өзараәрекеттесуде һ хабар жіберуге қажетті уақыт саны ретінде анықталады.

Уақыт пен бағасы келесі формуламен беріледі:

Tsuperster=Wmax+ghmax+l

мұндағы Wmax -кез келген ''вертуальды'' процессорлар орындайтын жергілікті амалдардың максималь саны (процесспен немесе ағынмен), процессор жібергеннемесе қабалдаған максимальды хабарлар саны. Программаның аяқталуына қажетті жалпы уақыт қадамдар саны түрінде беріледі. Берілген уақытты азайту үшін асақадам санын азайту керек,өйткені олардың әрбіреуі үшін 1синхрондау уақыты қажет. Сондай-ақ һжәне w-ні де азайту керек. Ол үшін жүктелгендерді үлестіру керек жәнепроцессорлар арасында хабарлар беруді баланстау керек, сондай-ақ жүктелгендерді үлестіру керек және процессорлар арасындағы есептеулерді баланстау керек.

BSP программаларды орындаудың қарапайым шаблондарын Oxford BSP libraryтабуға болады:

Bspstart(), bspfinish() - процесстерді басқару;

Bspstep(), bspstep_end() - синхрондау;

Bspfetch(), bspstore() - байланыс.

BSP модель PVM машина принципімен жұмыс істейді. Бұл модель Linux операциялық жүйесіне орнатылған, программалау үшін С++ программалау тілі қолданылады.

14 Лекция. Кескіндерді өңдеу типтері.

• 
  Occam- параллель программалау тілі
  

CSP алғашында 1978 жылы Тони Хоармен сипатталған. Бұл тіл Occam программалау тілін және тағы басқа соның ішіндегі Ада тілін жасауға ықпалын тигізді.

CSP тілі хабарды синхронды жіберуге және қорғалған өзараәрекеттесу негізделген.

Өзараәрекеттесу операторларын қарастырамыз.

А процессі В процесіне өрнек мәнін жіберу керек. CSP тілінде ол мынадай түрде болады:

process А {...В!е;...}

process В {...А?х…}

В!е операторы шығару операторы деп аталады. Ол В жіберілу процесін және осы процесске жіберетін өрнектің е мәнін береді. А?x енгізу операторы деп аталады. Ол А енгізу процесі мен қабылданған хабар жазылатын х айнымалысын көрсетеді. Берілген операторлар енгізу және шығару операторлары деп аталады. Енгізу және шығару операторлары процесті басқа процесс сәйкес келесі операторды оаындағанға дейін тоқтатады, содан кейін екі оператор бір уақытта орындалады. Егер с және х айнымалысының типтері сәйкес келсе, онда берілген операторлар келісілген деп аталады. өзара әрекеттесудің келесілген операторларының орындалуын үрестірілген меншіктелу деп қарастыруға болады. Ондағы бір процссетің мәні екіншісіндегі айнымалыға меншіктеледі. өзараәрекеттесу жүргенде бұл процесстер синхрондалады, одан кейін жұмыстары тәуелсіз орындалады.

Occam тілі CSP тілін кеңейтеді. Occam тілінің шығуы ``Occam алмасы`` деген сөзден шыққан. Ол бірінші рет 80 жылдардың басында жасалған және транспьютермен жұмысқа арналған, қазір осы тілдің 3 нұсқасы бар.

Occam тілінің базалық элементтері хабарлаулар және үш қарапайым «процесс»: меншіктеу, енгізу және шығару болады. Меншіктеу процесі қарапайым меншіктеу операторы. Енгізу және шығару процесі CSP тілінің енгізу және шығару командаларына ұқсас, бірақ каналдардың атаулары болады, ондағы әрбір канал бір ғана жіберуші мен алушыдан тұрады.

Базалық процесстер конструкторы көмегімен әдеттегі процестерге біріктіріледі. Тізбектегі конструктор параллель конструктор және өзараәрекеттсудің қорғалған операторы бар. Тілдің синтаксисіне сәйкес әрбір базалық процесс, конструктор және хабарлау жеке жолдан тұрады. Хабарлау қос нүктемен аяқталады,ал жазуларда шегінулер қолданылады.

Occam тіліндегі программа процесстердің статистикалық санына және өзараәрекеттесудің статистикалық жолынан тұрады. Рекурсия және динамикалық құрулардың басқа типтері және объектілердің атаулары қолдамайды, сондықтан көптеген алгоритмдерді программалау қиын. Сонымен қатар, берілген қасиет программадағы процесстер санын анықтауға және олардың өзараәрекеттесу әдістерін компилятордың анықтауына мүмкіндік туғызады.

Берілген тілде құрамдас типтер диапозоны шектелген:

REAL32, REAL64, INT, BOOL.

Барлық хабарлаулар қос нүктемен анықталады.

Occam тілінде екі базалық констуктор қолданылады: тізбекті орындалу үшін SEQ және параллель үшін PAR конструкторы көмегімен құрылады. Мысалы:

INT x,y:

SEQ

Y:=Y+1

CHAN OF BYTE comm:

PAR

WHILE TRUE-пернетақтадан енгізу процесі

SEQ

comm ! сһ

Мұндағы keyboard және screen-келісім бойынша сыртқы құрылғылармен (пернетақта және экран) байланысқан каналдар.

Қорғалған өзараәрекеттесу ALT конструкторымен жасалады. Қорғау енгізу процессінен, немесе логикалық өрнектен және енгізу процесінен,немесе логикалық өрнек және SKIP конструкторынан тұрады.

Occam тілінде шығару командасын ALT конструкторын қорғауға қолдануға болмайды. Одан басқа, бұл тіл егер қолданылмаса бос хабарларды рұқсат етпейді.

Occam тілінің программаларының кейбір мысалын www.cs.ncl.ac.uk/usr/local/kroc/current/course/examples-дан алуға болады.

• 
  Жылдам әрекеттесуші фортран (HPF)
  

Екінші нұсқасы 1997 жылдың басында басылған. Бірінші компилятор қазір де бар, ал HPF-программалар жылдам әрекеттесуші машыналардың негізгі типтерде жұмыс істейді.

HPF-деректері параллель тіл. Ол Фортран 90 тізбекті тілінің кеңейтілген түрі, онда массивтер және оның бөліктеріне бірқатар амалдардықоймайтын тіл. HPF жобасына Фортранның ертеректегі деректері параллель Фортран 90 әсер етті.

HPF-тің негізгі компоненттері: деректер бойынша параллель массифтерді меншіктеу, деректерді үлестіруді басқару үшін компилятор дерективасы және параллель циклдарды жазу және синхрондауоператорлары. Төменде тілдің осы компоненттерінің әрбіреуі қарастырылады.

Массивтерді меншіктеу.

HPF-те Фортран 90-ға ұқсас бүтін массивтерге қолданылатын амалдардың бірқатары бар: меншіктеу, қосынды, көбейтінді ,есептеу т.с.с Массивтерге амалдарды сондай-ақ салыстырылатын массив фрагменттеріне қолдануға болады (келісілген секциялар). Мысалы, егер new және grid nxn өлшемді матрицалар болса, онда келесі код Якоби итерациялық әдісінің бас есептеу циклын іске асырады:

New(2&n-1,2:n-1)=

(grid (1:n-2,2:n-1)+grid(3:n,2:n-1)+

grid(2:n-1,1:n-2)+grid(2:n-1,3:n))/4

grid=new

end do
Массивтерді меншіктеудің екеуінде де деректер бойынша параллельдік семантикасы барЖ алдымен 1-ші бөлігі есептеледі, одан кейін барлық мәндер сол жақ бөлігіне меншіктеледі. Біріншісінде мәнді меншіктеп әрбір ішкі нүкесінде new төрт көршісінің grid арифметикалық ортасының мәніне тең болады. Екінші меншіктеуде new массиві қайтадан grid-ке көшіріледі. Шындығында бұл цикл денесі былай программалауға болады.

(3:n,2:n-1)+ grid(2:n-1,1:n-2)+ grid(2:n-1,3:n))/4

Сол бір массив екі бөлікте де пайда болуы мүмкін-бұл деректер бойынша параллель массивтерді меншіктеу семантикасына себепті. Алйда осы оператор үшін генерацияланған компилятор кодында бәрібір уақытша массивті, мысалы new қолдану керек.

HPF тілінде сондай-ақ редукция операторлары, олар массивтің барлық элементтеріне қандай да бір амалды қолданады және скаляр мәнді қайтарады.HPF тілінде деректерді бейнелеу дерективалары программистке деректердің ораласуын басқаруға, дербес жағдайда, олардылокализациялауға, әсіресе үлестірілген жадылы машиналарда мүмкіндік береді. Дерективалар HPF компиляторына берілетін кепілдеме, яғни программисттің берілген кеңес бойынша орындалу керек. Шын мәнінде программада деректерді бейнелейтін барлық дерективаларды жою есептің нәтижесіне ешқандай әсер етпеуі керек: тек программа тиімді жұмыс істемейді.

Негізгі дертивалар: PROCESSOR, ALIGN, DISTRIBUTE.

PROCESSOR дерективасы виртуальды машина процессорларының пішінін және өлшемін анықтайды.

ALIGN туралы дерективасы екі массив элементтерінің арасындағы өзарамәнді сәкестікті анықтайды, яғни олар туралануы керек және бірдей үлестірілуі қажет екендігін көрсетеді.

DISTRIBUTE дерективасы алдындағы PROCESSOR дерективасы арқылы анықталған массив виртуальды машина жадында қалайша бейнелейтінін анықтайды; бұл екі әдіс BLOK (бұғаттаулар), және CYCLIC (жолақтар) көмегімен белгіленеді.

Мысал ретінде position және foree–векторлар деп қарастырып, n денелерді имитациялау есебінде келесі кодты қарасытырамыз:
!HPF$ PROCCESORS pr(8)

!HPF$ ALIGN position (:) WITH foree (:)

!HPF$ DISTRIBUTE position (CYCLIC) ONTO pr
Бірінші директива 8 процессоры бар абстрактылы машинаны анықтайды, екіншісі-force қатысты position туралауын береді. Үшінші директивада position векторы процессорларға циклды бейнеленетінін көрсетеді (жолақтар бойынша); сәйкес force векторы дәл солай процессорлар арасында жолақтарға бөлінеді.

HPF деректерді бейнелеудің қосымша директиваларын қолдайды. DYNAMIC директивасы, туралау немесе массивті үлестеру программа жұмыс істейтін кезде RELIGN немесе REDISTRIBUTE директиваларының көмегімен өзгерететіндігін көрсетеді.

HPF параллель циклдарды берудің екі механизмін жасайды.

Forall операторы цикл денесі параллель орындалу керек екендігін көрсетеді. Мысалы , келесі циклде grid –тегі барлық жаңа мәндер параллель есептеледі:
Forall(i=2:n-1, j=2:n-1)

New (I,j)=(grid(i-16j)+grid(i+1,j)+grid(I,j-1)+grid(I,j+1))/4

Мұндағы нәтиже массивтерді меншіктегендегідей. Алайда Forall операторындағы цикл денесі бірден артық операторлар санынан тұруы мүмкін. Цикл денесі предикатты беру үшін маскалардан тұруы мүмкін, ол индекстік мәндерді қанағаттандыруы керек.

Параллель циклдарды жазудың екінші механизмі INDEPENDENT директивасы. Программист оны do циклының алдында орналастырса, ол циклдардың тәуелсіз екендігін және сондықтан олар параллель орнатылғандығын көрсетеді. Мысалы, төмендегі кодта

!HPF$ INDEPENDENT

do i=1, n

А(Index(i))=B(i)

End do
Index(i)-дің барлық элементтері әртүрлі және А және В жадыда қабыспайды. Егер В массив емес фуекция болса, программист сондай-ақ PURE директивасын қолдануы мүмкін, В-дағы жанама әсердің жоқ екендігін хабарлайды.

OpenMp – компилятор директиваларының және көмекші программалар жиынтығы. Жады бөлінетін параллельдікті өрнектеу үшін қолданайық. OpenMp үшін қолданбалы программалық интерфейстер (Apis) жоғары әрекеттесуші апараттық және программалық жасау шығарушылар тобымен құрылған Фортран интерфейсі 1997 жылдың соңында анықталған, С/С++ интерфейсі 1998 жылдың аяғында, бірақ екеуінің стандартталуы жалғасуда, Интерфейстер сол бір функцияны қамтамасыз етеді, бірақ Фортран, С және С++ лингвистикалық өзгешеліктеріне байланысты әр түрлі өрнектеледі.

OpenMp интерфейс негізінен компилятор дтрективасының жиынтығынан жасалған. Программис оны тізбекті программа компяторға программаның қай бөлігі паралель орындалуы керек және синхрандау нүктелерінің беру үшін қосады. Директиваларды біртіндеп қосуға болады, сондықтан OpenMp бар программалық жасауды паралельдеуді қамтамасыз етеді. MPI – көмекші программадан тұрады, олар тізбекті программадан шақырылады және олармен біріктіріледі де программистен процесс арасындағы жұмысты қолмен үлестіруді талап етеді.

Төмендегі Якоби әдісінің Фортан программасы үшін OpenMp-ні қолдану сипатталған.

OpenMp-де «тармақталу-тоғыстыру» моделі қолданылады. Алдымен бір орындалу ағыны болады. Parallel директивасының бірін кездестіргенде компилятор бір ағынды бірнеше ішкі ағындар бірігіп көптеген жұмыс ағындарын құрады. Нақты жұмысшы ағындар санын компилятор орнатады немесе қолданушы анықтайды немесе орта айналасы (environment) көмегімен статикалық түрде немесе OpenMp кітапханасынан көмекші программаны шақыру көмегімен динамикалық түрде анықталады.

OpenMp көмегімен программаны паралельдеу үшін программист алдымен паралель орындалатын программа бөліктерін анықтайды, мысалы, циклдар және оларда parallel және end parallel директиваларымен қоршайды. Әрбір жұмысшы ағын бұл кодты итерациялар кеңістігінде әртүрлі ішкі жиындарды өңдей отырып немесе әртүрлі көмекші программаларды шақыра отырып орындайды. Одан кейін программаға орындалу барысында ағындарды синхрондау үшін қосымша директивалар қосылады. Осылайша, компятор ағындарды бөлу және олардың арасындағы жұмысты үлестіруге жауап береді, ал программист жеткілікті синхрондауды қамтамасыз ету керек.

Нақты мысал ретінде келесі тізбекті кодты қарастырамыз, онда grid және new ішкі нүктелерінің алғашқы мәндері ноль:

Do j=2,n-1

Do i=2, n-1

Grid(I,j)=0.0

new(i,j)=0.0

End do

Берілген кодты паралельдеу үшін оған OpenMp-ң үш директивасын қосамыз:

!$omp parallel do

!$omp&shared(n,grid,new), private(i,j)

do j=2,n-1

do j=2,n-1

grid(i,j)=0.0

new(i,j)=0.0

enddo

enddo

Компилятордың директивасы !$omp-дан басталады. Бірінші паралель do циклының басы. Екіншісі біріншісін толықтырады, !$omp-ге & символын қосып белгіленген. Екінші директивада барлық жұмысшы ағындарда n, grid және new бөлінетін айнымалылар, ал i және j жергілікті айнымалылар екендігін хабарлайды. Соңғы директива do паралель цикл соңын және соңын білдіреді және айқын емес тосқауылды синхрондау нүктесін анықтайды.

Берілген мысалда компилятор сыртқы do циклі интерациясын бөледі (j бойынша) және оларды жұмысшы процесстерге кейбір іске асыруға байланысты әдістерге тағайындайды. Тағайындауды басқару үшін программист Schedule сөйлемін қосу керек. OpenMp де тағайындаудың әр түрі бар, соның ішінде блок бойынша, жолақ бойынша (циклдық) және динамикалық (есептер портфелі). Әрбір жұмысшы ағын оған тағайындалған баған бойынша ішкі циклын орындайды.

С++ тілінде паралельдеу директивасы былай болады:

#pragram omp parallel {clause list}

Қолданбалы есептерді шешуде параллель алгоритмдерді қолдану

Берілген тарауда кейбір ғылыми есептер қарастырылады, яғни n-денелер есебі және жылу таралу есебі. Берілген есептерді шешу схемасы басқа да қолданбалы есептерді шешуде қолданылуы мүмкін, мысалы, сұйықтар қозғалысы, зарядталған денелердің өзара әрекеттесуі және т.с.с. Берілген есептерді тиімді шешу алгоритмдері келтірілген.

Мұнда есеп астрономиялық жүйелер терминінде зерттеледі, бірақ бұл әдістер басқа да қосымшаларда қолданылады.

Берілген есеп мақсаты – кеңістіктегі денелер қозғалысы мен орнын табу.

Басқа денелердің гравитациялық күшіне тәуелді.

7. 
   
   жүктеу/скачать 1,94 Mb.
   
   Достарыңызбен бөлісу: