Фурье түрлендіруі және Фурье алгоритмі

Тезәрекеттесуші Фортран -бұл Фортанға негізделген тілдердің жаңа өкілі. HPF-тің бірінші нұсқадан 1992 жылы университет, өндіріс және үкімет лабораториясындағы көптеген топтар жасаған.

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

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

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

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

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

Do iter=16MAXITERS

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-ке көшіріледі. Шындығында бұл цикл денесі былай программалауға болады.

Grid(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

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

doi=1, n

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

Enddo

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

6.6. OpenMp

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

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 end parallel do

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

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

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

#pragram omp parallel {clause list}

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

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

7.1 N-денелердің гравитациялық есебі.

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

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

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

 Ньютон физикасының заңына тәуелді.

N-денелердің гравитациялық есебінде қолданылатын формулалар

Екі дене арасындағы гравитациялық күш:

Ньютонның екінші заңы бойынша: