i
Изобретение относится к электронному моделированию и может быть применено для построения специализированных вычислительных машин, решающих Задачи на графах.
Известно устройство для.расчета и оптимизации сетевых графиков, содержащее поляризованные реле, шаговы искатель, схему сравнения, блок контроля нуля i .
Вычислительный процесс в таком устройстве имеет аналоговый характер
Наиболее близким техническим решением к изобретению является ячейка однородной вычислительной структуры, содержащая элементы И и ИЛИ, инверторы, счетчик, триггеры 2 .
Модель ветви в известном устройстве для моделирования экстремальных путей на графе моделирует одну ориентированную, взвешенную дугу к графе. Но так как больший класс задяч сетевого анализа, связи, вй,риационного исчисления и т.д. требует анализа асимметричных неориентированных графов, то при применении подобных устройств каждой дуге графа требуется поставить в соответствие две модели ветви, моделирующие функциональные веса дуги в двух про2
тивоположных направлениях, что приводит к увеличению количества оборудования и количества -коммутационных соединений на наборном поле. А это значит, что увеличиваются габариты вычислительной машины и наборного коммутационного поля, усложняется подготовка и .увеличивается время подготовки задачи к решению.
0
Цель изобретения - упрощение ячейки вычислительной структуры.
Указанная цель достигается тем, что в ячейку однороднсзй вычислительной структуры, содержащую запоминающий триггер, единичный выход которого подключен к первому входу первого элемента И, выход второго элемента И соединен со входом первого счетчика импульсов, выход которого подключен
0 к первому входу третьего элемента И, четвертый и пятый элементы И, первый элемент ИЛИ, первый функциональный преобразователь, первый ключевой элемент, триггер и инверторы, введе5ны второй и третий счетчики импульсов, второй функциональный преобразователь, второй ключевой элемент, элемент задержки и элементы ИЛИ, выход второго элемента ИЛИ через элемент
0 задержки подключен к первому входу четвертого элемента И, выход которого соединен с единичным входом триггера, единичный выход которого подключен к первому входу второго элемента И, второй вход которого являет ся тактовым входом ячейки, выход второго элемента И подключен к первому входу второго и входу третьего счетчиков импульсов, выход второго счетчика импульсов соединен с нулевым входом треггера, выход третьего счет чика импульсов подключен х первому входу пятого элемента И, выходы трет его и пятого элементов И соединены со входами первого элемента ИЛИ, выход которого подклю.чен к единичному .входу за:поминакяцего триггера, нулевой вход которого подключен к шине сброса в нулевое состояние, нулевой выход запоминающего триггера соединен со вторым входом четвертого элемента И и со входами первого и второго инверторов, выходы первого и второго инвертеров через первый и второй функциональные преобразователи подключены ко входам третьего и четвертого инверторов соответственно, выходы которых подключены ко вхо дам третьего элемента ИЛИ и ко вторы входам третьего и пятого элементов И выход третьего элемента-ИЛИ соединен с третьим входом четвертого элемента И и со вторым входом первого элемента И соответственно, выход которого через ключевые элементы подключен ко входу третьего и четвертого инверторов и ко входам второго элемента ИЛИ соответственно. На чертеже приведена блок-схема ячейки. Схема содержит запоминающий триггер 1, первый 2, третий 3., второй 4 и .четвертый 5 инверторы, третий элемент И б, первый элемент И 7, пятый элемент И 8, четвертый элемент И 9, первый элемент ИЛИ 10, второй элемент ИЛИ 11, третий элемент ИЛИ 12, функциональные преобразователи 13 и 14, ключевые элементы 15 и 16, эле мент 17 задержки, третий счетчик 18 импульсов, первый 19 и второй 20 счетчики импульсов, второй элемент .И 21, триггер 22, счетчики 19 и 20, элемент и 21 и триггер 22 образуют управляемый счетчик 23 импульсов. Функциональные- преобразователи 13 и 14 имеют вентильную характеристику и предназначены для разделения входных сигналов, поступающих на ком мутационные шины 24 и 25, от выходны сигналов, выдаваелййх на эти полюса запоминающим триггером 1. В качестве функциональных преобразователей 13 и 14 могут быть взяты полупроводниковые диоды, а ключевьми элементами 15 и 16 могут служить транзисторы, подключенные своими коллекторами соответственно к внешним коммутацион ным шинам 24 и 25. Элементом 17 задержки может быть простая резисторноемкостная цепь. В исходном состоянии ячейки однородной вычислительной структуры в счетчике 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 выдает разрешение на вход элемента ИЗ, а инвертор 3 запрещает срабатывание элемента И 6. После конца формирования функционального веса ветви графа в одном направлении сигналом логической единицы с выхода счетчика 18 импульсов запоминающий триггер 1 устанавливается в единичное состояние, и сигналы логической единицы с
выходов инверторов 2 и 4 через функциональные преобразователи 13 и 14 подаются на обе коммутационные шины 24 и 25, которыми элементы однородной вычислительной структуры соединяются между собой в вычислительную структуру. Сигналы логической единицы, появившиеся на коммутационных шинах 24 и 25, являются запускающими сигналами для других, еще не запущенных элементов однородной вычислительной структуры. Этот режим работы элемента однородной вычислительной структуры соответствует формированию веса дуги в одном направлении.
Аналогичным образом сработает элемент однородной вычислительной структуры, если запускающий сигнал единичного логического уровня придет на коммутационную шину 25. Только в, этом случае инвертор 5 запрещает срабатывание элемента И 8, а инвертор 3 выдает разрешающий сигнал на вход элемента И б, и запоминающий триггер 1 устанавливается в единичное состояние сигналомс выхода счетчика 19 импульсов. Элемент однорс ной вычислительной структуры произведет,формирование веса дуги в другом направлении. Таким образом, элемент однородной вычислительной структуры является симметричным по отношению к обеим коммутационным шинам 24 и 25 и его запуск производится тем сигналом логической- единицы, который придет раньше на любую из этих коммутационных шин 24 и 25.
Согласно специфики поиска экстремальных путей в неориентированных графах, если сигналы логической единицы придут на обе коммутационные шины 24 и 25 одновременно, запуск триггера 22 в управляемом счетчике 23 импульсов не должен произойти, так как в этом случае на выходе элемента ИЛИ 12 будет сигнал логического нуля, который запрещает срабатывание элемента И 9. В том случае, если сигнал логической единицы придет сначала на одну из коммутационных шин 24 или 25, а потом сигнал того же характера поступит и на вторую из коммутационных шин 25 или 24, но соответствующие счетчики 18 или 19 импульсов еще не окончили формирование своих функциональных весов, то устанооща в единичное состояние запоминаклцего триггера 1 блокируется сигналами логического нуля с выходов инверторов 3 и 4. После переполнения счетчика 20 импульсов на его выходе появляется сигнал логической единицы который сбросит триггер 22 управля.емого счетчика 23 импульсов обратно в нулевое состояние. Таким образом, происходит автоматическое защелкивание управляемого счетчика 23 импульсов. При этом автоматически производится восстановление исходной информации, записанной в счетчиках 19 и 18 импульсов, после каждого запуска триггера 22 управляемого счетчика 23 импульсов.
Кроме режима формирования функционсшьных весов, элемент однородной вычислительной структуры работает также в режиме индикации. Режим индикации производится сигналом нулевого логического уровня всегда после
0 режима формирования функциональных весов. В исходном состоянии элемента Однородной вычислительной структуры при режиме индикации на обеих коммутационных шинах 24 и 25 присут5ствуют сигналы единичного логического уровня. Эти сигналы подаются на внешние коммутационнтле шины 24 и 25, которые соединяются в узлы согласно топологии задачи, запоминающими триг0герами тех элементов однородной вычислительной структуры, которые входят Б найденное дерево экстремальных путей. Перед началом режима индикации на шину 26 необходимо подать сигнал единичного логического уровня.
5
В режиме индикации при подаче сигнала нулевого логического уровня на одну из коммутационных шин 24 или 25 ячейки однородной вычислительной среды, запоминающий триггер 1
0 которого находится в единичном состоянии, происходит передача этого сигнала логического нуля соответственно на его другие коммутационные шины 25 или 24. При поступлении сиг5нала логического нуля на коммутационную шину 24 на выходе инвертора 3 появится сигнал логической единицы, который через элемент ИЛИ 12 подается на вход элемента И 7. На остальных
0 входах элемента И 7 в это время при-.сутствуют сигналы логической единицы. Сигнал логической единицы с выхода элемента И 7 подается на индикационную шину 29 и входы ключевых элементов 15 и 16. Сигнал единичного логи5ческого уровня на второй коммутационной шине 25 через открытый ключевой элемент 16 понижается до нулевого логического уровня. Если же сигнал нулевого логического уровня поступит
0 на коммутационную шину 25, то аналогично описанному сработают инвертор 5, элемент.ИЛИ 12, элемент И 7 и через ключевой элемент 15 передается сигнал нулевого логического уровня
5 на коммутационную шину 24. Таким образом, ячейка однородной вычислительной структуры обеспечивает передачу в режиме инднка.ции сигнала нулевого логического уровня- с одной коммута0ционной шины на другую, если запоминающий триггер 1 этого элемента находится в единичном состоянии. Сигнал логической единицы с индикационной шины 29 может подаваться для видуалиэации на индикационный элемент.
5 В результате применения ячейки однородной вьочислительной структуры уменьшается на 40% о.бщее копичество оборудования и ртоимость вычислитель ного устройства, уменьшается в два раза число коммутационных соединений размер коммутационной панели, что да ет сокращение времени подготовки задачи к решению почти в два раза и увеличение на 15% надежности всей вы числительной структуры при меньших е габаритах. формула изобретения Ячейка однородной вычислительной структуры, содержащая запоминающий триггер, единичный выход которого подключен к первому входу первого элемента И, выход второго элемента И соеди ен со входом первого счетчика импульсов, выход которого подключен к первому входу третьего элемента И четвертый и.пятый элементы И, первый элемент ИЛИ, первый функциональный преобразователь, первыйключевой элемент, триггер и инверторы, отличающаяся тем, что, с целью упрощения ячейки вычислительной структуры, она содержит второй и третий счетчики импульсов, второй функциональный преобразователь, вто рой ключевой элемент, элемент задерж ки и элементы ИЛИ, выход второго эле мента ИЛИ через элемент задержки под ключен к первому входу четвертого элемента И, выход которого соединен с единичным входом триггера, единичный выход которого подключен к первому входу второго элемента И, второ вход которого является тактовым входом ячейки, выход второго элемента И подключен к первому входу второго и входу третьего счетчиков импульсов, выход второго счетчика импульсов подключен к первому входу элемента И, выход второго счетчика импульсов соединен с нулевым входом триггера, выход третьего счетчика импульсов подключен к первому входу пятого элемента И, выходы третьего и пятого элементов И соединены со входами первого элемента ИЛИ, выход-которого подключен к единичному входу запоминающего триггера, нулевой вход которого подключен к шине сброса в нулевое состояние, нулевой выход запоминающего триггера соединен со вторым входом четвертого элемента И и со входами первого и второго инверторов, выходы первого и второго инверторов через первый и второй функциональные преобразователи подключены ко входам третьего и четвертого инверторов соответственно, выходы которых подключены ко входам третьего элемента ИЛИ и ко вторым входам третьего и пятого элементов И, выход третьего элемента ИЛИ соединен с тре-тьим входом четвертого элемента И и со вторым входом первого элемента И соответственно, выход которого через ключевые элементы подключен ко входу третьего и четвертого инверторов и ко входам второго элемента ИЛИ соответственно. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 220643, кл. G 06 G 7/122, 1967. 2.Авторское свидетельство СССР № 305484, кл. G 06 G 7/122, 1969. (прототип).
гL.Jriil
Цг
Т-0
