Содержание к диссертации
ГЛАВА I. ОБЗОР ИССЛЕДОВАНИЙ ПО УПРАВЛЕНИЮ ДВУХУРОВНЕЮЙ
ПАМЯТЬЮ ШЧИСЛИГЕЛЬНЫХ СИСТЕМ ц
IЛ Общее состояние вопроса ц
Алгоритмы замещения Х4
Поведение программ и сравнительный анализ алгоритмов замещения 21
Двухуровневая память в системах управления базами данных 31
Методы улучшения поведения программ 36
Проблема совмещения вычислений и обменов 39
Выводы 42
ГЛАВА 2. РАЗРАБОТКА И РЕАЛИЗАЦИЯ МЕТОДА УПРАВЛЕНИЯ ДВУХУРОВ
НЕВОЙ ПАМЯТЬЮ НА ОСНОВЕ МУЛЬТИПРОЦЕССНОСТИ 45
Квазипараллельная организация вычислительного процесса и управление обменами 45
Мультипроцессный монитор 55
Система управления обменами 52
Совмещение вычислений и обменов в мультипроцессной
системе 72
Выводы 76
ГЛАВА 3. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ УПРАВЛЕНИЯ ДВУХУРОВНЕ
ВОЙ ПАМЯТЬЮ В МУЛЬТИПРОЦЕССНОЙ СИСТЕМЕ 78
Эффективность мультипроцессной системы для модели независимых обращений к внешней памяти 78
Об оптимальной настройке мультипроцессности 89
3.3. Оценка качества функционирования реальных
систем обработки данных . 96
Выводы 104
ГЛАВА 4. ПРИМЕНЕНИЕ МУЛЬТИПРОЦЕССНОСТИ В ЗАДАЧАХ ОБ
РАБОТКИ ДАННЫХ Ю7
Ввод документов в базу данных .. ,,, 107
Поиск в многофайловой базе данных НО
Задача расчета входимости 115
Рекомендации по практическому квазипараллельному программированию задач обработки данных .... 126
Об аппаратной поддержке мультипроцессности ..,«. 127 Выводы 129
ЗАКЛЮЧЕНИЕ 131
ЛИТЕРАТУРА 133
ПРИЛОЖЕНИЕ 141
_ 4 -
Введение к работе
Актуальность темы диссертации. Широкое использование средств вычислительной техники в разнообразных автоматизированных системах управления производством, в системах научно-технической информации и в других крупных интегрированных системах делает актуальной задачу эффективного использования этих средств.
Для современных информационных систем одной из главных проблем является обеспечение возможности работы с очень большими объемами данных. Большой прогресс в технологии обработки данных связан с развитием систем управления базами данных, обеспечивших стандартизацию многих функций хранения и доступа для больших объемов информации [3.45,58]. Тем не менее проблема эффективности решения задач обработки данных, даже при использовании систем управления базами данных, остается крайне важной [2,6,9, 22.26].
Одно из центральных мест в рамках этой проблемы занимает вопрос об организации обменов информацией между внешней и оперативной памятью вычислительной системы в процессе выполнения программ, характеризующихся большим объемом операций ввода-вывода. Эффективное управление обменами предполагает улучшение таких характеристик как общее количество обменов между уровнями памяти - внешней и оперативной, требуемых для решения задачи, а также степень совмещения вычислений и обменов в процессе выполнения программы, что, в конечном итоге, приводит к снижению общего времени выполнения программы в вычислительной системе.
В диссертационной работе разрабатывается подход к управлению двухуровневой памятью, базирующийся на возможности представления программ обработки данных в виде совокупности логически не-
- 5 -зависимых и параллельных программных процессов, которые могут выполняться в однопроцессорной вычислительной системе. Мульти-процессный режим решения задачи открывает принципиально новые возможности для управления обменами между уровнями памяти, используя особенности динамики выполнения квазипараллельной программы.
Несмотря на широкое распространение методов распараллеливания программ в практике системного и прикладного программирования [ 16 , 22,28. 29, 50 3 , в настоящее время отсутствуют работы, посвященные управлению двухуровневой памятью, базирующемуся на внутрипрограммном параллелизме. Разработка такого метода управления и оценки его эффективности необходимы для целенаправленного применения данного подхода для повышения эффективности систем обработки данных.
Цель диссертационной работы состояла в разработке метода
управления двухуровневой памятью вычислительной системы, ориентированного на квазипараллельную организацию вычислительного процесса и исследование эффективности этого метода, а также целесообразности его применения для повышения производительности вычислительной системы.
Методы исследований базируются на использовании теории случайных процессов и имитационного моделирования. Практические вопросы решены путем разработки и реализации рассматриваемых алгоритмов в системе команд ЭВМ EC-I040.
Научная новизна работы заключается в разработке метода управления двухуровневой памятью, ориентированного на мультипроцесс-ный режим выполнения программы, а также в получении оценок эффективности разработанного метода. В частности, получены следующие новые результаты.
- б -
Разработаны и реализованы алгоритмы управления обменами, обладающие возможностью адаптации к характеру ссылочного поведения программ и обеспечивающие совмещение вычислений и обменов в пределах одной программы.
Получена оценка эффективности мультипроцессного управления обменами в предположениях модели независимых обращений программы к блокам внешней памяти, а также оценка эффекта группировки заявок к внешней памяти, за счет которого возможен выигрыш по сравнению с традиционными методами управления обменами.
Предложены рекомендации по оптимальной настройке мульти-процессной системы и показана перспективность мультипроцессного управления обменами в практически важных ситуациях дефицита оперативной памяти.
Практическая ценность работы. Результаты диссертационной работы позволяют научно обоснованно решать важную при создании информационно-поисковых систем задачу проектирования программ, для которых необходима оптимизация обменных процедур с целью обеспечения заданного времени решения задачи. Применение разработанного метода возможно как в системах управления базами данных общего и специального назначения, так и в отдельных прикладных программах, входящих в состав любых программных комплексов, функционирующих под управлением операционной системы ОС ЕС. Разработанный метод может быть использован для расширения функциональных возможностей существующих ЭВМ, а также при разработке новых ЭВМ, в частности, ориентированных на обработку данных.
Достоверность научных положений, выводов и практических рекомендаций подтверждены корректным обоснованием математических моделей рассматриваемых процессов, результатами имитационных и натурных экспериментов, а также результатами практического ис-
пользования разработанного в диссертации метода управления двухуровневой памятью.
Реализация результатов работы. Наиболее полное воплощение полученные в работе теоретические и практические результаты нашли в проекте специализированного процессора мультиобработки, созданного для повышения производительности ЭВМ серии ЕС на задачах "Автоматизированной информационно-справочной системы оперативного планирования перевозок, работы флота и портов, контроля и анализа выполнения планов" (АСУ "Морфлот"). Работа выполнялась специалистами Института проблем управления, Всесоюзного института системных исследований и Института им. М.Пупина по советско-югославскому контракту № 38/81661/30 от 15.02.1980 г.
Программная реализация предложенного метода - мультипроцесс-ный монитор входит в состав системы управления базами данных ИНЕС как инструментальное средство повышения эффективности программ и программных комплексов обработки данных. Соответствующее программное обеспечение передано в централизованный фонд алгоритмов и программ "Центрпрограммсистем".
Результаты диссертационной работы и соответствующие практические рекомендации были использованы при создании программного обеспечения комплекса задач "Сбор и обработка квартальных заявок на перевозку внешнеторговых грузов", входящего в АСУ "Морфлот". В частности, в подсистеме декодирования документов за счет использования метода мультипроцессного управления обменами было достигнуто общее время решения, регламентированное технологическим циклом обработки данных.
Практическое использование результатов диссертационной работы подтверждено соответствующими актами о внедрении.
Апробация работы. Основные результаты диссертационной рабо-
ты были доложены на конференции молодых ученых и специалистов Института проблем управления (Москва, 1976 г., 1-е место), на Конференции молодых ученых и специалистов Всесоюзного научно-исследовательского института системных исследований (Москва, 1979 г., 2-е место), на Второй всесоюзной конференции по банкам данных (Ташкент, 1983 г.). Наряду с этим результаты работы обсуждались на семинарах Института проблем управления, Всесоюзного научно-исследовательского института системных исследований, а также на консультативных встречах советских и югославских специалистов по проекту процессора мультиобработки в соответствии с планом работ по контракту № 38/81661/30.
Публикации и личный вклад автора. Результаты, составляющие основное содержание диссертационной работы, получены автором самостоятельно. Они отражены в следующих печатных работах.
Годунов А.Н., Свердлов С.С. Об организации виртуальной памяти в мультипроцессной системе. - Автоматика и телемеханика, 1978, № 12, с.139-142.
Волков А.Ф., Годунов А,Н., Дагурова Н.В., Емельянов Н.Е., Золотухина Г.М., Макаров В.А., Свердлов С.С. Программная реализация мультипроцессности. - Препринт Института проблем управления, М., 1979.
Годунов А.Н., Свердлов С.С. Алгоритмы замещения страниц виртуальной памяти в мультипроцессной системе. - В сб.: Методы исследования сложных систем, М., ВНИИСИ, 1980, с.46-49.
Годунов А.Н., Емельянов Н.Е., Свердлов С.С. 0 программной реализации мультипроцессности. - Программирование, 1981, № 5, с.44-49.
Асратян Р.Э., Волков А.Ф., Годунов А.Н., Дагурова Н.В., Емельянов Н.Е., Золотухина Г.М., Макаров В.А., Свердлов С.С.
Аппаратная реализация мультипроцессности в ЕС ЭВМ. - Препринт
Института проблем управления, М., 1981. 6. Свердлов С.С. О повышении эффективности доступа к данным в
СУЩ на основе мультипроцессности. - В сб.: Банки данных,
Киев, 1983, с.12-15. В работах, написанных в соавторстве, личным вкладом автора являются: в [1/4] - выбор и реализация системы команд мультипроцессного монитора для работы с внешней памятью, исследование мультипроцессности в натурных экспериментах с задачами обработки данных; в L2.J - алгоритмы управления обменами и их реализация в мультипроцессном мониторе, исследования по эффективности мультипроцессного управления обменами; в L^J - алгоритмы функционирования системных процессов мультипроцессного монитора, управляющих обменами; в L^ J - выбор системы команд процессора мультиобработки, связанных с вводом-выводом, общая методика их аппаратной реализации.
Структура диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения.
