автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Организация вычисления оператора конволюции последовательностей с применением принципа волвового фронта

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ В.И.УЛЬЯНОВА (ЛЕНИНА)

Т

Ой

На правах рукописи

КРУПЫШЕВ МИХАИЛ АНАТОЛЬЕВИЧ

ОРГАНИЗАЦИЯ ВЫЧИСЛЕНИЯ ОПЕРАТОРА КОНВОЛЮЦИИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ С ПРИМЕНЕНИЕМ ПРИНЦИПА ВОЛНОВОГО ФРОНТА

Специальность 05.13:05 - Элементы и устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

САНКТ-ПЕТЕРБУРГ 1994 Г.

Работа выполнена в Санкт-Петербургском государственном электротехническом университете им. В.И.Ульянова (Ленмна)

НАУЧНЫЙ РУКОВОДИТЕЛЬ: _ г.

доктор технических наук, профессор "'Герасимов И. В.

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

Доктор технических наук, профессор Меньшиков Г.Г. Кандидат технических наук Селеджи Г. Ц.

ВЕДУЩАЯ ОРГАНИЗАЦИЯ - Институт информатики и автоматизации РАН

Защита состоится "_"__1994 г. в_часов на

заседании специализированного совета К 063.36.04 Санкт -Петербургского государственного электротехнического университета им. В.И.Ульянова (Ленина) по адресу С.Петербург, ул. Проф. Попова, 5.

С диссертацией можно ознакомиться а библиотеке университета

Автореферат разослан "_"_1994 г.

Ученый секретарь специализированного совета

ЮРКОВ '0. в.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

В этой связи нельзя не упомянуть о работах Н.Винера, использовавшего клеточно-автоматный подход для моделирования колебаний в сердечной мышце, что позволило ему обнаружить "новый тип упорядоченности в нелинейных средах - спиг ральные волны" . Известны работы А.Тьюринга - автора модели морфогенеза. Дж.фон Нейман также полагал, что "многие сложные явления, такие как самовоспроизведение, рост и развитие, морфогенез, турбулентные процессы, которые трудно моделировать с помощью дифференциальных уравнений, удастся описать с помощью клеточных автоматов".' Однако только в самые последние годы в процессе осознания фундаментальной моделирующей роли клеточных автоматов произошел подлинный прорыв. Это осознание связано, в частности, с последними работами Р.Фейнмана, а также С.Уолфрэма и ряда других авторов. "которые взглянули на физические теории с алгоритмической точки зрения" .

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

Достижение поставленной цели предусматривает решение следующих задач:

- декомпозиции алгоритма конволюции на информационную и управляющую компоненты;

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

- разработки концепции волновой обработки в рамках клеточно-автоматного подхода к организации распределенных вычислений;

- определения динамически перестраиваемой древовидной

структуры волнового процессора для вычисления конволюции;

- анализа свойств матричной среды с волновым межклеточным взаимодействием;

- планирования ресурса при организаций вычисления ли нейной свертки на клеточной среде;

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

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

Научная новизна проведенных исследований:

1. Разработана концепция навигационного поля в пространстве по управлению для класса алгоритмов типа конволюции последовательностей.

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

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

4. .Синтезированы алгоритмы планирования ресурса при организаций вычисления линейной свертки на клеточной среде.

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

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

бюджетной НИР по линии Института моделирования и интеллектуализации сложных систем).

Апробация работы. Основные положения и научные результаты диссертационной работы докладывались и обсуждались :

- на кауч.-техн. конф. профессорско-преподователь- " ского состава ЛЭТИ им. В.И.Ульянова (Ленина) 1992 г*:

- городском семинаре "теория автоматов"секцйи вычислительной техники НТО РЭС им. А. С. Попова, Санкт-Петербург, 1992,1993 гг.

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

Структура и объем работы . Диссертация состоит из введения, четырех глав с выводами, заключения, списка литературы, включающего 83 наименования и 3 приложений.

Основная часть работы изложена на 129 страницах машине писного текста. Работа содержит 76 рисунков и 2 таблицы.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Эффективная реализация оператора свертки является цену [п] - § ПСКЗ хС'п-кЗ К-0

тральным вопросом, решаемым в прикладной теории обработки сигналов.

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

1) асинхронной ;

2) синхронной ;

3) полевой (волновод .

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

В главе представлены схемы наглядно демонстрирующие

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

Решаемая задача вычисления линейной свертки представлена в префиксной операторной форме

у7 - 3(3(Б(и(х7, ПО). и(Хб. Ь1)). Б<и(х5. Л2). ЩХ4. ЬЗ)) >.

3(Б(и(хЗ. Ы), и(х2.Г15)), 3(и(х1. Ь6). ЩхО, П7)))1 где п=7 {для определенности рассмотрения обьем выборки фиксирован), и(•, •) - оператор умножения, $(•,•) - оператор суммирования.Для данной формы записи линейной свертки приведена соответствующая структура волнового процессора. Вычислительный процесс делится на две фазы. На первой фазе выполняется планирование вычислений и загрузка данных. На второй - собственно вычисления результата.

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

- Г ( Х/-1. (Х/-1) },

где X,' - значение определенного параметра отдельной ячейки, имеющей номер 1 на шаге V,

(ц) - некоторое множество ячеек, соседних с ячейкой 1. В таких системах взаимодействие между процессами осуществляется, как правило, путем непрерывной (синхронной) передачи значений непрерывной переменной. В рассматриваемо{ системе взаимодействие осуществляется путем' передачи логической информации о состоянии процесса (например, значенш предиката, отражающего состояние процесса). Это взаимодействие происходит в общем случае в заранее неизвестные моменть времени (асинхронно):

При описании поведения клеточной среды вводится два пространства - по управлению и по данным. В пространстве по управлению вводится фазовая переменная, принимающая значения от 0 до 3 . Эта переменная "видима" всем соседям клет-

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

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

- запуска, работы и остановки внутреннего таймера клетки;

- "отдыха" клетки после остановки внутреннего таймера до снятия с нее возбуждения;

- "отдыха41 клетки после снятия с нее возбуждения в результате передачи возбуждения тем ее соседям, которые способны принять это возбуждение;

- "отдыха" клетки до очередного запуска таймера.

Приводится модель развития возбуждения динамической

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

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

В третьей главе решаются задачи планирования ресурса при организации вычисления линейной свертки на клеточной среде.

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

Для реализации данной задачи предлагается описание алгоритма генерации класса Н- деревьев.

1234 ... 1234 ... 1234 ... 1234

1 2 3 4 2 1 О 1 0 1 1 0 1

2 1 .2 1 2 1

3 3 2 3 2

4 4 4 3

123 4 ... 1234 ... . 1234 ... 1234

1 2 3 4 0 1 1 0 1 2 1 0 1 2 1. 0 1 г

1 2 2 1 2 2 1 2 2 1 2

2 3 2 3 2 2 3 2 3

2 - 4 2 4 3 4 3 2 *

. Рис.1. Развитие процесса возбуждения ■ с учетом выделения отдельных подфаз изменения состояния клеток среды

Б{ и'*, *), и(».») ), и(».*). и (*,*) ) ), Б( и(*.*), и(*,*} ). 5( и{*,*), и (*,») ) ) ).

Это выражение определяет вычисление линейной свертки в префиксной форме, причем через Б обозначена операция сложе-. ния, и - операция умножения, * - аргумент. В этом случае построение дерева начинается в клетке - корне дерева.

Для построения Н-дерева порядка (1+1) из дерева порядка 1 необходимо выполнить следующее.

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

2. •Заменить каждый лист расширяемого Н-дерева порядка 1 на Й-дерево порядка 1. помещая корень Н-дерева порядка 1 в точку, где находится лист. Рис.2.

О

1

2

а б

0- -0 0- -11 -0

2' 1 - 3 - 1 2 1

0- 1 -1- -0 0- 1 -1- -0

в

Рис.2. Бинарные деревья первого (а), второго (б), третьего (в) порядков

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

( ( ( (*. *)и. (*,*)и { (*.*)и, (*.*)и )Б

( ( (*. *)и, (*,*)и ( (*.*)и,- (*, )Б )3. -.

В этом случае построение дерева следует начинать с листьев.

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

полнительным затратам на этапе организации вычислений. Снятие этих ограничений возможно путем перехода к рассмотрению так называемых Л-деревьев (рис.3).

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

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

4 4 " 3 4

4 3 2. 3 4

4 3 2 1 2 3 4

4 И 2 1 0 1 2 3 I 4 |

о

4 5-0-

-о-0

-о« 4

4 а

4 .3 4

4 3 2 3 4

| 3 2 1 2 3 4

* 3 2 1 0 1 2 Ф1

4

о

-01

-о! 4

Рис.3.Построение деревьев: а - небинарное .6- бинарное

- и -

Н-дерево глубины 1 покрывает квадрат клеточной среды, который содержит

3 . (2<1/2>М _ 1} (2С1/«>*1 - 1) клеток при четном 1. При нечётном 1 покрывается прямоугольник. который содержит

(2и/2> + 1 . 1} (2п/г>м _ 1} _ (2(1М)/!»1 -1)

5 _ -:--

2

«леток.

Предлагается второй вариант планирования ресурса $ использованием волнового алгоритма генерации Л-деревьев. Приводятся условия гарантированного построения бинарного дерева в зависимости от расположения клеток-приемников: если . клетки-приемники не, расположены в вершинах квадрата (а их 4), то построение бинарного дерева гарантируется. Рис.4. (а.Ь)

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

4 (к - 1) >- 2й. При этом предполагается, что в один ярус могут входи'ю элементы нескольких фронтов.

гп

> 3з14

4 3 1 2 1 3 ±1

га |Т 2 12 т| Ьп ,

| 4 I 3 2 10 1 2 3 I 4 |

3 2 12 3 4

4 3 12 13 4

4 | 3 || 4

а б

Рис.4. Построение бинарного дерева:

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

приемников к источнику

от

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

Представлена классификация клеток среды. Рис.5.

Трансферные клетки - это клетки среды, вошедшие в дерево, но не являющиеся его вершинами (эти клетки принадлежат пути между двумя соседними вершинами дерева).

{ Множество клеток среды )

{ Множество клеток, вошедших в дерево >

( Трансферные клетки } { Клетки-вершины дерева У

{ Множество клеток, не вошедших в дерево }

( Клетки-листья )

{ Клетки-внутренние вершины

{ Клетка-корень )

Рис. 5. Классификация клеток среды

Вершина имеет вес 0. если она является листом дерева, вес 1. если непосредственно предшествует листьям (трансферные клетки во внимание не принимаются) и т.д: по направлению к корню дерева. Дерево (приближенно) сбалансировано, если для каждой вершины дерева соответствующие два .поддерева содержат примерно равное число клеток. Для полного двоичного дерева сбалансированность предполагает примерно равное число трансферных клеток для. каждой вершины дерева. Отметим, что данный метод предполагает построение множества деревьев, содержащих минимальное число трансферных клеток

- 13 -

между соседними исходными вершинами.

Метод основывается на распространении прямой и обратных волн между-листьями, входящими в.парыи и выделения инварианта в виде суммы фронтов прямой и обратной волн.

В четвертой главе решена задача построения множества путей между клетками - листьями дерева и клетками - портами устройства ввода.

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

Предложены два варианта построения множества путей.

1. Детерминированный способ основан на распространении волны из клетки источника с использованием отношения соседства и заложенного а каждую клетку правила выбора приоритетного направления..

2. Множественный способ основан на тех же предпосылках, что и предыдущий метод, но при построении отраженных волн

вводятся правила:

а) обратные волны с одинаковыми номерами фронтов объединяются;

б) обратная волна с большим номером фронта поглощает волну с меньшим номером фронта.

Каждой клетке ставится в соответствие сумма номеров фронтов прямой и обратной волн. Эта сумма будет тем инвариантом, который определит множество клеток, которые могут потенциально войти в путь.

Каждое из выделенных подмножеств содержит пхт элементов. Любой из путей состоит только из элементов одного из подмножеств. Каждое из подмножеств содержит число путей равное

- и

(Ш+П-2)1

^й ♦ п - 2 = ~'" . . , , , . .

(П-1)I(Ш-1)!

где п X т - площадь рассматриваемых областей.

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

В общем случае путь - это вектор ( {а,0), (а-1,1), (а-2.2)..... (О,а) ). Таким образом, при множественном способе прокладки пути выделяется множество клеток, потенциально входящих в путь, а сам путь строится, как один из элементов множества, причем заранее неизвестно, какой.

В заключении диссертации перечислены основные результаты . Здесь в частности формулируются следующие выводы проведенной работы:

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Аль Ясин Дж., Крупышев М. А. Формальное описание поведения возбудимой среды с привлечением аппарата сетей Петри/ СПб. ГЭТУ - СПб., с.-Деп.В ВИНИТИ. 06.05.93, N 1204 - В93.

2. Герасимов И.В.. Крупышев М.А. Формализация описания волнового процесса с привлечением аппарата сетей массового

- 15 -

обслуживания / СПб.ГЭТУ. - СПб., с.-Деп.в ВИНИТИ. 23.07.93, Н2102-В93.

3. Крупышев М.А. Формальное описание возбудимой среды с привлечением аппарата темпоральной логики / СПб.ГЭТУ. -СПб.. с.-Деп. В ВИНИТИ. 21.07.93," N2062- В93.

Подписано в печать. Формат 60x84 1/16. Офсетная печать.

Печ.л; 1.0: уч.-изд.л. 1.0. Тираж 100 экз. Зак. N ш

Ротапринт МГП "Поликом" 197376, Санкт-Петербург ул. Проф. Попова, 5