Адаптивная система обработки данных

 

Изобретение относится к вычислительной технике и может быть использовано в измерительно-вычислительных комплексах на основе мультипроцессорных вычислительных систем. Цель изобретения - увеличение пропускной способности системы за счет повышения степени распараллеливания процесса обработки потока взаимозависимых заявок. Для этого в систему, содержащую блок памяти заявок 1, N блоков 2 обработки, каждый из которых содержит процессоры 3 и блок 4 захвата магистрали и N блоков выбора канала, дополнительно введена магистраль адреса /данных/ управления, обеспечивающая связь между всеми процессорами системы. 1 з.п. ф-лы, 4 ил.

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

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

РЕСПУБЛИН

А1

as SU (11) 1 2 (51) 5 С 06 F 15/16

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

Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР (21) 4421727/24-24 (22) 05.05,88 (46) 23.03.90. Бюл, № 11 (71) Ярославский государственный университет (72) В.А. Курчидис и М.Л.Королев (53) 681.325 (088.8) (56) Авторское свидетельство СССР № 926662, кл. С 06 Г 15/16, 1982.

Авторское свидетельство СССР № 1451713, кл. G 06 F 15/16,11.06.87. (54) АДАПТИВНАЯ СИСТЕМА ОБРАБОТКИ

ДАННЫХ (57) Изобретение относится к вычислительной технике и может быть использовано в измерительно-вычислительных комплексах на основе. мультипроцессорных вычислительных систем. Целью изобретения является увеличение пропускной способности системы за счет повышения степени распараллеливания процесса обработки потока взаимозависимых заявок.

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

1552195 блоков обработки к процессорам других блоков обработки, Для передачи результатов обработки от процессора которой формируется требование на подключение системной магистрали 11.

Эта магистраль подключается в том с чучае, если нет сигнала занятости на шине 12. О захвате магистрали 11 блок 41 сообщает блоку 39 выполнения операций передающего процессора 3 сигналом по связи 62. При этом блок

41 передающего процессора сразу выставляет сигнал занятости на шине 12 системной магистрали 11 препятст10 !

5 вуя доступу к этой магистрали остальным процессорам системы.

После того, как системная магистраль 11 захвачена, активизируется сигнал 59 на подключение системной магистрали 11 к информационным выходам 63-66 блока 39 через приемопередатчик 42. После этого передающий процессор 3 выставляет адрес процессора-абонента и передаваемые данные соответственно на шинах 17 и 18. Независимо от состояния процессора-абонента передаваемый адрес дешифрируется в дешифраторе 37, и последний вьдает сигнал записи в блок 38

30 буферной памяти по связи 45. В результате адрес и данные с шин 17 и 18 записываются в блок 38, который сигналом подтверждения записи по связи

46 через шину 15 освобождает доступ к системной магистрали другим процессорам. На этом процесс передачи данных по системной магистрали заканчивается.

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

"Заполнен" по связи 47 поступает на шину 12 занятости системной магистра45 ли, запрещая передачу данных по этой магистрали. Получение данных по результатам обработки зависимых потоков происходит в процессорах из блоков 38 буферной памяти. Считывание данных иэ блока 38 в блок 39 выполнения операций происходит при выполнении соответствующей команды, активизирующей сигнал считывания по связи 5 1. Результаты окончательной обработки заявок вьдаются процессора50

3 одного блока 2 обработки процессо-.

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

Режимы работы блоков обработки устанавливаются от внешних устройств путем установки соответствующих сигналов на шинах 20 магистрали 19 задания режима работы системы. Таким образом, в системе может быть органнзова»о несколько различных режимов обработки, что позволяет системе эФфективно адаптироваться K входным потокам разной структуры.

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

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

"E азрешение" первого процессора подключен к одноименному входу второго процессора, выход Запрос второго процессора подключен к входу нЗапрос первого процессора, выход Запрос первого процессора через входную шину подключен к входу "Запрос" блока памяти заявок, входы-выходы данных, адреса, сигналов выдачи, сигналов приема первого процессора через одноименные шины локальной магистрали подключены к одноименным входам-выходам второго процессора, выход Захват блока захвата магистрали подключен к одноименному входу первого процессора, выход Ответ которого подключен к входу Захват второго процес1552195

l2 сора, выход Запрос и вход-выход занятости первого и второго процес-. соров через одноименные шины локальной магистрали подключены к входам

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

l. йервого процессора подключен к входу сигнала "Захват" второго процессора, ll !! выход Ответ второго процессора i-го блока обработки подключен к входу

"Запрос" первого процессора i-ro блока обработки.

2. Система по п.1, о т л и ч а юа я с я тем, что процессор содержит первый и второй блоки буферной памяти, первый и второй приемопередатчики, первый и второй бло1 и обмена„ дешифратор адреса и блок

Выполнения операций, входы "Разре1пение", "запрос", "Задание режима"

И выходы Разрешение" и "Запрос"

Которого являются соответственно !дноименными входами и выходами процессора, выходы ™Пуст", "Адрес", "Данные" первого блока буферной памяти подключены соответственно к одноименным первым входам блока выполнения операции, первый выход !! lt

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

И первого приемопередатчика и является первым выходом приема процессора, выход !!Заполнен!! первого- блока буферной памяти подключен к одноименИому входу первого блока обмена и является первым выходом занятости

Процессора, первые информационные второй выход запроса захвата котороР

50

5 я

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

"Захват", выход "Ответ" и выход !! ll

Запрос первого блока обмена являются одноименными первыми входами и выходами процессора, выход "Разрешение захвата" первого блока обмена подключен к одноименному первому входу блока выполнения операций, первый выход запроса захвата которого подключен к одноименному входу первого блока обмена, первый выход

"Управление включением" блока выполнения операций подключен к одноименному входу первого приемопередатчика, информационные входы-выходы, входы-выходы выдачи и приема-которого подключены соответственно к одноименным входам-выходам второго приемопередатчика и входам-выходам блока выполнения операций, выход управления направлением передачи которого подключен к одноименным входам первого и второго приемопередатчиков, вход "Управление включением" которого подключен к одноименному второму выходу блока выполнения операций, го подключен к одноименному входу второго блока обмена, выход "Разрешение захвата которого подключен к одноименному второму входу блока выполнения операций, вторые выходы считывания и записи которого подключены к одноименным входам второго блока буферной памяти, выход Заполнен", "Пуст" "Адрес" и Данные" которого подключены к одноименным вторым входам блока выполнения one раций соответственно, входы-выходы адреса и данных второго приемопередатчика подключены к одноименным входам второго блока буферной памяти и являются одноименными вторыми вхоI.дами-выходами процессора, вход-выход выдачи второго приемопередатчика является одноименным вторым входом выходом процессора, вход-выход приема второго приемопередатчика соединен с одноименными выходом второго блока буферной памяти, входом второго блока

l4

13 обмена и является вторым входом-вы11 ходом приема процессора, вход Захват", выходы "Ответ", "Запрос и занятости второго блока обмена являются одноименными вторыми входом и вы-- ходами процессора.

1552195

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

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

На фиг. 1 представлена схема сис-! темы; на фиг.2 — схема процессора; на фиг.3 — схема блока выбора каналов;

lHa фиг.4 — схема блока захвата маги страли.

Адаптивная система обработки данных содержит (фиг.1) блок 1 памяти заявок, блоки 2 обработки, каждый з которых содержит процессоры 3 и блок 4 захвата магистрали, и блоки

) 5 выбора каналов.

Система имеет шину 6 запроса и ходную магистраль 7, содержащую

Мину 8 разрешения, шину 9 адреса и шину 10 данных, а также системную магистраль 11, содержащую шину 12 занятости, шину 13 запроса, шину 14 захвата — ответа, шину l5 приема, Шину 16 выдачи, шину 17 адреса и ши- 30 ,ну 18 данных, магистраль 19 задания ежима работы системы, каждый процессор 3 имеет вход 20 задания режима.

Блок 2 обработки имеет локальную магистраль 21, содержащую шину 22 бранных, шину 23 адреса,, шину 24 выдачи, шину 25 приема, шину 26 захваh а-ответа, шину 27 запроса и шину

28 занятости.

Каждый процессор 3 имеет выход 29 разрешения, вход 30 разрешения, вход 31 запроса и выход 32 запроса.

Блок 5 выбора каналов имеет информационные входы, подключенные к входной магистрали 7, а также стробирующий вход 33, выход 34 сигнала разрешения, выходы 35 и 36 адреса и данных соответственно.

Процессор 3 содержит (фиг.2) деШифратор 37 адреса, первый блок 38 буферной памяти, длок 39 выполнения операций, второй блок 40 буферной памяти, первый блок 41 обмена, первый 42 и второй 43 приемопередатчиКи, второй блок 44 обмена.

Блок 38 буферной памяти имеет вход 45 записи, выход 46 подтверждения записи, выход 47 "Заполнен", входы 48 и 49 данных и адреса соответственно, выход 50 "Пуст", вход

51 считывания, выходы 52 и 53 адре- са и данных соответственно.

Блок 39 выполнения операций имеет вход 54 разрешения, выход 55 запроса, задающий вход 56, выход 57 разрешения, вход 58 запроса, первый выход

59 управления включением, выход " 0 управления направлением передачи. первый выход 61 запроса захвата,первый вход 62 разрешения захвата, входы-выходы 63-66 соответственно данных, адреса, выдачи и приема,второй вход 67 разрешения захвата„ . второй выход 68 запроса захвата, вход

69 сигнала "Заполнен", вход 70 сигнала "Пуст", выход 71 считывания, выход 72 записи, буферные входы 73 и

74 адреса и данных соответственно, второй выход 75 управления включением.

Блок 40 буферной памяти имеет вход

76 адреса, выход 77 гриема и вход 78 данных.

Блок 5 выбора каналов содержит (фиг.3) приемопередатчики 79 и 80 и селектор 81 каналов.

Блок 4 захвата магистрали содержит (фиг„4) два элемента И 82 и 83.

Этот блок обеспечивает блоку 5 выбора каналов наивысший приоритет доступа к локальной магистрали 2 1 блока

2 обработки по отношению к процессорам 3 этого блока обработки.

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

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

При этом каждая заявка представляет собой совокупность номера (адреса) измерительного канала и выборки (значения параметра) но этому каналу,что выражается параллельными 16-разрядными двоичными кодами. Номер канала используется в процессоре в качестве начального адреса программы обработки выборки.

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

5 15521 системы в каждом конкретном применении.

В зависимости от значения сигналов на шинах задания режима работы маги-. страли 11 всякий блок обработки может

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

При описании работы системы пред-полагается, что все каналы разбиты предварительно на группы по числу блоков обработки, причем номера каналов одной группы используются как адреса, по которым в соответствующих селекторах 81 каналов записаны"1", а по 25 остальным адресам селекторов каналов записаны "0".

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

Прием заявок на обработку.

Для приема заявок на обработку каждый блок обработки, который не

35 загружен полностью, выставляет на выходе 32 запроса сигнал запроса. Запросы от блоков обработки по шине 6 запроса поступают на вход запроса блока 1 памяти. При наличии заявок и сигнала запроса на соответствующем входе блока 1 памяти последний выставляет на шинах адреса 9 и данных 10 коды номера канала и выборки очередной заявки и вьщает по шине 8

45 сигнал разрешения. Под действием сигнала разрешения, поступающего с выхода блока 1 памяти на синхровходы блоков 5 выбора каналов, на выходе

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

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

95 б

34 ни один из процессоров не может . осуществлять захват локальной магистрали.

Если на шине 28 отсутствует сигнал занятости, то сигнал разрешения проходит через элемент И 82. Если сигнал разрешения по связи 34 поступает в момент, когда локальная магистраль уже занята (на шине 28— единичный сигнал), то поскольку длительность сигнала разрешения превышает длительность цикла локальной магист рали,в момент снятия сигнала занятости в конце этого цикла сигнал разрешения проходит на выход элемента И 82.

С выхода элемента И 82 сигнал поступает на вход разрешения первого процессора рассматриваемого блока обработки и одновременно по связи 33 поступает на стробирующие входы приемопередатчиков 79 и 80 соответствующего блока выбора каналов. В результате этого информация с шин 9 и

10 через приемопередатчики 80 и 79 по связям 35 и 36 подается соответственно на шины 23 и 22 локальной магистрали блока 2 обработки.

Цепь распространения сигнала разрешения, поступающего на вход разрешения первого процессора 3 блока 2 обработки, устроена таким образом, что этот сигнал проходит на вход 72 записи блока 40 буферной памяти и разрешает запись данных в соответствующий блок с шин 22 и 23 локальной магистрали. По окончании действия сигнала разрешения локальная магистраль освобождается. Таким образом, процесс приема заявок на обработку совмещен в общем случае с процессом обработки заявок (независимо от режима работы блоков обработки).

Работа блока обработки в режиме параллельной обработки заявок.

В этом режиме на один блок обработки назначаются каналы, характеризующиеся обработкой выборок по независимым алгоритмам. Исходное состояние блока 2 обработки: все процессоры 3 свободны, блок 40 буферной памяти пуст (т.е. значение сигнала на выходе 70 равно."1", а на

69 — "0"), значение сигнала на входе

20 задания режима работы равно "1".

В этом случае каждый процессор выдает сигнал запроса с выхода 32. Сигнал разрешения, поступающий из блока 4

1552195 захвата магистрали на вход первого

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

Мотя бы одной заявки сигнал на выхо де 70 "Пуст" становится равным "0", поэтому сигнал опроса по связи 71 производит считывание очередной заявки из блока 40 буферной памяти, и блок 39 выполнения операций включается в работу. Если блок 40 буферной памяти пуст, то свободный процессор отсутствии запросов от последуюпроцессоров производит прием вки с шин 22 и 23 локальной магитрали по сигналу разрешения по но- 20 еру канала, считанному в блок 39, пределяется программа обработки аявки (номер первой выполняемой команды). Если блок 40 буферной па.жити заполнен, то сигнал на выходе 25

69 этого блока равен "1", а на выходе

70 — "0". В этом случае по окончании обработки заявки формируется сигнал запроса не дожидаясь окончания цикла считывания из блока 40.

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

Их освобождения. Тем самым обеспе- 40 чивается непрерывность работы всех

Процессоров и отсутствие простоев в

1 х работе при условии непрерывной

Вагрузки.. Результаты обработки заявок выдаются процессором 3 через

45 системную магистраль 11:на выход системы.

Работа блока обработки в режиме

Последовательной обработки.

А. Обработка взаимоне.зависимых

Потоков.

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

1процессоры 3 свободны, блок 40 буферз ной памяти пуст (т.е. значение сигнала на выходе 70 равно "1", а на выходе 69 — "0"), значение сигнала на входе 20 задания режима равно "0". В этом режиме сигнал запроса на выходе каждого процессора 3 формируется так же, как и в параллельном режиме.

Запросы на выходе 32 блока обработки в последовательном режиме формируются только от первого процессора 3 этого блока обработки. Появление сигнала разрешения на входе разрешения первого процессора инициирует запись заявки по связи 72 в блок 40 буферной памяти первого процессора

3 блока 2 обработки. Если блок буферной памяти первого процессора пуст в момент появления сигнала разрешения, то инициируется прием заявки с шин

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

При этом в блоке 39 второго процессора выполняются вторые части алгоритмов обработки заявок. Аналогичным образом происходит работа остальных процессоров 3 блока обработки 2 в последовательном режиме. Результаты окончательной обработки заявок выдаются процессором на выход системы через системную магистраль 11.

Б. Обработка взаимоза)зисимых потоков.

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

1552195

Составитель Б. Резван

Техред Л,олийнык Корректор В. Кабаний

Редактор В. Петраш

Заказ 331 Тираж 563 Подписное

ВНИИПИ Го -ударственного комитета по изобретениям и открытиям при 1 КНТ СССР

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

Производственно-издательский комбинат "Патент", r. Ужгород, уч. 1 а> арина, 101