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

 

Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств умножения чисел повышенной надежности, удобных для изготовления с применением технологии БИС и СБИС. Целью изобретения является повышение надежности устройства за счет продолжения работы на меньшем количестве основных операционных блоков с соответствующим снижением быстродействия устройства. Устройство содержит регистр множимого, n операционных блоков (n - разрядность множимого), по n коммутаторов первой и второй групп, коммутатор множимого, блок управления реконфигурацией и нововведенные коммутатор сдвига, два сдвигателя и коммутатор. 8 ил.

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

Известно устройство для умножения, содержащее регистр множимого и 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 значения: [Х˙Y+А+В] мл, где [ ] мл означает младший разряд двухразрядного результата; Х,Y - соответствующие разряды сомножителей, поступающие на входы множимого и множителя блоков 2; А - одноразрядное слагаемое, поступающее на входы слагаемых блоков 2; В - внутреннее одноразрядное слагаемое, хранимое в буферных регистрах 38 блоков 2.

Реализация блоков 2 показан на фиг.2. В этом случае каждый блок 2 содержит узел 37 вычисления разрядных значений произведения и буферные регистры 38 и 39. Узел 37 формирует на своих выходах двухразрядные значения функции F=Х˙Y+А+В, старший и младший разряды которых записываются соответственно в регистры 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=2^m (m=1,2,3,...) равна n/2^а, где l=1,2,...,m - степень деградации, определяющая состояние устройства с определенным уровнем быстродействия. В случае n=8 устройство может работать с использованием 8 операционных блоков 2 - исходное состояние, 4 операционных блоков 2 - первая степень деградации (l=1), 2 операционных блоков 2 - вторая степень деградации (l=2) и одного операционного блока 2 - третья степень деградации (l=3). Реализация блока 5 может быть различной. На фиг. 5 показана реализация блока 5 для случая n=8. В этом случае блок 5 содержит три регистра 45 и два коммутатора 46, причем первый регистр 45 - n/2-разрядный (в рассматриваемом случае 4-разрядный), второй регистр 45 - n/4-разрядный (в рассматриваемом случае 2-разрядный) и третий регистр 45 - n/8-разрядный (в рассматриваемом случае одноразрядный). Подавая на коммутаторы 46 управляющие сигналы, можно образовать цепь регистров разрядностью n/2 или n/2+n/4=3n/4 или n/2+n/4+n/8=7n/8. Регистры 45 блока 5 могут быть реализованы на синхронных двухтактных D-триггерах. Коммутаторы 46, передающие информацию на входы соответствующих регистров с или второго своих информационных входов, могут быть реализованы на элементах И и ИЛИ аналогично показанному на фиг.3 коммутатору 3.

Коммутатор 6 предназначен для передачи информации на свой выход 32 (информационный вход сдвигателя 9) с первого или второго своих информационных входов в зависимости от управляющего сигнала на входе 17 устройства. Он может быть реализован аналогично показанному на фиг.3 коммутатору 3.

Коммутатор 7 предназначен для передачи кода сдвига на управляющий вход сдвигателя 9 (выход 33 коммутатора 7) с первого входа 15 коррекции устройства или с выхода 35 блока 11 в зависимости от управляющего сигнала на входе 17 устройства. Он может быть реализован аналогично показанному на фиг.3 коммутатору 3.

Коммутатор 8 предназначен для передачи на свой выход 28 (информационный вход n-го коммутатора 4) информации с первого или второго своих информационных входов в зависимости от управляющего сигнала на входе 16 устройства. Он может быть реализован аналогично показанному на фиг.3 коммутатору 3.

Сдвигатель 9 предназначен для сдвига информации на величину, определяемую кодом на его управляющем входе. Он выполняет циклический сдвиг влево информации, поступающей на его информационный вход, и может быть реализован подобно тому, как это показано на фиг.6. В этом случае он содержит m коммутаторов 47, реализованных аналогично показанному на фиг.3 коммутатору 3, причем первый (младший) разряд кода сдвига на управляющем входе сдвигателя 9 настраивает первый коммутатор 47 на сдвиг на 0 или 1 разряд, второй разряд кода сдвига настраивает второй коммутатор 47 на сдвиг на 0 или 2 разряда, а m-й разряд кода сдвига - m-й коммутатор 47 на сдвиг на 0 или 2^m-1 разрядов. Таким образом, сдвигатель 9 под управлением кода, подаваемого на его управляющий вход, может быть настроен на сдвиг множимого на любое число разрядов.

Сдвигатель 10 предназначен для перераспределения разрядов множимого, поступающих на его информационный вход с выхода 30 регистра 1 множимого, между входами множимого блоков 2 таким образом, что информация может быть сдвинута влево, начиная с любого разряда, оставляя неизменной свою правую часть. Он может быть реализован как это показано на фиг.7. В этом случае он содержит n коммутаторов 48, реализованных аналогично показанному на фиг.3 коммутатору 3, причем первый (младший) разряд кода сдвига на управляющем входе сдвигателя 10 настраивает первый коммутатор 48 на сдвиг всей информации (n разрядов) влево на 0 или 1 разряд, второй разряд кода сдвига настраивает второй коммутатор 48 на сдвиг (n-1) разрядов информации влево на 0 или 1 разряд, третий разряд кода сдвига - третий коммутатор 48 на сдвиг (n-2) разрядов информации влево на 0 или 1 разряд и т.д.

Блок 11 управления реконфигурацией предназначен для выдачи управляющих сигналов на прерывание работы устройства при отказах блоков 2, на выбор работоспособной группы блоков 2 и организации ее связи с блоком 5 задержки и регистром 1, на выбор необходимой величины задержки в блоке 5, на установку кода сдвига множимого при его перезаписи в регистр 1 после каждого цикла работы устройства, а также для выдачи сигнала об отказе устройства после n отказов блоков 2. Одна из возможных реализаций блока 11 для устройства с количеством блоков 2 n=8 (m=3) показана на фиг.8. Блок 11 содержит две группы по n триггеров 49 и 50, группу из m триггеров 51, n-входовые элементы ИЛИ 52 иил ИЛИ 53, m-входовой элемент ИЛИ 54, три счетчика 55-57, два дешифратора 58, 59, n элементов И 60, m элементов И 61, элементы И 62 и НЕ 63 и группу из (m-1) элементов ИЛИ 64. Первая группа триггеров 49 фиксирует состояния блоков 2, причем если i-й блок 2 отказал, то i-й триггер 49 устанавливается в "0". Сигнал об отказе любого блока 2 через элемент ИЛИ 52 поступает на счетный вход счетчика 55, который совместно с дешифратором 58 определяет количество отказавших блоков 2 в устройстве. Кроме того, сигнал от отказе любого блока 2 сбрасывает в нулевое состояние счетчики 56 и 57 и вторую группу триггеров 50, а также поступает на выход 22 устройства, вызывая прерывание его работы. Выходы дешифратора 58 объединены с помощью элемента ИЛИ 64 в группы, выход каждой из которых соответствует определенной степени деградации быстродействия устройства, например, первый элемент ИЛИ 64 объединяет выходы дешифратора 58 с первого по n/2-й, т.е. до n/2 отказов блоков 2 устройство работает с первой степенью деградации быстродействия (с использованием n/2 работоспособных блоков 2), второй элемент ИЛИ 64 объединяет выходы дешифратора 58 с (n/2+1)-го по (n/2+n/4)-й, и сигнализирует о второй степени деградации быстродействия (использование n/4 работоспособных блоков 2). Сигналы с выходов элементов ИЛИ 64 и (n-1)-го выхода дешифратора 58 поступают на выход 34 блока 11 (настраивают соответствующую задержку блока 5) и устанавливают в "1" соответствующие триггеры 51, на выходах которых формируется код сдвига для сдвигателя 9, определяющий величину сдвига множимого после каждого цикла работы устройства в режиме с пониженным быстродействием.

Для определения, какие именно блоки 2 будут продолжать функционирование, а также для выработки сигналов настройки коммутаторов 3, 4 и сдвигателя 10, подключающих информационные входы и выходы соответствующих блоков 2 в рабочую конфигурацию, на второй управляющий вход 18 устройства (управляющий вход блока 11) подаются тактовые импульсы, поступающие через элемент И 62 на счетный вход счетчика 56. С выхода счетчика 56 через дешифратор 59 сигналы поступают на первые входы элементов И 60, начиная с первого элемента И 60, на выходах которых появляются "1", если соответствующий блок 2 исправен (соответствующий триггер 49 находится в "1"). Количество "1" на выходах элементов И 60, а следовательно, количество исправных блоков 2 подсчитываются с помощью счетчика 57. Когда количество отсчитанных счетчиком 57 работоспособных блоков 2 равно требуемому их количеству, которое определяется степенью деградации быстродействия устройства и выражается информацией на выходах дешифратора 58 и элементов ИЛИ 64, то на выходе соответствующего элемента И 61 появляется "1", которая через элементы ИЛИ 54 и НЕ 63 поступает на второй вход элемента И 62, запрещая дальнейшее прохождение тактовых импульсов на счетный вход счетчика 56. Счетчик 56 остается в состоянии, соответствующем номеру последнего блока 2 в рабочей конфигурации устройства. Одновременно с подсчетом счетчиком 57 исправных блоков 2 сигналами с выходов элементов И 60 осуществляется установка в "1" триггеров 50, соответствующих исправным блокам 2, подключаемым в рабочую конфигурацию. На выходе 36 блока 11 формируется управляющий код для настройки коммутаторов 3, 4 и сдвигателя 10.

После n-го отказа блоков 2 с n-го выхода дешифратора 58 на второй выход блока 11 (выход 21 устройства) выдается сигнал об отказе и невозможности дальнейшей реконфигурации устройства.

На структурных и функциональных схемах с целью упрощения условно не показаны цепи установки в нулевое состояние регистров 38, 39 блоков 2, триггеров 50, 51 и счетчиков 55-57 блока 11, цепи установки в единичное состояние триггеров 59 блока 11, а также цепи синхронизации регистра 1, регистров 38, 39 блоков 2 и регистров 45 блока 5. Однако можно отметить, что используется общая цепь синхронизации регистров 38, 39 блоков 2 и регистров 45 блока 5 (сигналы подаются в конце каждого такта работы устройства), цепь синхронизации регистра 1 (сигнал подается перед началом работы устройства и в конце каждого цикла его работы), общая цепь установки в нулевое состояние регистров 38, 39 блоков 2 (сигнал подается перед началом любого из режимов работы устройства) и общая цепь установки в нулевое состояние триггеров 59, 51 и счетчиков 55-57 блока 11, соединенная с цепью установки в единичное состояние триггеров 49 блока 11 (сигнал подается перед началом использования устройства при всех исправных блоках 2).

Работу устройства рассматривают для трех режимов: 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≅i ≅ n/2) присутствуют "1", а в остальных - "0" (этим набором сигналов определяется код сдвига для сдвигателя 10 и настраиваются коммутаторы 3 и 4 таким образом, что n/2 соответствующих работоспособных блоков 2 включаются в рабочую конфигурацию, а остальные n/2 блоков 2 исключаются из работы). Зтаем осуществляется обнуление регистров 38, 39 блоков 2, а на вход 17 устройства подают управляющий сигнал, настраивающий коммутаторы 6 и 7 на передачу информации с их вторых информационных входов. Устройство переходит в режим работы с пониженным быстродействием.

Режим работы с пониженным быстродействием.

При этом режиме вычисление 2n-разрядного произведения n-разрядных сомножителей производится за большее количество тактов, чем при использовании всех имеющихся операционных блоков 2. Так, в случае, когда общее количество операционных блоков 2 в устройстве n=2^m (m=1,2,3,...) произведение n-разрядных сомножителей может быть эффективно вычислено по m+1 алгоритмам, различающихся быстродействием: основной алгоритм, рассмотренный выше, когда все n блоков работоспособны и требуется 2n тактов работы устройства, и m алгоритмов с пониженным быстродействием, каждый из которых определяется степенью деградации 1 быстродействия устройства. При l-й степени деградации (l=1,... , m) произведение n-разрядных сомножителей вычисляется за 2^l циклов, каждый из которых состоит из (n+n/2^l) тактов, с использованием n/2^l операционных блоков 2 (при первой степени деградации l=1 используются n/2 блоков 2, при второй - n/4 блоков 2 и т.д.). В каждом цикле осуществляется вычисление частичного произведения n-разрядного множителя на n/2^l разрядов множимого и подсуммирование к нему суммы частичных произведений, сформированной в предыдущем цикле и хранимой в регистрах 45 блока 5 (старшие разряды) и в регистрах 39 блоков 2 (младшие разряды). В итоге получается новая сумма частичных произведений. Блок 5 настраивается на задержку в (n-n/2^l) тактов.

После первого отказа блока 2 и реконфигурации устройства работа продолжается с использованием n/2 блоков 2, начиная с первого и исключая отказавший блок 2, т.е. устанавливается первая степень деградации (l=1). Умножение n-разрядных сомножителей в устройстве выполняется за два цикла по (n+n/2^l) тактов каждый.

В первом цикле вычисляется частичное произведение n/2 разрядов множимого на n-разрядный множитель аналогично основному режиму. Отличие состоит в том, что по окончании каждого такта с выхода 25 первого блока 2 в первый регистр 45 блока 5 записывается очередной разряд частичного произведения (запись первого разряда частичного произведения производится во втором такте первого цикла, так как в первом такте этот разряд записывается в регистр 39 первого блока 2). В (n/2+2)-ом такте первого цикла первый разряд частичного произведения с выхода 29 блока 5 поступает на первый информационный вход коммутатора 8, однако на вход слагаемого n/2-го блока 2 (если номер отказавшего блока 2 i>n/2) или (n/2+1)-го блока 2 (если 1 ≅ i ≅ n/2) не проходит, как и последующие (n/2-1) разрядов частичного произведения (что достигается подачей соответствующего сигнала на вход 19 устройства), поскольку младшие n/2 разрядов частичного произведения являются разрядами окончательного результата и в последующих вычислениях не участвуют.

По окончании (n+1)-го такта первого цикла на вход 19 устройства подается сигнал, разрешающий прохождение информации с выхода 29 блока 5 на вход слагаемого n/2-го рабочего блока 2 и одновременно с записью в последующих (n/2-1) тактах первого цикла в первый регистр 45 блока 5 старших n/2 разрядов частичного произведения осуществляется запись в регистры 39 блоков 2 младших разрядов этого произведения.

В последнем такте первого цикла содержимое регистра 1 с помощью коммутатора 6 и сдвигателя 9 циклически сдвигается влево на n/2 разрядов под управлением кода на выходе 35 блока 11, так что на входы множимого участвующих в работе блоков 2 поступают старшие n/2 разрядов множимого.

Во втором цикле работы устройства вычисляется частичное произведение n-разрядного множителя на n/2 старших разрядов множимого и подсуммирование к нему n старших разрядов частичного произведения, сформированного в первом цикле (n/2 разрядов частичного произведения первого цикла хранятся в регистрах 39 блоков 2, а n/2 разрядов поступают в каждом из n/2 первых тактов второго цикла из блока 5).

Как в первом, так и во втором циклах в течение их первых n тактов на вход 13 устройства поступает по одному разряду, начиная с младших, множитель, а в течение последних n/2 тактов циклов - нулевая информация.

Следует отметить, что вывод 2n-разрядного произведения сомножителей осуществляется через выход 20 устройства в первые n/2 тактов первого цикла (младшие n/2 разрядов произведения) и в каждом такте второго цикла (старшие n+n/2 разрядов произведения).

При возникновении второго отказа среди блоков 2 устройство вновь переходит в режим реконфигурации по сигналу на выходе 22 прерывания устройства. Одновременно с выдачей этого сигнала осуществляется обнуление триггеров 50 и счетчиков 56, 57 блока 11, счетчик 55 переходит в состояние "2" и на втором выходе дешифратора 58 появляется "1". Поскольку первые n/2 выходов дешифратора 58 являются входами одного и того же элемента ИЛИ 64, то на выходах 34 и 35 блока 11 остается неизменная информация для настройки блока 5 и сдвигателя 9 соответственно. Во второй фазе реконфигурации при подаче тактовых сигналов на вход 18 устройства аналогично описанному выше случаю устанавливаются в "1" n/2 триггеров 50, начиная с первого и исключая те триггеры 50, номера которых соответствуют номерам отказавших блоков 2, остальные триггеры 50 остаются в нулевом состоянии. Таким образом, в продолжении вычислений участвуют n/2 работоспособных блоков 2, начиная с первого. Через остальные блоки 2 с помощью соответствующих коммутаторов 3 и 4 организуется "обходной путь" информации.

Первая степень деградации быстродействия устройства (использование при умножении n/2 работоспособных блоков 2) сохраняется до n/2 отказов блоков 2. После возникновения (n/2+1)-го отказа блоков 2 с соответствующего выхода дешифратора 58 "1" через второй элемент ИЛИ 64 поступает на выход 34 блока 11 (блок 5 настраивается на задержку (n/2+n/4) тактов), а также устанавливает в ""1" второй триггер 51, определяя код сдвига для сдвигателя 9 на выходе 35 блока 11 равным n/4 разрядов. Во второй фазе реконфигурации требуемым для продолжения работы количеством блоков 2 является n/4 блоков 2 (в рассматриваемом примере реализации блока 11 на фиг.4 требуется n/4=2 блока 2), что определяется "1" на выходе второго элемента ИЛИ 64. После того, как счетчик 57 отсчитал n/4 работоспособных блоков 2, запрещается подача тактовых сигналов через элемент И 62 на счетный вход счетчика 56. В работу включается n/4 работоспособных блоков 2, начиная с первого. Устанавливается вторая степень деградации быстродействия устройства, которая сохраняется при последующих (n/4-1) отказах блоков 2, после чего быстродействие снижается до третьей степени деградации и т.д.

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

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

ОТКАЗОУСТОЙЧИВОЕ УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ, содержащее n операционных блоков (n - разрядность множимого), две группы по n коммутаторов в каждой, коммутатор множимого и блок управления реконфигурацией, причем вход множителя i-го операционного блока (i = 1, ... , n) соединен с входом множителя устройства, вход множимого которого соединен с первым информационным входом коммутатора множимого, управляющие входы коммутаторов первой и второй групп соединены с первым выходом блока управления реконфигурацией, второй и третий выходы которого соединены соответственно с выходами отказа и прерывания устройства, вход контроля и первый управляющий вход которого соединены соответственно с входом контроля и управляющим входом блока управления реконфигурацией, вход слагаемого i-го операционного блока соединен с первым выходом i-го коммутатора второй группы, выход результата i-го операционного блока соединен с первым информационным входом i-го коммутатора первой группы, выход которого, кроме выхода первого коммутатора, соединен с информационным входом (i-1)-го коммутатора второй группы, выход первого коммутатора первой группы соединен с выходом результата устройства, отличающееся тем, что, с целью повышения надежности устройства, в него введены коммутатор сдвига, регистр множимого, два сдвигателя, блок задержки и коммутатор, причем выход коммутатора множимого соединен с информационным входом первого сдвигателя, выход которого соединен с информационным входом регистра множимого, выход которого соединен с информационным входом второго сдвигателя и вторым информационным входом коммутатора множимого, управляющий вход которого соединен с управляющим входом коммутатора сдвига и вторым управляющим входом устройства, первый вход коррекции которого соединен с первым информационным входом коммутатора сдвига, выход которого соединен с управляющим входом первого сдвигателя, а второй информационный вход - с четвертым выходом блока управления реконфигурацией, пятый выход которого соединен с управляющим входом блока задержки, информационный вход которого соединен с выходом первого коммутатора первой группы, а выход - с первым информационным входом коммутатора, выход которого соединен с информационным входом n-го коммутатора второй группы, второй выход i-го коммутатора второй группы соединен с вторым информационным входом i-го коммутатора первой группы, первый выход блока управления реконфигурацией соединен с управляющим входом второго сдвигателя, i-й выход которого соединен с входом множимого i-го операционного блока, третий управляющий вход и второй вход коррекции устройства соединены соответственно с управляющим входом и вторым информационным входом коммутатора.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8