Однородная вычислительная структура Советский патент 1985 года по МПК G06F11/20 H03K17/00 

I Изобретение относится к вычислительной технике и может быть использ вало при построении однородных вычислительных структур и сред, удовле воряющих заданным требованиям надежности и живучести. Цель изобретения - повышение наде ности однородной вычислительной стру туры путем спиралеобразного построения, обеспечивающего отключение толь ко неисправных ячеек, сохраняя при этом спиралеобразную структуру взаимосвязей меАду исдтравными ячейками. На фиг. 1 представлена блок-схема предлагаемой однородной вычислительной структуры; на фиг. 2 - Ълок-схема операционной ячейки, на фиг. 3 блок-схема коммутационной ячейки; на фиг.4 - структурная схема функционального элемента; на фиг.5- блок-схема предлагаемой однородной вычислительной структуры с указанными в качестве примера неисправными операционными ячейками и полученными при перестройке направлениями потоков информ ции между исправныьм ячейками. . Формула изобретения и фаг, 1,2, 3, 5 составлены для удобства восприятия в наиболее простом варианте, когда функциональный элемент передает информацию только по одному канаа и только в одну сторону в каждом из направлений: вертикальноми горизонтапьном (слева направо и сверху вниз Под эту формулу подпадают и более сложные варианты, когда производится многоканальная передача информации в обе стороны в каждом из этих направлений (достаточно перевернуть чертежи и наложить их на исходное,совмещая квадратики функциональных элементов). . Однородная вычислительная структура (фиг. 1) содержит столбец из п операционных ячеек 1 и ш .столбцов из п коммутационных ячеек 2 (). Каждая операционная ячейка (фиг.2 содержит функциональный элемент 3, элемент ИЛИ 4, элементы И 5-7, элемент НЕ 8. . . - . Каждая коммутационная ячейка (фиг. 3) содержит элемент ИЛИ 9, эле менты И 10 и П , элемент НЕ 12. Первые входы элементов И 10 и 11 каждой коммутационной ячейки 2 соединены с выходом элемента ИЛИ 9 той же ячейки, выход элемента И 10 i -и коммутационной ячейки каждого столб132ца (l iin-l) соединен с первым входом элемента РЛИ 9 (1+1)-й коммутационной ячейки того же столбца, выход элемента И 11 i-й коммутационной ячейки J-ro столбца ( li Jim-I ) соединен с вторым входом элемента ИЛИ 9 i-й коммутационной ячейки (j+l)-ro столбца, выход элемента ИЛИ 4 i -и операционной ячейки 1 соединен с вертикальным входом функционального элемента 3 и первым входом элемента И 5 ()-й операционной ячейки 1, выход элемента И 6 i-ой операционной ячейки 1соединен с вторым входом элемента ИЛИ 9 i-й коммутационной ячейки 2 перйого столбца, выход элемента НЕ 8 каждой операционной ячейки 1 соединен с первыми входами элементов И 6 и 7 той же ячейки, вторые входы которых соединены соответственно с горизонтальным И вертикальным выходами функционального элемента 3 той же ячейки, выход состояния которогй соединен с входом элемента НЕ 8 и вторым входом элемента И 5 той же i-й ячейки, а также с вторым входом элемента И 10 и входом элемента И 12 (i-j)-и коммутационной ячейки столбца, выходы элементов И 5 и 7 каждой операционной ячейки 1 соединены с соответствующими входами элемента ИЛИ 4 той же ячейки, выход элемента НЕ 12 каждой коммутационной ячейки 2 соединен с вторым входом элемента И И той же ячейки, выход элемента И 11 i-й коммутационной ячейки 2 т-го столбца соединен с горизонтальным входом функционального элемента 3 ()-й операционной ячейки 1. В качестве примера функционального элемента рассмотрим процессор модели 40 системы 360 (Ьирмы IBM. На фиг. 4 представлена егоукрупненная структурная схема. Процессор содержит регистры 1325, арифметико-логическое устройство- 26, схему приращения. 27, блок 28 основной памяти, блок 29 местной памяти, блок 30 постоянной памяти, регистр 31 адреса местной памяти, регистр 32 адреса постоянной памяти, регистр 33 адреса постоянной памяти при работе в режиме селекторного канала, регистр 34 состояния, схему декодирования 35.Имеются также интер-вальный таймер и схема обслуживания внутренних и внешних пр1грываний. 3 Выход первого программно-управля емого разряда регистра 34 состояния используем в качестве выхода состояния функционального элемента, гр пу 36 входов и выходов - в качестве горизонтальных и вертикальных входо и выходов. Вертикальным выходом будем считать также выход второго про граммно-управляемого разряда регист ра 34 состояния, а соответствующим ему вертикальным входом - вход пр ерывания следующего по вертикали фун ционального элемента.; В определенные моменты времени первьй исправный функциональный эл мент начинает выполнять программу моконтроля (тест а). Тестовая програ ма начинается тем, что на выходе состояния данного функционального .элемента устанавливается уровень 1, как если бы данный функционал ный элемент был неисправен. Если тест не заверпился. из-за фактической его неисправности , то установл ный уровень 1 сохраняется (памят функционального элемента является неразрушаемой при отк.пючении питания) . Сигналы с выходов состояния фун циональных элементов играют роль управляющих сигналов для коммутационно-перестраивающей сети, образованной всеми логическими элементами И, ИЛИ, НЕ всех ячеек. Эта сеть отключает все неисправные фун циональные элементы, направляя потоки информации обходными путями. Если тест завершается нормально, он снимает признак неисправнос ти и вьщает сигнал прерывания следующему ниже по вертикали исправному функциональному элементу в обход неисправных, если они бьши отключены ранее. По сигналу прерЫвЪния вызывается программа когирования информации из него в проверен ный функциональный элемент, чтобы тоже начать проверяться, а проверенный функциональный элемент за- меняет по основной работе следующий проверяемый, В это время количество функциональных,элементов, считающихся исправными, увеличивается на единицу, а потом опять уменьшается, Соответствукяцим-образом меняется структура их взаимо связей, В эти интервалы времени, отсчитываемые с помощью таймеров,. в составе каждого функционального 134 элемента, обмен другой информации между ними запрещен, иначе информация может попасть не адресату, а его соседу. Далее проверяется второй функциональный элемент, потому третий и т.д. до неисправного, который до этого считался исправным. Повторение таких циклов проверок обеспечивает поиск всех неисправных функциональных элементов, если они есть. Распределение потоков информации- между функциональными элементами производится следующим образом. Пусть функциональный элемент 3 Ч-й операционной ячейки 1 исправен. Тогда уровень О на его вы-, ходе состояния в этой ячейке закрывает элементы И 5 и через элемент НЕ 8 открывает элементы И 6 и 7, пропускающие информацию с горизонтального и вертикального выходов данного функционального элемента 3, а в (i-j)-й коммутационной ячейке 2 j-ro столбца закрывает элемент И 10 и через элемент НЕ 12 открывает элемент И II, пропускающий в горизонтальном направлении инфорацию, принимаемую элементом ИЛИ 12 с любого иэ двух направлений - горизонтального или вертикального. При неисправном функциональном ; элементе 3 в i-й операционной ячейке элементы И 6 и 7 иэолируют его выходы, элемент И 5 обеспечивдет передачу информации по вертикали в обход неисправного функционального элемента 3, а в (i-j)-й коммутационной ячейке информация передается по вертикали через элемент И 10, Таким образом получено распределение потоков информации , указанное в качестве примера на 4иг. 5 для случая, когда неисправны функциональные элементы 3 перечеркнутых операционных ячеек 1, Отсюда видно, что потоки информации (показано стрелками)обходят неисправные функциональныеэлементы также и по горизонтали, причем между всеми исправными функциональными элемен TaNM сохраняется спиралеобразная структура взаимосвязей. По сравнению с прототипом данная однородная вычислительная струк 5 тура обладает более высокой надежностью за счет того, что ее спиралеобразное построение позволяет отключать только неисправные функциональные элементы и оставлять в работе все исправные функциональные элементы, сохраняя между ними спиралеобразную структуру взаимосвязей. Расчет надежности и условий при менения предлагаемой однородной вы числительной структуры производится следующим образом. Принятые обозначения: q - надежность функционального элемента при выполнении основных функций в заданной области применения; q надежность логических элементов оп рационной ячейки; q надежность коммутационной ячей1Ш ; k - количество операгщонных ячеек, необходим при работе, в заданной области прим нения; - количество резервных оп рационных ячеек (). . Вероятность того, что операцион ная ячейка вьшша из строя, сохраня при этом способность перемкнуть се бя по вертикальным.входам-выходам а коммутационные ячейки отключили данную операционную ячейку; :. ,Н,-яГ. Вероятность того, что операцион ная нчейка и соответствующая ей ст ка коммутационных ячеек являются исправными, 1ГП Яг зНадежность однородной вычислите ной структуры равна суммарной веро ности всех ее рабЬтоспбсобнык неза висимых состояний, различаемых по количеству задействованных резервных ячеек: Заметим, что функция S) k} (I обладает свойствами: После дифференцирования и подст новки получаем Р, О-р) o -- C-P) При бес онечном количестве резервных ячеек имеем -eiff, рр Принимаемое на практике ограничение на количество рез ервных ячеек должно снижать надежность однородной вычислительной структуры соразмерно снижению ее надежности, обусловленному ненадежностью коммутационных ячеек. Иначе говоря,нет смысла запасаться резервными ячейками, если вероятность их использования мала. Пусть, например Рр РОС. соотношение можно использовать в качестве уравнения, решаемого относительно величины. Вразвернутом виде имеем Решение этого уравнения возможно, только если правая част не мень7 ше единицы. Для этого необходимо выполнение условий, ш.. (2) 2. HI . Применимость данного технического решения ограничена также условием. ,которое означает, что надежность данной перестра гваемой однородней вычислительной структуры должна быть не хуже надежности эквивалентной матричной однородной вычислительной структуры, лишенной возможности перестройин. Для этого необходимо выполнение условий . (З) .лГ Яикоторые оказываются строже условий (1).и.(2), . Матричную однородную вычислительую структуру, выбранную за проотип, можно рассматривать как частый случай данной спиралеобразной днородной вычислительной структуы: каждая строка с количеством чеек m рассматривается как одна крупненная ячейка с нгщежностью

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

Следовательно, для прототипа можно записать

- (

и-()на1

00

прот Положительный эффект Р Р

00 ДООэ

стирается при

m

Q

Л

0-v)c},))

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

при

164713

(6)

11-нТ-чТ

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

Кроме повышения надежности , данное техническое решение обеспечивает сокращение аппарат5фных затрат за счет того, что сравнительно простые коммутационные ЯЧЕЙКИ обеспечивают подключение резервных операционных ячеек в количестве,, равном количеству отказавших ячеек, и уст- раняют необходимость подключать стро- ку резервных ячеек вместо строки, ячеек исправных, кроме одной.

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

иг.1

gjui.2

фи.5