Содержание к диссертации
ВВЕДЕНИЕ. ПРОБЛЕМЫ ПЛАНИРОВАНИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ
ПРОЦЕССОВ И ОТЛАДКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ 4
Глава I. ПОСТАНОВКА ЗАДАЧИ ВЫБОРА СТРУКТУРЫ МУЛЬТИМИКРО ПРОЦЕССОРНОЙ СИСТЕМЫ С РАЗДЕЛЕНИЕМ ФУНКЦИЙ 14
1.1. Выбор множества допустимых конфигураций мульими кропроцессорных систем с разделением функций 14
1.2. Определение понятия структуры мультипроцессорной системы и степени связанности сложной задачи
1.3. Анализ взаимосвязи времени решения сложной задачи, стоимости мультипроцессорной системы и организации выполнения сложной задачи 26
1.4. Постановка задачи выборе структуры и определение метода ее решения 33
1.5. Выводы к первой главе 3?
Глава II. СОСТАВЛЕНИЕ ОПТИМАЛЬНОГО РАСПИСАНИЯ ВЫПОЛНЕНИЯ
СИЛЬНОСВЯЗАННОЙ СЛОЖНОЙ ЗАДАЧИ 38
2.1. Анализ взаимодействия сложных задач 38
2.2. Совмещение операций обмена и графическое описание ,сложной задачи 41
2.3. Модель задачи составления расписания 50
2.4. Аналитическая модель простой задачи 56
2.5. Постановка и решение задачи составления оптимального расписания 64
2.6. Выводы ко второй главе 69
Глава III. СОСТАВЛЕНИЕ ЛОКАЛЬНО-ОПТИМАЛЬНОГО РАСПИСАНИЯ ВЫ
ПОЛНЕНИЯ ШЬНОСВЯЗАННОЙ СЛОЖНОЙ ЗАДАЧИ 70
3.1. Оценка эффективности локально-оптимального расписания
3.2. Постановка и решение задачи составления локально-оптимального расписания 85
3.3. Инженерная методика выбора структуры мультипроцессорной системы с разделением функций 91
3.4. Выводы к третьей главе 95
Глава ІV. РАЗРАБОТКА СТРУКТУРЫ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ СПЕ
ЦИАЛИЗИРОВАННОЙ МУЛЬТИМИКРОПРОЦЕССОРНОЙ СИСТЕМЫ И
СРЕДСТВ ЕГО ОТЛАДКИ 96
4.1. Структура программного обеспечения мулътимикропро-цессорных систем с разделением функций 97
4.2. Методы диспетчирования и состав системного программного обеспечения 101
4.3. Отладка мультипроцессорных систем с разделением функций 108
4.4. Средства отладки проблемного программного обеспечения 114
4.5. Выводы к четвертой главе » 122
Глава V. ВЫБОР СТРУКТУРЫ И ОТЛАДКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ СИСТЕМЫ УПРАВЛЕНИЯ ОПТИЧЕСКОЙ СТАНЦИЕЙ 123
5 1« Технические средства оптической станции 123
5.2. Выбор структуры мультипроцессорной системы управления 126
5.3. Отладка программного обеспечения системы управления 133
5.4. Выводы к пятой главе 136
ВЫВОДЫ 137
ЗАКЛЮЧЕНИЕ 139
СПИСОК ЛИТЕРАТУРЫ 141
ПРИЛОЖЕНИЕ
Введение к работе
В принятых на ХХУІ съезде КПСС "Основных направлениях экономического и социального развития СССР на I98I-I985 гг, и на период до 1990 года" указано:Опережающими темпвми развивать производство быстродействующих управляющих и вычислительных комплексов, периферийного оборудования и программных средств к ним..,". Достижение этой цели требует решения целого ряда проблем в области проектирования ЭВМ и, в честности, проблем проектирования специализированных вычислительных систем, ориентированных на решение фиксированного набора задач.
Актуальность проблемы Данная работа посвящена вопросам выбора структуры специализированных мультимикропроцессорных систем, ориентированных на решение совокупности задач с большим объемом информационного обмена, разработке структуры программного обеспечения и средств его отладки.
Актуальность этой проблемы обусловлена следующими причинами:
I. Повышение производительности вычислительных систем осуществляется в двух направлениях: совершенствованием элементной базы и структурными методами. Первое направление связано с развитием, разработкой и внедрением элементов, построенных на базе новейших достижений в области технологии и физики полупроводников, обладающих более высоким физическим быстродействием. Второе направление связано с разработкой и исследованием новых методов структурной организации параллельных вычислительных систем и планирования параллельных вычислительных процессов на основе более полного использования возможностей существующей элементной базы. Поскольку дальнейшее совершенствование элементной базы ограничено причинами физического характера, то направление, связанное с разработкой структурных методов повышения производительности, становится наиболее важным. В рамках этого направления основное значение имеет разработка мультипроцессорных систем. В связи с этим особую актуальность приобретает проблема эффективного проектирования специализированных мультипроцессорных систем.
2. Появление дешевых и надежных микропроцессоров сделало технически и экономически выгодным построение мультимикропроцес-сорных управляюще-вычислительных систем. Программирование для микропроцессорных специализированных управляюще-вычислительных си-стем выдвинуло целый ряд сложных задач, вязанных с планированием выполнения параллельных программ и разработкой средств их отлад-ки. Поэтому проблема комплексного решения задач: выбора структуры мультипроцессорной системы,оптимально соответствующей решаемой управляюще-вычислнтельной задаче, составления расписания выполнения задачи с учетом выбранной структуры, разработки программного обеспечения и средств его отладки приобретает особую актуальность.
Состояние вопроса. В данной диссертационной работе рассматриваются специализированные управляюще-вычислительные мультими кропроцесоорные системы (в дальнейшем - специализированные мультипроцессорные системы), ориентированные на выполнение совокупности простых задач (простая задача может быть решена на одном процессоре), составляющих сильносвязанную (с большим объемом информационного обмена между простыми задачами) сложную задачу. К специализированной мультипроцессорной системе предъявлены требования: выполнения сложной задачи в масштабе реального времени с заданным директивным сроком выполнения сложной задачи или отдель - 6 ных ее частей; статического распределения задач; минимизации количества оборудования. Перечисленные требования ограничили область рассматриваемых мультипроцессорных систем системами с общей оперативной памятью.
Определим выбор структуры специализированной мультипроцессорной системы как определение конфигурации мультипроцессорной системы и ее параметров - количества процессоров и модулей памяти. Исходными данными в задаче выбора структуры мультипроцессорной системы являются структура сложной задачи и множество конфигураций мультипроцессорных систем с общей памятью. Целью задачи выбора структуры является построение структуры мультипроцессорной системы, способной решить сложную задачу в течение директивного срока. Наибольший интерес представляет решение этой задачи, поставленной как экстремальной.
В настоящее время задачу выбора структуры приходится рассматривать не как вычислительную, а как творческую, для решения которой необходимо использовать знание, опыт и интуицию исследователя.
Поставленная в работе экстремальная задача выбора структуры была преобразована в задачу составления расписания выполнения сложной задачи в течение директивного срока.
Решению задачи составления расписания посвящен большой ряд работ известных ученых l-l . Анализ методов, используемых при составлении расписания, позволяет разделить их на две группы -методы, основанные на теории массового обслуживания,и методы, основанные на графовых моделях. Применение теории массового обслуживания при составлении расписаний позволяет получить компактные, простые и достаточно точные оценки, но они носят вероятностный характер и не могут быть использованы при составлении расписания для специализированных мультипроцессорных систем реального време - 7 -ни, когда расчет времени выполнения сложной задачи проводится на худший случай.
Для методов расчета, основанных на графовых моделях, можно отметить следующее. В используемых в настоящее время для составления расписания моделях мультипроцессорных систем учитываются характеристики только процессоров - функциональные характеристики и характеристики производительности. При этом отличия между конфигурациями мультипроцессорных систем не рассматриваются и не учитываются. Кроме того, полагается, что обмен информацией между простыми задачами, а также доступ процессоров к любым данным никак не задерживают вычислительный процесс в сложной задаче, т.е, считается, что переключение между простыми задачами происходит мгновенно. Предположение о незначимости длительности обмена в случае составления расписания выполнения сложной задачи с большой длительностью информационного обмена не позволяет получить точной оценки времени выполнения, если применять существующие методы составления расписания. Кроме того, пренебрежение конфигурацией системы не позволяет учитывать и предотвращать конфликты между процессорами, которые неизбежно возникают при обращении к общей памяти и увеличивают время выполнения сложной задачи.
Эти факторы определили необходимость создания новых моделей и методов составления расписания для мультипроцессорной системы, выполняющей сложную задачу с большой длительностью информационного обмена в течение директивного срока.
Из задачи составления расписания непосредственно возникла задача разработки программного обеспечения, реализующего сложную задачу с учетом составленного расписания, и средств его отладки. Решение этой задачи потребовало разработки структуры программного обеспечения и создания средств отладки, универсальных по отноше - 8 -нию к структуре мультипроцессорной системы, но специализированных по отношению к выбранной структуре программного обеспечения»
Цели и задачи работы. Основная цель данной работы заключает-ся: І) в разработке методики выбора структуры и методов составления расписания выполнения сложной задачи мультипроцессорной системой выбранной структуры; 2) в разработке структуры программного обеспечения, реализующего алгоритм решения сложной задачи; 3) в разработке средств отладки программного обеспечения.
Основными задачами работы являются: построение модели сложной задачи с учетом длительности информационного обмена; составление расписания выполнения параллельной программы, реализующей сложную задачу; оценка эффективности составленного расписания; разработка структуры программного обеспечения мультипроцессорной системы; разработка структуры и программная реализация системы моделирования мультипроцессорных систем с целью отладки программного обеспечения.
Научная новизна. Основные научные результаты, полученные в работе, состоят в следующем:
1. Разработана методика выбора структуры специализированных мультимикропроцессорных систем, основанная на нетрадиционном подходе к решению задачи составления расписания, суть которого состоит в учете длительности информационного обмена.
2. Разработана структура программного обеспечения мультимикропроцессорных систем с разделением функций.
3. Разработана методика структурно-логической отладки мультимикропроцессорных систем, основанная на совместной отладке программного обеспечения и технических средств системы.
В рамках основных результатов были получены частные:
- разработэна аналитическая модель задачи, учитывающая кон - 9 -фигурацию мультипроцессорной системы и длительность информационного обмена;
- сформулирована и решена задача составления оптимального расписания, основанная на предложенной модели задачи,и критерии оптимальности, отличные от существующих;
- разработан метод оценки минимального времени выполнения задачи с учетом длительности информационного обмена;
- сформулированы и решены задачи составления локально-оптимального расписания, основанного на упрощенной модели задачи;
- разработана структура системы моделирования с целью отладки программного обеспечения, основанная на использовании системы разделения времени для мини-ЭВМ СМ-4.
Материалы диссертации характеризует единая направленность разработок, отвечающих задачам современного развития специализированных мультимикропроцессорных систем. Таким образом, полученные в диссертационной работе результаты содержат новое решение актуальной научной задачи, имеющей существенное значение в области проектирования вычислительных процессов в мультимикропроцессорных системах.
Выполнение диссертационной работы было связано с выполнением хоздоговорных научно-исследовательских работ по целевой комплексной программе "Микропроцессоры и микро-ЭВМ", задание 04 "Разработать теорию построения мультимикропроцессорных систем". Практическим итогом работы является создание программного обеспечения системы отладки мультимикропроцессорных систем и составления расписания выполнения параллельных программ. Практическая ценность полученных в диссертации научных результатов состоит в том, что их совокупность позволяет ставить и решать в едином вычислительном процессе задачи составления расписания выполнения параллель - 10 -ных программ и отладку программ с учетом составленного расписания. Основные положения» которые выносятся на защиту, заключаются в следующем.
1. Разработана методика выбора структуры специализированных мультимикропроцессорных систем, которая включает в себя: формали -зацию задачи, постановку экстремальной задачи выбора структуры, обоснование возможности решения задачи выбора структуры как задачи составления расписания на основе модели специального вида; разработку модели специального вида, учитывающей конфигурацию мультипроцессорной системы и длительность информационного обмена; постановку и решение задачи составления расписания; оценку эффективности составленного расписания.
2. Разработана структура программного обеспечения мультимикропроцессорных систем с разделением функций.
3. Разработана методика структурно-логической отладки специализированных мультимикропроцессорных систем с разделением функций, которая включает в себя: постановку задачи структурно-логической отладки как задачи одновременной отладки проблемного
и системного программного обеспечения; совместную отладку системного программного обеспечения и технических средств мультимикро-процессорной системы; отладку проблемного программного обеспечения на уровне архитектуры мультимикропроцессорной системы; разработку методов и алгоритмов построения системы моделирования мультимикропроцессорных систем с разделением функций для отладки проблемного программного обеспечения.
Реализация и внедрение результатов работы. В результате проведения научных исследований разработан комплекс программ системы моделирования мультимикропроцессорных систем с разделением функций для отладки программного обеспечения и программы составления
- II расписания. Программы написаны на языках ФОРТРАН-4 и БЕЙСИК-ПЛЮС в операционной системе ДОСКП для мини-ЭВМ СМ-4.
Научные и практические результаты диссертации внедрены в ОКБ МЭЙ, НИИ Приборостроения, НИИ Автоматики. Общий экономический эффект от использования внедренных результатов, согласно имеющимся актам о внедрении, составил 74 тыс,руб.
Апробация работы. Основные научные результаты диссертационной работы докладывались, обсуждались и были одобрены на Всесоюзном научно-техническом семинаре "Вопросы проектирования микропроцессорных систем и их применение" (Киев, 1983), на Всесоюзной научно-технической конференции "Автоматизация проектирования ЭВМ и систем" (Ереван, 1983), на ХП Всесоюзном совещании-семинаре "Автоматизация проектирования микропроцессоров, микропроцессорных систем и СБИС" (Симферополь, 1984), на Конференции молодых ученых и специалистов "Проблемы теории систем и САПР" (Москва, 1983), на Конференции "Микропроцессорные распределенные системы управления технологическими процессами и ГАП" (Москва, 1984).
Публикации по работе. По теме диссертации опубликовано шесть печатных работ.
Структура и объем работы. Содержание диссертационной работы изложено на 148 страницах машинописного текста, иллюстрированного 23 рисунками. Диссертация состоит из введения, пяти глав, заключения, списка использованной литературы (73 наименования) и приложения.
В первой главе описаны требования, предъявленные к специализированным мультимикропроцессорным системам; рассмотрены конфигурации мультипроцессорных систем и выбрано множество конфигураций, удовлетворяющих предъявленным требованиям; рассмотрены аппаратные и программные методы уменьшения времени решения сложной задачи;
-формализована и поставлена экстремальная задача выбора структуры специализированной мультипроцессорной системы; определен метод ее решения. Главным итогом первой главы является преобразование задачи выбора структуры в последовательность задач составления расписания.
Во второй главе рассмотрен состав управляюще-вычислительной сложной задачи; разработан способ графического представления сложной задачи и показана необходимость учета длительности и порядка выполнения операций обмена для получения точной оценки вре -мени решения сложной задачи; разработана модель задачи с учетом длительности и порядка выполнения операций обмена; поставлена экстремальная задача составления оптимального расписания; определен метод решения и проведена оценка его временной сложности. Главным итогом второй главы является разработка модели задачи и определение пути уменьшения временной сложности составления расписания,
Б третьей главе разработана упрощенная модель задачи; поставлена задача составления локально-оптимального расписания; определен метод ее решения; выполнена оценка эффективности локально-оптимального расписания по отношению к оптимальному расписанию; разработана инженерная методика выбора структуры. Главным итогом третьей главы является разработка методики выбора структуры муль-тимикропроцессорной системы с разделением функций.
Б четвертой главе разработана структура программного обеспечения специализированных мультипроцессорных систем с разделением функций; разработаны методы диспетчирования при выполнении сложной задачи; показана возможность одновременной отладки проблемного и системного программного обеспечения и необходимость совместной отладки системного обеспечения и технических средств; разработаны методы и алгоритмы создания системы моделирования с целью
-отладки проблемного программного обеспечения. Главным итогом четвертой главы является разработка структуры программного обеспечения мультипроцессорных систем с разделением функций, методики и средств отладки программного обеспечения.
В пятой главе приводится описание применения полученных в работе научных результатов и разработанного программного обеспечения при проектировании мультипроцессорной системы управления оптической станцией.
Приложение содержит документы, подтверждающие внедрение результатов диссертационной работы.
