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

Академия наук Республики Узбекистан Научно-производственное обг-единение "Кибернетика"

Л '

и V г';

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

Аль-Ккш Слеман Али

УДК.621.3.049

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

Специальность 05.1Л.13. - "Вычислительные машины, комплексы, системы и сети".

Автореферат диссертации на соискание

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

Ташкс1гг-1.996

Работа выполнена в Ордена Трудового Красного Знамени Институте Кибернетики Научно-производственного объединения "Кибернетика" АН РУз.

Научный руководитель - доктор техишкс*31х наук, профессор Магрупов Т.М.

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

доктор технических наук, Нлшанбаев Т. кавдидат технических наук, доцент Гадбназаров С.Д.

Ведущая организация - Особое Конструкторское Бюро (ОКБ) при ПО "ФОТОН"

Защита состоится "1б" ^Ч 1996 года в ¡4 часов па заседании специализированного Совета Д. 015.12.21/1 в НПО "Кибернетика" АН РУз по адресу: 700125, г.Ташкенг, ул. Ф.Ходжасва, 34.

С диссертацией можно ознако?г»гп>ся в библиотеке института Кибернетики НПО "Кибернетика" АН РУз.

Афгорефератразослан '¿>6" ¿>7 1996 г.

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

Р.У. Рахматуллаев

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

- анализ задач разбиения МЭВС на подсистемы и их оценка на Примере зарубежных и отечественных разработок;

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

- разработка оптимального метода и алгоритма декомпозиции взвешенных графов и модификации алгоритмов декомпозиции неориентированных графов;

- формализация и алгоритмизация процесса разбиения МЭВС;

- разработка алгоритмов разбиения МЭВСГ на большие интегральные схемы в покрытия схем подсхемами;

разработка способа реализации организации процесса решения задач разбиения МЭВС в диалоговой шпелсктуалыгой системе автоматизации проектирования (ДИСАП),

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

ОСНОЛТТЫЛ Т1Л:ТП'1'Г1 Г1Г(7 л т.7? »то

------'-■—- I ■■ Ч.» .1—4 1' ЧИЧМ ^ УЧЩ1ИЛ

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

1. Методы и алгоритмы декомпозиции графов для разбиения МЭВС.

3, Метод и алгоритмы решения'задач разбиения МЭВС с различны? критериями, охраничепиями и требованиями.

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

Объект и метхпы исследования, Объектами исследований ¡томясь мпкроаЛектрошше вычислительные системы, т.е. функциональная и электрическая схемы элементов МЭВС различного иерархического уровня. Исследования проводились на основе теории графов, теории схем и моделей, теории множеств и программирован) 1Я.

Шдохздишшш основных полученных результатов состоит в следующем:

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

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

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

определены основные функции разблмшя МЭВС и раз пиы алгоритмы их реализации;

предложен язык описания графовых объектов для проектирования МЭВС.

ПРЯКШ!КШ1Я-ЖШР£1Ь работы определяется возможностью практического использования научных результатов при решения

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

диссергтационной работы переданы на внедрение в произвел спзешюе объединение "Фотон". Алгоритмы и программное обеспечение разбиения микроэлектронных вычислительных систем с инструкцией для пользователя использованы при выполнении задач компоновки интегральных схем на печатных платах и при сборке больших интегральных схем на пластине. ■ Годовой экономический эффект составляет 72,0 тыс. сум. Кроме того, результаты научных исследований используются в учебном процессе на кафедре "Проектирование и технология ЭВС" Ташкентского государственного технического универсисгета при подготовке инженеров-системотехников и инженеров-конструкторов-технологов электронно-вычислительных средств.

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

Публикации. Основные результаты диссертации опубликованы в 5-ти печатньес трудах.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы. Работа изложена на 150-та страницах машинописного текста и содержит 25 рисунков, 5 таблиц и приложение..

Краткое содержание работа.

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

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

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

Рассмотрены различные труппы методов и алгоритмов разбиения вычислительной структуры на подструктуры с учетом выполнения различных комбинаций критериев. Решение этих задач в большой степени зависит от правильного выбора метода декомпозиции графов. Сделаны соответствующие выводы по рассмотренным методам декомпозиции графов, и с этой точки зрешш исследованы задачи компоновки элементов различного иерархического уровня: элементов БИС, элементов гибридных интегральных схем, БИС на стандартных блоках, на вентильных матрицах, печатных планах. Сформулирована общая задача разбиения, задан муяьтиграф 1/=<Х, и>, требуется разбить на

отдельные часта ^ =< Л^ >, =< Хги% >.....¿к =< ХкМк >

так, чтобы число ребер, соединяющих эти части, было минимальным.

- -е-.

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

\/0.(Х.№.)с0(Х,(/) {¡Л'.(~ л. ± Ал], максимальное число внешних

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

т. стандартного корпуса БИС или БГИС):

УО.и.,и.)сОи,1/)[|и ¡Л^т.1 ^ова1ШЯ на разделшую /»1

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

графа (обусловлено конструктивными соображениями и условиями электрической совместимости).

Об актуальности разработки алгоритмов декомпозиции Графов может свидетельствовать достаточно широкий круг областей применен'« этих алгоритмов.

НаьЛолее интересным для реализации является метод дехомиозииин графов, на базе которого а построены алгоритмы, реализованные в данной работе.

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

На втором ^»апе, выполняется присоедините верпшн по различным критериям, таким как: вершины, обладающие максимальной связанностью, т.е. числом ребер сосдан;сощих данную вершину с остальными вершинами текущего подграфа; критерий сонотншюсга (вершины выбираются так, чтобы получить подобные подграфы разбиения). Данный метод

обладает, тем преимуществом, что он оперирует не отдельными

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

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

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

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

Предложен метод оптимального разбиения взвешенного графа. Граф в определяется как ссЕскупксоть <Х,А>, где X

множество вершин и А - множество ребер -з.^. = (Х.,Х.) соединяющих некоторое, или все вершины (х.^х. е X). С каждым

ребром (х.^х.) е А связывается вес с.который может обозначать

длину данного ребра. . ' ^

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

е.. = е 5, то это значит, что это ребро - одно из

составляющих сечения, или, что то же самое, что вершины х, и

х. находятся одна в У, а другая з Т. Если -е.. е то это значит,

что это ребро исключено из сечения, т.е. что и х. и х., оба

находятся лпбо в У либо з У. Если ±в.. <г 5 - это значит, что это

ч

ребро еще не рассматривалось. Таким образом, дается начальный граф С=<Х,А>, множество решений, представленное множеством

Б и затем определяется подграфом О =< Х,А >, где А = Л-{е..\+е.. еЭ}

со значением ребер с?. = а>, если -е.. еЭ п с?. » с... если -е.. 5* 5.

</ '1 ч ч ч

Вес ребер в сечении в дальнейшем будет обозначаться как

23 = е.., а через 2 будет означаться наилучшее приемлемое

Ч . , ■

решите в текущий момент.

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

В продессе работы метода во множестве Б добавляются со знаком "+" необходимые ребра, которые формируют приемлемое сечение. После каждого добавления из значения максимального

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

♦

решения. Если эта граница В > Z , то алгоритм выполняет возврат. Иначе проверяются ограничения размерности. Ваш это ограничение нарушено, выбирается новое ребро для увеличения в Б, вычисляется новая нижняя гргшшхп и тд.

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

Пусть е.. = (х., х.) - ребро с (+ -ом) в Б. Тогда в любом решении вытекающем из Б х.еУ и х.еУ, или наоборот. Следовательно, если рассматривать веса ребер графа О^ как

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

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

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

В = тах{Ф..1в.. 51 IГ ч

Однако для нахождения максимума по этой формуле не нужно рассчитывать каждый полсокптелытай член множества 8.

Если С?.. - сечение, соответствующее потоку Ф.. и ребро е . - (х входит в О., (т.е. х находится з одном подграфе,

аЬ а о // а

и хь - в дротом, образованным сечением <? ), то нет

необходимости вычислять максимальный поток, так кок <} . <£?..

аЬ Ч

и следовательно, ФаЬ < Ф... В общем случае бывает необходимо

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

Более того, сели па какой-то стадии (до того как будет

получено окончательное значение) значение В становится таким, *

что 2 +В"г'£ , следует прекратись дальнейшие вычисления а выполнить возврат. Это значит, что значение мпкеиммыого

потока Ф.. из к, в х. достигаете,! увеличенгем текущего потока, то Ч I I

нет необходимости продолжать дальнейшие действия, если

7. +0.2:7*. ' V

Если дерево выходит за границы, то производится возврат, т.е. последнее ребро, введенное и Г> как положительны» »иен, меняет сиой знак (исключается из сечения). Таким сЦмзоч в общем случае некоторые члены Б - огр.пимелша и .может 6.л;,

определен граф ЛГ,/1 '>, т'Дс

Ц/Ч-е -е,7е5!

-я-

0' состонг из одной жш более связных компонент, и все

S '

верпшны в пределах одной компоненты, должны принадлежать (по определению Og') либо Y, либо Y\ Так, если наибольшая

компонента, допустим 0Q, имеет п^ вершин с nQ > U, то на

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

В следующем случае применяется более мощный тест по ограничению размерности.

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

S) следующее ребро е... Выбор следующего ребра естественно ч

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

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

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

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

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

Рассмотрим проектирование какой-либо структуры 3. на основе совокупности данных, математической модели структуры /4(5.) и алгоритма проектирования А. с тп'пвд "»рения автоматизации проектирования.

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

модели и алгоритмов проектирования, конкретной структуре Б.

соответствует индивидуальная математическая модель М(5.) п

1щгцп5идуальный алгоритм А..

Такой подход целесообразен только при решении весьма

сложных задач, когда разработка модели М(5.) п алгоритма А.

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

проектирования выбирается метод М(3.) из системы методов и используется индивидуальный алгоритм А., егла в алгоритм

входят конкретные параметры и другое дашшс Я. Дальнейшее

повышение уровня системности средств обсспсчлгия автоматизации проеитнровшшя связано с унификацией алгоритмов проектирования. Так, для унифицированной модели М(.?) может быть создай унлфицировшишй алгоритм А. Иаивыс1Ш1м уровнем унификации будет исп .-люоваоте модели М(Б) и унифицированного алгоритма Л, независимо от даштых о

проектируемом объекте 5.. В этом случае содержание алгоритма

Проектирования зависит от математического содержшпш

решаемой задачи и свойств модели М(Б). Данные Б. влияют не на

содержание Л, а лишь на результат решения задачи.

При этом проектиропшшс включает следующие процедуры: 1. Создание системы методов, охватывающей все этапы процесса проектирования структуры;

2. Создание системы алгоритмов решения задач данной иерархии проектирования;

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

В иерархической системе проектирования любой структурный уровень и этап проектирования проектируются одинаковым:: средствами. ^Рассматриваемая на любом уровне

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

имеет один и тот же прообраз 8, адекватный реальному объекту;

при этом 3. содержит лишь некоторую часть от Б. В моделях

различаются структуры трех типов: множество элементов самой структуры й; множество атрибутов Р; множество К отношения между элементами и атрибутами.

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

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

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

Прл проектировании совокухшость элементов структуры представляется в вице множества S совокупность

атрибутов F(S)= .....1-J структуры и совокупность атрибутов

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

подмкожестза R(s.) отношений между s. и другими элементами

S, подмножества R(F(S)) и Iï(F(,s.)) отношений между F. И

другими атрибутами F(S) н F(s.) и подмножества R(.F.(S)) п

R{F.{s.)) отношений между элементами и другими атрибутами стругсгури. Для повтлиения эффективности проектирования необходимо определить возможности вхождения s. е S в

иодмножеогао Sv с S элементов, обладающих заданными

А

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

В данной работе рассматривается алгоритм разбиения схемы М5>ВС на БИС, который в комплексе решает как задачу минимизации ггисла типов БИС, так и числа соединений между ними.

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

F=L + h.B,

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

2. Критерий для количественной оценки изменения

внешних связей А1. ]-го БИС (обозначим его имеющего т^

ФУ п -- 1,2,....т^, прь. введении в него ФУ А., имеющего а. внешних связей:

т1 п = I

где д^) определяет число соединений между ФУ А{. и

3. Критерий для оценки общего количества внешних связей

)-го БИС содержащего т^ ФУ, =

определяется как

0= X У-Л1 1 ¿Д (3)

л = 1 >3 = 1 + 1 г

где ( ¡'^р о определяет число связей между п-м и у/-м ФУ

БИС (2и1 я

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

- орл ентир ованный граф, сопоставленный схеме МЭВС п соответствующий уровню решения задача разбиения;

• ограничения, соответствующие уровню разбиения (для уровня БИС - общее количество вывалов корпуса Ьм, допустимый уровень интеграции в пересчете на допустимое количество ФУ вкутрн ЕНС тм, максимальное число БИС б^, на котором

должен быть реализован МЭВС).

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

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

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

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

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

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

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

- хорошие эксплуатационные параметры и условия (удобства в эксплуатации, требуемое машинное время, занимаемая оперативная память и др.);

возможность пополнения новыми программными компонентами (модулями);

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

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

С этой точки зрения рассмотрены отдельные вопросы для организации ироцесса декомпозиции МЭВС:

V. Создан язык описания графовых моделей МЭВС различного иерархического уровня и предложена структурная схема описания графовых объектов в системе ДИСАП.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

2. Разработаны алгоритмы реализации основных функций декомпозиции графов для разбиения МЭВС: формирования множества несовместимых вершин, упорядочивания веришн связности, формирования однотипных ПерпВДН П вибср ЗСршинЫ одного 1ииа для оргашпации фрагмента графа.

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

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

5. Предложены способы формализации и алгоритмизации задает разбиения МЭВС с помощью теории графов и множеств

6. Разработано программное обеспечение п виде подсистемы разбиешш вычислительных систем, которая предназначена для организации вычислителышгх процессов задачи разбиения МЭВС и их эле'-ентт/ой базы и позволяет рзепшрпть возможности проектирования при моделировании И компоновке схем, снизить расходы и сократить сроки разработки МЭВС, <

7. Создан язык описания графовых моделей МЭВС различного иерархического уровня и предложена структурная схема описания графовых объектов в системе ДИСАП.,

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

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

проектирования в связи со сложностью разрабатываемых обт^г" .

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

схем на пласпше. Годовой экономический эффект составляет 72,0 тыс. сум.

Внедрение результатов работы и основных тучных положений не только существенно упрощает решение поставленных задач, но и экономит'значительные материальные ресурсы, в частности, сокращение сроков компановки в 4 раза, и улучшает ка^ство проектирования, ориентировочно на 20!><?. В настоящее время результата научных и практических исследований используются в учебном процессе на кафедре "Проектирование и технология электрогшо-вычислителышк средств" Ташкентского государственного технического университета при подготовке инженеров системотехников и инженеров конструкторов-технологов электронно-вычислительных средств. Основные положения диссертации опубликованы в следующих работах;

1. Аль-Киш С А. Алгоритм типизации и покрытия микроэлектронных вычислительных структур. Узбекский журнал "Проблемы информатики и энергетики". Ташкент 1995г, No 3-4. с. 58-60.

2. Аль-Киш С А. Метод оптимального разбиения графов. Узбекский журнал "Проблемы информатики и энергетики". Ташкент 1995г, No 5-6. с. 82-85.

3. Магрупов Т.М., Аль-Киш С.А. Оптимальный метод разбиения микроэлеклронных вычиелнтелышх структур. Тезисы докладов "Научно-теоретической и техш!ческой хонферггщии профессоров, преподавателей, аспирантов и научных работников", 3-7 октября 1995г. Ташкент 1995. с. 167. (Основные концепции и реализация метода принадлежит соискателю).

4. Магрупов Т.М., Аль-Киш С.А. Об одном подходе Проек.нрования микроэлектронных вычислительных структур. Вопросы кибернетики "Вычислительная техника в управлении". Ташкент 1995г. No 152, с. 146-153. (Соискателю принадлежат основные принципы подхода к проектированию микроэлсктрон-ных вычислитетелышх структур).

5. Рашидов А-А-, Аль-Киш СЛ. Способы архитектурных и схемотехнических решений однокристальных специализированных процессорных злемекгов для обработки цифровых сигналов. Ешларнинг изланишлари ва ишлаб чикаришшшг иешкболи, илмий махолалар туплами. Ташкент 1994г. с. 94-96. (Соискателю Принадлежат основные способы архитектурных и схемотехнических решений).

Кискача хулоса ГраФларни ажратмш асосида яикроэлектрон хисоблаш тизимларини булиш петоли. алгоритилари-ва програяпа та-ькиноти.

Аль-Кию Аля

^исоблаш тенникаси курилмаларини доимий ривожланиш< . ва улзрни тэр^ибий ^испларини такомиллашуви лойихзлаш. конструкиия-лаш ва ишлэб чккэрик жаренларини мукаяяэЛлзцггиришни тэлаб атади. Бу холат уз навбатила ликроэлектрон ^исоблэш '. тизинларики СИХТ) :<ар лил дэражэдаги тархибий циснлэри буйича янгм метод ■ вэ алго-ритмлэрни тзткил эткшни таказо килади. Бу урянда ЧХТ-ни -тархибий кисплэрга, янги катта интеграл схемаларга,интеграл схепаларгз.мам-тикий элемент ва триггердзрга экрзтии ва улэр асоскда технологи* ва схемотехник жэраёнлэр'нм хиеобгэ олган цояа& функционал туг»-тмтэн сяемэлар у.осил килиш эсосий насаласи эчилади.

Берилган талабдарга пувофик МХТ-ни таркибий киспларга аж-ратиш, келгусида Фотошаблон, Фотооригинзя ва кристадяэрни ишбб, чикаришни енгиллзштиради. ,

Шу сабзбли уш6у ялиий иш НЗТ тзркибий' уиспяэрга будиши оп-типал метод аа алгоритнлариьи излают а блгншланган. Лрограя.-.а ташиноти орк,али улэр асосида олияган нати*.алар . -яхии, г.урсатхяч-ларга эгз булиб. Н^Т-ларни лойи^алашла са-пылав чи^ариола- асосий опил хисобланади.

Optimum approch, algorithms and software for partitioning microelectronic computing system on the ground of graphs's decomposition.

Alkeesh Sleman Ali

The constant development of the. computer technology and designing its composition parts demands intensification of construction and the process of production. Hence, it requires to organise new methods and algorithms of composition parts on the different degrees of microelectronic computing system CMCS3. Then.. partitioning the HCS's composition parts, VLSI. logical element and triggers and on this basis technologic processes, production of finished functional scheme is the basic problem. From these given things it makes easier to partition circuit on the composition» parts, and to produce ' the crystall and photooriginal. That why scientific work of MCS assenble unit to optimal method and algorithms investigation ordain, software behind their taking basis' result with a high resolution, to product and planning KC5'S basic reasons.

ЬСОМЛХОМЛГЛ ТОПШИРПЛДИ 6 ft.

посишгд 1>у.\<:.м этилуш С СЗ 96 л. когоэ

БПЧПМН №xü-l 1/16. ОФСЕ1" ЫН'.МА УСУЛ11. ДАЛОИИ ¿'С НУСХД. 1>ук.)|»гмд jo

y.s р од <к)1ы:и11пнкл» ппчв <;пгл к.имшлп

К! :r.i: PI Il-ч 11КЛ 111 ¡С 11И У il 1ППИГ ЫК.МАХОПЛСНДЛ

.401! ЭПШ All, 700Ы.Ч. rc)!(IKi:HI" ХГЖ.-Ш! КГЧ\Г11Л4 УИ.