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



Download 2,31 Mb.
Pdf ko'rish
bet18/108
Sana01.03.2022
Hajmi2,31 Mb.
#476325
TuriУчебное пособие
1   ...   14   15   16   17   18   19   20   21   ...   108
Bog'liq
ПАРАЛЛЕЛЬНЫЕ МЕТОДЫ И АЛГОРИТМЫ

1.
 
Задачи, при решении которых используется только 
оперативная память 
 
Компьютеры особенно быстро осуществляют доступ к словам с 
последовательными физическими адресами. Пусть, например, программа 
составляется на языке Фортран. В пределах этого языка нет разницы в 
обработке элементов массивов по строкам или столбцам. В первом случае 
осуществляется преобразование элементов матриц. Во втором случае 

элементов, транспонированных к ним. Массивы в Фортране располагаются в 
физической памяти последовательно по адресам; столбцы располагаются 
друг за другом. В случае алгоритм решения систем линейных алгебраических 
уравнений методом Гаусса, время работы программы будет определяться ее 
трехмерными циклами. Внутренние циклы программ могут осуществлять 
обработку, как уже упоминалось выше, по строкам и столбцам. В 
зависимости от того, расположена матрица системы в массиве по столбцам 
или строкам, внутренние циклы программы осуществляют обработку 


23 
элементов массивов по столбцам или строкам. Время реализации для этих 
двух случаев может значительно отличаться.
2.
Задачи, при решении которых используется медленная 
память
Увеличение объема памяти вызывает необходимость задействовать, 
наряду с оперативной, медленную память, которая часто реализуется на 
жестких дисках. Объемы информации, необходимые при решении больших 
задач, требуют хранения большей ее части в медленной памяти. С учетом 
того, что операции выполняются только в оперативной памяти, необходим 
многократный обмен данными между оперативной и медленной памятью. 
Таким образом, время решения задачи складывается из времени выполнения 
операций алгоритма и времени осуществления обменов между медленной и 
оперативной памятью. При неудачной организации обменов время обменов 
может превысить время выполнения операций алгоритма в тысячи раз. 
Организация обменов между медленной и быстрой памятью должна 
осуществляется с учетом следующих требований:

осуществление минимально возможного числа обращений к 
медленной памяти;
-
осуществление переноса максимально возможного количества 
данных за обмен;
-
достижение максимально возможного времени обработки данных 
при переносе в быструю память.
Для реализации обмена, с учетом этих требований, можно 
использовать виртуальную память, которая либо однородна, либо имеет 
некоторую структуру. В последнем случае для памяти разрабатывается 
система правил предпочтительного размещения данных. Универсальные 
алгоритмы, реализующие память практически не учитывают особенности 
конкретных программ.
Для проверки организации обменов существует следующая методика:


24 
-
определить пример, отражающий существо решаемой большой 
задачи;
-
замерить в
монопольном режиме астрономическое время 
реализации примера на компьютере;
-
подсчитать время выполнения необходимых операций;
-
найти отношение величин времени реализации примера и 
времени выполнения необходимых операций; 
-
провести анализ полученных
величин; если первая величина 
отличается от второй не более чем в несколько раз, то для
рассматриваемого 
класса задач организация обмена является удовлетворительной, иначе –
обмен следует организовывать самостоятельно. Существуют задачи, для 
которых нельзя минимизировать время обменов с медленной памятью.
Пример 
[1, с. 44]
В середине 60
-
х годов прошлого столетия в нашей стране были широко 
распространены вычислительные машины типа М
-
20, построенные 
коллективом, возглавляемым академиком С. А. Лебедевым. По тем временам 
это 
были 
вполне 
современные 
компьютеры, 
обладающие 
производительностью около 20 тыс. операций в секунду. Оперативная память 
машин этого типа была малой и позволяла решать системы линейных 
алгебраических уравнений с плотной матрицей порядка всего лишь 50—
100. 
Требования практики заставляли искать способы решения систем 
значительно большего порядка. В качестве медленной памяти на этих 
машинах использовались магнитные барабаны. Они играли тогда такую же 
роль, какую сейчас в персональном компьютере играют жесткие диски. 
Естественно, с поправкой на объем хранимой информации. Под этот тип 
медленной памяти была разработана специальная блочная технология 
решения больших алгебраических задач. Она позволяла с использованием 
только 300 слов оперативной памяти решать системы практически любого 
порядка. Точнее, такого порядка, при котором матрица и правая часть могли 
целиком разместиться в медленной памяти. При этом системы решались 


25 
почти столь же быстро, как будто вся информация о них на самом деле была 
размещена в оперативной памяти. Созданные на основе данной технологии 
программы были весьма эффективны. В частности, на машинах типа М
-20 
они позволяли решать системы 200
-
го порядка всего за 9 минут.
В конце 60
-
х годов прошлого столетия появилась машина БЭСМ
-6. 
Это 
была одна из лучших вычислительных машин в Европе. Она обладала 
производительностью около одного миллиона операций в секунду, т. е. была 
быстрее машин типа М
-
20 примерно в 50 раз. Разработана БЭСМ
-
6 была 
коллективом под руководством академика С. А. Лебедева, его заместителей 
В. А. Мельникова и Л. Н. Королева. Среди математического обеспечения 
машин БЭСМ
-
6 были и стандартные программы для решения системы 
линейных алгебраических уравнений большого порядка с использованием 
медленной памяти. Ожидалось, что
с их помощью можно решать большие 
системы, если и не в 50, то хотя бы в несколько раз быстрее. Однако опытная 
проверка дала удивительные результаты. Система 200
-
го порядка решалась 
за 20 минут. Данный результат явился следствием небрежного использования 
программистами медленной памяти. 

Download 2,31 Mb.

Do'stlaringiz bilan baham:
1   ...   14   15   16   17   18   19   20   21   ...   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