Модуль синхростратума для волновой обработки данных

Модуль синхростратума для волновой обработки данных

Иллюстрации

Показать все

Реферат

Изобретение относится к области вычислительной техники и дискретной автоматики.

В асинхронных системах, содержащих множество взаимодействующих блоков, а также ГАЛС (Глобально Асинхронных Локально Синхронных) или ГАЛП (Глобально Асинхронных Локально Произвольных) систем, удобно систему разбивать на два слоя, или стратума, один из которых состоит из управляемых блоков и является процессорным стратумом, а другой осуществляет управление блоками, координируя их взаимодействие, и является синхростатумом. Такое представление систем позволяет строить подсистему управления, абстрагируясь от конкретных реализаций системных блоков. При этом каждому блоку системы ставится в соответствие модуль синхростратума, который связан с управляемым блоком и с соседними модулями синхростратума парами управляющих сигналов по принципу запрос-ответ.

Так, известна схема управления асинхронным конвейером, состоящая из С-элементов Малера и инверторов. С-элемент Маллера - это триггерное устройство, выход которого принимает значение "лог. 1", если все его входы имеют значение "лог. 1", и значение "лог. 0", когда все его входы имеют значение "лог. 0", в противном случае выход устройства сохраняет предыдущее значение (Айвэн Сазерленд, "Micropipelines", CommunicationofACM, June 1989, Volume 32, Number 6, p. 728-730).

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

Наиболее близким по технической сути достигаемому результату является схема модуля синхростратума для конвейерной обработки данных, содержащая два С-элемента Маллера и инвертор, выход которого соединен с первым входом первого С-элемента Маллера, второй вход первого С-элемента Маллера соединен с выходом второго С-элемента Маллера предыдущего модуля, передающего управление, выход второго С-элемента Маллера соединен со входом инвертора и входом первого С-элемент Маллера следующего модуля, принимающего управление, первый вход второго С-элемента Маллера соединен с выходом элемента задержки (Айвэн Сазерленд, "Micropipelines", CommunicationofACM, June 1989, Volume 32, Number 6, p. 725-726).

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

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

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

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

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

Указанный технический результат достигается тем, что модуль синхростратума для волновой обработки данных, содержащий два многовходовых С-элемента Маллера и инвертор, выход которого соединен с первым входом первого многовходового С-элемента Маллера, второй вход первого многовходового С-элемента Маллера соединен с выходом второго многовходового С-элемента Маллера предыдущего модуля, передающего управление, выход второго многовходового С-элемента Маллера соединен со входом инвертора и входом первого многовходового С-элемент Маллера следующего модуля, принимающего управление, первый вход второго многовходового С-элемента Маллера соединен с выходом элемента задержки, согласно изобретению модуль синхростратума снабжен многовходовым элементом И и двухвходовым элементом ИЛИ-НЕ и имеет дополнительные входы первого многовходового С-элемента Маллера, дополнительные входы второго многовходового С-элемента Маллера, при этом каждый из дополнительных входов первого многовходового С-элемента Маллера соединен с соответствующим выходом второго многовходового С-элемента Маллера соседних модулей, передающих управление, выход первого многовходового С-элемента Маллера соединен с первым входом многовходового элемента И, с первым входом двухвходового элемента ИЛИ-НЕ и со вторым входом второго многовходового С-элемента Маллера, а выход второго многовходового С-элемента Маллера соединен со входами первых многовходовых С-элементов Маллера соседних модулей, принимающих управление, причем каждый из дополнительных входов многовходового С-элемента Маллера соединен с одним из входов многовходового элемента И и подключен к выходу двухвходового элемента ИЛИ-НЕ соответствующего соседнего модуля, подтверждающего прием управления, при этом в качестве элемента задержки использован автомат Мура, вход фазового сигнала которого соединен с выходом многовходового элемента И, а второй вход двухвходового элемента ИЛИ-НЕ подключен к выходу сигнала завершения блокировки информационных входов управляемого автомата Мура, причем выход двухвходового элемента ИЛИ-НЕ соединен с соответствующими дополнительными входами вторых многовходовых С-элементов Маллера и входами многовходовых элементов И всех соседних модулей, ожидающих подтверждения приема управления.

Изобретение поясняется чертежами, где на Фиг. 1 изображена схема модуля синхростратума; на Фиг. 2 изображена схема для моделирования поведения модуля синхростратума; на Фиг. 3 изображена сеть Петри для моделирования поведения элемента И; на Фиг. 4 изображена сеть Петри, описывающая работу модуля синхростратума.

Модуль синхростратума содержит многовходовый С-элемент Маллера 1, двувходовый элемент ИЛИ-НЕ 2, инвертор 3, многовходовый С-элемент Маллера 4, многовходовый элемент И 5, группу входов 6 сигналов запроса, подключенных ко входам элемента 1, выход 7 сигнала ответа на запросы по входам 6, выход 8 сигнала запроса, подключенный к выходу многовходового С-элемента Маллера 4, группу входов 9 сигналов ответа на запрос по выходу 8, подключенных ко входам многовходового С-элемента Маллера 4 и многовходового элемента И 5, выход 10 фазового сигнала, управляющего работой автомата Мура 11, подключенный к выходу многовходового элемента И 5, вход 12 сигнала индикации блокировки информационных входов автомата Мура 11, подключенный к первому входу двувходового элемента ИЛИ-НЕ 2, вход 13 сигнала завершения переходных процессов в автомате Мура 11, подключенный к первому входу многовходового С-элемента Маллера 4, причем выход многовходового С-элемента Маллера 1 соединен со вторыми входами двувходового элемента ИЛИ-НЕ 2 и многовходового С-элемента Маллера 4 и с первым входом многовходового элемента И 5, выход инвертора 3 соединен с одним из входов элемента 1, а вход инвертора 3 соединен с выходом многовходового С-элемента Маллера 4.

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

Работу схемы модуля удобно пояснить на примере простого конвейера, в котором соединения между блоками системы могут быть представлены последовательным орграфом. В этом случае группы входов 6 и выходов 9 представлены одиночными входами 6 и выходами 9.

Структура автомата Мура в модели Хаффмана состоит из комбинационной схемы, реализующей функции переходов, и двух регистров: основного R1 (на чертежах не показан) и вспомогательного R2 (на чертежах не показан). При конвейерной обработке данных в качестве выходов i-го автомата удобно использовать выходы его основного регистра R1_i, а в качестве информационных входов - выходы основного регистра R1_i-1 предыдущего (i-1)-го автомата. Работа автомата состоит из двух фаз, соответствующих значениям фазового сигнала а. В первой фазе (например, a="лог. 1") вычисляется новое состояние и записывается в основной регистр, при этом реализуется функция переходов:

R1_i(t):=F[R1_i-1(t),R₂,(t-1)] (запись в регистр R2i блокирована),

где t - шаг алгоритма; во второй фазе (а="лог. 0") осуществляется перепись данных из основного регистра во вспомогательный:

R2_i(t):=R1_i(t) (запись в регистр R1_i блокирована).

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

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

Схема работает следующим образом. Пусть, начиная с данного модуля, синхростратум находится в пассивном состоянии. Это означает, что данный модуль и все следующие за ним находятся в состоянии, в котором выходы обоих многовходовых С-элементов Маллера (1 и 4) имеют значение "лог. 0". Тогда выходы 8, 10 и входы 6, 12 и 13 будут иметь значение "лог. 0", а выход 7, выход инвертора 3 и вход 9 - значение "лог. 1". После завершения перехода предыдущим автоматом Мура (сформированы данные на его регистре R1) на входе 6 появляется "лог. 1". При этом выход многовходового С-элемента Маллера 1 становится равным "лог. 1" и срабатывают двувходовый элемент ИЛИ-НЕ 2 и многовходовый элемент И 5. На выходе 7 появляется "лог. 0", а на выходе 10 - "лог. 1". Сигнал с выхода 7 (ответ предыдущему модулю) инициирует вторую фазу работы предыдущего автомата: блокируются входы регистра R1, при этом R1 продолжает хранить информацию. А в случае использования автомата Мура, информация переписывается из R1 в R2. При появлении "лог. 1" на выходе 10 начинается фаза перехода автомата и "лог. 1" сначала появляется на входе 12, а затем по окончании переходного процесса в автомате на входе 13. Срабатывает многовходовой С-элемент Маллера 4, и на его выходе появляется "лог. 1", которая передается с выхода 8 следующему модулю (запрос) и переключает выход инвертора в "лог. 0".

Появление "лог. 1" на выходе 8 является запросом на работу следующего модуля синхростратума, который отвечает "лог. 0" на входе 9. При получении ответа от правого соседа срабатывает многовходовый элемент И 5 и на выходе 10 появляется сигнал "лог. 0", который инициирует вторую фазу в автомате, при выполнении которой "лог. 0" сначала появляется на входе 12 (входы регистра R1 заблокированы), а затем на входе 13 (переходный процесс второй фазы закончен).

Появление сигнала со значением "лог. 0" на входе 6 означает запрос завершения волны. При этом выход многовходового С-элемента Маллера 1 становится равным "лог. 0" и только после блокировки входов регистра R1 автомата ("лог. 0" на входе 12) срабатывает двувходовый элемент ИЛИ-НЕ 2 и на выходе 7 появляется значение "лог. 1", которое разрешает предыдущему модулю начать новый переход в своем автомате. При этом изменение состояния его регистра R1 не влияет на состояние регистра R1 следующего автомата. Появление "лог. 0" на выходе С1, на входе 13 и на входе 9 вызывает изменение состояния многовходового С-элемента Маллера 4 на "лог. 0", что является сигналом следующему модулю о завершении волны.

Обычно принято иллюстрировать работу устройства с помощью сигнальных графов, которые являются частным случаем сетей Петри и с их помощью можно представлять только устойчивые и безопасные сети Петри. В данном случае нарушено свойство устойчивости из-за наличия в схеме элемента И. Действительно, выход элемента И принимает значение "лог. 0" при появлении "лог. 0" на одном из его входов, причем эти события на его входах не упорядочены, т.е. имеет место свободный выбор и, следовательно, нарушено свойство устойчивости. Тем не менее работу схемы модуля можно описать с помощью сетей Петри.

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

Поведение всех элементов этой схемы, за исключением элемента И, описывается сигнальным графом. Поведение элемента И может быть описано с помощью фрагмента сети Петри. На этом фрагменте введены 4 вспомогательных события (b1 - b4) и 6 позиций (p1 - р6). Такая конструкция сети Петри применена для того, чтобы исключить накопление точек в позиции свободного выбора, т.е. для того, чтобы сделать сеть безопасной, что необходимо для получения ее реализации в виде схемы. События С1-, R- и AND- означают переключения сигналов C1, R и AND из состояния "лог. 1" в состояние "лог. 0", а событие AND+ - переключение сигнала AND из состояния "лог. 0" в состояние "лог. 1". При начальном состоянии сигнала AND="лог. 0" маркер находится в позиции р5.

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

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