Устройство для управления трассировкой электрических соединений на плоскости

 

Изобретение относится к технологическим средствам, обеспечивающим автоматизацию процесса трассировки соединений в интегральных схемах и печатных платах. Целью изобретения является расширение области применения за счет учета результатов предыдущего цикла. Устройство содержит дешифратор команд, регистр состояния, дешифраторы строки и столбца, M<SP POS="POST">.</SP>N блоков фиксации трассы, M<SP POS="POST">.</SP>N групп элементов И и M<SP POS="POST">.</SP>N групп элементов ИЛИ. Устройство имеет вход кода команды, вход номера строки и вход номера столбца, выход состояния и вход синхронизации. Устройство работает под управлением внешней микроЭВМ. 1 з.п. ф-лы, 3 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

)/l=== (191 щ) S С 06 F 15/20

К А ТОРСКОМУ СВИДЕТЕЛЬСТВУ

2 (54) УСТРОЙСТВО ДЛЯ УПРАВЛЕНИЯ ТРАССИРОВКОЙ ЭЛЕКТРИЧЕСКИХ СОЕДИНЕНИЙ НА

ПЛОСКОСТИ (57) Изобретение относится к технологическим средствам, обеспечивающим автоматизацию процесса трассировки соединений в интегральных схемах и печатных платах. Целью изобретения является расширение области применения за счет учета результатов предыдущего цикла. Устройство содержит дешифратор команд, регистр состояния, дешифраторы строки и столбца, Мх N блоков фиксации трассы, Их N групп элементов И и M x N групп элементов ИЛИ. Устройство имеет вход кода команды, вход номера строки и вход номера столбца, выход состояния и вход синхронизации. Устройство работает под управлением внешней микроЭВМ. 1 з.п. ф-лы, 3 ил. (21) 6 (22) 1 (46) 3 (72)

Н.И. (53) 6

Bla

А para

tectur

18th .le, Т

Но

А phys

Conf

Acade

Изо ратор 3 строки, дешифратор 4 столбца, M z N блоков 5 фиксации трассы, Mx N групп элементов И 6-8 и Hz N групп элементов ИЛИ 9-11.

Устройство имеет вход 12 кода команды, вход 13 номера строки, вход 14 номера столбца, выход 15 состояния, :вход 16 синхронизации. ческим автома соедин печат

Цел ласти зульта

На ройств

:сации

Уст .команд

ГОСУД РСТВЕННЫЙ КОМИТЕТ

ПО И БРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ КТ СССР

07278/24-24 ,11.88 .11.90. Бюл. ¹ 43

3. Копциовский, Г.В. Кушакова, азунов и И.Л. Сигалов

1.325(088.8)(56) reuer М.А., Shamsa K. А hardware outer. — J. Digital Syst

vol.4. по.4, Computer Sci. Press,1980. рр.39 -408.

Т. БСе зЛс М. W. van Cleemput, llel bit map processor archifor DA algorithms, in. Proc.

sign Automation Conf (Nashvil1981), рр. 837-845.

S.Y., Nair R., Shapiro Е.

ical design machine in VKSI 81

roc., I.P. Gray, Ed. New York:

ic Press, 1981. ретение относится к технологисредствам, обеспечивакяцим изацию процесса трассировки ний в интегральных схемах и х платах. изобретения — расширение обрименения за счет учета ре- ов предыдущего цикла. иг. 1 и 2 приведена схема устна фиг. 3 — схема блока фик-. рассы. ойство содержит дешифратор 1 регистр 2 состояния, дешифБлок 5 фиксации трассы содержит пять элементов НЕ 17-21, три триггера

22-24, одиннадцать элементов ИЛИ 2535, шестнадцать элементов И 36-51. t608686

Блок 5 фиксации трассы имеет четыре асинхронных информационных входа.

52-55, вход 56 синхронизации„ вход

57 установки запрета, вход 58 установ- ки источника, вход 59 установки в "0" счетчика, вход 60 установки в исходное состояние, синхронный информационный выход 61, асинхронный информационный выход 62. Устройство работает под 1О управлением внешней микроЭВМ.

Устройство работает следующим образом.

МикроЭВМ выдает на вход устройства код команды, адрес координаты блока фиксации трассы и импульсы синхронизации. Используются 11ять команд. По команде "Установка исходного состояния" все блоки 5 устанавливаются в исходное состояние,, соответствующее 2р нулевому состоянию триггеров 22-24.

Сигнал установки исходного состояния с выхода дешифратора 1 поступает на входы элементов ИЛИ 34 всех блоков

5. С выхода элемента ИЛИ 34 калдого 25 блока 5 сигнал установки в "0" поступает на входы триггеров 22-24.

Установка запрета. При выполнении этой команды на входы дешифраторов 3 и 4 поступает адрес соответствующего блока 5. При выполнении этой команды триггеры 22-24 соответствующего блока

5 устанавливаются в "1". Установка в.

"1" триггеров 22-24 происходит следующим образом. На четвертом выход дешифратора 1 появляется единичный

35 потенциал, который поступает на первые входы всех групп элементов И 7.

Единичный сигнал появляется на выходе только того элемента И 7, на вторые 40 и третьи входы которого поступают единичные сигналы с выходов дешифраторов 3 и 4. С выхода соответствующего элемента И 7 сигнал поступает на входы элементов ИЛИ 31-33, с выходов 45 которых эти сигналы поступают на входы установки в "1" триггеров 22-24 .J соответствующего блока 5.

Команда установки источника сопро вождается адресом и выполняется точнЬ так же, как и команда установки запрета за исключением того, что сигнал с выхода дешифратора 1 поступает на входы элементов И 8. Сигнал с выхода элемента И 8 соответствующего блока 5 поступает через элемент ИЛИ 33 блока

5 на вход установки в "1" триггера

24. На этом работа команды установки источника заканчивается.

Команда сброса счетчиков. Сигнал с выхода дешифратора 1 поступает на все элементы И 44 всех блоков 5. На втором входе элемента И 44 каждого блока 5 будет единичный сигнал при условии, что хотя бы один из триггеров 22, 23 ипи 24 данного блока 5 будет находиться в нулевом состоянии. Сигнал с выхода элемента И 44 каждого блока 5 через элемент ИЛИ 34 этого блока поступает на входы триггеров 22-24 и устанавливает их в "0". Таким образом, команда сброса счетчика обеспечивает установку в "0" всех триггеров блоков

5 за исключением тех блоков, где в триггерах 22-24 записан код 111 (т.е. запрет).

Команда дешифратора "Запрос состояния" точно так же, как и команда установки источника и установки запрета, сопровождается адресом соответствующего блока 5, который поступает на дешифраторы 3 и 4. Сигнал с выхода дешифратора, 1 поступает на первые входую всех элементов И 6. Единичный сигнал появляется на выходе только того элемента И 6, на вторые и третьи входы которого поступают единичные сигналц с выходов дешифраторов 3 и 4. Сигнал с выхода элемента И 6 поступает на элементы И 49-51 соответствующего блока 5 и обеспечивает выдачу состояний триггеров 22-24 на выходы соответствующего блока 5. Так как на выходе всех остальных блоков 5 сигналы отсутствуют, то сигналы состояния триггеров данного блока через элементы ИЛИ

9-11 соответствующего блока 5 и всех блоков 5, вторые индексы которых совпадают с вторым индексом данного блока, а первый индекс больше индекса данного блока, и через элементы ИЛИ

9- 11, индексы которых меньше или равны второму индексу данного блока, поступают на вход регистра 2. Все команды с выхода дешифратора 1 вырабатываются при отсутствии импульсов синхронизации. Выходы элементов И 46-48 соответствуют состояниям триггеров

22-24 каждого блока 5 за исключением кода 111 (все триггеры 22-24 данного блока 5 установлены в "1"), который через элементы И 45 и HE 20 преобразуется в "0", блокирующий выходы элементов И 46-48.

Элементы ИЛИ 25-27 каждого блока 5 обеспечивают объединение сигналов от соседних блоков 5„ Элемент ИЛИ 25

1 608686 к ажд разр четь элем рые с вь них

5 на на в блок бо ч но о рых запр тов либо

ИЛИ код 1

001, зует

27-3

001 ние элем

Данн пере коль обес элем

И 41 уста хотя в со мент и, с

НЕ 21 менть кода выхо любо

21-24 хро от тови

Вь новки согла обесп ров 2 после тояни ступ чес испол

5 го блока 5 объединяет старшие ды с выходов элементов И 46 всех ех соседних блоков 5. Аналогично йты ИЛИ 26 и 27 объединяют втомладшие разряды соответственно одов элементов И 47 и 48 соседлоков 5. триггеры 22-24 данного блока одятся в нулевом состоянии, то ходах элементов И 46-48 соседних в 5 будут либо нулевые коды, листь из них будет иметь ненулевые, наковые коды (при этом у некотооседей может быть состояние. та 111). Если на выходах элемен25-27 будет либо код 000, код 111, то на выходе элементов

8-30 будет код 000. Любой другой а выходе элементов ИЛИ 25-27 20

010, 011, 100, 101,110.преобрая в код на выходе элементов ИЛИ в коды 010, 011, 100, 101, 110, оответственно. Это преобразовабеспечивают элементы НЕ 17-19, 25 нты И 36-40 и элементы ИЛИ 28-30. е преобразование соответствует оду к следующему значению по у чисел 1, 2, 3, 4, 5, 6 и 1. льс синхронизации устройства 3р ечивает перенос кода с выходов нтов ИЛИ 28-30 через элементы

43 и элементы ИЛИ 31-33 на входы овки в "1" триггеров 22-24. Если бы один из триггеров 22-24 был тоянии 1, то на выходе элеlI tt

ИЛИ 35 будет единичный сигнал ответственно, на выходе элемента будет нуль, который через элеИ 41-43 заблокирует перенос с выхода элементов ИЛИ 28-30 на

1 триггеров 22-24, т.е. наличие о ненулевого кода в триггерах не меняется по импульсам синзации.

45 оритм управления устройством ро3ВМ следующий: 1 IIIA1 . Подгоьный этап. абатывается код команды уста- 50 исходного состояния, которая но логике, описанной выше, чивает установку в "0" тригге-24 всех блоков 5. После этого овательно устанавливаются в сос- 5

111 те блоки 5, которые недодля трассировки по технологипричинам. При этом столько раз зуется команда установки запрета, сколько блоков 5 должны быть ус-. тановлены в состояние запрета 111.

Далее циклически производятся трассировки отдельных цепей. Для этого командой "Сброс счетчиков" устанавливаются в "0" все блоки 5, не содержащие запрета, т.е. доступные для трассировки очередной цепи, После этого командой "Установка источника" обеспечивается установка в состояние 001 того блока 5, который является началом проводимой трассы (таких точек может быть несколько, например, необходимо продолжить от уже имеющейся трассы, в частности, при разводке цени питания, когда имеющаяся трасса яв ляется источником для ряда следуюиИх трасс). После этого микроЭВИ на вход

16 синхронизации подает импульс или пакет импульсов.

По каждому импульсу синхронизации блоки 5, имеющие нулевой код и хотя бы одного из соседей, имеющего код от 1 до 110, устанавливаются в состояние, соответствующее следующему значению кода. Так как первоначально быпи заданы одинаковые коды (001), то при каждом импульсе синхронизации происходит установка одного и того же следующего кода во все изменяемые блоки 5. Если данный блок 5 установлен в состояние К (001-110) i.-ì им-. пульсом синхронизации, то после (i+1)-го импульса синхронизации соседние с ним блоки могут находиться только в состоянии 111, (К-1), К (К+1) .

Отсутствие состояния К у соседних элементов является несущественным.По окончании пакета импульсов синхронизации по команде запроса состояния определяется состояние элемента-приемника. Если оно равно нулю, то проверяется количество пакетов импульсов синхронизации на максимально допустимое количество пакетов. Если количество пакетов превысило допустимое, то делается вывод о невозможности проведения данной трассы.

Если количество пакетов меньше максимально допустимого, то вырабатывают команду на выдачу следующего пакета импульсов синхронизации. Если состояние блока 5 приемника отлично от нуля, то прекращается выдача пакетов синхронизации и ЭВМ переходит к этапу фиксации трассы. Трасса начинает фиксироваться с блока 5 приемника, 1608686 координаты и состояние К которого запоминается. После этого блок 5 с запомненными координатами посредством команды установки запрета устанавли5 вается в состояние 111, затем последовательно командами (до 4-х) запроса состояния считываются состояния соседних блоков 5 и проверяется их состояние на равенство (К-1). Если таких блоков нет, то координаты запомненного являются координатами блока источника, и прокладка данной трассы закончена.

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

Каждый последовательно запомненный блок 5, который входит в фиксирован- 25 ную трассу, оказывается переведенным в состояние 7. Трассировка варианта данной схемы может иметь два исхода. Либо все необходимые трассы проверены и тогда задача полностью, g0 решена, либо при проведении очередной трассы ее провести не удалось. В этом случае в микроЭВИ запоминаются результат трассировки и количество пРоведенных тРасс. При Повторной по- 35 пытке трассировки за счет использования механизма случайного выбора направления при фиксации трассы трассировка пойдет по другому варианту, из двух последовательных вариантов трассировки выбирается вариант с наибольшим числом проведенных трасс.

Многократным повторением этого процесса (число рассматриваемых вариантов ограничивается заданием на трас- 45 сировку) добиваются либо получения: .завершенной трассировки, либо получения варианта незавершенной трассировки с.максимальным числом растрассированных цепей, больше чем при однократном рассмотрении. Таким образом, облегчается последующее ручное растрассирование оставшихся трасс, Формула изобретения

1. Устройство для управления трассировкой электрических соединений на плоскости, содержащее дешифратор команд, регистр состояния, дешифратор строки, дешифратор столбца, причем входы дешифратора команд, дешифратора строки и дешифратора столбца являются соответственно входами кода команды, номера строки и номера столбца устройства, выход регистра состояния является выходом состояния устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет учета результатов предыдущего цикла, устройство содержит M z N блоков фиксации трассы (где И вЂ” количество координатных точек по горизонтали, иначе столбцов, N — - количество координатных точек по вертикали, иначе строк), Mx N групп элементов И и

Их N групп элементов ИЛИ, причем i-й выход (где i = 1,И) дешифратора столбца подключен к первым входам групп элементов И -го столбца, j-й выход (где j =- 1,N) дешифратора строки под- ключен к вторым входам групп элементов И j-й строки, первый выход дешифратора команд подключен к входам установки в "0" счетчика блоков фиксации трассы, входы синхронизации блоков фиксации трассы подключены к входу синхронизации устройства, второй> выход дешифратора команд подключен к входам установки в исходное состояние блоков фиксации трассы, третий выход дешифратора команд подключен к третьим входам первых элементов И всех групп, четвертый выход дешифратора команд подключен к третьим входам вторых элементов И всех групп, пятый выход дешифратора команд подключен к третьим входам третьих элементов И всех групп, выходы первого, второго и третьего элементов И каждой группы подключены соответственно к входам установки запрета, установки источника и запроса состояния соответствующего блока фиксации трассы, асинхронный информационный выход блока фиксации трассы i-ro столбца .j-й строки подключен к первому асинхронному информационному входу блока фиксации трассы (i+1)-го столбца j-й строки, второму асинхронному информационному входу блока фиксации трассы (i-1)-ro столбца и j-й строки, третьему асинхронному информационному входу блока фиксации трассы i-ro столбца (j-1)-й строки, четвертому асинхронному информационному входу блока фиксации трассы i-ro столбца (j+1)-й

1608686

10 к в ( с б

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

ro столбца j-й строки подключены первым входам соответствующей груп5 элементов ИЛИ i-ro столбца j-й роки, выходы группы элементов ИЛИ

ro столбца j è строки подключены к орым входам группы элементов ИЛИ

+1)-го столбца j-й строки, разряды 10 нхронного информационного выхода ока фиксации трассы последнего олбца j-й строки подключены к вток входам группы элементов ИЛИ перго столбца (j-1)-й строки, разряды нхронного информационного выхода ока фиксации трассы первого столбца следней строки подключены к первым одам группы элементов ИЛИ второго олбца последней строки, выходы групп20 ементов ИЛИ последнего столбца подчены к соответствующим разрядам ода регистра состояния.

2. Устройство по и. 1, о т л и— а ю щ е е с я тем, что блок фикса- 25 трассы содержит пять элементов НЕ, и триггера, одиннадцать элементов шестнадцать элементов И, причем рвый, второй и третий разряды перro„ второго, третьего и четвертого нхронных информационных входов ока подключены к соответствующим одам соответственно первого, втого и третьего элементов ИЛИ, выходы торых подключены к первым входам ответственно первого, второго и

35 тьего элементов И, выходы которых чены соответственно к первому ду четвертого элемента ИЛИ, второвходу четвертого элемента ИЛИ, к вому входу пятого элемента ИЛИ, од третьего элемента ИЛИ подключен торому входу второго элемента И и ходу первого элемента НЕ, выход орого подключен к первым входам вертого и пятого элементов И, вывторого элемента ИЛИ подключен к тьему входу второго и второму вхочетвертого элементов И и к входу рorо элемента НЕ, выход вторoro мента НЕ подключен к вторым входам

50 вого и третьего элементов И, выпервого элемента ИЛИ подключен к рому входу пятого элемента И и к ду третьего элемента HE выход тьего элемента НЕ подключен к

55 тьим входам второго и четвертогоентов И, выход четвертого элета И подключен к второму входу пятого элемента ИЛИ и к первому входу . шестого элемента ИЛИ, выход пятого элемента И подключен к второму входу шестого элемента ИЛИ, выходы четвертого, пятого и шестого элементов ИЛИ подключены к первым входам соответственно шестого, седьмого и восьмого элементов И, выходы шестого, седьмого и восьмого элементов И соединены с первыми входами соответственно седьмого, восьмого и девятого элементов

ИЛИ, вход синхронизации блока соединен, с вторыми входами шестого, седьмого и восьмого элементов И, вход установки запрета блока подключен к вторым входам седьмого, восьмого и девятого элементов ИЛИ, вход установки источ» ника блока соединен с третьим входом девятого элемента ИЛИ, выходы седьмого, восьмого и девятого элементов, ИЛИ подключены к входам установки в и

1 соответственно первого, второго и третьего триггеров, входы установки

1I fl в 0 счетчика и установки в исходное состояние блока подключены к первым входам соответственно девятого элемента И и десятого элемента ИЛИ, выход десятого элемента ИЛИ соединен с входами установки в 0 триггеров, прямые выходы первого, второго и третьего: триггеров соединены соответственно с первым, вторым и третьим входами десятог о элемента И и одиннадцатого элемента ИЛИ, выход десятого элемента

И подключен к входу четвертого элемента НЕ, выход четвертого элемента

НЕ подключен к первым входам одиннадцатого, двенадцатого, тринадцатого и второму входу девятого элементов И, выход последнего подключен к второму входу десятого элемента ИЛИ, прямой выход первого триггера соединен с первым входом четырнадцатого и вторым входом одиннадцато го элементов И, выходы четырнадцатого и одиннадцатог о элементов И являются первыми разрядами соответственно синхронного и асинхронного информационных выходов блока, прямой выход второго триггера соединен с первым входом пятнадцатого и вторым входом двенадцатого элементов И, выходы пятнадцатого и двенадцатого элементов И являются вторыми разрядами соответственно синхронного и асинхронного информационных выходов блока, прямой выход третьего триггера соединен с вторым входом тринадцатого и первым входом шестнадцатого элеll

1608686

12 ментов И, выходы тринадцатого и шестнадцатого элементов И являются третьими разрядами соответственно синхронного и асинхронного информационных

5 выходов блока, выход одиннадцатого элемента. ИЛИ подключен к входу пятого элемента НЕ, выход которого соединен с третьими входами шестого, седьмого и восьмого элементов И, вход запроса состояния блока соединен с вторыми входами четырнадцатого, пятнадцатого и шестнадцатого элементов И.

1 608686

1608686 б2 б1

Фиг.д

Составитель С. Аверьянова

Техред А.Кравчук Корректор 0 КРавцова

Редактор Н. Тупица

Заказ 3619

Подписное

Тираж 569

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", r Ужгород„ ул. Гагарина, 101