Введение к работе
Актуялт-.утпг-гь тема. Растущая сложность средств
вычислительной техники и изделий микроэлектроники, играющей решающую роль в ускорении научно-технического прогресса во всех областях народного хозяйства, стимулирует в возрастающей степени поиск новых путей решения и ведение обширных мероприятий в области проектирования микроэлектронных вычислительных систем (МЭВС). Микрсэлектронные вычислительные системы представляют собой сложные многокомпонентные иерархические системы. Под иерархичностью понимается то, что компоненты системы сами имеют сложную структуру. Причина затруднений работ конструкторов н разработчиков заключается в еще достаточно высокой доле неформализуемых операций в процессе проектирования и производства.
Развитие технологии, усовершенствование методов проектирования, увеличение потребности народного хозяйства в средствах вычислительной тєхїшки и мнкроэлектренных изделий требует разработки новых принципов проектирования.
Структурно-алгоріггмический метод проектирования МЭВС и его принципы, в частности принцип структуризации применим для проектирования МЭВС высокой сложности. Основными достоинствами этого принципа являются:, обеспечение максимальной надежности (отсутствие или минимальное количество внешних соединений) и шпитальная потеря быстродействия из-за задержек сигналов в линиях связи.
Разнообразие и большая номенклатура компонентов МЭВС, требует унификации''и' стандартизации ее конструктивных единиц. Определяющими факторами в оценке сложности, стоимости, сроков изготовления и эксплуатации конструктивов МЭВС, являются' их конструктивно-технологические особенности, достигнутый уровень унификации конструктивов и специализация их производства.
Объективной тенденцией развитая элементной базы
является повншешіе уровня интеграции, что приводит к
снижению уровня схемной, т.е. функционально-логической
унификации. Снижение уровня схемной' унификации ведет, в
свою очередь, к увеличению стоимости, сроков проектирования н
изготовления аппаратуры, расширяет номенклатуру
конструктивов, что повышает стоимость эксплуатации, снижает
ремонтопригодность аппаратуры. Поэтому, необходимо
разработать такие методы проектирования МЭВС, которые
заключаются в разбиении электрической схемы МЭВС на
функционально-законченные части разной степени сложности с
учетом требований по обеспечению высокого уровня схемной
унификации и организации их в виде типовых. '
Разбиение схемы МЭВС на функционально-законченные части обеспечивает независимость электрической проверки схем типовых конструкций, создает предпосылки для построения достаточно простой системы контроля работы машины и локализации неисправностей (отказов), упрощает стендовую контрольно-испытательную аппаратуру.
Таким образом, решение задачи разбиения, должно обеспечивать сокращение сроков проектирования; снижение стоимости проектирования, производства и эксплуатации; изготовление типовых кс«струкдий по независимым циклам; достижение высокой степени унификации и стандартизации узлов и элементов проектируемой МЭВС. Решение данной задачи основано на методах теории графов, в частности декомпозиции графов.
Пели и задачи исследования. Целью работы является решение научной задачи, которая заключается в исследовании и разработке оптимального метода, алгоритмов и программного обеспечения процесса разбиения микроэлектронных вычислительных систем различного уровня иерархии на основе декомпозиции графов.
Для достижения поставленной цели были ; решены следующие задачи:
анализ задач разбиения МЭВС на подсистемы и их оценка на Примере зарубежных и отечественных разработок;
определение метода и алгоритмов декомпозиции графов с точки зрения их использования при решении задачи разбиения;
- разработка оптимального метода и алгоритма декомпозиции
взвешенных графов и модификации алгоритмов дскомпозигщи
ие^фаентарованных графов; ,
- формализация и алгоритмизация процесса разбиения МЭВС;
- разработка алгоритмов разбиения МЭВСГ на большие
интегральные схемы в покрытая схем подсхемами;
.- разработка способа реализации организации процесса решения задач разбиения МЭВС в диалоговой шпелсктуалыгоЗ системе автоматизации проектирования {ДИСАП);
.-5-
- апробация предложенных методов и алгоритмов разбиения на
примерах.
OcHOBTITJft пттггяттгг п%.тг,гчпгі.т* ї "ЦгїїГТ".".
1. Способ формализация задач разбиения микроэлектрошшх вычислительных систем на основе методов теории графоі), теория множеств и программтіроваїпія.
1. Методы и алгоритмы декомпозипіпі графов для разбиения МЭВС.
3, Метод и алгоритмы решения* задач разбиения МЭВС с
различны? іл критерия?.!!!, сірзничсшіями и требояаіпіяші.
4, Алгорігтаьг реализаций функций разбиения;
формирование множества совместимых вершин; упорццочившшя
вериыш связности; формнроваїшя однотипных всрипш и выбор
вершин одного типа для организации фрагмента графа.
Объект и метоли исследования, Объектами исследований явились мпкраолектрошше вычислительные системы, т.е. функциональная п электрическая схемы элементов МЭВС различного иерархического уровня. Исследования проводились на основе теории графов, теории схем и моделей, теории множеств и программирован) ія.
Шучиад.ши&ша осповігих полученных результатов состоит в следующем:
предложены отнмалышй метод л алгоритм декомпозиции взвешенных графов, позволяющие осуществить разбиение вычислительных систем различного иерархического, уровня, и обеспечивающие минимизацию повторяемости схем ії висьшнх соединений между ними;
разработаны эвристические ачгоритмы разбиения МЭВС tta БИС и покрытия схем подсхемами, обеспечивающие проектирование МЭВС повышенной надеж»„ости, уменьшение паводок и времени задержки сигнала п цепях за счет минимизации суммарной длины соединения;
осуществлено формал.пованнос предсташіепис процесса и объекта разбиения микрегаектронных вычислите лип їх систем si их олемсігшоі: базы различного иерархического уровня;
определены основные функции разбиения МЭВС и раз nun алгоритмы их реализации;
предложен язык описания графовых объектов для ироскінроваїпш МЭВС.
Практлчлріжщеїшрсть работы определяется возможностью практического использования научных результатов при решения
задач функционального, схемотехнического и конструкторского проектирования лшкрозлектронной аппаратуры. Предложенные алгоритмы и программное обеспечение декомпозиции графов, разбиения МЭВС и, язык описания графовых задач позволяют исключить возможность снижения надежности МЭВС на этапе проектирования и ^производства, повышают уровень формализации конструкторской деятельности и могут быть использованы в составе диалоговой интеллектуальной системы автоматизации проектирования.
Реализация результатов работы. Основные результаты диссертационной работы переданы на внедрение ъ производственное объединение "Фотон". Алгоритмы и программное обеспечение разбиения микроэлектронных вычислительных систем с инструкцией для пользователя использованы при выполнении задач компоновки интегральных схем на печатных платах и при сборке больших интегральных схем на пластине. Годовой экономический эффект сосговляет 72,0 тыс. сум. Кроме того, результаты научных исследований используются в учебном процессе на кафедре "Проектирование я технология ЭВС" Таизкснтского государственного технического универсистета при подготовке инженеров-системотехников и инженеров-конструктороВ"технологов электронно-вычислите51ь-ных средств.
Апробапия работы. Основные положения диссертационной работы докладывались и обсуждались на конференциях и научных семинарах кафедр факультету электроники, автоматики и вычислительной техники ТашГТУ.
Публикации. Основные результаты диссертации опубликованы в 5-ти печатных трудах.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы. Работа изложена на 150-ти страницах машинописного текста и содержит 25 рисунков, 5 таблиц и приложение..