Введение к работе
Актуальность проблемы. Одним из главных направлений развития техники обработки информации является создание параллельных вычислительных средств высокое производительности для обеспечения быстрого и элективного решения слоявых научных и технических задач.
Среди перспективных архитектурных концепций построения высокоэффективных параллельных вычислительных средств важное место занимает концепция -вычислительных систем " (ВС) с программируемой структурой, предложенная З.В.Евреиновым. Построение таких ПС основано на принципах параллельности выполнения" операций, конструктивной однородности и програкмируемостк структуры.Вычислительная система с программируемо!' структурой представляет co6of совокупность элементарных машин (?;.;), соединенных регулярной,программно настраиваемой сетью сргзи.-
Наряду с созданием архитектуры ВС необходимо также разработать быстрые и э(тг>.кт::гные параллельные алгоритмы решения сложных научных и технических задач.Исследования в этой области стали особенно актуальні та» с появлением разнообразных параллельных вычислительных среястЕ, и здесь Еакное место занимает проблема построения быстрых и элективных параллельных алгоритмов решен::?; сложных сильносвязкых задач, т.е. таких, при реализации которых требуется иитєнзггннй обмен информацией мезду ЕМ в ВС.
Цель работы. Выработка рекомендации по архитектуре и структуре ВС на основе анализа сложных сильносвягзных задач и ыетодо?. их решения; разработка" быстрых и элективных методйв параллельного решения сложных спльносвязных задач на.ВС с программируемо** структурой; ксследование и разработка параллельных алгоритмов решения модельных слокных сильносвязных задач и оценка их качества при. реализации на ВС типа микропроцессорной внчислигелькои системы МІЇКР0С, созданной на базе мини- и ьикроЭБМ семейства ".Электроника','
Методи исследования. Б работе используются методы теории вычислительных систем, численные методы решения задач математической г|изнки v. линейной алгебры, методы теории разностных схем и статистического коделирорэннг.
Новыэ научные результаты. На основе анализа сложных сильносвязных задач, явл люди-:-.-. нрс-ирнкі задачами математической физики, и методов их решения гг. дложены оптимальные физические структуры
ВС, обеспечивающие при естественном вложении алгоритмов решения этих задач в структуру ВС минимум временных затрат ВС с учетом времени на межмашинные обменные взаимодействия и не содержащие неиспользуемые связи между ЭМ в ВС. В частности, показано, что для решения одномерных задач методами Якоби, Ричардсона, простой итерации оптимальными являются структуры ВС типа "линейка", двумерных - структуры типа "решетка". Решение сложных сильносвязных задач методами Фурье, редукции, многосегочными целесообразно осуществлять на гиперкубических структурах.
Разработаны на основе естественного вложения алгоритмов решения задач- в структуру базовой ВС параллельные алгоритмы прямых и итерационных численных методов решения сложных силъносвязных задач математической физики; полученные расчетные формулы временных затрат базовой ВС позволяют упорядочить разработанные параллельные алгоритмы в порядке возрастания временных затрат ВС на их реализацию следующим образом: алгоритм распараллеливания прогонки, параллельные алгоритмы методов Фурье,' Ричардсона, попеременно-треугольного с чебышевским набором итерационных параметров, верхней релаксации, переменных направлении, попеременно-треугольного, решения по явной схеме, простей итерации, Зейделя.
Разработаны параллельные алгоритмы метода зонального разбиения для решения одномерных сложных сильносвязных задач на мощных ВС с программируемой структурой, вклвчающах в себя более 16 ЗМ, и маломощных ВС, которые превосходят до скорости и эффективности алгоритм распараллеливания прогонки более . чем в 1,75 раза главдаш образом за счет принципиального сокращения времени на межмашинные обмены информацией.
Разработан метод матричного зонального разбиения для решения многомерных сложных сильносвязных задач на ВС с программируемой структурой, реализация которого на базовой ВС позволяет сократить временные затраты ВС более чем в 2,72 раза по сравнению с параллельным алгоритмом комбинированного метода йурье и прогонки, являющимся наиболее быстрым из ранее известных.
Новые практические результаты. Выработаны практические рекомендации по организации физических структур ВС для решения сложных сильносвязных задач в зависимости от типа задач и методов их решения.
Построены параллельные алгоритмы решения на ВС с програмииру-
емой структурой модельных слоеных сильносвязных задач (разностной задачи Дирихле для уравнения Пуассона и разностной первой краевой задачи для одномерного уравнения теплопроводности) на базе методов решения по явной схеме, Фурье, редукции, прогонки, дробных шагов, простой итерации, Якоби, Ричардсона, верхней релаксации, Зейделя, попеременно-треугольного, попеременно-треугольного с чебышевским набором итерационных параметров, переменных направлений.
Разработаны и реализованы параллельные алгоритма решения модельных сложных сильносвязных задач на ВС с программируемой структурой, основанные на методах зонального разбиения и матричного зонального разбиения.
Получены числовые оценки -временных затрат и эффективности параллельных алгоритмов решения модельных сложных сильносвязных задач на ВС МИКРОС, в том числе для параллельных алгоритмов методов зонального разбиения.
Разработан ж реализован алгоритм выделения подсистем из ВС с программируемой структурой, для обеспечения мультипрограммного режима функционирования ВС при решении сложных сильносвязных задач.
Апробация работы. Основные положения и результаты работы докладывались на Х1Ш Всесоюзной научной сессии, посвященной Дню радио (Москва, -1988, май), на Республиканской научно-технической конференции "Вопросы разработки вычислительной техники" (Кишинев, 1989, май),на Третьем региональном семинаре СО АН СССР и Сибирской .территориальной группы" Советского национального комитета IMACS (Улан-Удэ, 1989, июль), на ЮГУ областной научно-технической конференции, посвященной 60-й годовщине образования СССР и Дню радио (Новосибирск, 1982, май), на научно-технических конференциях профессорско-преподавательского состава МИС (I988-I9S0).
Публикации. По материалам диссертации опубликованы 12 научных работ.
Структура и объем работы. Работа состоит из введения, четырех глав, заключения, трех приложений. Содержит 135 страниц машинописного текста, 18 таблиц, 28 рисунков, список литературы из 105 наименований.