Методы оптимизации использования внешней памяти ЭВМ на основе её стековой организации

• Автор: Волченков, Сергей Геннадьевич
• Шифр специальности: 05.13.13
• Научная степень: Кандидатская
• Год защиты: 1983
• Место защиты: Ярославль
• Количество страниц: 168 c. : ил

ГЛАВА I. МОДЕЛЬ ПРОЦЕССА ВЫЧИСЛЕНИЙ, ИСПОЛЬЗУЮЩЕГО

СТЕКОВУЮ ПАМЯТЬ

Использование памяти ЭВМ при различных расписаниях выполнения комплексов

программ

Преимущества стековой организации памяти для хранения промежуточной информации

. .

Основные определения и обозначения

Особенности расписаний выполнения комплексов программ, изображаемых деревьями

Свойства расписаний выполнения произвольных комплексов программ

Выводы

ГЛАВА 2. СТЕКОВАЯ ОРГАНИЗАЦИЯ ПАМЯТИ ПРИ ВЫЧИСЛЕНИЯХ,

ИЗОБРАЖАЕМЫХ ДЕРЕВЬЯМИ
Алгоритм нахождения плоской укладки дерева . .
Минимизация необходимого объема ВП
Минимизация общей загруженности памяти
Минимизация суммарного времени обращения к ВП .
Теорема об универсальном алгоритме
Выводы
ГЛАВА 3. СТЕКОВАЯ ОРГАНИЗАЦИЯ ПАМЯТИ ПРИ ВЫПОЛНЕНИИ
ПРОИЗВОЛЬНЫХ КОМПЛЕКСОВ ПРОГРАММ .
Алгоритм нахождения плоской укладки произвольного ориентированного графа
Общие замечания к алгоритмам оптимизации выполнения произвольных комплексов
программ .
Минимизация общей загруженности памяти
Минимизация необходимого объема памяти
Минимизация суммарного времени обращения к ВП .
Обобщение понятий длины и ширины укладок графов .
Выводы
ГЛАВА 4. КОНЦЕПЦИЯ МУЛЬТИСТЕКОВЫХ ВЫЧИСЛЕНИЙ И СВЯЗАННЫЕ
С НЕЙ ЗАДАЧИ
Задача разнесения информации по ВЗУ, на каждом
из которых используется стековая память
Нижняя оценка числа ВЗУ, необходимых для вычислений с использованием стековой
памяти
Оценка количества информационных массивов, которые могут быть помещены на одно
ВЗУ, использующее стековую память 2
Применение метода ветвей и границ для решения
задачи минимального расслоения
Некоторые случаи точного решения задачи минимального расслоения
Минимальное расслоение укладки полного графа . .
Нахождение расслоения укладки графа на два слоя . III
Выводы
ГЛАВА 5. ЭКСПЕРИМЕНТАЛЬНАЯ ПРОВЕРКА АЛГОРИТМОВ И АНАЛИЗ
РЕЗУЛЬТАТОВ
Пример оптимизации расписания выполнения комплекса программ по различным
критериям использования памяти 4
Результаты работы алгоритмов оптимизации для комплексов, содержащих различное
число программ и информационных связей между программами 6
Результаты работы алгоритма разнесения промежуточной информации по ВЗУ
Выводы
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


ГЛАВА I. ГЛАВА 2. Алгоритм нахождения плоской укладки дерева . Минимизация суммарного времени обращения к ВП . ГЛАВА 3. ПРОИЗВОЛЬНЫХ КОМПЛЕКСОВ ПРОГРАММ . Минимизация суммарного времени обращения к ВП . Обобщение понятий длины и ширины укладок графов . ГЛАВА 4. Минимальное расслоение укладки полного графа . Нахождение расслоения укладки графа на два слоя . ГЛАВА 5. ПРИЛОЖЕНИЕ А. ПРИЛОЖЕНИЕ I. ПРИЛОЖЕНИЕ 3. ВП. ЭВМ. Оптимальность размещения в ВП информационных массивов. ОП и ВП. Рассмотрим эти факторы более подробно. ВП. МЛ и т. ВП для работы. ГI с. Это требование подразумевает информационный обмен между ОП и ВП. В современных ЭВМ, как правило, используется виртуальная память, т. ОП для пользователей. СI с. Г,, . ЗОРИ на магнитных барабанах ЫБ приведены в 3 . II с. I с. I с. ОП. ООП. Удобства, получаемые от применения стековой памяти, сле дующие. Удобства при организации прерываний. Удобства при выполнении рекурсивных обращений. Эльбрус, некоторые мини и микроЭВМ. СОП в ОП при прерываниях 2 с. ОП ВП и получить следующие преимущества. Экономность размещения массивов в памяти. Удобство обращения к очередному массиву в ВП. Удобство организации обмена информацией между ОП и ВП. В каждый момент времени ЦП обращается к голове стека, находящейся в ОП. ВП. ВП. Очевидно, что это можно организовать, не привлекая ЦП. Цель исследования достигается в работе решением следующих задач. ЭВМ. Здесь, прежде всего, следует упомянуть работы Р. М.А. Шейдвассера ,, ,А. П.Ершова , М. Д.Адольфсона и Т. Ху и некоторых других авторов ,,,, . В.А. Г.Эрлиха, С. Эвена, Р. Е.Тарьяна , Т. М.Гэри и Д. Джонсона и другихС , 1. АСУ. На защиту диссертации выносятся следующие основные положения. ВЗУ. ОП, так и в ВП. В главе 2 строится алгоритм, находящий для комплекса прог . ВЗУ. Список использованной литературы содержит названий. Описывается математическая модель процесса вычислений.