Патент на изобретение №2177169
|
||||||||||||||||||||||||||
(54) ЯЧЕЙКА ОДНОРОДНОЙ СРЕДЫ ПРОЦЕССОРНЫХ ЭЛЕМЕНТОВ
(57) Реферат: Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении управляющих и вычислительных систем высокой производительности, АСУТП, а также других систем, к которым предъявляются жесткие требования по надежности. Техническим результатом является расширение области применения за счет введения технических средств, уменьшающих число перестраиваемых ячеек. Устройство содержит восемь элементов ИЛИ, двенадцать элементов И, четыре элемента запрета, элемент ИЛИ-НЕ, три элемента И-ИЛИ, четыре триггера, одновибратор. 5 ил. Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении управляющих и вычислительных систем высокой производительности, АСУТП, а также других систем, к которым предъявляются жесткие требования по надежности. Недостатками известного устройства являются низкое быстродействие и высокий процент ситуаций фатального отказа, для которых перестройка невозможна. Наиболее близкой к предлагаемому устройству по технической сущности является ячейка однородной среды процессорных элементов, содержащая десять элементов ИЛИ, шестнадцать элементов И и пять элементов запрета (патент 2103724 РФ, G 06 F 7/00, опубл. 27.01.98, БИ N 3). Недостатком известного устройства является узкая область применения, обусловленная низким быстродействием однородной среды из-за большого числа последовательно перестраиваемых ячеек. Технической задачей изобретения является расширение области применения за счет введения технических средств, уменьшающих число перестраиваемых ячеек. Техническая задача решается тем, что в ячейку однородной среды процессорных элементов, содержащую с первого по восьмой элементы ИЛИ, с первого по двенадцатый элементы И, первый, второй, третий и четвертый элементы запрета, дополнительно введены элемент ИЛИ-НЕ, первый, второй и третий элементы И-ИЛИ, первый, второй, третий и четвертый триггеры, одновибратор, причем первый вход ячейки однородной среды процессорных элементов соединен с первым входом четвертого элемента ИЛИ, инверсным входом первой группы входов третьего элемента И-ИЛИ, вторым входом седьмого элемента И и вторым прямым входом седьмого элемента ИЛИ, выход которого соединен с первым входом девятого элемента И, второй вход ячейки однородной среды процессорных элементов соединен со вторым входом четвертого элемента ИЛИ, первым входом шестого элемента ИЛИ и вторым входом десятого элемента И, выход которого соединен с пятым выходом ячейки однородной среды процессорных элементов, третий вход ячейки однородной среды процессорных элементов соединен с третьим входом четвертого элемента ИЛИ, вторым входом шестого элемента ИЛИ и вторым входом одиннадцатого элемента И, выход которого соединен с шестым выходом ячейки однородной среды процессорных элементов, четвертый вход ячейки однородной среды процессорных элементов соединен с четвертым входом четвертого элемента ИЛИ, первым входом второй группы входов третьего элемента И-ИЛИ, вторым входом элемента ИЛИ-НЕ и вторым входом восьмого элемента И, выход которого соединен с прямым входом четвертого элемента запрета, пятый вход ячейки однородной среды процессорных элементов соединен со вторым входом третьего элемента ИЛИ, прямым входом второй группы входов первого элемента И-ИЛИ и первым входом пятого элемента ИЛИ, выход которого соединен с прямым входом третьего элемента запрета, шестой вход ячейки однородной среды процессорных элементов соединен с первым входом первого элемента ИЛИ, вторым входом первой группы входов и первым входом второй группы входов второго элемента И-ИЛИ, выход которого соединен со входом установки четвертого триггера, седьмой вход ячейки однородной среды процессорных элементов соединен со вторым входом первого элемента ИЛИ, вторым входом второй группы входов второго элемента И-ИЛИ и вторым входом первого элемента И, выход которого соединен со входом установки третьего триггера, восьмой вход ячейки однородной среды процессорных элементов соединен со вторым входом пятого элемента ИЛИ, первым входом первой группы входов первого элемента И-ИЛИ и вторым входом второго элемента ИЛИ, выход которого соединен со входом установки первого триггера, девятый вход ячейки однородной среды процессорных элементов соединен с третьим входом пятого элемента ИЛИ и инверсным входом второго элемента запрета, выход которого соединен со вторыми входами второго, третьего, четвертого и пятого элементов И, десятый вход ячейки однородной среды процессорных элементов соединен со вторым входом первой группы входов первого элемента И-ИЛИ, инверсным входом второй группы входов первого элемента И-ИЛИ, прямым входом первой группы входов третьего элемента И-ИЛИ, вторым входом второй группы входов третьего элемента И-ИЛИ, третьим входом элемента ИЛИ-НЕ, инверсным входом седьмого элемента ИЛИ, вторым входом восьмого элемента ИЛИ и вторым входом девятого элемента И, выход которого соединен с инверсным входом четвертого элемента запрета, одиннадцатый вход ячейки однородной среды процессорных элементов соединен с пятым входом четвертого элемента ИЛИ и инверсным входом третьего элемента запрета, выход которого соединен с первыми входами шестого, седьмого и восьмого элемента И и первым прямым входом первого элемента запрета, двенадцатый вход ячейки однородной среды процессорных элементов соединен со входом одновибратора, выход которого соединен со входами сброса первого, второго, третьего и четвертого триггеров, выход первого элемента ИЛИ соединен с пятым входом пятого элемента ИЛИ и первыми входами второго и третьего элементов ИЛИ, выход третьего элемента ИЛИ соединен со входом установки второго триггера, выход первого элемента И-ИЛИ соединен с первым входом первого элемента И и первым входом первой группы входов второго элемента И-ИЛИ, выход четвертого элемента ИЛИ соединен с прямым входом второго элемента запрета и инверсным входом первого элемента запрета, инверсные выходы первого, второго, третьего и четвертого триггеров соединены с первыми входами второго, третьего, четвертого и пятого элементов И соответственно, выходы второго, третьего, четвертого и пятого элементов И соединены с первым, вторым, третьим и четвертым выходами ячейки однородной среды процессорных элементов соответственно, выход первого элемента запрета соединен с девятым выходом ячейки однородной среды процессорных элементов, выход третьего элемента И-ИЛИ соединен со вторым входом шестого элемента И, выход шестого элемента И соединен с первыми входами десятого и одиннадцатого элементов И, выход седьмого элемента И соединен с первым входом двенадцатого элемента И, выход шестого элемента ИЛИ соединен с первым входом элемента ИЛИ-НЕ и первым прямым входом седьмого элемента ИЛИ, выход элемента ИЛИ-НЕ соединен с первым входом восьмого элемента ИЛИ, выход восьмого элемента ИЛИ соединен со вторым входом двенадцатого элемента И, выход двенадцатого элемента И соединен с седьмым выходом ячейки однородной среды процессорных элементов, выход четвертого элемента запрета соединен с восьмым выходом ячейки однородной среды процессорных элементов. Сущность изобретения заключается в следующем. Множество ячеек однородной среды процессорных элементов является элементами настройки матрицы из nхm процессорных элементов (ПЭ). Местоположение ПЭ и соответствующей ему ячейки однородной среды процессорных элементов определяется ее физическим адресом (ФА) – (i, j) (где  – номер строки,  – номер столбца матрицы).
Каждая ячейка однородной среды процессорных элементов (i,j) настраивает соответствующий ПЭ (i, j) на один из алгоритмов функционирования: собственный (i, j), верхний (i+1, j), нижний (i-1, j), правый (i, j+1), левый (i, j-1) в зависимости от отказов или изменения алгоритмов функционирования верхнего (i+1, j)-го, нижнего (i-1, j)-го, правого (i, j+1)-го и левого (i, j-1)-го ПЭ.
Алгоритм функционирования (i’, j’), на который настроена (i, j)-я ячейка, будем называть виртуальным адресом (ВА) (i, j)-й ячейки.
Первоначально (при отсутствии отказов) все ПЭ, за исключением резервных, имеют ВА, равный ФА. Резервными являются ПЭ ]m/2[-го столбца (где ][ – операция округления до большего целого), которые первоначально имеют ВА = (0,0), т.е. не выполняют никакого алгоритма функционирования.
При возникновении отказов ПЭ множество взаимодействующих ячеек однородной среды процессорных элементов перенастраивает работоспособные ПЭ (в том числе и резервные) на новые ВА. Взаимодействие ячеек однородной среды процессорных элементов осуществляется сигналами потенциальных и реальных перемещений, поступающих от (i,k)-й ячейки однородной среды процессорных элементов в (i+1,j)-ю, (i-1,j)-ю, (i,j+1)-ю и (i,j-1)-ю. Сигналы потенциальных перемещений от (i,j)-й ячейки однородной среды процессорных элементов информируют соседние ячейки о возможности перенастройки (i,j)-го ПЭ на один из соответствующих алгоритмов функционирования. Сигнал реального перемещения от (i, j)-й ячейки информирует одну из соседних ячеек о ее перенастройке на (i, j)-й алгоритм.
При отсутствии отказов выработка сигналов потенциальных перемещений инициируется резервными элементами по всем направлениям. Остальные элементы вырабатывают сигналы потенциальных перемещений во всех направлениях при поступлении хотя бы с одного направления.
При возникновении отказов ПЭ выработка сигналов потенциальных перемещений от них прекращается. Каждый отказавший ПЭ инициирует сигнал реального перемещения в одном из 4-х направлений, начиная с приоритетного. Работоспособные ПЭ инициируют сигнал реального перемещения только при поступлении такого сигнала от соседей. Резервные элементы не инициируют сигналы реальных перемещений.
При поступлении в один ПЭ двух и более сигналов реальных перемещений возникает конфликтная ситуация, т.к. каждый ПЭ может выполнять только один алгоритм функционирования. Конфликтная ситуация разрешается путем блокирования выдачи сигналов потенциальных перемещений по направлению прихода менее приоритетных сигналов реальных перемещений. При этом ПЭ, вырабатывающие эти сигналы реальных перемещений, вырабатывают их в других направлениях. Приоритет направлений для ПЭ, расположенного слева от резервного элемента: вправо, вверх, вниз, влево. Для ПЭ, расположенного справа: влево, вверх, вниз, вправо.
В случае, если в отказавший ПЭ не поступает ни одного сигнала потенциального перемещения, возникает ситуация фатального отказа (ФО), т.е. перенастройка невозможна.
Сущность изобретения поясняется чертежами, где на фиг. 1 показана функциональная схема ячейки однородной среды процессорных элементов; на фиг. 2 – схема распространения сигналов при отсутствии отказов; на фиг. 3 – схема распространения сигналов при 1 отказе; на фиг. 4 – схема распространения сигналов при 2 отказах; на фиг. 5 – схема распространения сигналов при фатальном отказе.
Ячейка однородной среды процессорных элементов (фиг. 1) содержит первый 1, второй 2, третий 3, четвертый 4, пятый 5, шестой 6, седьмой 7 и восьмой 8 элементы ИЛИ, первый 9, второй 10, третий 11, четвертый 12, пятый 13, шестой 14, седьмой 15, восьмой 16, девятый 17, десятый 18, одиннадцатый 19 и двенадцатый 20 элементы И, первый 21, второй 22, третий 23 и четвертый 24 элементы запрета, элемент ИЛИ-НЕ 25, первый 26, второй 27 и третий 28 элементы И-ИЛИ, первый 29, второй 30, третий 31 и четвертый 32 триггеры, одновибратор 33, первый 34, второй 35, третий 36, четвертый 37, пятый 38, шестой 39, седьмой 40, восьмой 41, девятый 42, десятый 43, одиннадцатый 44, двенадцатый 45 входы ячейки, первый 46, второй 47, третий 48, четвертый 49, пятый 50, шестой 51, седьмой 52, восьмой 53, девятый 54 выходы ячейки, причем вход 34 ячейки соединен с первым входом элемента ИЛИ 4, инверсным входом первой группы входов элемента И-ИЛИ 28, вторым входом элемента И 15 и вторым прямым входом элемента ИЛИ 7, выход которого соединен с первым входом элемента И 17, вход 35 ячейки соединен со вторым входом элемента ИЛИ 4, первым входом элемента ИЛИ 6 и вторым входом элемента И 18, выход которого соединен с выходом 50 ячейки, вход 36 ячейки соединен с третьим входом элемента ИЛИ 4, вторым входом элемента ИЛИ 6 и вторым входом элемента И 19, выход которого соединен с выходом 51 ячейки, вход 37 ячейки соединен с четвертым входом элемента ИЛИ 4, первым входом второй группы входов элемента И-ИЛИ 28, вторым входом элемента ИЛИ-НЕ 25 и вторым входом элемента И 16, выход которого соединен с прямым входом элемента запрета 24, вход 38 ячейки соединен со вторым входом элемента ИЛИ 3, прямым входом второй группы входов элемента И-ИЛИ 26 и первым входом элемента ИЛИ 5, выход которого соединен с прямым входом элемента запрета 23, вход 39 ячейки соединен с первым входом элемента ИЛИ 1, вторым входом первой группы входов и первым входом второй группы входов элемента И-ИЛИ 27, выход которого соединен со входом установки триггера 32, вход 40 ячейки соединен со вторым входом элемента ИЛИ 1, вторым входом второй группы входов элемента И-ИЛИ 27 и вторым входом элемента И 9, выход которого соединен со входом установки триггера 31, вход 40 ячейки соединен со вторым входом элемента ИЛИ 5, первым входом первой группы входов элемента И-ИЛИ 26 и вторым входом элемента ИЛИ 2, выход которого соединен со входом установки триггера 29, вход 42 ячейки соединен с третьим входом элемента ИЛИ 5 и инверсным входом элемента запрета 22, выход которого соединен со вторыми входами элементов И 10, И 11, И 12 и И 13, вход 43 ячейки соединен со вторым входом первой группы входов элемента И-ИЛИ 26, инверсным входом второй группы входов элемента И-ИЛИ 26, прямым входом первой группы входов элемента И-ИЛИ 28, вторым входом второй группы входов элемента И-ИЛИ 28, третьим входом элемента ИЛИ-НЕ 25, инверсным входом элемента ИЛИ 7, вторым входом элемента ИЛИ 8 и вторым входом элемента И 17, выход которого соединен с инверсным входом элемента запрета 24, вход 44 ячейки соединен с пятым входом элемента ИЛИ 4 и инверсным входом элемента запрета 23, выход которого соединен с первыми входами элементов И 14, И 15 и И 16 и первым прямым входом элемента запрета 21, вход 45 ячейки соединен со входом одновибратора 33, выход которого соединен со входами сброса триггера 29, триггера 30, триггера 31 и триггера 32, выход элемента ИЛИ 1 соединен с пятым входом элемента ИЛИ 5 и первыми входами элементов ИЛИ 2 и ИЛИ 3, выход элемента ИЛИ 3 соединен со входом установки триггера 30, выход элемента И-ИЛИ 26 соединен с первым входом элемента И 9 и первым входом первой группы входов элемента И-ИЛИ 27, выход элемента ИЛИ 4 соединен с прямым входом элемента запрета 22 и инверсным входом элемента запрета 21, инверсные выходы триггера 29, триггера 30, триггера 31 и триггера 32 соединены с первыми входами элементов И 10, И 11, И 12 и И 13 соответственно, выходы элементов И 10, И 11, И 12 и И 13 соединены с выходами ячейки 46, 47, 48 и 49 соответственно, выход элемента запрета 21 соединен с выходом 54 ячейки, выход элемента И-ИЛИ 28 соединен со вторым входом элемента И 14, выход элемента И 14 соединен с первыми входами элементов И 18 и И 19, выход элемента И 15 соединен с первым входом элемента И 20, выход элемента ИЛИ 6 соединен с первым входом элемента ИЛИ-НЕ 25 и первым прямым входом элемента ИЛИ 7, выход элемента ИЛИ-НЕ 25 соединен с первым входом элемента ИЛИ 8, выход элемента ИЛИ 8 соединен со вторым входом элемента И 20, выход элемента И 20 соединен с выходом 52 ячейки, выход элемента запрета 24 соединен с выходом 53 ячейки однородной среды.
Для организации однородной среды ячейки процессорных элементов соединяются следующим образом: выходы 46 и 52 j-й ячейки i-й строки соединены с входами 34 и 38 (j+1)-й ячейки i-й строки соответственно, выходы 48 и 51 j-й ячейки i-й строки соединены с входами 36 и 40 j-й ячейки (i-1)-й строки соответственно, выходы 49 и 53 j-й ячейки i-й строки соединены с входами 37 и 41 (j-1)-й ячейки i-й строки соответственно, выходы 47 и 50 j-й ячейки i-й строки соединены с входами 35 и 39 j-й ячейки (i+1)-й строки соответственно, выходы 48 и 51 j-й ячейки (i+1)-й строки соединены с входами 36 и 40 j-й ячейки i-й строки соответственно, выходы 49 и 53 (j+1)-й ячейки i-й строки соединены с входами 37 и 41 j-й ячейки i-й строки соответственно, выходы 47 и 50 j-й ячейки (i-1)-й строки соединены с входами 35 и 39 j-й ячейки i-й строки соответственно, выходы 46 и 52 (j-1)-й ячейки i-й строки соединены с входами 34 и 38 j-й ячейки i-й строки соответственно. Для крайне левого столбца матрицы входные сигналы x11 равны нулю. Для крайне правого – входные сигналы x14 равны нулю. Для крайнего верхнего – входные сигналы x12 равны нулю. Для крайнего нижнего – входные сигналы x13 равны нулю.
Рассмотрим работу (i,j)-й ячейки однородной среды процессорных элементов. При этом работу ее будем рассматривать во взаимосвязи с другими ячейками однородной среды процессорных элементов. Когда все процессорные элементы матрицы находятся в работоспособном состоянии (фиг. 2), на входах 1, 2, 3 и 4 соответствующих им ячеек самоорганизации присутствуют единичные сигналы, на входах 5, 6, 7, 8 и 9 – нулевые сигналы, показывающие отсутствие необходимости в перенастройке матрицы. Таким образом, на входах первого элемента ИЛИ сигналы логического нуля, на его выходе нулевой сигнал, который поступает на первый вход второго элемента ИЛИ, на втором входе которого также сигнал логического нуля. С выхода этого элемента нулевой сигнал поступает на вход установки первого триггера. На входах третьего элемента ИЛИ нулевые сигналы, на его выходе сигнал логического нуля, который поступает на вход установки второго триггера. На первый вход первой группы входов и прямой вход второй группы входов первого элемента И-ИЛИ поступают нулевые сигналы, следовательно на его выходе сигнал логического нуля, на выходе первого элемента И также нулевой сигнал, который поступает на вход установки третьего триггера. На входах второго элемента И-ИЛИ сигналы логического нуля, на его выходе нулевой сигнал, который поступает на вход установки четвертого триггера. На первом, втором, третьем и четвертом входах четвертого элемента ИЛИ единичные сигналы, на его выходе сигнал логической единицы, который поступает на прямой вход второго элемента запрета, на инверсный вход которого поступает нулевой сигнал, свидетельствующий о работоспособности данного процессорного элемента. Таким образом, на первые входы второго, третьего, четвертого и пятого элементов И поступают единичные сигналы с выходов первого, второго, третьего и четвертого триггеров соответственно, а сигнал логической единицы с выхода второго элемента запрета поступает на вторые входы второго, третьего, четвертого и пятого элементов И, с выходов которых единичные сигналы поступают на первый, второй, третий и четвертый выходы ячейки соответственно. Следовательно, соседним ячейкам будет сообщено, что при необходимости можно осуществить перенастройку через данную ячейку. На входах пятого элемента ИЛИ нулевые сигналы, на его выходе сигнал логического нуля, который поступает на прямой вход третьего элемента запрета, с выхода которого нулевой сигнал через шестой элемент И поступает на десятый и одиннадцатый элементы И, а через седьмой и восьмой элементы И на двенадцатый элемент И и четвертый элемент запрета. Таким образом, через десятый, одиннадцатый и двенадцатый элементы И, а также через четвертый элемент запрета нулевые сигналы подаются на пятый, шестой, седьмой и восьмой выходы ячейки соответственно, сообщая соседним ячейкам об отсутствии необходимости в перенастройке матрицы через эти ячейки.
Если в одной из ячеек возникает отказ (фиг. 3), то на вход 9 отказавшей ячейки поступает единичный сигнал. Таким образом на инверсном входе второго элемента запрета сигнал логической единицы, на его выходе нулевой сигнал, который, пройдя через второй, третий, четвертый и пятый элементы И, поступает на первый, второй, третий и четвертый выходы ячейки соответственно. Нулевые сигналы с данных выходов поступают в соседние ячейки и сообщают о невозможности перенастройки через данную ячейку. Если отказавший элемент расположен в правой части матрицы, то на вход 10 ячейки поступает нулевой сигнал. При этом, если на вход 4 ячейки поступает единичный сигнал, т.е. справа от ячейки расположен исправный ПЭ, то на выходе третьего элемента И-ИЛИ нулевой сигнал, который, пройдя через шестой, десятый и одиннадцатый элементы И, поступает на пятый и шестой выходы ячейки. На первый вход элемента ИЛИ-НЕ с входа 4 ячейки поступает единичный сигнал, на его выходе нулевой сигнал, который поступает на первый вход восьмого элемента ИЛИ, на второй вход которого с входа 10 также поступает нулевой сигнал. Таким образом, на выходе восьмого элемента ИЛИ сигнал логического нуля, который, пройдя через двенадцатый элемент И, поступает на седьмой выход ячейки. С выхода третьего элемента запрета единичный сигнал поступает на первый вход восьмого элемента И, на второй вход которого поступает единичный сигнал с входа 4 ячейки. На выходе восьмого элемента И сигнал логической единицы, который поступает на прямой вход четвертого элемента запрета. С входа 10 ячейки через девятый элемент И нулевой сигнал поступает на инверсный вход четвертого элемента запрета. Таким образом только на выходе 8 ячейки установится единичный сигнал, указывающий на то, что перераспределение будет осуществляться влево в направлении к резерву. Если отказавший элемент расположен слева от резерва, то на вход 10 поступает единичный сигнал, который, пройдя через восьмой элемент ИЛИ и девятый элемент И, поступает на выход 7 ячейки. При этом, на выходе 8 ячейки установится нулевой сигнал. Таким образом, перераспределение алгоритма отказавшей ячейки будет осуществляться вправо к резерву.
В случае возникновения конфликтных ситуаций (фиг. 4) приоритет при перераспределении отдается отказавшим элементам, расположенным в левой части матрицы. Например, если на входы 5 и 8 ячейки одновременно поступают единичные сигналы, то на выходе 4 ячейки сигнал логической единицы, а на выходе 1 нулевой сигнал. Таким образом, ячейка отказавшего элемента, расположенного слева, получит единичный сигнал потенциального перемещения, разрешающий перераспределение вправо.
В случае возникновения фатального отказа (фиг. 5) на входы 1, 2, 3, 4 и 11 ячейки поступают нулевые сигналы, свидетельствующие о невозможности перенастройки через данный ПЭ ни в одном из направлений. Таким образом, на всех входах четвертого элемента ИЛИ нулевые сигналы, на его выходе сигнал логического нуля, который подается на инверсный вход первого элемента запрета. Если нет ни одного реального перемещения через данный ПЭ и он не отказал, то на входах 5, 6, 7, 8 и 9 присутствуют нулевые сигналы. Таким образом, на всех входах пятого элемента ИЛИ сигналы логического нуля, на его выходе нулевой сигнал, который, пройдя через третий и первый элементы запрета, формирует на выходе 9 ячейки единичный сигнал, свидетельствующий о наличии фатального отказа.
Таким образом, введение дополнительных технических средств позволяет обеспечить перестройку при существенном уменьшении числа перестраиваемых ячеек.
Формула изобретения
РИСУНКИ
MM4A Досрочное прекращение действия патента Российской Федерации на изобретение из-за неуплаты в установленный срок пошлины за поддержание патента в силе
Дата прекращения действия патента: 01.08.2002
Номер и год публикации бюллетеня: 4-2004
Извещение опубликовано: 10.02.2004
|
||||||||||||||||||||||||||
