Многопроцессорная система Советский патент 1989 года по МПК G06F15/163 

1

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

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

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

Процессорная система (фиг. 1) содержит процессоры 1-4 с первого по четвертый, первый коммутатор 5 , второй коммутатор 5, блоки ла- мяти (программ), счетчики 7, -74, блок 8 постоянной памяти (ПЗУ), блоки 9,- (94 многовходового буферного регистра,, входящие в состав соответственно с первого по четвертый процессоров.

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

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

Блок многовходовых буферных per.. гистров (фиг. 3) содержит первый элемент И 28, первый многорежимный регистр 29, первый узеп 30 оповещения первого типа, второй элемент И 31, второй многорежимный буферный регистр 32, второй узел 33 оповещения первого типа, третий элемент И 34, третий многорежимный буферный регистр 35, третий узел 36 оповещения первого типа5 дешифратор 37 и узел 38 оповещения второго типа.

Устройство управления (фиг. 4) содержит регистр 39 команды, счетчик 40, память 41 микрокоманд, регистр 42 микрокоманд, узел 43 управления и генератор 44 синхроимпульсов.

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

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

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

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

10

15

20

25

30

35

40

45

принципу (разряды с j-ro К-й подключаются к внешней шине команд системы, а остальные - к адресной шине, J, как правило, равно нулю).

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

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

.Допустим, что , тогда адрес поступает на адресньй вход второго блока 6 (программной) памяти. Одновременно по внешней шине команд поступает команда, которая должна быть записана в блок 6 памяти. Внешняя шина команд помимо разрядов, по которым передается само командное слово, содержит еще К разрядов, по кото рым передается управляющая инфор1 4эт ция. Каждый отдельный разряд связан только с одним входом записи соответ ствующего блока програм1чной памяти. Например, первый разряд кодового сло ва связан с первьш блоком 6 ( раммной) памяти, второй - с блоком 6j, третий - с блоком 6.j и т.д. Это позволяет легко сов 1естить управлени записью и комт тацию, т.е. хотя дануправление записью (первый бит управ- 50 ные поступают на все блоки одновре0

5

0

5

0

5

0

5

принципу (разряды с j-ro К-й подключаются к внешней шине команд системы, а остальные - к адресной шине, J, как правило, равно нулю).

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

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

.Допустим, что , тогда адрес поступает на адресньй вход второго блока 6 (программной) памяти. Одновременно по внешней шине команд поступает команда, которая должна быть записана в блок 6 памяти. Внешняя шина команд помимо разрядов, по которым передается само командное слово, содержит еще К разрядов, по которым передается управляющая инфор1 4эт ция. Каждый отдельный разряд связан только с одним входом записи соответствующего блока програм1чной памяти. Например, первый разряд кодового слова связан с первьш блоком 6 (.., раммной) памяти, второй - с блоком 6j, третий - с блоком 6.j и т.д. Это позволяет легко сов 1естить управление записью и комт тацию, т.е. хотя дан0 ные поступают на все блоки одновре

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

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

Адрес поступает по адресной шине команд. По отношению к вне анему устройству шина команд и шина адреса являются одной шиной. Разделение щи- ны производится по пространственному

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

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

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

Режим Работа. В этом режиме- осуществляется выполнение программ, которое протекает следующим образом. Общая система команд разбивается на четыре группы: А1, А2, A3, А4. Первая группа команд включает в себя только те команды, которые требуют для своего выполнения только один процессор, вторая группа - два, третья - три и четвертая - четыре. Для выполнения программа разбивается на К ветв ей (в нашем случае - четыре) . Разбиение желательно проводить так, чтобы каждая ветвь по ко- мандам группы А1 вьтолнялась параллельно. Код группы А1 (старпме два бита кода операции) равен 00. Команды из блоков памяти (программ) считываются одновременно по сигналу с выходов 1j, 2, 3g и 4, процессоров 1-4. Если это все команды группы А1, то на выходе блока 8 постоянной памяти формируется управляющий код, f по которому коммутатор 5 настраивается: i-й вход на i-й выход, т.е. выход первого блока программной па- мяти - на вход Ij, первого процессора, второго - на вход 2 второго и т,д. Таким образом, каждый процессор вьшолняет свою команду.

Рассмотрим вьтолнение команды в первом процессоре. Команда поступает с выхода Ij, на вход устройства 26 управления (фиг. 2). Код команды и признаки адресации поступают на, память микропрограмм как начальный адрес микропрограмм. Адреса данных через шины данных поступают в индексны

10

15

641686

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

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

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

20

25

30

УМН 1-J3, А1, Р, А2 ПЕР 56 П, 01, А2

Здесь 3, Р, П - признаки адресации (3 - память 24 данных, Р - блок 16 регистров, П - блок многовходовых буферных регистров, 01 - указатель номера процессора, в данном случае первого), А1, А2 - адреса.

При выполнении команды умножения код операции и признаки адресации поступают в счетчик адреса (фиг.4). Сформированньй адрес поступает на ПЗУ микрокоманд, и начинается выполнение Микропрограммы. В первом такте осуществляется передача.первого адреса в память данных в регистр 21 адреса, а второго - в регистр 17 адреса блока 16 регистров. Кроме того, осуществляется наращивание адреса в программной памяти на единицу. Во втором такте осуществляется считывание данных и запись их в регистры

7

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

В первом такте выполне1-шя команды ПЕР адрес из поля А2 коканды записывается в адресные реги1;:тры всех блоков многовходовьк буферных внешних регистров5 но срабатыза&т только тот который соответствует коду 01, т„е„ блок внешних регистров первого процессора.

При записи адреса одновременно формируется сигнал считывания значения семафоров, которые хранятся по тому же адресузчто и данные. Считан- ньй семафор записывается в триггеры 47 и 48 (фиг. 5), Есл15 Е триггерах хранится код 01 запись разрешена (код 00 соответствует зглрещенига И записи и считывалшя5 блокировка процессора; 01 - запись разрешена,, считывание запрелцено; 10 запись запреш;ена5, считывание э :3решено t1 - запись и считывание ., ра.зрешены без ограничения) то при подаче в следующем такте сигна.па записи на вход Зп фсрми:руется сигнал записи, который поступает на вход записи блока регистра, и триггсф з устройстве управления сбрасывается в нуль что возобновляет подачу на счетчик сигналов Сд, Если семафор сброшен в состояние 10, т,..е, предьщущие данны еще не считаны из ячейки, то сигнал записи не формируется триггер устройства управления не перебрасывается в нуль, и устройство управления ,(процессор)5 а вместе с ним - источ ник,, 6.ЛОКИРУ10ТСЯ„ При зтом семафор соответствующей .ччейкк будет считываться в каждом такте серии Сд постоянно до тех порS пока считывание из соответствующей .ячей: гси не произойдет,

Считывашш информащти осуществляется аналогично. Пусть необходимо выполнить команду АДЦ И, 01j А25 3 A3 (слоясить чис.по ;аз буферного регистра первой ceKDrHHj. адрес А2 и

,

4641688 .

число из ОЗУ, хранящегося по A3, ре- зультат записать по A3),

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

f-j

01 поступает на дешифратор, где вырабатывается сигнал выбора кристалла (в данном случае - на , первом ВЬЕХО- де) . Во втором, такте осуществляется

jQ считывание из операндов. Из ОЗУ по обычной схеме, а из блока многовхо- довых буферных регистров - через узел оповещения .второго типа. Если семафоры данной ячейки находятся в

Т5 состоянии 10 .-пибо 11, то сигнал считывания проходит на блок регистров и триггер устройства управления. Происходит считывание, и триггер сбрасывается в нуль, что разрешает даль20 нейшее выполнение микропрограммы. Если же триггеры находятся в состоянии 01, то и сигнал считывания не вырабатывается, и вьнислительный процесс блокируется по отсутствию дан

25 ных. Указанные блокировки позволяют осуществить синхронизацию параллельно выполняемому процессору.

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

TGUJ Р,А1,П10,А2

Аргумент X находится в регистре общего назначения с номером А1 про цессора 1, а в процессоре 2 аргумент X находится в регистре буферного регистра с номером 10, А2, т.е. в -. секции, связанной с, первым процессо- ром и номером А2в В процессоре 1 вычисляется величина 1/cosX. Эти функции вьмисляются пapaплeJ ьнo. Полученное значеьгае функции sinX передается в первый процессор через сис- темный регистр (это регистры блока буферных регистров, имеющие номер 0). Как только вычисления заканчиваются, то любой процессор может запросить команду, так как нараш шание счетчи-(

914

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

При возникновении команд группы А2 на двух входах, предпочтение отдается процессору с меньшим номером. Например, команда группы А2 возникла на первом, втором и третьем входах. Тогда первым будут выполнены команды на - 2 и 3- З - 4, а затем - 3.

Команды группы A3 требуют для вы- . полнения трех процессоров ( - 2-3, 2-2 -3-4, 3 3-4-1, - 1 - 2) . Команда группы А4 требует для своего выполнения четыре процессоров ( - 2 - 3 - 4, 3 - 4 - t и т.д.). Запуск и передача данных осзтествляется аналогично командам А2. К группе A3 относится команда Arc sin X:

Z X cosYo - -jl - X sinYp .

Аргумент X хранится в ЗУ данных А1 и передан в буферные регистры второго и третьего процессоров, страница первого процессора с адресом А2. Функция Y arcsinX вычисляется по алгоритму

Z X cosYg - ,

где Yj - начальное приближение функ- . ции arcsinX.

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

10

Y Y + Z.

Величина

Y, 4l - X

и произведе

5

0

5

0

0

-ITX sinY. ищутся в первом

5

ние

процессоре, во втором - cosY и произведение X cosYo , в третьем - sinY.

Передача результатов осуществляется по системным буферным регистрам (это регистры с номером О в секциях В и ДС первого процессора).

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

УМН M4U Р/К, X, А1, Р/К, X, А2.

где Р/К, X - регистровая косвенная, индексная адресация с шагом X.

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

вой ячейке - а

21

ВО второй - а

пер- и

22

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

, By, , Bj, , В,,, Bfi «

В

4t

В

43

В

44

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

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

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

шаге содержимое.регистров считывает- йя в первое устройство 19 и во второе устройство 20, где ога-х запоминаются. Одновременно их значения запи- (1;ыв аются в адресные регистры 21 и 22 1|1амяти данных. В третьем такте считы146416812

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

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

раются элементы а и b I, Ч во второ в третьем - а,

троцессоре a , Ь„ ,

,, и т „д.) Циклограмма определе- :тя одного элемента матрицы М 4 показана на фиг, 7. Для получения :зсех четырех элементов циклограмма :1овторяется четьфе раза. I Существует команда перемножения . йатриц с передачей элементов матрицы р из одного процессора в другой. В (этом случае матрица хранится следую- рщм образом. Первый столбец хранится IB блоке буферных регистров первого роцессора5 секция второго процессора, второй столбец в блоке буферных регистров второго процессора, секция третьего процессора и т.д. Одновременно с умножением организуется пе- |редача элементов Ь-- , Причем b,, из

мг Ь.

первого процессора в четвертый, Ь, ;из второго , процессора в первый, 1из третьего, Ь из четвертого в 1третий. Затем все повторяется для |элементов и так, пока не будут |определены все ..элементы требуемой |матрицы. Так как обмен осуществляет- ;ся в момент умножения, то по време- {ни выполнения обе команды эквивалентны.

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

Вьшохшение других команд осущестляется стандартно, В устройствах 19 и 20 формируются адреса первого и второго операндов5 которые поступают в память 24 (блок 16 регистров). Происходит считывание данных и запись -их Б один из арифметических блоков. После выполнения действия

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

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

duof 8t fu/HJU шина амиму.

AfpecHOf uft/на jr |ь Х /s 14

вхо

. внешмл с

Bxof dppCffaJt и/ума

д)аг.2

Фиг.1

lit.

lo to to

«SJ Csi 5j

Ф

М2.0

/УА/ МАУ Р,.

пп

Упя.

i/r г зг Г, fir п S1- SJ Юг пт 127 mm 5т 1бт

fij:i ija.j:ijnj:Ln rix

i.flniLjrci..j::iiL.,..., ш...

л

JifflinriiiaiQiirnironm

j riniiLJjiiinunim

Зтась

UMpiiltiHiiltiifiTV I 1| U

Фмг. б

Зтась рези ьтата

UMpiiltiHiiltiifiTV I 1| U