Алгоритми та методи компонування й розміщення. Графові моделі схем обчислювальних пристроїв та їхнього перетворення

Тема контрольної роботи «Алгоритми та методи компонування й розміщення. Графові моделі схем обчислювальних пристроїв та їхнього перетворення».
Мета роботи: вивчити основні класи алгоритмів компонування й роз-міщення, навчитися використовувати поняття теорії графів для опису моделей конструкції електронних обчислювальних апаратур, вирішувати основні завдання конструювання з використанням прикладних програм.

Першим у центр розширеної матриці встановлюється елемент, який має найбільше число впливових з'єднань, далі установлюється елемент, найбільш зв'язаний з максимально зв'язаним елементом і ці елементи умовно поєднуються в одну групу. Потім установлюється елемент, найбільш зв'язаний із цією групою й т.і., поки не будуть визначені посадкові місця для всіх елементів. При установці чергового елемента мінімізується наступна функція:
Fi = Σk Σj (άjΔxijk +βjΔyijk) + Si,
де: Si – невикористовувана площа плати, пов'язана з різногабаритносттю елементів;
άj, βj =0, якщо і-й елемент не пов'язаний з j-тим;
άj=0, βj=4, якщо елемент пов'язаний з корпусом;
βj=0, якщо елемент зв'язаний з вільним виводом з'єднувача.
У всіх інших випадках άj=1 βj=2, якщо і-тий елемент пов'язаний з j-тим δxijkδyijk – різниця відповідно між абсцисами й ординатами виводів установлюваного елемента із установленими.
підсумовування по k означає перебір по всіх виводах установлюваного елемента, а підсумовування по j – перебір по всіх установлених елементах.