Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683



Download 2,31 Mb.
Pdf ko'rish
bet55/108
Sana01.03.2022
Hajmi2,31 Mb.
#476325
TuriУчебное пособие
1   ...   51   52   53   54   55   56   57   58   ...   108
Bog'liq
ПАРАЛЛЕЛЬНЫЕ МЕТОДЫ И АЛГОРИТМЫ

τ
с 
* n/p.
Укладку кирпича на левой границе 
0
стены 
предваряет вычисление в процессе с номером rank функции, которая 
обеспечивает получение сообщения, поступающего от процесса с номером 
(rank 

1).
Процесс с номером 
(rank 

1) 
отвечает за выполнение функции 
передачи 
необходимых 
данных. 
Двусторонний 
обмен 
данными 
осуществляется между процессом rank и процессом 
rank 

 1
в общем случае. 
Таким образом каждые два соседних процесса обмениваются сообщениями, 
число которых равно двум. Все процессы, не являющиеся первыми и 
последними в цепочке, обмениваются четырьмя сообщениями с соседями. 
Оптимальное время работы составит:
Алгоритм, обеспечивающий это время

for(шаг = 

; шаг 
for(кирпич = rank*n/p; кирпич <(rank+1) * n/p; кирпич ++)
Уложить
(
кирпич

if(rank %2 ) 
{if(rank > 

) Send (rank-1, 
кирпич
уложен

if(rank > 

) Recv (rank-1, 
место
готово
? )
if(rank < p-1) Recv (rank+1, 
место
готово
? ) 
if(rank < p-1) Send (rank+1, 
кирпич
уложен
)

else 

if(rank < p-1) Recv(rank+1, 
место
готово
? ) 
if(rank < p-1) Send(rank+1, 
кирпич
уложен
)
if(rank > 

) Send(rank-1, 
кирпич
уложен

(12)


86 
if(rank > 

) Recv(rank-1, 
место
готово
? )

}
Порядок операций обмена данными в алгоритме представлен на рис. 28 а.
Эффективность
и ускорение алгоритма
Приведенные выше оценки имеют смысл при выполнении следующих 
условий:
-
количество кирпичей для процессов –
одинаково;
-
от положения кирпича в стене не зависит количество операций, 
выполняемых при его укладке;
-
производительности процессов;
-
латентности и пропускные способности каналов передачи данных 
равны.
На практике эти условия выполняются только приближенно в связи с 
наличием процессов, которые при укладке ряда кирпичей выполняют шаги 
за разное время. Примером может служить работа каменщиков на крайних 
участках стены. Если известны трудоемкость укладки каждого кирпича и 
производительность каждого процессора, то при статической балансировке 
можно улучшить показатели следующим образом: предположим, что заранее 
Рис. 28 а. 
Распределения данных аналогично методу геометрического
параллелизма
(13)


87 
известен процесс, выполняющий вычисления медленнее других и время на 
обработку каждого кирпича одинаково. В этом случае, для этого процесса, 
можно уменьшить объем количество кирпичей. Таким образом

удастся 
избежать простоев

и каждый процесс будет затрачивать равное время на 
вычисления. Иначе нагрузка процессоров должна балансироваться 
динамически.

Download 2,31 Mb.

Do'stlaringiz bilan baham:
1   ...   51   52   53   54   55   56   57   58   ...   108




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish