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

ЛЕНИНГРАДСКИЙ ОИЕНА ЛЕНИНА И ОРДЕНА ОКТЯБРЬСКОЙ.РЕВОЛЮЦИИ ЭЛЕКТН)ТЕХНИЧЕСКИЙ ИНСТИТУТ имени В.И.УЛЬЯНОВА(ЛЕНИНА)

ОРГАНИЗАЦИЯ И ПРОЕКТИРОВАНИЕ СИСТЕМ ДЛЯ ЛОГИЧЕСКОГО МОДЕЛИРОВАНИЯ ДИСКРЕТНЫХ УСТРОЙСТВ ' НА ОСНОВЕ АВТОМАТНЫХ Ф-МОДЕЛЕ.Я . ' \

Специальность 05.13.13 - Вычислительные машины,

комплексы, системы и сети

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

На правах рукописи

Савин Михаил Васильевич

УДК 621.396.6.001.63

Автореферат

Ленинград 1990

Работа выполнена в Ленинградском ордена Ленина и ордена Октябрьской Вгволюиии электртехническом институте имени В.И.Ульянова (Ленина).

Научный руководитель - кандидат технических наук

Петров Г.А.

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

доктор технических неук Шендерович й.И. кандидат технических наук Борщевич В.И.

Ведущее предприятие укаяяно в решении специализированного совета.

Защита диссертации состоится " /3 " ¿¿И?/^ 1990 г. в .-/Р"^'час. на заседании специализированного совета К.063.36.12 Ленинградского ордена Ленина и ордена Октябрьской Революции электротехнического' института имени В.И.Ульянова (Ленина), по адресу: 197022, Ленинград, ул. Прф. Попова, 5.

С диссертацией можно ознакомиться' в библиотеке Л'ЗТИ.

Автореферат разослан ". 'С2> " <.-¿¿¿1^ 1990 г;

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

Анисимов А.В.

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

Актуальность проблемы. Непрерывное совершенствование технологии СБИС сделало возможным создание все более сложных изделий вычислительной техники. Проектирование современных СБИС и систем на СБИС становится чрезвычайно трудным делом. Несмотря на быстрое развитие автоматизированного проектирования, в настоящее время методы автоматизированного проектирования наиболее хорошо разработаны для областей, связанных с технологией производства, то есть этапа технического проектирования систем. В отличие от этапа технического проектирования, этапы системного проектирования и логического проектирования выполняются до сих пор классическим способом, который базируется прежде всего на опыте и знаниях проектировщиков. Тщательная проверка, логических функции проектируемого обьекта в самом начале его создания имеет особую важность, так как выявление ошибок на более поздних этапах процесса проектирования может потребовать дорогостоящих переделок проекта. Стоимость одного изменения в СБИС при налаженном производстве оценивается в 300 - 800 тысяч рублей. Одной из наиболее трудных задач в "процессе проектирования является подтверждение правильности. (верификация) проектных, решений предъявляемым требованиям. 3 настоящее Бремя основным методом подтверждения правильности проектных решений является моделирование. Стоимость логической проверки проекта обьекта моделирования быстро растет с увеличением его зложности.. Кроме того, если проектировщик в дополнение к стандартен процедуре проверки обьекта захочет проверить его более тщательно, то стоимость, моделировзния возрастет пропорционально. В результате действия факторов, определяющих увеличение стоимости юделирования, сложилась такая обстановка, в которой затраты ¡декваткой проверки принимаемых решений на универсальных ЭВМ оие-швается десятками тысяч часов процессорного времени.

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

Широкий диапазон требований, предъявляемых к аппорапннм сред-

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

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

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

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

- обзор существующих систем логического моделирования;

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

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

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

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

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

''Ночная'новизна исследовании оостоит в том, что:

'доказано,! что задача декомпозиции моделируемого объекта

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

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

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

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

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

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

Реализация и внедрение результатов работы. Полученные в работе результаты использованы в работч/. Центра автоматизации яаучных исследований и метрологии АН МОСР, связанных с проектированием специализированных процессоров и устройств, используемых в аппаратуре KAiMAK, и позволили повысить качество и наде;к-юсть проектируемых комплексов, что подтверждается соответствую-дим актом о внедрении.

Апробация работы. Основные научные результаты диссертацион-юй работы обсуждались на Всесоюзной школе-семинаре " Рзспярал-1еливание обработки информации" (г. Львов, 1987 г.), а также на шучно-технических конференциях профессорско-преподавптельско 'о состава ЛЭТИ имени В.И.Ульянова (Ленина) (г. Ленинград, 1987 - 1989 гг.)

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

Структура и объем работы. Диссертационная работа состоит из введения, четырех разделов о выводами, заключения, списка литературы из IJ7 наименований. Работа содержит 121 страницы основного текста, 50 иллюстраций, и 8 таблиц.

ОСНОВНОЕ СОДЕШНИЕ РАБОТЫ

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

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

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

И качестве объектов моделирования в диссертационной работе выступают СЬИС и системы на СБИС, для которых приводится классификация по способу их реализации. Анализ способов реализации объектен моделирования позволил сделать вывод о возрастающей роли г.олу заказных (¿БИС на мировом рынке. Основными объектами моделирования в роботе предполагаются полу заказные СБИС о стандарты.«! ячзйканл. а также смлеьи in их ochote .

Выбор моделей оазолых ячеек объекта моделирования является и íóoj.ee кригичесьим моментом пои разработке средств логического 1!оделмровлн'.1Я. .Дело в тон, что в йгвмсимооти от рягме

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

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

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

С архитектурной точки зрения СЛМ можно разделить на следующие типы:

- Функционально-распределенные;

- Конвейерные;

- Параллельно-конвейерные;

- Параллельные;

- Матричные-

Анализ архитектурных и структурных решений существующих СЛМ позволил выделить ряд определяющих принципов их организации:

- модульность вычислительных ресурсов;

- конвейерная обработка алгоритма моделирования;

- параллельная обработка алгоритма моделирования;

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

- аппаратная реализация моделей объекта моделирования.

Сравнивая существующие в настоящее время СЛМ можно оделать .

вывод о том, что наиболее быстродействующими являются СЛМ с параллельной -и матричной архитектурой. Большие размеры созременных ооьёктов моделирования приводят к необходимости реализации оперативной памяти большого обьема с широким словом. Реализованная СЛМ с матричной архитектурой 'ААР-Х позволяет моделировать обьекты

используя только нулевые задержки, что затрудняет проверку моделируемых объектов с требуемым уровнем безошибочности.

Во втором разделе диссертационной работы уточняются задачи

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

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

1) ведущая ЭВМ осуществляет разделение обьекта на отдельные части;

2) ведущая ЭВМ преобразует формат описания моделируемого обьекта в формат СП;

3) ведущая ЭВМ осуществляет начальную загрузку программной модели • обьекта и исходных данных в поле СП;

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

5) в поле СП осуществляется параллельное моделирование' разделен. ного между СП обьекта моделирования;

6) ведущая ЭВМ считывает результаты из СП; .

7) ведущая ЭВМ преобразует данные из формата СП в формат описания обьекта моделирования;

8) ведущая ЭВМ осуществляет анализ полученных результатов моделирования.

Анализ функций, выполняемых р.зличными частями СЛМ, позволяет выделить наиболее значимые о точки зрения их влияния нэ длительность, цикла моделирования: разделение обьекта на отдельные части и организация параллельного моделирования в г.оле СП.

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

- провести анализ задачи разделения прогрннмиоЛ модели обьекта моделирования на отдельные чг.сти и рпзрпоотять алгоритмы для решения этой зэ~ чн;

- исследовать зависимость быстродействия СЛМ от структуры КС поля СГ1;

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

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

Решение задачи декомпозиции представляется в виде м?трицы:

У=11^11,

где _ Г\ -если модель £-й ячейки выполняется в ^ -м СП

~ (0 -в противном случае.

В качестве показателя эффективности СЛМ используется максимальное В1«мя завершения моделирования 7~= иДт

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

моделир>иония обьекта на к -ом варианте декомпозиции, а £ это число рассматриваемых вариантов декомпозиции.

Поскольку задача нахождения матрицы У связана с перебором варизнтов необходимо оценить ее сложность. Показано, что в общем случае для задачи декомпозиции справедлива следующая теорема: Задача получения оптимальной декомпозиции обьекта с целью миниыи-. заг.ии циклов моделирования для СЛМ, содержащей два СП при их сбалансированной работе является МР -полной. Теорема доказано путем сведения задачи о ранце, которая как изьестно является А/Р -полной, к задаче декомпозиции. Для М -процессорной СЛМ аналогичным образом доказано следующее следствие из зтей теоремы: '¿адача получения оптимальной декомпозиции ооьекта о целью минимизации цикла моделирования для М -процессорной СЛМ при соалансироьаь-ной работе СП является НР -полной. В работе также доказана следующая теорема: Верхняя оценка сложности декомпозиции определяется выражением = Я*1 , где М - число ячеек в объекте.

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

Для разработки алгоритмов декомпозиции обьекты моделирования разделены на два класса - однородные и неоднородные обьекты. На основе модели маосового обслуживания вида М/М/Х/М для однородных объектов выведено выражение для определения оптимального числа СП при известных характеристиках обьекта моделирования: Мопт = min {Me,t, mJ ,

где f-№(fl/-0, £ = Juys'p , J>=P/W,

i - количество условных единиц времени, необходимых для моделирования ячейки в СП;

V - число ячеек в обьекте;

р - вероятность генерации t -й ячейкой .запроса за данными к

J -й ячейке;

- среднее время обслуживания запроса в локальную память СП; i/j*p- среднее время обслуживания одного запроса в КС;

Л - число запросов, сгенерированных в СП за единицу времени.

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

Третий раздел диссертационной рзботы посвящен исследованию влияния структуры коммуникационной сети на быстродействие CJIM. Рассматриваются три типа КС: CJiM с шинной организацией как наиболее простая и дешевая; CJiM с полным матричным коммутатором как наиболее быотродействующля с точки зрения организации межпроцесс сорных связей; и кластерная организация CJIM как один из вариантов упрощения полного матричного коммутатора.

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

могут находиться в одном из двух состояний: I) состояние, находясь в котором СП не посылает запросы к КС на обслуживание; 2) состояние, в котором СП обменивается данными через КС. Состояния СЛМ классифицируются в соответствии с числом СП, запрашивающих данные, находящиеся в других СП.'Например, запись £(У.....»У»)

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

'У Л»е*=о ЗС^в

где о{у} -стационарная вероятность состояния у СЛМ.

Анализ полученной зависимости позволил сделать вывод о целесообразности использования общей шины в СЛМ когда число СП ^/б •

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

пР = < - ^>"1

где £ -вероятность обращения. СП к своей ЛП;

V -вероятность, с которой СП генерирует запросы в цикле.

Поскольку полный матричный коммутатор состоит из Ы2 связей, то для учет:: его сложности предлагается определять эффективность СЛМ как отношение - пропускная способность/стоимость ( стоимость Ы* условных единиц).

Полученная зависимость позволяет сделать вывод о том, что такая реализация рациональна при И^бЬ . Дальнейшее увеличение числа СП практически не увеличивает пропускную способность системы .

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

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

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

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

- небольшим количеством операций о плавающей точкой;

- большим разнообразием разрядности переменных (от -2 до 32 разрядов)

- частим использованием операций сравнения и ветвления (до 50% от общего количества);

- обилием булевых операций.

. Количественные показатели для характеристики природы вычис-

лений получаются используя способ измерения параметров программ, при котором выполняемые операции разбиваются на широкие, категории - присваивания, условные конструкции, и вызовы-возвраты из процедур. На. основе анализа, шести программ, написанных на языке ФОРТРАН, можно сделать вывод о том, что основная доля времени моделирования тратится на выполнение операций сровнения, ветвления, вызовов-возвратов из процедур. Другой класс измерений' с я-зан с типами операндов, используемых в программах логического моделирования. В этой связи с архитектурной точки зрения представляют интерес следующие наблюдения:

- большинство констант в программах имеет небольшую'разрядность (не более восьми разрядов);

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

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

X: =&Тч)/к>0 ,

Т.

/у -относительное время решения * -й задачи на J -м наборе, выраженное в тактах;

А/) -число команд в ./ -м наборе;

К -число задач в контрольном множестве.

В результате процедуры псевдослучайной селекции в набор команд СП вошли 2Ц команды, в том числе II команд арифметико-логической обработки типа "регистр-регистр", 10.команд управления, 2 команды обмена о памятью и пустая команда. На базе полученного набора команд разработана структура СП моделирования, которая имеет следующие отличительные особенности:

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

- использование тегированных данных;

- разделение Памяти данных на две части с синхронным чте-

нибм и записью;

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

- наличие памяти контрольных точек для вывода полученных результатов моделирования в ведущую ЭВМ.

Использование тегированных данных и хранение данных в упа-- кованном виде позволяет уменьшить обьем требуемой памяти на 30 - 40% по сравнению с традиционно реализованной памятью.

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

V-^м» * з] (Упр -А/}I) ,

где £ ~ размер единицы исчисляемой информации памяти данных; ТМ- максимальное возможное значение времени моделирования; квант времени моделирования;

- максимальное возможное значение задержки;

~ означает округление до целого в большую сторону.

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

ТмсЗ = ¿К V* Ь) Л/* Мг М ;

где А/к - число команд, необходимых СП для моделирования одной ячейки объекта;

tк - среднее время выполнения одной команды в СП;

СО - среднее число ячеек обьекта у которых изменились знамени/ входных не ременных на одном тестовом наборе (выражается в % от общего числа ячеек в обьекте);

А/т - число тестовых наборов в тестовой последовательности;

А/Л - количество прогонов на одном тестовом наборе;

И/ - число базовых ячеек в объекте моделирования.

На основе 12 контрольных примеров, соде ряса щи х типичные элементы вычислительной техники (сумматоры, счетчики, комоинацион-ные .схемы), показано, что повышенна быстродействия моделирования по сравненью с программно-! рсзлпзаииеи з системе моделирования "/'(•:етиснаходится в пределах 100 •- 500 ртз, в зависимости от т'/па моделируемой схемы;

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

В диссертационной работе получены следующие основные научные и практические результаты:

1. Доказано, что задача декомпозиции моделируемого обьекта для параллельной многопроцессорной СЛМ является А/Р-полной, и имее? сложность 2*** .

2. Получены аналитические выражения для определения оптимального количества СП в СЛМ при моделировании однородных объектов в зависимости от связности и размеров обьектов.

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

Исследовано влияние структуры КС на эффективность СЛМ. В частности, при помощи марковской модели исследована организация СЛМ с общей шиной; при помощи полученных аналитических выражений исследованы СЛМ с полным матричным коммутатором и СЛМ с кластерной организацией. Результаты исследований показывают, что для СЛМ с общей шиной рост быстродействия с добавлением СП ограничивается 16 процессорами; для СЛМ с полным матричным коммутатором рост эффективности системы наблюдается до 64 процессоров; для моделирования обьектов больших размеров при числе СП больше 64 предлагается использовать СЛМ с кластерной организацией.

5. Разработана архитектура спецпроцессора моделирования, ориентированная на эффективное моделирование обьектов, описанных при помощи Ф-моделей. Получены аналитические соотношения, позволяющие выбрать оптимальный обьем памяти СП при обеспечении баланса объемов памяти команд и данных. Используемые архитектурные решения позволили сократить число команд СП до 24; сэкономить 30 - ЧС% оперативной памяти по сравнению с построенной традиционно, а также .увеличить быстродействие в 100 - 500 раз по сравнению с программной реализацией.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Савин М.В. К вопросу о сложности декомпозиции проектов при их логическом моделировании в многопроцессорной системе / Ле-нингр. электротехн. лн-т им. В.И.Ульянова (Ленина). Л., 1989. -8 С. - Деп. в ВИНИТИ 04.08.89, № 5292.

2. Алмабеков М.1., Петров Г.А., Савин М.В. Об одном подходе к построению мультимикропроцессоршх систем с перестраиваемой структурой // Распараллеливание обработки информации: Тез. докл. Всесоюзной школы-семинара. - Львов: 1987. - С. 17 - 18.

3. Петров Г.А., Пузанков Д.В., Савин М.В. Об одном подходе к распределению ресурсов в функционально-ориентированных специализированных ВС // Проектирование функционально-ориентированных вычислительных систем: Сб. науч. тр. ЛГУ. - Л.; 1990. - С. 27-35.

Петров Г.А., Савин М.В. Микропроцессорные системы о функционально-гибкой архитектура // Изв. ЛЭТИ: Сб. науч. тр. / Ле-нингр. электротехн. ин-т им. В.И.Ульянова (Ленина). - Л., 19877 - Вып. 378. - С. 8 - 12.

Подп. к печ.' 16.05.90 М - 15606 формат 60 х 84 1/16. Офсетная печать. Печ.л'. 1,0; уч.-изд.л. 1,0. Тираж 100 экз. Зак.\№ 200. Бесплатно.

Ротапринт ЛЭТИ 197022, Ленинград, ул. Проф. Попова, д. 5