|
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 минут. Данный результат явился следствием небрежного использования
программистами медленной памяти.
Do'stlaringiz bilan baham: | 
