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

Полезная модель относится к вычислительной технике и может быть использована в измерительно-вычислительных комплексах на основе мультипроцессорных вычислительных систем. Задачей полезной модели является увеличение пропускной способности вычислительной системы за счет повышения степени распараллеливания процесса обработки потока взаимозависимых заявок. Для этого в систему, содержащую блок памяти заявок, входную магистраль, линейку из M₁ модулей обработки и M₁ селекторов каналов, магистраль задания режимов работы системы, выходную магистраль передачи сигналов дополнительно введены N-1 линеек обработки, состоящих из модулей обработки, M_n блоков выбора каналов и выходной магистрали передачи сигналов, регистр задания режимов работы модулей обработки, мультиплексор/демультиплексор выходных магистралей, N дешифраторов адреса, приоритетный шифратор. 10 ил.

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

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

Для этого в систему, содержащую блок памяти заявок, входную магистраль передачи сигналов, линейку из M₁ модулей обработки и M₁ селекторов каналов, магистраль задания режимов работы системы, выходную магистраль передачи сигналов дополнительно введены N-1 линеек обработки, состоящих из модулей обработки, М_n блоков выбора каналов и выходной магистрали передачи сигналов, регистр задания режимов работы модулей обработки, мультиплексор/демультиплексор выходных магистралей, N дешифраторов адреса, приоритетный шифратор.

Из существующего уровня техники известна адаптивная система обработки данных [1], содержащая блок памяти и один модуль обработки, содержащий цепочку из N процессоров, объединенных шинами и линиями для передачи сигналов.

(А.С. SU 1455342 А1, кл. G06F 15/16, опубл. 30.01.1989. Бюл. 4).

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

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

(А.С. SU 1451713 А1, кл. G06F 15/16, опубл. 15.01.1989. Бюл. 2).

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

В качестве прототипа принята известная из существующего уровня техники адаптивная система обработки данных [3], содержащая блок памяти заявок, подключенный к входной магистрали передачи сигналов, линейку из M₁ модулей обработки с входом установки режима работы, шинным входом и K шинными выходами каждый, M₁ селекторов каналов, соответствующих модулям обработки, магистраль задания режимов работы системы, выходную магистраль передачи сигналов, содержащую шину сигналов занятости, шину сигналов запроса, шину сигналов захвата/ответа, шину приема, шину выдачи, шину адреса и шину данных, подключенных к одноименным выводам K шинных выходов каждого модуля обработки, причем входная магистраль передачи сигналов содержит шину сигналов запроса, шину сигналов разрешения, шину адреса и шину данных, выход сигналов запроса каждого модуля обработки подключен через шину запроса входной магистрали передачи сигналов к входу запроса блока памяти заявок, выходы разрешения, адреса и данных через одноименные шины входной магистрали передачи сигналов подключены к входам разрешения, адреса и данных всех селекторов каналов, у каждого из которых вход строба, выход разрешения, шина адреса и шина данных подключены к одноименным выводам шинного входа соответствующего модуля обработки.

(А.С. SU 1552195 А1, кл. G06Р 15/16, опубл. 23.03.1990. Бюл. 11). Недостатком прототипа является низкая пропускная способность системы при обработке потока заявок сложной структуры из-за ограниченной степени распараллеливания потока заявок, обусловленной наличием в системе единственной линейки обработки и единственной выходной магистрали передачи сигналов.

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

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

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

Сущность системы поясняется чертежами, на которых изображено:

на фиг.1 - схема системы;

на фиг.2 - схема модуля обработки;

на фиг.3 - схема блока захвата магистрали;

на фиг.4 - схема процессора;

на фиг.5 - схема селектора каналов;

на фиг.6 - схема блока выбора каналов;

на фиг.7 - фрагмент потока задач;

на фиг.8 - реализация задач обработки;

на фиг.9 - реализация обработки в прототипе;

на фиг.10 - реализация обработки в предлагаемой системе.

Адаптивная система обработки данных содержит (фиг.1) блок 1 памяти заявок, входную магистраль 2 передачи сигналов, одну линейку 3 обработки, N-1 линеек 4 обработки, магистраль 5 задания режимов работы системы, N выходных магистралей 6 передачи сигналов, регистр 7 задания режимов работы модулей 8 обработки, мультиплексор/демультиплексор 9 выходных магистралей с управляющим входом 10, N дешифраторов адреса 11, приоритетный шифратор 12, выходную магистраль 13 передачи сигналов системы.

Линейка 3 обработки содержит M₁ модулей 8 обработки и M₁ соответствующих им селекторов 14 каналов. Каждая из N-1 линеек 4 обработки содержит модулей 8 обработки и M_n соответствующих им блоков 15 выбора каналов.

Входная магистраль 2 передачи сигналов содержит шину 16 сигналов запроса, шину 17 сигналов разрешения, шину 18 адреса и шину 19 данных.

Выход 20 сигналов запроса каждого модуля 8 обработки линейки 3 обработки подключен через шину 16 сигналов запроса входной магистрали 2 передачи сигналов к входу запроса блока 1 памяти заявок.

Селектор 14 каналов имеет информационные входы, подключенные к одноименным шинам 17, 18 и 19 входной магистрали 2 передачи сигналов, стробирующий вход 21, выход 22 сигнала разрешения, выходы 23 и 24 адреса и данных соответственно, подключенные к одноименным выводам шинного входа соответствующего модуля 8 обработки.

Выходная магистраль 6 передачи сигналов каждой линейки обработки содержит шину 25 сигналов занятости, шину 26 сигналов запроса, шину 27 сигналов приема, шину 28 сигналов выдачи, шину 29 адреса, шину 30 данных и шину 31 сигналов захвата/ответа.

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

Блок 15 выбора каналов имеет информационные выводы, подключенные к одноименным шинам 25 сигналов занятости, 26 сигналов запроса, 27 сигналов приема, 28 сигналов выдачи, 29 адреса, 30 данных выходной магистрали 6 передачи сигналов предыдущей линейки обработки, стробирующий вход 33, выход 34 сигнала разрешения, выходы 35 и 36 адреса и данных соответственно, вход 37 подтверждения приема, а также вход 38 сигналов запроса, подключенный к выходу 20 сигналов запроса соответствующего модуля 8 обработки.

Блоки 1, 8, 14 могут быть реализованы аналогично тому, как они выполнены в прототипе [3].

Например, на фиг.2 представлена структура модуля 8 обработки, которая аналогична структуре блока обработки прототипа и может быть использована в данной полезной модели. В модуле 8 обработки имеются несколько процессоров 39, объединенных локальной магистралью 40 и блок 41 захвата магистрали. Локальная магистраль имеет шину 42 данных, шину 43 адреса, шину 44 сигналов выдачи, шину 45 сигналов приема, шину 46 сигналов захвата/ответа, шину 47 сигналов запроса и шину 48 сигналов занятости.

Блок 41 захвата магистрали (фиг.3) содержит два элемента И 49 и 50. Этот блок обеспечивает селекторам 14 каналов и блокам 15 выбора каналов наивысший приоритет доступа к локальной магистрали 40 модуля 8 обработки по отношению к процессорам 39 этого модуля обработки.

На фиг.4 показана возможная реализация процессора 39. Каждый процессор 39 имеет выход 51 разрешения, вход 52 разрешения, вход 53 запроса и выход 54 запроса, дешифратор 55 адреса, первый блок 56 буферной памяти, блок 57 выполнения операций, второй блок 58 буферной памяти, первый блок 59 обмена, первый 60 и второй 61 приемопередатчики, второй блок 62 обмена.

Первый блок 56 буферной памяти имеет вход 63 записи, выход 64 подтверждения записи, выход 65 «Заполнен», входы 66 и 67 данных и адреса соответственно, выход 68 «Пуст», вход 69 считывания, выходы 70 и 71 адреса и данных соответственно.

Блок 57 выполнения операций имеет вход 72 разрешения, выход 73 запроса, задающий вход 74, выход 75 разрешения, вход 76 запроса, первый выход 77 управления включением, выход 78 управления направлением передачи, первый выход 79 запроса захвата, первый вход 80 разрешения захвата, входы/выходы 81-84 соответственно данных, адреса, выдачи и приема, второй вход 85 разрешения захвата, второй выход 86 запроса захвата, вход 87 сигнала «Заполнен», вход 88 сигнала «Пуст», выход 89 считывания, выход 90 записи, буферные входы 91 и 92 адреса и данных соответственно, второй выход 93 управления включением.

Второй блок 58 буферной памяти имеет вход 94 адреса, выход 95 приема и вход 96 данных.

Селектор 14 каналов (фиг.5) реализуется по аналогии с прототипом и содержит приемопередатчики 97 данных, 98 адреса и селектор 99 каналов. В селекторе 14 каналов могут быть использованы стандартные микросхемы приемопередатчиков, например серий К580, К589, К555 [4, 5].

На фиг.6 показана возможная реализация блока 15 выбора каналов, который содержит приемопередатчики 100 данных и 101 адреса, триггер 102, дешифратор 103 адреса, два элемента И 104 и 105 и блок буферной памяти 106.

Блок буферной памяти по своей структуре, входам и выходам полностью соответствует блоку буферной памяти прототипа (см. [3], фиг.2, блок 42). Он имеет входы 107 адреса, 108 данных, 109 считывания, 110 записи, выходы 111 адреса, 112 данных, 113 сигнала «Пуст», 114 сигнала «Заполнен», 115 подтверждения записи.

Реализация мультиплексора/демультиплексора 9 выходных магистралей, дешифраторов адреса 11, приоритетного шифратора 12 возможна на стандартных микросхемах мультиплексоров, демультиплексоров, дешифраторов, приоритетных шифраторов соответственно, например серий К555, К533, КР1533, КР1531 [4, 5|.

Реализация регистра 7 задания режимов работы модулей обработки возможна на стандартных микросхемах регистров на основе D-триггеров, например серий К580, К555, К533, КР1533, КР1531 [4, 5].

РАБОТА СИСТЕМЫ.

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

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

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

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

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

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

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

В работе системы следует выделить следующие процессы:

1. Прием заявок на обработку первой линейкой обработки системы.

2. Обработка информации в линейках обработки.

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

4. Передача промежуточных результатов обработки от предыдущей линейки обработки к последующей линейке обработки.

5. Выдача результатов обработки любой линейки на выход системы.

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

1. Прием заявок на обработку первой линейкой обработки системы.

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

Для приема заявок на обработку каждый модуль 8 обработки линейки 3 обработки, который не загружен полностью, выставляет на выходе 20 запроса сигнал запроса. Запросы от модулей обработки по шине 16 запроса поступают на вход запроса блока 1 памяти заявок. При наличии заявок и сигнала запроса на соответствующем входе блока 1 памяти последний выставляет на шинах адреса 18 и данных 19 коды номера канала и выборки очередной заявки и выдает по шине 17 сигнал разрешения. Под действием сигнала разрешения, поступающего с выхода блока 1 памяти на синхровходы селекторов 14 каналов, на выходе 22 одного из селекторов 14 будет установлен единичный сигнал разрешения, который поступает на вход блока 41 захвата магистрали модуля 8 обработки. При этом цепь действия сигналов запроса от процессоров прерывается, так как на выходе элемента И 50 нулевой сигнал. Таким образом, на время действия сигнала разрешения по связи 22 ни один из процессоров не может осуществлять захват локальной магистрали.

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

С выхода элемента И 49 сигнал поступает на вход разрешения первого процессора рассматриваемого блока обработки и одновременно по связи 21 поступает на стробирующие входы приемопередатчиков 98 и 97 соответствующего селектора 14 каналов. В результате этого информация с шин 18 и 19 через приемопередатчики 98 и 97 по связям 23 и 24 подается соответственно на шины 43 и 42 локальной магистрали модуля 8 обработки.

Цепь распространения сигнала разрешения, поступающего на вход разрешения 52 процессора 39 модуля 8 обработки, устроена таким образом, что этот сигнал проходит на вход 90 записи блока 58 буферной памяти и разрешает запись данных в соответствующий блок с шин 42 и 43 локальной магистрали. По окончании действия сигнала разрешения локальная магистраль освобождается. Таким образом, процесс приема заявок на обработку совмещен в общем случае с процессом обработки заявок (независимо от режима работы блоков обработки).

2. Обработка информации в модулях обработки.

Режимы работы модулей 8 обработки задаются от внешних устройств по магистрали 5 задания режима работы системы путем установки в ноль (параллельная обработка) или единицу (последовательная обработка) соответствующих разрядов в регистре 7 задания режимов работы модулей обработки. Каждый выход этого регистра соединен с соответствующим входом 32 задания режима работы каждого модуля 8 обработки. Таким образом, в системе может быть реализовано несколько различных режимов обработки, что позволяет системе эффективно адаптироваться к входным потокам разной структуры.

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

В этом режиме на один модуль обработки назначаются каналы, характеризующиеся обработкой заявок, допускающих параллельное исполнение соответствующих задач. Исходное состояние модуля 8 обработки: все процессоры 39 свободны, блок 58 буферной памяти пуст (значение сигнала «Пуст» на выходе 88 равно единице, значение сигнала «Заполнен» на выходе 87 - нулю), значение сигнала на входе 32 задания режима работы равно нулю. В этом случае каждый процессор 39 выдает сигнал запроса с выхода 54. Сигнал разрешения, поступающий из блока 41 захвата магистрали на вход первого процессора модуля обработки, проходит последовательно через все процессоры и производит запись очередной заявки в блок 58 буферной памяти последнего процессора, выставившего запрос. При появлении в блоке 58 буферной памяти хотя бы одной заявки сигнал на выходе 88 «Пуст» становится равным нулю, поэтому сигнал опроса по связи 89 производит считывание очередной заявки из блока 58 буферной памяти, и блок 57 выполнения операций включается в работу. Если блок 58 буферной памяти пуст, то свободный процессор при отсутствии запросов от последующих процессоров производит прием заявки с шин 42 и 43 локальной магистрали 40 по сигналу разрешения. По номеру канала, считанному в блок 57, определяется программа обработки заявки (номер первой выполняемой команды). Если блок 58 буферной памяти заполнен, то сигнал на выходе 87 этого блока равен единице, а на выходе 88 равен нулю. В этом случае по окончании обработки заявки формируется сигнал запроса, не дожидаясь окончания цикла считывания из блока 58.

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

Результаты обработки заявок выдаются процессором 39 через соответствующую выходную магистраль 6 передачи сигналов линейки обработки для передачи на последующую линейку 4 обработки или на соответствующий информационный вход мультиплексора/демультиплексора 9 выходных магистралей для выдачи результатов на выход системы.

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

В этом режиме на один модуль обработки назначаются каналы, характеризующиеся обработкой заявок, допускающих последовательное исполнение соответствующих задач. Каждая заявка последовательно обслуживается в каждом процессоре модуля обработки по частям, начиная с первого процессора этого модуля. Исходное состояние модуля 8 обработки: все процессоры 39 свободны, блок 58 буферной памяти пуст (значение сигнала «Пуст» на выходе 88 равно единице, значение сигнала «Заполнен» на выходе 87 - нулю), значение сигнала на входе 32 задания режима работы равно единице. В этом режиме сигнал запроса на выходе каждого процессора 39 формируется так же, как и в параллельном режиме. Запросы на выходе 54 модуля обработки в последовательном режиме формируются только от первого процессора 39 этого модуля обработки. Появление сигнала разрешения на входе 52 разрешения первого процессора инициирует запись заявки по связи 90 в блок 58 буферной памяти первого процессора 39 модуля 8 обработки. Если блок 58 буферной памяти первого процессора пуст в момент появления сигнала разрешения на входе 52 разрешения, то инициируется прием заявки с шин 42 и 43 в первый процессор и ее обработка в нем. Если блок 58 не пуст, то первый процессор при его освобождении принимает очередную заявку, которую начинает обрабатывать по соответствующему алгоритму частичной обработки. Первый процессор 39 модуля 8 обработки, выполнив первую часть алгоритма обработки заявки, выдает сигнал разрешения с выхода 51 разрешения на вход 52 разрешения второго процессора. По этому сигналу во втором процессоре происходят такие же действия, что и в первом процессоре. При этом в блоке 57 второго процессора выполняются вторые части алгоритмов обработки заявок. Работа остальных процессоров 39 модуля 8 обработки в последовательном режиме происходит аналогичным образом.

Результаты обработки заявок выдаются процессором 39 через соответствующую выходную магистраль 6 передачи сигналов линейки обработки для передачи на последующую линейку 4 обработки или на соответствующий информационный вход мультиплексора/демультиплексора выходных магистралей 9 для выдачи результатов на выход системы.

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

При наличии информационной зависимости между обрабатываемыми заявками может возникнуть (запрограммированная) потребность в передаче/приеме результатов обработки от процессоров одних модулей обработки к процессорам других модулей обработки одной и той же линейки обработки. Для передачи результатов обработки от процессора 39 одного модуля 8 обработки к процессору 39, находящемуся в другом модуле 8 обработки этой же линейки обработки, предусмотрена команда, по которой формируются требования на подключение выходной магистрали 6 соответствующей линейки обработки. Эта магистраль подключается в том случае, если нет сигнала занятости на шине 25. О захвате выходной магистрали 6 первый блок 59 обмена сообщает блоку 57 выполнения операций передающего процессора 39 сигналом по связи 80. При этом блок 59 передающего процессора сразу выставляет сигнал занятости на шине 25 выходной магистрали 6, запрещая доступ к этой магистрали остальным процессорам системы.

После того, как выходная магистраль 6 захвачена, активизируется сигнал 77 на подключение выходной магистрали 6 к информационным выводам 81-84 блока 57 через первый приемопередатчик 60. После этого передающий процессор 39 выставляет адрес процессора-абонента и передаваемые данные соответственно на шинах 29 и 30. Независимо от состояния процессора-абонента передаваемый адрес дешифрируется в дешифраторе 55, и последний выдает сигнал записи в блок 56 буферной памяти по связи 63. В результате адрес и данные с шин 29 и 30 записываются в блок 56 буферной памяти, который сигналом подтверждения записи по связи 64 через шину 27 освобождает доступ к выходной магистрали другим процессорам. На этом процесс передачи информации от процессора одного модуля обработки к процессору другого модуля обработки одной и той же линейки по выходной магистрали заканчивается.

Прием данных в блок 56 буферной памяти может осуществляться до тех пор, пока не произойдет заполнение блока 56 буферной памяти. В случае заполнения блока 56 сигнал «Заполнен» по связи 66 поступает на шину 25 занятости выходной магистрали, завершая передачу данных по этой магистрали. Полученные данные по результатам обработки информационно зависимых заявок, записанные в блок 56 буферной памяти, далее используются процессором. При этом считывание данных из блока 56 буферной памяти в блок 57 выполнения операций происходит при выполнении соответствующей команды, активизирующей сигнал считывания по связи 69.

4. Передача промежуточных результатов обработки от предыдущей линейки обработки к последующей линейке обработки.

Для передачи результатов обработки от любого процессора 39 любого модуля 8 обработки i-ой линейки к любому модулю 8 обработки (i+1)-ой линейки в процессорах 39 предусмотрено выполнение команды, по которой формируется требование на подключение выходной магистрали 6 i-ой линейки к передающему процессору 39 этой линейки. Выходная магистраль 6 подключается в том случае, если нет сигнала занятости на шине 25 занятости этой магистрали. О захвате магистрали первый блок 59 обмена передающего процессора сообщает блоку 57 выполнения операций этого процессора первым сигналом разрешения захвата по связи 80. При этом первый блок 59 обмена передающего процессора сразу выставляет сигнал занятости на шине 25 занятости выходной магистрали 6 i-ой линейки, препятствуя доступу к этой магистрали остальным процессорам i-ой линейки.

После того, как выходная магистраль 6 i-ой линейки захвачена, в передающем процессоре на выходе 77 активизируется первый сигнал управления на подключение этой выходной магистрали через первый приемопередатчик 60 к выводам 30 данных, 29 адреса, 28 выдачи и 27 приема блока обработки 57 передающего процессора.

Затем передающий процессор выставляет адрес блока 15 выбора каналов (i+1)-ой линейки обработки (которому предназначены данные) на шине 29 адреса и передаваемые данные на шине 30 данных выходной магистрали 6 i-ой линейки. Адрес и данные поступают на все блоки 15 выбора каналов (i+1)-ой линейки, а так же на все процессоры 39 i-ой линейки и на соответствующий информационный вход мультиплексора/демультиплексора 9 выходных магистралей.

В блоках 15 выбора каналов адрес блока выбора каналов поступает на дешифратор 103 адреса, который совместно с элементом И 104 при совпадении адреса и равенстве нулю на выходе 114 значения сигнала «Заполнен» выдает на вход 110 записи сигнал записи.

В результате адрес и данные с шин 29 адреса и 30 данных выходной магистрали 6 i-ой линейки записываются в блок 106 буферной памяти блока 15 выбора каналов. Далее блок 106 буферной памяти сигналом подтверждения записи с выхода 115 через шину 27 приема выходной магистрали 6 освобождает доступ к выходной магистрали 6 i-ой линейки другим процессорам 39 этой линейки.

Если значение сигнала «Заполнен» на выходе 114 равно единице (нет свободных ячеек в блоке 106 буферной памяти), то передающий процессор, не дождавшись подтверждения записи на шине 27 приема выходной магистрали 6, откладывает запись информации до момента появления свободных ячеек памяти в блоке 106 буферной памяти (до тех пор, пока значение сигнала «Заполнен» на выходе 114 не станет равным нулю).

На этом процесс передачи результатов обработки по выходной магистрали 6 от i-ой линейки к (i+1)-ой линейке заканчивается.

Записанные в блок 106 буферной памяти результаты обработки для соответствующего модуля 8 обработки (i+1)-ой линейки являются заявками на обработку.

Для дальнейшей работы модуль 8 обработки выполняет процедуру приема заявок на обработку от блока 106 буферной памяти. Для этого модуль 8 обработки (i+1)-ой линейки, если он не загружен полностью, выставляет на выходе 20 запроса сигнал запроса, который поступает по связи 38 на вход установки в единицу триггера 102 соответствующего блока 15 выбора каналов для выработки сигнала разрешения на передачу информации в процессор.

Если в блоке 106 буферной памяти блока 15 выбора каналов есть хотя бы одна необработанная заявка (значение сигнала «Пуст» на выходе 113 равно нулю), то в ответ на сигнал запроса с выхода элемента И 105 блока 15 выбора каналов по связи 34 на модуль 8 обработки выдается сигнал разрешения, который поступает на блок 41 захвата локальной магистрали 40 модуля 8 обработки. При этом цепь действия сигналов запроса от процессоров 39 прерывается, так как на выходе элемента И 50 блока 41 захвата присутствует нулевой сигнал. Таким образом, на время действия сигнала разрешения ни один процессор 39 модуля 8 обработки не может осуществлять захват локальной магистрали 40.

Если на шине 48 занятости локальной магистрали 40 отсутствует сигнал занятости, то сигнал разрешения проходит через элемент И 49 блока 41 захвата магистрали.

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

С выхода элемента И 49 сигнал разрешения поступает на вход 52 разрешения первого процессора рассматриваемого модуля обработки и одновременно по линии 33 строба поступает на стробирующие входы приемопередатчиков 101 адреса и 100 данных блока 15 выбора каналов, а также на вход 109 считывания блока 106 буферной памяти. В результате этого информация из блока 106 буферной памяти через приемопередатчики 101 адреса и 100 данных по соответствующим связям подаются на шину 43 адреса и шину 42 данных локальной магистрали 40 модуля 8 обработки.

Цепь распространения сигнала разрешения, поступающего на вход 52 первого процессора модуля 8 обработки, устроена таким образом, что этот сигнал проходит на вход 90 записи второго блока 58 буферной памяти процессора 39 и разрешает запись информации в этот блок с шин 43 адреса и 42 данных локальной магистрали 40.

По окончании записи процессор 39, принявший заявку, выставляет на шине 45 приема локальной магистрали 40 сигнал подтверждения приема информации, который по связи 37 поступает на вход установки в ноль триггера 102 блока 15 выбора каналов. При этом сигнал разрешения на выходах элементов И 105 и 49 прекращает свое действие и локальная магистраль 40 освобождается, а переданная заявка удаляется из блока 106 буферной памяти.

В случае если в блоке 106 буферной памяти блока выбора каналов нет заявок (значение сигнала «Пуст» равно единице), то модуль обработки продолжает работу по заданной программе, ожидая появления заявок (установления значения сигнала «Пуст» равным нулю).

5. Передача результатов обработки любой линейки на выход системы.

Для передачи результатов обработки от любого процессора 39 любого модуля 8 обработки любой линейки обработки на выход системы в процессорах 39 предусмотрено выполнение команды, по которой формируется требование на подключение выходной магистрали 6 линейки обработки к передающему процессору 39 этой линейки. Выходная магистраль 6 подключается в том случае, если нет сигнала занятости на шине 25 занятости этой магистрали. О захвате магистрали первый блок 59 обмена передающего процессора 39 сообщает блоку 57 выполнения операций этого процессора первым сигналом разрешения захвата, поступающий на вход 80. При этом первый блок 59 обмена передающего процессора 39 сразу выставляет сигнал занятости на шине 25 занятости выходной магистрали 6 данной линейки обработки, запрещая доступ к этой магистрали остальным процессорам рассматриваемой линейки обработки.

После того, как выходная магистраль 6 линейки обработки захвачена, в передающем процессоре 39 на выходе 77 активизируется первый сигнал управления на подключение этой выходной магистрали через первый приемопередатчик 60 к выводам 81-84 данных, адреса, выдачи и приема блока 57 обработки передающего процессора.

Затем передающий процессор 39 выставляет адрес линейки обработки (от которой данные должны быть выданы на выход системы) на шине 29 адреса и передаваемые данные на шине 30 данных выходной магистрали 6, которые поступают на соответствующий информационный вход мультиплексора/демультиплексора 9 выходных магистралей, на все блоки 15 выбора каналов последующей линейки обработки, а так же на все процессоры 39 текущей линейки обработки.

С шины 26 адреса текущей линейки обработки адрес линейки обработки поступает на соответствующий дешифратор 11 адреса, который при совпадении адреса выдает единичный сигнал на соответствующий вход приоритетного шифратора 12. При выборе выходных магистралей для передачи информации на выход системы реализован приоритет по номеру выходной магистрали 6. Магистраль с меньшим номером имеет наивысший приоритет, так как наибольшая частота поступающих на обработку потоков информации имеется у первой линейки обработки. С выхода приоритетного шифратора 12 на управляющий вход 10 мультиплексора/демультиплексора 9 выходных магистралей поступает двоичный код, соответствующий номеру старшей выходной магистрали 6, претендующей на подключение к выходной магистрали системы 13. При этом все шины выходной магистрали 6 выбранной линейки обработки оказываются подключенными к одноименным шинам выходной магистрали системы 13. На выход системы поступают результаты обработки от этой линейки обработки. По окончании передачи результатов обработки на шине 25 приема выходной магистрали 6 появляется сигнал подтверждения приема, выдаваемый устройством, подключенным к выходной магистрали системы 13 и принявшим эти результаты. При этом код номера выходной магистрали 6 с выхода приоритетного шифратора 12 снимается, выходная магистраль системы 13 отключается от выходной магистрали 6 выбранной линейки обработки и освобождается.

ОЦЕНКА ПОЛОЖИТЕЛЬНОГО ТЕХНИЧЕСКОГО ЭФФЕКТА ОТ ПРИМЕНЕНИЯ ПОЛЕЗНОЙ МОДЕЛИ.

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

Рассматриваемый фрагмент потока задач сложной структуры характеризуется высокой степенью связанности между исполняемыми задачами S_i , , т.к. результаты обработки одних задач являются входными данными для других задач. Каждая связь, показанная дугой, характеризуется объемом v_j данных, передаваемых от задачи к задаче в потоке.

Пусть в потоке каждая задача S _i характеризуется двумя параметрами обработки:

средним временем _ср выполнения задачи на одном модуле обработки;

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

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

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

, (задач/с).

В реальной системе пропускная способность зависит от структуры системы.

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

Оценка пропускной способности прототипа.

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

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

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

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

Тогда реальная пропускная способность системы-прототипа составит

, (задач/с).

Опенка пропускной способности предлагаемой системы.

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

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

На каждую выходную магистраль выдается общий объем передаваемых данных 4_ср. При этом с учетом коэффициента совмещения k₁0,1..0,4 среднее общее время, необходимое на выполнение задачи и передачу данных состава .

Тогда реальная пропускная способность предлагаемой системы составит

(задач/с).

Опенка выигрыша.

Особенность потоковых задач состоит в том, что время t_ср , затрачиваемое на передачу данных объемом _ср от одной задачи S обычно составляет t _ср=k_2ср, где k₂0,1..0,3. То есть, на 100 команд выполнения различных операций в вычислительных системах вполне реальны 10...30 команд передач данных. Это объясняется тем, что задачи обработки реализуются достаточно короткими с целью повышения пропускной способности системы.

С учетом этого, выигрыш в пропускной способности от применения предлагаемой системы по сравнению с прототипом составит:

Численное значение выигрыша от применения полезной модели в зависимости от значения коэффициентов k ₁ и k₂ представлено в таблице.

k1	0,10	0,20
k 2	0,10	0,15	0,20	0,25	0,30	0,10	0,15	0,20	0,25	0,30
с прот	0,86	0,81	0,76	0,71	0,68	0,76	0,68	0,61	0,56	0,51
с предл	0,96	0,94	0,93	0,91	0,89	0,93	0,89	0,86	0,83	0,81
	1,12	1,17	1,22	1,27	1,32	1,22	1,32	1,41	1,50	1,58
k1	0,30	0,40
k 2	0,10	0,15	0,20	0,25	0,30	0,10	0,15	0,20	0,25	0,30
с прот	0,68	0,58	0,51	0,45	0,41	0,61	0,51	0,44	0,38	0,34
с предл	0,89	0,85	0,81	0,77	0,74	0,86	0,81	0,76	0,71	0,68
	1,32	1,46	1,58	1,69	1,79	1,41	1,58	1,73	1,86	1,97

Таким образом, в предлагаемой системе пропускная способность на рассмотренном фрагменте потока задач в 1,121,97 раза выше, чем в прототипе при одинаковых заданных коэффициентах k₁ и k₂ При этом организация исполнения задач в линейках обработки должна соответствовать структуре потока, т.е. структура системы и процесс выполнения задач должны быть настроены на структуру входного потока задач. В предлагаемой системе адаптация структуры под различные входные потоки задач обеспечивается более гибко, чем в прототипе.

ЛИТЕРАТУРА

1. В.М.Антонов, В.Н.Середкин, В.А.Курчидис, Н.А.Андреев, К.П.Тиханович. Адаптивная система обработки данных. Авторское свидетельство СССР SU 1455342 А1, кл. G06F 15/16, опубл. 30.01.1989. Бюл. 4.

2. В.А.Курчидис. Адаптивная система обработки данных. Авторское свидетельство СССР SU 1451713 А1, кл. G06F 15/16, опубл. 15.01.1989. Бюл. 2.

3. В.А.Курчидис, М.Л.Королев. Адаптивная система обработки данных. Авторское свидетельство СССР SU 1552195 А1, кл. G06F 15/16, опубл. 23.03.1990. Бюл. 11.

4. Пухальский Г.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах: Справочник. - М.: Радио и связь, 1990. - 304 с.: ил.

5. Пухальский Г.И. Проектирование микропроцессорных устройств:

Учебной пособие для вузов. - СПб.: Политехника, 2001. - 544 с.: ил.

Адаптивная система обработки данных, содержащая блок памяти заявок, подключенный к входной магистрали передачи сигналов, линейку из M₁ модулей обработки с входом установки режима работы, шинным входом и К шинными выходами каждый, M ₁ селекторов каналов, соответствующих модулям обработки, магистраль задания режимов работы системы, выходную магистраль передачи сигналов, содержащую шину сигналов занятости, шину сигналов запроса, шину сигналов захвата/ответа, шину приема, шину выдачи, шину адреса и шину данных, подключенных к одноименным выводам К шинных выходов каждого модуля обработки, причем входная магистраль передачи сигналов содержит шину сигналов запроса, шину сигналов разрешения, шину адреса и шину данных, выход сигналов запроса каждого модуля обработки подключен через шину запроса входной магистрали передачи сигналов к входу запроса блока памяти заявок, выходы разрешения, адреса и данных через одноименные шины входной магистрали передачи сигналов подключены к входам разрешения, адреса и данных всех селекторов каналов, у каждого из которых вход строба, выход разрешения, шина адреса и шина данных подключены к одноименным выводам шинного входа соответствующего модуля обработки, отличающаяся тем, что, с целью увеличения пропускной способности системы за счет повышения степени распараллеливания процесса обработки входного потока данных, в систему введены N-1 линеек обработки, каждая из которых содержит M_n (n=) модулей обработки, М_n, соответствующих им блоков выбора каналов и выходную магистраль передачи сигналов, а также в систему введены регистр задания режимов работы модулей обработки с количеством выходов, соответствующим общему количеству модулей обработки в системе, подключенный своими входами к магистрали задания режимов работы системы, причем каждый выход этого регистра подключен к входу установки режима работы соответствующего модуля обработки системы, входы сигналов разрешения, шин адреса и данных, выходы сигналов запроса, строба и подтверждения приема каждого модуля обработки подключены к одноименным выводам соответствующего блока выбора каналов каждой введенной линейки обработки, к входам каждого блока выбора каналов каждой введенной линейки обработки подключены шины адреса, данных, сигналов выдачи, приема, запроса и занятости, соединенные с одноименными шинами выходной магистрали передачи сигналов предыдущей линейки обработки, каждая из N выходных магистралей передачи сигналов подключена к соответствующему информационному входу мультиплексора/демультиплексора выходных магистралей, причем к шине адреса каждой из N выходных магистралей передачи сигналов подключен вход соответствующего дешифратора адреса, выход каждого дешифратора адреса соединен с соответствующим входом приоритетного шифратора, выход приоритетного шифратора подключен к управляющему входу мультиплексора/демультиплексора выходных магистралей, к информационному выходу которого подключена выходная магистраль передачи сигналов системы.