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

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 матрицасын баан бойынша блу)