Алгоритмічне та програмне забезпечення для розміщення різногабаритних елементів електронних пристроїв комбінованими методами ієрархічної оптимізації

Abstract

Дисертацію присвячено питанням розробки та дослідження алгоритмічних та програмних засобів розміщення різногабаритних елементів на конструктиві. Досліджено особливості задач розміщення для різногабаритних елементів. Розроблено алгоритм багаторівневого низхідного ієрархічного розміщення з можливістю оптимізації на кожному рівні декомпозиції сканувальною областю для макромоделей. Розроблено алгоритм на основі дворівневого групування за висхідною стратегією. Розвинуто алгоритм сканувальної області з врахуванням особливостей реалізації для різногабаритних елементів. Вперше реалізовано алгоритм сканувальної області для макромоделей. Розроблено алгоритм точкового сканування елементом та групою елементів конструктиву. Проведено експериментальні дослідження розроблених алгоритмів та дано порівняльний аналіз ефективності кожного з них. Для розробленого алгоритмічного забезпечення створено комп’ютерну систему для використання в проектуванні електронних пристроїв, зокрема друкованих плат.Диссертация посвящена вопросам разработки и исследованию алгоритмических и программных средств размещения разногабаритных элементов на конструктиве. Исследовано особенности задач размещения для разногабаритных элементов. В работе развивается иерархическое макромоделирование на основе многоуровневой кластеризации схемы, которое позволяет выделить группы сильносвязанных элементов – макроэлементы, которые желательно размещать вплотную. Как базовый используется метод оптимального свертывания схемы, в котором математической моделью иерархической кластеризации служит дерево оптимального свертывания. Разработан алгоритм многоуровневого нисходящего иерархического размещения с возможностью оптимизации сканируюющей областью для макромоделей на всех уровнях декомпозиции. Разработан алгоритм начального размещения элементов, основанный на двууровневом группировании по восходящей стратегии при объединении элементов в группы на одном уровне декомпозиции. Развит алгоритм сканирующей области с учетом особенностей реализации для разногабаритных элементов, который используется как средство оптимизации положения элементов на каждом уровне иерархической декомпозиции. Впервые разработана реализация алгоритма сканирующей области для макроэлементов. Разработан алгоритм точечного сканирования элементом и группой элементов конструктива. Проведены экспериментальные исследования разработанных алгоритмов и дан сравнительный анализ эффективности каждого из них. Для разработанного алгоритмического обеспечения создана компьютерная система с целью использования при проектировании электронных устройств, в частности печатных плат, с помощью которой размещение, сформированное системой P-CAD, может модифицироваться. Исходные данные об элементах и их размещении получаются из PDF-файлов системы P-CAD. Дальнейшее формирование размещения элементов осуществляется компьютерной системой с помощью реализованных в ней алгоритмов и средств. The dissertation deals with the elaboration and investigation of algorithms and software of placement of variouse size elements of the electronic devices. Peculiarities of tasks of placement various size elements is investigated. The algorithm of multilevel top-down hierarchical placement with further optimization of scanning area for macromodels is developed. The algorithm based on two-level botton-up strategy is developed. The point scanning algorithm with provision for particularities for various size elements is proposed. The scanning area algorithm for macromodels is developed. The algorithm of point scanning by element or group of elements is suggested. The experimental investigations at the basis of proposed algorithms are made and the comparative analysis of efficiency is given. The computer system with proposed algorithms is developed.