Устройство для вычисления двумерной свертки

 

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

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

Известно устройство, содержащее P x Q операционных блоков, где P x Q - размер окна двумерной свертки, каждый из которых содержит регистр весового коэффициента ω_pq, где P = 1, ..., P, q = 1, ...., Q - сумматор, умножитель и регистр сдвига [1].

Наиболее близким по технической сущности к предлагаемому изобретению является устройство, содержащее матрицу {i, j, K} блоков обработки, каждый из которых содержит регистры, умножитель и сумматор [2].

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

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

Поставленная цель достигается тем, что в устройство, содержащее I блоков обработки 1, где I - размерность решаемой задачи, причем тактовый вход 17 устройства подключен к тактовым входам блоков обработки с первого по I-й, информационные входы первой 8 и второй 9 групп устройства подключены соответственно к информационным входам первой и второй групп первого блока обработки I_о, выходы первой и второй групп i-го блока обработки (i = 1, ..., I-1) подключены соответственно к информационным входам первой и второй групп (i + 1)-го блока обработки, введены с (I +1)-го по L-й блоки обработки, где L = I + R, R - число резервных блоков обработки, L комбинационных сумматоров 2, (L - 1) регистр 3, L узлов сравнения 4, (L - 1) группа элементов ИЛИ 5, L групп элементов И 6 и элемент ИЛИ-НЕ 7, причем первый, второй и третий управляющие входы 10 - 12 устройства подключены соответственно к первому, второму и третьему управляющим входам первого блока обработки, первый, второй и третий выходы i-го блока обработки (где i = 1, ..., I - 1) подключены соответственно к первому, второму и третьему управляющим входам (I + 1)-го блока обработки, тактовый вход 17 устройства подключен к тактовым входам блоков обработки с (I + 1)-го по L-й и тактовым входам регистров 3 с первого по (L - 1)-й, выходы первой и второй групп, первый, второй и третий выходы j-го блока обработки (где j = 1, ..., L - 1) подключены соответственно к информационным входам первой и второй групп, к первому, второму и третьему управляющим входам (j + 1)-го блока обработки, четвертый и пятый управляющие входы 13 и 14 устройства подключены соответственно к четвертым и пятым входам блоков обработки с первого по L-й, управляющие входы первой группы 16 устройства подключены соответственно к управляющим входам первых групп блоков обработки с первого по L-й и соответственно ко входам первых групп узлов сравнения и с первого по L-й, выходы которого подключены соответственно ко входам элемента ИЛИ-НЕ 7, выход которого подключен к выходу 25 признака отказа устройства, управляющие входы второй группы 15 которого подключены соответственно к управляющим входам второй группы первого блока обработки, входы третьей группы K-го блока обработки (где K = I, ...., L) подключены соответственно к информационным входам группы K-го комбинационного сумматора 2, выходы n-го комбинационного сумматора 2 (где n = I, ..., L - 1) подключены соответственно к информационным входам n-го регистра 3 и соответственно ко входам второй группы n-го узла сравнения 4, выходы n-го регистра 3 подключены соответственно к первым входам элементов ИЛИ 5 n-й группы, выходы четвертой группы K-го блока обработки подключены соответственно к первым входам элементов И 6 K-й группы, выходы которых подключены соответственно к выходам 22 K-й группы результата устройства, выходы пятой группы n-го блока обработки подключены соответственно ко вторым входам элементов ИЛИ n-й группы, выходы которого подключены соответственно к управляющим входам второй группы (n + 1)-го блока обработки и соответственно к выходам 23 (L + n)-й группы результата устройства, выходы L-го сумматора подключены соответственно ко входам второй группы L-го узла сравнения и соответственно к выходам 23 результата L-й группы устройства, четвертый выход K-го блока обработки подключен к информационному входу K-го сумматора, вторым входам элементов И 6 K-й группы и K-му выходу 24 признака отказа группы устройства, K-й вход установки первой группы 18, K-й вход установки второй группы 19, K-й вход установки третьей группы 20 и K-й вход блокировки 21 устройства подключены соответственно к первому, второму, третьему входам установки и входу блокировки K-го блока обработки. Каждый блок обработки 1 содержит первый и второй вычислительные узлы 26 и 27, узел сравнения 28, триггер 29, с первого по третий узлы 30 - 32 элементов И, узел элементов ИЛИ 33 и элемент И 34, причем управляющие входы первой группы 43 блока обработки подключены соответственно к управляющим входам групп первого и второго вычислительных узлов, информационные входы первой и второй групп 35 и 36, с первого по пятый управляющие входы 37 - 41 и управляющие входы второй группы блока обработки подключены соответственно ко входам группы первого узла 30 элементов И и соответственно ко входам группы второго узла 31 элементов И, выходы первой группы первого узла элементов И подключены соответственно ко входам первой группы узла 33 элементов ИЛИ, выходы которого подключены соответственно к выходам первой 52, второй 53, четвертой 54 групп, к первому 55, второму 56 и третьему 57 выходам блока обработки, выходы первой группы второго узла 31 элементов И подключены соответственно к информационным входам первой и второй групп и к управляющим входам с первой по пятый первого 26 и второго 27 вычислительных узлов, выходы первой, второй и третьей групп, первый, второй и третий выходы первого вычислительного узла подключены соответственно ко входам первой группы узла сравнения 28 и ко входам группы третьего узла 32 элементов И, выходы которого подключены соответственно ко входам второй группы узла 33 элементов ИЛИ, выходы первой, второй и третьей групп, первый, второй и третий выходы второго вычислительного узла 27 подключены соответственно ко входам второй группы узла сравнения 28, выход которого подключен к информационному входу триггера 29, выход которого подключен к входу третьего узла 32 элементов И, инверсному входу первого узла, входу второго узла 31 элементов И и четвертому выходу 50 блока обработки, выходы вторых групп первого 30 и второго 31 узлов элементов И подключены соответственно к выходам пятой 51 и третьей 49 групп блока обработки, первый вход установки 46 которого подключен ко входам установки в исходное состояние первого и второго вычислительных узлов, второй и третий входы установки 47 и 48, тактовый вход 45 и вход блокировки 44 блока обработки подключены соответственно к входу установки в нуль триггера 29, входу установки в единицу триггера 29, первому и второму (инверсному) входам элемента И 34, выход которого подключен к тактовым входам первого и второго вычислительных узлов 26 и 27 и входу синхронизации триггера 29.

Каждый вычислительный узел 26 (27) содержит с первой по четвертую группы регистров 58, 59, 61, 63, первый и второй регистры 60 и 62, умножитель 64 и сумматор 65, группу триггеров 66, с первого по четвертый триггеры 67 - 70, (2M + 2N + 5) групп элементов И 71, ..., 78, 79₁, ..., 79_M, 80₁, ..., 80_N, . . . , 81₁ . .., 81_N-1, 82₁, ..., 82_M-2, (где M = (Q + 1)J + 1, N = Q + 2), восемь групп элементов ИЛИ 84, ...., 91, первый и второй дешифраторы 93 и 94, M элементов И 83 и элемент ИЛИ 92, причем информационные входы первой группы 95 узла подключены к информационным входам первого регистра 58₁ первой группы и первым входам элементов И 71 первой группы, выходы которых подключены, соответственно к первым входам элементом ИЛИ 84 первой группы, выходы которых подключены к информационным входам первого регистра 59₁ второй группы, выходы а-го регистра первой группы 58 (где а = I, ...., M - I) подключены к информационным входам (a + I)-го регистра 58 первой группы и первым входам элементов И 79_a (a + 1)-й группы выходы M-го регистра первой группы 58_M подключены к первым входам элементов И 79_M (M + 1)-й группы, выходы элементов И 79 групп с второй по (M + 1)-ю подключены соответственно ко входам элементов ИЛИ 88 второй группы, выходы которых подключены к выходам первой группы вычислительного узла, выходы первого регистра 59_I подключены к первым входам элементов И 80_I (M + 2)-й группы, информационным входам второго регистра 59₂ второй группы и информационным входам первой группы умножителя 64, выходы б-го регистра второй группы 59_б (где б = 2, ..., N - I) подключены к информационным входам (б + 1)-го регистра 59 второй группы и первым входам элементов И 80_б (M + 1 + б)-й группы, выходы N-го регистра 59_N второй группы подключены к первым входам элементов И 80_N (M + N + 1)-й группы, выходы элементов И групп (M + 2)-й по (M + N + 1)-ю подключены соответственно ко входам элементов ИЛИ 89 третьей группы, выходы которых подключены соответственно к первым входам элементов И 72 (M + N + 2)-й группы, выходы которых подключены соответственно ко вторым входам элементов ИЛИ первой группы, выходы умножителя 64 подключены соответственно к первым входам элементов И 73 (M + N + 3)-й группы, выходы которых подключены к первым входам элементов ИЛИ 85 четвертой группы, выходы которых подключены к информационным входам первой группы сумматора 65, выходы которого подключены к первым входам элементов И 77 (M + N + 4)-й группы и информационным входам первого регистра 62, выходы которого подключены соответственно к информационным входам второй группы сумматора, информационные входы второй группы 96 подключены к информационным входам второго регистра 60 и к первым входам элементов И 74 (M + N + 5)-й группы, выходы которых подключены к первым входам элементов ИЛИ 86 пятой группы, выходы которых подключены к информационным входам первого регистра 61, третьей группы, выходы которого подключены к информационным входам второй группы умножителя, информационным входам второго регистра 61₂ третьей группы и первым входам элементов И 81₁ (M + N + 6)-й группы, выходы в-го регистра 61 третьей группы (где b = 2, ..., N - 2) подключены к информационным входам (b + 1)-го регистра 61 третьей группы и первым входам элементом И 81_b (M + N + 5 + b)-й группы, выходы (N - 1)-го регистра 61 третьей группы подключены к первым входам элементов И 81_N-1 (M + 2N + 4)-й группы, выходы элементов И 81 групп с (M + N + 6)-й по (M + 2N + 4)-ю подключены к соответствующим входам элементов ИЛИ 90 шестой группы, выходы которых подключены соответственно к первым входам элементов И 75 (M + 2N + 5)-й группы, выходы которых подключены соответственно ко вторым входам элементов ИЛИ 86 пятой группы, выходы второго регистра 60 подключены к выходам второй группы вычислительного узла, выходы первого регистра 63₁ четвертой группы подключены к первым входам элементов И (M + 2N + 6)-й группы 76 и элементов И (M + 2N + 7)-й группы 78, выходы которых подключены соответственно ко вторым входам элементов ИЛИ 85 четвертой группы и первым входам элементов ИЛИ 87 седьмой группы, выходы которых подключены к информационным входам второго регистра 63₂ четвертой группы, выходы которого подключены к выходам третьей группы 107 вычислительного модуля, информационным входам третьего регистра 63₃ четвертой группы и первым входам элементов И 82₁ (M + 2N + 8)-й группы, выходы С-го регистра 63_c четвертой группы (где C = 3, ..., M - 2) подключены соответственно к информационным входам (C + 1)-го регистра четвертой группы и первым входам элементов И 82_c-1 (N + 2M + 6 + C)-й группы, выходы (M - 1)-го регистра 63_M-1 четвертой группы подключены соответственно к первым входам элементов И 82_M-2 (2N + 2M + 4)-й группы, выходы элементов И 82 групп с (2N + M + 8)-й по (2N + 2M + 4)-й подключены к соответствующим входам элементов ИЛИ 91 восьмой группы, выходы которых подключены к информационным входам первого регистра 63₁ четвертой группы, первый управляющий вход 97 подключен ко вторым входам элементов И первой группы, вторым (инверсным) входам элементов И (M + N + 2)-й группы и информационному входу первого триггера 66₁ группы, выход d-го триггера 83_d группы (где d = 1, ..., M - 1) подключен к первому входу d-го элемента И 83_d и информационному входу (d + 1)-го триггера, выход M-го триггера группы подключен к первому входу M-го элемента И 83_M, выходы элементов И 83 с первого по M-й подключены соответственно ко входам элемента ИЛИ 92, выход которого подключен к первому выходу вычислительного узла, второй управляющий вход 98 которого подключен ко вторым входам элементов И 74 (M + N + 5)-й группы, вторым (инверсным) входом элементом И 75 (M + 2N +5)-й группы и информационному входу первого триггера 67, выход которого подключен ко второму выходу вычислительного узла, третий управляющий вход которого подключен к первому входу установки в нуль первого регистра четвертой группы и информационному входу второго триггера, выход которого подключен к третьему выходу вычислительного узла, четвертый управляющий вход 100 которого подключен к информационному входу третьего триггера 68, выход которого подключен к первому входу установки в нуль первого регистра, пятый управляющий вход 101 вычислительного узла подключен к информационному входу четвертого триггера 69, выход которого подключен ко вторым входам элементов И (M + 2N +6)-й группы элементов И (M + N + 4)-й группы, вторым (инверсным) входом элементов И (M + N + 3)-й группы и элементов И (M + 2N + 7)-й группы, управляющие входы с первого по r-й 102₁ и с (r + 1)-го по V-й 102₂ группы вычислительного узла (где r-log₂ M, V-r=log₂N) подключены соответственно ко входам первого и второго дешифраторов, f-й выход первого дешифратора 93 (где f = 1, ..., M) подключен ко вторым входам элементов И (f + 1)-й группы, элементов И (2N + M + 5 + h)-й группы (где h = 3, ..., M) и f-го элемента И, p-й выход второго дешифратора 94 (где p = 1, . . ., N) подключен ко вторым входам элементов И (M + 1 + q)-й группы и элементов И (M + N + 4 + q)-й группы (где q = 2, ..., N), тактовый вход 104 вычислительного модуля подключен ко входам записи/считывания регистров групп с первой по четвертую, первого и второго регистров, входам синхронизации триггеров группы и триггеров с первого по четвертый, вход 103 установки в исходное состояние вычислительного узла подключен ко входам установки в нуль всех триггеров, второго регистра, регистров групп с первой по третью, регистров со второго по (M -1)-й четвертой группы и вторым входам установки в нуль первого регистра и первого регистра четвертой группы.

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

Устройство для конвейерной обработки информации содержит L блоков обработки 1, где L = I + R, I - число основных блоков обработки, R - число резервных блоков обработки, L комбинационных сумматоров 2, (L - 1) регистр 3, L узлов сравнения 4, (L - 1) группу элементов ИЛИ 5, L групп элементов И 6, элемент ИЛИ-НЕ 7, информационные входы 8 и 9, управляющие входы 10 - 16, тактовый вход 17, входы установки 18 - 20, входы блокировки 21, выходы 22 первой группы результата, выходы 23 второй группы результата, выходы 24 группы признака отказа и выход 25 признака отказа устройства. Каждый блок обработки 1 содержит вычислительные узлы 26 и 27, узел сравнения 28, триггер 29, узлы элементов И 30 - 32, узел элементов ИЛИ 33, элемент И 34, информационные входы 35 и 36, управляющие входы 37 - 43, вход блокировки 44, тактовый вход 45, входы установки 46 - 48, выходы 49 - 57. Каждый вычислительный узел 26 (27) содержит регистры 58 - 63, комбинационный умножитель 64, комбинационный сумматор 65, триггеры 66 - 70, группы элементов И 71 - 82, элементы И 83, группы элементов ИЛИ 84 - 91, элемент ИЛИ 92, дешифраторы 93 и 94, информационные входы 95 и 96, управляющие входы 97 - 102, вход 103 начальной установки, тактовый вход 104 и выходы 105 - 110.

В основу работы устройства положен алгоритм вычисления двумерной свертки который состоит из двух частей: Первая часть алгоритма - вычисление вторая часть - вычисление .

При описании работы устройства в обозначении x^(k_ij⁾ индекс (K) в скобках указывает номер такта работы устройства, а индекс K без скобок - номер рекуррентного шага.

Вычислительный узел 26 (27) обладает возможностью реализации следующих функций: где xⁱ и ωⁱ - значения соответственно на входах 95 и 96 вычислительного узла на i-м такте, < Рег 62 >ⁱ - содержимое регистра 62 на i-м такте, τⁱ₁,τⁱ₂,τⁱ₃,τⁱ₄,τⁱ₅ - значения соответственно на управляющих входах 97 - 101 вычислительного узла на i-м такте, xⁱ, Ωⁱ и Yⁱ - значения соответственно на выходах 105, 106 и 107 вычислительного узла на i -м такте, Tⁱ₁,Tⁱ₂ и Tⁱ_3/ - значения соответственно на выходах 108, 109 и 110 вычислительного узла на i-м такте.

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

На информационные входы 95 и 96 подаются соответственно значения X_кl и ω_pq. Режим работы вычислительного узла задается управляющими сигналами τ₁,...,τ₅, которые подаются соответственно на входы 97 - 101.

При τ₁ = 1 входное значение X_кe записывается в регистры 58 и 59 (элементы И 71 открыты) и выдается на выход 105 с задержкой на (Q + 1)J + 1, тактов.

При τ₂ = 1 входное значение ω_pq записывается в регистры 60 и 61 (элементы И 74 открыты) и выдается на выход 106 с задержкой на один такт. При τ₂ = 0 значение ω_pq, записанное в регистре 61_Q+1, переписывается в регистр 61₁ (элементы И 75 открыты).

При τ₃ = 1 регистр 63₁ устанавливается в нулевое состояние.

При τ₄ = 1 регистр 62 устанавливается в нулевое состояние.

При τ₅ = 1 содержимое регистра 63₁ через открытые элементы И 76 подается на соответствующий информационный вход комбинационного сумматора 65, с выхода которого через открытые элементы И 77 записывается в регистр 63₂. При τ₅ = 0 значение X - ω с выхода комбинационного умножителя 64 через открытые элементы И 73 подается на соответствующий информационный вход комбинационного сумматора 65, с выхода которого результирующее значение Y_ij через элементы И 77 записываются в регистр 63₂ и выдаются на выход 107 вычислительного узла. Значение размерности M ≅ (Q+1)I+1 и N ≅ Q + 2, используемое для вычисления свертки на данном устройстве подаются через входы 16 устройства, входы 43 блоков обработки 1 и выходы 102₁ и 102₂ вычислительных узлов соответственно на входы дешифраторов 93 и 94. При дешифрации значения M, с соответствующего выхода дешифратора 93, выдается единичное значение α_M, которое открывает соответствующие элементы И 79, 82 и 83, с выходов которых информация поступает соответственно на входы элементов ИЛИ 88, 91 и 92. При дешифрации значения N, с соответствующего выхода дешифратора 94 выдается единичное значение β_N, которое открывает соответствующие элементы И 80 и 81, с выходов которых информация поступает на входы элементов ИЛИ 89 и 90. Таким образом, в устройстве реализуются возможности решения задач двумерной свертки различной размерности (для различных значений Z и Q).

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

Значения X_кl подаются в моменты времени
= t_o + max{O; l}(Q+1)+min{0;(-1)}-K(Q+1)J,
где K =-(P-1), (I-1), l= -(Q-1),(J-1),
t_o =(I-1)(Q+1)J.

Значения ω_pq подаются в моменты времени
tω_pq = t_o+p(Q+1)J+q,
где
Управляющий сигнал τ₁= 1 подается в моменты времени , в остальные моменты τ₁= 0.
Управляющий сигнал τ₂= 1 подается в моменты времени , в остальные моменты τ₂= 0
Управляющий сигнал τ₃= 1 подается в моменты времени

где , в остальные моменты τ₃= 0.
Управляющий сигнал τ₄= 1 подается в i-й блок обработки 1_i в моменты

где в остальные моменты τ₄= 0.
Управляющий сигнал τ₅= 1 подается i-й блок обработки в моменты времени

где j =
в остальные моменты времени τ₅= 0.
Элементы Y_ij формируются в i -м блоке обработки 1_i в моменты времени

Последний элемент y_IZ формируется в момент времени

Период подачи элементов X_кl очередной задачи двумерной свертки равен
T = J(Q+1)(P+I-1)-Q+1
тактов.

В каждом блоке обработки 1 производятся дублирование выполняемых операций с помощью вычислительных узлов 26 и 27. Результаты выполнения операций формируются на выходе комбинационного сумматора 65 по завершению переходных процессов в комбинационных схемах 64 и 65 и через элементы И 77, ИЛИ 87 с выхода регистра 63₂ выдаются на выходы 107 вычислительных узлов 26 (27), откуда эти результаты поступают соответственно на информационные входы узла сравнения 28. При совпадении информации, поступающей на информационные входы узла сравнения 28 из вычислительных узлов 26 и 27, данный блок обработки 1_j считается исправным и единица с выхода узла сравнения 28 записывается в триггер 29, который используется для фиксации признака исправности данного блока обработки 1_j. С выхода триггера 29 единица поступает на соответствующие входы элементов И 31 и 32 и информация с выходов 105 - 110 вычислительного узла 26 через элементы И 32 и ИЛИ 33 поступает на выходы 52 - 57 блока обработки 1_j.

Единичный сигнал с выхода триггера 29 поступает также на инверсный вход элементов И 30 блокирует обход данного блока обработки 1_j. В результате этого значения g, поступающее на вход 42 блока 1_j выдается на выход 49 блока 1_j. Единичное значение выдается также на выход 50 блока 1_j и, соответственно, на выход 24 признака отказа устройства. Единичный сигнал на выходе 24_j устройства указывает средствам внешнего управления об исправности блока 1_j. При несовпадении информации, поступающей на информационные входы узла сравнения 28 из вычислительных узлов 26 и 27, данный блок обработки 1_j считается неисправным и нулевой сигнал с выхода узла сравнения 28 записывается в триггер 29. С выхода триггера 29 нулевой сигнал поступает на соответствующие входы элементов И 31 и 32 и выдача информации с выходов 105-110 вычислительного узла 26 блокируется. Нулевой сигнал с выхода триггера 29 поступает также на инверсные входы элементов И 30. В результате этого, поступление информации в вычислительные узлы 26 и 27 через элементы И 31 блокируется и открывается путь обхода данного блока обработки 1_j. В этом случае информация, поступающая из предыдущего блока обработки 1_j-1, через элементы И 30 и ИЛИ 33, выдается соответственно на выходы 52 - 57 данного блока обработки 1_j. Значение g, поступающее на вход 42 блока 1_j, выдается на выход 51 блока 1_j. Нулевое значение выдается также на выход 50 блока 1_j и, соответственно, на выход 24_j признака отказа устройства. Нулевой сигнал на выходе 24_j устройства указывает средствам внешнего управления об обнаружении отказа блока 1_j.

Для того, чтобы в определенных ситуациях принудительно вывести блок 1_j из состава устройства, используется установочный вход 18 устройства. В этом случае внешними средствами управления на входе 18_j устройства формируется единичный сигнал, который через вход 47 блока обработки 1_j поступает на вход установки в нуль триггера 29. Для того, чтобы принудительно ввести блок обработки 1_j в состав устройства, например, после его принудительного вывода или после фиксирования ложного отказа, используется вход 19_j устройства. В этом случае внешними средствами управления на входе 19_j устройства формируется сигнал, который через вход 48 блока обработки 1_j поступает на вход установки в единицу триггера 29. При этом работа блока обработки 1_j может быть блокирована путем подачи на вход 20_j устройства единичного сигнала. В этом случае единичный сигнал через вход 44 блока 1_j поступает на инверсный вход элемента И 34, который блокирует прохождение тактовых импульсов на тактовые входы вычислительных узлов 26 и 27 и триггера 29.

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

На вход 15 устройства подается нулевое значение величины g. При наличии исправных блоков 1₁, . .., 1_I-1 с выходов 24₁, ..., 24_I-1 признака отказа устройства выдаются единичные значения, которые поступают на входы соответствующих комбинационных сумматоров 2₁, ..., 2_I-1. Значение g, поступающее на вход 42 блока 1_i, где в случае исправности блоков 1₁, ..., 1_I-1 , равно (I-1). В случае исправности блока 1_i данное значение g выдается на выход 49 блока 1_i и поступает на соответствующий вход комбинационного сумматора 2_i, с выхода которого снимается значение g = i, которое записывается в регистр 3_i и поступает на вход узла сравнения 4_i, на другой вход которого поступает значение I. Таким образом, на каждом такте, в случае исправности блока 1_i, с выхода комбинационного сумматора 2_i выдается значение g = i. При сравнении значений g и I с выхода узла сравнения 4_i выдается единичный сигнал, который поступает на соответствующий вход элемента ИЛИ-НЕ 7, с выхода которого нулевой сигнал поступает на вход 25 признака отказа устройства. Нулевой сигнал на выходе 25 устройства свидетельствует о сохранении работоспособности устройства на данном шаге. Единичное значение с выхода 50 исправного блока обработки 1_K поступает также на соответствующие входы элементов И 6_K, на другие входы которых с выхода 54 блока 1_K поступают вычисленные в блоке 1_K значения Y_кj. При этом с выходов элементов ИЛИ 5_K выдается значение g, которое поступает на выход 23_K. Таким образом, в случае исправности блока обработки 1_K на выход 22_K выдается вычисленное значение Y_кj, а на выход 23_к выдается конкретное значение K = g, соответствующее первому индексу элемента Y_кj. Значение K, выдаваемое с выхода 23_K, используется для указания средствам внешнего управления о значении первого индекса числа Y_кj при различных ситуациях отказа блоков обработки 1_K', где K' < K. В случае отказа блока 1_K происходит обход этого блока, как описано выше. При этом, в случае исправности предыдущих блоков 1₁, ..., 1_K-1, на вход 42 блока 1_K поступает значение g=K-1, которое далее поступает на выход 51 блока 1_K, с выходов 43 и 49 блока 1_K снимаются нулевые значения и, таким образом, с выхода комбинационного сумматора 2_K снимается нулевое значение g. В результате этого с выхода узла сравнения 4_I-1 снимается нулевое значение. Если блок 1_I исправен, то на вход 42 блока 1_I поступает значение g=I, с выхода 49 блока 1_I выдается единичный сигнал и, следовательно, с выхода комбинационного сумматора 2_I снимается значение g= I-1. В результате этого с выхода узла сравнения 4_I снимается единичный сигнал, который поступает на соответствующий вход элемента ИЛИ-НЕ 7, с выхода которого на выход 25 устройства выдается нулевой сигнал, свидетельствующий о сохранении работоспособности устройства. Нулевое значение величины g, формируемое на комбинационном сумматоре 2_K на последующих тактах, поступает на соответствующие входы элементов ИЛИ 5_K и в дальнейшем не влияет на формируемую величину g, поступающую на вход 42 блока 1_K+1. Таким образом, в данном случае с выходов 22₀, .. . , 22_K-1 снимаются значения соответственно Y_0,j, Y_1,j, ... , Y_K-1,j, а с выходов 22_K+1, ..., 22_I снимаются значения Y_K,j, ..., Y_I-1,j. С выходов 23₀, . . ., 23_K-1 снимаются значения, соответственно 0, 1,..., K-1, выход 23_K игнорируется (так как на выходе 24_K присутствует нулевой сигнал), с выходов 23_K+1, . .. , 23_I снимаются значения, соответственно K, K+1,..., I-1. Таким образом, блок обработки 1_K выводится из вычислительного процесса путем обхода, а первый из исправных резервных блоков, например, 1_I вводится в процесс вычисления, при этом длина линейки исправно функционирующих блоков обработки 1 устройства сохраняется. При обнаружении S отказов блоков 1 происходит обход отказавших блоков 1, как было описано выше. Пусть K - номер последнего отказавшего блока 1 линейки, тогда с выхода 51 блока 1_K будет выдаваться значение g= I-S-1, которое поступит на вход 42 блока 1_K+1. Поскольку блок 1_K+1 считается исправным, то с выхода 49 блока 1_K+1 выдается единичный сигнал, с выхода комбинационного сумматора 2_K+1 будет выдано значение g=I-S, которое поступит на вход 42 блока 1_K+2 и т.д. При показании значения g на вход 42 исправного блока 1_i на выходе комбинационного сумматора 2_i формируется величина, равная g+1. При показании значения g на вход 42 неисправного блока 1_i на выходе комбинационного сумматора 2_i формируется нулевое значение, а значение g с выхода 51 блока 1_i поступает на вход 42 следующего блока 1_i+1 линейки. С выхода комбинационного сумматора 2_I+S-1 на вход узла сравнения 4_I+S-1 подается значение g=I-1, с выхода узла сравнения 4_I+S-1 выдается единичный сигнал, который поступает на соответствующий вход элемента ИЛИ-НЕ 7. Через открытые элементы И6 значения Y_ij выдаются выходы 22, соответствующие исправным блокам обработки 1, при этом на выходы 23, соответствующие исправным блокам 1, выдаются значения i. В данном случае на один из входов элемента ИЛИ-НЕ 7 поступает единичный сигнал и, соответственно, на выходе 25 признака отказа устройства присутствует нулевой сигнал, который свидетельствует о работоспособности устройства. При R < S на выходах узлов 4 будут нулевые значения, с выхода элемента ИЛИ-НЕ 7 на выход 25 признака отказа устройства будет выдано единичное значение, которое свидетельствует об исчерпании резерва и отказа устройства. Таким образом, при накоплении R отказов работоспособность устройства сохраняется и длина линейки исправно функционирующих блоков обработки 1 устройства остается постоянной. При обнаружении (R+1)-го отказа устройства, с выхода 25 устройства выдается признак отказа устройства, который далее поступает на средства внешнего управления.

При работе устройства незаблокированные резервные блоки 1 автоматически функционируют в режиме контроля дублированием. В этом случае на входы первого блока обработки 1_p, где p≥ 1, находящегося в резервуаре, с выхода рабочей линейки устройства поступает вычисленное значение итерации.

В результате обработки этого значения в вычислительных узлах 26 и 27 и последующего сравнения результатов в узле 28 резервных блоков обработки 1_p происходит обновление значений триггеров 29 этих блоков. Дальнейшее использование этих резервных блоков обработки 1_p будет происходить с учетом их исправности.

Рассмотрим работу устройства для конкретного случая I=J=P=Q=2 и R=1. Организация входного и выходного потоков данных задается выражениями:

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

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

На такте t = 10 обнаружен отказ блока 1₁, на такте t = 11 происходит блокировка блока 1₁ (в дальнейшем информация, находящаяся в его узлах, не влияет на дальнейший процесс обработки) и обнуление блока 1₀, на такте t = 12 происходит перезапуск устройства (на входы блока 1₀ начата подача соответствующих значений). С такта t = 11 производится обход блока 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+к: чтение информации с блока 1_j+к+1 в блок 1_j+к+2, блокировка и обнуление блока 1_{j+к+ ++1}, разблокировка блока 1_j+к-1.

Если t_n - время (число тактов), требуемое для подготовки к перезапуску устройства со стороны средств внешнего управления, то время реинициализации линейки составляет (j + t_n) тактов. Все временные диаграммы подачи значений входных элементов матриц и управляющих сигналов формируются с помощью средств внешнего управления или аппаратурной среды. В силу технологической структуры кристалла ИС состояния исправности или неисправности его различных долей взаимосвязаны. Степень связи между отказами различных долей ИС измеряется коэффициентом корреляции, величина которого тем больше, чем выше уровень технологии и степень интеграции ИС. Наличие не менее 16-разрядных комбинационных умножителя и сумматора обуславливает степень интеграции и уровень технологии, достаточные для проявления высокой степени корреляции отказов. При контроле дублированием вычислительных узлов необходимо, чтобы отказы этих узлов были независимы. Для этого нужно, чтобы узлы 26 и 27 блока обработки 1 были реализованы на разных кристаллах ИС. Аналогично, исходя из соображений корреляции отказов внутри кристалла ИС, необходимо, чтобы избыточные (резервные) блоки 1 не размещались на одних кристаллов ИС вместе с рабочими.

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

В предлагаемом устройстве осуществляется непрерывный аппаратный контроль на протяжении всего времени работы и блокировка выдачи ошибочной информации при обнаружении отказавшего блока обработки. В устройстве реализован наиболее полный аппаратный контроль, ориентированный на обнаружение всех видов отказов, при этом время контроля сравнимо с тактовым периодом. Достоверность функционирования блока обработки 1 систолического устройства будет определятся как D_ф(t) = P_пр(t) + P_о,о(t),
где
P_пр(t) - вероятность правильной работы блока обработки 1;
P_о,о(t) - вероятность правильной работы блока обработки 1 и выдача с выхода блока 1 сигнала отказа.

Для рассматриваемого систолического устройства

где
P_уз(t) - вероятность безотказной работы вычислительного узла 26 (27).

Следовательно, достоверность функционирования всего устройства будет D_ф = (2 P_уз(t)) - P²_уз (t))ⁿ.

P_уз = 0,99, n = 3, D_ф = 0,996;
P_уз = 0,99, n = 10, D_ф = 0,9891;
P_уз = 0,999 n = 3, D_ф = 0,999997;
P_уз = 0,999, n = 10, D_ф = 0,999989;
P_уз = 0,9999 и выше D_ф практически равна 1. Время восстановления вычислительного процесса (получение достоверного результата на выходе устройства) пропорционально значению m_отк, где m_отк - максимальный номер отказавшего блока обработки 1 в линейке устройства.

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

1. Устройство для вычисления двумерной свертки, содержащее I блоков обработки, каждый из которых включает первые вычислительный узел, где I - размерность решаемой задачи, причем тактовый вход устройства подключен к тактовым входам блоков обработки с первого по I-й, информационные входы первой и второй групп устройства подключены соответственно к информационным входам первой и второй групп первого блока обработки, выходы первой и второй групп i-го блока обработки (i = 1, ..., I - 1) подключены соответственно к информационным входам первой и второй групп (i + 1)-го блока обработки, отличающееся тем, что в него введены с (I + 1)-го по L-й блоки обработки, где L = I + R, R - число резервных блоков обработки, L комбинационных сумматоров, (L - 1) регистров, L узлов сравнения, (L - 1) группа элементов ИЛИ, L групп элементов И и элемент ИЛИ-НЕ, причем первый, второй и третий управляющие входы устройства подключены соответственно к первому, второму и третьему управляющим входам первого блока обработки, первый, второй и третий выходы i-го блока обработки (где i = 1, ... I - 1) подключены соответственно к первому, второму и третьему управляющим входам (i + 1)-го блока обработки, тактовый вход устройства подключен к тактовым входам блоков обработки с (I + 1)-го по L-й и тактовым входам регистров с первого по (L - 1)-й, выходы первой и второй групп, первый, второй и третий выходы j-го блока обработки (где j = 1, ..., L - 1) подключены соответственно к информационным входам первой и второй групп, первому, второму и третьему управляющим входам (j + 1)-го блока обработки, четвертый и пятый управляющие входы устройства подключены соответственно к четвертым и пятым входам блоков обработки с первого по L-й, управляющие входы первой группы устройства подключены соответственно к управляющим входам первых групп блоков обработки с первого по L-й и соответственно к входам первых групп узлов сравнения с первого по L-й, выходы которых подключены соответственно к входам элемента ИЛИ-НЕ, выход которого подключен к выходу признака отказа устройства, управляющие входы второй группы которого подключены соответственно к управляющим входам второй группы первого блока обработки, выходы третьей группы K-го блока обработки (где K = 1, ..., L) подключены соответственно к информационным входам группы K-го комбинационного сумматора, выходы n-го комбинационного сумматора (где n = 1, . . . , L - 1) подключены соответственно к информационным входам n-го регистра и соответственно к входам второй группы n-го узла сравнения, выходы n-го регистра подключены соответственно к первым входам элементов ИЛИ n-й группы, выходы четвертой группы K-го блока обработки подключены соответственно к первым входам элементов И K-й группы, выходы которых подключены соответственно к выходам K-й группы результата устройства, выходы пятой группы n-го блока обработки подключены соответственно к вторым входам элементов ИЛИ n-й группы, выходы которого подключены соответственно к управляющим входам второй группы (n + 1)-го блока обработки и соответственно к выходам (L + n)-й группы результата устройства, выходы L-го комбинационного сумматора подключены соответственно к входам второй группы L-го узла сравнения и соответственно к выходам результата 2L-й группы устройства, четвертый выход K-го блока обработки подключен к информационному входу K-го комбинационного сумматора, к вторым входам элементов И K-й группы и K-му выходу признака отказа группы устройства, K-й вход установки первой группы, K-й вход установки второй группы, K-й вход установки третьей группы и K-й вход блокировки устройства подключены соответственно к первому, второму, третьему входам установки и входу блокировки K-го блока обработки, причем каждый блок обработки дополнительно содержит второй вычислительный узел, узел сравнения, триггер, с первого по третий узлы элементов И, узел элементов ИЛИ и элемент И, причем управляющие входы первой группы блока обработки подключены соответственно к управляющим входам групп первого и второго вычислительных узлов, информационные входы первой и второй групп, с первого по пятый управляющие входы и управляющие входы второй группы блока обработки подключены соответственно к входам группы второго узла элементов И, выходы первой группы первого узла элементов И подключены соответственно к входам первой группы узла элементов ИЛИ, выходы которого подключены соответственно к выходам первой, второй, четвертой групп, первому, второму и третьему входам блока обработки, выходы первой группы второго узла элементов И подключены соответственно к информационным входам первой и второй групп и управляющим входам с первого по пятый первого и второго вычислительных узлов, выходы первой, второй и третьей групп, первый, второй и третий выходы первого вычислительного узла подключены соответственно к входам первой группы узла сравнения и входам группы третьего узла элементов И, выходы которого подключены соответственно к входам второй группы узла элементов ИЛИ, выходы первой, второй и третьей групп, первый, второй и третий выходы второго вычислительного узла подключены соответственно к входам второй группы узла сравнения, выход которого подключен к информационному входу триггера, вход которого подключен к входу третьего узла элементов И, инверсному входу первого узла, входу второго узла элементов И и четвертому выходу блока обработки, выходы вторых групп первого и второго узлов элементов И подключены соответственно к выходам пятой и третьей групп блока обработки, первый вход установки которого подключен к входам установки в исходное состояние первого и второго вычислительных узлов, второй и третий входы установки, тактовый вход и вход блокировки блока обработки подключены соответственно к входам установки в нуль триггера, входу установки в единицу триггера, первому и второму (инверсному) входам элемента И, выход которого подключен к тактовым входам первого и второго вычислительных узлов и входу синхронизации триггера.

2. Устройство по п.1, отличающееся тем, что каждый вычислительный узел содержит с первой по четвертую группу регистров, первый и второй регистры, умножитель и сумматор, группу триггеров, с первого по четвертый триггеры, (2М + 2N + 5) групп элементов И (где М = (Q+1)τ+1, N = Q + 2), восемь групп элементов ИЛИ, первый и второй дешифраторы, М элементов И и элемент ИЛИ, причем информационные входы первой группы узла подключены к информационным входам первого регистра первой группы и первым входам элементов И первой группы, выходы которых подключены соответственно к первым входам элементов ИЛИ первой группы, выходы которых подключены к информационным входам первого регистра второй группы, выходы a-го регистра первой группы (где a = 1, ..., М - 1) подключены к информационным входам (a + 1)-го регистра первой группы и первым входам элементов И (a + 1)-й группы, выходы М-го регистра первой группы подключены к первым входам элементов И (М + 1)-й группы, выходы элементов И групп с второй по (М + 1)-ю подключены соответственно к входам элементов ИЛИ второй группы, выходы которых подключены к выходам первой группы вычислительного узла, выходы первого регистра подключены к первым входам элементов И (М + 2)-й группы, информационным входам второго регистра второй группы и информационным входам первой группы комбинированного умножителя, выходы δ-го регистра второй группы (где δ = 2, ..., N - 1) подключены к информационным входам (δ + 1)-го регистра второй группы и первым входам элементов И (М + 1 + δ)-й группы, выходы N-го регистра второй группы подключены к первым входам элементов И (М + N + 1)-й группы, выходы элементов И группы с (М + 2)-й по (М + N + 1)-ю подключены соответственно к входам элементов ИЛИ третьей группы, выходы которых подключены соответственно к первым входам элементов И (М + N + 2)-й группы, выходы которых подключены соответственно к вторым входам элементов ИЛИ первой группы, выходы умножителя подключены соответственно к первым входам элементов И (М + N + 3)-й группы, выходы которых подключены к первым входам элементов ИЛИ четвертой группы, выходы которых подключены к информационным входам первой группы сумматора, выходы которого подключены к первым входам элементов И (М + N + 4)-й группы и информационным входам первого регистра, выходы которого подключены соответственно к информационным входам второй группы сумматора, информационные входы второй группы подключены к информационным входам второго регистра и первым входам элементов И (М + N + 5)-й группы, выходы которых подключены к первым входам элементов ИЛИ пятой группы, выходы которых подключены к информационным входам первого регистра третьей группы, выходы которого подключены к информационным входам второй группы умножителя, информационным входам второго регистра третьей группы и первым входам элементов И (М + N + 6)-й группы, выходы b-го регистра группы (где b = 2, ..., N - 2) подключены к информационным входам (b + 1)-го регистра третьей группы и первым входам элементов И (М + N + 5 + b)-й группы, выходы (N - 1)-го регистра третьей группы подключены к первым входам элементов И (М + 2N + 4)-й группы, выходы элементов И групп с (М + N + 6)-й по (М + 2N + 4)-ю подключены к соответствующим входам элементов ИЛИ шестой группы, выходы которых подключены соответственно к первым входам элементов И (М + 2N + 5)-й группы, выходы которых подключены соответственно к вторым входам элементов ИЛИ пятой группы, выходы второго регистра подключены к выходам второй группы вычислительного узла, выходы первого регистра четвертой группы подключены к первым входам элементов И (М + 2N + 6)-й группы и элементов И (М + 2N + 7)-й группы, выходы которых подключены соответственно к вторым входам элементов ИЛИ четвертой группы и первым входам элементов ИЛИ седьмой группы, выходы которых подключены к информационным входам второго регистра четвертой группы, выходы которого подключены к выходам третьей группы вычислительного модуля, информационным входам третьего регистра четвертой группы и первым входам элементов И (М + 2N + 8)-й группы, выход c-го регистра четвертой группы (где c = 3, ..., М - 2) подключены соответственно к информационным входам (c + 1)-го регистра четвертой группы и первым входам элементов И (2N + М + 6 + c)-й группы, выходы (М - 1)-го регистра четвертой группы подключены соответственно к первым входам элементов И (2N + 2М + 4)-й группы, выходы элементов И групп с (2N + М + 8)-й по (2N + 2М + 4)-ю подключены к соответствующим входам элементов ИЛИ восьмой группы, выходы которых подключены к информационным входам первого регистра четвертой группы, первый управляющий вход подключен к вторым входам элементов И первой группы, вторым (инверсным) входам элементов И (М + N + 2)-й группы и информационному входу первого триггера группы, выход d-го триггера группы (где d = 1, ..., М - 1) подключен к первому входу d-го элемента И и информационному входу (d + 1)-го триггера, выход М-го триггера группы подключен к первому входу элемента И, выходы элементов И с первого по М-й подключены соответственно к входам элемента ИЛИ, выход которого подключен к первому выходу вычислительного узла, второй управляющий вход которого подключен к вторым входам элементов И (М + N + 5)-й группы, вторым (инверсным) входам элементов И (М + 2N + 5)-й группы и информационному входу первого триггера, выход которого подключен к второму выходу вычислительного узла, третий управляющий вход которого подключен к первому входу установки в нуль первого регистра четвертой группы и информационному входу второго триггера, выход которого подключен к третьему выходу вычислительного узла, четвертый управляющий вход которого подключен к информационному входу третьего триггера. выход которого подключен к первому входу установки в нуль первого регистра, пятый управляющий вход вычислительного узла подключен к информационному входу четвертого триггера, выход которого подключен к вторым входам элементов И (М + 2N + 6)-й группы, элементов И (М + N + 4)-й группы, вторым (инверсным) входам элементов И (М + N + 3)-й группы и элементов И (М + 2N + 7)-й группы, управляющие входы с первого по r-й и с (r + 1)-го по v-й группы вычислительного узла (где r = log₂M, v - r = log₂N) подключены соответственно к входам первого и второго дешифраторов, f-й выход первого дешифратора (где f = 1, ..., М) подключен к вторым выходам элементов И (f + 1)-й группы, элементов И (2N + М + 5 + h)-й группы (где h = 3, ..., М) и f-го элемента И, P-й выход второго дешифратора (где P = 1, . .., N) подключен к вторым входам элементов И (М + 1 + P)-й группы и элементов И (М + N + 4 + q)-й группы (где q = 2, ..., N), тактовый вход вычислительного узла подключен к входам записи/считывания регистров групп с первой по четвертую, первого и второго регистров, входам синхронизации триггеров группы и триггеров с первого по четвертый, вход установки в исходное состояние вычислительного узла подключен к входам установки в нуль всех триггеров, второго регистра, регистров групп с первой по третью, регистров с второго по (М - 1)-й четвертой группы и вторым входам установки в нуль первого регистра и первого регистра четвертой группы.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9, Рисунок 10, Рисунок 11, Рисунок 12, Рисунок 13, Рисунок 14