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

• Сухарев, Андрей Валериевич
• кандидат технических наук
• 2003

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

Введение.

1. Анализ алгоритмов компоновки ТС АСУ.

1.1. Постановка задачи и критерии компоновки ТС АСУ.

Выводы.

2. Общая характеристика алгоритмов компоновки ТС АСУ.

Выводы.

3. Алгоритмы оптимизации исходных схем соединений элементов в ТС АСУ.

3.1. Алгоритм оптимизации исходной схемы соединений путем минимизации числа ребер получаемого графа.

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

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

Выводы.

4. Разбиение графа схемы соединений на части.

4.1. Определение степени близости расположения вершин на графе

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

Выводы.

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

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

5.2. Программная реализация процедуры компоновки, редактор принципиальных схем FreeStyle Schematic

5.3. Пример компоновки элементов схемы в узлы (разрезание схемы) в редакторе FreeStyle Schematic.

Выводы.

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

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

По уровню организации разработки, масштабам проектирования, производства и эксплуатации АСУ специального назначения являются одними из самых сложных технических систем, созданных человечеством. Общий срок разработки составляет 7-10 лет, а период эксплуатации достигает 20 и более лет. В разработке, изготовлении и эксплуатации участвуют десятки специализированных научно-исследовательских и промышленных предприятий.

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

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

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

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

4. Высокие функциональные и массогабаритные показатели.

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

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

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

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

Актуальность работы подтверждается проведением НИР и ОКР в рамках программ:

- федеральная целевая программа «Российсике верфи»;

- федеральная программа «Российская электроника»;

- межотрослевая программа «Координация деятельности в области промышленной автоматизации и системостроения»;

- программа Госстандарта РФ «Базовые несущие конструкции, печатные платы, сборка и монтаж электронных модулей».

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

В соответствии с этим в работе ставились и решались следующие задачи:

- анализ методов компоновки ТС АСУ, формирование объективной оценки качества результата;

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

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

- разработка эффективного метода компоновки ТС АСУ;

-создание программных средств автоматизированной компоновки

ТС АСУ.

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

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

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

- в разработке эффективного алгоритма компоновки ТС АСУ.

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

Результаты диссертационной работы в виде программного продукта FreeStyle Schematic используются в ОАО «Техприбор», ФГУП ЦНИИ «Морфизприбор» и ОАО «Авангард». Кроме того, программой пользуются ряд частных лиц. Результаты диссертационной работы используются в учебном процессе Северо-Западного государственного заочного технического университета.

Основные положения диссертационной работы докладывались и обсуждались на 51-ой научно-технической конференции студентов и аспирантов ГУТ, г. Санкт-Петербург, 1997 г; 53-ой научно-технической конференции студентов и аспирантов ГУТ, г. Санкт-Петербург, 1999 г; 53-ой научно-технической конференции профессорско-преподавательского состава, научных сотрудников и аспирантов ГУТ, г. Санкт-Петербург, 2000 г; 11-ой международной научно-технической конференции студентов, аспирантов и молодых специалистов стран СНГ, г. Санкт-Петербург, 2000г; Юбилейной научно-технической конференции «Связисты СПб ГУТ и телекоммуникации XXI века», г. Санкт-Петербург, 2000г; II 1-ой международной научно-технической конференции студентов, аспирантов и молодых специалистов стран СНГ, г. Одесса, 2001 г; 55-ой научно-технической конференции студентов, аспирантов и молодых специалистов ГУТ, г. Санкт-Петербург, 2001 г.; 1У-ой международной научно-практической конференции "Современные информационные и электронные технологии1', Одесса, 2003г.; 1-ой научно-технической конференции молодых специалистов ФГУП ЦНИИ "Морфизприбор", Санкт-Петербург, 2003 г.

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

Диссертация состоит из введения, пяти глав, заключения и списка литературы, включающего 81 наименование. Основная часть работы изложена на 108 страницах машинописного текста, содержит 20 рисунков и 8 таблиц.

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

Выводы

1. На основании проведенных исследований можно утверждать, что разработанный последовательно-параллельный алгоритм компоновки ТС АСУ, в основе которого лежит параметр отдаленности, позволяет получать качественные результаты как в случаях с сильно связанными группами элементов в исходной схеме соединений, так и в схемах с минимальным среднеквадратичным разбросом степеней вершин и с большим диаметром.

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

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

101

Заключение

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

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

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

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

4. Алгоритмы и модели, полученные в результате работы, были использованы при создании программного комплекса разработки принципиальных схем FreeStyle Schematic, которая проходит опытную эксплуатацию в ОАО «Техприбор», ФГУП ЦНИИ «Морфизприбор» и ОАО «Авангард».

102

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

1. Абакумов В.Г., Сербии С.А. Сравнительный анализ методов конструирования печатных плат. - Управляющие системы и машины. 1981, Вып.5. С. 43-47.

2. Абрайтис Л.Б. Лучевой алгоритм для проведения печатных соеди- • нений. Вопросы радиоэлектроники. Сер.ЭВТ, 1968. Вып.З. С.35-45.

3. Абрайтис Л. Б., Гирнюс А. П. Канальная трассировка с учетом контактов разъемов и меняющейся ширины канала. Управляющие системы и машины, 1983. №6. С. 24-27.

4. Абрайтис Л.Б., Шнейкаускас Р.И., Жилявичус В.А. Автоматизация проектирования ЭВМ. М.: Сов. радио, 1978, 272с.

5. Авдеев Е. В., Еремин А. Т. и др. Системы автоматизированного проектирования в радиоэлектронике: Справочник. М.: Радио и связь, 1986, с. 368.

6. Авенье Е.П. Обзор методов проектирования топологии. ТИИЭР, 1983. т.71. № 1. с.60-70.

7. Автоматизация проектирования цифровых устройств./ Под ред. С.С.Бадулина. М.: Радио и связь, 1981. - 240с.

8. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного метода конструирования электронных устройств. Львов.: Вища школа, 1981.- 168с.

9. Балтрушайтис Р.И. Задача и оценки размещения. В сб.: Вычислительная техника. Каунас, КПИ, 1982, с.65-66.

10. Ю.Баранов С.И., Майоров С.А. Сахаров Э.П., Селютин В.А. Автоматизация проектирования цифровых устройств. Л.: Судостроение, 1979. -264с.

11. Бахтин Б.И. Автоматизация в проектировании и производстве печатных плат радиоэлектронной аппаратуры. Л.: Энергия, 1979. - 120с.

12. Бершадский A.M. Применение графов и гиперграфов для автоматизации проектирования РЭА и ЭВА. Изд-во Саратовского ун-та, 1983. -120с.

13. Берштейн JI.C., Сапрыкин A.A. Минимизация наиболее длинных связей при линейном размещении элементов схемы. Изв. АН СССР, Техн. кибернетика, 1981, № 6, с.91 -99.

14. Берштейн JI.C. Селянкин В.В. Линейное размещение гиперграфов. -Изв. АН СССР, Техн. кибернетика, 1973. № 3, с. 128 -135.

15. Бибило П.Н., Лицкевич В.Г. Покрытие булевой сети библиотечными элементами. Управляющие системы и машины, 1999, №6, с. 16-24.

16. Борде Б. И. Основы САПР неоднородных вычислительных устройств и систем: Учебное пособие. Красноярск: КГТУ. 2000. 350 с.

17. Борде Б. И. Программно-методический комплекс «Основы САПР неоднородных вычислительных устройств и систем». Красноярск: ГКТУ. 2000. CDROM.

18. Теория к методы автоматизации проектирования вычислительных систем // Под ред. Бреуера М. М.: Мир, 1977. - 284с.

19. Варшавский А.Д. Универсальный алгоритм размещения связных объектов в двухмерном пространстве. Экспресс-информация, ТС-9, Экономика и технология приборостроения, М.: 1979. Вып.5. - 16с.

20. Гаевенко А.Ю. Критерий качества и алгоритм размещения элементов РЭА. Тез. докл. Всесоюзного совещания "Автоматизация проектирования микроэлектронной аппаратуры", ч.2, 1Л., 1983, с.251-252.

21. Глушков В.М., Мясников В.А., Половинкин А.И. Автоматизация поискового конструирования. Вестник АН СССР, 1979, № 7. С.42-48.

22. Гндоян A.K. Об одном подходе к задаче трассировки. Вопросы радиоэлектроники, сер. ЭВТ, 1980, Вып. 14, С. 43-47.

23. Журавлев 10.Н. Теоретико-множественные методы в алгебре логики. В ст.: "Проблемы кибернетики", вып. 8, М., Физ.мат., 1962, с.5-44.

24. Гель П.П., Иванов-Есипович Н.К. Конструирование радиоэлектронной аппаратуры. Л.: Энергия, 1982, 232с.

25. Гндоян А.К. Об одном алгоритме покрытия внешних связей печатных плат. — Вопросы радиоэлектроники, сер. ЭВТ, 1979, Вып.9, С. 52-53.

26. Горбатов В.А., Демьянов В.Ф. Частотно-минимальный алгоритм покрытия булевых матриц. В сб.: Оптимизация дискретных систем управления., М.: ГВЦ Госплана СССР. 1972, с.48-57.

27. Горошенко А.Г. Матричный метод проектирования межсоединений на типовых печатных платах. УСиМ, 1975, № 5, с. 128-132.

28. Григоровский Л.Ф., Куранов Б.В. Ускоренный последовательный алгоритм размещения конструктивных элементов. Тез. докл. Всесоюзного совещания "Автоматизация проектирования микроэлектронной аппаратуры", ч.2, М., 1983, с.223-224.

29. Деньдобренко E.H., Малика A.C. Автоматизация проектирования радиоэлектронной аппаратуры. М.: Высшая школа, 1980. -384с.

30. Деньдобренко Б.Н., Селютин В.А. Опыт использования ЭВМ при конструировании радиоэлектронной аппаратуры. Л.: ЛДНТП, 1977. - 32с.

31. Ершов А. П. Введение в теоретическое программирование. М.: Наука. 1977.-288с.

32. Закревский Л.Д., Островский В.И. Оптимизация поиска кратчайшего покрытия. В сб.: Проблемы синтеза цифровых автоматов. - М.: Наука, 1968.- 150с.

33. Зуев Ю.А. Задача о покрытии: локальный подход и метод типа ветвей и границ. -Журн. выч. мат. и мат. физ., 1979. т. 19, № 6, с. 1533-1573.

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

35. Корячко В. П., Курейчик В. М., Норенков И. П. Теоретические основы САПР: Учебник для вузов. М.: Энергоатомиздат, 1987, с. 400, ил.

36. Кристофидес Н. Теория графов. М.: Мир, 1978. - 423с.

37. Кузьмин Б.А., Эйдес A.A. О критериях качества размещения. Управляющие системы и машины, №13, 1982, с.53-55.

38. Курейчик В. М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР: Учебник для вузов. М.: Радио и связь, 1990, с. 352, ил.

39. Лазарева Т.О., Крапчин Л. И., Покровский А. И. Алгоритм трассировки печатных соединении на основе представления о каналах. Автоматика и вычислительная техника, № 5, 1969, с. 12-15.

40. Литвинов З.Н. Об одном подходе к решению задачи минимизации . длины связывающей сети при размещении геометрических объектов. В сб.: . Размещение геометрических объектов и вопросы оптимального проектирования. ИК АН УССР, Киев, 1977. -48с.

41. Мелихов А. Н., Берштейи Л. С., Курейчик В. М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974, 304 с.

42. Морозов К.К. и др. Методы разбиения схем на конструктивно-законченные части. М.: Радио и связь, 1978. - 134с.

43. Морозов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированное проектирование радиоэлектронной аппаратуры. М.: Радио и связь, 1983.-280с.

44. Морозов К.К. к др. Проектирование монтажных плат на ЭВМ. -М.: Советское радио, 1979. 224с.

45. Ненашев А. Н. Конструирование радиоэлектронных средств: Учебник для вузов. М.: Высшая школа, 1990, 432 с.

46. Норенков И.П., Маничев В.Б. Системы автоматизированного проектирования электронной и вычислительной аппаратуры. М.: Высшая школа, 1979.-272с.

47. Норенков И. П. Основы автоматизированного проектирования. Учебник для вузов. М.: Издано МГТУ им. Баумана. 2000. 360 с.

48. Островский В.М. К исследованию свойств кратчайших покрытий. -В сб.: Синтез дискретных автоматов и управляющих устройств. .

49. Парфенов Е. М., Камышная Э. Н. Усачов В. П. Проектирование конструкций радиоэлектронной аппаратуры: Учебное пособие для вузов. -М.: Радио и связь, 1989, с. 272.

50. Петренко А.И., Тетельбаум А.Я. Формальное конструирование . электронно-вычислительной аппаратуры. М.: Советское радио, 1979. - 253с.

51. Петренко А.П., Тетельбаум А.Я., Забалуев Н.Н. Топологические алгоритмы трассировки многослойных печатных плат. М.: Радио И связь, 1983.- 152с.

52. Петренко А.И. Основы автоматизации проектирования. Киев.: Техника, 1982.-295с.

53. Рощин В.А., Сергиенко И.В. Об одном подходе к решению задачи о покрытии. Кибернетика, 1984, № 6. с.65-69.

54. Рузаев Е.Н., Канунов А.И., Муравьев C.B. Алгоритмы нахождения минимального покрытия булевой матрицы. Изв. ВУЗов, Радиоэлектроника, 1981, №8. с.92-94.

55. Селютин В.А. Машинное конструирование электронных устройств. -М.: Советское радио, 1977, 384с.

56. Селютин В.А. Автоматизированное проектирование БИС. М.: Радио и связь, 1982. - 113с.

57. Сергиенко И.В., Рощин В.А. Один метод решения задачи о покрытии. ДАН УССР , 1983, №9, сер.А, с.73-75.

58. Смолич Г.Г., Смолич Л.И. Минимизация числа переходных отверстий при проектировании двухсторонних печатных плат. Обмен опытом в радиопромышленности, 1984, вып.11. с.54-56.

59. Соколов В.А., Фридман М.Г., Шеин П.,Д. Состояние и перспективы развития систем автоматизированного проектирования двухсторонних печатных плат. Изв.АН СССР, Техническая кибернетика, 1982, №2, с.171-178.

60. Соукуп И. Компоновка электронных схем. ТИИЭР, 1981. г.69, с.119-145.

61. Сухарев А. В. Моделирование процессов синтеза печатного электромонтажа РЭС как сложных систем./ Сухарев А. В., Шелест В.И. // СПб.:СПбГУТ им. проф. М.А.Бонч-Бруевича. 1999. -227 с.

62. Сухарев А. В. Модели и процедуры оптимизации в автоматизации проектирования (Программный комплекс FreeStyle Router). / Сухарев А. В., Золотое О.И. // СПб.: СЗТУ. 2001. - 165 с.

63. Толстун А.И., Мельничук И.Г., Горощенко А.Г. Программа направленной компоновки модулей. УСиМ. 1985, № 2, с. 29-33.

64. Финкелыитейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. -М.: Наука, 1973. 231с.

65. Фрумкин Г. Д. Расчет и конструирование радиоаппаратуры: Учебник для вузов. М.: Высшая школа, 1989, с. 463.

66. Харари Ф. Теория графов. М.: Мир, 1973. - 300с.

67. Шерип К.Ю. Синтез типоразмерных рядов базовых несущих конструкций радиоэлектронных средств АСУ.- СПб.: СПб.ГУТ им. проф. М.А. Бонч-Бруевича, 2000. 116 с.

68. Шрамченко Б. JI., Абакумов В. Г. Об определении матрицы смежности модулей. В кн.: Автоматизация проектирования и электронике. Вып.11., Киев.: Техника, 1975.

69. Штейн М. Е. Об ортогональных графах и оптимальных соединениях схем, Изв. АН СССР, Техн. Кибернетика, 1970, №2.

70. Юрин О.Н. Единая система автоматизации проектирования ЭВМ, проектирование блоков и узлов вычислительных машин, Киев, 1970.

71. Mailhot Г., De Micheli G. Algorithm for technology mapping based on binary decision diagrams and Boolean operations // IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems. 1993. - Vol.12, №5. - p. 599620.

72. Goodman E., Tetelbaum A., Kureichik V. A genetic algorithm approach to compaction, bin packing and nesting. Problems, Technical report №940702, Michigan state university, USA, 1994, p. 71.

73. Dergatchev S., Kureichik V. Allocation problem using genetic algorithm. SREU, Taganrog, №2, 1998, p. 251-253.

74. ACCEL EDA. Version 14. ACCEL PC AD PCB, ACCEL Tango PCB. User's Guide and Reference. ACCEL Technologies, Inc., 1999.

75. ACCEL EDA. Version 14. ACCEL PRO Route. User's Guide and Reference. ACCEL Technologies, Inc., 1999.

76. SPECCTRA. Version 5.3. Tutorial. Cooper & Chyan Technology, Inc.,1994.

77. SPECCTRA. Version 5.3. User's Reference. Cooper & Chyan Technology, Inc., 1994.1. АКТоб использовании результатов диссертационной работы Сухарева А. В.

78. Комиссия в составе Исправникова. В. А., Дорогунцева В. Г. и

79. Радушновой Е. М. составила настоящий акт о том, что теоретические и• практические результаты диссертационной работы Сухарева А. В., используются в научно-исследовательских и опытно-конструкторских работах предприятия ОАО «Техприбор».

80. Использование указанных математических моделей, алгоритмов и• программ обеспечивает многовариантный поиск наиболее целесообразных решений, существенно сокращает сроки и стоимость проектных работ.1. Нач. отдела АСУП1. Нач. отдела1. Вед. инженер-програг*

81. Исправников В. А./ /Дорогунцев В. Г./ /Радушнова Е. М./

82. УТВЕРЖДАЮ Проректор СЗТУ по учебной работе, д.т.н., проф.1. B.R Воронцов2003 г.1. АКТоб использовании диссертационной работы Сухарева A.B.в учебном процессе

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

84. Начальник отдела 1338, к.т.н.1. Тарасов Г.Г.

85. УТВЕРЖДАЮ Начальник 7 НИО,е^Л^НЬШ КОНСТруКТОр1. АКТоб использовании результатов диссертационной работы Сухарева А. В.

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

87. Кульгин В. Л./ / Николаев Н. И./ /Федорова Н. А./