О КРИТЕРИИ ОПТИМАЛЬНОСТИ МОДЕЛИ ПОВЕДЕНИЯ КОМБИНАЦИОННЫХ СХЕМ

Иванов Александр Леонидович

канд. техн. наук, доцент Российского государственного социального университета (РГСУ), г. Москва.

E-mail: Alex_Ivanov1949@mail.ru

Рассматривая поставленную задачу, которая при предлагаемом подходе ранее не изучалась, необходимо отметить, что несмотря на многочисленные исследования, направленные на формирование схем цифровых устройств с жесткой логикой (ЦУ), отличающихся высокотехнологичной структурой для их микроэлектронной реализации [2; 3], сохраняется противоречие между этапом ТП — технического проектирования ЦУ — и предшествующим ему этапом логического проектирования (ЛП). На этапе ТП решаются задачи компоновки, размещения конструктивных модулей (КМ) ЦУ, а также трассировки их соединений. Здесь стараются получить унифицированные варианты конструкций, особенно в условиях создания монолитных БИС или БГИС и применяют  критерии оценки качества решений на каждой стадии ТП, как:

_j    (1)

где U_ij — дуги графа, соединяющие подграфы G_i — отображает систему элементов, образующих i-тый КМ;

F=P+λD, (2)

где  Р — число межмодульных связей,  D — число типов КМ,

λ — коэффициент относительной важности  P и D.

Это позволяет получать более высокие технологические характеристики микроэлектронного ЦУ. Алгоритм, приведенный в [6, с 81], позволяет по данному критерию оптимизировать модель структуры ЦУ так, что она характеризуется минимальным числом типов КМ.

На выделении и формировании часто повторяющихся (устойчивых) групп элементов (т. н. базовых структур — БС) основан и другой алгоритм типизации. Здесь каждый из вариантов состава БС формируется с использовании коэффициента относительной связности, выступающего в качестве локально- оптимального критерия, что в общем случае приводит к уменьшению числа внешних выводов КМ.

Для ЦУ различных классов и, прежде всего, для восстанавливаемых ЦУ, универсальным показателем, оценивающим унификацию КМ и характеристики надежности является потребный объем ЗИП. Поэтому наиболее точно отражает качество таких устройств полученный аналитически критерий L [4]:

L=a 

где b_i — число КМ i-го типа в ЦУ;  - число КМ i-го типа в ЗИП; t — число типов КМ в ЦУ; а=2-3 для радиотехнических предприятий.

Хотелось бы отметь, что критерий (3) получен аналитически впервые в отличие от множества предлагаемых критериев, полученных «с потолка».

Заметим,  при выводе выражения (3) полагалось, что стоимость модулей всех типов одинакова. В реальности это не выполняется, поэтому в выражение (3) следует ввести нормирующий коэффициент Ni — уровень интеграции КМ i-го типа. Тогда критерий оптимальности структуры восстанавливаемых ЦУ будет иметь вид:

L=a  ,            (4)  

при ограничениях:

V ≤ V_доп, Т  ≤ Т _доп,                  (5),

где: V_доп — допустимое число внешних выводов КМ,       Т _доп — допустимое число КМ в ЦУ.

В то же время на этапе ЛП продолжают применять (главным образом в теории) приближенные методы минимизации ЦУ, поскольку это — каноническая оптимизация,  и программное обеспечение этого процесса давно и подробно разработано.

Для того, чтобы единая стратегия проектирования сохранялась на всех этапах, необходимо на каждом этапе проводить оптимизацию по критерию, отражающему характеристики того типа модели ЦУ, который  используется на данном этапе и который имеет один и тот же смысл и на следующем этапе. Иначе говоря, необходима оптимизация по адекватным критериям.

Значит, для проектирования ЦУ различного назначения следует на этапе ЛП сформировать критерии оптимальности модели поведения (МЛП), адекватные критериям  (2,3,4) этапа ТП с последующим получением такого вида МЛП ЦУ, который бы удовлетворял сформированным критериям.

Здесь хочется отметить совершенно новый подход к ЛП ЦУ: предлагается не использовать настраиваемые КМ для реализации полученной аналитически МЛП ЦУ, а получать такой вид МЛП, который позволял отображать её абсолютно одинаковыми КМ без всякой настройки, лишь подавая на определенные входы константы: 0 или 1. Поскольку такой подход никто из известных мне авторов не публиковал, то хочется думать, что он составляет новое научное направление, которое заслуживает тщательной разработки.

Определение 1. Морфологической оптимизацией МЛП  ЦУ называется её формирование в виде, обеспечивающем получение минимума типов КМ, имеющих заданные конструктивные характеристики, реализующих ЦУ [8].

Одной из первых попыток морфологической оптимизации МЛП комбинационных схем (КС) следует признать эвристический метод, предложенный А.Г. Алексенко [1, с. 98], в основе которого лежит получение такого вида МЛП, который отображается минимальным числом функциональных модулей в избыточном Ф-базисе. Цель оптимизации — получение булевых выражений (МЛП КС), экономично реализуемых по числу МДП-транзисторов в соответствии с критерием:

Ф =  ,    (6)

где m — число структур Ф-типа, т.е. сочетания логических элементов И-ИЛИ-…-НЕ и ИЛИ - И- ИЛИ-…-НЕ, включая вырожденные конфигурации ИЛИ-И- …- НЕ, И-НЕ и т. д.;

Очевидно, что такой критерий в некоторой степени адекватен целевой функции (2),  однако он не отражает затраты на эксплуатацию ЦУ и не инвариантен к виду базовой технологии КМ.

В последнее время в связи с принципиальной возможностью изготовления заказных СБИС уже много лет большое число специалистов [7; 9] склоняются к приоритету несвязанных вентильных матриц (UGA) или групп активных элементов (AEG) перед другими типами интегральных субструктур, т.к. они наилучшим образом подходят к технологии БИС, а длительность цикла их разработки и разработки ЦУ на их основе в 3-10 раз меньше, чем заказных БИС. Учитывая это, очевидно, что особое внимание целесообразно уделять разработке методов морфологической оптимизации МЛП ЦУ, которые наилучшим образом позволяют реализовать устройства на основе субструктур, подобных  UGA или AEG.

Значит, при проектировании ЦУ различного назначения следует осуществлять  морфологическую оптимизацию их МЛП по критерию адекватному целевой функции (4) при ограничениях (5).

Исходной информацией для стадии компоновки ЦУ является его схема электрическая принципиальная, которая на этапе КП трансформируется лишь топологически. Значит априорно определено, что если морфологические свойства схемы плохие, то нельзя достигнуть требуемых характеристик технологичности, т.к. все возможные алгоритмы компоновки, ориентированные на удовлетворение перечисленных выше показателей качества, позволяют лишь незначительно улучшить морфологические свойства ЦУ. Поскольку же эти алгоритмы очень сложны и требуют больших вычислительные ресурсов, затрат машинного времени и длительной подготовки информации для ввода в ЭВМ, то при проектировании ЦУ реальной сложности необходимость и достижимость  решения задачи унификации КМ на этапе КП становятся проблематичными.

Тем самым радикально возрастает актуальность выполнения морфологической оптимизации ЦУ на этапе ЛП, в результате которого получаем схему электрическую функциональную, максимально приближенную к схеме электрической принципиальной, но обладающую весьма полезными свойствами.

Задача установления адекватности математических выражений в контексте формул (2) и (4) ранее никогда не ставилась и не решалась.

Однако на основании некоторых известных математических методов [5, с. 516] можно сформулировать предложения относительно путей формального установления адекватности математических выражений.

Предложение 1. Алгебраические выражения можно представить словами в ассоциативном исчислении. Чтобы задать ассоциативное исчисление, необходимо определить алфавит и конечную систему допустимых подстановок. Слова можно задать в алфавите букв: математических символов переменных и алгебраических операторов. Тогда наиболее вероятно, что адекватными будут формулы, представляемые эквивалентными словами.

Заметим очевидное: отношение эквивалентности — самое сильное свойство на любом пространстве математических процедур.

Определение 2.  Два слова называются эквивалентными, если одно из них можно получить из другого последовательным применением конечного числа подстановок.

Предложение 2. Понятие изоморфизма обычно определяется в теории множеств. Однако, если интерпретировать алгебраические выражения в терминах теории множеств как множество математических символов переменных и заданным на пространстве переменных подмножеством алгебраических операторов, то, видимо можно говорить и о изоморфизме математических выражений. Тогда наиболее вероятно, что адекватными будут изоморфные формулы.

Определение 3. Изоморфными называются такие множества, которые обладают одинаковыми свойствами относительно определенных на них операций.

Предложение 3. Наиболее вероятно, что адекватными будут равносильные формулы.

Определение 4. Две функции считаются равносильными, если на любых значениях аргументов эти функции принимают одинаковые значения.

На основании последовательного применения этих предложений получим формулы, адекватные выражениям (4) и (6):

Реализация предложения 1. Зададим ассоциативное исчисление алфавитом символов (пусть N_i=1):

{а; b_i; l_i; q_i; h_i (i=), V, V_доп, υ, υ_крит., Т, Т_доп, R, R_доп.; *, +, ≤}

и системой допустимых подстановок (   —  есть символ подстановки):

{[ а* b_i+] — [ а* q_i+]; [l_i— h_i , () ]; [lt— ht];[V— υ];

[≤V_доп— ≤υ_крит.];[T—R]; [≤Т_доп — ≤R_доп.]}.

В результате применения каждой подстановки в исходном слове можно получить новое слово, которое входит в образующуюся при подстановках дедуктивную цепочку слов. Для наглядности представим выражения (4) и (6) в виде:

  L= (ab₁+)( ab₂+)…(ab_t+) (l₁+)(l₂+)…(l_t)       (7) 

 (V)( ≤V_доп.); (T)( ≤Т_доп).                  

  После применения 2t+4 подстановок в слове (7) получим слово-систему:

K= (aq₁+)(aq₂+)…(aq_t+) (h₁+)(h₂+)…(h_t)

                       (υ)( ≤υ_крит.); (R)( ≤R_доп.).                      (8)

На каждом шаге можно определять эквивалентность исходного и вновь сформированного слова, используя дедуктивные варианты — свойства, остающиеся постоянными для всех слов дедуктивной цепочки. Например, если в подстановках правая и левая части имеют одинаковое число вхождений буквы а, то в любой дедуктивной цепочке все слова должны содержать одно и то же число вхождений буквы а. Сравнивая систему слов в начале и в любом месте, в том числе и в конце дедуктивной цепочки, устанавливаем, что число вхождений буквы а равно t. Следовательно, система слов (8) эквивалентна исходной системе слов (7), а значит систему (8) можно представить в виде:

              K= a_{i     +  i}                   (9)

(υ)( ≤υ_крит.); (R)( ≤R_доп.).

Реализация предложения 2. Выражения (4) и (5), соответственно, представляются подмножествами переменных:

{a, b_i, l_i (i=1,t)},{V, V_доп}, {T,  Т_доп}

и операторов: {+, *} и { ≤ }.

В силу определения 3 выражения, изоморфные формулам (4) и (5), должны иметь вид:

F{C;q_i,h_i (i=);+,*} = C _{i     +  i}      (10)

                      υ ≤υ_крит.; R ≤R_доп.,                       (11)  

т. к. переменные обладают одинаковыми свойствами относительно определенных на них операций {+, *, ≤ }.

Дадим ряд определений [8].

Булево выражение (БВ) задается на пространстве, представляемом кортежем <Ф,а₁,…,а_θ>, где Ф={φ_i}, i=, есть множество булевых подфункций, в то время, как множество А = {a_δ∈A|δ= } — бинарные отношения, заданные на множестве Ф, т. е. булева функция

f (x₁,x₂,…,x_L) = { φ₁a₁ φ₂a₂… a_θ φ_l},       (12)

В частности может быть, что А={а1}.

Определение 5. Морфологической структурой БВ   y= f (x₁,x₂,…,x_L), x_i ∈ X, где у — выходной сигнал, соответствующий в каждый момент автоматного времени комбинации входных переменных x_i, называется совокупность подфункций Ф={φ_i}(i=, и связывающих их бинарных операторов А={a _δ}, (δ = , таких, что φ_i a_δ φ_j,  (}.

На первый взгляд наблюдается некоторая тавтологичность данного определения, но здесь используется «структурный» подход к анализу формулы. Всегда в дальнейшем будем полагать, что любая подфункция φ_i реализуется КМ некоторого уровня конструктивной иерархии: БИС, чипом и т. п.

Определение 6. Качественной оценкой морфологической структуры БВ называется порядок следования (_k) бинарных операторов a_δ при конкретном варианте  расположения подфункций φ_i в пределах формулы БВ. Индекс k определяет класс БВ [8].

Определение 7. БВ F₁ и F₂ называются морфологически однородными на конечном множестве бинарных операторов А_f, если _k(F₁) = _k(F₂).

Замечание 1. Поскольку подфункцию φ_i (i∈{тоже можно представить в виде φ_i  = { φ_{i i}  a _δi  φ_{i j}}, то определения 5, 6, 7 верны и для подфункции φ_i.

Замечание 2. Определение 7 отличается от определения однотипных БФ, входящих в одну из L-классификаций [5, с. 670], т. к. БВ F₁ и F₂ не относятся в общем случае к классу бесповторных.

Реализация предложения 3. Исходя из данных определений, задача морфологической оптимизации МЛП КС формулируется как поиск (или формирование) такого БВ, которое представляется декомпозицией морфологически однородных подфункций φ_i (i∈{

В таком случае формулы (4), (5),  (10) и (11) будут попарно равносильны, если С=а.  При изготовлении ЦУ методами интегральной технологии последнее допущение справедливо, если БГИС разрабатывается и изготавливаются на том же предприятии, что и ЦУ. Поэтому критерием оптимальности МЛП КС будем считать выражение вида:

K= a ,  или, что то же самое,

K=  ,              (13)     при ограничениях

      υ ≤υ_крит.; R ≤R_доп.,          (14)

где а=2-3 для радиотехнических предприятий; t — число типов морфологически однородных подфункций в БВ; q_i — число морфологически однородных подфункций i — го типа; h_i — число подфункций i — го типа, реализуемых в КМ дополнительно к основным и коммутируемым либо в процессе изготовления ЦУ металлизацией, либо в процессе настройки или эксплуатации электрической коммутаций; Ni — число морфологически однородных подфункций i — го типа, реализуемых в КМ; υ — число букв (переменных или их отрицаний) в подфункции;  υ_крит — максимальное число букв в подфункции, при котором БВ предварительно не подвергается декомпозиции; R — общее число подфункций, реализуемых в КМ.

При N_i = N = const подфункции, входящие в число h_i, реализуются в виде отдельных КМ и составляют ЗИП.

Согласно [10] число модулей i — го типа в ЗИП для показателя обеспеченности изделия Р тр = 0,9 определяется как:

h_i, =  =     (15)

где  - знак округления до ближайшего меньшего целого числа; t_n — время пополнения ЗИП; Ti — среднее время безотказной работы КМ i — го типа; =1/ T_i — интенсивность отказов КМ i — го типа. Если построить график функции (15), то легко убедиться, что чем меньше отношение t_n/T_i, тем больший эффект достигается за счет сокращения числа типов КМ.

Таким образом, предложенный критерий оптимальности МЛП КС определяет качество решения задачи унификации на этапе ЛП и характеристики надежности.

Выводы и основные результаты.

1.  Впервые предложено при синтезе КС выполнять  настройку не конструктивных модулей, отображающих модель поведения КС, а настройку самой модели поведения для её отображения одинаковыми КМ без их дополнительной настройки.

2.  Впервые предложено выполнять оптимизацию модели поведения микроэлектронных ЦУ по критериям, адекватным показателям качества, применяемым на этапе конструкторского проектирования.

3.  Аналитически получен критерий оптимальности морфологической структуры модели поведения восстанавливаемых ЦУ, отражающий характеристики надежности и технологичности. Выражение критерия получено в результате использования предложенных принципов формального установления факта адекватности показателей качества.

Cписок литературы:

1.Алексенко А.Г. Основы микросхемотехники.  М.: ЮНИМЕДИА-СТАЙЛ.   Серия: Технический университет. 2009. — 448 с.

2.Артюхов В.Л., Копейкин Г.А., Шалыто А.А. Настраиваемые модули для управляющих логических устройств.  Л.: Энергоиздат, 1981. — 168 с.

3.Баранов С.И., Скляров В.А. Цифровые устройства на программируемых БИС с матричной структурой. М.: Радио и связь, 1986.— 272 с.

4.Березин А.И. Об использовании структурной избыточности на этапе конструкторского проектирования типовых элементов замены. // В сб. Автоматизация конструкторского проектирования РЭА и ЭВА.  Пенза: ППИ. — 1977, С. 21 — 24.

5.Выгодский М.Я. Справочник по математике. М.: АСТ, Астрель, 2010. — 1056 с.

6.Григорьян С.Г. Конструирование электронных устройств систем автоматизации и вычислительной техники. М.: Феникс. Серия: Высшее образование. 2007.— 304 с.

7.Dunbury A.J. Filling the Compexity Gap. // Journ. For Angan and Manedg. In Electronics. —1977, v. 51, № 12, p. 51-57.

8.Иванов А.Л., Угрюмов Е.П. Особенности оптимизации структур комбинационных схем. // Известия ВУЗов. Приборостроение. —1980, т. 23, № 8, С. 34 — 37.

9.Hurst S.L. A Survey of  Published Information on Universal Logic Arrays. //  Microelectronics and Reliabil. — 1977, v. 16, № 6, p. 663 — 674.

10.ОСТ 4.ГО.012.021. Аппаратура радиоэлектронная. Проектирование и комплектование ЗИП. — Редакция 1 — 71.