Ортогональная многопроцессорная система Советский патент 1993 года по МПК G06F15/16 

импульсов узла синхронизации соединен с входом синхроимпульсов узла обработки и с входом синхроимпульсов узла формирователей, р+1,р+2,...,р+п+1-выходы адреса узла обработки соединены с соответствующими входами адреса узла формирователей, а р+п-выход адреса соединен и с входом старшего разряда адреса узла синхронизации, выход ЗАПИСЬ/ЧТЕНИЕ узла обработки соединен с входом ЗАПИСЬ/ЧТЕНИЕ узла формирователей, выходы Переключение и Конец цикла блока обработки узла синхронизации соединены соответственно с од- ноименнымивходами узла формирователей, узел синхронизации состоит из D-триггера, элемента И, элемента ИЛИ и первого и второго 1К-триггеров, причем вход синхроимпульсов D-триггера, I- вход и К-вход первого К-триггера, первый вход элемента И являются соответственно входами синхроимпульсов, Конец цикла системы, Конец цикла блока обработки и старшего разряда адреса узла синхронизации, прямые выходы первого и второго IK- триггеров, инверсный выход D-триггера и выход элемента ИЛИ являются соответственно выходами Конец цикла блока обработки. Переключение, Конец цикла блока обработки инверсный и синхроимпульсов узла синхронизации, D-вход и вход синхроимпульсов Ь-триггера соединены соответственно с прямым выходом первого IK-триггера и с вторым входом элемента ИЛИ, прямой выход D-триггера соединен с вторым входом элемента И, выход элемента И соединен с первым входом элемента ИЛИ, выход которого соединен с входами синхроимпульсов первого и второго 1К-триг- геров, 1-вход первого IK-триггера соединен с К-входом и с 1-входом второго IK-триггера, узел формирователей состоит из дешифратора режима буферов, первого и второго формирователей маски, первого и второго дешифраторов канала чтения, первого и второго шинных формирователей, элемента И-НЕ, причем п информационных входов первого формирователя маски совместно с первым входом элемента И-НЕ образуют вход адреса узла формирователей, при этом первый вход элемента И-НЕ соответствует старшему p+n+1-разряду адреса, входы нулевого разряда и первого разряда дешифра- тора режима буферов являются соответственно входами Переключение и ЗАПИСЬ/ЧТЕНИЕ узла формирователей, второй и третий входы элемента И-НЕ являются соответственно входами синхроимпульсов и Конец цикла блока обработки инверсный узла формирователей, выходы первого и второго формирователей маски

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

шинного формирователя и второго шинного формирователя, информационные входы первого формирователя маски соединены с соответствующими информационными входами второго формирователя маски,

них, соответствующие р+1, р+2,,,.,р+ /3-раз- рядам адреса, соединены также с входами первого и второго дешифраторов канала чтения, причем/ 1од2П, если logan G N, и /J ent 1од2п+1, если logan N+, где М -множество положительных целых натуральных чисел и ent Iog2n - целая часть login, выходы первого и второго дешифраторов канала чтения соединены соответственно с информационными входами первого и второго

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

Сопоставительный анализ с прототипом показывает, что заявляемая ортогональная многопроцессорная система отличается наличием новых узлов и элементов: п-входоврго элемента И в системе и по узлу синхронизации и узлу формирователей

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

Сравнение заявляемого решения с другими техническими решениями показывает,

что для реализации алгоритмов численных методов решения систем уравнений широко используются вычислительные системы класса SIMD (единственный поток команд - множественный поток данных). Однако в

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

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

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

На фиг.1 представлена структурная схема многопроцессорной системы; на фиг,2 - структурная схема блока обработки информации; на фиг.З и 4 приведены соответственно структурная схема узла синхронизации и узла формирователей; на фиг.5 показан формат адресной команды блока обработки: на фиг.б и 7 приведены форматы адресных частей команд обращения к буферам памяти соответственно с циклом записи информации и циклом чтения информации; на фиг.8 показана блок-схема программы решения системы m алгебраических уравнений методом простых итераций на однопроцессорной ЭВМ; на фиг.9 - блок- схема программы одной из п параллельных ветвей алгоритма решения той же системы и тем же методом на заявляемом устройстве; фиг. 10 иллюстрирует форму и временные параметры синхроимпульсов.

Многопроцессорная система (фиг. 1) содержит блоки 1(1), 1(2),..,,1(п) обработки информации, матрицу n x n двухпортовых блоков 2 памяти и элемент И 3. Здесь и в дальнейшем е скобках, которые следуют сразу после номеров позиций, указан порядковый номер одинаковых по своему фун- кциональному назначению блоков. Последовательность двух арабских цифр, разделенных запятой и заключенных в круглые скобки,указывает на положение буфера памяти в матричной структуре. Просто цифрой в скобках обозначены номера линий в шине, Входы блоков, узлов и элементов расположены на левых сторонах, а их выходы - на правых сторонах соответствующих позиций. Нумерация как входов, так и выходов идет сверху вниз. В тех случаях, когда указанный порядок нумерации нарушается, вход или выход пронумерован отдельной цифрой в скобках. Входы и выходы всех

0 блоков и узлов поименованы по названию сигналов и имеют краткое обозначение, приведенное в табл.1.

Каждый блок 1(1) обработки предназначен для программной реализации части ал5 горитма, выполняемого системой, и осуществления взаимодействия с другими процессорами системы. Арифметико-логи- ческие операции, выполняемые блоками обработки, производятся над М-разрядными

0 двоичными операндами. Он содержит (фиг.2) формирователь 4 синхроимпульсов, узел 5 синхронизации, узел 6 обработки и узел 7 формирователей.

В систему команд блока обработки вхо5 дит стандартный набор операций: арифметико-логические операции, операции управления, к которым отнесены операции безусловного и условного переходов и обращение к подпрограммам, и операции вво0 да/вывода. Кроме того, для осуществления синхронизации обмена в систему команд блока обработки введена команда POST. Операцией обмена может служить любая адресная команда блока обработки при ус5 ловии, что ее адресная часть заключена в определенном абсолютном диапазоне значений. В блоке обработки допустимо использование любой системы адресации. Так как в Нем отсутствуют специальные коман0 ды обмена, то часть адресного диапазона отведена для обращения к буферам памяти и процедурой обмена является процесс обращения посредством адресной команды в определенную фиксированную область па5 мяти в абсолютном фиксированном диапазоне адресов. Для иллюстрации использована адресная система команд. На фиг.5 изображен возможный формат М-раз- рядной адресной команды, в котором разря0 ды 0-(р+п+1) отведены под адрес, а разряды (p+n+2)-(N-1) - под код операции, при этом имеется в виду, что емкость буфера составляет 2Р+1 слов. Единица в старшем р+п+1- разряде адреса служит признаком

5 обращения к блокам памяти, младшие р+1 разрядов отведены для кодирования ячейки в блоке памяти. В адресной части команды записи в блоки памяти (фиг.б) (р-1МР+т) разряды адреса предназначены для маски- рования блоков памяти, в которые

необходимо записать заданный операнд. В адресной части команды с циклом чтения из блоков памяти (фиг.7) (р+1)-(р+/3)-разряды адреса предназначены для кодирования номера блока памяти, причем / logan, если logan € , и /3 em logan+l, если logan ЈN.

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

Номер nij блока 1(j) обработки в системе нумерации блоков 1(1) обработки определяется из соотношения

ПН

j n - i Ч-j при. j j - I при i j .

При записи информации i-м блоком обработки в блоке памяти адресная часть команды записи определяется из соотношения

At 2Р(2

п+1

+ 2

j i

где

л Л 1. если бсуществляетсязапись в блок 2 ( l,j ). . ™ . 1 0 , если запись в блок 2(i.j) не производится;

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

При чтении информации i-м блоком обработки из ячейки с номером а блока 2(1 ,j) памяти адресная часть команды определяется из соотношения

AIJ 2(2 + nij - 1)+ а.

Все примеры, которые далее приведены, относятся к частному случаю системы. Каждый блок обработки ее имеет 24-разрядную команду, в которой под адресную часть отведены 16 разрядов. Четыре младших из них предназначены для кодирования ячейки блока памяти, т.е. р 3 и наибольшее допустимое число блоков обработки в системе при такой разрядности адресной части команды n 11.

В качестве примера производятопреде- ление адресной части команды записи информации в 13-ю ячейку блоков 2(4,2), 2(4,5), 2(4,7) и 2(4,11) памяти.

Вычисляют по формуле (1) относительные номера блока обработки 2, 5, 7 и 11 в системе нумерации четвертого процессора:

гц,2 11-4 + 2 9;

гц,5 5-4 1;

(Н7 7-4 3;

гн,11 11-4 7.

5По формуле (2) определяют адресную часть команды записи

A4 23(2t2 + 29 + 21+23 +

+ 27)+13io 945Di6,

Для чтения четвертым блоком обработ- 10 ки записанного в 13-ю ячейку блоков 2(4,2), 2(4,5), 2(4,7) и 2(4,12) памяти операнда необходимо последовательно производить чтение с использованием адресных команд с циклом чтения информации из памяти. При 15 этом адресные части команд чтения инфор- . мации из блоков 2(4,2), 2(4,5), 2(4,7) и 2(4,11) памяти определяются из соотношения (3) и соответственно равны

А4.2 24(211 + 9 - 1) + 13ю - 808D16: 20 А4 5 2(211 + 1 - 1) -МЗю - 800Di6:

А4.7 2Т211 + 3-1) + 13ю 802Di6;

A4.11 2 (211 + 7 - 1) + 13ю 806D16.

Блок 2(i,j) памяти является двухпортовой памятью с двумя тристабильными дву- 25 направленными информационными выходами, которые на структурной схеме являются соответственно частью входа АУД1 Вх для порта 1 и частью входа АУД2Вх из порта 2. На каждый из названных входов, 30 кроме того, поступают (рН)-разрядные адреса и сигналы ЗАПИСЬ/ЧТЕНИЕ. Он предназначен для записи, чтения и хранения информации и является частью ОЗУ соответствующих ему двух процессоров систе- 35 мы. Доступ к блоку 2(i,j) памяти через порт 1 имеет блок 1(1) обработки и через порт 2 - блок 1(j) обработки.

Формирователь 4 синхроимпульсов предназначен для формирования синхро- 40 импульсов и выполнен по типовой схеме (см. Микропроцессоры./Под ред. чл.-корр. АН СССР Л.Н.Преснухина. М.: Высшая школа, 1986, книга 2. Средства сопряжения. Контролирующие информацией но-управля- 45 ющие системы, с,270, рис.2,26).

Узел 5 синхронизации (фиг.З) предназначен для фиксации сигнала Конец цикла блока обработки, формирования сигнала Переключение и длительности положи- 50 тельной фазы синхроимпульсов, Он состоит из D-триггера 13, элемента И 14, элемента ИЛИ 15 и К-триггеров 16(1) и 16(2).

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

кончая отдельными операционными узлами типа матричного умножителя, которые однако обеспечивают формирование необходимого набора управляющих сигналов, адреса и операнда на их выходах. Одним из возможных вариантов арифметико-логического устройства, устройства управления, памяти данных и программ являются схемы, описанные в упомянутой монографии (с.270-284, рис.2.28, 2.32, 2.33, 2.35).

Узел 7 формирователей (фиг.4) предназначен для формирования сигналов выборки соответствующих блоков памяти как функции от значений разрядов адреса Ар-и - Ар+п-м, а также сигналов ЗАПИСЬ/ЧТЕНИЕ, Переключение и Конец цикла блока обработки инверсный. Он содержит дешифратор 8 режима буферов, формирователи 9(1) и 9(2) маски, дешифраторы 10(1) и 10(2) канала чтения, шинные формирователи 11(1) и 1 1(2), элемент И-НЕ 12. В качестве формирователей маски использованы шинные формирователи с инверсией (типа 589 АП 26).

Для иллюстрации работы системы рассмотрим процесс решения на ней методом простых итераций системы линейных уравнений вида

Х ВХ + Ь,(4) где В - заданная числовая квадратная матрица n-го порядка;

В 6 Rm - заданный вектор (свободный член).

Итерационная последовательность векторов строится по формуле

Хк + b, К 1,2,...(5)

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

.к

x -J;

Х,р

i 1

где Х|к + bi;

BI - числовая матрица размерности mi x х гл;

bi 6 R1711 - заданный вектор (свободный член).

Вектор Xi имеет компоненты Хгоуи,

Xf(.v..Xf(|)tm.

f(i)

i -1

2) mj при i 1 I 1 О при ,

причем Ј т - гл. i 1

Следовательно, решение системы 3 лег- ко распараллелить таким образом, чтобы вычисление каждого 1-го вектора осуществлялось в i-м блоке обработки информации, Для определенности полагают, что mi 2P+1. На фиг.8 и 9 приведены для сравнения блок-схемы решения системы (4) на однопроцессорной и заявляемой системе соответственно. Решение системы (4) на однопроцессорной ЭВМ осуществляется в соответствии с блок-схемой на фиг.8. В бло- ке 1 (К-1)-у вектору присваивается начальное значение, в блоке 2 происходит определение К-х компонент вектора по формуле (5). в блоке 3 осуществляется сравнение нормы вектора с заданным числом и.

если выполняется условие ,1хк.хк-1,, е

то происходят выдача результата и окончание программы, в противном случае (К-1)-у вектору присваивается значение вычисли- тельного К-ro вектора и весь цикл вычислений повторяется, начиная с блока 2. Перед тем как рассматривать решение системы (4) на заявляемой системе рассматривают основные принципы ее межпроцессорного об

мена.

Блок 1(1) обработки в зависимости от состояния системы имеет доступ к блокам памяти или только i-й строки, или только i-ro столбца матрицы. Блоки 1(1) и 1(|) обработки

взаимодействуют только через блоки 2(1, j) и 2(j, I) памяти. Для обращения к блокам 2(1, J) и 2Q, I) памяти в блоке 1(1) обработки используется один и тот же интервал адресов. Обращение к блхжам памяти можно

осуществлять любой адресной арифметико- логической операцией (а не командами вво- да-вывода). Все блоки обработки информации в любой произвольный момент времени могут иметь доступ либо только к

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

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

строке на доступ к столбцу осуществляется в системе синхронно.

В заявляемой системе при решении системы (4) каждый j-й блок обработки информации выполняет в соответствии с блок-схемой программы, приведенной на

фиг.9, предназначенную ему часть общесистемного алгоритма, функционируя параллельно с остальными блоками обработки, вычисляя при этом на каждом шаге итерации пгн компонент вектора и обмениваясь ими с другими блоками обработки. Назначение двух первых блоков аналогично назначению двух блоков уже рассмотренной выше блок-схемы на фиг.8 и отличается лишь числом вычислительных компонент. В блоке 3 осуществляется запись вычисленных компонент в блоки памяти для использования их другими блоками обработки информации на следующем шаге итерации. В блоке 4 происходит выполнение единст- венного оператора POST, исполнителем которого блок обработки информирует систему об окончании им данной итерации и готовности приступить к выполнению следующей. Выполнение каждой новой итера- ции начинается одновременно всеми блоками системы по исполнении оператора POST на предыдущей итерации последним блоком обработки информации, т.е. тем блоком обработки, каждая итерация которого требует наибольшего времени (если таковая существует). В общем случае каждый блок обработки информации после исполнения им оператора POST (кроме блока обработки, выполнившего оператор POST последним) и начала новой итерации некоторый промежуток времени to находится в режиме ожидания, Режим ожидания осуществляется аппаратными средствами. С точки зрения программиста блок обработки после испол- нения оператора POST переходит сразу к выполнению блока 5 без каких-либо промежуточных прбграммных процедур, связанных с режимом ожидания. Назначение блоков 5, 6 и 7 соответствует блокам 3, 4 и 5 рассмотренной выше блок-схемы на фиг.8. Единственная их особенность состоит в том, что часть необходимых компонент, вычисленных остальными блоками обработки информации,считывается из соответствующих блоков памяти.

Система адресных команд блока обработки, как уже отмечено, имеет особенность, связанную с определением исполнительного адреса при обращении к блокам памяти. Эта особенность заключается в том, что каждая ячейка блока памяти имеет некоторый абсолютный адрес AIJ в адресном пространстве 1-го блока обработки и абсолютный адрес AJI в адресном про- странстве j-ro блока обработки, причем в общем случае AIJ AJI. Методика вычисления этих адресов описана выше.

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

Мнемоническое обозначение оператора записи операнда в память имеет вид ST ADR, по исполнении которого операнд, находящийся в аккумуляторе процессора, записывается по адресу, определяемому символическим именем ADR.

Оператор одновременной записи операнда i-м блоком обработки в блоки 2(1, J1), 2(i, j2)...2(i, jl) памяти по адресу А имеет вид

STMA(i, j1,j2,...jl) + A,

Так, запись Т МА (3, 1, 4, 7) + 6 предписывает третьему блоку обработки запись операнда, находящегося в его аккумуляторе, в шестую ячейку блоков 2(3,1), 2(4,4) и 2(3,7) памяти.

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

ADDMA(i,j) + A,

который предписывает j-y блоку обработки сложить содержимое своего аккумулятора с содержимым А-й ячейки блока 20, j) памяти и результат поместить в аккумулятор.

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

Обратимся к решению системы (4) на заявляемой многопроцессорной системе. При выполнении блоков 1 и 2 блок-схемы на фиг.9 каждый блок обработки информации работает автономно и его функционирование не имеет отличий от функционирования обычной однопроцессорной ЭВМ. Формирователь 4 синхроимпульсов каждого блока обработки формирует последовательность синхроимпульсов с параметрами Т и tn (фиг. 10). При этом параметры синхроимпульсов различных блоков обработки могут быть различны. С выхода формирователя синхроимпульсов (фиг.2) синхроимпульсы поступают на вход СИВх узла 5 синхронизации. Если в выполняемой операции нет обращения к блокам памяти, то синхроимпульсы, пройдя по цепям узла синхронизации, подаются с его выхода СИВых на вход СИВх узла б обработки. Узел обработки, который построен по классической схеме процессора, выполняет операции в соответствии с программой, хранящейся в его памяти программ. При реализации блока 3 происходит засылка вычисленных компонент вектора каждым блоком обработки в те блоки памяти, которые указаны в поле операнда соответствующих инструкций записи, При этом нет необходимости в предварительном программном анализе состояния загружаемых блоков памяти. Строго говоря, загрузку компонент вектора лучше производить прямо по мере их вычислений при реализации блока 2 данной программы, но для того, чтобы подчеркнуть особенность загрузки и раскрыть нагляднее работу системы, он выделен в отдельный блок. Загрузка компонент вектора осуществляется под управлением оператора.

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

Блок 1(0 обработки может осуществлять доступ при нулевом состоянии триггера 16(2) только к блокам памяти i-й строки матрицы, а при единичном состоянии триггеры 16(2) только к блокам памяти i-ro столбца матрицы.

Так, при исполнении оператора ADD MA (3,4) + 5 блоком 1(3) обработки при нулевом состоянии его триггера 16(2) осуществляется чтение операнда из пятой ячейки блока 2(3,4) памяти, а при единичном его состоянии - из блока 2 (4,3) памяти. К блокам 2(4,3) и 2(3,4) памяти может иметь доступ и блок 1(4) обработки, но к блоку 2 (3,4) памяти блок 1(4) обработки имеет доступ при единичном состоянии его триггер 16(2), к блоку 2(4,3) памяти - при нулевом его состоянии. Таким образом, для любой произвольной пары блоков обработки существует доступная только им единственная пара блоков памяти, через которую они и осуществляют обмен информацией.

В процессе начальной установки триггеры 16(2) всех блоков обработки информации

устанавливаются в нулевое состояние, и тогда каждый блок обработки имеет доступ к блокам памяти соответствующей строки, при этом в системе не существует блока

памяти, доступ к которому имели бы более одного блока обработки. При таком состоянии триггеров 16(2) каждый блок обработки начинает выполнение программы (фиг.9) на первой итерации, завершив запись необхо0 димых компонент в блоки памяти соответствующей строки, каждый блок обработки исполнением оператора POST выдает единицу на соответствующий вход элемента И 3, на выходе которого по окончании каждой

5 очередной итерации вырабатывается единичный сигнал, который каждый раз опроки- дывает триггеры 16(2) всех блоков обработки, заменяя тем самым доступ блока обработки к соответствующей строке на до0 ступ к соответствующему столбцу или наоборот, так что вторую операцию каждый блок обработки начинает с выполнения блока 5 при единичном состоянии его триггера 16(2), и возможностью доступа к соответст5 вующему столбцу блоков памяти, в которых уже произведена запись необходимых компонент вектора, вычисленных остальными блоками обработки и необходимых блоку обработки при реализации блоков 5 и 6 про0 граммы.

К примеру, если блоком 1(4) обработки в процессе выполнения блока 3 на нечетной итерации необходимо записать одну из компонент в 15-ю ячейку блоков 2(4.2), 2(4,4),

5 2(4,5), 2(4,7) и 2(4,11) памяти, то это достигается исполнением оператора ST МА (4, 2, 5, 7, 11)+ 15,

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

0 П4.2 11-4 + 2 9; П4.4 11 -4 + 4 11; П4.5 5 - 4 1; П4,7 7-4 3; 04.11 11-4 7;

5

А4

оЗ/

2°( + 211 + 21 + 23 +

+ 27)+ 1510 D45Fi6.

На очередной четной итерации, выполняя блоки 5 и 6, блоки 1(2), 1(4), 1(5). 1(7) и 1(11) обработки используют эту компоненту, 0 Пусть каждый из них загружает ее в свой аккумулятор исполнением соответственно операторов

LDMA(2,4)+15;

LD MA (4,4) + 15; 5LD MА (5,4)+15;

LD МА(7,4)+15;

LDMA(11,4)+15.

Адресные части соответствующих команд загрузки вычисляют в соответствии с той же методикой.

П2.4 4-2 2;

rt4.4 11-4 + 4 11;

П5.4- 11 - 5 + 4 10;

п.4 11 - 7 + 4 8;

пц,4 11 - 11 +4 4;

А2 4 24(1211 + 2-1)+ 15 801F;

А4.4 2(211 + 11 1)+ 15io 80AFi6;

А54 24(211 + Ю- 1)+ 15io 809Fi6;

А 4 2Т211 + 8 - 1) + 15ю 807Fi6;

Ац,4 2Д211 +4-1)+ 15io 803Fi6.

На четной итерации блок 1(4) обработки командой STD 45 F записывает компоненту уже в блоки 2(2,4), 2(4,4), 2(7,4) и 2(11,4) памяти. Блоки 1(2), 1(4), 1(5), 1(7) и 1(11) обработки исполнением команд соответственно LD 801 F, LD 80AF, LD 809F, LD 807F и LD 803F на очередной итерации загружают ее в свои аккумуляторы. Таким образом осуществляется обмен информацией между блоками обработки,

Чтобы перейти к работе блоков, узлов и элементов системы, остановимся вкратце на методике, которую используют при этом рассмотрении. Блок обработки для заявляемой системы может быть получен на базе практически любого известного процессора путем некоторой его модернизации. Для этой цели выделяют в нем два основных узла: формирователь синхроимпульсов и узел обработки, К этим двум узлам добавляют новые узлы, которые позволяют функционировать блоку обработки в системе и не оказывают никакого влияния на исходную систему функций процессора. Чтобы стало возможным функционирование блока обработки в системе, в его систему команд введена команда синхронизации (оператор POST) и перераспределено адресное пространство, часть которого отведена для обращения к блокам памяти. Поэтому остановимся на специфических для функционирования системы операциях, оставив вне рассмотрения весь спектр вопросов, связанных с функционированием процессора фон-неймановского типа. Такими операциями являются операции с циклом обращения к блокам памяти и команда синхронизации. Специфика обращения к блокад памяти посредством адресных команд является спецификой использования адресной части команды, которая не имеет отражения в их микропрограммах.

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

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

При таком рассмотрении функционирование узла обработки может быть представлено табл.2. В ней весь набор адресных

0 команд блока обработки заменяют значением сигнала З/Ч (ЗАПИСЬ/ЧТЕНИЕ), который определяет режим работы памяти при выполнении той или иной адресной команды. Причем режим чтения имеет место при

5 З/Ч 1, а режим записи - при .

Выход АВых разбит на четыре группы, каждая из которых несет определенную функциональную нагрузку, Ар+п+1 - это старший разряд адреса, значение которого, рэв0 ное единице, в нашем случае является признаком обращения к блокам памяти. Нулевое значение старшего разряда адреса является признаком обращения процесса к своей локальной памяти, которое выпадает

5 из рассмотрения. Как видно из табл.2, при исполнении оператора POST на выходе КЦПВых узла обработки формируется сигнал нулевого (неактивного) уровня. На двунаправленном выходе данных АВых узла 6

0 устанавливается операнд, который при 3/4 1 передается из блока памяти в узел 6 и при З/Ч 1 - из узла 6 в блок памяти.

Узел 5 синхронизации (фиг.З) работает следующим образом.

5В исходном состоянии триггеры 13, 16(1) и 16(2) установлены в нулевое состояние, при котором синхроимпульсы, подаваемые на СИВх узла синхронизации и далее на один из входов элемента ИЛИ 15, на

0 другой вход которого подается нулевой уровень с выхода элемента И 14, поступают беспрепятственно на выход СИВых узла синхронизации. Одной из функций узла синхронизации является блокирование в неко5 торыхслучаях прохождения синхроимпульсов, которое может осуществлять D-триггер 13 подачей сигнала единичного уровня на один из входов элемента И 14, на другой вход которого подается значе0 ние Ар+п+1 старшего разряда адреса с узла 6 обработки, В случае формирования на выходе элемента И 14 единичного уровня он далее поступает на один из входов элемента ИЛИ 15, формируя на выходе последнего

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

Другой функцией узла синхронизации является формирование сигнала Переключение, которое осуществляет триггер 16(2).

При этом сигнал Конец цикла блока обработки единичного уровня, формируемый в узле обработки в процессе исполнения оператора POST, подается на КЦПВх узла синхронизации, откуда он подается на счетный вход (объединенные I- и К-входы) триггера 16(2) и всякий раз опрокидывает его, подключая тем самым к блоку обработки либо строку, либо столбец блоков памяти.

Последней функцией узла синхрониза- ции является фиксация сигнала Конец цикла блока обработки, осуществляемая триггером 16(1) путем подачи единичного (активного) уровня этого сигнала на 1-вход этого триггера, что устанавливает триггер 16(1) в единичное состояние. Кроме того, единичный уровень с выхода триггера 16(1), воздействуя на D-вход триггера 13, устанавливает его в единичное состояние. В исходное (нулевое) состояние триггер 16(1), а следовательно, и триггер 13 устанавливаются сигналом Конец цикла системы единичного уровня, формируемым на выходе элемента ИЗ.

Функции узла формирователей следую- щие. В режиме записи информации в блоки памяти происходят инвертирование и передача (р+1)-(Р+п Разрядов адреса (маски) в зависимости от значения сигнала Переключение либо на выходы ВСтрВых, либо на выходы ВСтбВых. В режиме чтения информации из блоков памяти происходят дешифрация содержимого (р+1)-(р+ +/3)-разрядов адреса и выдача результата дешифрации в зависимости от значения сиг- нала Переключение либо на выходы ВСтрВых, либо на выходы ВСтбВых.

Формирователи 9(1), 9(2) маски и шинные формирователи 11(1), 1.1(2) совместно с дешифратором 8 образуют коммутатор с од- ной линии на четыре, работа которого определяется табл.3. Формирователи 9(1) и 9(2) маски функционируют в режиме записи информации в блоки памяти, шинные формирователи 11(1) и 11(2) - в режиме чтения информации из блоков памяти,

Режим работы формирователей 9(1) и 9(2) маски, шинных формирователей 11(1) и 11(2) задает дешифратор 8 режима буферов, на адресные входы которого подаются сиг- налы Переключение и ЗАПИСЬ/ЧТЕНИЕ, формируемые соответственно в узле 5 синхронизации и узле 6 обработки. Каждая из четырех возможных комбинаций этих сигналов активизирует один из формирователей 9(1), 9(2), 11(1) и 11(2), что иллюстрирует табл.3. Дешифратор 8 стробируется сигналом ST КЦПИЛСИЛ Ар-п+1, поступающим с выхода элемента И-НЕ 12 на его стробиру- ющий вход.

В-режиме записи информации (З/Ч 0) содержимое (р+1)-(Р+п)-разрядов адреса с входов АВх узла формирователей подается на информационные входы формирователей 9(1) и 9(2) маски. В зависимости от значения сигнала Переключение содержимое этих разрядов инвертируется и выдается либо на ВСтрВых, либо на ВСтбВых процессора. Напомним, что сигнал Переключение меняет свое значение после каждого исполнения оператора POST.

В режиме чтения информации из блока памяти (р+1)-(р+/3)-разряды адреса поступают на входы дешифраторов 10(1) и 10(2), с выхода которых результат дешифрации подается на информационные входы соответственно шинных формирователей 11(1) и 11(2), В зависимости от значения сигнала Переключение результат дешифрации поступает либо на ВСтрВых, либо на ВСтбВых узла формирователей.

Рассмотрим работу процессора в целом с учетом рассмотренных выше функций его отдельных узлов. Синхроимпульсы, формируемые формирователем 4 синхроимпульсов, поступают на СИВх узла 5 синхронизации, и если триггер 13 узла синхронизации установлен в ноль, то синхроимпульсы передаются на СИВых узла 5, откуда они подаются на СИВх узла 6 обработки, обеспечивая его функционирование в соответствии с программой, и на вход СИВх узла 7 формирователей, в котором они обеспечивают необходимые временные соотношения сигналов выборки, выдаваемых на ВСтрВых и ВСтбВых процессора. При выполнении всех адресных операций А0 - Ар и сигнал ЗАПИСЬ/ЧТЕНИЕ выдаются соответственно с АВых и З/Ч Вых узла обработки на АУДВых процессора, Ар+1 - Ap+n+i с АВых узла обработки поступают на АВх узла формирователей.

В режиме записи информации в блоки памяти разряды адреса Ар-1 - Ар+п, в которые помещается маска, инвертируются и выдаются на ВСтрВых при нулевом уровне сигнала Переключение и на ВСтбВых при единичном его уровне, на выходах АУДВых кроме указанных выше сигналов устанавливается N-разрядный операнд, что в совокупности обеспечивает его запись в те блоки памяти, не входы выборки которых поступает сигнал выборки нулевого уровня.

В режиме чтения информации с блоков памяти в узле 7 формирователей осуществляется дешифрация Ар-1 - результат дешифрации поступает на ВстрВых при нулевом уровне сигнала Переключение и на ВСТВых при единичном его уровне, обеспечивая выборку одного блока памяти, oneранд с которого поступает на АУДВых процессора, При нулевом значении стробирую- щего сигнала СТ на выходе элемента И-НЕ 12 выходы формирователей 9(1} и 9(2) маски шинных формирователей 11(1) и 11(2) оста- ются в высокоимпедансном состоянии.

В цикле исполнения оператора POST на КЦПВых узла обработки устанавливается сигнал единичного уровня, который, поступая на КЦПВхузла 5 синхронизации, выпол- няет следующие функции: формирует новое значение сигнала Переключение, которое с ПВых узла синхронизации подается на ПВх узла 7 формирователей, зафиксированный триггером в узле 5 синхронизации он поступает на КЦПВых и далее на один из входов элемента И, информируя таким образом систему об окончании очередной итерации и готовности выполнения новой итерации, переводит процессор в режим ожидания тем, что блокирует прохождение синхроимпульсов на СИВых узла синхронизации.

Сигнал Конец цикла системы, формируемый элементом И 3, поступает на КЦСВх блока обработки, который является и одноименным входом узла синхронизации, сбра- сывает сигнал Конец цикла блока обработки в узле синхронизации, восстанавливая тем самым прохождение синхро- импульсов на его СИВых.

Рассмотрение функционирования блоков памяти целесообразно проводить в контексте функционирования системы в целом, тем более что, как условлено выше, специ- фическими системными операциями (мнемоническое имя ST) считают вс е операции с циклом чтения информации из блоков памяти и операцию, реализующую оператор POST и связанное с ее исполнением форми- рование системного сигнала Конец цикла системы, которым завершается выполнение очередной итерации или шага интегрирования в системе.

При .выполнении любой адресной one- рации 1-м блоком обработки на его выходах АУДВых устанавливаются значение адреса АО - Ар, сигнал ЗАПИСЬ/ЧТЕНИЕ, которые по соответствующей шине подаются на АУД1Вх всех блоков памяти i-й строки мат- рицы и на входы АУД2Вх всех блоков памяти 1-го столбца матрицы. Кроме того, в режиме записи информации на выходе АУДВых процессора устанавливается М-разряд- ный операнд, который по упомянутой шине одновременно поступает на АУД1Вх всех блоков памяти i-й строки матрицы и на АУД2Вх всех блоков памяти i-ro столбца матрицы, при этом сигнал ЗАПИСЬ/ЧТЕНИЕ принимает значениеуровня логического О.

Если запись операнда осуществляется в блоки памяти 1-й строки матрицы, то инвертированное значение маски устанавливается на выходах ВСтрВых i-ro блока обработки, каждый разряд которого поступает на вход выборки порта 1, соответствующего данному разряду маски блока памяти i-й строки матрицы. При этом во все блоки памяти, на вход выборки порта 1 которых поступает сигнал нулевого уровня, осуществляется запись одного и того же операнда и по одному и тому же адресу (режим трансляции).

Если запись операнда осуществляется в блоки памяти 1-го столбца матрицы, то инвертированное значение маски устанавливается на выходах ВСтбВых 1-го блока обработки, каждый разряд которого поступает на вход выборки порта 2, соответствующего данному разряду маски блока памяти i-ro столбца матрицы. При этом во все блоки памяти, на вход выборки порта 2 которых поступает сигнал нулевого уровня, осуществляется запись операнда.

В режиме чтения информации вырабатываемый сигнал ЗАПИСЬ/ЧТЕНИЕ принимает значение, равное логической 1. Если при этом i-й блок обработки информации осуществляет чтёние.из i-й строки матрицы, то результат дешифрации (р+1)-(р+/ -разрядов адреса устанавливается на выходах ВСтрВых блока обработки. Тогда на входе АУД1 Вх блока памяти, на вход В1 Вх которого подан сигнал нулевого уровня, устанавливается записанный в соответствующей ячейке операнд, который по соответствующей шине данных подается на АУДВых блока обработки. Заметим, что двунаправленные выходы данных блока обработки и двунаправленные входы данных порта 1 блока памяти выполняют соответственно функции входов данных блока обработки и выходов данных порта 1 соответствующего блока памяти.

Аналогично в режиме чтения информации из блока памяти i-ro столбца матрицы результат дешифрации (р-1)-(р+Д)-разрядов адреса устанавливается на выходах ВСтбВых блока обработки, а считанный из соответствующего блока памяти операнд поступает на шину данных с входа АУД2Вх, по которой он далее поступает на АУДВых блока обработки.

В режиме исполнения инструкции POST на выходе КЦПВых блока обработки устанавливается единица, которая предварительно запоминается в узле синхронизации

и меняет значение сигнала Переключение. С выхода КЦПВых блока обработки сигнал КЦП единичного уровня поступает на один из входов элемента И 3, после чего блок 1(1) обработки, если он не является в системе последним блоком обработки, выдавшим сигнал КЦП, переходит в режим ожидания. Как только последний блок обработки выдает сигнал КЦП на соответствующий вход элемента И 3, на выходе элемента И 3 формируется сигнал КЦС единичного уровня, который свидетельствует об окончании очередной итерации (шага интегрирования) в системе. Этот сигнал поступает на КЦСВх всех блоков обработки, сбрасывает в ноль триггеры, которые хранили сигнал КЦП, разблокирует прохождение синхроим- пульсов на узлы обработки, начиная тем самым новую итерацию (шаг интегрирования).

(56) 1.Мультипроцессорные системы и параллельные вычисления./Под ред.Эпслоу, М.: Мир, 1976, с.62.

2. Патент Японии № 61-55706, кл. G 06 F 15/16, опублик. 1989.

15

Таблица 1

1

2

3

4

1

2

3

4,

Вход синхроимпульсов

Прямой выход

Узел обработки

Вход синхроимпульсов

Выход Конец цикла блока обработки

Выходы адреса

Двунаправленные выходы данных

Выход ЗАПИСЬ/ЧТЕНИЕ

Узел формирователей

Вход Переключения

Входы адреса

Вход ЗАПИСЬ/ЧТЕНИЕ

Вход синхроимпульсов

Вход Конец цикла блока обработки

инверсный

Выходы Выборка в столбце

Выходы Выборка в строке

Дешифратор режима буферов

Вход нулевого разряда

Вход первого разряда

Вход стробирования

Первый выход

Второй выход

Третий выход

Четвертый выход

Формирователь маски

Информационные входы

Вход выборки

Выход

Дешифратор канала чтения Адресные входы

Выходы

Шинный формирователь

Информационные входы

Вход выборки

Выходы Блок памяти Вход Выборка порта 1

Продолжение тэбл. 1

4 СИВх

СИВх

КЦПВых

АВых

ДВых

3/ЧВых

ПВх

АВх 3/ЧВх СИВХ

КЦПИВх ВСтбВых ВСтрВых

ИВх ВВх Вых

АВх Вых

ИВх ВВх

Вых

В1Вх

X - безразличное состояние.

Z - состояние высокого импеданса.

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

Продолжение табл. 1

Таблица 2

Таблица 3

информации соединен с входами Выборка первого порта блока памяти i-й строки матрицы блоков памяти, выход Выборка в столбце 1-го блока обработки информации соединен с входами Выборка второго порта блоков памяти 1-го столбца матрицы блоков памяти, отличающаяся тем, что, с целью повышения производительности системы за счет обеспечения обмена данными между всеми блоками обработки ин- 0 формации за один такт работы системы, в нее введены n-входовый элемент И, выход которого соединен с входами Конец цикла системы всех блоков обработки информации, выход Конец цикла блока обработки

информации i-ro блока обработки информации соединен с i-м входом п-входового элемента И.

5 0 n 5 0

5

0

5

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

fft)

W

w

W)

т

Wn

t)

№t)

Ы

ID

fa-iT

Iki

if)

r-f)

fn-rt

W)

ft)

(n)

глЗ

(I)

Wi

т

a

ш

10Ж

fai,

w

$4

Pui.Z

/00Я/оКод операцииАдресная час/ль

Фиг.5

8

ffff)

LJ

признак обращения к блоком памяти

Признак обращения к блокам памяти

s /

Не использу- Номер ютсяблока памяти

Фиг. 7

МАСКА

Адрес ячейки блока памяти

Фиг. 5

/Г Адрес ячейки Ј 5локе

памяти

Q/avajo)

Определение компонент

Выдача $ результата

С Началоj

Определение компонея/я

tfK . у угДГ

v/W / rffi)t,..., V/)

Запись ломломемп

Xf(iH, xt(i)t,.... а)тч В djioKt/ памяти