Введение к работе
Актуальность работы. Несмотря на достигнутые успехи в области организации вычисления оператора конволюции с учетом ограничений со стороны современной технологии СБИС, ряд теоретических и практически важных вопросов, касающихся организации распределенных отношений, до сих пор открыт.
Не решены вопросы установления взаимосвязи среды реализации и классов наиболее предпочтительных для решения задач, что позволило бы естественно отразить параллелизм оператора свертки с' учетом условий обеспечения погрешности вычислений. Именно на этом пути структуризации - представлении аппаратной системы совокупностью параллельно работающих Простых и однотипных модулей, каждый из которых решает локальную задачу обработки и транспорта данных, а все модули координируются для решения общей задачи, многие исследователи видят решение проблемы технологичных и надежных сред реализации.- К их числу относятся и так называемые волновые структуры. Этот термин обязан своему появлению результатам, полученным в области асинхронных клеточных структур типа систолических сред.
Формирование вычислительного .процесса в таких средах осуществляется управлением, которое воспринимает информацию о состоянии вычислений в информационном пространстве (пространстве данных) и на основании этой информации выясняет готовность отдельных подпроцессов к выполнению, способ организации обменов данными между подпроцессами и характер управления базируются на запрос-ответной дисциплине взаимодействия между отдельными компонентами среды реализации. Для волнового принципа организации вычисления характерно наличие двух фаз процесса вычисления: рабочая и пассивная. В- первой реализуется преобразование или транспорт данных, во второй осуществляется подготовка к,выполнению возложенных на компоненту среды функций. Благодаря чередованию этих фаз при композиции подпроцессов формируется самовоспроизводящийся механизм продвижения данных по компонентам среды реализации и во времени, похожий на механизм распространения волн в возбудимых средах. Именно поэтому рассматривав-
-2--мые в работе структуры и процессы получили название волновых. В них реализуется конвейерный параллелизм со многими свойственными ему достоинствами и недостатками, причем благодаря асинхронности протекания отдельных подпроцессов приобретаются новые качества, возникают требующие детального исследования новые проблемы. Решению ряда из них и -посвящена настоящая работа.
В этой связи нельзя не упомянуть о работах Н.Винера, использовавшего клеточно-автоматный подход для моделирования колебаний в сердечной мышце, что позволило ему обнаружить "новый тип упорядоченности в нелинейных средах - СПИг ральные волны" . Известны работы А.Тьюринга - автора модели морфогенеза. Дж.фон Нейман также полагал, что "многие сложные явления, такие как самовоспроизведение, рост и развитие, морфогенез, турбулентные процессы, которые трудно моделировать с помощью дифференциальных уравнений, удастся описать с помощью клеточных автоматов".' Однако только в самые последние годы в процессе осознания фундаментальной моделирующей роли клеточных автоматов произошел подлинный прорыв. Это осознание связано, в частности, с последними работами Р.Фейнмана, а также. С. Уолфрэма и ряда других авторов, "которые взглянули на физические теории с алгоритмической точки зрения" .
Целью диссертационной работы является обоснование и разработка композиционного метода формирования управляющего пространства процесса выполнения оператора конволюции в волновой клеточно-автоматной среде.
Достижение поставленной цели предусматривает решение следующих задач:
декомпозиции алгоритма конволюции на информационную и управляющую компоненты;
обоснования волновой интерпретации структурного задания хода параллельного вычисления оператора конволюции;
разработки концепции волновой обработки в рамках клеточно-автоматного подхода к организации распределенных вычислений;
определения динамически перестраиваемой древовидной
- З -структуры волнового процессора для вычисления конволюции;
анализа свойств матричной среды с волновым межклеточным взаимодействием;
планирования ресурса при организации вычисления ли нейной свертки на клеточной среде;
построения множества путей между клетками-листьями дерева, отражающего структурную организацию волнового процессора конволюции, и клетками-портами устройства ввода последовательностей.
Методы исследования базируются на общей теории автома тов и'вычислительных алгоритмов , теории алгоритмических систем и конечных множеств , . теории графов и сетей . используют результаты теории самоорганизации , взаимодействующих процессов , систолических и волновых структур , формальные модели поведения дискретных систем . а также накопленный к настоящему времени' опыт проектирования асинхронных цепей .
Научная новизна проведенных исследований:
-
Разработана концепция навигационного поля в пространстве по управлению для класса алгоритмов типа конволюции последовательностей.
-
Выявлены характеристические свойства процессов распространения возбуждения и структурообразования в рамках двумерной клеточной автоматной среды;
-
Установлены свойства самоподдерживающихся источников возбуждения, возникающие в модельной среде, а также определение механизма из образования.
4. .Синтезированы алгоритмы планирования ресурса при
организаций вычисления линейной свертки на клеточной среде.
5." Сформулированы методические рекомендации по решению задачи волнового взаимодействия компонентных автоматов двумерной клеточной среды.
Практическая ценность :разработанное описание асинхронного волнового процесса в двухмерной среде послужило основой для решения задач управления вычислением.свертки конечных последовательностей и выработки рекомендаций по проектированию устройств обработки сигналов (в рамках гос-
бюджетной НИР по линии Института моделирования и интеллектуализации сложных систем).
Апробация работы. Основные положения и научные результаты диссертационной работы докладывались и обсуждались :
на кауч.-техн. конф. профессорско-преподователь- " ского состава ЛЭТИ им. В.И.Ульянова (Ленина) 1992 г*:
городском семинаре "теория автоматов"секцйи вычислительной техники НТО РЭС им. А. С. Попова, Санкт-Петербург, 1992,1993 гг.
Публикации. По материалам диссертационной работы опубликовано 3 печатные работы, из них 2 - в соавторстве.
Структура и объем работы . Диссертация состоит из введения, четырех глав с выводами, заключения, списка литературы, включающего 83 наименования и 3 приложений.
Основная часть работы изложена на 129 страницах машино писного текста. Работа содержит 76 рисунков и 2 таблицы.
