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

ВВЕДЕНИЕ. ПРОБЛЕМЫ ПЛАНИРОВАНИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ

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

Глава I, ПОСТАНОВКА ЗАДАЧИ ВЫБОРА СТРУКТУРЫ МУЛЬТИМИКРО

ПРОЦЕССОРНОЙ СИСТЕМЫ С РАЗДЕЛЕНИЕМ ФУНКЦИЙ

1.1» Выбор множества допустимых конфигураций мультимикропроцессорных систем с разделением функций

1.2. Определение понятия структуры мультипроцессорной системы и степени связанности сложной задачи

1.3. Анализ взаимосвязи времени решения сложной задачи, стоимости мультипроцессорной системы и организации выполнения сложной задачи

1.4. Постановка задачи выборе структуры и определение метода ее решения

1.5. Выводы к первой главе. 3?

Глава П. СОСТАВЛЕНИЕ ОПТИМАЛЬНОГО РАСПИСАНИЯ ВЫПОЛНЕНИЯ

СИЛЬНОСВЯЗАННОЙ СЛОЖНОЙ ЗАДАЧИ

2Д. Анализ взаимодействия сложных задач

2.2. Совмещение операций обмена и графическое описание сложной задачи

2.3. Модель задачи составления расписания

2.4. Аналитическая модель простой задачи

2.5. Постановка и решение задачи составления оптимального расписания

2.6. Выводы ко второй главе

Глава Ш. СОСТАВЛЕНИЕ ЛОКАЛЬНО-ОПТИМАЛЬНОГО РАСПИСАНИЯ ВЫПОЛНЕНИЯ ШЬНОСВЯЗАННОЙ СЛОЖНОЙ ЗАДАЧИ.

3.1. Оценка эффективности локально-оптимального расписания

3.2. Постановка и решение задачи составления локально-оптимального расписания

3.3. Инженерная методика выбора структуры мультипроцессорной системы с разделением функций . . . . •

3.4. Выводы к третьей главе.

Глава 1У. РАЗРАБОТКА СТРУКТУРЫ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ СПЕЦИАЛИЗИРОВАННОЙ МУЛЬТИМИКРОПРОЦЕССОРНОЙ СИСТЕМЫ И СРЕДСТВ ЕГО ОТЛАДКИ.

4.1. Структура программного обеспечения мультимикропро-цессорных систем с разделением функций

4.2. Методы диспетчирования и состав системного программного обеспечения.

4.3. Отладка мультипроцессорных систем с разделением функций.

4.4. Средства отладки проблемного программного обеспечения

4.5. Выводы к четвертой главе

Глава У. ВЫБОР СТРУКТУРЫ И ОТЛАДКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ СИСТЕМЫ УПРАВЛЕНИЯ ОПТИЧЕСКОЙ СТАНЦИЕЙ

5.1. Технические средства оптической станции

5.2. Выбор структуры мультипроцессорной системы управления

5.3. Отладка программного обеспечения системы управления

5.4. Выводы к пятой главе

ВЫВОДЫ.

ПРОБЛЕМЫ ПЛАНИРОВАНИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ И ОТЛАДКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ

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

Актуальность проблемы* Данная работа посвящена вопросам выбора структуры специализированных мультимикропроцессорных систем, ориентированных на решение совокупности задач с большим объемом информационного обмена, разработке структуры программного обеспечения и средств его отладки.

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

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

Состояние вопроса. В данной диссертационной работе рассматриваются специализированные управляюще-вычислительные мультими-кропроцесоорные системы (в дальнейшем - специализированные мультипроцессорные системы), ориентированные на выполнение совокупности простых задач (простая задача может быть решена на одном процессоре), составляющих сильносвязанную (с большим объемом информационного обмена между простыми задачами) сложную задачу. К специализированной мультипроцессорной системе предъявлены требования: выполнения сложной задачи в масштабе реального времени с заданным директивным сроком выполнения сложной задачи или отдельных ее частей; статического распределения задач; минимизации количества оборудования. Перечисленные требования ограничили область рассматриваемых мультипроцессорных систем системами с общей оперативной памятью.

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

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

Поставленная в работе экстремальная задача выбора структуры была преобразована в задачу составления расписания выполнения сложной задачи в течение директивного срока.

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

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

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

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

Пели и задачи работы. Основная цель данной работы заключается: I) в разработке методики выбора структуры и методов составления расписания выполнения сложной задачи мультипроцессорной системой выбранной структуры; 2) в разработке структуры программного обеспечения, реализующего алгоритм решения сложной задачи; 3) в разработке средств отладки программного обеспечения.

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

Научная новизна. Основные научные результаты, полученные в работе, состоят в следующем:

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

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

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

В рамках основных результатов были получены частные:

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

- сформулирована и решена задача составления оптимального расписания, основанная на предложенной модели задачи,и критерии оптимальности, отличные от существующих;

- разработан метод оценки минимального времени выполнения задачи с учетом длительности информационного обмена;

- сформулированы и решены задачи составления локально-оптимального расписания, основанного на упрощенной модели задачи;

- разработана структура системы моделирования с целью отладки программного обеспечения, основанная на использовании системы разделения времени для мини-ЭВМ СМ-4.

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

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

Основные положения» которые выносятся на защиту, заключаются в следующем.

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

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

3. Разработана методика структурно-логической отладки специализированных мультимикропроцессорных систем с разделением функций, которая включает в себя: постановку задачи структурно-логической отладки как задачи одновременной отладки проблемного и системного программного обеспечения; совместную отладку системного программного обеспечения и технических средств мультимикро-процессорной системы; отладку проблемного программного обеспечения на уровне архитектуры мультимикропроцессорной системы; разработку методов и алгоритмов построения системы моделирования мультимикропроцессорных систем с разделением функций для отладки проблемного программного обеспечения.

Реализация и внедрение результатов работы. В результате проведения научных исследований разработан комплекс программ системы моделирования мультимикропроцессорных систем с разделением функций для отладки программного обеспечения и программы составления расписания. Программы написаны на языках ФОРТРАН-4 и БЕЙСИК-ПЛЮС б операционной системе ДОСКП для мини-ЭВМ СМ-4.

Научные и практические результаты диссертации внедрены в ОКБ МЭЙ, НИИ Приборостроения, НИИ Автоматики. Общий экономический эффект от использования внедренных результатов, согласно имеющимся актам о внедрении, составил 74 тыс,руб.

Апробация работы. Основные научные результаты диссертационной работы докладывались, обсуждались и были одобрены на Всесоюзном научно-техническом семинаре "Вопросы проектирования микропроцессорных систем и их применение" (Киев, 1983), на Всесоюзной научно-технической конференции "Автоматизация проектирования ЭВМ и систем" (Ереван, 1983), на ХП Всесоюзном совещании-семинаре "Автоматизация проектирования микропроцессоров, микропроцессорных систем и СБИС" (Симферополь, 1984), на Конференции молодых ученых и специалистов "Проблемы теории систем и САПР" (Москва, 1983), на Конференции "Микропроцессорные распределенные системы управления технологическими процессами и ГАП" (Москва, 1984).

Публикации по работе. По теме диссертации опубликовано шесть печатных работ.

Структура и объем работы. Содержание диссертационной работы изложено на 148 страницах машинописного текста, иллюстрированного 23 рисунками. Диссертация состоит из введения, пяти глав, заключения, списка использованной литературы (73 наименования) и приложения.

ВЫВОДЫ

1. Разработана методика выборе структуры специализированной мультимикропроцессорной системы с разделением функций, которая включает в себя:

- формализацию задачи выбора структуры;

-— постановку задачи выбора структуры как задачи определения минимального количества оборудования мультимикропроцессорной системы, способной выполнить сложную задачу в течение директивного срока;

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

2. Разработан метод составления оптимального расписания выполнения сильносвязанной сложной задачи, который включает в себя:

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

- постановку задачи составления расписания как задачи определения наименьшей длительности выполнения сложной задачи;

- разработку алгоритма решения задачи составления расписания и оценку его временной сложности.

3. Разработан метод составления локально-оптимального расписания выполнения сильносвязанной сложной задачи, который включает в себя:

- 138

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

- постановку задачи составления локально-оптимального расписания как задачи разбиения множестве вершин графа сложной задачи на непересекающиеся подмножества;

- разработку алгоритма решения и оценку эффективности локально-оптимального расписания по отношению к оптимальному расписанию.

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

5. Разработана методика отладки программного обеспечения, которая включвет в себя:

- выбор уровня моделирования при отладке системного и проблемного программного обеспечения;

- обоснование возможности одновременной отладки проблемного и системного программного обеспечения и необходимости совместной отладки системного программного обеспечения и технических средств мультипроцессорной системы;

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

6. Разработан программный комплекс составления расписаний и моделирования на базе операционной системы разделения времени ДОС КП и мини-ЭВМ СМ-4.

- 139 -ЗАКЛЮЧЕНИЕ

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

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

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

- 140 тируемых мультипроцессорных систем. Тем не менее задача построе ния быстрого алгоритма составления оптимального расписания является весьма перспективной.

1. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний.-М.: Наука, 1975,- 360 с.

2. Теория расписаний и вычислительные машины. Под редакцией

3. Коффмана Э.Г.- М.: Наука, 1984,- 334 с, 1

4. Hoogendorn C.H. Reduetion of memory interference in multiprocessor systems о AETPS Proc.PJCC. 1977, p.179-183.17* Nilsen R.N. Distributed computer architectures; a survey. Proc. 8th Hawaii Int. Conf. Syst. Sci., 1975, P-19-20.

5. Casaglia G.F., Copelli S., Lijtmaer N. Distributed control for local network of minisi a design approach using microprocessors. Microprocessing and microprogramming, EUROMICRO 2-nd,1976,p.119-125»

6. Young S.J. Inter-process communication primitives for DSM multiprocessors. Implementing functions. EUROMICRO 7-th, 1981, p-327 -332.

7. Russo P.M. Interprocessor Communication for Multi-Microcomputer Sytems. Computer, 1977, v.10, N4, p.67-75*

8. Cuncep P. Архитектура связи в распределенных системах. Книга I. М. : Мир, 1981, - с.1-445.

9. Сипсер Р. Архитектура связи в распределенных системах. Книга 2.-М. : Мир, 1981, с.446-742.

10. Вэйцман К. Распределенные системы мини- и микро-ЭВМ. М. : Финансы и статистика, 1982. 382с.

11. Bishop P.G. The desing of software for distributed conrol systems. EUROMICRO Journal, 1979, v.5, Ж6, p.368-362.

12. Okada Y.,Taoima H., Mori R. A novel multiprocessor array. Microprocessing and microprogramming, EUROMICRO 2-nd, 1976, p.83-90.

13. Tanaka T. HASPS ( Hokkaido University Array Processor System a new hierarchical array processor system. Microprocessing and microprogramming, EUROMICRO 2-nd, 1976, p.91-98.

14. Hoener S., Roehder W. Modular multi-microprocessor arghi-tecture with virtual memory. Microprocessing and microprogramming, EUROMICRO 2-nd, 1976, p.99-108.

15. Mazare G., MCS a symetric multi-microprocessor system. Microprocessing and microprogramming, EUROMICRO 2-nd, 1976,p.135-140.

16. De Francesco N., Vaglini G., Vannesehi M. Implementation of parallel computation schemata. Microprocessing and microprogramming, EUROMICRO 2-nd, 1976, p.157-163.

17. Kempken E., Lange 0. Program controlled multiprocessor structures based on universal DDA-like processor elements. Microprocessing and microprogramming, EUROMICRO 2-nd, 1976,p.277-283.

18. Steinhoff J., McGill R. An approach to solving scientific problems using multiple microprocessrs. Microprocessing and microprogramming, EUROMICRO 2-nd, 1976, p.285-293*

19. Corsini P., Frosini G., Galati G., Grandoni F., La Manna M. Serial microprocessor array for radar signal processing. Microprocessing and microprogramming, EUROMICRO 2-nd, 1976,p.317-325.

20. Treleaven P.C., Wathanasin S. A design environment formulti-microprocessor computer systems and their software. Microprocessing and microprogramming, EUROMICRO 2-nd, 1976, p.205-211.

21. Negrini R., Sami M.G. The "assembly-line" multi microprocessor structure. Microcomputer architectures, EUROMICRO 3-£cl» 1977, p.266-276.

22. Huhtanen T., Lehtinen T., Nikkila S., Pulkkis G.

23. JUG* a hybrid redundant multimicroprocessor. Microprocessors and t their applications, EUROMICRO 5-th, 1979, p.285-294.

24. Van der Ouderaa E.M., Vrielink H., Willemse A.

25. COMA, a single-chip communication interface for distributed microcomputer systems. Microprocessors and their applications, EUROMICRO 5-th, 1979, P«305-314•

26. Deshmukh H.A., Scott R.G.F., Roberts P.D.

27. A hierarchically structured multimicroprocessor system. Microprocessors and their applications, EUROMICRO 5-th, 1979, p.317-328.

28. Van Laethem D., Gregoire T., Goldstein J. A ring network for industrial processes and distributed systems. Implementing functions, EUROMICRO 7-th, 1981, p.91-98.

29. Moller-Nielsen P., Staunstrup J., Soe K., Andersen J.S. A multi-processor for multi-program experiments. Implementing functions, EUROMICRO 7-th, 1981, p.117-124.

30. Conte G., Del Corso D., Gregoretti P., Pasero E. T0MP80 a multiprocessor prototype. Implementing functions, ElffiOMICRO 7-th, 1981, p.401-410.

31. Andreassen J.K., Rubner-Petersen T. A multiprocessor structure for real time processing. Implementing functions, EUROMCRO 7-th, 1981, p.455-464.

32. Гэри M., Джонсон Д. Вычислительные машины и трудноре-шаемые задачи. М. : Мир, 1982. - 416с.65* Сергиенко Й.В., Каепшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. Киев. : Наукова думка, 1981. - 288с.

33. Голубеико С.В., Радзиевский Г.П., Сохацкий А.А. Транслятор с языка описания цифровых вычислительных устройств СИМОД. ~ Москва, 1984. 33с.- Рукопись представлена Московским институтом электронного машиностроения.Деп. в ВИНИТИ 9 февраля 1984, №799 - 84.

34. Bifonte J. A technology for all systems software for true multiprocessor network. Data systems, 1980, I, p.12-13.

35. Bogong S., Grishman R. Emulating an MIMD architecture. Proc. of the 15th Annual Workship on microprogramming, 1982, Oct., p.197-199*71• Intellec series II hardware reference manual. S.1: Intel Corp.