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



Download 2,31 Mb.
Pdf ko'rish
bet62/108
Sana01.03.2022
Hajmi2,31 Mb.
#476325
TuriУчебное пособие
1   ...   58   59   60   61   62   63   64   65   ...   108
Bog'liq
ПАРАЛЛЕЛЬНЫЕ МЕТОДЫ И АЛГОРИТМЫ

 
М
1
 
до 
M
N
. Поэтому на одном процессоре этот алгоритм сводится к 
последовательному двоичному поиску. Значит его стоимость равна 
O(log N),
а время выполнения тоже 
O(log N).
При использовании 
N
процессоров мы возвращаемся к первому 
параллельному варианту со стоимостью 
O(N) 
и временем выполнения 
O(1).
В промежуточных вариантах, для р списков, содержащих 
N / p
элементов 
каждый, время выполнения равно 
O(log(N /p))
, а его стоимость 
O(p log(N /


96 
p)). Если 
р = log N, то log (N / log N) = log N ­ log (log N)

log N.
Время 
выполнения равно 
О(log N)
при стоимости 
О((log N) * (log N)) = О(log2 N).
Порядок времени выполнения параллельного алгоритма совпадает с 
порядком последовательного двоичного поиска, однако константа в оценке 
оказывается меньше, поэтому параллельный алгоритм будет выполняться 
быстрее. Стоимость 
O(log2 N)
превышает стоимость 
O(log N)
оптимального 
последовательного поиска, однако не настолько, чтобы сделать 
параллельный алгоритм бессмысленным. 
10.2. Сортировка на линейных сетях 
 
Начнем с метода сортировки, основанного на линейной конфигурации 
сети. Если число процессоров равно числу сортируемых значений, то сорти
-
ровку можно осуществить, передавая сети в каждом цикле одно значение. 
Первый процессор читает поданное значение, сравнивает его с 
текущим и передает большее значение своему соседу. Остальные процессоры 
делают то же самое: сохраняют меньшее из двух значений и пересылают 
большее следующему звену в цепочке. Получаем следующий алгоритм: 
for i = l to N 
­ 1 
do
занести следующее значение в М[1] 
Parallel Start
P[j] 
читает
M[j] 
в
Current
for k = l to j ­ 1 do 
P[k] читает M[k] в New 
if Current > New then
P[k] 
пишет
Current 
в
M[k + l]
Current = New
else
P[k] 
пишет
New 
в
M[k + l]
end if
end for k
Parallel End


97 
занести следующее значение в М[1] 
Parallel Start
P[j] 
читает
M[j] 
в
Current
for k = l to j ­ 1 do 
P[k] читает M[k] в New 
if Current > New then
P[k] 
пишет
Current 
в
M[k + l]
Current = New
else
P[k] 
пишет
New 
в
M[k + l]
end if
end for k
Parallel End
Parallel Start
for j = l to N ­ 1 do 
P[j] 
пишет
Current 
в
M[j]
end for j
Parallel End
На первых этапах выполнения вычислений первый процессор 
считывает значение элемента списка в переменную 
New
. Далее, в процессе 
работы алгоритма, очередному параллельному проходу предшествует запись 
значения текущего элемента списка, при его наличии, в начальную ячейку 
памяти 
Current
. Процессу соответствует цикл 
for
, который содержит 
параллельные блоки. Первый из этих блоков отвечает за чтение первого 
значения списка, а второй блок –
за сравнение элементов. Элементы 
записываются в память по окончании вычислений.
На рис. 32 а и 32 б [2] представлена работа этого алгоритма на входном
списке 15, 18, 13, 12, 17, 11, 19, 16, 14. 


98 
Шаг А –
происходит запись в память 1
-
го элемента списка, который 
считывается процессором 1. 
Шаг В –
происходит запись в память 2
-
го элемента, который 
сравнивается со значением в процессоре 

Download 2,31 Mb.

Do'stlaringiz bilan baham:
1   ...   58   59   60   61   62   63   64   65   ...   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