Лекция. Фурье түрлендіруі және Фурье алгоритмі

• 
  Жылдам әрекеттесуші фортран (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 директивасын қолдануы мүмкін, В-дағы жанама әсердің жоқ екендігін хабарлайды.