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

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