Однородная вычислительная структура

 

ОДНОРОдаАЯ ВЫЧИСЛИТЕЛЬНАЯ СТРУКТУРА, содержащая столбец из и операционных ячеек и m столбцов из п коммутационных ячеек, каждая из которых включает элемент ИЛИ и два элемента И, первые входы которых соединены с выходом элемента ИЛИ той же коммутадионной ячейки, вьпсод первого элемента И i-й коммутационной ячейки каждого столбца () подключен к первому ёхрду элемента ИЛИ

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И 0THPbfTMA (21 ) 3492460/24-24 . (22) 22.09.82 (46) 30.06.85. Бюл . !! 24 (72) А.С.Ильин (53) 681.325(088.8) (56 ) Фет Я.И. Параллельные процессоры для управляющих систем, М.:

Энергоиэдат, 1981, с. 21-31, рис.ll.

Авторское. свидетельство СССР

У 66179 3, кл. Н 03. К 17/00, (Н 03 К 17/02),!979. (54)(5?) ОДНОРОДНАЯ ВЫЧИСЛИТЕЛЬНАЯ

СТРУКТУРА, содержащая столбец иэ и операционных ячеек и m столбцов иэ и коммутационных ячеек,,каждая из которых включает элемент ИЛИ и два элемента И, первые входы которых соединены с выходом элемента ИЛИ той же коммутационной ячейки, выход первого элемента И i-й коммутационной ячейки каждого столбца (l i n-1) подключен к первому входу элемента

ИЛИ (i+1)-й коммутационной ячейки того же столбца, выход второго элемента И i-й коммутационной ячейки

J-ro столбца (16)

-соединен с вертикальным входом функ:ционального элемента (i+1) и операционной ячейки, .а выход первого элемента И i-й операционной ячейки подключен к второму входу элемента

„„SU„„11 4713 А

4р1> <: 06 Е 1!/20 Н 0 3 К 17/00

ИЛИ i-й коммутационной ячейки первого столбца, о т л и ч а ю щ а— я с я тем, что, с целью повышения надежности, каждая коммутационная ячейка включает элемент НЕ, а каждая операционная ячейка включает третий элемент И и элемент НЕ, вход и выход которого соединены соответственно с выходом состояния функционапьного элемента и вторым входом первого элемента И той же операционной ячейки, первый и второй входы элемента ИЛИ каждой операционной ячейки подключены к выходам соответственно второго и третьего элементов

И той же операционной ячейки, первые входы второго и третьего элементов

И каждой операционной ячейки соединены соответственно с выходом состоя-. ния функционального элемента и выходом элемента НЕ той же операционной ячейки, вторые входы второго и третьего элементов И i-й операционной ячейки, кроме первой подключены соответственно к выходу элемента ИЛИ (i-1}-й операционной ячейки И, к вертикальному выходу функционального элемента i — и операционной ячейки, выход состояния функционального элемента i-й операционной ячейки соединен с вторым входом первого. элемента И и входом элемента НЕ (i-g) é коммута- ° ционной ячейки J-ro столбца, выход элемента НЕ каждой коммутационной ячейки подключен к второму входу вто. рого элемента И той же ячейки, выход второго элемента И i-коммутационной ячейки п-го столбца соединен с горизон-. тальным входом функционального элемента ii+m)-й операционной ячейки, 11647 3

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

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

На фиг. 1 представлена блок-схема предлагаемой однородной вычислитель- !5 ной структуры, на фиг. 2 — Ълок-схема операционной ячейки, на фиг, 3— блок-схема коммутационной ячейки, на фиг.4 — структурная схема функционального элемента, на фиг.5- блок-схема предлагаемой однородной вычислительной структуры с укаэанными s качестве примера неисправными операционными ячейками и полученными при перестройке направлениями потоков информа-25 ции между исправными ячейками.

Формула изобретения и фиг. 1, 2, 3, 5 составлены для удобства восприятия в наиболее простом варианте, когда функциональный элемент переда- 30 ет информацию толЬко по одному каналу и только в одну сторону в каждом из направлений: вертикальном и горизонтальном (слева направо и сверху вниз)

Под эту формулу подпадают и более

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

40 совмещая квадратики функционапьных элементов) .

Однородная вычислительная структура (фиг. 1) содержит столбец из п операционных ячеек 1 и m столбцов из

45 п коммутационных ячеек 2 (m=5) .

Каждая операционная ячейка (фиг.2) содержит функциональный элемент 3, элемент ИЛИ 4, элементы И 5-7, эле мент НЕ 8.

Каждая коммутационная ячейка (фиг. 3) содержит элемент ИЛИ 9, элементы И 10 и 11, элемент HE 12;

Первые входы элементов И 10 и 11 каждой коммутационной ячейки 2 сое- 55 динены с выходом элемента ИЛИ 9 той же ячейки, выход элемента И 10 1 -й коммутационной ячейки каждого столб. ца (I

g-ro столбца (I+g

ИЛИ 9 i — и коммутационной ячейки 2 первого столбца, выход элемента НЕ 8 каждой операционной ячейки 1 соеди,нен с первыми входами элементов И 6 и 7 той же ячейки, вторые входы которых соединены соответственно с горизонтальным и вертикальным выходами функционального элемента 3 той же ячейки, выход состояния которого соединен с входом элемента НЕ 8 и вторым входом элемента И 5 той же

i-й ячейки, а также с вторым входом элемента И 10 и входом элемента

И 12 (i-g)-й коммутационной ячейки

2 ) -го столбца, выходы элементов

И 5 и 7 каждой операционной ячейки

1 соединены с соответствующими входами элемента ИЛИ 4 той же ячейки, выход элемента НЕ 12 каждой коммутационной ячейки 2 соединен с вторым входом элемента И 11 той же ячейки, выход элемента И 11 i-й коммутационной ячейки 2 m-ro столбца соединен с горизонтальным входом функционального элемента 3 (4m). — и операционной ячейки 1.

В.качестве примера функционального элемента рассмотрим-процессор модели 40 системы 360 фирмы IBM.

На фиг. 4 представлена его укрупненная структурная схема.

Процессор содержит регистры 1325, арифметико-логическое устройство 26, схему приращения 27, блок 28 основной памяти, блок 29 местной памяти, блок 30 постоянной памяти, регистр 31 адреса местной памяти, регистр 32 адреса постоянной памяти, регистр 33 адреса постоянной памяти при работе в режиме селекторного канала, регистр 34 состоя:яия, схему

) 4 декодирования 35,Имеются также интер-. вальный таймер и схема обслуживания внутренних и внешних прерываний. з 164

Выход первого программно-управляемого разряда регистра 34 состояния используем s качестве выхода состояния функционального элемента, группу 36 входов и выходов — в качестве горизонтальных и вертикальных входов и выходов. Вертикальным выходом будем считать также выход второго программно-управляемого разряда регистра 34 состояния, а соответствующим ему вертикальным входом - вход прерывания следующего по вертикали функционального элемента.

В определенные моменты времени первый исправный функциональный элемент начинает выполнять программу самоконтроля (теста). Тестовая программа начинается тем, что на выходе состояния данного функционального ,элемента устанавливается уровень

"1", как если бы данный функциональный элемент был неисправен. Если тест не завершился. из-за фактической его неисправности, то установленный уровень "1" сохраняется (память функционального элемента является неразрушаемой при отключении питания).

Сигналы с выходов состояния функциональных элементов играют роль управляющих сигналов для коммутационно-перестраивающей сети, образованной всеми логическими элементами И, ИЛИ, НЕ всех ячеек. Эта сеть отключает все неисправные функциональные элементы, направляя потоки информации обходными путями.

Если тест завершается нормально, он снимает признак неисправности и выдает сигнал прерывания следующему ниже по вертикали исправ-

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

" "l 3 4 элемента, обмен другой информации между ними запрещен, иначе информация может попасть не адресату, а его соседу.

Далее проверяется второй функциональный элемент, потому третий и т.д. до неисправного, который до этого считался исправным. Повторение таких циклов проверок обеспечивает поиск всех неисправных функциональных элементов, если они есть.

Распределение потоков информации между функциональныьм элементами производится следующим образом.

Пусть функциональный элемент 3 -й операционной ячейки 1 исправен. Тогда уровень "О" на его вы-, ходе состояния в этой ячейке закрывает элементы И 5 и через элемент HE 8 открывает элементы И 6 и 7, пропускающие информацию с горизонтального и вертикального выходов данного функционального элемента 3, а в (1-J) é коммутационной ячейке 2 J — го столбца закрывает элемент И 10 и через элемент НЕ 12 открывает элемент И 11 пропускающий в горизонтальном направлении инфор ацию, принимаемую элементом ИЛИ 12 с любого из двух направлений — горизонтального или вер тикал ьн о го .

При неисправном функциональном элементе 3 в i-й операционной ячейке элементы И 6 и 7 изолируют его выходы, элемент И 5 обеспечивает передачу информации по вертикали в обход неисправного функционального элемента 3, а в (i-J) é коммутационной ячейке информация передается по вертикали через элемент И 10.

Таким образом получено распре— деление потоков информации, указанное в качестве примера на фиг. 5 для случая, когда неисправны функциональные элементы 3 перечеркнутых операционных ячеек 1. Отсюда видно, что потоки информации (покаI эано стрелками) обходят неисправные функциональные элементы также и по горизонтали, причем между всеми испр авными функциональными элемен-. таля сохраняется спиралеобразная структура взаимосвязей.

По сравнению с прототипом данная однородная вычислительная струк

ll64713

1<(123 3 с

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

43 =0

Заметим, что функция (+31

F, () - K „,, p обладает свойствами:

1р 0 3

,(р)=:Ср =

1Р

F (F)= . " - — " зе еее,»(F(с А F» »е(P> е е ар е: ар»

После дифференцирования и подстановки получаем тура обладает более высокой надежностью sa счет того, что ее спиралеобразное построение позволяет отключать только неисправные функциональные элементы и оставлять в . S работе все исправные функциональные элементы, сохраняя между ними спиралеобразную структуру взаимо.связей.

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

Принятые обозначения: .ql - на, дежность функционального элемента 15 при выполнении основных функций в .. заданной области применения; надежность логических элементов операционной ячейки; цк - надежность коммутационной ячейки; k — количе- 20 ство операционных ячеек, необходимое при работе в заданной области применения, f. — количество резервных операционных ячеек (n=k+f).

Вероятность того, что операцион- 5 ная ячейка вышла из строя, сохраняя при этом способность перемкнуть себя по вертикальным входам-выходам, а коммутационные ячейки отключили данную операционную ячейку; 30 3 1 q3

Вероятность того, что операционная ячейка и соответствующая ей стрбка коммутационных ячеек являются исправными

J

F = — --е K. с

0 (l P)K K. К е. („Р)»с

При бесКонечном количестве резерв. ных ячеек имеем (е К .ВЕщ Р

О1 8 (Р)к

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

Пусть, например Ре =Р . Это соотношение можно испольэовать в качестве уравнения, решаемого относительFIo величинык . В развернутом виде имеем

С P =

Решение этого уравнения воэмож(2) но, только если правая часть не меньше единицы. Дпя этого необходимо выполнение условий:

Я

2 с((1)

-.(е-sg, ° .(, Применимость данного технического решения ограничена также условием. Ре,которое означает, что надежк

1 ность данной пер естр аиваемой одно. » родной вычислительной структуры должна быть не хуже надежности эквивапентной матричной однородной вычислительной структуры, лишенной возможности перестройки. Для этого не об ходи мо выполи ение у сл овий; (з) (4)

g2 (g ° с (с, (1 т Ъ " 9 с которые оказываются строже условий (1) и (2).

Матричную однородную вычислительную структуру, выбранную за прототип, можно рассматривать как частный случай данной спирапеобраэной однородной вь1чиспительной структуры: каждая строка с количеством ячеек ш рассматривается как одна укрупненная ячейка с надежностью основных функций я и надежностью перемыкания по вертикальным входамвыходам q ; количество укрупненных

2 ячеек k/m; коммутационные ячейки отсутст вуют, Следовательно, для прототипа можно записать

1 прот

Положительный эффект P Р, достигается при

rn

„,,„j ц,„(5)

Условие (5) строже условия (3) при

164713 (T 2 1 тп т 2 (6) Индукцией по рп нетрудно доказать, что дробь в (5) меньше единицы, а дробь в (6) больше m-й степени дро- . би в (4 ).

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

I164713

1164713

Составитель Г. Виталиев

Редактор Л.Авраменко Техред М.Пароцай Корр е к т ор М. Самбор ская, Заказ а188/46 Тираж 710 Подпи сное

ВНИИПИ Государственного коьытета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал IIIIII "Патент", г. Ужгород ул. Проектная, 4 1