Введення

В даний час відбувається стрімкий розвиток систем автоматизованого проектування (САПР). Основним завданням САПР є спрощення і підвищення ефективності роботи інженерів за допомогою взаємодії з ЕОМ. САПР використовується для проведення різних технічних робіт, полегшення процесів конструювання в різних галузях, підвищення якості результатів проектування, наскрізного автоматизованого проектування та інше.

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

Завдання дослідження

Метою є розробка навчальної комп'ютерної підсистеми розміщення друкованої плати із застосуванням методу гілок і меж. Розміщення друкованих плат є важливим етапом при проектуванні друкованих плат. Від якісного виконання даного етапу залежить вдале виконання подальшого етапу проектування, а саме-трасування друкованих з'єднань і розшарування друкованої плати.

Поняття самої системи автоматизованого проектування

Під даною системою (САПР) розуміють організаційно–технічну систему, що складається із сукупності комплексу засобів автоматизації проектування і колективу фахівців підрозділів проектної організації, здатну вирішувати завдання проектування [1]. На даний момент існують кілька популярних САПР, кожна з них має свої особливості і можливості.

В даний час в якості основного засобу автоматизації виступає сукупність обчислювальної техніки і обчислювальних методів. Можна виділити дві основні групи завдань, які передбачають використання цих коштів.

перша група пов'язана з удосконаленням методів проектування на основі математичного моделювання та автоматизації пошуку рішень. На цьому рівні забезпечується:

–Автоматизація синтезу проектних рішень;

-Автоматизація аналізу прийнятих проектних рішень.

Друга група пов'язана із заміною трудомістких робіт програмними операціями. До такого завдання відносяться роботи з формування та випуску проектної документації.

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

Вимога моделі-придатності для об'єкта повинні бути можливі:

-розробка адекватних математичних моделей об'єктів та окремих його елементів, визначення обчислювальних ресурсів моделі;

-необхідних обсягів пам'яті і машинного часу для здійснення моделей;

-можливість реалізації для об'єкта операцій синтезу;

-вимоги контролю-придатності, що передбачають можливість створення контрольних тестів для створеного в результаті проектування об'єкта.

На сьогоднішній день існує досить велика кількість пакетів автоматизованого проектування ПП. Серед них є як системи початкового рівня, так і промислові системи для багатокористувацької роботи.

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

Методи розміщення елементів на друкованій платі

Вихідною інформацією при вирішенні завдань розміщення елементів є:

-дані про конфігурацію і розміри комутаційного простору, що визначаються вимогами установки і кріплення даної складальної одиниці в апаратурі;

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

-схема з'єднань, а також ряд обмежень на взаємне розташування окремих елементів, що враховують особливості розроблюваної конструкції.

Завдання зводиться до відшукання для кожного розміщуваного елемента таких позицій, при яких оптимізується обраний показник якості і забезпечується найбільш сприятливі умови для подальшого електричного монтажу. Особливого значення це завдання набуває при проектуванні апаратури на друкованих платах [2]p>

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

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

Тому всі застосовувані в даний час алгоритми розміщення використовують проміжні критерії, які лише якісно сприяють вирішенню основних завдання: отримання оптимального трасування з'єднань. До таких критеріїв належать:

-мінімум сумарної зваженої довжини з'єднань;

-мінімум числа з'єднань, довжина яких більше заданої;

-мінімум числа перетину провідників;

-максимальне число з'єднань між елементами, що знаходяться в сусідніх позиціях або в позиціях, зазначених розробником;

-максимум числа ланцюгів простої конфігурації.

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

Структура навчальної САПР друкованих плат

Для побудови математичної моделі електричної схеми [6] використовується теорія графів. Електрична схема інтерпретується у вигляді ненаправленого графа G (X, U), в якому безліч вершин графа Х – конструктивні елементи схеми, а безліч ребер U – електричні зв'язки. У зв'язку з труднощами, при розробці програмного продукту, які викликає опис схем за допомогою графів, для виконання завдань використовується матриця суміжності R і матриця геометрії Q [4].

Проектування друкованих плат можна розділити на п'ять етапів:

-проектування схеми, редактор;

-компонування друкованих плат;

-розміщення елементів друкованої плати;

-трасування модулів друкованої плати;

-розшарування друкованої плати.

У редакторі схеми можна спроектувати типи корпусів скільки входів і виходів буде використовуватися dip14, dip16, dip18, dip24. З'єднання елементів, за принципом який номер входу елемента підключається провідників до іншого елементу, наприклад: D1.1 - D4.1-таким чином видно, що елемент D1 з'єднаний з елементом D4 провідником через перші номери входів корпусу.

В результаті виконання компонування визначається, які елементи схеми будуть перебувати в кожному конструктивному вузлі, а також зв'язку всередині кожного вузла і зв'язку між вузлами.

Iснують два варіанти компонування:

-компонування схем типової конструкції, що не мають схемної уніфікації;

-компонування схем в модулі заданого схемно-уніфікованого набору.

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

Після компонування конструктивних елементів для кожної комірки, плати і так далі, відбувається етап розміщення елементів у вузлі.

Мета розміщення полягає у визначенні найкращого розташування [7]елементів і зв'язків між ними в монтажному просторі конструкції. Обов'язково повинні бути дотримані конструктивно-технологічні обмеження.

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

Етап трасування з'єднань, найчастіше є заключним етапом проектування схеми. Він полягає у визначенні ліній, які з'єднують контакти елементів і компонентів, які є складовими проектованого пристрою.

Математична точка зору трасування визначається як завдання вибору найкращого рішення з численного числа варіацій.

Завдання трасування є однією з найбільш трудомістких завдання, які виникають при автоматизації проектування. Складність полягає в різноманітті методів конструктивно-технологічної реалізації з'єднань. Для кожного з цих методів при вирішенні завдання застосовуються спеціальні критерії оптимізації та обмежень.

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

Етап розшарування послідовно по шарах і в міру заповнення чергового шару відбувається перехід на інший шар, або проводиться попереднє розшарування; всі з'єднання межу парами контактів прокладаються тільки в одному шарі.

Структурна схема навчальної САПР наведена на рис 1. Зі схеми видно, що навчальна[8] САПР складається з п'яти підсистем.

<

Розробка методу гілок і меж

Основні правила алгоритму можуть бути сформульовані[9] наступним чином:

1. Розгалуженню в першу чергу піддається підмножина з номером, якому відповідає найменше значення нижньої оцінки цільової функції.

2. Якщо для деякого i-го підмножини виконується умова, то розгалуження його необхідно припинити.

3. Розгалуження підмножини припиняється, якщо знайдене в задачі оптимальне рішення.

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

5. Після знаходження хоча б одного допустимого рішення вихідної задачі може бути розглянута можливість зупинки роботи алгоритму з оцінкою близькості кращого з отриманих допустимих рішень до оптимального, приклад виконання рішення шляхом даного методу (мал. 2).

Основні способи розгалуження:

-Розбиття безлічі варіантів на підмножини за методом "в ширину" і вибір вершини розгалуження по мінімуму (максимуму) оціночної функції.

-Розбиття безлічі варіантів за методом» в глибину з поверненням", тобто послідовне побудова гілок.

-Комбінація двох розглянутих способів.

Метод гілок і кордонів як скорочення повного перебору

Основна ідея повного перебору полягає в переборі всіх можливих розташувань елементів на друкованій платі в пошуках оптимального.

Перевагою даного методу є гарантоване знаходження оптимального[10] розміщення.

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

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

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

Довільному розміщенню елементів відповідає в повному дереві деякий шлях, що виходить з початкової вершини. Для кожної вершини дерева можна розрахувати нижню межу цільової функції для безлічі шляхів, пов'язаних з цією вершиною.

Якщо в процесі просування по дереву нижні межі не розраховуються і відповідно не проводиться усічень дерева, то метод гілок і кордонів зводиться до повного перебору

Можна виділити наступні способи відсікання гілок:

1) порівняння оцінки зі значенням цільової функції для вже знайденого рішення. Опорне рішення можна отримати наближеним алгоритмом заздалегідь або в ході вирішення завдання методам гілок і кордонів.

2) порівняння двох оцінок.

Література

1 В.В. Муленко учебное пособие для студентов вузов «Компьютерные технологии и автоматизированные системы в машиностроении». - РГУ нефти и газа им. И.М.Губкина, М., 2015. – С. 3

2 Н.П. Курочка, В.Н. Шипилов, Б.А. Шиянов научная статья «Задачи оптимального размещения ресурсов организации» - Воронежского государственного технического университета 2009

(https://cyberleninka.ru/article/n/zadachi-optimalnogo-razmescheniya-resursov-organizatsii/viewer)

3 В.М. Бондарик «Система автоматизированного проектирования» уч.пособие Мн. БГУИР, 2006- 46 с.

4 В.Е. Алексеев, В.А. Таланов «Графы. Модели вычислений. Структуры данных» Учебник Нижний Новнгород,2004 – 12 с.

5 А.В. Григорьев Методы поиска новых решений в специализированной инструментальной оболочке для создания интеллектуальных САПР Десятая национальная конференция по искусственному интеллекту с международным участием КИИ-2006 (25-28 сентября 2006г., Обнинск): Труды конференции. В 3-т. Т.3. -- М.: Физматлит, 2006. С. 1031-1046.

6 И.М. Трифоненко, Н.В. Горячев, И.И. Кочегаров, Н.К. Юрков Обзор систем сквозного проектирования печатных плат радиоэлектронных средств Трифоненко И.М., Горячев Н.В., Кочегаров И.И., Юрков Н.К - Пензенский государственный университет

7 Норенков И.П. Основы автоматизированного проектирования: Учеб.для вузов / И.П. Норенков. - М.: Изд-во МГТУ им. Н.Э.Баумана, 2002.-336 c.

8 СабунинА.Е.Altium Designer. Новые решения в проектировании электронных устройств / А.Е. Сабунин. — М.: Солон-Пресс, 2009. – 432 с.

9 Горячев Н.В., Проектирование топологии односторонних печатных плат, содержащих проволочные или интегральные перемычки / Н.В. Горячев, Н.К. Юрков // Труды международного симпозиума "Надежность и качество". 2011. Т. 2. С. 122-124.

10 Горячев Н. В. Опыт применения систем сквозного проектирования при подготовке выпускной квалификационной работы / Н. В. Горячев, Н. К. Юрков // Известия ПГПУ им. В.Г. Белинского. Физикоматематические и технические науки. 2011. № 26. С. 534–540.