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: 
