BC/NW 2014 №1 (24) :8.4

ОБ ОДНОМ ПОДХОДЕ К АГРЕГАЦИИ АСИНХРОННЫХ АВТОМАТНЫХ СХЕМ НА РЕГУЛЯРНЫХ КОМПОНЕНТАХ

Гущин К.И., Калинина Г.А.

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

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

Предлагаемый метод агрегации регулярных компонентов включает следующие основные этапы:

1. Для каждого компонента СхОД по описанию его диаграммы перехо-дов строится развернутая диаграмма переходов (РДП), содержащая α ра-бочих циклов, где α – коэффициент разметки компонента [1].

2. По РДП компонентов строится граф зависимостей (ГЗ) СхОД. В ГЗ РДП компонентов представляются линейными графами, связанными друг с другом дугами, отображающими акты передачи данных между компонентами через связывающие их буферы.

3. ГЗ приводится к гамачной форме, вершины и дуги которой взвешены временными параметрами, характеризующими исходную СхОД.

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

Литература

1. Калинина Г.А., Мороховец Ю.Е.Задача анализа реализуемости асинхрон-ных автоматных схем с регулярными компонентами. // Электронный журнал ВЫЧИСЛИТЕЛЬНЫЕ СЕТИ. Теория и практика / NETWORK-JOURNAL. Theory and practice. 2012 (21). № 2.