УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДВУМЕРНОЙ СВЕРТКИ Российский патент 1995 года по МПК G06F17/16 G06F11/16 

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных системах для вычисления двумерной свертки.

Обычно для обеспечения достоверности получаемых при обработке информации результатов используется тестовый периодический контроль, проводимый с помощью внешних программно-аппаратных средств. При периодическом тестовом контроле вероятность пропуска отказа блока обработки пропорциональна времени между тестовыми проверками (период контроля), при этом объем ошибочной информации, выдача которой происходит между тестовыми проверками, также пропорционален периоду контроля. Временные затраты на тестовую проверку определяются объемом теста, поэтому пропускная способность линейки из блоков обработки известных устройств находится в обратно пропорциональной зависимости от временных затрат на тестовые проверки. Вероятность обнаружения отказа с помощью тестовых проверок определяется разрешающей способностью теста и объемом аппаратуры, охваченной контролем. Время восстановления отказа с помощью тестовых проверок определяется разрешающей способностью теста и объемом аппаратуры, охваченной контролем. Время восстановления вычислительного процесса после обнаружения отказа блока обработки (получение достоверного результата на выходе устройства) пропорционально числу n блоков обработки устройства (длина n линейки устройства).

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

Поставленная цель достигается тем, что в устройство, содержащее с первого по Q-й блоки 1 обработки, причем информационные входы 13 и 14 первой и второй групп, первый и второй управляющие входы 16 и 17 устройства подключены соответственно к информационным входам первой и второй групп, первому и второму управляющим входам первого блока обработки, выходы первой и второй групп, первый и второй выходы i-го блока обработки (где i1, Q-1) подключены соответственно к информационным входам первой и второй групп, первому и второму управляющим входам (i+1)-го блока обработки, вход 21 тактовых импульсов устройства подключен к тактовым входам блоков обработки с первого по Q-й, введены с (Q+1)-го по L-й блоки обработки 1, где L Q + R, R число резервных блоков обработки 1, первый и второй блоки суммирования 2 и 3, L сумматоров 4, L-1 регистров 5, группа из L узлов сравнения 6, узел сравнения 7, с первой по (L+1)-ю группы элементов ИЛИ 8 и 9, L групп элементов И 10, элемент ИЛИ-НЕ 11 и элемент ИЛИ 12, причем выходы первой и второй групп, первый и второй выходы j-го блока обработки (где j Q, L-1) подключены соответственно к информационным входам первой и второй групп, первому и второму управляющим входам (j+1)-го блока обработки, вход тактовых импульсов 21 устройства подключен к тактовым входам блоков суммирования 2 и 3, блоков обработки с (Q+1)-го по L-й, входам записи/считывания регистров 3, информационные входы третьей группы 15 устройства подключены соответственно к информационным входам третьей группы первого блока обработки, выходы третьей группы К-го блока обработки (где К 1, L-1) подключены соответственно к первым входам элементов И 10 К-й группы и соответственно к управляющим входам первой группы (K+1)-го блока обработки, выходы третьей группы L-го блока обработки подключены соответственно к первым входам элементов И 10 L-й группы, управляющие входы 19 первой группы устройства подключены соответственно к управляющим входам первой группы первого блока обработки, выходы четвертой группы К-го блока обработки подключены соответственно к первым входам элементов ИЛИ 8 К-й группы, выходы которых подключены соответственно к управляющим входам первой группы (К+1)-го блока обработки, выходы пятой группы l-го блока обработки (где l 1,L) подключены соответственно к информационным входам группы l-го сумматора 4, выходы К-го сумматора 4 подключены соответственно к информационным входам К-го регистра 5 и соответственно ко входам первой группы К-го узла сравнения 6, выходы L-го комбинационного сумматора 4 подключены соответственно ко входам первой группы L-го узла сравнения 6 группы, управляющие входы второй группы 20 устройства подключены к управляющим входам вторых групп блоков обработки с первого по L-й и входам вторых групп узлов сравнения 6 групп, выход l-го узла сравнения 6 группы подключен к вторым входам элементов И 10 l-й группы и l-му входу элемента ИЛИ-НЕ 11, выход которого подключен к первому входу элемента ИЛИ 12, выход которого подключен к выходу 27 признака отказа устройства, выходы К-го регистра 5 подключены соответственно к вторым входам элементов ИЛИ 8 К-й группы, третий выход l-го блока обработки подключен к информационному входу l-го сумматора 4 и l-му выходу 26 группы признака отказа устройства, третий управляющий вход 18 которого подключен к управляющим входам блоков суммирования 2 и 3, выходы элементов И 10 групп с первой по L-ю подключены соответственно ко входам элементов ИЛИ 9 L-й группы, выходы которых подключены к информационным входам блоков суммирования 2 и 3, выходы первого блока суммирования 2 подключены к выходам 28 результата устройства и входам первой группы (L+1)-го узла сравнения 7, инверсный выход которого подключен ко второму входу элемента ИЛИ 12, выходы второго блока суммирования 3 подключены соответственно ко входам второй группы (L+1)-го узла сравнения 7, l-й вход установки первой группы 22, l-й вход установки второй группы 23, l-й вход установки третьей группы 24 и l-й вход блокировки 25 устройства подключены соответственно к первому, второму, третьему входам установки и входу блокировки l-го блока обработки.

Каждый блок обработки 1 содержит первый и второй вычислительные узлы 29 и 30, узел сравнения 31, триггер 32, с первого по третий узлы элементов И 33-35, узел элементов ИЛИ 36 и элемент И 37, причем в каждом блоке обработки информационные входы первой, второй и третьей группы 37-39, первый и второй управляющие входы 40 и 41 и управляющие входы 42 первой группы блока подключены соответственно ко входам группы первого узла элементов И 33 и выходам группы второго узла элементов И 34, выходы первой группы первого узла элементов И 33 подключены соответственно ко входам первой группы узла элементов ИЛИ 36, выходы которого подключены соответственно к выходам первой группы 52, второй группы 53, третьей группы 54, первому 55 и второму 56 выходам блока, выходы первой группы второго узла элементов И 34 подключены к информационным входам первой группы, второй группы, третьей группы, первому и второму управляющим входам первого и второго вычислительных узлов, выходы первой, второй и третьей групп, первый и второй выходы первого вычислительного узла 29 подключены ко входам первой группы узла сравнения 31 и входам группы третьего узла элементов И 35, выходы которого подключены соответственно ко входам второй группы узла элементов ИЛИ 36, выходы первой, второй и третьей групп, первый и второй выходы второго вычислительного узла 30 подключены соответственно ко входам второй группы узла сравнения 31, выход которого подключен к информационному входу триггера 32, выход которого подключен ко входу третьего узла элементов И 35, третьему выходу 50 блока обработки, инверсному входу первого узла элементов и 33 и входу второго узла элементов И 34, выходы вторых групп первого и второго узлов элементов И 33 и 34 подключены соответственно к выходам четвертой 51 и пятой 49 групп, управляющие входы второй группы 43 блока обработки подключены соответственно к управляющим входам группы первого вычислительного узла и управляющим входам группы второго вычислительного узла, первый и второй входы установки 45 и 46 блока обработки подключены соответственно ко входам установки в "нуль" и "единицу" триггера 32, третий вход установки 44 блока обработки подключен ко входам установки в исходное состояние первого и второго вычислительных узлов, тактовый вход 48 и вход 47 блокировки блока обработки подключены соответственно к первому и второму (инверсному) входам элемента И 37, выход которого подключен к тактовым входам первого и второго вычислительных узлов и триггера.

Каждый блок суммирования 2(3) содержит два регистра 97, 98 и сумматор 99, причем тактовый вход 102 блока суммирования подключен ко входам записи/считывания первого и второго регистров 97 и 98, выходы которых подключены соответственно к информационным входам сумматора 99, выходы которого подключены к выходам 103 блока суммирования и информационным входам второго регистра 98, информационные входы 100 и управляющий вход 101 блока суммирования подключены соответственно к информационным входам первого регистра 97 и входу установки в нуль второго регистра 98.

Каждый вычислительный узел содержит четыре группы регистров 57-60, регистр 61, умножитель 62, сумматор 63, группу триггеров 64, триггер 65, М + 3Р + 7 групп элементов И 66-73, где М 1Р + 1, шесть групп элементов ИЛИ 74-79, элемент И 80, элемент ИЛИ 81 и два дешифратора 82 и 83, причем информационные входы первой группы 84 вычислительного узла подключены к информационным входам первого регистра первой группы 57₁ и первым входам элементов И первой группы 70, выходы которых подключены к первым входам элементов ИЛИ первой группы 76, выходы которых подключены к информационным входам первого регистра второй группы 59₁, выходы m-го регистра 57 первой группы (где m 1, М-1) подключены к информационным входам (m+1)-го регистра 57 первой группы и первым входам элементов И (m+1)-й группы 66, выходы элементов И группы 66 с второго по (М+1)-й подключены к соответствующим входам элементов ИЛИ второй группы 74, выходы которых подключены к выходам первой группы 92 вычислительного узла, информационные входы второй группы 85 которого подключены к информационным входам первого регистра третьей группы 58₁ и первым входам элементов И (М+2)-й группы 72, выходы которых подключены к первым входам элементов ИЛИ третьей группы 79, выходы которых подключены к информационным входам первого регистра четвертой группы 60₁, выходы первого регистра второй группы 59₁ подключены к информационным входам первой группы умножителя 62, первым входам элементов И 68₁ (М+3)-й группы и информационным входам второго регистра второй группы 59₂, выходы n-го регистра 59 второй группы (где n 2, Р) подключены к информационным входам (n+1)-го регистра второй группы 59 и первым входам элементов И 68 (М+2+n)-й группы, выходы элементов И 68 групп с (М+3)-й по (М+3+Р)-ю подключены к соответствующим входам элементов ИЛИ 77 четвертой группы, выходы которых подключены к первым входам элементов И 71 (М+Р+4)-й группы, выходы которых подключены соответственно ко вторым входам элементов ИЛИ 76 первой группы, выходы S-го регистра 58 третьей группы (где S 1,P) подключены к информационным входам (S+1)-го регистра 58 и к первым входам элементов И 67 (М+Р + 4 + +S)-й группы, выходы элементов И 67 групп с (М+Р+5)-й по (М+2Р+5)-ю подключены к соответствующим входам элементов ИЛИ 75 пятой группы, выходы которых подключены соответственно к выходам второй группы вычислительного узла, выходы первого регистра 60 четвертой группы подключены к первым входам элементов И 69₁ (М + 2Р + 6)-й группы, информационным входам второго регистра четвертой группы 60₂ и информационным входам второй группы умножителя 62, выходы которого подключены соответственно к информационным входам первой группы сумматора 63, выходы которого подключены соответственно к выходам группы 94 вычислительного узла, информационные входы третьей группы 86 которого подключены соответственно к информационным входам регистра 61, выходы которого подключены соответственно к информационным входам второй группы сумматора 63, выходы r-го регистра 60 четвертой группы (где r 2, Р) подключены к информационным входам (r+1)-го регистра четвертой группы и первым входам элементов И 69 (М+2Р+6+r)-й группы, выходы элементов И 69 групп с (М+2Р+7)-й по (М+3Р+7)-ю подключены к соответствующим входам элементов ИЛИ 78 шестой группы, выходы которых подключены соответственно к первым входам элементов И 73 (М+3Р+8)-й группы, выходы которых подключены соответственно ко вторым входам элементов ИЛИ 79 третьей группы, первый управляющий вход 87 устройства подключен к вторым входам элементов И 70 первой группы, вторым (инверсным) входам элементов И 71 (М+Р+4)-й группы и информационному входу первого триггера 64₁ группы, выход v-го триггера 64 группы (где v 1, М-1) подключен к информационному входу (v+1)-го триггера группы 64 и первому входу v-го элемента И 80, выходы элементов И 80 с первого по М-й подключены соответственно к входам элемента ИЛИ 81, выход которого подключен к первому выходу вычислительного узла 95, второй управляющий вход 88 которого подключен ко вторым входам элементов И 72 (М+2)-й группы, вторым (инверсным) входам элементов И 73 (М+3Р+8)-й группы и информационному входу триггера 65, выход которого подключен ко второму выходу 96 вычислительного узла, управляющие входы 89 группы с первого по а-й (где а log₂M) которого подключен соответственно ко входам первого дешифратора 82, i-й выход которого (где i 1,M) подключен ко вторым входам элементов И 66 (i+1)-й группы и второму входу i-го элемента И 80, управляющие входы 89 группы с (a+1)-го по Н-й (где Н а log₂(P+1)) вычислительного узла подключен к входам второго дешифратора 83, j-й выход которого (где j 1, Р+1) подключен к вторым входам элементов И (М+Р+4+j)-й группы 67, (М+2+j)-й группы 68 и (M+2P+6+j)-й группы 69, тактовый вход 90 вычислительного узла подключен к тактовым входам регистров и триггеров, вход 91 установки в исходное состояние вычислительного узла подключен ко входам установки в нуль всех регистров и триггеров.

На фиг. 1 представлена структурная схема устройства; на фиг. 2 структурная схема блока обработки; на фиг. 3 структурная схема вычислительного узла.

Устройство для вычисления двумерной свертки содержит L блоков обработки 1, где L Q + R, Q размерность окна двумерной свертки (Р х Q), R число резервных блоков, блоки суммирования 2 и 3, L сумматоров 4, L-1 регистров 5, L узлов сравнения 6, узел сравнения 7, L групп элементов ИЛИ 8 и 9, L групп элементов И 10, элемент ИЛИ-НЕ 11, элемент ИЛИ 12, информационные входы 13-15, управляющие входы 16-20, тактовый вход 21, входы установки 22-24, входы блокировки 25, выходы 26, 27 признака отказа, выход результата 28.

Каждый блок обработки 1 содержит вычислительные узлы 29 и 30, узел 31 сравнения, триггер 32, узлы элементов И 33-35, узел элементов ИЛИ 36, информационные входы 37-39, управляющие входы 40-43, входы установки 44-46, вход блокировки 47, тактовый вход 48, выходы 49-56.

Каждый вычислительный узел 29 (30) содержит группы регистров 57-60, регистр 61, умножитель 62, сумматор 63, группу триггеров 64, триггер 65, группы элементов И 66-73, группы элементов ИЛИ 74-79, элемент И 80, элемент ИЛИ 81, дешифраторы 82 и 83, информационные входы 84-86, управляющие входы 87-89, тактовый вход 90, вход 91 установки в исходное состояние, выходы 92-96.

Каждый блок суммирования 2(3) содержит регистры 97 и 98, сумматор 99, информационные входы 100, управляющий вход 101, тактовый вход 102 и выход 103.

В основу работы устройства положен алгоритм вычисления двухмерной свертки
Y_ij= x_i-p,j-q, i , j , который состоит из двух частей:
1. Zoi

При описании работы устройства в обозначении х_ij^(k) индекс (К) в скобках указывает номер такта работы устройства, а индекс К без скобок номер рекуррентного шага.

Вычислительный узел 29 (30) обладает возможностью реализации следующих функций:
Х^i+Ip+1 xⁱ;
Ω^i+p+1=ωⁱ
Zⁱ⁺¹ Zⁱ+aⁱ bⁱ, где
aⁱ=
bⁱ=
T₁^i+Ip+2 τ₁ⁱ
T₂ⁱ⁺¹ τ₂ⁱ, где xⁱ ωⁱ и αⁱ значения соответственно на информационных входах 84, 85 и 86 вычислительного узла на i-м такте;
Хⁱ, Ωⁱ и Zⁱ значения соответственно на выходах 92, 93 и 94 вычислительного узла на i-м такте;
τ₁ⁱ и τ₂ⁱ значения соответственно на управляющих входах 87 и 88 вычислительного узла на i-м такте;
Т₁ⁱ и Т₂ⁱ значения соответственно на выходах 95 и 96 вычислительного узла на i-м такте.

Блок суммирования 2(3) обладает возможностью реализации следующих функций:
Yⁱ⁺¹= где Zⁱ значение на информационных входах 100 блока суммирования на i-м такте;
Yⁱ значение на выходе 103 блока суммирования на i-м такте;
τ₃ⁱ значение на управляющем входе 101 блока суммирования на i-м такте.

Вычислительный узел 29(30) работает следующим образом.

На входы 13-17 подаются соответственно значения х, ω, Z, τ₁ и τ₂. При τ₁ 1 значение х записывается в регистры 57₁ и 59₁ и выдаются на выход 92 с задержкой на IP+1 тактов. При τ ₁ 0 содержимое регистра 59_р+1 переписывается в регистр 59₁. При τ₂ 1 значение ω записывается в регистры 58₁ и 60₁ и выдается на выход 93 с задержкой на Р+1 тактов. При τ₂ 0 содержимое регистра 60_р+1 переписывается в регистр 60₁. С выходов регистров 59₁ и 60₁ значения х и ω поступают на информационные входы комбинационного умножителя 62, с выходов которого произведение ω˙ х поступает на один информационный вход комбинационного сумматора 63, на другой информационный вход которого поступает содержимое регистра 61, в результате этого на выходе сумматора 63 формируется значение х ωⁱ + z. Управляющий сигнал τ₁ выдается на выход 95 с задержкой на IP+1 тактов, управляющий сигнал τ₂ выдается на выход 96 с задержкой на один такт.

Значения М IP+1 и P+1 подаются на входы 20 устройства и через выходы 43 блоков обработки 1 и через выходы 89 вычислительных узлов 29, 30 поступают соответственно на входы дешифраторов 82 и 83. В результате дешифрации значения М с соответствующего выхода дешифратора 82 выдается единичное значение α_i, где i ≅ М, которое открывает элементы И 66_i и 80_i. В результате этого информация с выходов регистра 57_i и триггера 64_iсоответственно через элементы И 66_i и 80_i и соответственно через элементы ИЛИ 74 и 81 выдается на выходы 92 и 95. В результате дешифрации значения Р + 1 с соответствующего выхода дешифратора 83 выдается единичное значение β_i, где i ≅ P+1, которое открывает элементы И 67_i, 68_i и 69_i. В результате этого информация с выходов регистров 58_i, 59_i и 60_i соответственно через элементы И 67_i, 68_i и 69_i и соответственно через элементы ИЛИ 74, 75 и 77 поступает на выходы 92, 93 и на выходы элементов И 71. Таким образом, в устройстве реализуются возможности решения задач вычисления двумерной свертки различной размерности (для различных значений I, τ, P и Q).

Блоки суммирования 2(3) работает следующим образом. При τ₃ 1 регистр 98 обнуляется и на выходе сумматора 99 формируется значение 0+Z, где Z содержимое регистра 97. При τ₃ 0 блок суммирования работает в режиме накапливающего сумматора, при этом на выходе сумматора 99 формируется сумма Zⁱ + Zⁱ⁺¹, которая выдается на выход 103 блока суммирования.

Входные и выходные потоки данных задаются следующими выражениями.

Значения x_kl подаются на выход 13 в моменты времени
t=
Значения ω_pq подаются на выход 14 в моменты времени
t t_o + p Pq,
p ,
q ,
t_o I ˙p(Q-1)
Значения τ₁ 1 подается на вход 16 в моменты времени t=t_xkl, в остальные моменты времени τ₁ 0. Значение t₂ 1 подается на вход 17 в моменты времени t t_o + μ, где μ 0, Р-1. При μ >p τ₂ 0. Значение τ₃=1 подается на вход 18 в моменты времени t t_o + ip + jIP + Q, где i 0, I-1, j 0. τ 1. Значение τ₃ 0 подается в моменты времени t_i3=0 t_o + ip + jIP + Q + V, где i , j , v .

На выходе 28 значения Y_ij формируются в моменты t t_o + iP + jIP + Q + P- 1, где i , j . Период вычисления элементов Y_ij равен IP( τ+Q-1)-P тактов. Время решения N задач двумерной свертки равно N˙I˙P (τ +Q-1)-NP+P+Q тактов.

В каждом блоке обработки 1 производится дублирование выполняемых операций с помощью вычислительных узлов 29 и 30. Результаты выполнения операций, начинающихся по заднему фронту тактового сигнала, формируются на выходе комбинационного сумматора 63 по завершении переходных процессов в комбинационных схемах 62 и 63 и выдаются на выходы 94 вычислительных узлов 29 и 30, откуда эти результаты поступают на соответствующие входы узла сравнения 31. При совпадении информации, поступающей на входы узла сравнения 31 из вычислительных узлов 29 и 30, данный блок обработки 1_j считается исправным и единица с выхода узла сравнения 31 записывается в триггер 32, который используется для фиксации признака исправности данного блока обработки 1_j. С выхода триггера 32 единица поступает на соответствующие входы элементов И 34, 35 и на инверсные входы элементов И 33, в результате этого информация с выходов 92-96 вычислительного узла 29 через элементы И 35 и ИЛИ 36 поступает на выходы 52-56 блока обработки 1_j. Единичный сигнал с выхода триггера 32 поступает также на инверсные входы элементов И 33 и блокирует обход данного блока обработки 1_j. В результате этого значение g, поступающее на вход 42 блока 1_j, выдается на выход 49 блока 1_j. Единичное значение выдается также на выход 50 блока 1_j и соответственно на выход 26_j признака отказа устройства. Единичный сигнал на выходе 26_j устройства указывает средствам внешнего управления об исправности блока 1_j. При несовпадении информации, поступающей на входы узла сравнения 31 из вычислительных узлов 29 и 30, данный блок обработки 1_j считается неисправным, и нулевой сигнал с выхода узла сравнения 31 записывается в триггер 32. С выхода триггера 32 нулевой сигнал поступает на соответствующие входы элементов И 34 и 35 и на инверсные входы элементов И 33, в результате этого выдача с выходов 92-96 вычислительного узла 29 блокируется. Нулевой сигнал с выхода триггера 32 поступает также на инверсные входы элементов И 33, в результате этого поступление информации в вычислительные узлы 29 и 30 через элементы И 34 и выдача информации из узла 29 блокируется и открывается путь обхода данного блока обработки 1_j. В этом случае информация, поступающая из предыдущего блока обработки 1_j-1 через элементы И 33 и ИЛИ 36 выдается соответственно на выходы 52-56 данного блока обработки 1_j. Значение g, поступающее на вход 42 блока 1_j, выдается на выход 51 блока 1_j. Нулевое значение выдается на выход 50 блока 1 и соответственно на выход 26_jпризнака отказа устройства. Нулевой сигнал на выходе 26 устройства указывает средствам внешнего управления об обнаружения отказа блока 1_j.

Для того чтобы в определенных ситуациях принудительно вывести блок 1_j из состава устройства, используется установочный вход 22_j устройства. В этом случае внешними средствами управления на входе 22_j устройства формируется единичный сигнал, который через вход 45 блока обработки 1_jпоступает на вход установки в нуль триггера 32. Для того чтобы принудительно ввести блок обработки 1_j в состав устройства, например, после его принудительного вывода или после фиксирования ложного отказа, используется вход 23_j устройства. В этом случае внешними средствами управления на входе 23_j формируется сигнал, который через вход 46 блока обработки 1_j поступает на вход установки в единицу триггера 32. При этом работа блока обработки 1_j может быть блокирована путем подачи на вход 25_j устройства единичного сигнала. В этом случае единичный сигнал через вход 25_j блока 1 поступает на инверсный вход элемента И 37, который блокирует прохождение тактовых импульсов на тактовые входы вычислительных узлов 28, 30 и триггера 32.

Для установки регистров и триггеров вычислительных узлов 29 и 30 блока 1_j в исходное состояние при запусках и перезапусках устройства используется вход 24_j устройства. Для установки блока 1_j в исходное состояние на вход 24_j устройства подается единичный сигнал, который через вход 44 блока 1_j поступает на входы установки в исходное состояние вычислительных узлов 29 и 30. Вход установки в исходное состояние вычислительных узлов 29 и 30 подключен к входам установки в нулевое состояние всех регистров и триггеров узлов 29 и 30 (на фиг. 3 не показаны).

На вход 19 устройства подается нулевое значение величины g. При наличии исправных блоков 1₁,1_Q с выходов 26₁, 26_Q признака отказа устройства выдаются единичные сигналы, которые поступают на входы соответствующих комбинационных сумматоров 4₁,4_Q. Значение g, поступающее на вход 42 блока 1_i, где 1, Q, в случае исправности блоков 1₁, 1_i-1, равно i-1. В случае исправности блока 1_i данное значение выдается на выход 49 блока 1_i и поступает на соответствующий вход сумматора 4_i, с выхода которого снимается значение g=i, которое записывается в регистр 5_i и поступает на вход узла сравнения 6_i, на другой вход которого поступает значение Q. Таким образом, на каждом такте, в случае исправности блока 1_i, с выхода сумматора 4_i выдается значение g i. При совпадении значений g и Q с выхода соответствующего узла сравнения 6i выдается единичный сигнал, который поступает на соответствующий вход элемента ИЛИ-НЕ 11, с выхода которого нулевой сигнал поступает на один из входов элемента ИЛИ 12. При совпадении результатов, полученных на выходах блоков 2 и 3 суммирования, нулевой сигнал с выхода узла сравнения 7 поступает на соответствующий вход элемента ИЛИ 12. Наличие нулевых сигналов на входах элемента ИЛИ 12 соответствует исправности блоков 2 и 3 и сохранению работоспособности (или исправности) линейки блоков 1 обработки. В этом случае нулевой сигнал с выхода элемента ИЛИ 12 поступает на выход 27 признака отказа устройства. Нулевой сигнал на выходе 27 устройства свидетельствует о сохранении работоспособности устройства на данном шаге.

В случае отказа блока 1_К происходит обход этого блока. При этом в случае исправности предыдущих блоков 1₁, 1_К-1, на выход 42 блока 1_Kпоступает значение g K-1, которое проходит далее на выход 51 данного блока 1_K, с выходов 49 и 50 блока 1_К снимаются нулевые значения и, таким образом, с выхода сумматора 4_К снимается нулевое значение g. В результате этого с выхода узла сравнения 6_К снимается нулевое значение. Если блок 1_Q+1 исправен, то на вход 42 блока 1_Q+1 поступает значение g Q-1, с выхода 49 блока 1_Q+1 выдается единичный сигнал и, следовательно, с выхода комбинационного сумматора 2_Q+1 снимается значение g=Q. В результате с выхода узла сравнения 6_Q+1 снимается единичный сигнал, который поступает на соответствующий вход элемента ИЛИ-НЕ 11, с выхода которого на соответствующий вход элемента ИЛИ 12 выдается нулевой сигнал. Нулевое значение величины g, формируемое сумматором 4_К на последующих тактах, поступает на соответствующие входы элементов ИЛИ 8_Ки в дальнейшем не влияет на формируемую величину g, поступающую на вход 42 блока 1_К+1. Таким образом, блок обработки 1_К выводится из вычислительного процесса путем обхода, а первый из исправных резервных блоков, например 1_Q+1, вводится в процесс вычисления, при этом длина линейки исправно функционирующих блоков обработки 1 устройства сохраняется.

При обнаружении S отказов блоков 1 происходит обход отказавших блоков. Пусть К номер последнего отказавшего блока 1 линейки, тогда с выхода 51 блока 1_К будет выдаваться значение g Q-S, которое поступит на вход 42 блока 1_К+1. Поскольку блок 1_К+1 считается исправным, то с выхода 49 блока 1_К+1 выдается единичный сигнал, с выхода сумматора 4_К+1будет выдаваться значение g Q-S+1, которое поступит на вход 42 блока 1_К+2 и т.д. При попадании значения g на вход 42 исправного блока 1_i на выходе сумматора 4_i формируется величина, равная g+1. При попадании значения g на вход 42 неисправного блока 1_i на выходе сумматора 4_iформируется нулевое значение, а значение g с выхода 51 блока 1_iпоступает на вход 42 следующего блока 1_i+1 линейки. С выхода сумматора 4_Q+S на вход узла сравнения 6_Q+S подается значение g=0, с выхода узла сравнения 6_Q+S выдается единичный сигнал, который поступает на соответствующий вход элемента ИЛИ-НЕ 11. Через открытые элементы И 10 и элементы ИЛИ 9 результат поступает в блоки суммирования 2 и 3. При совпадении результатов на выходах блоков 2 и 3 с инверсного выхода узла сравнения 7 выдается нулевой сигнал, который поступает на вход элемента ИЛИ 12 и, таким образом, с выхода узла сравнения 7 выдается нулевой сигнал, который поступает на вход элемента ИЛИ 12, а с выхода элемента ИЛИ 12 на выход 27 признака отказа устройства выдается нулевой сигнал, который свидетельствует об истинности результата, выдаваемого с выхода блока суммирования 2 на выход результата 28 устройства. При R<S на выходах узлов сравнения 6 будут нулевые значения, с выхода элемента ИЛИ-НЕ 11 будет выдаваться единичное значение, которое поступит на вход элемента ИЛИ 12 и свидетельствует об исчерпании резерва блоков 1. При несовпадении результатов на выходах блоков суммирования 2 и 3 с инверсного выхода узла сравнения 7 будет выдаваться единичное значение, которое поступит на соответствующий вход элемента ИЛИ 12. Следовательно, при R<S или при обнаружении отказа блока суммирования 2(3) с выхода элемента ИЛИ 12 на выход 27 признака отказа устройства будет выдано единичное значение, которое свидетельствует об отказе устройства.

Таким образом, при накоплении R отказов блоков обработки 1 работоспособность устройства сохраняется и длина линейки исправно функционирующих блоков обработки 1 устройства остается постоянной. При обнаружении (R+1)-го отказа или отказа блока суммирования 2(3) с выхода 27 устройства выдается признак отказа устройства, который далее поступает на средства внешнего управления.

При работе устройства незаблокированные резервные блоки обработки 1 автоматически функционируют в режиме контроля дублированием. В этом случае на входы первого блока обработки 1_р, где Р ≥ Q+1, находящегося в резерве, с выхода рабочей линейки устройства поступает вычисленное значение. В результате обработки этого значения в вычислительных узлах 29 и 30 и последующего сравнения результатов в узле 31 резервных блоков обработки 1_р, происходит обновление значений триггеров 32 этих блоков. Дальнейшее использование этих резервных блоков обработки 1_р будет происходить с учетом их исправности.

Рассмотрим работу устройства для конкретного случая I τ P Q 2 и R 1. Организация входного и выходного потоков данных задается выражениями:
t_o 4
t= 4+
t= 4+p-P·q, p , q
t tx_kl
t 4 + μ; μ= 0,1;
t 1 6 + 2i + 4j; i, j 0, 1
t 7 + 2i + 4j, i, j 0, 1.

Организация входного и выходного потоков данных, управляющих сигналов, содержимое триггеров и регистров, значения, формируемые на выходе комбинационного сумматора блоков обработки 1₁ и 1₂, приведены в табл. 1 и 2. В табл. 3 описывается работа блоков суммирования 2(3) для рассматриваемого случая.

Пусть на 8-м такте работы устройства обнаружен отказ блока обработки 1₂. В этом случае организация входного и выходного потоков данных, управляющих сигналов, содержимое регистров и триггеров и значения формируемых на выходе комбинационных сумматоров блоков обработки 1₁, 1₂ и 1₃, приведены в табл. 4-6.

На также t 8 обнаружен отказ блока 1₂, на такте t 9 происходит блокировка блока 1₂ (в дальнейшем информация, находящаяся в его узлах, не влияет на дальнейший процесс обработки) и обнуление блока 1₁, на такте t 10 производится перезапуск устройства (на входы блока 1₁начата подача соответствующих значений). С такта t 9 производится обход блока 1₂ и включения в работу резервного блока 1₃. Длина линейки устройства остается прежней.

Возможный алгоритм восстановления процесса после обнаружения отказа блока 1_j предусматривает следующую последовательность действий:
такт i: фиксирование блока 1_j с обнаруженным отказом, блокировка блока 1_j, чтение информации с блока 1_j+1 в блок 1_j+2, обнуление блока 1_j+1 и блокировка блока 1_j+1.

такт i+1: чтение информации с блока 1_j+2 в блок 1_j+3, блокировка и обнуление блока 1_j+2, обнуление блоков 1₁,1_j-1.

такт i+2: чтение информации с блока 1_j+3 в блок 1_j+4, блокировка и обнуление блока 1_j+3, разблокировка блока 1_j+1.

такт i+3: чтение информации с блока 1_j+4 в блок 1_j+5, блокировка и обнуление блока 1_j+4, разблокировка блока 1_j+2.

такт i+K: чтение информации с блока 1_j+k+1 в блок 1_j+k+2, блокировка и обнуление блока 1_j+k-1.

Если t_n время (число тактов), требуемое для подготовки к перезапуску устройства со стороны средств внешнего управления, то время реинициализации линейки составит j + t_n тактов.

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

В силу технологической структуры кристалла ИС состояния исправности или неисправности его различных долей взаимосвязаны. Степень связи между отказами различных долей ИС измеряется коэффициентом корреляции, величина которого тем больше, чем выше уровень технологии и степень интеграции ИС. Наличие не менее чем 16-разрядных умножителя 62 комбинационного типа, сумматоров 63 и 99 комбинационного типа и групп регистров 57-60, регистров 61, 97 и 98 обуславливают степень интеграции и уровень технологии, достаточные для проявления высокой степени корреляции отказов. При контроле дублирования вычислительных узлов необходимо, чтобы отказы этих узлов были независимы. Для этого нужно, чтобы узлы 29 и 30 блока обработки 1, а также блоки суммирования 2 и 3 были реализованы на разных кристаллах ИС. Аналогично, исходя из соображений корреляции отказов внутри кристалла ИС, необходимо, чтобы избыточные (резервные) блоки обработки 1 не размещались на одних кристаллах ИС вместе с рабочими.

Технико-экономический эффект предлагаемого устройства заключается в следующем.

В предлагаемом устройстве осуществляется непрерывный аппаратный контроль на протяжении всего времени работы и блокировки выдачи ошибочной информации при обнаружении отказавшего блока обработки. В устройстве реализован наиболее полный аппаратный контроль, ориентированный на обнаружение всех видов отказов, при этом время контроля сравнимо с тактовым периодом. Достоверность функционирования блока обработки систолического устройства будет определяться как: D_cp(t) P_пр(t) + P_0,0(t), где Р_пр(t) вероятность правильной работы блока обработки 1,
Р_0,0(t) вероятность правильной работы блока обработки 1 и выдача с выхода 50 блока 1 сигнала отказа.

Для рассматриваемого систолического устройства
Р_пр(t) Р_у3²(t),
P_0,0(t) 2Р_у3(t)(1-Р_у3(t)), где Р_у3(t) вероятность безоткатной работы вычислительного узла 29 и 30.

Достоверность функционирования всего устройства определяется выражением:
D_ср (2Р_у3(t) Р_у3²(t))^Q. При Р_уз(t) 0,99, Q 3 D_ср 0,996,
Р_уз(t) 0,99, Q 10 D_cр 0,9891,
Р_уз(t) 0,999, Q 3 D_ср 0,999997,
Р_уз(t) 0,999, Q 10 D_ср 0,999989,
Р_уз(t) 0,9999 и выше D_ср практически равна 1.

Время восстановления вычислительного процесса (получение достоверности результата на выходе устройства) пропорционально значению n_отк, где n_отк ≅Q, n_отк минимальный номер среди номеров отказавших блоков обработки линейки устройства.

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных системах для вычисления двумерной свертки. Цель изобретения сокращение аппаратурных затрат, повышение надежности за счет организации контроля и резервирования и расширение функциональных возможностей за счет решения задач различных размерностей. Поставленная цель достигается тем, что конвейерное устройство для обработки информации содержит L блоков обработки, где L Q + R, Q - порядок решаемой задачи, R число резервных блоков, два блока суммирования, L сумматоров, L 1 регистров, группу из L узлов сравнения, узел сравнения, L групп элементов ИЛИ, L групп элементов И, элемент ИЛИ НЕ и элемент ИЛИ. 2 з. п. ф-лы, 3 ил. 6 табл.

1. УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДВУМЕРНОЙ СВЕРТКИ, содержащее с первого по Q-й блоки обработки, каждый из которых содержит первый вычислительный узел, причем информационные входы первой и второй групп, первый и второй управляющие входы устройства подключены соответственно к информационным входам первой и второй групп, первому и второму управляющим входам первого блока обработки, выходы первой и второй групп, первый и второй выходы i-го блока обработки (где i=1, Q 1) подключены соответственно к информационным входам первой и второй групп, первому и второму управляющим входам (i + 1)-го блока обработки, вход тактовых импульсов устройства подключен к тактовым входам блоков обработки с первого по Q-й, отличающееся тем, что в него введены с (Q + 1)-го по L-й блоки обработки, где L Q + R, R число резервных блоков обработки, первый и второй блоки суммирования, L сумматоров, L 1 регистров, группу из L узлов сравнения, узел сравнения, с первой по (L + 1)-ю группы элементов ИЛИ, L групп элементов И, элемент ИЛИ НЕ и элемент ИЛИ, причем выходы первой и второй групп, первый и второй выходы j-го блока обработки (где j Q, L 1) подключены соответственно к информационным входам первой и второй групп, первому и второму управляющим входам (j + 1)-го блока обработки, вход тактовых импульсов устройства подключен к тактовым входам блоков суммирования, блоков обработки с (Q + 1)-го по L-й и входам записи-считывания регистров, информационные входы третьей группы устройства подключены соответственно к информационным входам третьей группы первого блока обработки, выходы третьей группы K-го блока обработки (где K=1, L 1) подключены соответственно к первым входам элементов И K-й группы и соответственно к управляющим входам первой группы (K + 1)-го блока обработки, выходы третьей группы L-го блока обработки подключены соответственно к первым входам элементов И L-й группы, управляющие входы первой группы устройства подключены соответственно к управляющим входам первой группы первого блока обработки, выходы четвертой группы K-го блока обработки подключены соответственно к первым входам элементов ИЛИ K-й группы, выходы которых подключены соответственно к управляющим входам первой группы (K + 1)-го блока обработки, выходы пятой группы l-го блока обработки (где l=1, L) подключены соответственно к информационным входам группы l-го комбинационного сумматора, выходы K-го комбинационного сумматора подключены соответственно к информационным блокам K-го регистра и соответственно к входам первой группы K-го узла сравнения, выходы L-го комбинационного сумматора, выходы K-го комбинационного сумматора подключены соответственно к входам первой группы L-го узла сравнения группы, управляющие входы второй группы устройства подключены к управляющим входам вторых групп блоков обработки с первого по L-й и входам вторых групп узлов сравнения групп, выход l-го узла сравнения группы подключен к вторым входам элементов И l-й группы и l-му входу элемента ИЛИ НЕ, выход которого подключен к первому входу элемента ИЛИ, выход которого подключен к выходу признака отказа устройства, выходы K-го регистра подключены соответственно к вторым входам элементов ИЛИ K-й группы, третий выход l-го блока обработки подключен к информационному входу l-го сумматора и l-му выходу группы признака отказа устройства, третий управляющий вход которого подключен к управляющим входам блоков суммирования, выходы элементов И групп с первой по L-ю подключены соответственно к входам элементов ИЛИ L-й группы, выходы которых подключены к информационным входам блоков суммирования, выходы первого блока суммирования подключены к выходам результата устройства и входам первой группы (L + 1)-го узла сравнения, инверсный выход которого подключен к второму входу элемента ИЛИ, выходы второго блока суммирования подключены соответственно к входам второй группы (L + 1)-го узла сравнения, l-й вход установки первой группы, l-й вход установки второй группы, l-й вход установки третьей группы и l-й вход блокировки устройства подключены соответственно к первому, второму, третьему входам установки и входу блокировки l-го блока обработки, при этом каждый блок обработки содержит дополнительно второй вычислительный узел, узел сравнения, триггер, с первого по третий узлы элементов И, узел элементов ИЛИ и элемент И, причем в каждом блоке обработки информационные входы первой, второй и третьей групп, первый и второй управляяющие входы и управляющие выходы первой группы блока подключены соответственно к входам группы первого узла элементов И и входам второго узла элементов И, выходы первой группы первого узла элементов И подключены соответственно к входам первой группы узла элементов ИЛИ, выходы которого подключены соответственно к выходам первой группы, второй группы, третьей группы, первому и второму выходам блока, выходы первой группы второго узла элементов И подключены к информационным входам первой группы, второй группы, третьей группы, первому и второму управляющим входам первого и второго вычислительных узлов, выходы первой, второй и третьей групп, первый и второй выходы первого вычислительного узла подключены к входам первой группы узла сравнения и входам группы третьего узла элементов И, выходы которого подключены соответственно к входам второй группы узла элементов ИЛИ, выходы первой, второй и третьей групп, первый и второй выходы второго вычислительного узла подключены соответственно к входам второй группы узла сравнения, выход которого подключен к информационному входу триггера, выход которого подключен к входу третьего узла элементов И, третьему выходу блока обработки, инверсному входу первого узла элементов И и входу второго узла элементов И, выходы вторых групп первого и второго узлов И подключены соответственно к выходам четвертой и пятой групп, управляющие входы второй группы блока обработки подключены соответственно к управляющим входам группы первого вычислительного узла и управляющим входам группы второго вычислительного узла, первый и второй входы установки блока обработки подключены соответственно к входам установки в "0" и "1" триггера, третий вход установки блока обработки подключен к входам установки в исходное состояние первого и второго вычислительных узлов, тактовый вход и вход блокировки блока обработки подключены соответственно к первому и второму (инверсному) входам элемента И, выход которого подключен к тактовым входам первого и второго вычислительных узлов и триггера. 2. Устройство по п.1, отличающееся тем, что каждый блок суммирования содержит два регистра и комбинационный сумматор, причем тактовый вход блока суммирования подключен к входам записи-считывания первого и второго регистров, выходы которых подключены соответственно к информационным входам сумматора, выходы которого подключены к выходам блока суммирования и информационным входам второго регистра, информационные входы и управляющий вход блока суммирования подключены соответственно к информационным входам первого регистра и установки в "0" второго регистра. 3. Устройство по п.1, отличающееся тем, что каждый вычислительный узел содержит четыре группы регистров, регистр, умножитель и сумматор, группу триггеров, триггер, M + 3P + 7 групп элементов И, где M=IP + 1, шесть групп элементов ИЛИ, элемент И, элемент ИЛИ и два дешифратора, причем информационные входы первой группы вычислительного узла подключены к информационным входам первого регистра первой группы и первым входам элементов И первой группы, выходы которых подключены к первым входам элементов ИЛИ первой группы, выходы которых подключены к информационным входам первого регистра второй группы, выходы m-го регистра первой группы (где m=1, M-1) подключены к информационным входам (m+1)-го регистра первой группы и первым входам элементов И (m+1)-й группы, выходы элементов И групп с второй по (M+1)-ю подключены к соответствующим входам элементов ИЛИ второй группы, выходы которых подключены к выходам первой группы вычислительного узла, информационные входы второй группы которого подключены к информационным входам первого регистра третьей группы и первым входам элементов И (M + 2)-й группы, выходы которых подключены к первым входам элементов ИЛИ третьей группы, выходы которых подключены к информационным входам первого регистра четвертой группы, выходы первого регистра второй группы подключены к информационным входам первой группы умножителя, первым входам элементов И (M + 3)-й группы и информационным входам второго регистра второй группы, выходы n-го регистра второй группы (где n 2, P) подключены к информационным входам (n+1)-го регистра второй группы и первым входам элементов И (M + 2 +n)-й группы, выходы элементов И групп с (M+3)-й по (M + 3+ P)-ю поддключены к соответствующим входам элементов ИЛИ четвертой группы, выходы которых подключены к первым входам элементов И (M+P+4)-й группы, выходы которых подключены соответственно к вторым входам элементов ИЛИ первой группы, выходы S-го регистра третьей группы (где S= 1, P) подключены к информационным входам (S + 1)-го регистра и первым входам элементов И (M + P + 4 + S)-й группы, выходы (P + 1)-го регистра третьей группы подключены к первым входам элементов И (M+2P+5)-й группы, выходы элементов И групп с (M+P+5)-й по (M+2P+5)-ю подключены к соответствующим входам элементов ИЛИ пятой группы, выходы которых подключены соответственно к выходам второй группы вычислительного узла, выходы первого регистра четвертой группы подключены к первым входам элементов И (M+2P+6)-й группы, информационным входам второго регистра четвертой группы и информационным входам второй группы умножителя, выходы которого подключены соответственно к информационным входам первой группы сумматора, выходы которого подключены соответственно к выходам третьей группы вычислительного узла, информационные входы третьей группы которого подключены соответственно к информационным входам регистра, выходы которого подключены соответственно к информационным входам второй группы сумматора, выходы r-го регистра четвертой группы (где r= 2, P) подключены к информационным входам (r + 1)-го регистра четвертой группы и первым входам элементов И (M + 2P + 6 + r)-й группы, выходы элементов И групп с (M + 2P + 7)-й по (M + 3P + 7)-ю подключены к соответствующим входам элементов ИЛИ шестой группы, выходы которых подключены соответственно к первым входам элементов И (M + 3P + 8)-й группы, выходы которых подключены соответственно к вторым входам элементов ИЛИ третьей группы, первый управляющий вход устройства подключен к вторым входам элементов И первой группы, вторым (инверсным) входам элементов И (M + P + 4)-й группы и информационному входу первого триггера группы, выход V-го триггера группы (где V=1, М-1) подключен к информационному входу (V + 1)-го триггера группы и первому входу V-го элемента И, выходы элементов И с первого по M-й подключены соответственно к входам элемента ИЛИ, выход которого подключен соответственно к входам элемента ИЛИ, выход которого подключен к первому выходу вычислительного узла, второй управляющий вход которого подключен к вторым входам элементов И (M+2)-й группы, вторым (инверсным) входам элементов И (M + 3P + 8)-й группы и информационному входу триггера, выход которого подключен к второму выходу вычислительного узла, управляющие входы группы с первого по a-й (где a=log₂ M) которого подключены соответственно к входам первого дешифратора, i-й выход которого (где i=1, М) подключен к вторым входам элементов И (i + 1)-й группы и второму входу i-го элемента И, управляющие входы группы с (a+1)-го по H-й [где H a log₂(P + 1] вычислительного узла подключены к входам второго дешифратора, j-й выход которого (где j= 1, P + 1) подключен к вторым входам элементов И (M + P + 4 + j)-й группы, (M + 2 + j)-й группы м (M + 2P + 6 + j)-й группы, тактовый вход вычислительного узла подключен к тактовым входам регистров и триггеров, вход установки в исходное состояние вычислительного узла подключен к входам установки в "0" всех регистров и триггеров.