Ячейка однородной вычислительнойструктуры

 

Союз Советсник

Соцнаектическик

Расвублнк

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ >805300 (61) Дополнительное н авт. свид-ву— (22) Заявлено 040578 (21.) 2608936/18-24 -.: с присоединением заявки ¹â€” (23) Приоритет

Опубликовано 15,02Л1. бюллетень И9 6

Дата опубликования описания i 80281 (511М. Кл.

0 06 f 7!00

Государствеяяыя комятет

СССР яо делам язобретеяяй я открытяй (5З) Уд 681. 325 (088.8) В .В. Васильев, А.Г. ДодЬнов, О.Н. Голованова, Я;Я. Фенюк и В.В, Хаджинов

1 (72) Авторы изобретения (71) Заявитель

Институт электродинамики AH HHc o CCP (54 ) ЯЧЕЙКА ОДНОРОДНОЙ В61ЧИСЛИТЕЛЬНОЙ

СТ РУ КТУ РЬ

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

Известно устройство для.расчета и оптимизации сетевых графиков, содержащее поляризованные реле, шаговый искатель, схему сравнения, блок контроля нуля. (1J.

Вычислительный процесс в таком устройстве имеет аналоговый характер.

Наиболее близким техническим решением к изобретению является ячейка однородной вычислительной структуры, содержащая элементы И и ИЛИ, инверторы, счетчик, триггеры f2) .

МЬдель ветви в известном устройстве для моделирования экстремальных путей на графе моделирует одну ориентированную, взвешенную дугу к графе. Но так как больший класс задзч сетевого анализа, связи, вариационного исчисления и т.д. требует анализа асимметричных неориентированных графов, то при применении подобных устройств каждой дуге графа требуется поставить в соответ-. ствие две модели ветви, моделирующие функциональные веса дуги в двух противоположных направлениях, что приводит к увеличению количества оборудования и количества .коммутационных соединений на наборном поле. А это значит, что увеличиваются габариты вычислительной машины и наборного коммутационного поля, усложняется подготовка и .увеличивается время под10 готовки задачи к решению.

Цель изобретения †упрощение ячейки вычислительной структуры.

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

2О к первому входу третьего элемента И, четвертый и пятый элементы И, первый элемент ИЛИ, первый функциональный преобразователь, первый ключевой элемент, триггер и инверторы, введе25 ны второй и третий счетчики импуль сов, второй функциональный преобразователь, второй ключевой элемент, элемент задержки и элементы ИЛИ, выход второго элемента ИЛИ через элемент

ЗО задержки подключен к первому входу

805300 четвертого элемента И, выход которого соединен с единичным входом триггера, единичный выход которого подключен к первому входу второго элемента И, второй вход которого является тактовым входом ячейки, выход второго элемента И подключен к первому входу второго и входу третьего счетчиков импульсов, выход второго счетчика импульсов соединен с нулевым входом треггера, выход третьего счет- 1О чика импульсов подключен и первому входу пятого элемента И, выходы третьего и пятого элементов Й соединены со входами первого элемента ИЛИ, выход которого подключен к единичному входу запоминающего триггера, нулевой вход которого подключен к шине 1 сброса в нулевое состояние, нулевой выход запоминающего триггера соединен со вторым входом четвертого эле- . мента И и со входами первого и вто- 20 рого инверторов, выходы первого и второго инвертсров через первый и второй функциональные преобразователи подключены ко входам третьего и четвертого инверторов соответственно, выходы которых подключены ко входам третьего элемента ИЛИ и ко вторым входам третьего и пятого элементов И, выход третьего элемента-ИЛИ соединен с третьим входом четвертого эле- 30 мента И и со вторым входом первого элемента И соответственно, выход которого через ключевые элементы подключен ко входу третьего и четвертого инверторов и ко входам второго элемента ИЛИ соответственно.

На чертеже приведена блок-скема ячейки.

Схема содержит запоминающий триггер 1, первый 2, третий 3., второй 4 и .четвертый 5 инверторы, третий эле- 4О мент И 6, первый элемент И 7, пятый элемент Й 8, четвертый элемент И 9, первый элемент ИЛИ 10, второй элемент ИЛИ 11, третий элемент ИЛИ 12, функциональные преобразователи 13 и 14, ключевые элементы 15 и 16, элемент 17 задержки, третий счетчик 18 импульсов, первый 19 и второй 20 счетчики импульсов, второй элемент

И 2"., триггер 22, счетчики 19 и 20, элемент И 21 и триггер 22 образуют управляемый счетчик 23 импульсов.

Функциональные преобразователи

13 и 14 имеют вентильную характеристику и предназначены для разделения входных сигналов, поступающих на коммутационные шины 24 и 25, от выходных сигналов, выдаваемых на эти полюса запоминающим триггером 1. В качестве функциональных преобразователей

13 и 14 могут быть взяты полупровод- 60 никовые диоды, а ключевыми элементами 15 и 16 могут служить транзисторы, подключенные своими коллекторами соответственно к внешним коммутационным шинам 24 и 25. Элементом 17 за- 5 держки может быть простая резисторноемкостная цепь.

В исходном состоянии ячейки однородной вычислительной структуры в счетчике 19 импульсов управляемого счетчика 23 импульсов и счетчике 18 импульсов записаны величины весов в двух направлениях для дуги сети, которую этот элемент моделирует. Запоминающий триггер 1, триггер 22 и счетчик 20 импульсов в управляемом счетчике 23 импульсов установлены в исходное нулевое состояние. На шины

26 и 27 извне подаются потенциалы нулевого логического уровня.

Один из входов элемента И 21 подключен к шине тактового генератора

28. На выходе элемента И 7, входах ключевых элементов 15 и 16 и индикационной шине 29 присутствуют сигналы нулевого логического уровня. Так как запоминающий триггер 1 находится в нулевом состоянии, то на выходах инверторов 2 и 4 присутствует сигнал логического нуля. На внешних коммутационных шинах 24 и 25 тоже будет сигнал логического нулевого уровня.

При подаче запускающего рабочего сигнала единичного логического уровня на коммутационную шину 24 срабатывает элемент ИЛИ 11, и си" íàë логической единицы через элемент 17 задержки поступает на вход элемента И 9. На двух остальных входах элемента И 9 в этот момент присутствуют сигналы логической единицы.

Сигналом того же характера с выхода элемента И 9 устанавливается в единичное состояние триггер 22 управляемого счетчика 23 импульсов. Триггер 22 выдает разрешение на прохождение сигналов тактового генератора через элемент И 21 на входы трех счетчиков 18-20 импульсов одновременно. Выход элемента И 21 является функциональным входом управляемого счетчика 23 импульсов для счетчиков

18-20 импульсов. Счетчик 20 импульсов идентичен счетчикам 19 и 18 импульсов и предназначен для автоматической регенерации записанной в них исходной информации после каждого запуска триггера 22.

Импульсами с выхода элемента И 21 формируются функциональные задержки в обоих задающих счетчиках 18 и 19 импульсов, но на единичный вход запоминающего триггера 1 подается сигнал с выхода только счетчика 18 импульсов, так как инвертор 5 выдает разрешение на вход элемента И 8, а инвертор 3 запрещает срабатывание элемента И 6. После конца формирования функционального веса ветви графа в одном направлении сигналом логической единицы с выхода счетчика

18 импульсов запоминающий триггер 1 устанавливается в единичное состояние, и сигналы логической единицы с

805300 выходов инверторов 2 и 4 через функциональные преобразователи 13 и 14 подаются на обе коммутационные шины

24 и 25, которыми элементы однородной вычислительной структуры соединяются между собой в вычислительную структуру. Сигналы логической единицы, появившиеся на коммутационных шинах 24 и 25, являются запускающими сигналами для других, еще не запущенных элементов однородной вычислительной структуры. Этот режим работы элемента однородной вычислительной структуры соответствует формированию веса дуги в одном направлении.

Аналогичным образом сработает элемент однородной вычислительной структуры, если запускающий сигнал единичного логического уровня придет на коммутационную шину 25. Только в этом случае инвертор 5 запрещает срабатывание элемента И 8, а инвертор 3 выдает разрешающий сигнал на вход элемента И 6, и запоминающий триггер 1 устанавливается в единичное состояние сигналом с выхода счетчика 19 импульсов. Элемент однорс пной вычислительной структуры произведет. форми рование веса дуги в другом направлении. Таким образом, элемент однородной вычислительной структуры является симметричным по отношению к обеим коммутационным шинам 24 и 25 и его запуск производится тем сигналом логической единицы, который придет раньше на любую из этих коммутационных шин 24 и 25.

Согласно специфики поиска экстремальных путей в неориентированных графах, если сигналы логической единицы придут на обе коммутационные шины 24 и 25 одновременно, запуск триггера 22 в управляемом счетчике 23 импульсов не должен произойти, так как в этом случае на выходе элемента ИЛИ 12 будет сигнал логического нуля, который запрещает срабатывание элемента И 9. В том случае, если сигнал логической единицы придет сначала на одну из коммутационных шин

24 или 25, а потом сигнал того же характера поступит и на вторую из коммутационных шин 25 или 24, но соответствующие счетчики 18 или 19 импульсов еще не окончили формирование своих функциональных весов, то установ@д в единичное состояние запоминающего триггера 1 блокируется сигналами логического нуля с выходов инверторов 3 и 4. После переполнения счетчика 20 импульсов на его выходе появляется сигнал логической единицы, кб7ерый сбросит триггер 22 управля.емого счетчика 23 импульсов обратно в нулевое состояние. Таким образом, происходит автоматическое "защелкивание" управляемого счетчика 23 импульсов. При этом автоматически производится восстановление исходной информации, записанной в счетчиках 19 и 18 импульсов, после каждого запус.. ка триггера 22 управляемого счетчика 23 импульсов.

Кроме режима формирования функциональных весов, элемент однородной вычислительной структуры работает также в режиме индикации. Режим индикации производится сигналом нулевого логического уровня всегда после режима формирования функциональных весов. В исходном состоянии элемента однородной вычислительной структуры при режиме индикации на обеих коммутационных шинах 24 и 25 присут 5 ствуют сигналы единичного логического уровня. Эти сигналы подаются на внешние коммутационные шины 24 и 25, которые соединяются в узлы согласно топологии задачи, запоминающими триг20 герами тех элементов однородной вычислительной структуры, которые входят в найденное дереве экстремальных путей. Перед началом режима индикации на шину 26 необходимо пода ь е д5 сигнал единичного логического уровня.

В режиме индикации при подаче сигнала нулевого логического уровня на одну из коммутационных шин 24 или 25 ячейки однородной вычислительной среды, запоминающий триггер 1 которого находится в единичном состоянии, происходит передача этого сигнала логического нуля соответственно на его другие коммутационные шины 25 или 24. При поступлении сигнала логического нуля на коммутационную шину 24 на выходе инвертора 3 появится сигнал логической единицы, который через элемент ИЛИ 12 подается на вход элемента И 7. На остальных

40 входах элемента И 7 в это время при-.сутствуют сигналы логической единицы.

Сигнал логической единицы с выхода элемента И 7 подается на индикационную шину 29 и входы ключевых элементов 15 и 16. Сигнал единичного логического уровня на второй коммутационной шине 25 через открытый ключевой элемент 16 понижается до нулевого логического уровня. Если же сигнал

50 нулевого логического уровня поступит на коммутационную шину 25, то аналогично описанному сработают инвертор

5, элемент ИЛИ 12, элемент И 7 и через ключевой элемент 15 передается сигнал нулевого логического уровня на коммутационную шину 24. Таким образом, ячейка однородной вычислительной структуры обеспечивает передачу в режиме индикации сигнала нулевого логического уровня-с одной коммута60 ционной шины иа другую, если запоминающий триггер 1 этого элемента находится в единичном состоянии. Сигнал логической единицы с индикационной шины 29 может подаваться для ви 5 зуализации на индикационный элемент.

805300

В результате применения ячейки однородной вычислительной структуры уменьшается на 40% общее количество оборудования и стоимость вычислительного устройства, уменьшается в два раза число коммутационных соединений, размер коммутационной панели, что дает сокращение времени подготовки задачи к решению почти в два раза и увеличение на 15t надежности всей вычислительной структуры при меньших ее габаритах.

Формула изобретения

Ячейка однородной вычислительной 15 структуры, содержащая запоминающий триггер, единичный выход которого подключен к первому входу первого элемента И, выход второго элемента И. соединен со входом первого счетчика щ . импульсов, выход которого подключен к первому входу третьего элемента И, четвертый и пятый элементы И, первый элемент ИЛИ, первый функциональный преобразователь, первый ключевой элемент, триггер и инверторы, о т л и ч а ю щ а я с я тем, что, с целью упрощения ячейки вычислительной структуры, она содержит второй и третий счетчики импульсов, второй функциональный преобразователь, вто30 рой ключевой элемент, элемент задержки и элементы ИЛИ, выход второго элемента ИЛИ через элемент задержки подключен к первому входу четвертого элемента И, выход которого соединен с единичным входом триггера, единичный выход которого подключен к первому входу второго элемента И, второй вход которого является тактовым входом ячейки, выход второго элемента И подключен к первому входу второго и входу третьего счетчиков импульсов, выход второго счетчика импульсов подключен к первому входу элемента И, выход второго счетчика импульсов соединен с нулевым входом триггера, выход третьего счетчика импульсов подключен к первому входу пятого элемента И, выходы третьего и пятого элементов И соединены со входами перво"о элемента ИЛИ, выход которого подключен к единичному входу запоминающего триггера, нулевой вход которого подключен к шине сброса в нулевое состояние, нулевой выход запоминающего триггера соединен со вторым входом четвертого элемента И и со входами первого и второго инверторов, выходы первого и второго инверторов через первый и второй функциональные преобразователи подключены ко входам третьего и четвертого инверторов соответственно, выходы которых подключены ко входам третьего элемента ИЛИ и ко вторым входам третьего и пятого элементов И, выход третьего элемента ИЛИ соединен с третьим входом четвертого элемента И и со вторым входом первого элемента И соответственно, выход которого через ключевые элементы подключен ко входу третьего и четвертого инверторов и ко входам второго элемента ИЛИ соответственно.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

Р 220643, кл. G 06 G 7/122, 1967.

2. Авторское свидетельство СССР

9 305484, кл. С 06 G 7/122, 1969. (прототип).

805300

Тираж 756 Подписное

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

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

Заказ 10903/71

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

Составитель И. Дубинина

Редактор С. Пыжова Техред M. Коштура Корректор М. Вигула