Многопроцессорная система

 

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

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

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

РЕСПУБЛИК (5в 4 С 06 F 15/00 15/16

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

H А BT0PCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4235581/24-24 (22) 23. 04. 87 (46) 07.03.89. Бюл. У 9 (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) В.Е.Золотовский, Р.В.Коробков, Л.Ф.Карпенко и А.К.Степанян (53),681 325(088.8) (56) Авторское свидетельство СССР

У 438015, кл. G 06 F 15/00, 1974 °

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

9 608160, кл. G 06 Р 15/00, 1978.

Энелоу Ф. Г. Мультипроцессорные системы и параллельные вьиисления.

N. 1976. с. 261.

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

Цель изобретения - повышение быстродействия за счет параллельной обработки команд.

На фиг. 1 изображена многопроцессорная система, для случая четырех процессоров (К = 4), на фиг. 2 — процессор многопроцессорной системы на фиг, 3 — блок многовходовых буферных регистров; на фиг. 4 — устройство управления; на фиг. 5 — узел оповещения первого типа; на фиг. 6 — узел оповещения второго типа, на фиг. 7— временная диаграмма работы.

„„80„„3464168 . А1 (54) МНОГОПРОЦЕССОРНАЯ СИСТЕМА (57) Изобретение относится к области вычислительной техники и может быть использовано при построении цифровых многопроцессорных систем высокого быстродействия. Целью изобретения является повышение быстродействия.

Многопроцессорная система содержит

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

Процессорная система (фиг. 1) содержит процессоры 1-4 с первого по ця четвертый, первый коммутатор 5<, вто- ф рой коммутатор 5, блоки 6, -64 .лв- ф мяти (программ), счетчики 7, -74, блок р

8 постоянной памяти (ПЗУ), блоки 91— 94 многовходового буферного регистра, входящие в состав соответственно с первого по четвертый процессоров.

Процессор (фиг. 2) содержит арифметико-логическое устройство 10 (АЛУ), умножитель 11, делитель 12, коммутатор 13, первый 14 и второй 15 блоки памяти, блок 16 регистров, первый 17 и второй .18 регистры, первое 19 и второе 20 индексные арифметические устройства, третий 21, четвертый 22 и пятый 23 регистры, память

24 данных, первый демультиплексор

1464168

25, устройство 26 управления и второй демультиплексор 27.

Блок многовходовых буферных ре"... гистров (фиг. 3) содержит первый элемент И 28, первый многорежимный регистр 29, первый узел 30 оповещения первого типа, второй элемент

И 31, второй многорежимный буферный регистр 32, второй узел 33 оповещения первого типа, третий элемент

И 34, третий многорежимный буферный регистр 35, третий узел 36 оповещения первого типа, дешифратор 37 и узел 38 оповещения второго типа. 15

Устройство управления (фиг. 4) содержит регистр 39 команды, счетчик

40, память 41 микрокоманд, регистр

4 2 микрокоманд, узел 43 управления и генератор 44 синхроимпульсов. 2р

Узел оповещения первого типа (фиг. 5} содержит первый элемент

И 45 первый тристабильный ключ 46, первый 47 и второй 48 триггеры, второй элемент И 49, второй тристабиль- 25 ный ключ 50, третий элемент И 51 и элемент 52 задержки.

Узел оповещения второго типа (фиг. 6) содержит первый элемент

И 53, первый тристабильный ключ 54, щ первый 55 и второй 56 триггеры, второй элемент И 57, элемент 58 задержки, второй тристабильный ключ 59 и третий элемент И 60.

В работе многопроцессорной системы можно выделить два режима: занесение начальной информации, работа.

-В первом режиме из внешних устройств, в качестве которых могут быть ЭВМ, устройство ввода (дисплей, ввод с перфоленты или перФокарты) или внешняя память (диски, магнитная лента}, заносятся программа и данные, подлежащие обработке. Программная информация записывается в блоки па,мяти следующим. образом. По внешней шине команд поступает команда. Формат поступающей команды следующий: К старших бит, где K — число блоков программной памяти, отводится под управление записью (первый бит управ- 50 ляет записью в первый блок, второй— во второй и т.д.), остальные биты— собственно команда.

Адрес поступает по адресной шине команд. По отношению к внешнему устройству шина команд и шина адреса являются одной шиной. Разделение шины производится по пространственному принципу (разряды с j-го К-й подключаются к внешней шине команд системы, а остальные — к адресной шине, 1, как правило, равно нулю).

Коммутатор .5 работает следующим образом.

Информация, поступающая на его вход, поступает на один из выходов в с зависимости от кода, поступающего на его управляющие входы. При этом в качестве управляющих берутся значения четырех старших разрядов адресной шины. Наличие "1" в i-м разряде подготавливает включение цепи вход — 1 и выход коммутатора 5, Окончательно цепь формируется тогда, когда на первом управляющем выходе i-ro процессора (i .= 1,n) отсутствует сигнал, т.е. он равен нулю. Если сигнал равен единице на управляющем выходе

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

Допустим, что i = 2, тогда адрес поступает на адресный вход второго блока 6 (программной) памяти. Одновременно по внешней шине команд поступает команда, которая должна быть записана в блок 6 памяти. Внешняя шина команд помимо разрядов, по которым передается само командное слово, содержит еще К разрядов, по которым передается управляющая информа» ция. Каждый отдельный разряд связан только с одним входом записи соответствующего блока программной памяти.

Например, первый разряд кодового сло- ва связан с первым блоком 6 (прог-=., раммной) памяти, второй - с блоком

6, третий — с блоком 6, и т.д. Это позволяет легко совместить управление записью и коммутацию, т.е. хотя данные поступают на все блоки одновременно, но запись происходит только в один блок. В то же время при необходимости информация может бьггь размножена, т.е. одна и та .же команда записана в несколько блоков (программной) памяти. Так как одновременная запись и считывание запрещены в блок памяти команд, то считывание

1464

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

5 на соответствующий вход коммутатора.

Аналогично осуществляется запись начальных данных в процессоры. Сами данные поступают по внешней шине данных, а номера ячеек в памяти данных — по .адресной шине данных. Такая организация записи программ и данных позволяет осуществить виртуальные режимы работы памяти программ и памяти данных. Для организации виртуальных режимов любая память разбивается на несколько страниц (в минимальном случае — две}. Запись информации ведется в отработанную страницу °

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

Общая система команд разбивается íà 25 четыре группы: А1, А2, АЗ, А4. Первая группа команд включает в себя только те команды, которые требуют для своего выполнения только один процессор, вторая группа — два, третья — три и четвертая — четыре.

Для выполнения программа разбивается на К ветвей (в нашем случае — четыре). Разбиение желательно проводить так, чтобы каждая ветвь по ко:мандам группы А1 выполнялась парал35 лельно. Код группы Ai (старшие два бита кода операции) равен 00. Команды из блоков памяти (программ) считываются одновременно по сигналу с выходов 1, 2, 3 и 4> процессоров

1-4. Если это все команды группы А1, то на выходе блока 8 постоянной памяти формируется управляющий код, по которому коммутатор 5 настрайва45 ется: i-й вход íà i-й выход, т.е. выход первого блока программной памяти — на вход 1 первого процессора, второго — на вход 2 второго и т.д. Таким образом, каждый процессор выполняет свою команду.

Рассмотрим выполнение команды в первом процессоре. Команда поступает с выхода 1 на вход устройства 26 управления (фиг. 2). Код команды и

55 признаки адресации поступают на память микропрограмм как начальный адрес микропрограмм. Адреса данных через шины данных поступают в индексные

168 о арифметические устройства,9 и 20, где формируются физические адреса ячеек памяти данных. В процессоре имеется три памяти: регистровая 16, оперативная 24 и блока многавходавсго буферного регистра 9. Регистрова" и оперативная являются внутренней памятью, поэтому обращение к ним не вызывает останова вычислительного процессора по отсутствию данньас, так как в указанной памяти хранятся на- чальные данные и промежуточные результаты предыдущих вычислений.

В та же время работа с памятью связи существенно отличается ат работы с внутренней памятью прежде всего тем, чта готовность данных,пня дальнейшего вычисления априори неизвестна. Поэтому блок многавхадc Hcãа буферного регистра снабжается специальными семафорами, катсрые в::адят в угль; оповещения (фиг. 3).

Рассмотрим, как осуществляется передача данных между двумя процес=. сарами, например между вторым (источник} и первым (приемник). Для нередачи используется специальная ко" манда. Эта команда позволяет указать адрес передаваемого даннога. Пусть, например, необходимо произвести умножение двух чисел с последующей псредачей результата в другой проц=-.ссор. Фрагмент программы имеет вид

УМН <- 3 А1; Р, А2

ПЕР— 56 П, 01, А2

Здесь 3, Р, П вЂ” признаки адресации (3 — память 24 данных, Р— блок

16 регистров, П вЂ” блок мнагавхадавых буферных регистров, 01 — указатель номера процессора, в данном случае первого), А1, А2 — адреса.

Прн выполнении команды умножения код операции и признаки адресации поступают в счетчик адреса (фиг.4).

Сформированный адрес поступает на

ПЗУ микракоманц, и начинается выполнение микрОпрограммы. В первом такте осуществляется передача, первого адреса в память данных в регистр 21 адреса, а второго — в регистр 17 адреса блока 16 регистров. Кроме того, осуществляется наращивание адреса в программной памяти на единицу. Ва втором такте осуществляется считывание данных и запись их в регистры умножителя 1 1 и запуск е г о на выполнение операции. В третьем такте осуществляется запись результата в блок

16 регистров к регистр 23 связи (э регистр связи записывается результат выполнения любой опера1н-.и) к, кроме того, в третьем такте осуществляется запись следующей команды в устройство 26, Этой командой в данном случае является команда передачи (ПЕР).

В первом такте вь".IIO;Iнения команды

ПЕ1 адрес из поля А2 к 2манды запк=ь3вается в адреснь2е реги .тры всех блоков многовходовых буфе 2вых внешних регистров, но суабатьгз ° эт только тот, который соответствует коду 01, т.B. блок внешних pBгкстро:2 I.Bp:3oI о Iipo цессора.

При записи адреса одновремепнo формируется сигнал счк "шва гкя значения семафоров, которые хранятся пз тому же адресу,что и данные. Считанный семафор записываег я в триггеры

47 к 48 (фиг. 5). Если в тркггерах хранится код 01 — запи.ь разрешена (код 00 сотгве "cTvyBT запрещению к записи к считьп3ак2ия, блс ки 2овка процессора; 0, — запи.::ь разрешена, счкть|вание эапрещенО > 1 0 = запись запрещена, счк гывание 2 эрешено.

11 — запись и считывание. разрешены без ограничения),, тo †. ри подаче в следующем такте сигнал-.. записи на вход 3п формируется сигнал записи, которыи поступает на t3 I(2ä записи блока pBI истра, и pI4I i ер в уc 3 poH"стве управления сбрасывается в нуль, что возобновляет пода=.у на счетчик сигналов С . Если семафор сброшен в состояние 10, т,,е. предь3дуагие данные еще не с и:тены из . че3"к-; то сигнал записи не формкруетс :, триггер устройст33а управления не п..ребрасывается в нуль, и ус. ройст3:-о управления (процессор), а вместе с нкм — источник, блокируются. При з гом семафор соответствующей ячейки будет считываться в каждом такте с рНН С постоянно дo тех IIop пока считывавгке иэ соответствующей лчеь Й H не прок зайдет.

Считывание информации осуществляется аналогично, Пусть необходимо выполнить команду АДД П, 01, А2, 3, АЗ (сложить число кз буферного реI"HcTpR первой cBKI2HИ,. адрес А2 и

64168 8 число из ОЗУ, хранящегося по А3, результат записать по АЗ).

B первом такте адрес А2 заносится в буферные регистры всех секций. Код

01 поступает на дешифратор, где вырабатывается сигнал выбора кристалла (в данном случае — на первом выходе). Бо втором такте осуществляется считывание иэ операндов. Из ОЗУ по обычной схеме, а из блока многовходовых буферных регистров — через узел оповещения второго типа. Если семафоры данной ячейки находятся в состоянии 10,либо 11, то сигнал считывания проходит на блок регистров и триггер устройства управления. Происходит считывание, и триггер сбрасывается в нуль, что разрешает дальнейшее выполнение микрог:.рограммы.

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

Рассмотрим случай, когда в одном из блоков памяти (программ) считывает30 ся команда группы А2, а из остальных считываются команды группы А1. Допустим, чго такая команда считывается из блока 6, . В этом случае код (01000000) на входе блока 8 нреобразуется в такой код, который подключает вход 1 к выхоцам 1 и 2, а остальные остаются без изменения, т.е.

3 3, 4 4 (1 в 1 — 2,3 3,4-4) ° В качестве примера рассмотрим реалиэа О цию функции = tgX

TG L-з Р,А1,„П10,А2

Аргумент х. находится в регистре общего назначения с номером А1 про цессора 1„ а в процессоре 2 аргумент

Х находится в регистре буферного регистра с номером 10, А2, т.е. в секции, связанной с,первым процессоро» и номером А2. В процессоре 1 вычисляется величина 1/сос;Х. Эти функции вычисляются параллельно. Полученное значение функции sinX передается в первый процессор через сис, темный регистр (это регистры блока буферных регистров, имен2щие номер О) .

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

1464168 ка адреса и считывание команды осуществляется сразу же после запуска текущей команды. Поэтому на входах первого коммутатора 5 стоит ситуация, отличная от предыдущей. Если на входах первого коммутатора 5, команды группы А1, то сначала второй процессор, а затем первый процессор продолжает работу, как это ..описано.

Если же на каком-либо входе стоит . команда гРуппы А2, то она блокируетсоответствующие входы коммутатора 5 и ресурсы передаются этой команде.

Распределение ресурсов команды группы А2 следующее: 1 «1 2,2" 2—

3,3«3 — 4,4 4 — 1 (первым указывается вход коммутатора 5, где появилась команда группы А2, а далее идут номера процессоров.В тех случаях,. когда ресурс занят, первый процессор не закончил работу, а четвертый процессор начал выполнение команды, то синхронизация осуществляется с. помощью блокировок, как это описано.

При возникновении команд группы

А2 на двух входах, предпочтение отдается процессору с меньшим номером.

Например, команда группы А2 возникла на первом, втором и третьем входах. Тогда первым будут выполнены команды на 1- 1 — 2 и 3 -3 - 4, а затем 2-2 — 3.

Команды группы АЗ требуют для вы- . . полнения трех процессоров (1"1

2-3, 22-3-4, 3 3-4-1, 4- 4 — 1 — 2) . Команда группы А4 требует для своего выполнения четырех процессоров (1 «1 — 2 — 3 — 4, 2 «23 — 4 — 1 и т .д.) . Запуск и передача данных осуществляется аналогично командам А2. К группе АЗ относится команда Arc sin Х:

Y=Y,+Z.

Такое расположение позволяет избежать пересылок в процессоры. Запись результата ведется в ячейки, где

50 хранятся элементы. B каждом процессоре образуется строка результата.

Рассмотрим, как формируется первый элемент матрицы Y = А В, где А =

65 = (a;jj, B(b ;1, Y = (у,j) 1 = — 1 4, j = 1 4.

Из команды считываются адреса регистров А1 и А2, которые поступают на блок 16 регистров. В следующем

Z = Х cosY — 1 — Х зюУ

Аргумент х хранится в ЗУ данных

А1 и передан в буферные регистры второго и третьего процессоров, страница первого процессора с адресом

А2. Функция Y = arcsinX вычисляется по алгоритму

Z = Х cosYд — 1 — Х яма„, где Y — начальное приближение функции arcsinX °

Обычно для восьми старших разрядов Х (хранится в ПЗУ) .

Величина У, 1 — Х .и произведение 1 — Х з1пУ ищутся в первом

2 процессоре, во втором — сов7 и произведение Х созУ„, в третьем — sinY, Передача результатов осуществля10 ется по системным буферным регист» рам (это регистры с номером О в секциях В и ДС первого процессора) .

К группе. У4 относятся, например, команды перемножения матриц, отыскания матриц, отыскания собственных значений и тому подобные. Рассмотрим команду перемножения матрицы ИХИ, где И = 4.

УИН N4 LI P/Ê, Х, А1, P/К, Х, А2. где P/К, Х вЂ” регистровая косвенная, индексная адресация с шагом Х.

Данные размещаются следующим о6разом. Элементы матрицы А по строкам размещаются в памяти данных процессоров, начиная с адреса, хранимого в регистре с номером А1. Как правило, элементы располагаются по порядку,поэтому в начальной ячейке первого процессора хранится элемент а« во второй — а, и т.д. с Х = 1. Аналогично во втором процессоре, в первой ячейке — а, во второй — а и.

Э т.д . Элементы матрицы хранятся в виде копий в каждом процессоре, т.е. в первом процессоре — своя матрица, В, во втором — своя и т.д. В памяти данных матрица располагается, начи40 . ная с адреса, хранимого .в регистре с номером А2 по строкам последовательно, т.е.

В«, В, В3, В4q, Вiz ...> В4

В4 ю 44

14б41б8 шаге содержимое. регистров считывается в первое устройство 19 и во второе устройство 20, где они запоминаются. Одновременно их значения запи<."ываются в адресные регистры 21 и 22 памяти данных. В третьем такте считываются элементы а, и Ь, (во втором процессоре à,, b„, в третьем — а,, н и т.д.) . ЦиклогРамма опРеделе- 10 ия одного элемента матрицы М = 4 оказана на фиг. 7. Для получения сех четырех элементов циклограмма повторяется четыре раза.

Существует команда перемножения . атриц с передачей элементов матрицы из одного процессора в другой. В том случае матрица хранится следуюм образом. Первый столбец хранится ф блоке буферных регистров первого 2g процессора, секция второго процессо ра, второй столбец в блоке буферных регистров второго процессора, секция третьего процессора и т.д. Одновре,менно с умножением организуется пе- 25 редача элементов Ь„" . Причем Ь <, иэ

"J первого процессора в четвертый, Ь, из второго процессора в первый, Ь„ из третьего, Ъ, из четвертого в (! третий. Затем все повторяется для gg

|элементов Ь и так, пока ье будут

11

;определены все . элементь| требуемои матрицы. Так как обмен осуществляет,ся в момент умножения, то по време ни выполнения обе команды эквивалентны.

Рассмотрим теперь выполнение команды перехода, т.е. изменение ес тественного хода программы. Пусть в первом процессоре выполняется коман- 4О да "Условный переход". В зависимости от признака результата предыдущей команды, который хранится в АЛУ, содержимое адресного поля . А1 передается в устройство 19, где формируется физический адрес перехода. Далее сформированный адрес по шине числа, и сигнал записи по управляющей шине поступают в счетчик 7, . Таким образом, переход на. новый адрес программы осуществлен.

5О

Выполнение других команд осуществляется стандартно В устройствах 19 и 20 формируются адреса первого и второго операндов, которые .поступают в память 24 (блок 1б регистров).

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

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

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

К-й блоков памяти соединены соответственно с первого IIG К-й информационными входами первого коммутатора, вход данных системы подключен к первым информационным входам с перйого по К -й процессоров„ о т л и ч а ю щ а я с я тем, что, с целью повышения быстродействия за счет параллельной обработки команд, система дополнительно содержит К счетчиков, второй коммутатор, блок постоянной памяти, причем,, адресный вход данных системы соединен с адресными входами с первого по К-й процессоров, адресный выход i-го процессора (i = 1, ..., K5 соединен с информационным входом з-го счетчика, выход которого соединен с i-м выходом второго коммутатора и подключен к адресному входу i-го блока памяти, первый разряд управляющего выхода

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

1464168

14 мационньп» выход 1-го процессора соединен с j-ми информационными входаФрюмак

Яэмых

&оР . ВнЕянян жМо / ми Остальных процессоров, где j

= 2, ..., (и+1).

1464i68

1464168 ач

ev Ьц

1,бй1 68

Яйп 0Г ОБРЩ

ОООО 0»706КЯенйЯ Я2ОЬОВ2>ЛОВ» l

;, ;,1

<

I I

I ! ( с

1 !

1 1

ФУ,) 1 1

М

\

1

1 „;;г

4

Ъ

» 9

1 ( -»

ЪФ

СЕт0000 (ЗО

»

, еуущхРй,|с

» - г,1 Р У

«РЪ". б

1У. ЯУ „2 2У; = -- -,;-,7У- уу У ЯУ- ф; У У У 5"r Д У;,су 15r Nr ("3 Г- 3 :.: 1 " Г1 Г1 ГН П П Г3

ЙП.

Т, Т 1 1й1 (Ц „ — — — — — .Ес

1)! 1fIi

-"о- -"""- Корр екторМ.Шароши:

Редактор Н,Лдола

Заказ 82б/52 Годнисное

ЦН 2ЩПИ 1 он уд аоо;,а;: »0=.», !fîãî к a- f!! а нз н-",»)о»ретенЯЯЯ- и откр дтину дан TKHT CCCP

Пранзводотвенно- —. з;.„; 2;.::О;:,".и1 к,.к ":-::н -. г " агент, г. Ужгород, ул. Гагарина, 1 01