Патент на изобретение №2273876
|
||||||||||||||||||||||||||
(54) ЯЧЕЙКА МАРШРУТИЗАЦИИ ОДНОРОДНОЙ СРЕДЫ ПРОЦЕССОРНЫХ ЭЛЕМЕНТОВ
(57) Реферат:
Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении высоконадежных матричных, конвейерных, систолических, векторных и других процессоров. Техническим результатом является расширение области применения однородной среды процессорных элементов за счет введения технических средств, обеспечивающих передачу сообщения в условиях возникающих отказов отдельных модулей однородной среды процессорных элементов и связей между ними. Устройство содержит блок выбора максимального континуального адреса, блок сброса, блок адресной селекции, блок выбора минимальной континуальной величины, блок формирования кода направления, таблицу маршрутизации, блок коррекции направления, блок коммутации сигналов достижимости, блок коммутации континуального адреса, блок-сумматор, блок источник опорных напряжений, буферный блок сообщений, блок коммутации сообщений, элемент “ИЛИ”, 2 аналого-цифровых преобразователя. 20 ил.
Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении высоконадежных матричных, конвейерных, векторных и других процессоров, в которых в процессе обработки происходит передача данных в вычислительной среде, а также при построении коммутационных средств управляющих и информационно-измерительных систем. Известна распределенная система для программного управления, содержащая n Недостатком известной системы являются высокие требования к надежности блоков анализа, отвечающих за передачу сообщений между модулями, что существенно сужает область применения однородной среды процессорных элементов. Наиболее близкой к предлагаемому устройству по технической сущности является распределенная система для программного управления, содержащая n Недостатком известной системы является узкая область применения, обусловленная невысоким процентом успешных передач сообщений в условиях отказов отдельных модулей, отсутствие средств выбора оптимального маршрута передачи сообщения. Технической задачей изобретения является расширение области применения однородной среды процессорных элементов за счет введения технических средств, обеспечивающих передачу сообщений в условиях возникновения отказов отдельных модулей однородной среды процессорных элементов. Техническая задача решается тем, что в однородную среду процессорных элементов, содержащую M×N модулей, где М – число строк, N – число столбцов, дополнительно введены ячейки маршрутизации однородной среды процессорных элементов, причем i-ая ячейка Сущность изобретения заключается в следующем. Предлагаемое устройство совместно с другими аналогичными устройствами образует систему обмена сообщениями между процессорными элементами (ПЭ). Система представляет собой однородную матричную структуру из M×N ячеек (устройств), каждая ячейка (устройство) которой соединена по четырем направлениям с соседними ячейками (устройствами). Передача сообщений между любыми ячейками (устройствами) осуществляется через другие ячейки (транзитным способом). Местоположение ячейки маршрутизации и соответствующего ему ПЭ определяется ее физическим адресом (ФА)-(i,j) (где Каждый ПЭ (i,j) выполняет один из алгоритмов: собственный (i,j)-й, верхний (i-1,j)-й, нижний (i+1,j)-й, правый (i,j+1)-й, левый (i,j-1)-й в зависимости от отказов или изменения алгоритмов функционирования соседних ПЭ. Алгоритм функционирования (i’,j’), на который настроен (i,j)-й ПЭ, будем называть логическим адресом (ЛА) (i,j)-ого ПЭ. Первоначально (при отсутствии отказов) все ПЭ имеют ЛА, равный ФА. При построении функциональной схемы устройства двойное обозначение (i,j) физического или логического адреса заменяется одним числом ФА или ЛА соответственно. Взаимодействие ячеек маршрутизации однородной среды обеспечивает доставку сообщений от одного ПЭ (источника) до другого ПЭ (приемника) по логическому адресу приемника в условиях возникающих отказов ПЭ и каналов передачи сообщений. Принцип передачи сообщений между ПЭ заключается в следующем: при получении ячейкой сообщения сравнивается адресная часть сообщения (адрес приемника сообщения) и логический адрес текущей ячейки, если они равны, то сообщение считается принятым и передается в ПЭ соответствующий текущей ячейки маршрутизации однородной среды, в противном случае ячейка маршрутизации передает сообщение в направлении, извлеченном из собственной таблицы маршрутизации из памяти по адресу приемника сообщения. Ячейки маршрутизации однородной среды процессорных элементов, взаимодействуя между собой, настраивают таблицы маршрутизации таким образом, чтобы обеспечивалась передача сообщения необходимому ПЭ по кратчайшему пути в обход отказавших элементов и каналов передачи сообщений. При этом в начальный момент (до появления отказов) таблицы маршрутизации всех ячеек среды настроены так, чтобы передача сообщения осуществлялась по кратчайшему пути без учета отказавших ПЭ (сначала горизонтально до достижения столбца приемника и далее вертикально до достижения строки приемника). До появления отказов ПЭ на выходах с одиннадцатого по четырнадцатый и с пятнадцатого по восемнадцатый всех ячеек маршрутизации установлено нулевое значение. После возникновения отказов и логической перестройки в матрице процессорных элементов происходит изменение логических адресов ПЭ и соответствующих им ячеек маршрутизации. Такие ячейки маршрутизации однородной среды начинают процесс распространения сигналов достижимости, выставляя на всех выходах с одиннадцатого по четырнадцатый значение минимальной ненулевой континуальной величины d, а на выходах с пятнадцатого по восемнадцатый уровень континуальной величины, соответствующий собственному логическому адресу (ЛА). Ячейки, получив сигналы достижимости и логические адреса от соседних ячеек, осуществляют выбор минимального сигнала достижимости из тех, которые соответствуют максимальному логическому адресу. Направление приема минимального сигнала достижимости записывается в таблицу маршрутизации в ячейку памяти с адресом, соответствующим логическому адресу минимального сигнала достижимости. Далее минимальный сигнал достижимости увеличивается на величину d и вместе с соответствующим логическим адресом передается во все направления, при этом сигналы достижимости, не соответствующие максимальному логическому адресу, не рассматриваются. Через промежуток времени Tmax ячейкой маршрутизации, инициировавшей распространение сигнала достижимости, вырабатывается сигнал сброса (выходы с седьмого по десятый ячейки маршрутизации), с помощью которого выходы с одиннадцатого по четырнадцатый и с пятнадцатого по восемнадцатый всех ячеек маршрутизации принимают нулевое значение, тем самым возвращаясь в исходное состояние. Таким образом, таблицы маршрутизации всех ячеек маршрутизации корректируются с учетом сменившихся ЛА процессорных элементов и возникших отказов каналов передачи сообщений. Об отказах каналов передачи сообщения каждой ячейке сообщается с помощью сигналов ERk (входы ячейки маршрутизации с шестнадцатого по девятнадцатый) (k Сущность изобретения поясняется чертежами, где на фиг.1 представлена функциональная схема i-ой i-ая Ячейка маршрутизации однородной среды процессорных элементов (фиг.1) содержит блок 1 выбора максимального континуального адреса, блок 2 сброса, блок 3 адресной селекции, блок 4 выбора минимальной континуальной величины, блок 5 формирования кода направления, таблицу маршрутизации 6, блок 7 коррекции направления, блок 8 коммутации сигналов достижимости, блок 9 коммутации континуального адреса, блок-сумматор 10, блок 11 источник опорных напряжений, буферный блок 12 сообщений, блок 13 коммутации сообщений, элемент “ИЛИ” 14, первый 15 и второй 16 аналого-цифровые преобразователи, входы 17-20 (аналоговые величины) континуальных адресов, входы 21-24 (аналоговые величины) сигналов достижимости, входы 25-28 сброса, вход 29 (аналоговая величина) логического адреса, вход 30 (аналоговая величина) физического адреса, вход 31 (k-разрядный цифровой вход, время распространения сигнала достижимости) управления, входы 32-35 флаги отказов окружающих линий связи, информационные входы 36-40 (h-разрядные входы) сообщений, информационные выходы 41-45 сообщений, выход 46 сигнала фатального отказа, выходы 47-50 сигнала сброса, выходы 51-54 (аналоговые величины) сигналов достижимости, выходы 55-58 (аналоговые величины) сигналов континуального адреса, причем входы 17-20 соединены с первым, вторым, третьим и четвертым входами блока 1 выбора максимального континуального адреса и вторым, третьим, четвертым и пятым входами блока 3 адресной селекции соответственно, первый выход блока 1 выбора максимального континуального адреса соединен с первым входом блока 3 адресной селекции, вторым входом блока 8 коммутации сигналов достижимости, вторым входом блока 9 коммутации континуального адреса и входом АЦП 15, выход которого соединен со вторым входом таблицы маршрутизации 6, второй выход блока 1 выбора максимального континуального адреса соединен с третьим входом блока 2 сброса, первый выход которого соединен с пятым входом блока 1 выбора максимального континуального адреса, входы 21-24 ячейки маршрутизации соединены соответственно с шестым, седьмым, восьмым и девятым входами блока 3 адресной селекции, первый, второй, третий и четвертый выходы которого соединены соответственно с первым, вторым, третьим и четвертым входами блока 4 выбора минимальной континуальной величины, а также соответственно со вторым, третьим, четвертым и пятым входами блока 5 формирования кода направления, выход блока 4 выбора минимальной континуальной величины соединен с первым входом блока 5 формирования кода направления и вторым входом блока-сумматора 10, выход которого соединен с пятым входом блока 8 коммутации сигналов достижимости, входы 25-28 ячейки маршрутизации соединены соответственно с первым, вторым, третьим и четвертым входами элемента “ИЛИ” 14, выход которого соединен с первым входом блока 8 коммутации сигналов достижимости, первым входом блока 9 коммутации континуального адреса и пятым входом блока 2 сброса, второй выход которого соединен с выходами 47-50 ячейки маршрутизации, вход 29 ячейки соединен с шестым входом блока 1 выбора максимального континуального адреса, вторым входом блока 2 сброса, третьим входом блока 8 коммутации сигналов достижимости и входом АЦП 16, выход которого соединен с шестым входом блока 13 коммутации сообщений, входы 30 и 31 ячейки соединены с первым и четвертым входами блока 2 сброса соответственно, входы 32-35 ячейки соединены с пятым, шестым, седьмым и восьмым входами блока 7 коррекции направления, седьмым, восьмым, девятым и десятым входами блока 8 коммутации сигналов достижимости, третьим, четвертым, пятым и шестым входами блока 9 коммутации континуального адреса соответственно, первый, второй, третий и четвертый выходы блока 5 формирования кода направления соединены с четвертым, пятым, шестым и седьмым входами таблицы маршрутизации 6 соответственно, первый, второй, третий и четвертый выходы которой соединены соответственно с первым, вторым, третьим и четвертым входами блока 7 коррекции направления, первый, второй, третий и четвертый выходы которого соединены соответственно со вторым, третьим, четвертым и пятым входами блока 13 коммутации сообщений, первый, второй, третий, четвертый и пятый выходы которого соединены соответственно с выходами 41-45 ячейки, входы 36-40 ячейки соединены с первым, вторым, третьим, четвертым и пятым входами буферного блока 12 сообщений, выход которого соединен с первым входом блока 13 коммутации сообщений, адресная часть сообщения с выхода буферного блока 12 сообщений поступает на первый вход таблицы маршрутизации 6, при этом первый разряд адресной части сообщения с выхода буферного блока 12 сообщений поступает на третий вход таблицы маршрутизации 6, первый, второй, третий и четвертый выходы блока 8 коммутации сигналов достижимости соединены соответственно с выходами 51-54 ячейки маршрутизации, первый, второй, третий и четвертый выходы блока 9 коммутации континуального адреса соединены с выходами 55-58 ячейки маршрутизации соответственно, пятый выход блока 7 коррекции направления соединен с выходом 46 ячейки, первый выход блока 11 источника опорных напряжений соединен с седьмым входом блока 1 выбора максимального континуального адреса, шестым входом блока 5 формирования кода направления, третьим входом блока-сумматора 10 и четвертым входом блока 8 коммутации сигналов достижимости, второй выход блока 11 источника опорных напряжений соединен с десятым входом блока 3 адресной селекции, первым входом блока-сумматора 10 и шестым входом блока 8 коммутации сигналов достижимости. Блок 1 выбора максимального континуального адреса (фиг.2) содержит элементы континуальной конъюнкции первый 59, второй 60, третий 61, четвертый 62, пятый 63, шестой 64 и седьмой 65, выход которого соединен со вторым выходом блока 1 выбора максимального континуального адреса, первый вход которого соединен с первым входом первой группы входов и первым входом второй группы входов элемента 59 континуальной конъюнкции, выход которого соединен с первыми входами первой и второй групп входов элемента 60 континуальной конъюнкции, выход которого соединен с первыми входами первой и второй групп входов элемента 62 континуальной конъюнкции, выход которого соединен с первыми входами первой и второй групп входов элемента 64 континуальной конъюнкции, выход которого соединен с первым выходом блока 1 выбора максимального континуального адреса и первым входом первой группы входов элемента 63 континуальной конъюнкции, выход которого соединен с первым входом второй группы входов элемента 65 континуальной конъюнкции, вторые входы первой и второй групп входов которого заземлены, второй, третий и четвертый входы блока 1 выбора максимального континуального адреса соединены со вторыми входами первых и вторых групп входов элементов 59, 60 и 62 континуальной конъюнкции соответственно, пятый вход блока 1 выбора максимального континуального адреса соединен с первыми входами первых групп входов элементов 65 и 61 континуальной конъюнкции, вторые входы первой и второй групп входов элемента 64 континуальной конъюнкции соединены с выходом элемента 61 континуальной конъюнкции, вторые входы первой и второй групп входов которого заземлены, шестой вход блока 1 выбора максимального континуального адреса соединен с первым входом второй группы входов и вторым входом первой группы входов элементов 61 и 63 континуальной конъюнкции, седьмой вход блока 1 выбора максимального континуального адреса соединен с первым входом второй группы входов элемента 63 континуальной конъюнкции, второй вход второй группы входов которого заземлен. Блок 2 сброса (фиг.3) содержит первый 66 и второй 67 аналого-цифровые преобразователи (АЦП), генератор одиночных импульсов 68, первый 69 и второй 72 элементы сравнения, элемент 70 “И”, элемент 73 “ИЛИ”, счетчик 71 и элемент задержки 127, причем первый и второй входы блока 2 сброса соединены с входами первого 66 и второго 67 АЦП соответственно, выход второго АЦП 67 соединен со вторым входом элемента сравнения 69, выход первого 66 АЦП соединен с первым входом элемента сравнения 69, инверсный выход которого соединен с первым выходом блока 2 сброса и первым входом элемента 70 “И”, второй вход которого соединен с выходом генератора одиночных импульсов 68, выход элемента 70 “И” соединен с управляющим входом “Start” счетчика 71, выход которого соединен с первым входом элемента 72 сравнения, выход которого соединен с первым входом элемента 73 “ИЛИ” и с входом элемента задержки 127, выход которого соединен с управляющим входом “Stop” счетчика 71, управляющий вход “Clear” которого соединен с третьим входом блока 2 сброса, четвертый вход которого соединен со вторым входом элемента 72 сравнения, пятый вход блока 2 сброса соединен со вторым входом элемента 73 “ИЛИ”, выход которого соединен со вторым выходом блока 2 сброса. Блок 3 адресной селекции (фиг.4) содержит первый 74, второй 75, третий 76 и четвертый 77 элементы континуальной конъюнкции, причем первый вход блока 3 адресной селекции соединен с первыми входами первых групп входов элементов 74, 75, 76 и 77 континуальной конъюнкции, выходы которых соединены соответственно с первым, вторым, третьим и четвертым выходами блока 3 адресной селекции, второй, третий, четвертый и пятый входы блока 3 адресной селекции соединены со вторыми входами первых групп входов элементов 74, 75, 76 и 77 континуальной конъюнкции соответственно, шестой, седьмой, восьмой и девятый входы блока 3 адресной селекции соединены со вторыми входами вторых групп входов элементов 74, 75, 76 и 77 континуальной конъюнкции соответственно, десятый вход блока 3 адресной селекции соединен с первыми входами вторых групп входов элементов 74, 75, 76 и 77 континуальной конъюнкции. Блок 4 выбора минимальной континуальной величины (фиг.5) содержит первый 78, второй 79 и третий 80 элементы континуальной конъюнкции, причем первый вход блока 4 выбора минимальной континуальной величины соединен с первым входом первой группы входов и вторым входом второй группы входов элемента 78 континуальной конъюнкции, аналогичным образом третий вход блока 4 выбора минимальной континуальной величины соединен с входами элемента 79 континуальной конъюнкции, второй вход блока 4 выбора минимальной континуальной величины соединен со вторым входом первой группы входов и первым входом второй группы входов элемента 78 континуальной конъюнкции, аналогично четвертый вход блока 4 выбора минимальной континуальной величины соединен с входами элемента 79 континуальной конъюнкции, выход элемента 78 континуальной конъюнкции соединен с первым входом первой группы и вторым входом второй группы входов элемента 80 континуальной конъюнкции, выход элемента 79 соединен со вторым входом первой группы и первым входом второй группы входов элемента 80 континуальной конъюнкции, выход которого соединен с выходом блока 4 выбора минимальной континуальной величины. Блок 5 формирования кода направления (фиг.6) содержит десять элементов континуальной конъюнкции, причем первый вход блока 5 формирования кода направления соединен со вторыми входами первых групп входов элементов 81, 82, 83 и 84, второй, третий, четвертый и пятый входы блока 5 формирования кода направления соединены с первыми входами первых групп входов элементов 81, 82, 83 и 84 соответственно, шестой вход блока 5 формирования кода направления соединен со вторыми входами вторых групп входов элементов 81, 82, 83 и 84, первые входы вторых групп входов которых заземлены, выход элемента 81 континуальной конъюнкции соединен с первым выходом блока 5 формирования кода направления и первыми входами первых групп входов элементов 85, 86 и 87 континуальной конъюнкции, выходы элементов 82, 83 и 84 соединены со вторыми входами вторых групп входов элементов 85, 86 и 87 континуальной конъюнкции соответственно, выход элемента 85 соединен со вторым выходом блока 5 формирования кода направления и первыми входами первых групп входов элементов 88 и 89, выходы элементов 86 и 87 соединены со вторыми входами вторых групп входов элементов 88 и 89 соответственно, выход элемента 88 соединен с третьим выходом блока 5 формирования кода направления и первым входом первой группы входов элемента 90, выход которого соединен с четвертым выходом блока 5 формирования кода направления, выход элемента 89 соединен со вторым входом второй группы входов элемента 90 континуальной конъюнкции, второй вход первой группы и первый вход второй группы входов элементов 85, 86, 87, 88, 89 и 90 континуальной конъюнкции заземлены. Таблица маршрутизации 6 (фиг.7) содержит мультиплексор адреса 91, элемент памяти 92, первый 93, второй 94, третий 95 и четвертый 96 элементы “И”, причем первый и второй входы таблицы маршрутизации 6 соединены с первым и вторым информационными входами мультиплексора 91 соответственно, выход которого соединен с адресным входом элемента 92 памяти, четвертый, пятый, шестой и седьмой входы таблицы маршрутизации 6 соединены соответственно с первым, вторым, третьим и четвертым выводами данных элемента памяти 92 и вторыми входами элементов 93, 94, 95, 96, выходы которых соединены с первым, вторым, третьим и четвертым выходами таблицы маршрутизации 6 соответственно, третий вход таблицы маршрутизации 6 соединен с управляющим входом мультиплексора адреса 91, управляющим входом чтения/записи элемента памяти 92 и первыми входами элементов 93, 94, 95 и 96. Блок 7 коррекции направления (фиг.8) служит для изменения направления ретрансляции сообщения в случае отказа соответствующей линии связи между ячейками маршрутизации, значения выходов блока 7 коррекции направления определяются как значения функций от входов блока 7 по следующим формулам: Блок 8 коммутации сигналов достижимости 8 (фиг.9) содержит первый 97, второй 98, третий 99, четвертый 100, пятый 101, шестой 102 и седьмой 103 элементы континуальной конъюнкции, причем первый вход блока 8 коммутации сигналов достижимости соединен с первым входом первой группы входов элемента 99 континуальной конъюнкции, выход которого соединен со вторыми входами вторых групп входов элементов 100, 101, 102 и 103 континуальной конъюнкции, выходы которых соединены с первым, вторым, третьим и четвертым выходами блока 8 коммутации сигналов достижимости соответственно, второй и третий входы блока 8 коммутации сигналов достижимости соединены с первым и вторым входами первой группы входов элемента 97 континуальной конъюнкции соответственно, выход которого соединен с первым входом первой группы входов элемента 98 континуальной конъюнкции, выход которого соединен со вторым входом второй группы входов элемента 99 континуальной конъюнкции, четвертый вход блока 8 коммутации сигналов достижимости соединен со вторым входом второй группы входов элемента 97 и первым входом второй группы входов элемента 98 континуальной конъюнкции, второй вход второй группы входов которого соединен с пятым входом блока 8 коммутации сигналов достижимости, шестой вход которого соединен с первыми входами вторых групп входов элементов 100, 101, 102, 103 континуальное конъюнкции, седьмой, восьмой, девятый и десятый входы блока 8 соединены с первыми входами первых групп входов элементов 100, 101, 102, 103 соответственно, вторые входы первых групп входов элементов 98, 99, 100, 101, 102, 103 континуальной конъюнкции заземлены, первые входы вторых групп входов элементов 97, 99 континуальной конъюнкции заземлены. Блок 9 коммутации континуального адреса (фиг.10) содержит первый 104, второй 105, третий 106, четвертый 107 и пятый 108 элементы континуальной конъюнкции, причем первый и второй входы блока 9 коммутации континуального адреса соединены с первым входом первой группы входов и вторым входом второй группы входов элемента 104 континуальной конъюнкции соответственно, выход которого соединен со вторыми входами вторых групп входов элементов 105, 106, 107 и 108 континуальной конъюнкции, выходы которых соединены соответственно с первым, вторым, третьим и четвертым выходами блока 9 коммутации континуального адреса, третий, четвертый, пятый и шестой входы которого соединены с первыми входами первых групп входов элементов 105, 106, 107 и 108 континуальной конъюнкции соответственно, второй вход первой группы входов и первый вход второй группы входов элементов 104, 105, 106, 107 и 108 заземлены. Блок-сумматор 10 (фиг.11) содержит первый 109 и второй 111 элементы континуальной конъюнкции и аналоговый сумматор 110, причем первый вход блока-сумматора 10 соединен с первым входом первой группы входов элемента 109, выход которого соединен с первым входом аналогового сумматора 110, выход которого соединен с первыми входами первой и второй групп входов элемента 111, выход которого соединен с выходом блока-сумматора 10, второй вход которого соединен со вторым входом первой группы и первым входом второй группы входов элемента 109 континуальной конъюнкции, третий вход блока 10 соединен со вторым входом аналогового сумматора 110 и вторым входом первой группы входов элемента 111, вторые входы вторых групп входов элементов 109 и 111 континуальной конъюнкции заземлены. Буферный блок 12 сообщений (фиг.12) содержит первый 112, второй 113, третий 114 и четвертый 115 элементы запрета и первый 116, второй 117, третий 118, четвертый 119 и пятый 120 электронные ключи, причем первый, второй, третий, четвертый и пятый входы буферного блока 12 соединены с информационными входами электронных ключей 116, 117, 118, 119 и 120, выходы которых соединены с выходом буферного блока 12 сообщений, отвод первого входа буферного блока 12 соединен с управляющим входом электронного ключа 116, вторым, третьим, четвертым и пятым входами элементов 112, 113, 114, 115 запрета соответственно, отвод второго входа буферного блока 12 соединен с первым входом элемента 112 запрета, выход которого соединен с управляющим входом ключа 117 и вторым, третьим и четвертым входами элементов 113, 114 и 115 запрета соответственно, отвод третьего входа буферного блока 12 соединен с первым входом элемента запрета 113, выход которого соединен с управляющим входом ключа 118 и вторым и третьим входами элементов запрета 114 и 115 соответственно, отвод четвертого входа буферного блока 12 соединен с первым входом элемента запрета 114, выход которого соединен с управляющим входом ключа 119 и вторым входом элемента запрета 115, отвод пятого входа буферного блока 12 соединен с первым входом элемента запрета 115, выход которого соединен с управляющим входом ключа 120. Блок 13 коммутации сообщений (фиг.13) содержит первый 122, второй 123, третий 124, четвертый 125 и пятый 126 электронные ключи и компаратор 121, причем адресная часть сообщения с первого входа блока 13 коммутации сообщений поступает на первый вход компаратора 121, первый вход блока 13 соединен с информационными входами ключей 122, 123, 124, 125 и 126, выходы которых соединены с первым, вторым, третьим, четвертым и пятым выходами блока 13 соответственно, второй, третий, четвертый и пятый входы которого соединены с управляющими входами ключей 122, 123, 124 и 125 соответственно, шестой вход блока 13 соединен со вторым входом компаратора 121, выход которого соединен с управляющим входом ключа 126. 1, w2) первую группу входов, а предметным переменным – (DI1, DI2) вторую группу входов. Результат операции фиксируется на выходе DO, при этом Для организации однородной среды ячейки маршрутизации (фиг.16) соединены следующим образом: выходы 56, 52, 48, 42 ячеек i-ой строки соединены со входами 19, 23, 27, 38 ячеек i-1-ой строки соответственно, выходы 57, 53, 49, 43 ячеек i-ой строки соединены со входами 18, 22, 26, 37 ячеек i+1-ой строки соответственно, выходы 55, 51, 47, 41 ячеек j-ого столбца соединены со входами 20, 24, 28, 39 ячеек j-1-ого столбца соответственно, выходы 58, 54, 50, 44 ячеек j-ого столбца соединены со входами 17, 21, 25, 36 ячеек j+1-ого столбца соответственно, выходы ячеек первой строки соединены с соответствующими входами ячеек М-ой строки, выходы ячеек М-ой строки соединены с соответствующими входами ячеек первой строки, выходы ячеек первого столбца соединены с соответствующими входами ячеек N-ого столбца, выходы ячеек N-ого столбца соединены с соответствующим входами ячеек первого столбца, таким образом организуется однородная среда с замкнутыми границами. Рассмотрим работу (i,j)-ой ячейки маршрутизации однородной среды процессорных элементов. При этом ее работу будем рассматривать во взаимосвязи с другими ячейками маршрутизации. Когда все элементы матрицы процессорных элементов находятся в работоспособном состоянии и не происходит изменения логических адресов ПЭ и ячеек маршрутизации, то подстройка таблиц маршрутизации не требуется и, следовательно, на всех выходах (i,j)-ой ячейки присутствуют нулевые сигналы. Пусть на одном или нескольких входах 36-40 ячейки появляются сообщения. На выходе буферного блока 12 сообщений формируется одно из принятых сообщений, которое поступает на первый вход блока 13 коммутации сообщения. При этом адресная часть сообщения (фиг.15) поступает на первый вход блока 6 таблицы маршрутизации. В блоке 6 с помощью единичного значения сигнала, поступившего на третий вход таблицы маршрутизации 6, осуществляется чтение кода направления из ячейки элемента памяти 92 с адресом, поступившим на первый вход таблицы маршрутизации 6. Считанный код с выходов таблицы маршрутизации поступает в блок 7 коррекции направления, где в случае отказа соответствующей линии связи (единичные сигналы, поступившие на входы 5-8 блока 7) заменяется на ортогональное направление (направление 1 меняется на 2 или 3, направление 2 меняется на 1 или 4, направление 3 меняется на 1 или 4, направление 4 меняется на 2 или 3). В случае отказа всех окружающих линий связи и невозможности исправить направление передачи сообщения на пятом выходе блока 7 выставляется единичный сигнал, сообщающий о фатальном отказе. Исправленное направление передачи сообщения поступает на входы 2-5 блока 13 коммутации сообщения. В блоке 13 сравнивается адресная часть сообщения, поступившего на первый вход блока 13, и логический адрес текущей ячейки, поступивший на шестой вход блока 13. Если они равны, т.е. приемником сообщения является соответствующий данной ячейке ПЭ, то данное сообщение фиксируется на выходе 45, в противном случае сообщение передается в направлении, соответствующем коду на входах 2-5 блока 13 и выставляется на одном из выходов 41-44 ячейки маршрутизации. Рассмотрим процесс настройки таблиц маршрутизации после перестройки процессорных элементов. Предположим, что в однородной среде в результате отказов ПЭ и перестройки структуры логические адреса некоторых ПЭ и соответствующих ячеек маршрутизации изменились. Тогда у данных ячеек на входах 30 и 29 присутствуют различные величины физического и логического адресов, что вызывает перевод текущей ячейки в активное состояние и формирование сигнала единичного уровня на первом выходе блока 2 сброса (текущая ячейка маршрутизации становиться источником распространения сигналов достижимости). При этом в блоке 2 запускается счетчик 71, значение которого увеличивается до значения Tmax, присутствующего на четвертом входе блока 2 сброса (в момент равенства значения счетчика 71 и значения Tmax происходит распространение сигнала сброса). Блок 1 выбора максимального континуального адреса функционирует следующим образом. Если на пятом входе блока присутствует единичное значение, то на первом выходе блока 1 формируется значение, равное минимальному из значений, присутствующих на входах 1-4, 6 блока 1, при этом на втором выходе будет единичное значение только если значение на первом выходе блока 1 не равно значению на шестом входе блока 1. Если на пятом входе блока присутствует нулевая величина, то на первом выходе фиксируется значение, равное минимальному из значения на входах 1-4, а на втором выходе фиксируется нулевое значение. Блок 8 функционирует следующим образом. Если на седьмом входе присутствует единица (отказ линии связи в направлении 1), то независимо от состояния других входов на первом выходе блока формируется значение максимальной континуальной величины D, аналогичное решение получается для восьмого входа и второго выхода, девятого входа и третьего выхода, десятого входа и четвертого выхода блока коммутации сигналов достижимости. При поступлении на первый вход единичного уровня сигнала сброса выходы блока 8 принимают нулевое значение. Если значения на втором и третьем входах блока равны, то на всех выходах формируется минимальная ненулевая континуальная величина d, в противном случае на всех выходах формируется значение с пятого входа блока коммутации сигналов достижимости (т.е. принятый сигнал достижимости, увеличенный на величину d). Блок 9 функционирует следующим образом. Если на третьем входе присутствует логическая единица (сигнал отказа линии связи в направлении 1), то независимо от состояния остальных входов блока на первом выходе формируется нулевая величина, аналогичное решение получается для четвертого, пятого и шестого входов и второго, третьего и четвертого выходов блока коммутации континуального адреса соответственно. Если на первый вход блока поступает единичный уровень сигнала сброса, то на всех выходах устанавливается нулевое значение, иначе на всех выходах формируется значение с второго входа блока коммутации континуального адреса. Блок 3 функционирует следующим образом. Входы 2-9 блока образуют пары, причем входы 2-5 блока образуют первые элементы пар, а входы 6-9 образуют вторые элементы пар. Каждой из четырех пар соответствует выход блока адресной селекции. Если значение первого элемента пары равно значению на первом входе блока адресной селекции, то на соответствующем выходе фиксируется значение, равное значению второго элемента пары, иначе на соответствующем выходе фиксируется значение максимальной континуальной величины D. Блок 5 функционирует следующим образом. Если значение на втором входе равно значению на первом входе блока, то на выходах блока формируется код направления 1000, иначе, если значение на третьем входе равно значению на первом входе, то на выходах формируется код направления 0100, иначе, если значение на четвертом входе равно значению на первом входе, то формируется код направления 0010, иначе, если значение на пятом входе равно значению на первом входе, то на выходах блока формируется код направления 0001, иначе на выходах блока формируется код 0000. Если на входах 17-20 текущей ячейки маршрутизации присутствуют нулевые континуальные адреса или адреса, меньшие чем логический адрес текущей ячейки, то на первом выходе блока 1 выбора максимального континуального адреса формируется логический адрес текущей ячейки маршрутизации, который поступает на первый вход блока 3, второй вход блока 6 (через АЦП), второй вход блока 8 и второй вход блока 9. При этом на втором выходе блока 1 формируется нулевой сигнал. Т.к. на втором и третьем входах блока 8 присутствуют равные значения, то на всех выходах блока 8 формируются значения величины d, которые передаются на соответствующие входы соседних ячеек маршрутизации, при этом на выходах блока 9 формируется значение, равное значению на втором входе данного блока, т.е. логический адрес текущей ячейки маршрутизации однородной среды процессорных элементов. Спустя некоторое время в ячейках маршрутизации будут возникать конфликты сигналов достижимости, распространяемые различными ячейками. В этом случае на входах 17-20 текущей ячейки будут присутствовать различные логические адреса. На первом выходе блока 1 выбора максимального континуального адреса сформируется значение, равное максимальному из присутствующих на входах 1-4 блока 1. Если на первом выходе блока 1 значение будет больше, чем логический адрес текущей ячейки, то на втором выходе блока 1 сформируется единичный сигнал, который вызовет сброс счетчика 71 в блоке 2 сброса в нулевое состояние. На выходах 1-4 блока 3 адресной селекции сигналов достижимости будут выделены сигналы достижимости, соответствующие максимальному континуальному адресу. На выходе блока 4 выбора минимальной континуальной величины сформируется значение, равное минимальному из присутствующих на входах блока 4, которое поступает на первый вход блока 5 и второй вход блока 10. На выходах 1-4 блока 5 будет сформирован код направления принятия минимального из сигналов достижимости, поступающих на входы 2, 3, 4, 5 блока 5, при этом сигнал единичной (ненулевой величины d) величины будет присутствовать только на одном выходе блока 5. Например, если минимальный сигнал достижимости в текущую ячейку маршрутизации поступил с направления 3, то на выходах блока 5 сформируется код 0010, который поступает на входы 4-7 таблицы маршрутизации 6. В таблице маршрутизации 6 код направления по нулевому сигналу, присутствующему на третьем входе, будет записан в ячейку элемента памяти 92 с адресом, выставленным на втором входе блока 6 (единичный сигнал на третьем входе блока 6 будет только в момент приема ячейкой маршрутизации сообщения, см. фиг.15). В блоке 10 значение минимального сигнала достижимости увеличивается на величину d и поступает на пятый вход блока 8 коммутации сигналов достижимости. В блоке 8 в случае отсутствия отказа линий связи (нулевые сигналы на входах 7-10 блока 8) и отсутствия сигнала сброса на первом входе блока 8 на всех выходах 51-54 сформируется величина, равная значению на пятом входе блока 8 коммутации сигналов достижимости, т.е. минимальный сигнал достижимости, увеличенный на величину d. Одновременно с этим на выходах блока 9 коммутации континуального адреса сформируются величины, равные значению на втором входе блока 9, т.е. значение максимального континуального адреса принятых сигналов достижимости. Таким образом, каждая ячейка маршрутизации будет ретранслировать сигналы достижимости ячеек с наиболее приоритетным адресом, т.е. максимальным, и записывать направление приема минимального сигнала достижимости в таблицу маршрутизации. Ячейка маршрутизации, у которой счетчик 71 в блоке 2 достигнет максимального значения Tmax (третий вход блока сброса), на выходах 47-50 формирует единичный уровень сигнала сброса, который удерживается в течение времени, достаточного для распространения по всей матричной структуре. По окончании действия сигнала сброса возобновляется процесс распространения сигналов достижимости. Следует отметить, что если отказала линия связи между ячейками маршрутизации, то с помощью блоков 8 и 9 текущей ячейки в соответствующих направлениях буду выставлены сигналы достижимости максимальной величины D и континуальный адрес нулевой величины. Это обеспечит невозможность выбора данного направления для ретрансляции сообщения. Описанный последовательно процесс функционирования на самом деле осуществляется параллельно во всех ячейках маршрутизации однородной среды процессорных элементов. Рассмотрим процесс подстройки таблиц маршрутизации для примера показанного на фиг.17. Физические (неизменяемые) адреса показаны в левом верхнем углу ячеек, а логические адреса в нижнем правом. В начальный момент логические адреса равны физическим и таблицы маршрутизации всех ячеек маршрутизации настроены без учета возможных отказов ПЭ и связей между ними. Пусть в результате отказов ПЭ с физическими адресами 2 и 10 и реконфигурации структуры ПЭ соответствующие ячейки маршрутизации с физическими адресами 1 и 11 изменили свои логические адреса на 2 и 10 соответственно. Т.к. логический и физический адреса данных ПЭ неравны, то соответствующие им ячейки маршрутизации переводятся в активный режим и начинают процесс распространения сигналов достижимости, показанный на фиг.17 (показаны первый и второй шаг распространения сигнала достижимости). Через некоторое время появляются конфликты сигналов достижимости. На фиг.18 показано, что в ячейке маршрутизации с физическим адресом 6 возник конфликт сигналов достижимости, распространяемых ячейками с логическими адресами 2 и 10. При этом на первом, втором, третьем и четвертом входах блока 1 выбора максимального континуального адреса соответствующей ячейки маршрутизации присутствуют значения 2, 0, 0, 10 соответственно, и т.к. на пятом входе блока 1 присутствует нулевой сигнал (данная ячейка не является источником распространения сигналов достижимости), то на первом выходе блока 1 формируется значение 10. На втором, третьем, четвертом и пятом входах блока 3 адресной селекции присутствуют значения 2, 0, 0, 10, а на шестом, седьмом, восьмом и девятом входах блока 3 присутствуют значения 2, 16, 16, 2. Т.к. на первом входе блока 3 значение 10, то на первом, втором, третьем и четвертом выходах блока 3 формируются значения 16, 16, 16, 2 соответственно. Следовательно, на выходе блока 4 выбора минимальной континуальной величины сформируется значение 2, а на четырех выходах блока 5 значения 0, 0, 0, 1 соответственно. Т.е. в таблице маршрутизации 6 код направления 0001 запишется в элемент памяти 92 по адресу 10. Т.к. на втором входе блока 10 присутствует значение 2, то на его выходе формируется значение 3, которое через блок 8 формируется на выходах 51 и 54 ячейки с физическим адресом 6. Одновременно с этим на выходах 55 и 58 формируется логический адрес 10. Таким образом ячейка маршрутизации осуществила адресную селекцию и продолжила распространение наиболее приоритетного сигнала достижимости (на фиг.18 показан третий шаг распространения сигнала достижимости). Далее продолжается распространение сигналов достижимости, показанное на фиг.19 (шаг 4 и 5 распространения сигнала достижимости). На фиг.20 (шаг 6 и 7) показано, что сигнал достижимости от ячейки с логическим адресом 10 распространился по всей матричной структуре, т.е. во всех ячейках маршрутизации осуществилась корректировка таблицы маршрутизации для ячейки с логическим адресом 10. Далее подобный процесс настройки таблиц маршрутизации возобновляется для ячейки маршрутизации с логическим адресом 2.
Формула изобретения
Ячейка маршрутизации однородной среды процессорных элементов, отличающаяся тем, что содержит блок выбора максимального континуального адреса, блок сброса, блок адресной селекции, блок выбора минимальной континуальной величины, блок формирования кода направления, таблицу маршрутизации, блок коррекции направления, блок коммутации сигналов достижимости, блок коммутации континуального адреса, блок-сумматор, блок источник опорных напряжений, буферный блок сообщений, блок коммутации сообщений, элемент “ИЛИ”, первый и второй аналого-цифровые преобразователи, причем первый, второй, третий и четвертый входы ячейки маршрутизации соединены с первым, вторым, третьим и четвертым входами блока выбора максимального континуального адреса и вторым, третьим, четвертым и пятым входами блока адресной селекции соответственно, первый выход блока выбора максимального континуального адреса соединен с первым входом блока адресной селекции, вторым входом блока коммутации сигналов достижимости, вторым входом блока коммутации континуального адреса и входом первого АЦП, выход которого соединен со вторым входом таблицы маршрутизации, второй выход блока выбора максимального континуального адреса соединен с третьим входом блока сброса, первый выход которого соединен с пятым входом блока выбора максимального континуального адреса, пятый, шестой, седьмой и восьмой входы ячейки маршрутизации соединены соответственно с шестым, седьмым, восьмым и девятым входами блока адресной селекции, первый, второй, третий и четвертый выходы которого соединены соответственно с первым, вторым, третьим и четвертым входами блока выбора минимальной континуальной величины, а также соответственно со вторым, третьим, четвертым и пятым входами блока формирования кода направления, выход блока выбора минимальной континуальной величины соединен с первым входом блока формирования кода направления и вторым входом блока-сумматора, выход которого соединен с пятым входом блока коммутации сигналов достижимости, девятый, десятый, одиннадцатый и двенадцатый входы ячейки маршрутизации соединены соответственно с первым, вторым, третьим и четвертым входами элемента “ИЛИ”, выход которого соединен с первым входом блока коммутации сигналов достижимости, первым входом блока коммутации континуального адреса и пятым входом блока сброса, второй выход которого соединен с седьмым, восьмым, девятым и десятым выходами ячейки маршрутизации, тринадцатый вход ячейки маршрутизации соединен с шестым входом блока выбора максимального континуального адреса, вторым входом блока сброса, третьим входом блока коммутации сигналов достижимости и входом второго АЦП, выход которого соединен с шестым входом блока коммутации сообщений, четырнадцатый и пятнадцатый входы ячейки маршрутизации соединены с первым и четвертым входами блока сброса соответственно, шестнадцатый, семнадцатый, восемнадцатый и девятнадцатый входы ячейки маршрутизации соединены с пятым, шестым, седьмым и восьмым входами блока коррекции направления, седьмым, восьмым, девятым и десятым входами блока коммутации сигналов достижимости, третьим, четвертым, пятым и шестым входами блока коммутации континуального адреса соответственно, первый, второй, третий и четвертый выходы блока формирования кода направления соединены с четвертым, пятым, шестым и седьмым входами таблицы маршрутизации соответственно, первый, второй, третий и четвертый выходы которой соединены соответственно с первым, вторым, третьим и четвертым входами блока коррекции направления, первый, второй, третий и четвертый выходы которого соединены соответственно со вторым, третьим, четвертым и пятым входами блока коммутации сообщений, первый, второй, третий, четвертый и пятый выходы которого соединены соответственно с первым, вторым, третьим, четвертым и пятым выходами ячейки маршрутизации, входы ячейки маршрутизации с двадцатого по двадцать четвертый соединены соответственно с первым, вторым, третьим, четвертым и пятым входами буферного блока сообщений, выход которого соединен с первым входом блока коммутации сообщений, адресная часть сообщения с выхода буферного блока сообщений поступает на первый вход таблицы маршрутизации, при этом первый разряд адресной части сообщения с выхода буферного блока сообщений поступает на третий вход таблицы маршрутизации, первый, второй, третий и четвертый выходы блока коммутации сигналов достижимости соединены соответственно с одиннадцатого по четырнадцатый выходами ячейки маршрутизации, первый, второй, третий и четвертый выходы блока коммутации континуального адреса соединены с выходами с пятнадцатого по восемнадцатый ячейки маршрутизации соответственно, пятый выход блока коррекции направления соединен с шестым выходом ячейки маршрутизации, первый выход блока источника опорных напряжений соединен с седьмым входом блока выбора максимального континуального адреса, шестым входом блока формирования кода направления, третьим входом блока-сумматора и четвертым входом блока коммутации сигналов достижимости, второй выход блока источника опорных напряжений соединен с десятым входом блока адресной селекции, первым входом блока-сумматора и шестым входом блока коммутации сигналов достижимости.
РИСУНКИ
MM4A – Досрочное прекращение действия патента СССР или патента Российской Федерации на изобретение из-за неуплаты в установленный срок пошлины за поддержание патента в силе
Дата прекращения действия патента: 10.11.2006
Извещение опубликовано: 20.06.2008 БИ: 17/2008
|
||||||||||||||||||||||||||
m модулей, где n – число строк, m – число столбцов, причем i-й модуль 
{1,2,3,4} – возможные направления). Если значение какого-либо из сигналов ERk равно логической “1”, то в соответствующем направлении отказ канала передачи сообщения. При этом направление 1 – горизонтально влево, 2 – вертикально вверх, 3 – вертикально вниз, 4 – горизонтально вправо. В направлении, соответствующем отказавшему каналу, выставляется сигнал достижимости (один из выходов с одиннадцатого по четырнадцатый) с уровнем континуальной величины D=M
