Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Задача покрытия схем набором конструктивных модулей.

Читайте также:
  1. XV. СВЕРХЗАДАЧА. СКВОЗНОЕ ДЕЙСТВИЕ
  2. Анализ результатов ровности покрытия
  3. Боевая задача выполнена
  4. В. (гневно): Так зачем вы взялись лечить нас, если заняты своими задачами?
  5. В. (гневно): Так зачем вы взялись лечить нас, если заняты своими задачами?
  6. В. (гневно): Так зачем вы взялись лечить нас, если заняты своими задачами?
  7. В. (гневно): Так зачем вы взялись лечить нас, если заняты своими задачами?

В результате решения задачи покрытия каждый элемент схемы привязывается к некоторому конструктивному модулю из набора Q={Q1, Q2, …,Qm}.

Математическая постановка задачи покрытия зависит от типа конструктивных модулей набора. Различают 3 типа конструктивных модулей:

1) Каждый модуль содержит базовые логические элементы одного типа, при этом все входы и выходе логических элементов являются выводами модуля.

Например:

2) Тоже что и предыдущий тип, однако в одном конструктивном модуле могут содержаться разнотипные логические элементы.

Модули 1-го и 2-го типов называются модулями с несвязанными элементами.

3) Конструктивный модуль в общем случае содержит связанные между собой разнотипные элементы и не все входные и выходные выводы элементов имеются на внешних контактах конструктивного модуля.

Рассмотрим математическую постановку задачи покрытия схемы конструктивными модулями с несвязанными элементами (1-го и 2-го типов).

Обозначим через bi количество логических элементов ti типа, содержащихся в функционально-логической схеме (ФЛС). При таком подходе состав ФЛС может быть описан матрицей-столбцом: B= || bi || n, где n – число типов логических элементов схемы, bi – число логических элементов ti типа в ФЛС. Будем считать, что каждый тип конструктивного модуля Qj в общем случае содержит несколько типов ti базовых элементов, а весь набор конструктивных модулей Q может быть описан матрицей A= || aij || nxm, где aij – количество базовых логических элементов типа ti в конструктивном модуле типа Qj ().

Пример.

      Q1 Q2 Q3
    t1      
A = t2      
    t3      
    t4      

В качестве критерия оптимизации будем использовать минимум стоимости покрытия. Обозначим cj стоимость конструктивного модуля Qj.

Пусть для покрытия ФЛС необходимо выделить yj конструктивных модулей Qj, тогда в качестве целевой функции можно взять функцию вида:

.

Будем считать, что каждый тип базового логического элемента схемы может быть реализован как базовый логический элемент того же набора, так и БЛЭ другого типа набора. Например:

Обозначим через xki количество логических элементов типа tk, которое идет на покрытие логических элементов схемы типа ti. Возможность замены БЛЭ типа tk на БЛЭ типа ti будем описывать матрицей W =|| wki || nxn,

Очевидно, что xki >0 если wki =1.

Учитывая введенные обозначения, задачу покрытия можно сформулировать следующим образом: если yj количество требуемых конструктивных модулей типа Qj, а в каждом Qj конструктивном модуле содержится aij элементов типа ti, то определяет количество логических элементов типа ti, содержащихся во всем выделенном для покрытия ФЛС наборе конструктивных модулей.

Очевидно, что для покрытия всей ФЛС необходимо выполнение следующего условия:

,

где второе слагаемое – количество логических элементов других типов, которые идут в покрытии на реализацию логических элементов типа ti; последнее слагаемое – количество логических элементов типа ti, которые идут на реализацию логических элементов других типов.

Т. о., ставится задача отыскания таких значений yj и xki, удовлетворяющих (**), чтобы обеспечивался минимум целевой функции (*) – стоимости покрытия. На практике используются приближенные методы, опирающиеся на специфику используемых конструктивных модулей. Если имеем дело с несвязанными элементами конструктивного модуля, то здесь в результате определения требуемого числа модулей не осуществляется привязка логических элементов схемы к конструктивным модулям, отсюда появляется возможность оптимизации по другому критерию, в частности по критерию минимума межблочных связей.

Пример Q={Q1, Q2, Q3}, t={t1, t2, t3, t4} приведен нами выше. Требуется покрыть ФЛС, описываемую вектором B={ 5, 4, 1, 1 }, заданным набором конструктивных модулей.

Блок-схема алгоритма определения требуемого числа конструктивных модулей по критерию минимума стоимости покрытия приведена на рисунке.

 

 

Требуемое число корпусов модуля j-го типа определяется из выражения:

(1)

Для нашего примера:

Так как a31=0 и a41=0, то в качестве коэффициента

Полагаем, что j=2 и вычисляем

, и следовательно

j=3

Переходим к :

, (остальные bi=0)

Т.о. имеем , , , .

Эти данные подставляем в выражение (1) и определяем:

,

,

.

После определения требуемого числа корпусов, можно осуществить привязку элементов к корпусам. Для этого могут быть использованы рассмотренные ранее алгоритмы решения задач компоновки (задачи разбиения).


Дата добавления: 2015-08-21; просмотров: 187 | Нарушение авторских прав


Читайте в этой же книге: ОБЩАЯ ХАРАКТЕРИСТИКА ОСНОВНЫХ ЗАДАЧ ЭТАПА КОНСТРУКТОРСКОГО ПРОЕКТИРОВАНИЯ | МАТЕМАТИЧЕСКИЕ МОДЕЛИ СХЕМ ЭВС | МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ КОМПОНОВКИ СХЕМ КОНСТРУКТИВНО УНИФИЦИРОВАННЫМИ МОДУЛЯМИ | ПОСЛЕДОВАТЕЛЬНЫЙ АЛГОРИТМ КОМПОНОВКИ | ЗАДАЧА РАЗМЕЩЕНИЯ КОНСТРУКТИВНЫХ МОДУЛЕЙ | КОНСТРУКТИВНЫЕ АЛГОРИТМЫ РАЗМЕШЕНИЯ | Метод обратного размещения. | ТРАССИРОВКИ. | ЛУЧЕВОЙ АЛГОРИТМ ТРАССИРОВКИ. | Алгоритм Рабина. |
<== предыдущая страница | следующая страница ==>
Итерационные алгоритмы размещения| Трассировка печатных соединений

mybiblioteka.su - 2015-2024 год. (0.008 сек.)