автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Методы оптимизации использования внешней памяти ЭВМ на основе её стековой организации

ВВЕДЕШЕ.

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

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

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

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

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

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

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

Выводы.

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

ИЗОБРАЖАЕМЫХ ДЕРЕВЬЯМИ

2.1. Алгоритм нахождения плоской укладки дерева

2.2. Минимизация необходимого объема ВП

2.3. Минимизация общей загруженности памяти

2.4. Минимизация суммарного времени обращения к ВП

2.5. Теорема об универсальном алгоритме

Выводы.

ГЛАВА 3. СТЕКОВАЯ ОРГАНИЗАЦИЯ ПАМЯТИ ПРИ ВЫПОЛНЕНИИ

ПРОИЗВОЛЬНЫХ КОМПЛЕКСОВ ПРОГРАММ

3.1. Алгоритм нахождения плоской укладки произвольного ориентированного графа

3.2. Общие замечания к алгоритмам оптимизации выполнения произвольных комплексов программ

3.3. Минимизация общей загруженности памяти

3.4. Минимизация необходимого объема памяти

3.5. Минимизация суммарного времени обращения к ВП

3.6. Обобщение понятий длины и ширины укладок графов

Выводы.

ГЛАВА 4. КОНЦЕПЦИЯ МУЛЬТИСТЕКОВЫХ ВЫЧИСЛЕНИЙ И СВЯЗАННЫЕ

С НЕЙ ЗАДАЧИ.

4.1. Задача разнесения информации по ВЗУ, на каждом из которых используется стековая память

4.2. Нижняя оценка числа ВЗУ, необходимых для вычислений с использованием стековой памяти

4.3. Оценка количества информационных массивов, которые могут быть помещены на одно ВЗУ, использующее стековую память

4.4. Применение метода ветвей и границ для решения задачи минимального расслоения

4.5. Некоторые случаи точного решения задачи минимального расслоения.

4.5.1. Минимальное расслоение укладки полного графа

4.5.2. Нахождение расслоения укладки графа на два слоя . III

Выводы.

ГЛАВА 5. ЭКСПЕРИМЕНТАЛЬНАЯ ПРОВЕРКА АЛГОРИТМОВ И АНАЛИЗ

РЕЗУЛЬТАТОВ.

5.1. Пример оптимизации расписания выполнения комплекса программ по различным критериям использования памяти

5.2. Результаты работы алгоритмов оптимизации для комплексов, содержащих различное число программ и информационных связей между программами

5.3. Результаты работы алгоритма разнесения промежуточной информации по ВЗУ

Выводы.

Одной из важнейших проблем в области естественных и технических наук, названных в принятых ХШ съездом КПСС "Основных направлениях экономического и социального развития СССР на 19811985 годы и на период до 1990 года", является "совершенствование вычислительной техники, ее элементной базы и математического обеспечения, средств и систем сбора, передачи и обработки информации". Внимание, оказываемое развитию вычислительной техники, не случайно. В настоящее время центр тяжести использования ЭВМ переместился из области научных исследований в область экономики, планирования, управления производством и распределением, т.е. в сферы, непосредственно затрагивающие интересы большинства людей.

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

В настоящей диссертации рассматриваются вопросы, связанные с планированием выполнения работ, обеспечивающем рациональ-, нов использование ресурсов ЭВМ, в основном, внешней памяти (ВП).

Интенсивное использование ВП является одной из основных особенностей организации вычислительного процесса в современных ЭВМ. В этих условиях пропускная способность машины в значительной степени определяется фактическим быстродействием ВП, т.е. средним временем обработки одного запроса к ней.

Если отвлечься от конструктивных особенностей конкретных ЭВМ, то среди факторов, определяющих быстродействие памяти, и в частности ВП, можно отметить следующие наиболее существенные.

1. Оптимальность размещения в ВП информационных массивов.

2. Способ организации обмена информацией между двумя основными уровнями памяти: оперативной памятью (ОП) и ВП.

Рассмотрим эти факторы более подробно.

1. Оптимальным размещением информации является такое, которое обеспечивает минимальные потери времени центрального процессора (ЦП) за счет обращений к ВП. Указанные потери возникают из-за неподготовленности устройства ВП к записи или чтению информации в момент обращения к нему, например, требуется переместить блок головок магнитного диска (МД) на другой цилиндр, перемотать магнитную ленту (МЛ) и т.д.

Самым распространенным и естественным способом устранения этих потерь в современных вычислительных системах является организация мультипрограммной работы ЭВМ, при которой происходит совмещение по времени процессов счета ЦП и подготовки устройств ввода-вывода (в частности, ВП) для работы. Хотя на этом пути достигнуты большие успехи, однако, встречены и трудности принципиального характера, например, возникновение конфликтов при нескольких обращениях к одному внешнему устройству ГI с.162] .

2. Для бесперебойной работы ЦП необходимо, чтобы в ОП постоянно находилась нужная информация, а также имелось свободное место для записи промежуточных результатов. Это требование подразумевает информационный обмен между ОП и ВП. В современных ЭВМ, как правило, используется виртуальная память, т.е. память достаточно большого объема, находящаяся вся якобы в ОП для пользователей. Использование виртуальной памяти создает много удобств, но и требует эффективных алгоритмов замещения информации между уровнями памяти ГI с.68, 2 с.180 J .

Задачи оптимизации размещения информации (ЗОРИ) в ВП, а также разработка алгоритмов замещения информации между уровнями памяти постоянно находятся в сфере актуальных задач для специалистов по организации вычислительных процессов. Как правило, эти задачи достаточно сложны, поэтому для их решения вводят те или иные дополнительные ограничения. Так при решении ЗОРИ на МЛ рассматривают случаи, когда равны между собой все информационные массивы, когда используется лишь одна МЛ, когда вероятности обращения к тому или иному массиву информации не зависят от предыдущих обращений и т.д.С 29,30,31 ] •

При решении ЗОРИ на МД часто исходят из предположения, что известна стационарная частота Р(ь^), с которой происходят запросы сначала к ь -му, а сразу за ним к £ -му массиву информации. При этом предположении представляется возможным применить методы марковских цепей для получения относительно эффективных эвристических алгоритмов размещения [29,32,34] . Аналогичные результаты для ЗОРИ на магнитных барабанах (МБ) приведены в [ 33] .

При разработке и исследовании алгоритмов замещения информации предполагают заданным либо порядок обращения к различным участкам памяти, либо вероятности обращения в каждый момент к той или иной странице, либо выполнение лишь отдельных свойств, присущих реальным процессам, а именно, свойств локальности,редких обращений или рабочего комплекта 1'1 с.80] . Такие допущения приводят к разработке либо точных [ I с.93; 26,27 3 , либо приближенно оптимальных алгоритмов замещения [ I с.112,117; 28] . На практике же из-за невыполнения дополнительных условий разработанные алгоритмы часто оказываются неудовлетворительными.

Необходимо отметить, что задачи,аналогичные вышеперечисленным, ставятся не только на ступени ОП - БП, но и на более быстрой ступени СОП (сверхоперативная память) - ОП. Одним из способов организации работы здесь является применение стековой или магазинной памяти в качестве СОП.

Удобства, получаемые от применения стековой памяти, следующие.

1. Безадресное вычисление арифметических выражений, базируемое на использовании стека при, так называемой, польской бесскобочной записи.

2. Удобства при организации прерываний.

3. Удобства при выполнении рекурсивных обращений.

Принципы стековой организации памяти нашли широкое применение в ряде современных вычислительных систем, таких как kdf-9 ,

Burroughs , Эльбрус, некоторые мини и микро-ЭВМ.

Наряду со многими достоинствами отмечались и недостатки стековой памяти: не всякий вычислительный процесс можно организовать, используя только стековую память, что ведет к усложнению системы команд (наряду со специальными командами работы со стеком используется и традиционная система инструкций); необходимость в некоторых случаях повторно вычислять некоторые части арифметических выражений и некоторые другие недостатки, связанные, в частности, со сложностью пересылки содержимого стека из СОП в ОП при прерываниях Г 2 с.70 ] .

Целью исследования, проведенного в данной работе, является разработка методов, позволяющих распространить принципы стековой организации памяти на новую ступень, а именно, ступень ОП - ВП и получить следующие преимущества.

1. Экономность размещения массивов в памяти. На уровне ОП это ведет к уменьшению эффекта фрагментации [5 с.144] , а на уровне ВП к общему сокращению использованной памяти.

2. Удобство обращения к очередному массиву в ВП. Так,например, при стековой организации ВП считывающе-записывающая головка МЛ всегда находится в конце информационного участка (стека) и готова либо к записи очередного массива, либо к чтению последнего записанного массива.

3. Удобство организации обмена информацией между ОП и ВП. В каждый момент времени ЦП обращается к голове стека, находящейся в ОП. Если при этом стек заполняет почти всю ОП, то его "хвост" можно заблаговременно перемещать в ВП. Аналогично, при уменьшении объема стека в ОП его можно пополнять из ВП. Очевидно, что это можно организовать, не привлекая ЦП.

Цель исследования достигается в работе решением следующих задач.

1. Построением математической модели вычислений, использующих стековую организацию памяти.

2. Описанием класса процессов, допускающих использование стековой памяти при их выполнении на ЭВМ.

3. Разработкой для этого класса алгоритма построения расписания работ, при котором используется стековая память.

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

5. Обоснованием концепции мультистековых вычислений для процессов, не допускающих выполнения с использованием одного стека.

6. Разработкой эффективного алгоритма, находящего для данного процесса способ выполнения, который требует минимальное количество внешних запоминающих устройств (ВЗУ), на каждом из которых используется стековая организация памяти.

В последние годы широкое распространение при исследовании вопросов нахождения оптимальных расписаний выполнения взаимосвязанных работ наряду с традиционными методами теории расписаний получили и методы теории графов и комбинаторного анализа, а именно, методы, базирующиеся на концепции укладки (топологической сортировки) графа. Здесь, прежде всего, следует упомянуть работы Р.Реджеевского [44] , М.А.Шейдвассера [35,37,38] ,А.П.Ершова [36] , М.А.Иорданского [41,42] , Д.Адольфсона и Т.Ху [43] и некоторых других авторов [39,40,45,54,55 ] . На языке теории графов были сформулированы некоторые критерии оптимальности расписаний. В.А.Чебоковым [ 49] было введено понятие плоской укладки графа и предложен способ нахождения плоской укладки невзве-шенного корневого ориентированного дерева минимальной ширины. Однако, не было замечено, что плоские укладки графов могут служить моделью вычислительного процесса, использующего стековую организацию памяти. При такой интерпретации исследование плоских укладок графов находилось в начальной стадии. В первых главах настоящей диссертации этому исследованию применительно к организации вычислительного процесса, оптимального по критериям использования памяти, уделено основное внимание.

В основу решения задачи организации мультистековых вычислений, сформулированной в четвертой главе диссертации, поставлена задача нахождения хроматической раскраски графа пересечений дуг укладки. Концепция графа пересечений для различных геометрических объектов чрезвычайно широко используется во многих прикладных областях теории графов (в радиоэлектронике, биологических, социологических исследованиях и многих других). Это объясняется прогрессом в исследовании графов пересечений, достигнутым благодаря работам Г.Эрлиха, С.Эвена, Р.Е.Тарьяна [ 521 , Т.Каши-вабары [53] , М.Гэри и Д.Джонсона и другихС 56,58 ] . Некоторые результаты относительно графов пересечений дуг в укладке, полученные автором, использованы в настоящей диссертации.

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

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

Алгоритмы, разработанные в диссертационной работе, оформленные в виде пакета прикладных программ, были использованы для улучшения работы комплексов программ в Ярославском транспортном управлении, а также при разработке и использовании математического обеспечения центров коммутации сообщений единой сети связи гражданской авиации. Экономический эффект от их внедрения в Ярославском транспортном управлении составил 14 тыс. рублей в год.

На защиту диссертации, выносятся следующие основные положения.

1. Математическая модель выполнения на ЭВМ комплекса взаимосвязанных программ с использованием стековой памяти для хранения промежуточной информации.

2. Набор алгоритмов, позволяющих организовать выполнение данного комплекса программ на ЭВМ с использованием стековой памяти с минимальным необходимым объемом ВП, минимальной общей загруженностью памяти и максимальной ее экономичностью.

3. Концепция мультистековых вычислений и набор алгоритмов, обеспечивающих мультистековые вычисления оптимальным образом (с минимальным количеством используемых ВЗУ).

Результаты экспериментальной проверки положений и выводов диссертационной работы и их внедрения в работу ВЦ Ярославского транспортного управления и п/я Г-4122.

Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и приложений.

Основные результаты диссертации опубликованы в следующих работах.

1. Булычев С.Ф., Волченков С.Г. Оптимальные плоские укладки деревьев.- В сб.: Эвристические алгоритмы оптимизации.- Ярославль: изд. ЯрГУ, 1978, с.36-68.

2. Маматов Ю.А., Волченков С.Г., Булычев С.Ф. Построение оптимальных расписаний выполнения подпрограмм, минимизирующих суммарный объем обращений к внешней памяти. - Изв. АН СССР. Техническая кибернетика, № 4, 1979, с.213-214.

3. Маматов Ю.А., Волченков С.Г. Плоские укладки графов и стековая организация памяти.- В сб.: Методы и программы решения оптимизационных задач на графах и сетях.- Новосибирск: ВЦ СО АН СССР, 1980, с.157-159.

4. Волченков С.Г. Минимизация суммарного количества обращений к внешней памяти ЭВМ.- Изв. ВУЗов. Приборостроение, № 4, 1981, с.42-45.

5. Волченков С.Г. Нахождение хроматического числа графа пересечений диагоналей правильного И-угольника.- В сб.: Эвристические алгоритмы оптимизации.-Ярославль: изд.ЯрГУ, 1981 ,с.17-19.

6. Волченков С.Г. Организация вычислений, позволяющая использовать стековую память.- Изв. АН СССР. Техническая кибернетика, № I, 1982, 0.148-153.

7. Волченков С.Г., Маматов Ю.А. Плоские укладки графов и стеки.- Ярославль, 1983, 24с. - Деп. в ВИНИТИ АН СССР 22.06.83, № 3367-83.

8. Маматов Ю.А., Волченков С.Г. Построение процедур оптимального поиска информационных массивов.- Автоматика и вычислительная техника. К0. 3, 1981, с.71-72.

9. Волченков С.Г. Алгоритмы нахождения максимальной клики и множества вершинной независимости графа пересечений хорд окружности.- В сб.: Математические методы в исследовании операций. Тезисы Международной конференции. София, 24-29 октября 1983.

10. Волченков С.Г. Оценки необходимого количества запоминающих устройств при использовании стековой памяти.- В сб.: Алгоритмические конструкции и их эффективность.- Ярославль: изд. ЯрГУ, 1983, с.61-67.

11. Волченков С.Г. Алгоритмы для процессоров с мультистеко-вой памятью.- В сб.: Изчислителна техника'83 "Микропроцесорни системи". Резюмета. Пловдив, 17-19 ноября 1983, с.32.

ЗАКЛЮЧЕНИЕ

Диссертация посвящена исследованию вопросов, связанных с оптимизацией вычислительного процесса в ЭВМ по критериям использования памяти. Обоснована целесообразность нахождения расписаний выполнения комплексов программ, при которых используется стековая организация памяти, как оперативной, так и внешней.Разработанная и исследованная в настоящей диссертации методика позволила реализовать конструктивный подход к решению задач оптимального планирования вычислений на основе использования стековой памяти.

Основными результатами работы являются.

1. Построение математической модели процесса вычислений на ЭВМ, использующего стековую память для хранения промежуточной информации.

2. Разработка алгоритмов, позволяющих находить для широкого класса процессов расписания их выполнения, использующие стековую память.

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

4. Обоснование концепции мультистековых вычислений для процессов, не допускающих выполнения с использованием обычной стековой памяти.

5. Разработка алгоритмов, обеспечивающих мультистековые вычисления с минимально необходимым количеством внешних запоминающих устройств.

6. Экспериментальная проверка разработанных методов на широком классе специально построенных моделей вычислительных процессов, а также на реально действующих в АСУ предприятий комплексах программ.

Основные положения работы докладывались и обсуждались на научных семинарах и конференциях Ярославского государственного университета, на Всесоюзном совещании "Методы и программы решения оптимизационных задач на графах и сетях" (г. Новосибирск, 1980 г.) и на Международных конференциях "Математические методы в исследовании операций" ( НРБ, г. София, 1983 г.) и "ВТ'83 Микропроцессорные системы" ( НРБ, г. Пловдив, 1983 г.).

1. Авен 0.И.,Коган Я.А. Управление вычислительным процессом в ЭВМ.- М.: Энергия, 1978, - £40 с.

2. Карцев М.А. Архитектура цифровых вычислительных машин.- М.: Наука, 1978, 296 с.

3. Каган Б.М.,Каневский М.М. Цифровые вычислительные машины и системы.- М.: Энергия, 1970, 679 с.

4. Королев Л.Н. Структуры ЭВМ и их математическое обеспечение.-М.: Наука, IS74, 352 с.

5. Основы теории вычислительных систем./Под ред. Майорова С.А.-М.: Высшая школа, 1978, 408 с.

6. Нечас И. Организация памяти вычислительных машин.- М.: Энергия, 1974, 168 с.

7. Майоров С.А.,Новиков Г.И. Структура цифровых вычислительных машин.- Л.: Машиностроение, 1970, 480 с.

8. Запоминающие устройства современных ЭЦВМ./СБ. статей. Перевод с англ. под ред. А.А.Крупского.- М.: Мир, 1968, 172 с.

9. Танаев B.C.,Шкурба В.В. Введение в теорию расписаний.- М.: Наука, 1975, 256 с.

10. Коньей Р.В.,Максвелл В.л.,шиллер Л.В. Теория расписаний.- М.: г!аука, 1975, 360 с.

11. Харари Ф. Теория графов.- М.: Мир, 1973, 300 с.

12. Ope 0. Теория графов.- М.: Наука, 1980, 336 с.

13. Зыков А.А. Теория конечных графов.- Новосибирск: Наука, 1969,543 с.

14. Майника Э. Алгоритмы оптимизации на сетях и графах.- М.: Мир, 1981, 324 с.

15. Ахо А.Допкрофт Да.,Ульман Дк. Построение и анализ вычислительных алгоритмов.- М.: Мир, 1979, 536 с.

16. Рейнгольд Э.,Нивергельт Ю.,Део Н. Комбинаторные алгоритмы.- М.: Мир, 1980, 476 с.

17. Мелихов А.Н.,Берштейн Л.С.Дурейчик В.М. Применение графов для проектирования дискретных устройств.- М.: Наука, 1974, 304 с.18