Л1-Савельев, Овчинников - Конструирование ЭВМ и систем - 1984 год, страница 51

Построение базовой модели из первичного описания выполняется в два этапа: преобразование исходного описания во внутреннее представление данных и получение структуры памяти информапионных массивов модели из него. Получение внутреннего представления данных о схеме заключается в преобразовании совокупности звеньев (записей) предложений входного языка в векторную структуру простых элементов данных массивов УЭ, ТЭ, МК, МЦ: Х [В) -+ У" [й[, где Х вЂ” имя (указатель) поля звена„И вЂ” переменное имя звена; У вЂ” имя вектора (УЭ, ТЭ, МК, МЦ); й — индекс. Алгоритм построения структуры памяти информационных массивов базовой модели нз внутреннего представления данных о схеме.

Массивы МЭ, ТЭ, МК и УЦ рассматриваем как множество А упорядоченных четверок вида < УЭ, ТЭ, МК, УЦ >. Если цепи и элементы идентифицированы именами, то им присваиваются условные номера. Основные пункты алгоритма. 1.

Элементы массива А упорядочиваем по номерам элементов схемы, т. е. в множестве А образуем множество подмножеств А; упорядоченных четверок с одинаковыми первыми элементами: А = — (А!7!' = 1, М), А; = — ( УЭ, ТЭ, МК, Л!Ц >з7й =- 1, а!), где У вЂ” количество элементов схемы; и; — количество задействованных контактов 1-го элемента. 2. По третьему и четвертому элементам упорядоченных четверок в каждом подмножестве А; формируем упорядоченные двойки вида «- УК, МЦ - и приписываем нм номер и тип элемента.

Получаем подмножество вида А;=-(<УЭ, ТЭ >, «УК, УЦ>ьй= — 1, и;'»). 3. Из каждого подмножества А! номер и тип элемента заносим в массивы номеров и типов элементов базовой модели. Получаем множество А,". =- ( < МК, МЦ > ь!'я = 1, л!).

4. Элементы массивов А; упорядочиваем в соответствии с распо ложением контактов элементов схемы и разбиваем на два непересекающихся подмножества в зависимости от того, является второй элемент упорядоченной пары выходным или входным контактом: А;- = ( < МК, МЦ > !!'1 =- 1, и!), Л; = ( < МК, МЦ > !Ц = 1, и ), где и'; 1 и! = а!, а! и и,". — количество задействованных выходных и входных контактов !'-го элемента схемы. б.

Объединяем первые элементы упорядоченных двоек, имеющих одинаковый второй элемент, в упорядоченные л-ки (слова-выходы и слова-входы !ъго элемента схемы) и приписываем им номер цепи, т. е. формируем новыеупорядоченныедвойки вида( УК,, УКм..., УК!>, МЦ > . Получаем подмножества: А; =(«МК,>В=1, Т1, МЦ>!!1=-1,5!), А; =- (~МК,> — — 1, Т!, МЦ >!!1 = 1, 5!), где Т' — количество контактов, входящих в 1-е слово-выход; Т!— ! количество контактов, входящих в 1'-е слово-вход; 5,' и 5;: — количе- ство слов-выходов и слов-входов !-го элемента схемы соответственно. 6.

Номера цепей, т. е. вторые элементы упорядоченных двоек вида «МК!>М= 1, Т! (Т!), МЦ >, подмножеств А, и А, заносим в массивы Л(НЦ[ и МНЦ2 соответственно (см. рнс. 1! .5). Формируем подмножества А,' и А упорядоченных а-ок вида < МК, > Ц = ! = 1, Т) (Т') >, т. е, слова-выходы и слава-входы !'-го элемента схемы: А ! — — (« УК, > В = 1, Т; > Д = 1, 5)), А' .=(«ЛIК,>Ц = 1, Г; >Д=1,5!). Множество этих подмножеств (! = 1, М) образуют массивы слов- выходов (МВЫХК) и слов-входов (Л4ВХК) соответственно. 7. Вычисляем элементы массивов Л!ГРКВЫХ и МГРКВХ по правилу: МГРКВЫХ; = Л4ГРКВЫХ,, + [А!1" [, Л(ГРКВХ! = МГРКВХ! ! + [А, причем МГРКВЫХ, = МГРКВХ, -- О. 8. Формируем подмножества Р; и Щ, элементы которых равны чис- лу контактов, входящих в 1-е слово-выход (вход): Р, = (Т[l[ = 1, 5,'), 9! =-- (Т'! 11' — — 1, 5;:).

9. Формируем множества Р и ф Р =-. (Р!~!' =- 1, М), Д = Я!!! = 1, Л!) или Р = (р„lй = 1, 5'), [~= (д!М =- 1, 5"), где 5' = 2; 5;., 5" =- 2"„5! и вычисляем элементы массивов границ ! — ! !=! слов-выходов и слов-входов по правилу: МГРСВЪ|Х„= МГРСВЪ|Х,, + ры МГРСВХ, = МГРСВХ,, + дь причем МГРСВЪ|Х, = МГРСВХ, = О. 10. Элементам массивов МНЦ| и МНЦ2 сопоставляем числа натурального ряда /г = 1, 2, ..., Э'; 1 = 1, 2, ..., 8". Упорядочивая числа натурального ряда й = 1, 2, ..., В' в соответствии с номерами цепей массива МНЦ|, а числа ряда | = 1, 2, ..., 5" в соответствии с номерами цепей массива МНЦ2, получаем массивы номеров указателей слов- выходов (МНУТ-') н слов-входов (МИУР) для обратного и прямого отображений.

11, Массивы )УЦ, НЭ, ФК рассматриваем как множество В упорядоченных троек вида «ЖЦ, ФЭ, ЖК ) . Выполняем упорядочивание элементов массива В по номерам цепей, т. е. в множестве В образуем множество подмножеств В упорядоченных троек с одинаковым первым элементом: В=(В |т=1, М), В =(«)УЦ, )УЭ, НК: „|й=1, и где М вЂ” число цепей схемы; и — количество контактов, принадлежащих и-й цепи. 12. Из упорядоченных троек исключаем номер цепи, получаем множество подмножеств упорядоченных двоек: В' =- ( «НЭ, ФК ) „|й = 1, и„). 13, Каждое множество В' разбиваем на два непересекающихся подмножества В' и В' в соответствии с выходными и входными кон. тактами элементов: 15. В массивах В" и В' исключаем вторые элементы упорядочен- ных двоек: В = (НЭ||1 = 1, Н'), В = (НЭ|11 = 1, ,В" ). 16.

Вычисляем элементы массивов границ указателей прямого и обратного отображений (МГРУР и МГРУР-т) по правилам: МГРУР„= МГРУР, + )В„"'~, МГРУГ,„' = МГРУР ' ~ + ~В„Д, причем МГРУРо = МГРУРо' = 0 17. Множество подмножеств В и В Оп = 1, М) образуют массивы номеров элементов прямого (МНЭР) и обратного (МНЭР-т) отображений соответственно. Построение базовой модели схемы закончено. В' = ( «ФЭ, НК ) 1Н = 1, л' ), В' = («НЭ, ЛК ~,Н = 1, п"), где и' + л" = и, и' и и" — количество выходных и входных контактов, принадлежащих и-й цепи соответственно. 14. Объединяем вторые элементы упорядоченных двоек подмножеств В' и В', имеющие одинаковый первый элемент, и приписываем нм номер элемента, т.

е. формируем новые упорядоченные двойки вила «НЭ, «ЖК„НКм ..., й|К,,р. Получаем подмножества: В,„= ( =ФЭ,«НК,),Н="1, Р; '° Я=1, Р'), В;= («ЙЭ,«НК,),Н=1, Р! ~,|/=1, г".), где Р' — количество элементов, выходные контакты которых принадлежат т-й цепи; Н вЂ” количество элементов, входные контакты которых принадлежат т-й цепи; Р; 'и Р1 — количество контактов, входящих в |-е слово-выход или слово-вход соответственно. иа СПИСОК ЛИТЕРАТУРЫ ОГЛАВЛЕНИЕ 1. Абрайтис Л. Б., Шейиаусхас Р. Н., /Кияявичюс В. А. Автоматизация проектирования ЭВМ. — Мл Советское радио, !978. — 269 с. 2. Наффин Р., Питерсон Э., Зенер К.

Геометрическое программирование.— М,с Мир, !972. — 31! с. 3. Деиьдобренко Б. Н., Малика А. С. Автоматизация конструирования РЭА. — Мл Высшая шкала, 1980. — 384 с. 4. Доляарт В. М., Новик Г. Х. Конструктивные и электрические характеристики многослойных печатных плат. — М.: Советское радио, !974. — 87 с. 5. Нруясинин Г.

В. Надежность автоматизированных систем. — М.: Энергия, 1977. — 536 с. 6. Нульнез Г. Н„Тарновский Н Н. Тепловые режимы электроияой аппаратуры. — Лл Энергия, 1971. — 248 с. 7. ЗыковА. А. Теория конечных графов, т. 1. — Новосибирск: Наука, 1969.— 544 с. 8. Конструирование функциональных узлов ЭВМ на интегральных схемах/Ермолаев Б. Н., Вартанян В. Н., Нудоров Н.

В. и дрл Под ред. Б. Н. Ермолаева. — Мл Советское радио, !978. — 200 с. 9. Майоров С. А., Крутовских С. А,, Смирнов А. А, ЭВМ: Справочник по конструированию/ Под ред. С. А. Майорова. — Мл Советское радио, 1975.— 504 с. !О. Мелихов А. Н., Берштейи Л, С., Курейчих В. М. Применение графов для проектирования дискретных устройств. — Мл Наука, 1974. — 303 с. 1!. Методы разбиения схем РЭА на конструктивно законченные части/ Морозов К. К., Ме шхов А. Н., Бирштейн Л. С, и дрл Под ред.

К. К. Морозова. — Мл Советское радио, 1978. — 134 с. 12. Наумов Ю. Е., Аваев Н. А., Бедрековский М. А. Помехоустойчивость устройств на интегральных логических схемах. — Мл Советское радио, 1975.— 215 с. 13. Ненашев А. П., Колсдов Л. А. Основы конструирования микроэлектронной аппаратуры. — М.: Радио и связь, !98!. — 303 с. !4. Овчинников В. В., Ншхуняи В. Л., Чичерин Ю. Е.