17. Компоновка типовых элементов конструкций эвм. Постановка задачи. Критерии оптимизации и ограничения.

Задача компоновки заключ в определении схемного состава типовой конструкции каждый уровня. Эта задача реш обычно снизу вверх, т.е известна схема соедин эл-ов (i-1)-го уровня, необходимо распредел их по типовым конструкц i-го уровня. Можно выделить 2 метода реш этой задачи:1)разрезание – разрезание схемы соединения эл-ов i-1 уровня на части заданного размера. Эта задача характерна для типовых конструкций, начиная с уровня субблока. 2)покрытие – переход от схемы электр функц к схеме электр принцип.

Задача покр сложнее, чем разрез, т.к она сводится к поиску морфологической эквивалентности подграфа схемы электр принцип и графа определяемого ИС.

Критерии оптимизации при рассмотрении вопроса компоновки. 1.Мин суммарного числа модулей, необход для реализации схемы Ni=Xij – число модулей, Xij – число модулей j-го типа i-го уровня, получается в рез-е компоновки схемы. 2.Мин числа типовх скомпонованных модулей или макс коэфф их повторений Kповтор=(1-m*n)/Ni-1, n - число типов модулей, m – число эл-ов i-го уровня в модуле, Ni-1 – общее кол-во эл-ов в i-1 уровня в схеме. 3.Мин избыточность в реализации ∆mi=∑∆mi,k, mik–число неисп элементов в каждом модуле i-го уровня

4.Мин сумма числа внешних выводов всех модулей. Ri=(1/2)∑Ri,k, Rik- число внеш связей каждого модуля i-го уровня. 5.Мин сумма числа внеш выводов всех модулй Si=∑Si,k. Чем < связей, тем < вер-то отказа.

На задачу компоновки накладывается ряд огран: *число эл-ов в типовой конструкции каждого уровня и число их выводов. *требование на раздельную или совместную компоновку, связанные с обеспеч норм теплового режима помехозащищ и простоты диагностики. При компоновке БИС основное огран – площадь, отводящаяся под схему.

В точности постановку задачи компоновки формул как задача нелин целочисленного программир:

Пусть схема сост из множ-ва Е={ei}, кот соединено с множ-ом Т={tj} электр цепей. Зададим схему матрицей инцидентности, имеющую вид А=||aij||

Каждый эл матрицы aij= {1,если ei вход в цепь tj; 0, в противном случае}.

Необход скомпоновать схему в N подсхем, каждая из кот должна иметь не более Мi эл-ов и Кi внешн выводов, т.е каждая электр схема должна входить в один типовой конструктив. Необход разбить множво Е эл-ов на L подмнож таким обр, чтобы достигался один из критериев для всех сформированных подсхем.

Решение задачи д.б. матрица Х, состоит из элементов

Х=||xi,l||NxL

xil={1, если li→lj; 0, если нет}

Колво элементов L в подсхеме: L=∑ xi,l

Введем целочисленную переменную Yil, кот равна 1 если J цепь соединена с элементами L–ой подсхемы и какой-нибудь элемент из другой подсхемы, 0 иначе.

Колво внеш выводов L-ой подсхемы будет вычисляться как ∑yi,l

А суммарное колво внеш выводов всех подсхем вычисл как S=∑∑ yi,l

А число межмод соединений будет вычя след обр R=∑(∑yi,l -1)

Такое реш задачи компоновки, в приведенной постановке, возможно только методом полного перебора, что для реализации схемы не представляет возможным даже для реальной ЭВМ, поэтому практическое примен находят приближенные алгоритмы, кот делятся на три группы последовательным алгоритмом формирования состава типовой конструкции

Алгоритмы: *последов алг формир состава типовой конструкции;*итерац алг улучшения получ рез-та; *смеш