Отказоустойчивое устройство для умножения чисел

(54) . ОТКАЗ ОУСТ ДЛЯ УМНОЖЕНИ (57) Изобретение числительной тех зовано при разра УСТРОЙСТВ ОЙЧИВОЕ Я ЧИСЕЛ относится ики и може отке быстр области выбыть исполь- ействующихввввввЪ ввввввй ГОСУДАРСТВЕННОЕ ПАТЕНТНВЕДОМСТВО СССР(ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБ АВТОРСКОМУ СВИДЕТЕЛЬСТВ(71) Научно-исследовательский инстэлектронных вычислительных машин(56) Авторское свидетельство СССРМ 888109, кл. 6 06 Г 7/52, 1978.Авторское свидетельство СССРМ 1702362, кл. 6 06 Г 7/52, 1990. Изобретение относится к области вычислительной техники и может быть использовано при разработке быстродействующих устройств умножения чисел повышенной надежности, удобных для изготовления с применением технологии БИС и СБИС,Известно устройство умножения чисел, содержащее и операционных блоков (и - разрядность множимого), каждый из которых включает одноразрядный регистр множимого, узел вычисления разрядных значений произведения и два буФерных регистра с соответствующими связями.Данное устройство удобно для изготовления с применением БИС и СБИС, отличается достаточно высоким быстродействием. Недостатком его является низкая надежность.Наиболее близким по технической сущности к изобретению является отказоустой 1777134 А 1 устройств для умножения чисел повышен"ной надежности, удобных для изготовления с применением технологии БИС и СБИС. Целью изобретения является сокращение аппаратурных затрат, Отказоустойчивое устройство для умножения содержит и основныхх операционных блоков, п 1 резервных операционных блоков, первую и вторую группы по (и+а) коммутаторов, коммутатор множимого и блок управления, В устройстве организован принцип обходного пути потока информации через неисправные и неиспользованные операционные блоки, что дает возможность сократить аппаратурные затраты на реализацию средств управления реконфигурацией и коммутацию. 4 ил,чивое устройство умножения чисел, содержащее и основных операционных блоков (и - разрядность множимого), щ резервных операционных блоков и = 1, 2, 3, .), первую и вторую группы по (п+в) коммутаторов, в коммутаторов мнокимого, щ регистров замены, и элементов ИЛИ и блок управления, причем вход множителя устройства соединен с входами множителя основных и резервных операционных блоков, вход слагаемого )-го основного операционного блока О - 1, , и) соединен с первым выходом )-го коммутатора первой группы, вход множимого- с входом множимого устройства и информационным входом к-го коммутатора множимого (М = 1, , (и), выход которого соединен с входом множимого М-го резервного операционного блока, вход слагаемого которого соединен с выходом (и+К)-го коммутатора первой группы, )-й информацион 3 1777134ный вход которого соединен с вторым выходом -го коммутатора первой группы, выход результата -го основного операционного блока соединен с первым информационным входом )-го коммутатора второй группы, второй информационный вход которого соединен с выходом )-го элемента ИЛИ, 1-й вход которого соединен с -м выходом (и+Ц- го коммутатора второй группы, информационный вход которого соединен с выходом результата К-го резервного операционного блока, информационный вход -го коммутатора первой группы ( = 1, , и) соединен с выходом (+1)-го коммутатора второй группы, управляющие входы )-х коммутаторов первой и второй групп обьединены между собой и соединены с выходом отказа -го основного блока блока управления и первыми входами в регистров замены. первый выход 1-го регистра замены соединен с управляющими входами М-го коммутатора множимого и (и+Ц-х коммутаторов первой и второй групп, второй выход М-го регистра замены соединен с вторым входом (1+1)-го регистра замены, второй выход щ-го регистра замены соединен с выходом структуры устройства, вход запрета которого соединен с вторым входом первого регистра замены, выход первого коммутатора второй группы соединен с выходом результата устройства, вход коррекции которого соединен с информационным входом и-го коммутатора первой группы, третий и четвертый входы а регистров замены соединены соответственно с вторым выходом блока управления, первым входом блока управления и первым входом контроля устройства, второй вход контроля которого соединен с вторым входом блока управления, третий и четвертый выходы которого соединены соответственно с выходами отказа и прерывания устройства.Известное устройство имеет более высокую надежность, поскольку продолжает функционирование после отказов операционных блоков. Недостатком известного устройства являются большие аппаратурные затраты на реализацию средств управления и коммутации.Целью изобретения является сокращение аппаратурных затрат,Поставленная цель достигается тем, что а отказоустойчивом устройстве для умножения чисел, содержащем и основных операционных блоков (и - разрядность множимого), гп резервных операционных блоков (гп 1, 2, 3, ), первую и вторую группы по (и+а) коммутаторов, коммутатор множимого и блок управления, причем вход множителя устройства соединен с входами множителя основных и резервных операционных блоков, входы множимого гп резервных операционных блоков соединены с соответствующими щ выходами коммутато ра множимого, информационный вход которого соединен с входам множимого устройства, первый и второй входы контроля которого соединены соответственно с первым и вторым входами блока управле ния, выходы отказа и прерывания которогосоединены соответственно с выходами отказа и прерывания устройства, выход результата которого соединен с выходом первого коммутатора второй группы, пер вые выходы (и+в) коммутаторов первойгруппы соединены с входами слагаемых со ответствующих и основных и гп резервныхоперационных блоков, выходы результата которых соединены с первыми информаци онными входами соответствующих (и+в)коммутаторов второй группы, информационный вход -го ( = 1 п) коммутатора первой группы соединен с выходом (+1)-го коммутатора второй группы, управляющие 25 входы )-х коммутаторов первой и второйгрупп ( - 1, ., и) обьединены между собой и соединены с выходом отказа)-го основного блока блока управления, в нем входы множимого и основных операционных бло ков соединены с соответствующими и входами коммутатора множимого, информационные входы коммутаторов с иго по(п+а)-й первой группы соединены с выходами коммутаторов с(п+1)-го по(п+е).й 35 второй группы соответственно, информаци. онный вход (и+в)-го коммутатора первойгруппы соединен с входом коррекции устройства, вторые входы коммутаторов первой группы соединены с вторыми 40 информационными входами соответствующих коммутаторов второй группы, управляющие входы 1-х коммутаторов первой и второй групп (1 - и+1, , е) обьединены между собой и соединены с выходом запре та блока управления и первым управляющим входом коммутатора множимого, второй управляющий вход которого соединен с выходом отказа -го основного блока блока управления.50 Отказоустойчивое устройство умноже- .ния чисел содержит отличительные признаки, не обнаруженные ни в одном из известных аналогичных устройств - а нем вторые выходы коммутаторов первой груп пы соединены с вторыми информационными входами соответствующих коммутаторов второй группы, а входы слагаемого и основных операционных блоков соединены с соответствующими выходами коммугатора множимого, Это позволяет обеспечить ра 1777134ботоспособность устройства с использованием и основных и резервных операционных блоков; организуя "обходной путь" потока информации через неисправные и неиспользуемые операционные блоки, сократив, таким образом, аппаратурные затраты на реализацию средств управления реконфигурацией и коммутацию.На фиг,1 приведена структурная схема предлагаемого устройства; на фиг,2 - структурная схема операционного блока; на фиг.З - функциональная схема коммутатора множимого для случая и =4, в = 2; на фиг.4 - функциональная схема блока управления подключением резерва.Устройство для умножения чисел (фиг.1) содержит и основных операционных блоков 1 (и - число разрядов множимого) в резервных операционных блоков 2 (в = 1, 2, 3), (и+в) коммутаторов 3 первой группы, (и+в) коммутаторов 4 второй группы, коммутатор 5 множимого, блок 6 управления, входы 7 и 8 множителя и множимого устройства соответственно, вход 9 коррекции устройства, первый 10 и второй 11 входы контроля устройства, выходы 12 - 14 результата, прерывания и отказа устройства соответственно. Вход множителя )-го 3 = 1 п) блока 1 соединен с входом множителя 1-го (1 = 1, , в) блока 2 и входом 7 множителя устройства, вход множимого )-го блока 1 - с )-м выходом 15 коммутатора 5, вход 16 слагаемого - с первым выходом )-го коммутатора 3, выход 17 результата )-го блока 1 соединен с вторым информационным входом )-го коммутатора 4, вход множимого М-го блока 2 соединен с (и+1)-м выходом 15 коммутатора 5, вход 18 слагаемого К-го блока 2- с первым выходом (и+К)-го коммутатора 3, выход 19 результата К-го блока 2 соединен с вторым информационным входом (и+К)-го коммутатора 4, второй выход 20 -го ( = 1 п+в) коммутатора 3 соединен с первым информационным входом -го коммутатора 4, выход 21 -го коммутатора 4 соединен с информационным входом ( - 1)-го коммутатора 3, выход 21 первого коммутатора 4 соединен с выходом 12 результата устройства, вход 8 коррекции которого соединен с информационным входом (и+в)-го коммутатора 3, управляющие входы )-х коммутаторов 3 и 4 обьединены и соединены с вторым управляющим входом коммутатора 5 и выходом 22 блока 6, выход 23 которого соединен с первым управляющим входом коммутатора 5 и суправляющими входами(п+Ц-х коммутаторов 3 и 4, первый и второй входы блока 6 соединены с первым 10 и вторым 11 входами контроля устройства соответственно, выход прерывания блока 6 соединен с выхо 15 щие разряды сомножителей, поступающих ЗО 35 40 Он может быть реализован на элементах 2 ИИЛИ.Коммутатор 5 множимого предназначендля передачи разрядов множимого со свое го информационного входа (входа 8 устрой;ства) в определенном порядке на свои выходы 15 в соответствии с управляющими сигналами. Порядок коммутации следующий: под действием управляющих сигналов 510 20 25 45 50 дом 13 прерывания устройства, выход 14 отказа которого соединен с выходом отказа блока 6, вход 8 множимого устройства соединен с информационным входом коммутатора 5 множимого,Рассмотрим функциональное назначение и реализацию узлов и блоков устройства,Операционные блоки 1(2) предназначены для вычисления разрядных значений произведения и формируют на своих выходах 17(19) результата значения (ХУ + А+ В) мл, где мл означает младший разряд двух- разрядного результата; ХУ - соответствуюна входы множителя и множимого блоков 1(2);А - одноразрядное слагаемое, поступающее на вход 16(18) слагаемого блоков 1(2);В - внутреннее одноразрядное слагаемое, хранимое в одном из буферных регистров блоков 1(2).Реализация блоков 1(2) показана на фиг,2. В этом случае каждый блок 1(2) содержит узел 24 вычисления разрядных значений произведения, буферные регистры 25 и 26 и регистр множимого 27. В регистре 27 хранится соответствующий разряд множимого, Узел 24 формирует двухразрядные значения функции Р=ХУ+А+ В,старшие и младшие разряды которых записываются соответственно в регистры 25 и 26. Реализация узла 24 зависит от требований к регулярности структуры и к быстродействию и может быть осуществлена известным образом. Регистры 25 - 27 могут быть реализованы на синхронных двухтактных О-триггерах, причем регистры 25 и 26 имеют входы установки в нулевое состояние,Коммутатор 3 предназначен для выдачи информации со своего входа на первый или второй свои выходы в зависимости от управляющих сигналов. Он может быть реализован на элементах 2 И,Коммутатор 4 предназначен для передачи информации на свой выход с первого или второго своих информационных входов в зависимости от управляющих сигналов.блоков - рабочий/отказавший) осуществляется сдвиг влево разрядов множимого, начиная с позиции соответствующей отказавшему операционному блоку. Например, для коммутатора 5, показанного на фиг.З, при отказе второго операционного блока 1, сигналом "1" во втором разряде на первом управляющем входе коммутатора 5(выходе 22 блока 6) разрешается прохождение информации через группы элементов И 29 и ИЛИ 34 таким образом,.что разряды множимого с второго по п-й передаются на выходы 25 коммутатора 5 с третьего по(п+1)- й. Коммутатор 5 может быть реализован различными методами, например, как это ,показано на фиг.З. В этом случае для коммутации 4-разрядного множимого с информационного входа коммутатора 5 на шесть его выходов 15(для использования вустройстве . с четырьмя основными и двумя резервными операционными блоками) коммутатор 5 со-, держит 28 двухвходовых элементов И 28- 32, 9 двухвходовых элементов ИЛИ 33-36 и один четырехвходовый элемент ИЛИ 37.Блок 6 управления подключением резерва предназначен для выдачи управляющих сигналов на прерывание работы устройства при отказах основных и резервных блоков 1(2), на отключение отказавшихблоков 1(2) и подключение в работу резервных блоков 2, на перекоммутацию разрядов множимого между рабочими блоками 1(2), а также для выдачи сигнала об отказе устройства после в+1 отказов блоков 1(2). Одна из возможных реализаций блока 6 показана на фиг.4. Блок 6 содержит и ВЗ-триггеров 38 первой группы, а ЯЯ-триггеров 39 второй группы, элемент ИЛИ 40, счетчик 41 и дешифратор 42, В триггерах 38 и 39 хранится информация о состоянии соответственно основных и резервных блоков 1(2). Одновременно с.записью в триггеры 38 и 39 сигналы об отказах блоков 1(2) через элемент ИЛИ 40 поступают на счетный вход счетчика 41, устанавливая его в очередное состояние, и на выход прерывания блока 6 (выход 13 устройства), вызывая прерывание работы устройства, Дешифратор 42 определяеточередной резервный блок 2, который должен включиться в работу, и устанавливает соответствующий триггер 39 в нулевое состояние. После (а+1) отказов блоков 1(2) на (а+1)-м выходе дешифратора 42 формируется сигнал, поступающий на выход 14 отказа устройства.На структурных и функциональной схемах с целью упрощения условно не показаны цепи установки в нулевое состояниерегистров 25 и 26 блоков 1, 2, триггеров 38 и счетчика 41 блока 6, цепь установки триг геров 39 в исходное единичное состояние, а также цепи синхронизации регистров 25 - 27 блоков 1, 2, однако можно отметить, что имеется общая цепь синхронизации регистров 25 и 26 блоков 1, 2, цепь установки в нулевое состояние регистров 25 и 26 соединена с цепью синхронизации регистров 27 блоков 1, 2, а также имеется общая цепь установки в исходное состояние триггеров 38 и 39 и счетчика 41 блока 6(включает цепь 5 10 установки в нулевое состояние триггеров 38 и счетчика 41 и цепь установки в единичное состояние триггеров 39).Устройство работает следующим обра зом.8 исходном состоянии регистры 25 и 26блоков 1(2), триггеры 38 и счетчик 41 блока 6 обнулены, триггеры 39 блока 6 установлены в "1", коммутаторы 3 и 4 под управлением 20 нулевого кода на выходе 22 блока 6 и единичного кода на выходе 23 блока 6 настроенына организацию связей между блоками 1 и исключение иэ работы блоков 2 (органиэацию обходного пути), коммутатор 5 под дей ствием этих же управляющих сигналовнастроен на передачу разрядов множимого с входа 8 устройства на первые свои и выходов 15, в регистре 27)-го О = 1, , и) блока 1 хранится )-й разряд множимого.30 Устройство работает в двух режимах;рабочем и реконфигурации.В рабочем режиме в устройстве производится умножение и-разрядных сомножителей в течение 2 п тактов с использованием 35 и операционных блоков 1(2). Пусть все блоки1 исправны. В каждом иэ и первых тактов работы устройства на его вход 7 поступает по одному разряду, начиная с младших, множитель, При этом в )-м Ц - 1, , и) блоке 40 1 производится умножение разряда множителя, поступающего на его вход множителя с входа 7 устройства, на )-й разряд множимого, хранимый в регистре 27)-го блока 1, и прибавление к младшему разряду получив;45 шегося при этом двухразрядного произведения младшего разряда произведения 0+1)-го блока 1, сформированного в предыдущем такте и поступающего на вход 16 слагаемого -го блока 1 с первого выхода 1-го 50 коммутатора 3, а также старшего разрядапроизведения )-го блока 1, сформированного в предыдущем такте и хранимого в его регистре 25, Сформированные к концу такта старший и младший разряды произведения 55 )-го блока 1 записываются в его регистры 25и 26 соответственно.После выполнения и первых тактов работы. устройства на его вход 7 поступает нулевая информация и далее осуществляется еще дополнительно и тактов, в течениекоторых из устройства выводится с соответствующим преобразованием информация, хранимая в регистрах 25 и 26 блоков 1. Следует отметить, что вывод 2 п-разрядного произведения сомножителей в устройстве осуществляется через его выход 12 по одному разряду в каждом такте. В рассмотренном случае на вход 9 коррекции устройства во всех его тактах работы подается нулевая информация. В тех же случаях, когда требуется получить округленное значение произведения, необходимо в первом такте работы устройства на его вход 9 подать определенную информацию (например, для округления 2 п-разрядного произведения сомножителей, представленных в двоичнокодированной шестнадцатиричной системе счисления, необходимо на вход 9 в первом такте подать двоичный код 1000). Это позволяет осуществить округление результата без дополнительных временных затрат. Вход 9 может быть использован также для введения результирующей коррекции по знакам множимого и множителя в случае умножения чисел в дополнительном коде,В процессе функционирования блоки 1(2) могут отказывать. Будем предполагать, что каждый операционный блок 1(2) имеет средства обнаружения отказа в виде средств встроенного контроля, которые могут быть организованы любыми известными способами, например дублированием или контролем по модулю, Информация о состоянии блоков 1(2) поступает на входы 10 и 11 устройства в моменты опроса средств контроля блоков 1(2), периодичность которого определяется различными требованиями к работе устройства, Ввиду малой вероятности одновременного отказа двух и более блоков 1(2) эта ситуация не рассматривается. Средства контроля блоков 2, находящихся в "горячем" (нагруженном) или "холодном" (ненагруженном) состоянии, опрашиваются при условии включения соответствующего блока 2 в процесс вычисления произведения сомножителей, причем вероятность отказа резервных блоков 2 в случае "холодного" резервирования значительно ниже,Рассмотрим работу устройства. в режиме реконфигурации.Пусть работа устройства обеспечивается и основными блоками 1, а все блоки 2 находятся в резерве. При отказе )-го блока 1 через вход 10 устройства сигнал об этом. поступает на первый вход блока 6, где устанавливает )-й триггер 38 в "1", и через элемент ИЛИ 40 и выход прерывания блока 6 поступает на выход 13 устройства, вызывая прерывание его работы, Кроме того, по сиг налу отказа счетчик 41 устанавливается в состояние "1" и на первом выходе дешифратора 42 формируется сигнал, устанавливающий первый триггер 39 в "0" (в исходное состояние все триггеры 39 установлены в"1"), который через выход 23 блока 6 поступает на управляющие входы (и+1)-х коммутаторов 3 и 4, в результате чего вход 18 слагаемого первого блока 2 подключается к 10 входу 9 коррекции устройства, а выход 19 первого блока 2 соединяется с входом 16 слагаемого и-го блока 1. Сигнал "1" с выхода )-го триггера 38 блока 6 через его выход 22 поступает на управляющие входы )-х коммутаторов 3 и 4, которые исключают иэ работы 15 Я+1)-й выход 15 коммутатора 5, +1)-й разряд множимого - на 0+2)-й выход и т.д., т.е. осуществляется сдв 1 г влево разрядов множимого, начиная с )-го разряда. Таким образом, первый блок 2 включается в работу25 и устанавливается новая конфигурация устройства. По окончании режима реконфигурации на вход 8 устройства подается множимое, разряды которого через комму татор 5 записываются в регистры 27 блоков 1 и первого блока 2 следующим образом; первые О - 1) разрядов множимого - в соответствующие блоки 1, с )-го по (и)-й разряды множимого - в блоки 1 с 0+1)-го по п-й, э и-й разряд множимого - в первый блок 2. 35 Одновременно с этим обнуляются регистры 25 и 26 блоков 1 и 2, Далее устройство вновь переходит в рабочий режим и начинает выполнять умножение с первого такта (кэк это 40 было описано выше). При отказе во время работы устройства еще одного блока 1 выполняются аналогичные действия по прерыванию работы устройства; установке в "1" соответствующего триггера 38 блока 6, исключению из работы отказавшего блока 1, сдвигу влево в коммутаторе 5 разрядов множимого, начиная с разряда, соответствующего отказавшему блоку 1, переключению счетчика 41 с дешифратором 42 во второе положение и установке в "0" второго триггера 39, в результате чего второй резервный блок 2включается в работу.Если же произойдет отказ в блоке 2, 55 включенном в работу вместо отказавшегоранее блока 1, то в устройстве осуществляется следующая последовательность действий. По сигналу на входе 11 устройства через элемент ИЛИ 40 блока 6 выдается сигнал на прерывание нормальной работы и)-й блок 1 (организуется обход), кроме того, этим же сигналом в коммутаторе.5 осуществляется коммутация выходной информации таким образом, что )-й разряд.множимого с 20 входа 8 устройства поступает напереход устройства в режим реконфигурации. Этим же сигналом соответствующий триггер 39 устанавливается в "1" и производится исключение из работы отказавшего блока 2. Счетчик 41 переключается в очередное состояние, и по сигналу с соответствующего выхода дешифратора 42 устанавливается в "О" очередной триггер 39, в результате чего в рабочую конфигурацию включается следующий резервный блок 2, В коммутаторе 5 сигналом об отказе блока 2 осуществляется перекоммутация выходов разрядов множимого путем сдвига влево информации, начиная с соответствующего отказавшему блоку 2 выхода 15 коммутатора 5,После регистрации счетчиком 41 и дешифратором 42 блока 6 (в+1)-го отказа блоков 1(2) на выход 14 устройства выдается сигнал об его отказе, указывающий на возможность дальнейшей реконфигурации и правильной работы устройства.Таким образом, устройство за счет скользящего резервирования запасными операционными блоками сохраняет работоспособность до (а+1)-го отказа в операционных блоках.Устройство состоит иэ одинаковых узлов и блоков, что делает его перспективным при разработке современных наращиваемых средств на БИС и СБИС.Технико-экономические преимущества отказоустойчивого устройства умножения чисел заключаются в сокращении аппаратурных затрат на реализацию средств управления реконфигурацией и коммутации (в предположении, что устройство обрабатывает 32-разрядные числа, представленные в 28 256-ричной системе счисления, и при использовании двух резервных блоков, на реализацию средств управления и коммутации затрачивается примерно в 1,6 раз меньше аппаратуры).Формула изобретения Отказоустойчивое устройство для умножения чисел, содержащее и основных операционных блоков (и - разрядность множимого). в резервных операционных блоков(гп -1,2,), первую и вторую группы по (и+а) коммутаторов. коммутатор множимого и блок управления, причем вход мно 10 20 жителя устройства соединен с входом множителя основных и резервных операционных блоков, входы множимого в резервных операционных блоков соединены с соответствующими гп выходами коммутатора множимого, информационный вход которогосоединен с входом множимого устройства,первый и второй входы контроля которого соединены соответственно с первым и вторым входами блока управления, выходы отказа и прерывания которого соединены соответственно с выходами отказа и прерывания устройства, выход результата которого соединен с выходом первого коммутатора второй группы, первые выходы (и+а) коммутаторов первой группы соединены с входами слагаемых соответствующих и основных и в резервных операционных блоков, выходы результата которых соединены с первыми информационными входами соответствующих (и+в) коммутатороввторой группы, информационный вход 1-го коммутатора первой группы ( - 1 п) соединен с выходом (1+1)-го коммутатора второй группы. управляющие входы )-х коммутаторов первой и второй групп О = 1, ., и) объединены между собой и соединены с выходом отказа )-го основного блока управления, отл ича ющеес я тем,что,с целью сокращения аппаратурных затрат, входы множимого и основных операционных блоков соединены с соответствующими и выходами коммутатора множимого,информационные входы коммутаторов с иго по (п+а)-й первой группы соединены с выходами коммутаторов с (и+1)-го по(о+в)-й второй группы соответственно, информационный вход (и+в)-го коммутатора первой группы соединен с входом коррекции уст 40 ройства, вторые выходы коммутаторов первой группы соединены с вторыми информационными входами соответствующих коммутаторов второй группы, управляющие входы т-х коммутаторов, первой и45 второй групп (т - и+1 гп) объединены между собой и соединены с выходом запрета блока управления и первым управляющим входом коммутатора множимого, второй управляющий вход которого соеди 50 нен с выходом отказа )-го основного блока управления, 17773341 ТТ 7134 Составитель А.ШостакТехред М.Моргентал рректор М.Керецман Иванова еда каз 4122 Тираж Подписное ВНИИПИ ГосУдарственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раувская наб., 4/5 роизводственно-издательский комбинаг "Патент", г, Ужгор Гагарина, 10