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


Глава 8.  Базовые методы построения параллельных алгоритмов



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

Глава 8. 
Базовые методы построения параллельных алгоритмов: 
метод сдваивания, геометрический параллелизм
 
8.1. 
Базовые методы построения параллельных алгоритмов
 
Параллельные алгоритмы не всегда показывают более высокую, чем 
последовательные алгоритмы, степень эффективности. Несмотря на это 
имеется достаточно большой набор задач, решение которых возможно 
улучшить за счет применения параллельных вычислений. 
Правильность этих методов подтверждена многолетней практикой и 
дает возможность обеспечивать
их применимость для решения самых разных 
задач. Рассмотрим последовательно следующие методы:

метод сдваивания;

метод геометрического параллелизма;
 
Пример
. Определение суммы элементов массива a, содержащего n 
элементов [2]. На рис. 26 приведен пример нахождения суммы 8
-
ми 
элементов массива, используя 4 процессора.
Рис. 26. Нахождения суммы 8
-
ми элементов массива чисел на четырех процессорах 
методом сдваивания


79 
Последовательный алгоритм:
 
s=a[1]; 
for(i=2;i<=n;i++) 
s=s+a[i]; 
Будем учитывать только операции сложения чисел, пренебрегая 
операциями, связанными с организацией цикла суммирования, чтением 
элементов массива из памяти и им подобными. Данные операции не важны с 
точки зрения оценки свойств рассматриваемого метода.
Пусть 
τ
А

время выполнения операции сложения двух чисел; 
T
1

время 
работы последовательного алгоритма, тогда: 
Степень параллелизма алгоритма равна 1. 
8.2. Построение параллельного алгоритма методом сдваивания
 
Предположим, что размер массива составляет n = 2
q

В этом случае
количество этапов выполнения алгоритма сдваивания составит q = log
2
n: 
1-
й этап 

n/2 действий, 
2-
й этап 
- n/4, 

q-
й –
1. 
Пусть k –
некоторый этап выполнения алгоритма. Тогда степень 
параллелизма на этом этапе составит n/2
k
. Ускорение 
S
p
параллельного 
алгоритма по сравнению с наилучшим последовательным, достигаемое в 
системе из p процессоров, при p = n/2:
где 


доля операций алгоритма, выполнение которых невозможно 
одновременно с другими операциями (операции со степенью параллелизма 
1); E


сверхлинейное ускорение, которое превышает вычислительные 
возможности системы (число процессов для решения вычислительной 
(1)
(2)


80 
задачи) 
S
p
> p
. Причины появления сверхлинейного ускорения –
особенности, используемых вычислительных систем, неудачный выбор 
последовательного алгоритма
Метод обеспечивает высокое ускорение и низкую эффективность. При 
n
= 1024 ускорение равно 102, эффективность ‒
20%. Причина низкой 
эффективности в простаивании большей части процессоров на всех стадиях. 
Так как вычисления выполняются на всех стадиях только на первом 
процессоре. Алгоритм предполагает
использование 
n/2
процессоров для 
обработки n элементов. Разобьем массив
, состоящий из n на p одинаковых 
частей. При условии уменьшения количества процессоров, вычисления в 
каждой части будут выполняться двумя этапами на отдельном процессоре:

Download 2,31 Mb.

Do'stlaringiz bilan baham:
1   ...   47   48   49   50   51   52   53   54   ...   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