Новости

МАТЕМАТИЧНІ МОДЕЛІ МОНТАЖНО-КОМУТАЦІЙНОГО ПРОСТОРУ

Работа добавлена:






МАТЕМАТИЧНІ МОДЕЛІ МОНТАЖНО-КОМУТАЦІЙНОГО ПРОСТОРУ на http://mirrorref.ru

Тема 6  МАТЕМАТИЧНІ МОДЕЛІ МОНТАЖНО-КОМУТАЦІЙНОГО ПРОСТОРУ

Монтажно-комутаційний простір (МКП) призначений для розміщення конструктивних модулів і трасування з'єднань між їх контактами, які повинні бути сполучені електричними колами. Форма і математична модельМКП залежать від рівня модуля, для якого в даний момент розв'язується задача конструювання (базовий матричний кристал, друкована плата, панель і т.д.). Надалі обмежимося тільки плоскиммонтажно-комутаційним простором, відповідним конструктивному модулю типу друкована плата. Вважаємо, що простір має прямокутну форму, оскільки введенням областей, в яких забороняється розміщення конструктивних модулів нижчого рівня або трасування з'єднань, можна надати простору довільну форму.МКПслужить для вирішення двох задач:

  • розміщення модулів
  • трасування.

Тому моделі МКП, що використовуються для вирішення кожної задачі, матимуть відмінності. Розглянемо ці моделі докладніше.

Найбільше розповсюдження для вирішення задач розміщення конструктивних модулів в плоскомуМКПодержали евристичні дискретні моделі. Такі моделі (будемо їх називати МКП1) будуються таким чином (рис. 6.1а):МКП розбивається   на елементарні  площадки  (дискрети),  кожна з яких призначена для розміщення одного конструктивного модуля нижчого рівня, наприклад мікросхеми на друкованій платі. Ці площадки надалі називатимемо Дискретами  робочого  поля  (ДРП).   Кожен, дискрет  в процесі рішення задачі розміщення може знаходитися в одному з наступнихстанів:вільний для розміщення, зайнятий. Дискрет має певну  вагу,  що забороняє  розміщення  в  ньому модуля, т.д. Така_ модель МКП відрізняється простотою і зручністю для використання в евристичних алгоритмах розміщення, однак вона  не є  повністю формалізованою.

а)б)   в)

Рис. 6.1 Дискретні моделі МКП

Одним з різновидів моделі МКП1 є модель з ортогональною сіткою, у вузлах якої можуть розміщуватися модулі нижчого рівня (рис. 6.1б). Крок сітки вибирається з умови можливості розміщення модулів в сусідніх вузлах сітки.

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

Аналогічні дискретні моделі використовуються і для вирішення задач трасування. В цьому випадкудискрет є квадратом із сторонами, рівними ширині провідника плюс "Зазор” між ними (рис. 6.1в). При цьому вважається, що провідник з кожногодискрета може бути проведений тільки в сусіднійДРП.

Найбільше поширення для вирішення задач розміщення набули моделіМКП у вигляді зваженого графаVG(S,V), які позначатимемо МКП2. Зважений графVG є симетричним графом, в якому множина вершинS відповідає множині установочних позицій в комутаційному просторі для модулів нижчого рівня, а множина гілок інтерпретує множина зв'язків між відповідними установочними позиціями. Кожній гілці графаvij приcвоюється вагарij, яка рівна числу умовних одиниць відстані між центрами установочних позиційsi іsj, що інтерпретуються вершинами, інцидентними даній гілці. Вага гілкирij визначається залежно від метрики простору по одній з формул (5.1тема5).

Для опису зваженого графаVG зручно використовувати матрицю суміжностейQ. Рядки і стовпці матриці відповідають вершинам графа, тобто множині установочних позицій в МКП, а елементиqij дорівнюють вазі гілки, інцидентноїi-й іj-й вершинам графа. Елементи, що лежать на головній діагоналі матрицісуміжностейQприймаються рівними нулю. ДляМКП, показаного на рис. 6.2а, модель у вигляді зваженого графа при ортогональній метриці просторуприведена на рис 6.2б.

  ДРП    •

  ДРП   •

  ДРП   •

  ДРП   •

а)

           S1            2                     S2

    1  1

          S3              2                     S4

б)

Рис. 6.2 Графові  моделіМКП для розв’язку задачі  розміщення.

S1

S2

S3

S4

S1

0

2

1

0

Q=

S2

2

0

0

1

S3

1

0

0

2

S4

0

1

2

0

Для вирішення задач розміщення застосовуються і інші графові моделі.

Великі можливості для формалізації процесу трасування мають комбіновані дискретно-графові моделіМКПЗ. В цьому випадкуМКП моделюється симетричним графомG(S,V), в якому кожномуДРП ставиться у відповідність вершина графа. Вершиниsi іsj з'єднуються гілкою, якщо вони відповідають сусіднім дискретам, через які може проходити провідник. Траси провідників можуть проходити тільки по гілках графа, а довжина трас визначається відповідно до вибраної метрики простору. На рис. 6.3а показані моделі МКП2 для трасування по ортогональних напрямах і при дозволі трасування під кутом в 450 (трасування по шести напрямах).

а)б)

Рис. 6.3. Графові моделі МКП для розв’язку задач трасування

Симетричний графG(S,V),  з множиною вершинS і множиною гілокV може бути описаний в ПК матрицею інциденцій А, елемент якоїаij = 1, якщо вершинаsi інцидентна гілціvij, і інакшеаij = 0. Для графа, показаного на рис. 6.3а, при дозволі трасування по восьми напрямах матрицяінциденцій має вигляд:

V12

V13

V14

V23

V24

V34

S1

1

1

1

0

0

0

A =

S2

1

0

0

1

1

0

S3

0

1

0

1

0

1

S4

0

0

1

0

1

1

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

Аналогічна доМКПЗ і графова модель простору МКП4, також використовується для вирішення задач трасування. Модель МКП4 представляє собою симетричний графG(S,V), вершини якогоS відповідають вузлам координатної сітки, нанесеної на плоске МКП, а гілки графаvij - елементарним відрізкам координатної сітки, що сполучають дві сусідні точки (рис. 6.3б). Особливістю моделі МКП4 в порівнянні з МКПЗ є інтерпретація гілки графаG(S,V)  як елементарного відрізка провідника, який може бути прокладений в цьому місці МКП. По своїх можливостях модель МКП4 еквівалентнаМКПЗ.

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

Одна з таких моделей МКП5 представляє мультиграф МG(S,V),  в якому множина вершин графаS відповідає множинаі установочних позицій в комутаційному просторі для модулів нижчого рівня, а множина гілокV - множині взаємно незалежних безпосередніх переходів між установочними позиціями, тобто множині областей, що допускають трасування з'єднань між цими позиціями без перетинів.

a)б)

Рис. 6.4. Моделі МКП  у вигляді мультиграфа.

МультиграфМG(S,V) може бути описаний за допомогою матриці суміжностейQ, в якій, як і для зваженого графа, елементиqij, що лежать на головній діагоналі, приймаються рівними нулю, а недіагональні елементиqij рівні числу кратних гілок, інцидентнихij-й вершинам графа. Для прикладу, на рис. 6.4, а показані фрагмент комутаційного простору з установочними позиціями і його модель у вигляді мультиграфа при допущенні трасування без перетинів трьох провідників між сусідніми позиціями. Матрицясуміжності такого мультиграфа має вигляд:

S1

S2

S3

S4

S1

0

3

3

0

Q=

S2

3

0

0

3

S3

3

0

0

3

S4

0

3

3

0

Ще загальнішою моделлю МКП у вигляді мультиграфа, яка використовується для вирішення задач трасування, є модель МКП6, в якій вершини графа відповідають макродискретами, на які розбивається МКП. Ребра мультиграфа сполучають сусідні вершини, причому кількість кратних гілок визначається тим, скільки провідників може пройти через межі сусідніх дискретів. Відстань визначається як кількістьмакродискретів, пройдених провідником при трасуванні. Приклад фрагмента МКП з макродискретами, через межі яких допускається проходження трьох і двох провідників, і відповідний йому мультиграф показані на рис. 6.4б.

Модель МКП6 припускає проведення трасування провідників в два етапи: на першому визначається шлях з точністю до вершини мультиграфа (макродискрета), на другому - шлях конкретизується з точністю до гілки. Це дозволяє на першому етапі вибрати якнайкраще взаємне розташування трас, а на другому - провести власне трасування, що зменшує залежність кількості реалізованих в комутаційному просторі трас від черговості трасування

МАТЕМАТИЧНІ МОДЕЛІ МОНТАЖНО-КОМУТАЦІЙНОГО ПРОСТОРУ на http://mirrorref.ru


Похожие рефераты, которые будут Вам интерестны.

1. Реферат МАТЕМАТИЧНІ МОДЕЛІ КОНСТРУКЦІЙ РА

2. Реферат МАТЕМАТИЧНІ МОДЕЛІ ТЕХНІЧНИХ ОБ’ЄКТІВ

3. Реферат Економіко-математичні методи та моделі аналізу процентної ставки

4. Реферат СПРИЙНЯТТЯ ПРОСТОРУ

5. Реферат Математичні методи дослідження операцій

6. Реферат Використання підземного простору в містах

7. Реферат НАБЛИЖЕНІ МАТЕМАТИЧНІ ОБЧИСЛЕННЯ В ЗАДАЧАХ РОЗПІЗНАННЯ ОБРАЗІВ

8. Реферат Становлення медіа-освітнього простору як філософська проблема

9. Реферат Матриці. Лінійні дії з матрицями. Поняття лінійного простору

10. Реферат Математичні основи асиметричної криптографії. Арифметика чисел великої розрядності