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


В сетях сортировки актуальна задача минимизации времени



Download 5,19 Mb.
Pdf ko'rish
bet81/101
Sana16.10.2022
Hajmi5,19 Mb.
#853454
TuriУчебное пособие
1   ...   77   78   79   80   81   82   83   84   ...   101
Bog'liq
fel20E533

В сетях сортировки актуальна задача минимизации времени 
работы. Для значений n <= 10 известны сети, обладающие минимально 
возможным временем. Для шести процессоров известна сеть 
сортировки, выполняющаяся всего за 5 шагов (рис. 51). 
 
Рис. 50. Одновременное выполнение на шаге 5 компараторов (1, 2), (3, 4) и (5, 6) 
Рис. 51. Сеть сортировки для шести процессоров 


141 
 
Глава 
14. 
Технологии 
параллельного 
программирования: 
использование традиционных последовательных 
языков 
 
14.1. Принципы анализа параллельных алгоритмов 
При проведении анализа параллельных алгоритмов
 
рассматриваются 
две характеристики ‒ коэффициент ускорения и стоимость. 
Коэффициент 
ускорения
характеризует скорость работы параллельного алгоритма 
относительно 
наилучшего 
последовательного 
алгоритма. 
Для 
последовательного алгоритма сортировки необходимо O(N log N) операций. 
Для параллельного алгоритма сортировки (сложность O(N)) составит O(log 
N). 
Стоимость
вычисляется как произведение сложности алгоритма и 
количества необходимых для вычисления процессоров. Так для 
параллельного алгоритма сортировки O(N), при количестве процессоров 
равном числу входных записей, стоимость составит O(N
2
). То есть по
сравнению с алгоритмом последовательной сортировки, стоимость которого 
составляет O(N log N), параллельный алгоритм обладает большей 
стоимостью. Для того чтобы параллельный алгоритм сортировки имел 
смысл, число используемых процессоров не должно меняется при росте 
длины входных данных, и быть в значительной степени меньше 
предполагаемого объема входных данных

Download 5,19 Mb.

Do'stlaringiz bilan baham:
1   ...   77   78   79   80   81   82   83   84   ...   101




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