Вводные замечания


Вариант с разбиением суммирований по столбцам, последовательно-иерархический



Download 122,25 Kb.
bet2/4
Sana21.02.2022
Hajmi122,25 Kb.
#66825
TuriЗадача
1   2   3   4
Bog'liq
Задание №1(1-u)

Вариант с разбиением суммирований по столбцам, последовательно-иерархический


В этом варианте для каждого из столбцов сумма накапливается отдельно, а потом эти полученные частные суммы прибавляются к общему "накопителю". На Фортране 77 соответствующая подпрограмма-функция будет выглядеть так:
real function COLSUM(A,N,M)
real A(N,M), S, R
S = 0.
Do 20 J = 1,M
R = 0.
Do 10 I = 1,N
R = R + A(I,J)
10 continue
S = S+R
20 continue
COLSUM=S
return
end


И синими, и зелёными обозначены элементарные операции сложения чисел. В даном графе алгоритма, как и ранее, мы опустили передачи начальных данных и инициализации временных переменных. Как видно, общее количество элементарных операций увеличилось на M, но при этом критический путь 1 графа уменьшился до N+M+2, так что вполне возможны параллельные реализации. Например, можно реализовать параллельно внутренний цикл в представленной функции. Не следует, однако, забывать, что тогда мало будет одной накопительной переменной R на все циклы, и надо будет её размножить в массив.

Пирамиды и каскадные схемы


Последовательные ветви (как в двух полностью последовательных вариантах, так и в последовательно-иерархическом) могут быть заменены на пирамиду. Наибольшую быстроту при таком распараллеливании даёт пирамида сдваиванием. Её, однако, редко записывают на последовательных языках, поскольку применяется-то сдваивание для распараллеливания.Если всё же записывают, то чаще с помощью рекурсивных вызовов, что не очень удобно для анализа графа. Причина - в том, что промежуточные результаты при нерекурсивной реализации надо хранить, и для этого нуже массив всего вдвое меньший, чем суммируемый. Рассмотрим подпрограмму пирамидного суммирования одномерного массива на Фортране 77 (простенький вариант для N, являющегося степенью двойки):
real function PIRSUM(A,B,N, L)
C L=logN
real A(N), B(N/2)
do 10 I=1,N/2
B(I) = A(2*I-1)+A(2*I)
10 continue
do 20 J = 1, L-1
do 20 I=1,N/2,2**J
B(I)=B(I)+B(I+2**(J-1))
20 continue
PIRSUM=B(1)
return
end
Дадим её схему для суммирования 8 элементов на рисунке:

Здесь, как и ранее, синим цветом обозначены элементарные сложения, а чёрными стрелками - дуги графа алгоритма. Красным обозначены начальные данные (элементы массива) и их передача соответствующим вершинам графа алгоритма. Что хорошо в пирамиде сдваивания, это то, что в ней нет лишних элементарных сложений, и при этом имено она даёт минимальный критический путь 1 графа алгоритма.
Теперь рассмотрим рекурсивный вариант программы (на Си), но уже для произвольного N:
double PIRSUM(a,N)
double *a;
int N;
{
double s; int i,j;
 if (N<=0) {
s=0.;
return s;
 }else if (N==1) {
s=*a;
return s;
 }else{
i=N/2; j=N-i;
s=PIRSUM(a,i)+PIRSUM(a+i,j);
return s;
 }
}

Её схема при равных N аналогична схеме предыдущей подпрограммы. Однако, при использовании такой схемы для гигантских N рекурсия всё же нежелательна, поскольку при большой глубине вызовов подпрограмм может переполниться стек, который часто используют для хранения параметров вызова во многих трансляторах.


Сложные каскадные схемы суммирования прямоугольного массива предполагают замену такой вот пирамидой последовательных участков (как синих, так и зелёных) предыдущей иерархически-последовательной схемы.
1Критическим путём в ациклическом ориентированном графе (коим является граф алгоритма) называется самый длинный из путей. Здесь мы считаем его по количеству 
Download 122,25 Kb.

Do'stlaringiz bilan baham:
1   2   3   4




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