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



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

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


Неискушённый в параллельном программировании читатель может быть удивлён тем, насколько простая задача выбрана для разбора.
Однако, во-первых, уже те студенты, что изучали математические основы распараллеливания на самом простом уровне, знают, что задача суммирования элементов массива является прекрасной моделью для распространения приёмов, используемых на ней, на другие, более сложные задачи. Ассоциативность операции скалярного сложения, позволяющая нам при конструировании алгоритма суммирования использовать различный порядок для получения ускорения, является общим свойством также и многих других операций (скалярного умножения, матричных сложения и умножения), что позволяет распараллеливать, казалось бы, такие нераспараллеливаемые последовательные методы, как схемы Горнера и прогонки. Поэтому если мы научимся эффективно суммировать массивы, то этим также сделаем большой шаг к эффективной реализации на этой вычислительной архитектуре и более сложных методов.
Во-вторых, не надо забывать о том, что специфические для различных архитектур задачи, возникающие при адаптации программ к этой архитектуре, удобнее всего рассмотреть именно на примере простых программ. А даже для простой программы важно прежде всего знать её теоретические основы.

Математика задачи и общеизвестные варианты её решения


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

Последовательный вариант


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

переставить местами циклы и получить последовательное суммирование по столбцам:
real function SEQSUM(A,N,M)
real A(N,M), S
S = 0.
Do 10 J = 1,M
Do 10 I = 1,N
S = S + A(I,J)
10 continue
SEQSUM=S
return
end


Ясно, что в обоих случаях ни о каком параллелизме речи быть не может. Критический путь 1 графа будет равен NM+1 (на графе не показано первоначальное присвоение нуля переменной S).


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