автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Разработка метода автоматизированного проектирования персональных суперЭВМ и его приложение к задаче многомерного моделирования элементов СБИС

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи ЮНЕС Мамун Фауаз

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

Специальность 05.13.16 - применение вычислительной

техники, математического моделирования и математических методов в научных исследованиях;

05.13.13 - вычислительные машины, комплексы, системы и сети.

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Минск - 1992

Работа выполнена в Белорусском государственном университете

Научные руководители:

- доктор технических наук, профессор С.Г.Мулярчик

- кандидат технических наук, доцент Г.И.Шпаковский.

Официальные оппоненты:

- доктор технических наук Тихоненко О.М.

- кандидат технических наук Курбацкий А.Н.

Ведущая организация: НИИ ЭВМ

Защита состоится 29.12.1992 года в 10 часов на заседании специализированного совета К 056.03.14 при Белгосуниверситете (2200506 г. Минск, проспект Ф.Скорины, 4, Университетский городок).

С диссертацией можно ознакомиться в библиотеке Белгосуниверситета.

Автореферат разослан

Ученый секретарь специализированного совета

доктор технических наук

В.М.Скришшк

Г (К" . .• /.:; ■

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Однако параллелизм операций в каждой прикладной задаче представлен в виде особых конструкций, называемых формами параллелизма (ФП). Для каждой ФП необходима соответствующая архитектура параллельного процессора. Если арихитектура процессора неадекватна ФП, то ускорения вычисления задачи не ггроисходит. В связи с этим разработка методов автоматизированного выбора архитектур параллельных процессоров под класс решаемых задач является актуальной проблемой при проектировании ПС ЭВМ.

Цель и задачи работы. Целью работы является разработка метода автоматизированного проектирования персональных суперЭВМ и апробация этого метода в приложении к задаче многомерного моделирования элементов СБИС.

Для достижения поставленной цели должна быть решена следующая последовательность задач:

1. Определить и формализовать понятие персональной суперЭВМ, обосновать возможность и необходимость их создания.

2. Выбрать и обосновать состав, характер и уровень частных

моделей, описывающих элементы ПС ЭВМ (модель задачи, распараллеливателя и структуры параллельного процессора). В качестве параметров моделей должны использоваться реально измеряемые характеристики прикладных задач. На основе частных моделей построить интегральную модель системы для оцешси параметров ПС ЭВМ.

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

4. Исследовать эффективность метода автоматизированного проектирования ПС ЭВМ на задачах многомерного моделирования элементов СБИС.

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

Методы исследования. В работе использованы методы теории параллельных вычислений и структур, методы теории программирования и теории графов. Для анализа многомерных структур СБИС используются методы вычислительной математики. Для представления программ и структур применяются методы теории моделирования и семантические модели.

Научная новизна заключается в следующем:

1. На основе анализа тенденций развития .средств параллельной вычислительной техники, микроэлектроники и средств автоматизации проектирования введен и определен новый класс ЭВМ - персональные суперЭВМ.

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

3. Предложен алгоритм СИНТАЛ синтеза оптимальной структуры параллельной системы при заданных свойствах прикладной задачи, представленной в виде гнезда вложенных циклов.

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

5. Предложены и реализованы новые алгоритмы многомерного моделирования элементов СБИС, обладающие высоким потенциальным

о

параллелизмом.

6. Алгоритм СИНТАЛ реализован программно, получены экспериментальные результаты.

Практическая ценность работы заключается в следующем:

1. Алгоритм СИНТАЛ позволяет на ' начальных этапах проектирования путем изучения характеристик"реалььных прикладных задач выбрать структуру параллельного процессора, обеспечивающего наилучшие эксплуатационные характеристики проектируемой системы: быстродействие, стоимость и др.

2. Алгоритм СМИТАЛ позволяет измерять параллелизм задач, следовательно, с его помощью можно производить разработку новых алгоритмов, обладающих нужной степенью параллелизма.

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

Апробация работы и публикации. Основные научные результаты и выводы, полученные в диссертационной работе, докладывались и обсуждались на международной конференции "Automation, simulation & measurement" (Таллинн, 1991), на межреспубликанской научно-практической конференвди "Актуальные проблемы информатики: математическое, программное и информационное обеспечение" (Минск, 1992).

По теме диссертации имеются 2 публикации.

<

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения. Объем диссертации составляет 202 страницы, включая 47 рисунков, 14 таблиц и 163 наименования литературы. <

СОДЕРЖАНИЕ РАБОТЫ

Во введении кратко рассмотрено влияние быстродействия вычислительных средств на возможности САПР и рабочих станций,

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

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

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

Персональные суперЭВМ определяются как параллельные 3BW относительно небольшого единичного быстродействия (10 - 5С МФлоп/с) с традиционной последовательной системой программирования. Автоматическое распараллеливание программ производится программно или аппаратно.

Исследованы возможности технической реализации ПС ЭВМ. Показано, что наиболее подходящими для построения ПС ЭВМ являются RISC-микропроцессоры с программируемым параллелизмом типа I860 фирмы INTEL, DSP 96002 фирмы Motorola и др.

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

В главе .1 произведен обзор работ по автоматизированному синтезу структур параллельных ЭВМ. Показано, что прями; результатов в этом направлении еще не получено.

С целью выбора или разработки метода синтеза ускорение системы г представлено в виде:

г = R * ZApn * Zs. где г - потенциальное ускорение задачи при неограниченных ресурсах, 2дрп и ZQ - пропускная способность автоматического распараллеливателя (АРП) и структуры процессора S.

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

Рассмотрены различные виды моделей для представления программ: графовые, на основе марковских цепей, систем массового обслуживания, имитационные .модели разного уровня. Показано, что для описания параллелизма гнезд циклов, представляющих задачу, наиболее удобными являются модели на основе ФП, так как параметры последних поддаются непосредственному измерению. В работе определ&ш основные формы параллелизма: DO ALL, DO ACROSS, SEQ и др. С каждой ФП связан набор параметров: число операций в теле цикла, число итераций, объем межитерационных обменов, наличие операторов переходов, вероятности этих переходов и т.д.

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

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

Дана постановка задачи.

Глава 2. В главе 2 теоретически обосновывается и предлагается метод синтеза структур параллельных процессоров 01ТНТМ. Под синтезом погашается процесс выбора оптимальной по быстродействию структуры под заданную задачу или класс задач.

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

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

i-a с г = е/ Га__ + _; ,

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

Здесь а и с - параметры задачи, пит- параметры структуры.

Получен ряд следствий для особых вариантов построения системы.

Следствие Если в выражении для ускорения г величина с= =nk, где k>i, то ускорение системы с ростом п падает. Это может иметь место в циклах с "широковещательным" обменом, когда для каждой переменной отводится собственный процессорный элемент и после очередной итерации результат из кавдого процессорного элемента передается во все другие процессорные элементы.

Следствие 2. Если объем оборудования h параллельного процессора ограничен, то для каждого набора параметров цикла имеется оптимальный вариант распределения этого оборудования между основными и служебными функциями этого параллельного процессора.. В частности, если h = п + т, то оптимальное значение п будет:

п = ШШ 1-а-с

Следствие 3. Если на одном уровне гнезда циклов имеется несколько циклов с различными ФП, то для каждой ФГ^ нужен процессор со структурой типа Si. Ускорение такой одноуровневой системы определяется выражением:

Д- b J- с

г = О/(а + ) — + ) —)

1 п L— m t-i i i=i i

[' - И ]

I I

где Ь. = 1 - a , ^ cv = с .

Доказана теорема, что совместное ускорение многоуровневой

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

всех уровней этой системы и находится в следующих границах к

г = | | г* , rfn а г* < гТх ,

1 = 1

где r?ln, г?ах - минимальное и максимальное частичное ускорение уровня I; г* - промежуточное ускорение уровня I. Получено следствие о максимальном ускорении. Следствие 4. Если в многоуровневой системе отсутствуют накладные расходы и все уровни гнезда циклов являются параллельными, то система развивает максимальное совместное ускорение:

г - П ■

i = i

где п^ - количество процессоров на уровне I.

Основным элементом алгоритма СИНГАЛ является базовое правило (БП), которое позволяет вычислить ускорение для заданной ФП^ и структуры Sj_. В библиотеку БП "входит I*J правил, где I, J -количество используемых ФП и структур соответственно. В главе 2 построена такая библиотека. Часть библиотеки представлена в таблице 1.. Каждое выражение определяет rt j.

В таблице 1 в дополнение к ранее введенным обозначениям принято: w - число операций в одной итерации; q - величина развертки; / - число тактов, необходимых для реализации пакета связей коммутатором; t - время такта связи; t - затраты на синхронизацию; t - время одного такта процессора; 6 - коэффициент загрузки процессоров (СКе<1); S - удельный вес операций синхронизации; К - пропускная способность средств синхронизации; I - ширина параллелизма одной итерации; d - величина сдвига итераций в конвейере.

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

Алгоритм СИНТАЛ представлен ниже.

Табллтха I

Библиотека базовых правил

^^тип ^процес-ТИП \^СрОВ циклов ^^ 7ЫЖ окэд МКМД

- скалярный е2 е2

а1°2 , С2 , 4*2 «2 «2 т °2 , ■ Ъ'2

Еекторный е1 е1

е1п1 е1 2 1*2 К1 61П1е2 К1 &2 С2 52 1-а / / / 4*2 ' Ъ Ь

с кезависиммьм Еетвями е2 О«-* С ¿о е1

а+ /■ ■ / б0п ; к. к ^ с ^ о 61*Г2 т\ К1 л ■ г Г? К/ 2 *"'*>

IV * Г

. -V В-—*- ( "1 — 1 / ТГ>.0\1 71 ) л _ а' 5ггс0 ' а, к? £>*2/е0 М+В+С^+^-т-^-"'1 К1

Алгоритм СИНТАЛ

ВХОД: гнездо циклов произвольной формы глубиной К;

параметры всех циклов, п процессоров, набор типов процессоров, библиотека базовых правил. ВЫХОД: бинарная комплексная структура.

МЕТОД: ^ \Гпт>ат1г\пт*фт- фтггт пфгтт/тчгтпт гтлптюпрлпо тттта пиу'гпошшу

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

3. Для всех I = к - ? до I = 2, используя ББП, вычислить

для всех циклов } уровня:

для п - !. 2, ..., N и заполнить результаты в /-той

строке таблицы Т(Б1).

Установить новый тип структуры и перейти на

пункт 1.

По ТЛбЛИЩМ Т(З^) ,Т(32).....построить таблицу

У, где и содержится искомая структура. Профиль распределения процессоров находится обратным проходом )Т т.^лиц К к таблицам Т(Б^).

[п { г О*;}}.^ { Г О"}}}

■У ^ V < 1 > J J К V < , >

V < ,) >

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

Показано, что для внутренних циклов при определенных условиях лучшими характеристиками обладает структура со сверхдлинной командой (Ш¥-структура).

В третьей главе рассматриваются возможности метода СИНТАЛ для распараллеливания основных этапов задачи двумерного численного моделирования элементов кремниевых микроэлектронных структур. Обосновывается выбор

дрейфово-диффузионной модели явлений переноса заряда в полупроводниковой среде, приведены основные уравнения:

у • [ е >л/) } = р ,

где е - диэлектрическая проницаемость вещества; р - объемная плотность заряда; ц> - электростатический потенциал; д - заряд электрона Jn, - плотности электронного и дырочного токов; п, р - концентрации (плотности) электронов и дырок; йп, Я -превышение скорости рекомбинации над скоростью генерации для электронов и дырок соответственно; t - время. Далее приведены граничные условия и модели характеристик среды.

После алгебраизации на непрерывной прямоугольной сетке приведенная система решается численными методами. При использовании экономичных схем последовательного интегрирования фундаментальных уравнений на каздой итерации необходимо решить три линейные системы с' пятидиагоналыюй (в двумерном случае) матрицей.

Длд того, чтобы обеспечить условия применимости анализируемых методов решения систем линейных алгебраических уравнений (СЛАУ), в. уравнениях фундаментальной системы физики

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

Далее в главе проведено измерение параллелизма некоторых методов решения СЛАУ. Сначала рассмотрен метод неполного Ит-разложения Холецкого. Полученные оценки, свидетельствующие о наличии достаточно большого потенциального параллелизма данного метода, представлены в таблице 2.

Таблица 2

Результаты измерения параллелизма задачи для метода 1Ьт-разложения

Тип Ы: число процессоров

СТруК- --=-

туры 1 2 4 8 16 32

УЬШ 1.2 2.4 4.4 8.7 16.6 31.0

ОКОД 1.0 1.6 2.3 3.1 3.6 4.0

ОВД 1.0 2.0 3.7 7.2 13.9 25.8

Аналогичные выводы сделаны и в отношении Ь01т-разложения. Кроме указанных прямых методов исследован также метод сопряженных" градиентов с предобусловливанием при помощи неполного Ш-разложения (НФСГ). Полученные оценки (табл. 3) свидетельствуют

Таблица 3.

Результаты измерения параллелизма задачи для НФСГ-метода

Тин структуры N1 число про ц е с с 0 р 0 В

1 о 4 8 16 32

УЫУ/ ОКОД окмд ! .2 1.0 1 .0 2.0 1.4 1 .7 3.8 2.1 3.2 7.9 2.8 6.6 15.4 3.3 12.8 28.3 3.7 23.3

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

На основании проведенных исследований сделан вывод о предпочтительности прямых методов при решении задачи численного моделирования элементов СБИС на параллельных процессорах. В главе разработан эффективный метод решения СЛАУ с пятидиагональной матрицей, основанный на редуцировании исходной СЛАУ к системе с порядком вдвое меньшим. Такое редуцирование достигается путем преобразования с использованием проектора

«^.¿ьмм: .

Ьт Р>.

где I - единичная матрица, А - матрица исходной СЛАУ, р^, I = 1, 2, ..., к - набор ¿-сопряженных векторов, определяемых из априорной информации о структуре матрицы А. В дальнейшем преобразованная система решается методом 1Ш,т-разложения. Этот подход позволяет почти вдвое сократить вычислительные затраты на решение СЛАУ, поскольку ширина полосы матрицы в результате редукции не изменится. Проведенные исследования свидетельствуют о том, что потенциальный параллелизм -данного метода не становится меньшим, чем в случае традиционного метода Холецкого (см. таблицу 4).

Таблица 4.

Результаты измерения параллелизма задачи по разработанному методу для матрицы А

Тип структуры И: число про ц е с с о р о в

1 2 4 8 16 32

ГШ 2.4 4.8 8.8 17.2 33.2 61.8

ОКОД 2.0 3.2 4.6 6.2 7.4 8.0

ОВД 2.0 ' 4.0 7.4 14.4 27.8 51 .6

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

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

В четвертой главе производится детализация базовых правил, выведенных в § 2.4, программная реализация алгоритма СИНТАЛ и его экспериментальная проверка на тестах и задачах многомерного моделирования элементов СБИС.

Показано, что базовое правило для УЬШ-структуры включает наибольшее количество параметров и поэтому является в некоторой степени общим случаем для других структур: ОКОД, ОКМД, МКМД.

Для БП УЫ1У принципиально важной является зависимость величины ускорения г от длины базового блока ш. Такая зависимости получена на основе анализа статистических данных в виде выражения

г = 1 + О.

Для БП УЫ(У введены новые формы скалярного (локального) параллелизма: ЛП1 (арифметико-логические операции), ЛП2 (обращение к памяти), ЛПЗ (индексные операции). Введена развертка итераций цикла. При выборе трасс учитываются затраты на компенсационные коды.

Получены выражения, учитывающие затраты на коммутацию в зависимости от числа процессоров и их типа.

С учетом всех указанных факторов разработана аналитика базового правила УХШ-структуры. Целью этих вычислений является определение длины базового блока I после распараллеливания и упаковки. В приведенных ниже выражениях приняты следующие обозначения: Н^ ' - ширина (-той формы локального параллелизма; - коэффициент пропорциональности; т - число операций в базовом блоке; п^ - число АЛУ для ЛПр -

длина ¿-той формы локального параллелизма; Ь - исходная длина базового блока.

Для вычисления I необходимо выполнить следующие действия:

й'1^ 1 * а,

Я*2'-: 1 + ,0

/Г^ ! / ,,,

1'3

Vй = Ъ ; иначе г'" = Г^-1'1

I П, I

1?(}Г\Ш.пг) 1С2> = I ; иначе 1<2> = р—-]'1'

К

1¥(й*.Шлъ) 1(3> = Ъ ; иначе !<3> I = тах(1ш, г'21. 1Ф)

-

Аналогичные построения произведены и для других структур процессоров.

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

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

В главе 3 проводилось измерение потенциального параллелизма наиболее вычислительно трудоемких этапов численного моделирования элементов СБИС. В главе 4 осуществлено измерение параллелизма задачи моделирования в целом. С учетом слабой физической зависимости некоторых параметров твердотельных элементов друг от друга представляется возможным решение двух уравнений непрерывности одновременно. Экспериментально с помощью пакета СИНГАЛ показано, что в этом случае обеспечивается большой уровень параллелизма, при . атом наибольшее ускорение обеспечивает структура типа УХШ.

Текст программ пакета СИНТАЛ и описание представления данных и результатов даны в приложении.

ЗАКЛЮЧЕНИЕ

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

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

1. Сформулировано понятие персональной суперЭВМ как ЭВМ с параллельной структурой оборудования и традиционной последовательной системой программирования. Показана необходимость и возможность реализации ПС ЭВМ. Наиболее перспективными в отношении технической базы' ПС ЭВМ являются МЗС-микропроцессоры с программируемым параллелизмом.

2. На основе анализа известных методов моделирования структур ЭВМ и требований к методу автоматизированного синтеза структур ПС ЭВМ определен состав и уровень моделей, в совокупности представляющих вычислительную систему на базе ПС ЭВМ. В частности, показано, что наиболее предпочтительной моделью задачи пользователя является модель, характеризующая состав и параметры форм параллелизма этой задачи. Такая модель делает возможным прямое измерение характеристик классов задач или отдельных задач.

3. Показано, что основным объектом распараллеливания как правило являются гнезда циклов. При этом, в состав данного поля вложения входят как программные, так и служебные аппаратные циклы. Для всех этих циклов используются единые принципы распараллеливания. :

В соответствии с многоуровневой структурой задачи предложена* многоуровневая модель вычислений на базе ПС ЭВМ для - оценки ускорения вычислений, связывающая измеренные параметры задачи и характеристики структуры оборудования. Модель. . являетсй теоретической основой метода СИНТАЛ, необходима, для аналитической оценки различных свойств системы и допускает различную степень детальности рассмотрения.

4. Предложен метод СИНТАЛ для автоматизированного .синтеза структур параллельных процессоров в зависимости от класса решаемых задач. Основой метода являются базовые правила для описания свойств одноуровневой системы и алгоритм оптимального распределения заданного числа процессоров "по ■ уровням гнезда циклов. Конечная структура параллельной системы может быть однородней или неоднородной. Наиболее предпочтительной является бинарная структура._

Метод СИНГАЛ является вычислительной реализацией многоуровневой модели системы на базе ПС ЭВМ.

5. Разработана и обоснована библиотека базовых правил для ряда ФП (БЕ(3, ВК, ВТ, КНВ) и структур параллельных процессоров (УШ\ ОКОД, ОКМД, МКМД). Каждое базовое правило по существу является элементом теории исследуемой структуры.

Библиотека базовых правил является открытой как в отношении количества правил, так и в отношении степени их детализации.

6. Эффективность метода СИНТАЛ проверена на классе задач многомерного моделирования элементов СБИС. Показано, что СИНТАЛ достаточно полно выявляет реальный параллелизм задачи. Этот параллелизм является достаточно большим и наиболее предпочтительной является структура типа УЬШ.

7. Произведена программная реализация метода СИНТАЛ. С этой целью разработаны способы представления входной информации, детализировано описание задачи (введены три разновидности скалярного параллелизма, учитывается длина базового блока, затраты на компенсационные коды и др.) и структуры (учтены затраты на коммутацию и синхронизацию).

Программный пакет СИНТАЛ проверен на тестовых задачах и задачах многомерного моделирования СБИС.

По теме диссертации опубликованы следующие работы:

1. Юнее М.Ф. Алгоритм СИНТАЛ для измерения параллелизма программ в САПР микроэлектроники / В сб. трудов межреспубликанской научно-практической конференции творческой молодежи "Актуальные проблемы информатики: Математическое, информационное и программное обеспечение", 18-22 мая 1992 г. /Мн.: Университетское, 1992.

2. Шпаковский Г.И., Мулярчик С.Г., Юнее М.Ф. (Сирия). Алгоритм СИНТАЛ для измерения параллелизма программ в САПР микроэлектроники // Вестник БГУ, Сер. физ.6 мат., мех., 1992,

* 3, с.