отказоустойчивое устройство для умножения
Классы МПК: | G06F7/52 для умножения; для деления G06F11/00 Обнаружение ошибок, исправление ошибок; контроль |
Автор(ы): | Шостак А.А., Яскевич В.В. |
Патентообладатель(и): | Научно-исследовательский институт электронных вычислительных машин |
Приоритеты: |
подача заявки:
1991-07-03 публикация патента:
15.10.1994 |
Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств умножения чисел повышенной надежности, удобных для изготовления с применением технологии БИС и СБИС. Целью изобретения является повышение надежности устройства за счет продолжения работы на меньшем количестве основных операционных блоков с соответствующим снижением быстродействия устройства. Устройство содержит регистр множимого, n операционных блоков (n - разрядность множимого), по n коммутаторов первой и второй групп, коммутатор множимого, блок управления реконфигурацией и нововведенные коммутатор сдвига, два сдвигателя и коммутатор. 8 ил.
Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8
Формула изобретения
ОТКАЗОУСТОЙЧИВОЕ УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ, содержащее n операционных блоков (n - разрядность множимого), две группы по n коммутаторов в каждой, коммутатор множимого и блок управления реконфигурацией, причем вход множителя i-го операционного блока (i = 1, ... , n) соединен с входом множителя устройства, вход множимого которого соединен с первым информационным входом коммутатора множимого, управляющие входы коммутаторов первой и второй групп соединены с первым выходом блока управления реконфигурацией, второй и третий выходы которого соединены соответственно с выходами отказа и прерывания устройства, вход контроля и первый управляющий вход которого соединены соответственно с входом контроля и управляющим входом блока управления реконфигурацией, вход слагаемого i-го операционного блока соединен с первым выходом i-го коммутатора второй группы, выход результата i-го операционного блока соединен с первым информационным входом i-го коммутатора первой группы, выход которого, кроме выхода первого коммутатора, соединен с информационным входом (i-1)-го коммутатора второй группы, выход первого коммутатора первой группы соединен с выходом результата устройства, отличающееся тем, что, с целью повышения надежности устройства, в него введены коммутатор сдвига, регистр множимого, два сдвигателя, блок задержки и коммутатор, причем выход коммутатора множимого соединен с информационным входом первого сдвигателя, выход которого соединен с информационным входом регистра множимого, выход которого соединен с информационным входом второго сдвигателя и вторым информационным входом коммутатора множимого, управляющий вход которого соединен с управляющим входом коммутатора сдвига и вторым управляющим входом устройства, первый вход коррекции которого соединен с первым информационным входом коммутатора сдвига, выход которого соединен с управляющим входом первого сдвигателя, а второй информационный вход - с четвертым выходом блока управления реконфигурацией, пятый выход которого соединен с управляющим входом блока задержки, информационный вход которого соединен с выходом первого коммутатора первой группы, а выход - с первым информационным входом коммутатора, выход которого соединен с информационным входом n-го коммутатора второй группы, второй выход i-го коммутатора второй группы соединен с вторым информационным входом i-го коммутатора первой группы, первый выход блока управления реконфигурацией соединен с управляющим входом второго сдвигателя, i-й выход которого соединен с входом множимого i-го операционного блока, третий управляющий вход и второй вход коррекции устройства соединены соответственно с управляющим входом и вторым информационным входом коммутатора.Описание изобретения к патенту
Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств умножения чисел повышенной надежности, удобных для изготовления с применением технологии БИС и СБИС. Известно устройство для умножения, содержащее регистр множимого и n операционных блоков (n-разрядность множимого). Обладая высоким быстродействием, данное устройство имеет низкую надежность, что и является его недостатком. Наиболее близким по технической сущности к предлагаемому изобретению является отказоустойчивое устройство для умножения, содержащее n основных операционных блоков (n-разрядность множимого), m резервных операционных блоков (m= 1,2,3,...), две группы по n+m коммутаторов в каждой, коммутатор множимого и блок управления реконфигурацией, причем вход множителя i-го основного операционного блока (i=1,...n) соединен с входом множителя i-го резервного операционного блока (j= 1,...,m) и входом множителя устройства, вход множимого которого соединен с информационным входом коммутатора множимого, n+m выходов которого соединены с входами множимого соответствующих n основных и m резервных операционных блоков, управляющие входы с первого по n-й коммутаторов первой и второй групп соединены с первым выходом блока управления реконфигурацией и первым управляющим входом коммутатора множимого, второй управляющий вход которого соединен с управляющими входами с (n+1)-го по (n+m)-й коммутаторов первой и второй групп и вторым выходом блока управления реконфигурацией, третий и четвертый выходы которого соединены соответственно с выходами отказа и прерывания устройства, вход контроля и первый управляющий вход которого соединены соответственно с входом контроля и управляющим входом блока управления реконфигурацией, вход слагаемого i-го основного операционного блока соединен с первым выходом i-го коммутатора второй группы, выход результата i-го основного операционного блока соединен с первым информационным входом i-го коммутатора первой группы, вход слагаемого j-го резервного операционного блока соединен с первым выходом (j+n)-го комутатора второй группы, выход результата j-го резервного операционного блока соединен с первым информационным входом (j+n)-го коммутатора первой группы, второй выход k-го коммутатора второй группы (k=1,.. .,n+m) соединен с вторым информационным входом k-го коммутатора первой группы, выход которого, кроме первого коммутатора первой группы, соединен с информационным входом (k-1)-го коммутатора второй группы, выход первого коммутатора первой группы соединен с выходом результата устройства, вход коррекции которого соединен с информационным входом (n+m)-го коммутатора второй группы. Данное устройство обладает способностью продолжать функционирование после отказов основных операционных блоков за счет их замены на резервные операционные блоки. Недостатком данного устройства является его низкая надежность при малом количестве резервных операционных блоков, а при их увеличении резко возрастают аппаратурные затраты. Целью предлагаемого изобретения является повышение надежности устройства за счет продолжения работы на меньшем количестве основных операционных блоков с соответствующим снижением быстродействия устройства. Цель достигается тем, что в отказоустойчивое устройство для умножения, содержащее n операционных блоков (n - разрядность множимого), две группы по n коммутаторов в каждой, коммутатор множимого и блок управления реконфигурацией, причем вход множителя i-го операционного блока (i=1,...,n) соединен с входом множителя устройства, вход множимого которого соединен с первым информационным входом коммутатора множимого, управляющие входы коммутаторов первой и второй групп соединены с первым выходом блока управления реконфигурацией, второй и третий выходы которого соединены соответственно с выходами отказа и прерывания устройства, вход контроля и первый управляющий вход которого соединены соответственно с входом контроля и управляющим входом блока управления реконфигурацией, вход слагаемого i-го операционного блока соединен с первым выходом i-го коммутатора второй группы, второй выход которого соединен с первым информационным входом i-го коммутатора первой группы, выход результата i-го операционного блока соединен с вторым информационным входом i-го коммутатора первой группы, выход которого, кроме выхода первого коммутатора, соединен с информационным входом (i-1)-го коммутатора второй группы, выход первого коммутатора первой группы соединен с выходом результата устройства, дополнительно введены коммутатор сдвига, регистр множимого, два сдвигателя, блок задержки и коммутатор, причем выход коммутатора множимого соединен с информационным входом регистра множимого, выход которого соединен с информационным входом второго сдвигателя и вторым информационным входом коммутатора множимого, управляющий сдвига, выход которого соединен с управляющим входом первого сдвигателя, а второй информационный вход - с четвертым выходом блока управления реконфигурацией, пятый выход которого соединен с управляющим входом блока задержки, информационный вход которого соединен с выходом первого коммутатора первой группым, а выход - с первым информационным входом коммутатора, выход которого соединен с информационным входом n-го коммутатора второй группы, первый выход блока управления реконфигурацией соединен с управляющим входом второго сдвигателя, i-ый выход которого соединен с входом множимого i-го операционного блока, третий управляющий вход и второй вход коррекции устройства соединены соответственно с управляющим входом и вторым информационным входом коммутатора. На фиг. 1 приведена структурная схема предлагаемого отказоустойчивого устройства для умножения; на фиг.2 - структурная схема операционного блока; на фиг.3 - функциональная схема коммутатора первой группы; на фиг.4 - функциональная схема коммутатора второй группы; на фиг.5 - структурная схема блока задержки при n=8; на фиг.6 - структурная схема первого сдвигателя; на фиг. 7 - структурная схема второго сдвигателя; на фиг.8 - функциональная схема блока управления реконфигурацией. Предлагаемое отказоустойчивое устройство для умножения содержит регистр 1 множимого, n операционных блоков 2 (n - разрядность множимого), n коммутатор 3 первой группы, n коммутаторов 4 второй группы, блок 5 задержки, коммутатор 6 множимого, коммутатор 7 сдвига, коммутатор 8, первый 9 и второй 10 сдвигатели, блок 11 управления реконфигурацией, входы 12, 13 и 14 множимого, множителя и контроля устройства соответственно, первый 15 и второй 16 входы коррекции устройства, первый 18, второй 17 и третий 19 управляющие входы устройства, выходы 20, 21 и 22 результата, отказа и прерывания устройства соответственно. Вход множителя i-го блока 2 соединен с входом 13 устройства, вход множимого - с i-ым выходом 23 сдвигателя 10, вход слагаемого - с первым выходом 24 i-го коммутатора 4, выход 25 результата - с первым информационным входом i-го коммутатора 3, второй информационный вход которого соединен с вторым выходом 26 i-го коммутатора 4, информационный вход которого соединен с выходом 27 (i+1)-го коммутатора 3, информационный вход n-го коммутатора 4 соединен с выходом 28 коммутатора 8, первый информационный вход которого соединен с выходом 29 блока 5 задержки, информационынй вход которого соединен с выходом первого коммутатора 3 и выходом 20 результата устройства, вход 12 множимого которого соединен с первым информационным входом коммутатора 6, второй информационный вход которого соединен с информационным входом второго сдвигателя 10 и выходом 30 регистра 1 множимого, информационный вход которого соединен с выходом 31 первого сдвигателя 9, информационный вход которого соединен с выходом 32 коммутатора 6, управляющий вход которого соединен управляющим входом коммутатора 7 и вторым управляющим входом 17 устройства, первый вход 15 коррекции которого соединен с первым информационным входом коммутатора 7, выход 33 которого соединен с управляющим входом первого сдвигателя 9, управляющий вход блока 5 соединен с выходом 34 блока 11, выход 35 которого соединен со вторым информационным входом коммутатора 7, управляющие входы i-ых коммутаторов 3 и 4 объединены и соединены с управляющим входом второго сдвигателя 10 и первым выходом 36 сблока 11, второй и третий выходы которого подключены соответственно к выходам 21 и 22 устройства, входы 14, 16, 18 и 19 которого соединены соответственно с входом контроля блока 11, вторым информационным входом коммутатора 8, управляющим входом блока 11 и управляющим входом коммутатора 8. Рассмотрим функциональное назначение и реализацию узлов и блоков устройства. Регистр 1 предназначен для хранения разрядов множимого и представляет собой n-разрядный регистр, который может быть реализован на синхронных двухтактных D-триггерах. Операционные блоки 2 предназначены для вычисления разрядных значений произведения и формируют на своих выходах 25 значения:[Х
![отказоустойчивое устройство для умножения, патент № 2021631](/images/patents/452/2021005/729.gif)
где [ ] мл означает младший разряд двухразрядного результата;
Х,Y - соответствующие разряды сомножителей, поступающие на входы множимого и множителя блоков 2;
А - одноразрядное слагаемое, поступающее на входы слагаемых блоков 2;
В - внутреннее одноразрядное слагаемое, хранимое в буферных регистрах 38 блоков 2. Реализация блоков 2 показан на фиг.2. В этом случае каждый блок 2 содержит узел 37 вычисления разрядных значений произведения и буферные регистры 38 и 39. Узел 37 формирует на своих выходах двухразрядные значения функции
F=Х
![отказоустойчивое устройство для умножения, патент № 2021631](/images/patents/452/2021005/729.gif)
старший и младший разряды которых записываются соответственно в регистры 38 и 39. Реализация узла 37 зависит от требований к регулярности структуры и к быстродействию, и может быть осуществлена, например, в виде однородной ячеистой структуры. Регистры 38 и 39 могут быть реализованы на синхронных двухтактных D-триггерах с входами установки в нулевое состояние. Коммутор 3 предназначен для передачи информации на свой выход 27 с первого или второго своих информационных входов в зависимости от управляющих сигналов. Реализация коммутатора 3 на элементах И 40, 41 и ИЛИ 42 показана на фиг.3. Коммутатор 4 предназначен для выдачи информации со своего информационногоо входа на первый 24 или второй 25 свои выходы в зависимости от сигнала на управляющем входе. На фиг.4 показана реализация коммутатора 4 на элементах И 43, 44. Блок 5 задержки предназначен для хранения разрядов сумм частичных произведений, формируемых при работе устройства с пониженным быстродействием после отказов блоков 2 и реконфигурации устройства. В зависимости от сигналов на управляющем входе блока 5 он может быть настроен на различную задержку прохождения информации с его информационного входа к его выходу 29. Величина задержки при количестве блоков 2 n=2m (m=1,2,3,...) равна
![отказоустойчивое устройство для умножения, патент № 2021631](/images/patents/452/2021631/2021631t.gif)
1) рабочий режим;
2) режим реконфигурации;
3) рабочий режим с пониженным быстродействием. В исходном состоянии регистры 38, 39 блоков 2, триггеры 50, 51, и счетчики 55-57 блока 11 обнулены, триггеры 49 установлены в "1", на входы 17 и 19 устройства поданы управляющие сигналы, настраивающие соответственно коммутаторы 6 и 7 на передачу информации с их первых информационных входов (входов 12 и 15 устройства), а коммутатор 8 - на передачу информации с его второго информационного входа (входа 16 устройства). В регистр 1 через сдвигатель 9, на управляющем входе которого установлен нулевой код, присутствующий на входе 15 устройства, записывается без сдвига n-разрядное значение множимого, поступающего на вход 12 устройства. Под управлением нулевого кода на выходе 36 блока 11 на i-ом выходе сдвигателя 10 присутствует i-й разряд множимого, коммутаторы 4 этим же сигналом настроены на передачу информации с их информационных входов на их выходы 24, а коммутаторы 3 - с их первых информационных входов (выходов 25 соответствующих блоков 2) на их выходы 27. Рабочий режим. В устройстве вычисляется 2n-разрядное произведение n-разрядных сомножителей за 2n тактов. В каждом из n первых тактов работы устройства на его вход 13 поступает по одному разряду, начиная с младшего, множитель. При этом в i-ом операционном блоке 2 производится умножение i-го разряда множимого, поступающего на его вход множимого с i-го выхода 23 сдвигателя 10, на разряд множителя, поступающего на его вход множитель с входа 13 устройства, и прибавление к младшему разряду получившегося при этом двухразрядного произведения младшего разряда произведения (i+1)-го блока 2, поступающего на его вход слагаемого с выхода 24 i-го коммутатора 4 и старшего разряда произведения i-го блока 2, хранящегося в его регистре 38, старший и младший разряды сформированного i-ым блоком 2 произведения в конце каждого такта записываются в его регистры 38 и 39. После выполнения n первых тактов работы на вход 13 устройства поступает нулевая информация, и далее выполняется еще n тактов, в течение которых из устройства выводится с соответствующими преобразованиями информация, хранящаяся в регистрах 38, 39 блоков 2. Следует отметить, что вывод 2n-разрядного произведения в устройстве осуществляется через его выход 20 по одному разряду в каждом такте. В рассмотренном случае, в течение всей работы устройства на его входе 16 присутствует нулевая информация. Если же требуется получить округленное значение произведения, то необходимо в первом такте работы утсройства на его вход 16 подать определенную информацию (например, для округления 2n-разрядного произведения сомножителей, представленных в двоично-кодированной системе счисления, необходимо на вход 16 в первом такте работы устройства подать двоичный код 1000). Это позволяет осуществить округление результата без дополнительных временных затрат. Кроме того, вход 16 устройства может быть использован для введения результирующей коррекции по знакам при умножении чисел в дополнительном коде. Режим реконфигурации. В процессе функционирования блоки 2 могут отказывать. Предполагается, что каждый блок 2 имеет средства обнаружения отказа в виде средств встроенного контроля, которые могут быть организованы любыми известными способами, например, дублированием или контролем по модулю два. Информация о состоянии блоков 2 поступает на вход 14 устройства в моменты опроса средств контроля блоков 2. Ввиду малой вероятности одновременного отказа двух и более блоков 2 эту ситуацию рассматривать не будем. Сигнал от отказе i-го блока 2 со входа 14 устройства поступает в блок 11, где устанавливает i-й триггер 49 в "0", а также через элемент ИЛИ 52 поступает на выход 22 устройства, вызывая прерывание его работы, а на счетный вход счетчика 55, устанавливая его в первое состояние. Этот сигнал также устанавливает счетчики 56, 57 и триггеры 50 в ноль. Устройство переходит в режим реконфигурации, который условно можно разделить на две фазы. В первой фазе блоком 11 вырабатываются сигналы для настройки блока 5 задержки и сдвигателя 9, определяемые количеством отказавших блоков 2. Во второй фазе блоком 11 вырабатываются сигналы управления коммутаторами 3 и 4 и сдвигателем 10, какие именно из блоков 2 будут продолжать функционирование. После установки счетчика 55 в первое состояние на первом выходе дешифратора 58 появляется "1", которая через первый элемент ИЛИ 64 поступает на первый выход 34 блока 11 и далее на управляющий вход блока 5, настраивая первый коммутатор 46 на передачу информации с информационного входа блока 5 на вход первого регистра 45. Кроме того, этот сигнал устанавливает в "1" первый триггер 51, определяя тем самым на выходе 35 блока 11 величину кода сдвига для сдвигателя 9, равную n/2 разрядов, а также поступает на первый вход первого элемента И 61, подготавливая его к работе во второй фазе реконфигурации. Во второй фазе реконфигурации на вход 18 устройства подаются тактовые импульсы, которые через элемент И 62 блока 11 поступают на счетный вход счетчика 56. При этом на входах дешифратора 59 последовательно появляются "1", разрешая прохождение информации через соответствующие элементы И 60. На других входах элементов И 60 присутствуют "1", за исключением i-го элемента И 60 (поскольку i-й триггер 49 установлен в "0" сигналом об отказе i-го блока 2), поэтому "1" с выходов дешифратора 59 проходят через соответствующие элементы И 60 на входы ИЛИ 53 и далее поступают на счетный вход счетчика 57, который осуществляет отсчет работоспособных блоков 2. Когда количество отсчитанных работоспособных блоков 2 (сигнал на соответствующем выходе счетчика 57) равно требуемому их числу для продолжения работы (в данном случае требуется n/2 блоков 2, что определяется сигналом на выходе первого элемента ИЛИ 64), на выходе соответствующего элемента И 61 (в данном случае первого элемента И 61) появляестя "1", которая через элементы ИЛИ 54 и НЕ 63 запрещает дальнейшую подачу тактовых импульсов на счетный вход счетчика 56 через элемент И 62. Одновременно с отсчетом работоспособных блоков 2 осуществляется настройка группы триггеров 50, которые вначале режима реконфигурации единичным сигналом с выхода элемента ИЛИ 52 были установлены в "0". При наличии "1" на выходе элементов И 60 соответствующие триггеры 50 устанавливаются в "1". В рассматриваемом случае в "1" будут установлены n/2 триггеров 50, остальные останутся в нулевом состоянии. Таким образом, по окончании режима реконфигурации на выходах блока 11 будет следующая информация: на выходе 34 - в первом разряде присутствует "1", а в остальных разрядах "0" (этим набором сигналов блок 5 настраивается на задержку в n/2 разрядов); на выходе 35 - в первом разряде присутствует "1", а в остальных - "0" (этим набором сигналов определяется код сдвига для сдвигателя 9, равный n/2 разрядов); на выходе 36 - в n/2 разрядах, начиная с первого и исключая i-й (если 1
![отказоустойчивое устройство для умножения, патент № 2021631](/images/patents/452/2021002/8773.gif)
![отказоустойчивое устройство для умножения, патент № 2021631](/images/patents/452/2021002/8773.gif)
![отказоустойчивое устройство для умножения, патент № 2021631](/images/patents/452/2021002/8773.gif)
![отказоустойчивое устройство для умножения, патент № 2021631](/images/patents/452/2021002/8773.gif)
Класс G06F7/52 для умножения; для деления
Класс G06F11/00 Обнаружение ошибок, исправление ошибок; контроль