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

Короткий опис

Щерб'юк Ігор Федорович. Алгоритмічне та програмне забезпечення для розміщення різногабаритних елементів електронних пристроїв комбінованими методами ієрархічної оптимізації : Дис... канд. наук: 05.13.12 - 2008.

Щерб’юк І.Ф. Алгоритмічне та програмне забезпечення для розміщення різногабаритних елементів електронних пристроїв комбінованими методами ієрархічної оптимізації.- Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.12 "Системи автоматизації проектувальних робіт". Національний університет "Львівська політехніка", Львів, 2008.
Дисертацію присвячено питанням розробки та дослідження алгоритмічних та програмних засобів розміщення різногабаритних елементів на конструктиві.
Досліджено особливості задач розміщення для різногабаритних елементів. Розроблено алгоритм багаторівневого низхідного ієрархічного розміщення з можливістю оптимізації на кожному рівні декомпозиції сканувальною областю для макромоделей. Розроблено алгоритм на основі дворівневого групування за висхідною стратегією. Розвинуто алгоритм сканувальної області з врахуванням особливостей реалізації для різногабаритних елементів. Вперше реалізовано алгоритм сканувальної області для макромоделей. Розроблено алгоритм точкового сканування елементом та групою елементів конструктиву.
Проведено експериментальні дослідження розроблених алгоритмів та дано порівняльний аналіз ефективності кожного з них. Для розробленого алгоритмічного забезпечення створено комп’ютерну систему для використання в проектуванні електронних пристроїв, зокрема друкованих плат.

В результаті виконаних досліджень розв’язано наукову задачу розроблення методів та алгоритмів розміщення різногабаритних елементів електронних пристроїв, які поєднують принципи багаторівневої декомпозиції та ієрархічної оптимізації і реалізовані в комп’ютерній системі "Розмел" з інтеграцією в сучасній системі автоматизованого проектування P-CAD, що покращило якість проектування.
Отримано такі наукові і практичні результати:

Аналіз та дослідження відомих систем автоматизованого проектування засобів приладобудівної та електронної техніки (зокрема, P-CAD та ACCEL) виявили, що якість розв’язування задачі розміщення різногабаритних елементів електронних пристроїв є недостатньо високою та вимагає покращення.
Для покращення якості розміщення різногабаритних елементів конструкцій електронної апаратури в системах автоматизованого проектування запропоновано поєднати багаторівневі алгоритми низхідного та висхідного розміщення базових та макроелементів з алгоритмами глобальної та локальної оптимізації на кожному рівні ієрархічної декомпозиції схеми.
Розроблено, розвинуто і експериментально досліджено для конструкцій з різногабаритними елементами два підходи для отримання початкового розміщення:

висхідного дворівневого розміщення з послідовним нарощенням елементів, придатного для отримання якісних розв’язків з невеликою кількістю елементів;

низхідного ієрархічного багаторівневого розміщення з використанням макромоделей, придатного для отримання якісних розв’язків для задач з великою кількістю елементів.
Обґрунтовано доцільність сумісного використання обох підходів: на верхніх рівнях низхідне ієрархічне розміщення, на нижніх двох рівнях послідовне нарощування елементів з врахуванням зв’язків з рештою елементів.

Для оптимізації положення як базових, так і макроелементів, розроблено, розвинуто та експериментально досліджено алгоритми:

точкового сканування (розроблено вперше);
сканувальної області.
Обґрунтовано доцільність сумісного комбінування обох алгоритмів на кожному кроці ієрархічної декомпозиції схеми.

Розроблені та досліджені алгоритмічні засоби мають близьку до лінійної обчислювальну складність та ряд додаткових нових функційних можливостей, зокрема виділяти сильнозв’язані групи елементів з наступним описом їх ієрархічно-вкладеними макромоделями, комбіновано поєднувати на кожному кроці багаторівневої декомпозиції набір алгоритмів початкового розміщення та його оптимізації з використанням макромоделювання. Алгоритмічні засоби забезпечують також вибір орієнтації елементів, виділення фіксованих місць для окремих елементів, виділення зон, заборонених для розміщення елементів.

Експериментально досліджено ефективність розроблених алгоритмів та програмних засобів на задачах реальних конструкцій електронної апаратури. Застосування розробленої комп’ютерної системи "Розмел" для таких задач підвищило якість отриманих розв’язків до 26,6% в порівнянні з результатами, одержаними системою P-CAD.

Розроблено комп’ютерну систему "Розмел", яка реалізує комплекс розроблених алгоритмічних засобів, має гнучку модульну структуру з власними засобами керування та призначена як для автономного використання, так і для взаємодії з системами автоматизованого проектування широкого використання, такими як P-CAD, ACCEL та іншими.

Система має засоби інтерактивної взаємодії, які забезпечують покращення якості отриманих розв’язків для задач, що погано формалізуються, особливо у випадку великого розкиду габаритів елементів, наявності фіксованих елементів та заборонених зон. Вперше запропоновано виводити в діалогове вікно (для використання проектантом) інформацію про структуру дерева оптимального згортання, що дозволяє оперувати ієрархічно-вкладеними макроелементами, які відповідають групам сильнозв’язаних елементів кластерам схеми.

Розроблену комп’ютерну систему "Розмел" впроваджено в процес реального проектування друкованих плат в Науково-дослідному і конструкторському інституті електронної вимірювальної та обчислювальної техніки (м.Львів) та в навчальний процес на кафедрі "Програмне забезпечення" Національного університету „Львівська політехніка”.