Разработка аппаратно-программных средств интеллектуализации систем автоматизации проектирования на основе методов теории графов тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Калиев, Айдархан Миралиевич

• Калиев, Айдархан Миралиевич
• кандидат технических наук
• 1993

Оглавление диссертации кандидат технических наук Калиев, Айдархан Миралиевич

Введение.

Глава 1. Современное состояние вопроса интеллектуализации систем автоматизации проектирования

1.1 Задачи САПР с точки зрения интеллектуализации.

1.2 Математический аппарат САПР (обзор).

1.3 Постановка задачи исследований.

Выводы по первой главе.

Глава 2. Формализация базовых задач автоматизации проектирования и методика их решения

2.1 Формализация обьектов автоматизации проектирования аппаратом теории графов.31;

2.2 Единая методика решения базовых задач

2.3 Модифицированный алгоритм решения базовых задач на примере распознавания изоморфизма графов).

2.4 Аппаратно-программные средства решения базовых задач (на примере распознавания изоморфизма графов).

Выводы по второй главе.

Глава 3. Инструментальные средства и принципа интеллектуализации систем автоматизации проектирования

3.1 Инструментальные средства интеллектуализации системы?

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

3.3 Структура и принцип функционирования Функционально-ориентированного процессора.,

3.4 Оценка эффективности аппаратных и программных.средств интеллектуализации системы.

Выводы по третьей главе.

Глава 4. Практическая реализация средств интеллектуализации системы автоматизации проектирования

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

4.2 Диагностический контроль топологии БИС и СБИС.

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

Выводы по четвертой главе.

Введение диссертации (часть автореферата) на тему «Разработка аппаратно-программных средств интеллектуализации систем автоматизации проектирования на основе методов теории графов»

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

Интеллектуальные САПР не могут формировать новые идеи, |!l) |1 ТО V0 ПрОМЯ опираясь на знания, базовые алгоритмы реые-ния проектируемых обьектов, технологий изготовления изделий, алфавит компилятора и параметры элементов систем позволяют проводить направленный поиск реиений.

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

1. Интеллектуальная система обеспечения системотехнических исследований (ИСОСИ);

2. Интеллектуальная сервисная система (ИСС),, для обеспечения работы пользователя в целом с системой проектирования и сохранения высокой надежности ее функционирования.

ИСОСИ обеспечивает проектировщика интеллектуальными средствами, для помощи в проведении системотехнических исследований и состоит в основном из:

- интеллектуальной системы программирования, системы проектирования, баз знаний:

- интеллектуальной систем!» проектирования сверхбольиих интегральных схем.

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

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

В диссертации исследуются и разрабатываются следующие задачи:

- анализ существующих методов, алгоритмов и систем автоматизации проектирования,

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

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

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

- аппаратная и программная реализация решения задач теории графов,

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

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

На у ч н а я н о в и ъ н а. Основными научными результатами работы являются разработка методшкпчш создания интеллектуальной САПР на основе единой методики решения.задач теории графов и единого входного языка описания обьектов различных предметных областей. Принципиальный вклад в развитии интеллектуализации систем автоматизации проектирования состоит в следующем:

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

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

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

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

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

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

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

Практическая ценность работы.

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

Реализация результатов работы. Основные результаты диссертации получены при- выполнении научно-исследовательской работы в лаборатории "ВТ и САПР" Института Кибернетики с ВЦ Академии наук Республики Узбекистан; для ре-сения проблемы диагностического контроля топологии БИС и .СБИС б радиоэлектронной промышленности. Инструментальные средства и программное обеспечение системы одобрены Художественно-тех--ническими Советами Акционерного объединения "ШОБУВЬ", Яаы-билского производственного торгово-кьейного объединения "СУДУ" и приняты на опытную эксплуатацию. Внедрение результатов работы подтверждено соответствующими актами.

А п р о б а ц и я р а 0 и т и. Основные положения диссертационной работы докладывались и обсуждались на следующих, конференциях и' семинарах: "Проблемы вычислительной математики и автоматизации научных исследований" (Алма-Ата,1308), IX Республиканская межвузовская научная конференция по математике и механике (Алма-Ата,1389), Международная научно-техническая конференция "Теория и методы создания интеллектуальных САПР в машиностроении и приборе,г. грс.с-нии" (Минск,.1332), IV Всесоюзная конференция "Методы и средства обработки сложной графической информации" (Нижний Новгород,1331), Региональная иаучно-мэтодичоская кпнференция &уяиь Ирллл и Сибири (Челябинск, 1989). III Международная научна техническая конференция "Интеллектуальные САПР" fТаганрог,1ПЗ^М и др. п у б л vi к о 11 и и. по т к ч >: дисс ертоции опу иликоват«'

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

Структура побьем работы.

Диссертация состоит из введения, четырех глав, заключения, списка литературы и прилоченил. Работа содержит 150 страниц текста, 55 рисунков, 4 таблицы, 10 листингов программ и списка литературы из 107 наименований.

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Калиев, Айдархан Миралиевич

ЗАКЛЮЧЕНИЕ I

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

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

2. Разработана единая методика решения: " базовых задач теории графов, • основанная на методе разбиения вершин графов на уровни.

3. Разработан единый входной язык описания графов в формальной квадратичной Форме. Предложена универсальная структура комбинированной записи графовой.информации с постоянными и переменными частями для обработки знаний и данных о различных предметных областях. !

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

Список литературы диссертационного исследования кандидат технических наук Калиев, Айдархан Миралиевич, 1993 год

1. Автоматизация проектирования технологических процессов в машиностроении./Корсаков B.C., Капустин Н.М. и др. •!. :Маииностр<., 1985. с.304.

2. Автоматизированное проектирование и производство в машиностроении./ Соломенцем Е.М., Митрофанов В.Г. и др. М.: Иашиностр. , 1988, 25G с.

3. Автоматизированная система проектирования; техноло-. гических процессов механосборочного производства. /Зарубин Г.М., Капустин Н.М.и др., М.: Машиностроение, 1979, 247 с.

4. Автоматизация проектирования в радиоэлектронике и гнчислительной техники. М: МДНТП, 1981. ■

5. Агафонов В.Н. Типы и абстракция данных в языках программирования : Обзор// Данные в языках программирования . М.: Мир, 1982. - с.' 265-327.

6. Алексеева Е.В. Гуленков В.Ю. Структурные принципы : технологического процесса в условиях ГПС.// сб. Гибкие произодственные системы . М.: Изд-во стандартов. 1987.

7. A.c. 596951 СССР, МКИЗ G06F 15/20. Устройство для пределения изоморфизма графов / В.М. Курейчик и др.- Опубл.1378 , Бюл. Н 9. .

8. A.c. 732879 СССР, ШЗ G06F 15/20. Устройство-для .феделения изоморфизма для ориентированных графов / А.Г. Коолев, В.И. Курейчик, В.А. Калашников,- Опубл. 1980,- Бил. IL.« •

9. A.c. 1305703 СССР, МКИЗ G06F 15/20. Устройство для •збиения графа на подграфы / В.М. Глушань,, В.М; Курейчик, И.

10. Левин, Л.И. Щербаков.- Опубл. 1987, Бюл. N 15. .

11. A.c. 596951 СССР, МКИЗ G06F 15/20. Устройство для | пределения изоморфизма графов. /В.М. Курейчик и др.- Опубл. .378, Бюл.Н- 9. . '

12. Байков В.Д., Смолов В.Б, Аппаратурная реализация лементарных функций в ЦВМ. Л.: Машиностроение. Ленинградско-i института, 1975, 96 с.

13. Баталов Б.В., Магрупов Т.М. Определение соответс-■ ия больиой интегральной схемы принципиальной схеме. // Микзлектроника. 1974 Bun. 4. с. 311.

14. Баталов D.B., Норенков H.H. . Системы тонатизированного проектирования СБИС // Микроэлектроника "Л т.9 вып. 5. с. 401-412.

15. Батицев Д.И. Оптимизация радиоэлектронных устойств. М.:Сов.радио, 1975. с.47.

16. Буданова Т.И.,Гудим И.В. и др. Структурная модель охнологического' процесса изготовления швейных изделий для винного проектирования потоков.// РС : Швейная 'промышленность, вып.З. М. ЦНИИТЗИ Легпром. 1983.

17. Васильев В.В., Радугин Е.А. Электронные модели за-14 на графах. Киев.: Паук, думка, 1987. 152 с.

18. Васин О.В. Алгоритм установления изоморфизма гра-// Алгоритмизация логического проектирования;дискретныхстройств. Киев, 1974, 168 с.

19. Вермишев В.Х. Основы автоматизации проектирования. Радио и связь, 1988, с. 280.

20. Вирт Н. Алгоритмы + структуры данных = программы: : р. с англ.- М.: Мир, 1985, 406 с.

21. Вирт Н. Язык программирования ПАСКАЛЬ // Алгоритмы организация решения экономических задач. М.: Статистика, :74, Вып. 3, с. 38-66.

22. Вирт Н. Алгоритмы и структуры данных ': пер. с игл. И. : Мир', 1989, 360 с.

23. Гридин В.II. Формализация средств лингвистического -оимодействия пакетов прикладных программ в комплексной САПР

24. Вопросы электроники. Сер. ЗВТ. 1984 N 3. с. ■9-145.

25. Гридин В.П., Сперанский С.Н. и др. Система реляци-мно-логического программирования КОНЦЕПТ,- ориентированная!надачи САПР //Докл. I международной научно-практической конвенции САПР СВТ . 89 .М. .

26. Гридин В.Н. Тенденции построения ^развития прог- ' '.мннотехнических средств автоматизации проектирована микроэтронной аппаратуры // Лекции школы -семинара по объемным тегралышм схемам . Тбилиси : ГПИ : 1988, с. 7-14

27. Гроувс С. Система взаимодействия меяду основным . оцессором и сопроцессорами стандартного интерфейса // .онтроника. 1983, N. 10, с. 66-71. •

28. Грувер К., Знинерс 3. САПР и автоматизация произтва. М. : Мир, 108?.

29. Гуткин Л.С. Методы оптимального проектирования.М.: но и связь, 1984. с.86.

30. Деньдобренько Б.IL, Малика A.C. Автоматизация труирования РЗА, И.: Высш. ^кола, 1980, 384 с.

31. Дхонс Дл.К. Методы проектирования. М.: Мир, 1986.

32. Диксон Дн. Проектирование систем: Изобретательст-анализ и принятие решений. М.: Наука, 1977, с, 243.

33. Евстигнеев В.А. Применение теории графов в прог-пфовании. // под ред. А,П. Ершова. М.: Наука. 1985. -352.

34. Замулин A.B. Типы данных в языках программирования; • -•.зах данных . Новосибирск : Наука, 1987. - 150 с. i

35. Зыков A.A. Теория конечных графов. Новосибирск, :3. 543 с.

36. Иванов Е.А., Певченко В.П. 0 паралельных вычисле-• на графах. // Кибернетика. 1981. Н 3. - с. 89-94.

37. Иванов Е.А. Паралельные алгоритмы на графах // Кинетика. 1981 - IL 3. с. 81-83.

38. Ильичев A.B. и др. Эффективность проектируемых •:ентов сложных систем. М.: Высш. школа, 1982. с. 106.

39. Интеллектуальные интегрированные САПР РЗА и СБИС. .: Наука, 1990. с. 165. . .

40. Интеллектуальные системы имитации./ Тез. докл. 6-й • ;но-метод. конференции 28-30 октября 1985 г., Новосибирск

41. Кабулов В.К., Гуськов Г.9., Магрупов Т.М. Концеп-ьное проектирование микроэлектронных вычислительных ктур и ситем. Ташкент.: Фан, 1989. с, 224

42. Казенное Г.Г. Структура, основные требованиями .:: :цнпы построения САПР микроэлектронных приборов. М.: Высш. • а. 1978

43. Казеннов Г.Г., Шепелев В.А., Попова Т.Н. и др. :см контроля топологии интегральных схем на базе мини-ЗВМпользованием дисплеев. В кн.: Микроэлектроника; Вып.,9. ' ов. радио, 1976.

44. Калиев A.M. Аппаратно-программные средства интел-.альной системы распознования изоморфизма графов // Модеи, методи и программные сродства управления организационно-технологическими системами / Сборник научных трудов. Алматн 1991

45. Карелин В.Н,, Миронов Б Л1. Алгоритм определения 'изоморфизма однородных неориентированных графов // Изв. АН СССР. Техническая кибернетика, 1975. IL 2.-е. 145-148.

46. Карапетян A.M. Автоматизация оптимального; конструирования ЭВМ. М.: Сов. радио, 1973. с. 382

47. КерниганБ., Плоджер Ф. Инструментальные средства программирования на языке Паскаль. М.: Радио и связь,: 1985 , - 313 с.

48. Кикуст П. В, Алгоритм распознавания изоморфизма графов и его применение б идентификации логических сетей // Автоматика и вычислительная техника. 1979., - Н 4 - с. ;М-27.

49. Князьков В.С., Волченская Т.В. Организация; аппаратных средств подд.-ркки САПР // ЛЭТИ, вып. 364, 1985, с. 40 ■46.

50. Конструирование Функциональных узлов ЭВМ на интегральных схемах / Под ред. Ермолаева. М.: Сов, радио,.1988.

51. Корячко В.П. и др. Теоретические основы! САПР: !'чебник для вузов. Знергоптомиздат, 1987. с. 400.

52. Краснощеков П.С., Петров А.А. и др. Информатика и ::роектироание. М-.: Знание, 1986. Сер. Математика, .Кибернетика. N 10. Г

53. Курейчик В.К. и др. Система электронного моделирования задач автоматизации конструирования. // Электронное ыо--олироание. 1384. т.О. IL 1. с. 16-17 . .

54. Курейчик В.К. и др. Специализированная вычислительная система для решения задач автоматизации конс-груирования. // Яоь'иннне методы конструкторского проектированы РЗА и ЗВА / Издат. Саратов. ун„та, 1983. с. 16-17.

55. Курейчик В.«. Королев А.Г. Об *одном подходе рас-.ознования изоморфизма графов // Кибернетика 1977 N—2. с. 82 •37 .• :. ,, • .:

56. Курейчик P.M., Королев В.П. Применение алгоритма зонорфизма графов для контроля схем БИС // Микроэлектроника.-.070. IL5 с. 400-400 . 1 ' Г

57. Курейчик В.М., Глуиань В.М., Щербаков Л.И. Комби-.-.торные аппаратике модели и алгоритмы в САПР. М.:; Радио изь. с. 214 i

58. Магруков Т.М. Автоматизация проектирования микроэлектронных вычислительных структур.//Техника средств связи, сер. Микроэлектронная аппаратура, 1982. Вып.КЗ).

59. Магрупов Т.М. Алгоритм плотного размещения менсое-динений монолитных Ги.льыих интегральных; схем// Вопросы кибернетики. Вып.58. Ташкент : ИК с ВЦ АН УзССР. 1973.

60. Магрупов Т.М. Графы, сети, алгоритмы и их приложения. Тапкент.: Сон,1900. с. 120.

61. Магрупов Т.К., Калиев А.М. Интеллектуальная среда для распознавания изоморфизма-, графов при автоматизации'проектирования // ИСАПР. Тезисы докл. 3-й Меад. научно-техн. кон-ссрснции/ Таганрогский радиотехнический ин-т. • Таганрог 1992. ' ' ,

62. Магрупов Т.М., Ариджанов М.К., Юсупов^ С.Ю". Разбиение цифровых устройств на Апльиие интегральные схемы// Вопроси кибернетики, вып. 110. Ташкент,. 1980. •

63. Методы разбиения схем РЗА на конструктивно* законченные части/ под ред. Морозова К.К. -М.: Сов. радио, 1978. -130 с.

64. Меликиг. Е.Х. Золотцева Л.В. и, др. Лабораторный г. л;: г и кум по технологии ¡звейных изделий. М. :Легпромбытиздат.~

65. КелихнБ fi.II., Курейчик В.М., Королев А.Т;. Решение задач контроля при техническом проектировании на основе рас п о ^ :м в а ни я из ом о р ф из ма графов// Материалы XXUI Республ. конф K"j::ac. 1977. с. 139-141. '

66. Мелихов А.П., Бернатейн Л.С., Корелин В.П. Об изо-¡:;.I :изме графов и конечных автоматах// Изв. АН СССР Технич. кибернетика . 1368. - !Н . - с. 128-134.

67. Мелихпн ПЛ., Бернштейн Л.С. и др. Применение гра-для проектирования дискетных устройств. М.:* Наука, 1974.

68. Мелихов А.!!. Бернштейн Л.С. и др. Об изоморфномпни графов.// Математическое моделирование и теория ¡ирических цепей. Run. 8". Киев. 1972. с. 288.

69. Морозов К.К. и др. Автоматизированное проектирова-:•: -нструкций радиоэлектронной аппаратуры . М.: Радио и1983 . 200 с.

70. Морозов К.К,.Одинцов В.Г. и др. Автоматизация про-ания конструкций РЗА. М.: Радио и связь,- 1983.

71. Мурога С. Системное проектирование ;сверхбольших етральных схем1: Пер. с англ. / под ред. В.М. Кисельнико- К.: Мир, 1982.

72. Нильсон 1!. Принципы искусственного^интеллекта . :. г.но и связь , 1985.- с.285.

73. Иукдихин В.Г., Беседин А.Л. Системы автоматизиро-проектирования . Киев .: Вища школа, 1984,

74. Сапокков К.А. и др. Решение задач методом-выделе-графе изоморфных подграфов // Автоматизации конструко проектирования РЗА и ЗВА. Пенза, 1977.- с. 12-19. >1. Селютип В.ft. Машинное конструирование электронных '. тв. И.: Сов. радио, 1977. 383 с.,, , .

75. Серова Т.Н. Разработка организационно-технологи--.оделой проептиропани^ чвейикх потоков./Автореф . дис.• •■»», ii 1 г| о о

76. Г» . I . tl , , 14 , 1 vMM> .а. Сечкин ft.В. , Гудин И.В. и др. Проектирование тех-оких процессов изготовления швейных изделий. М.: . :;тиздат. 1388. .

77. Скирута li.ft., Коммисаров О.Ю. и др. Системное; про;; .ние технолигических потоков в легкой; промышленности.ка. 1900.

78. Смолов В.Б.,!.одяхо ft .И. .Пузалков Д.В. Высоко про-не процессоры для вычисления элементарных функций. ССР. Приборостроение, Л.: ЛИТМО, 1983, с.30-34. Смирнов О.Л., Падапко С.И. САПР: формирование и гание проекмшх модулей . М.: Машиностроение,

79. ЭВМ fl—i*o томления; концепции, проблемы, перспективы./ пЬд ред. Т.Мото-ика; пер. с англ. М.: Финансы и статистика,; 1904.

80. Djavaherv !!., Osborne S. Modula 2f : fin Alternative to С for Sysler>is Prograaning// 3ournal of Pascal, Ada, and Modula 2 . 1ЯСП. U.5, N3. - p.47 - 52.

81. Hayuard D. -CoEpared Anatomy of the Programming Languagel Pascal and C// ACM SIGPLANiNotices. -1986. U.21.N5.-P. 50-601 " .107.,Turbo pascal reference manual.Borland1.ternational, IIIC. 1985. - 376 p. . ,l •

82. У .Т В Е Р I Д А Ю Генеральный директо1. Акционерного объединен^9:М9НЙТАЕ1п1. Ж&1 '19'33г1. АКТприема-сдачи научно-технической продукции на опытную

83. От предприятия Начальник технического отдела

84. От Института Кибернетики с ВЦ АН Республики Узбекистан

85. УТВЕРЗДАЮ Генз&ззт^^ш^директор Iфизводствен-гйного Ш"1. Аргинбаев 1993 г.1. А К Тприемки-сдачи научно-исследовательской работы в опытную эксплуатацию

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