Адаптивная система обработки данных Советский патент 1989 года по МПК G06F15/177 

4 О1

tN9

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

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

На фиг. 1 представлена структурна схема системы; на фиг. 2 - схема бло ка выполнения операций; на фиг. 3 - система команд; на фиг. А - схема блока коммутации; на фиг. 5 - схема блока двунаправленных переключателей; на фиг. 6 - схемы блока буферной памяти и логического блока; на фиг. 7 - схема арифметико-логи- ,ческого блока; на фиг. 8 - временная диаграмма; .на фиг. 9 - система микрокоманд; на фиг. 10 - схема блока обмена; на фиг. 11 - его временная диаграмма; на фиг. 12 - система микрокоманд; на фиг. 13 - схемы элементов коммутации, входящих в состав арифметико-логического блока и блока обмена; на фиг. 14 - схема элемента коммутации; на фиг. 15 - схема блока памяти; на фиг. 16 - схема блока подключения магистрали; на фиг. 17, 18 - блок-схемы алго- ритмов работы процессоров в системе. Адаптивная система обработки данных содержит блок 1 памяти заявок, процессоры 2, каждый из которых содержит блок 3 коммутации, блок 4 выполнения операций, элемент ИЛИ 5, элемент И 6, демультиплексор 7, блок. 8 буферной памяти, магистраль 9 передачи сигналов, разделенную на секции через блоки 10 двунаправленных переключателей и содержащую шину 11 адреса, шину 12 данных, магистраль 13 выдачи, магистраль 14 приема, магистраль 15 запроса, магистраль 16 занятости, магистраль 17 запроса захвата и магистраль 18 выхода ответа; магистраль 19 задания режима, выход 20 разрешения, вход 21 запроса, первую связь 22 запроса, вторую связь 23 запроса, связь 24 записи, первую связь 25 запуска, вторую связь 26 запуска, связь 27 обращения, связь 28 опроса, связь 29 сигнала Пуст, связь 30 сигнала Заполнен.

Блок 4 выполнения операций содержит блок 31 памяти, счетчик 32 команд, дешифратор 33, первую связь 3 управления, вторую связь 35 управлния, третью связь 36 управления, четвертую связь 37 управления, пяту связь 38 управления, элемент ИЛИ 39 арифметико-логический блок 40, блок 41 обмена, блок 42 подключения магистрали, шину 43 команд, связи 44, 45 исполнения, адресную связь 46, информационную связь 47 выдачи, связь 48 приема, связь 49 захвата, связь 50 разрешения захвата.

Блок 3 коммутации содержит элементы И 51-55, элемент ИЛИ 56.

Блок 10 двунаправленных переключтелей содержит двунаправленные переключатели 57-63.

Логический блок 7 содержит два элемента И 64 и 65, а блок 8 буферной памяти - счетчик 66 адреса записи, дешифратор 67 адреса записи, счетчик 68 заполнения, счетчик 69 адреса считывания, дешифратор 70 адреса считывания, входной регистр 71, блок 72 памяти, выходной регистр 73.

Арифметико-логический блок 40 содержит блок 74 приема-передачи, регистр 75, блок 76 регистров общего назначения, сумматор 77, сдвига- тель 78, регистр 79 состояния, элемент 80 коммутации, дешифратор 81 микрокоманд, регистр 82. микрокоманд, формирователь 83 синхроимпульсов.

Блок 41 обмена содержит блок 84 приема, блоки 85, 86 приема-передачи, элементы 87, 88 коммутации, регистр 89, коммутатор 90, дешифратор 91 микрокоманд, формирователь 92 синхроимпульсов, элемент И 93, регистр 94 микрокоманд, элемент ИЛИ 95.

Элемент 80 коммутации содержит элементы И 96, 97, элемент ИЛИ 98; элемент 87 коммутации - элементы И 99, 100, элемент ИЛИ 101; элемент 88 коммутации - элементы И 102, 103, ключевые элементы 104, 105, элемент ИЛИ 106.

Блок 31 памяти содержит регистры 107, 108 адреса, узел 109 памяти. Блок 42 подключения магистрали содержит элементы И 110-113, триггер 114, ключевые элементы 115, 116.

Система работает в одном из двух режимов обработки заявок: параллельном или последовательном. Вид режим обработки зависит от значения сигна на магистрали 19 задания режима. В зависимости от заданного режима работа системы протекает следующим образом.

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

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

В этом случае каждый процессор 2 выдает сигнал запроса, который формируется блоком 4 выполнения операций всякий раз после окончания алгоритма обработки выборки. С вькода опроса блока 4 выполнения операций этот сигнал проходит по связи 28 на первый вход элемента И 64 демульти- плексора 7, далее - на его выход (так как сигнал Пуст на связи 29 равен 1) и поступает по второй связи 23 запроса на.- второй вход элемента ИЛИ 5. На п ервый вход элемента ИЛИ 5 в режиме параллельной обработки поступает сигнал от блока 3 коммутации, формирующийся из запросо последующих процессоров. Сигнал на первой связи 22 запроса (выход элемента И 6) в этом режиме всегда раве О, так как на первый инверсный вход элемента И 6 подано значение сигнала 1.

Объединяясь через элементы ИЛИ 5, все запросы поступают на вход 21 запроса блока 1 памяти заявок. По сигналу запроса блок 1 при наличии в нем заявки вьщает с адресного и информационного выходов в магистраль 9 передачи сигналов код номера канала и код выборки соответственно, которые устанавливаются на шине 11 адреса и шине 12 данных. С выхода 20 разрешения блока 1 памяти заявок выдается сигнал разрешения.

Все двунаправленные переключатели 57-63 блоков 10 двунаправленных переключателей замкнуты под действием единичного сигнала на магистрали 19. Поэтому отдельные секции магистрали образуют единую системную магистраль 9 передачи сигналов.

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

10

15

20

30

вляется сигналом по первой связи 25 запуска на первый запускающий вход блока 4 выполнения операций. При этом в блок 4 считываются коды номера канала и выборки с шин 11 и 12 соответственно. Одновременно блокируется сигнал опроса, поступающий по связи 28 с блока 4 (аннулируется запрос данного процессора), что служит разрешением включения в работу предыдущего процессора. Сигналы на связях 26 и 24 всегда равны О, поэтому Состояние блока 8 буферной памяти не меняется и этот блок в режиме параллельной обработки не используется. Тем самым создается топологический приоритет процессоров по мере удаления их от блока 1 памяти заявок.

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

Алгоритм работы системы в режиме параллельной обработки заявок показан на фиг. 17.

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

Исходное состояние: все процессоры 2 свободны, блок 8 буферной памяти пуст (значение сигнала на выходе 29 равно 1, а на выходе 30 - О), значение сигнала на магистрали 19 задания режима равно О.

, В этом режиме двунаправленные переключатели 57-63 блоков 10 двунаправленных переключателей разомкнуты. Поэтому магистраль 9 передачи сигналов оказывается разделенной на электрически не связанные секции. При этом в системе организуются независимые связи передачи - приема между парами соседних процессоров по шинам 12 данных магистральных секций.

В начальный момент в каждом процессоре 2 формируются, одновременно 5 два сигнала запроса. Во-первых, свободный блок 4 выполнения операций выдает сигнал с выхода опроса, пос- тупающий по связи 28 через демульти- плексор 7 на второй вход элемента .

35

0

5

0

или 5 по связи 23 в качестве сигнала первого запроса. Во-вторых, на вьвсоде элемента И 6 формируется сигнал второго запроса (так как значение сигнала Заполнен на свя1зи 30 равно О), поступающий по связи 22 на третий вход элемента ИЛИ 5 и на информационный вход блока 3 коммутации. Сигнал второго запроса при работе в последовательном режиме постоянно поступает через элемент ИЛИ 5 на вход запроса блока 3 коммутации предыдущего процессора 2 до тех пор, пока не заполнится блок 8 буферной памяти.

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

Появление сигнала разрешения на входе разрешения блока 3 коммутации первого процессора 2 инициирует выдачу с выхода записи блока 3 по связи 24 сигнала записи, который записывает в блок 8 буферной памяти код выборки с шины 12 данных первой магистральной секции. Поскольку блок 8 теперь не пуст, то сигнал запроса, поступающий с выхода опроса блока 4 по связи 28 в логический блок 7, формирует на связи 26 сигнал, который запускает блок 4, а также передает в него из блока 8 выборку, которую блок 4 начинает обрабатывать по соответствующему алгоритму частичной обработки. При этом сигнал с выхода опроса блока 4 снимается.

В то время как блок 4 выполняет первую часть алгоритма обработки заявки, сигнал первого запроса про- цессора сохраняется, поэтому блок 1 памяти заявок продолжает выдавать заявки, которые записываются в узел 8 буферной памяти данного процессора 2 Эта передача заявок заканчивается

.

17126

при полном заполнении бдока 8 буферной памяти.

Блок 4 выполнения операций первого процессора 2, выполнив первую часть алгоритма обработки заявки, вьщает с выхода обращения по связи 27 сигнал обращения в блок 3 коммутации. Если при этом на входе запроса блока 3 10 имеется сигнал запроса от второго процессора 2, то блок 3 вьщает с выхода разрешения сигнал, поступающий на вход разрешения блока 3 второго процессора 2,

15 Во втором процессоре 2 блок 3 коммутации сигналом с выхода записи по связи 24 передает в блок 8 буферной памяти этого процессора результат частичной обработки заявки (проведен- 20 ной первым процессором) по шине 12 данных второй магистральной секции, куда он поступил из первого процессора. По сигналу с выхода опроса блока 4 выполнения операций, поступаю- 25 щему по, связи 28, демультиплексор 7 выдает по связи 26 сигнал управления, который поступает на второй запускающий вход блока 4 выполнения операций, а также передает данные из бло- 30 ка 8 в блок 4 для последующей обработки, т,е. для выполнения второй части алгоритма. Аналогичным образом происходит включение в работу остальных процессоров 2.

Поскольку в этом режиме формирование сигнала запроса и. прием информации в блок 8 буферной памяти процессоров 2 не связаны с окончанием выполнения части алгоритма, то су- . 40 щественно сокращаются простои процессоров 2 из-за неравномерности длин частей алгоритмов. Подобрав соответствующим образом объем памяти блока 8, можно практически полностью исключить простои в системе. Более того, прием информации в блок 8 процессоров 2 и выдача информации из процессоров в этом режиме выполняются независимо ввиду разделения магистрали 9 передачи сигналов на несвязанные.секции, что дополнительно сокращает простои процессоров в системе ,

Алгоритм рабо ты процессоров 2 55 системы в режиме последовательной обработки заявок показан на фиг. 18.

Логика формирования сигналов, управляющих работой процессоров 2 в системе в нужном режиме, реализу35

45

50

7

ется в блоке 3 коммутации, элементе И 6, демультиплексоре 7.

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

Адаптивная система обработки данных, содержащая блок памяти заявок и N процессоров, каждый из которых содержит блок выполнения операций, блок коммутации и элемент ИЛИ, приче вход запроса блока памяти заявок подключен к выходу элемента ИЛИ первого процессора, вход разрешения блока памяти заявок подключен к входу разрешения блока коммутации первого процессора, первый вход элемента ИЛИ каждого процессора подключен к выходу запроса блока коммутации того же процессора, выход разрешения блока коммутации i-ro (i 1 ,1Т) процессора подключен к входу разрешения блока коммутации (1+1)-го процессора, первый запускающий вход блока выполнени операций каждого процессора подключе к запускающему входу блока коммутаций того же процессора, выход обращения блока выполнения операций подключен в каждом процессоре к входу обращения блока коммутации, вход запроса блока коммутации i-ro процессора подключен к выходу элемента ИЛИ (i-t-l)-ro процессора, входы задания режима блока коммутации каждог процессора соединены между собой и являются одноименным входом системы, отличающаяся тем, что, с целью увеличения пропускной способности системы при обработке взаимозависимых заявок за счет уменьше- ния времени простоя процессоров в последовательном режиме работы системы, в нее введены N двунаправленных переключателей, вход задания режима системы подключен к входу задания режима каждого из двунаправленных переключателей, вход адреса блока памяти заявок подключен к выходу адреса двунаправленного переключателя, вход-выход данных блока памяти заявок подключен к входам-выходам данных первого двунаправленного переключателя и первого про712;8

цессора, выход запроса первого двунаправленного переключатепя подключен к входу Ответ первого двунаправленного переключателя, входы-кы- ходы адреса данных выдачи, приема, запроса, занятости i-ro двунаправленного переключателя подключены к соответствующим входам-выходам 1-го процессора и (i-t-l)-ro двунаправленного переключателя, выход Запрос захвата i-ro двунаправленного переключателя подключен к входу Запрос захвата i-ro процессора, выход Ответ i-rn процессора подключен к входу OTsei (1+1)-го двунаправленного переключателя, причем в каждый процессор введены элемент И, демультиплексор, блок буферной памяти, информационный вход демультиплексора подключен к выходу опроса блока выполнения операций, а управляющий вход демультиплексора подключен к выходу Пуск блока буферной памяти, первый выход демультиплексора подключен к второму запускающему входу блока выполнения операций и к входу считывания блока буферной памяти, второй выход демультиплексора подключен к второму входу элемента ИЛИ, первьй вход Э11емента И подключен к выходу заполнения блока буферной памяти, второй вход элемента И подключен к входу задания режима системы, а его выход подключен к третьему входу элемента ИЛИ и к первому входу запроса блока коммутации, выход признака записи которого подключен к входу признака записи блока буферной памяти, информационный выход которого подключен к информационному входу блока выполнения операцийJ вход-выход данных .блока буферной памяти является входом-выходом данных процессора, входы-выход адреса, данных, выдачи, приема, запроса и занятости блока выполнения операций являются соответствующими входами-выходами процессора, вход Запрос захвата и выход Ответ блока выполнения операций являются соответствующими входом и выходом процессора.

Шина команд

Изобретение относится к вычислительной технике и может быть использовано в измерительно-вычислительных комплексах и авто 1атизиро- ванных системах управления на основе мультипроцессорных вычислительных систем. Целью изобретения является увеличение пропускной способности системы в режиме обработки взаимозависимых заявок за счет уменьшения времени простоя процессоров в последовательном режиме работы системы. Поставленная цель достигается тем, что в систему введены N двунаправленных переключателей, где N определяется числом процессоров в системе, а в каждый процессор введены элемент И, демультиплексор, блок буферной памяти. 18 ил. (Л

Q- ел Ц

«s

|

i

-N 3

§

«о «&

«:

Фиг.2

НК-микрокоманда. Фи,г.З

Кб

Л

От npe udt/ще о 10

Tf

9т 1Я

Г., 73

к5

Фт.б

К посае уюи ему Ю

От К35

Запись f 81 Запись в 75

Запись результата

(лг.д

/(42 Om3i ОтЗ „ „ Ofn 33

От

Фиг. 10

У У7у4У

f иг. 9

Сигна/} на i

Фи. 11

/г 74

Фаг. 12

4-f

К85

и.г.15 ,86

pwt 1

31

0m 1

0m предм- дущево 2

От 32f(32,33,1

4:

PtC3. 15

KM

Фиг. 16

ГИачапоj

Выдача сигнала опроса, из лока, Вь}д(1ча сигнала запуска по свйзи 23

Включение олока 4 по nepSou свази 15 запуска. Снятие сигналов опроса и запуска.

Считывание 9а.ннш с шин И. П в лок 4

Oifpafomtfa заявки 8 локе ftВы9ачи сигнала разрешения 8 nec edy№U4uu п{)оа,ессорг

Фиг. 17

Начат

J

8идача сигнала опросе

д

(Выдача сигна/га первого ел по связи. 11

CmfrikiffuHue Р. Ч.О заябки. с мины П 6 yieft8

включение блока, h- по fmojio- ми злпускающену Sxcdy 26. Снятие сигна/га впроса

Считывание f.4.0 заявки, из u3flo в в ffaoif

JL

.{чаетчная) зв9{кивщ

ofpauteHuiujj

SBffPyc ent rWffffflfifUfflS

j tfymwifl,,.-Ла.

выдача cuiHo/te, разрешении

В noc/fefi/fOU4UU профессор j.

Выдача Р.Ч.О. заявки 9 noc/te- уукщий процессор

±

Bbffava сигнала onpoct ufMA

с

М.О,-результат частичной обработки

CHftrme cutHeaa nfp9ot& злпрвсц