Параллель алгоритмдер өңделу: матрицаны матрицаға көбейту

MPI параллельді бағдарламалау стандарты. МРІ-дағы екі нүктелі және ұжымдық мәліметтер алмасулар.

Екі нүктелі коммуникация

• Екі процесс арасындағы коммуникация.

• Бастапқы процесс мақсатты процесске хабарлама жібереді.

• Коммуникация коммуникатор ішінде атқарылады.

4. Процесстер коммуникатордағы рангдары бойынша анықталады.

Хабарлама жіберу

Хабарламаны қабылдау

Ұжымдық операциялар

MPI_.......…v (Gatherv, Scatterv, Allgatherv, Alltoallv)

Екі нүктелі коммуникациялардың талаптары

Коммуникация сәтті болу үшін:

• Жіберуші міндетті түрде жарамды мақсатты рангты нұсқау тиіс.

• Қабылдаушы міндетті түрде жарамды бастапқы рангты нұсқауы керек.

• Коммуникатор бірдей болуы тиіс.

• Тегтер міндетті түрде сәйкес керу керек.

• Хабарламалардың деректер үлгілері міндетті түрде сәйкес келу керек.

• Қабылдаушының буфері міндетті түрде жеткілікті үлкен болуы тиіс.

32. MPI-да ұжымдық мәліметтер алмасудың түрлері, сәйкесінше қолданатын MPI функциялары Ұжымдық коммуникациялар

• Процестер тобын біріктіретін байланыс

• Коммуникатордағы барлық процестермен шақырылады

• Мысалдар:

- Барьерді синхронизациялау

- Трансляция, шашу, жинақтау

- Глобалдық қосынды, глобалдық максимум, т.б.

Трансляция

Шашу

Жинақтау

 

 

33. Параллель алгоритмдер өңделу: матрицаны векторға көбейту.

M × n өлшемді А матрицасымен n элементтен тұратын b векторының көбейтіндісінен m өлшемді с векторын аламыз.

Матрица мен векторды көбейту есебінің тізбекті алгоритмі

Матрица-векторлық көбейту –бұл скалярлық туындының есептелуінің тізбектілігі болып табылады. N ұзындықты вектордың скалярлы туындысының әрбірінің есептелуі көбейтудің n операциясын және n-1 қосу операциясын есептеуді талап етеді. Матрица-векторлық көбейтудің орындалуы үшін скалярлы туындыны есептеудін m операциясын жүзеге асыру қажет.

Параллелді бөліп берудің принциптері

Барлық матрицалық есептеулерге тән мінездеме- ол матрицаның әр түрлі элементтері үшін бір есептеу іс-әрекеті қайталанып жүреді.

Матрицаны бөлудің ең кең қолданылатын әдістері деректерді жолға бөлу (вертикаль немесе горизонталь) немесе тіктөртбұрышты фрагментке бөлу (блоктар) тұрады.

Деректерді жолға бөлу арқылы матрицаны векторға көбейту

 

Параллель алгоритмдер өңделу: матрицаны матрицаға көбейту

Декомпозиция – үлкен көлемді есептің шешімін табу үшін оны кішкене бөліктерге бөлу арқылы есептің шешімін табудың ғылыми әдісі.Бірөлшемді декомпозиция әдісі немесе матрицаларды блокты түрде көбейту деп те аталады.Бұл әдісте бастапқы А, В матрицалары және көбейдінді нәтижесі болатын С матрицалары блоктар жиыны ретінде қаралады. Барлық матрицалар n*n өлшемді және горизонтальды және вертикальды бөлінген блоктар саны бірдей q деп қарастырылады. Сонымен қоса барлық блоктар k*k өлшемді,

k = n/q деп алынады. Осыдан кейін А және В матрицаларының блокты түрдегі көбейтіндісі төмендегідей түрде болады:

Пайда болған С матрицасының әрбір элементі келесідей түрдегі қосындымен анықталады:

Матрицаларды көбейтудің блокты әдісінің негізінде әрбір сәйкес көбейтілетін блоктарға қарапайым матрицаларды көбейту алгоритімі қолданылады. Мысалы 2х2 өлшемді матрицаларды көбейту формуласы төмендегідей:

Осы формуланы біле отырып 4х4 өлшемді матрицаларды блоктарға бөліп көбейтуге болады. Мысал ретінде 4х4 өлшемді төмендегі қарастырайық.

Мұндағы әрбір матрицаны 2х2 өлшемді 4 кішкене матрицаларға бөлуге болады:

Енді бұл блоктарды 2х2 өлшемді матрицаларды көбейту формуласымен көбейтеміз. 1-ші блок үшін элементі:

Матрицаларды көбейту:

Немесе

 

Тізбектелген алгоритм

q Алгоритм С матрицасының жолдарын тізбектелген түрде есептейді.

q i айнымалысы бойынша циклдің бір итерациясында A матрицасының бірінші жолы мен B матрицасының барлық бағандары қолданылады.

 

Скалярлық көбейтуді есептеу операциялар саны m·n болатын матрица-векторлық көбейту орындалады.

O(mnl) ретті есептеу уақыты болады.

Параллелді алгоритм 1: жол схемасы бойынша…

• Негізгі ішкі есеп (агрегация) – С матрицасының қандайда бір жолының барлық элементтерін есептеу процедурасы. (процестер саны size)

• Мәліметтерді тарату – жол схемасы (A матрицасын жол бойынша, ал B матрицасын баған бойынша бөлу)