Введение к работе
Актуальность проблемы. В основных направлениях экономического и социального развития народного хозяйства, принятых на ЖУП съезде КПСС, решающая роль отводится повышению уровня комплексной автоматизации производства за счет разработки и внедрения высокоэффективной вычислительной техники.
Реализация программы повышения уровня автоматизации обусловливает необходимость широкого использования средств вычислительной техники с целью перехода к применению самоорганизующихся технологических и производственных комплексов во всех сферах народного хозяйства, что является основным направлением интенсификации физического и интеллектуального труда человека, повышения производительности труда.
Современный этап развития средств вычислительной техники характеризуется интенсивным использованием принципа параллельной обработки информации. Концепция развития систем параллельной обработки информации неразрывно связана с концепцией модели коллектива вычислителей, предложенной и развиваемой ,j.B.Eb-реиноЕым. Переход от использования однородных вычислительных систем к более интенсивному внедрению однородных вычислительных структур и сред выдвигает на первый план задачу разработки их системного и прикладного программного обеспечения.
Проблема организации функционирования однородных вычислительных структур и сред (ОВС) в условиях заданных ограничений на их ресурсы многопланова, сложна и требует решения целого комплекса задач, начиная от разработки метода и параллельной программы решения сложной задачи и кончая обеспечением оптимального планирования и управления вычислениями. Роль алгоритмов планирования вычислительных процессов ещё более возрастает в связи с начавшимся внедрением мультитранспьютерных станпиР и систолических матриц, которые имеют в своем составе сотни и тысячи элементарных модулей, "мультитранспьютерные станции и систолические матрицы в плане реализации являются новыми средствами, однако в концептуальном плане они являются одно!5 из конкретизации идеи однородных вычислительных систем, структур и сред. Процесс решения сложной задачи на данных технических
средствах сводится к параллельному решению набора задач меньшей сложности, связанных между собой определенными обменными взаимодействиями. Решающую роль при разбиении сложной задачи на набор задач меньшей сложности играет логическая схема алгоритмов (ЛСА), полученная в свою очередь на основе формальной модели. Решение сложной задачи укрупнённо разбивается на два этапа: этап планирования, атап реализации. На этапе планирования устанавливается взаимосвязь между структурой логических схем параллельных алгоритмов и топологией ОВС с целью последующего отображения логических схем и настройки вычислительной структуры на решение данного алгоритма. На этапе планирования отображение логических схем алгоритмов в ОВС необходимо производить с учетом отказов элементарных модулей. На этапе реализации существенную роль играет режим отказоустойчивости функционирования ОВС, который предпологает завершение процесса решения задачи при отказах одного или части элементарных модулей, настроенных на реализацию логических схем алгоритмов. В связи с этим возникает проблема оптимального отображения логических схем алгоритмов в ОВС с учетом ненадежности функционирования элементарных модулей на этапах планирования и реализации заданных алгоритмов.
Целью диссертации является разработка метода оптимального отображения логических схем алгоритмов произвольной структуры в отказоустойчивую ОВС.
В соответствии с поставленной целью в диссертационной работе решаются следующие основные задачи:
исследование и обоснование выбора формальное модели представления структуры логических схем алгоритмов;
разработка метода оптимального отображения логических схем алгоритмов произвольной структуры в ОВС с учетом отказов элементарных модулей;
разработка средств организации эффективной настройки 0J3C на реализацию заданных логических схем алгоритмов и их практическая реализация.
Методы исследования. Б качестве математического аппарата используются методы теории надежности, теории формальных языков, теории алгоритмов, теории графов, теории алгоритмических алгебр.
-V/
Научная новизна результатов работы заключается в следующем:
-
Обоснован выбор функционально-потокошГ модели представления логических схем параллельных алгоритмов, как наиболее адекватной по своей структуре топологии 0ІЗС и обеспечивающей повышение эффективности решения сложно? задачи.
-
Разработан метод дискретно-траекторного отображения логических схем алгоритмов произвольной структуры в отказоустойчивую Ох>С, отличающийся от известных быстродействием и дискретным характером построения траектории Функции оптимального отображения алгоритмов, учетом отказов олементарньг/ "одулей
на ьтапах планирования и реализации вычислительного процесса. Кетод включает в себя следующие основные теоретические результаты:
получены аналитические зависимости для расчета показателей надежности функционирования отказоустойчивых 0.-;0, учитывающие высокую надежность функционирования елементарних модулей, взаимосвязь меиду структурой логических схем алгоритмов и топологией 0BG в процессе отображения;
разработана процедура оптимального отображения логических схем алгоритмов произвольной структуры в UbC с учетом отказов модулей на этапах планирования и реализации вычислительного процесса;
разработана алгоритмическая реализация метода дискретно-траекторного отображения логических схем алгоритмов в отказоустойчивую 05С с использованием аппарата системы алгоритмических алгебр. -
3. Разработана функционально-логическая схема модуля 0п.З,
отличающаяся от известных наличием блока сравнения, блока за
держки и цепи синхронизации процесса настройки. Модуль, обес
печивает сокращение времени настройки 0UG при одновременном
планировании нескольких вычислительных процессов.
Личный вклад автора. Все основные результаты, изложенные в диссертации, получены автором лично.
Практическая ценность работы. Разработанные в диссертационной работе метод и технические средства позволяют повысить эффективность Ьункционирования ОсС за счет оптимального отображения структуры алгоритмов в топологию вычислительной структуры, сократить время настройки на
реализацию заданных алгоритмов. Полученные в работе аналитические формулы для расчета показателей надежности позволяют получить достоверные оценки качества функционирования ОаС с учетом структуру логических схем алгоритмов и топологии вычислительной структуры. Метод дискретно-траекторного отображения логических схем алгоритмов в отказоустойчивую ОБО доведен до программной реализации.
Реализация результатов работы. Диссертационная работа выполнялась на кафедре вычислительной техники и управляющих систем Московского института связи в соответствии с хоздоговорной НИР с Центральным научно-исследовательским институтом "Центр", а также по договору о творческом содружестве между отделом АСУ АН Азерб. ССР и МИС.
Результаты диссертационной работы реализованы при проведении научно-исследовательских работ и включены в научно-технический отчет (гос. per. № 01890034386).
Результаты работы реализованы при разработке проблешо-ориентированных программно-технических комплексов, при проектировании аппаратных средств локальной сети и их глобальных структур , а также были использованы при составлении методического указания по выполнению лабораторной работы по курсу "Операционные системы управляющих систем электросвязи" в Московском институте связи.
Реализация результатов работы подтверждена соответствующими актами.
Апробация работы. Основные результаты диссертации докладывались и обсуждались на Всесоюзной научно-технической конференции "Микропроцессорные средства локальной автоматики" (Гродно, 1989), на Всесоюзном научно-техническом семинаре "Качество функционирования и надежность систем автоматической коммутации и сетей электросвязи" (Новосибирск, Ь8о), на Республиканской научно-технической конференции "Дэс-тижение науки - производству" (Баку, 1988), на IX научно-технической конференции молодых ученых и специалистов ЦНИИС (Москва, 1990), на научно-технических конференциях профессорско-преподавательского состава и аспирантов МИС (Москва, 1989,
1990) .
Публикации. По теме диссертации опубликовано
І0 печатных работ.
Структура и объем работы. Диссертационная работа состоит из введения, четырех разделов, заключения и списка литературы. Работа изложена на 135 страницах -машинописного текста, содержит 20 страниц рисунков, список литературы включает 112 наименований. ~