Введение к работе
Актуальность темы. Широкие возможности вычислительной техники нашли эффективное примякянке н практике обработки больших массивов информации в реальном масштабе времени, в связи с этим возникают потребности в разработке вычислительных систем оптимально отвечающих требованиям цифровой обработки информации и сигналов.Одной из ключевых проблем, стоящих при решении задач цифровой обработки сигналов (ЦОС), в том числе цифровой фильтрации (Ш). является создание высокопроизводительных проблемно -ориентированных вычислительных систем реального времени. Повышение производительности может быть достигнуто в основном за счет совершенствования элементной базы и схемотехнических решений, принимаемых при построении вычислительных систем, или за счет создания новых архитектур вычислительных систем и способов организации вычислительного процесса.В настоящее время наиболее перспективным направлением повышения производительности вычислительных систем реального времени, ориентированных на определенный класс решаемых задач, является архитектурный. Исследование и разработка новых архитектурных решений ведутся уже более тридцати лет. Еще в 60-е годы Э.В. Евреиновым была предложена концепция однородных вычислительных систем, структур и сред, которая получила наибольшее развитие в работах научных коллективов под руководством И.В. Прангишвили, К.Г.Самофалова, Г.М.Луцкого, В.Г. Хорошевского, Ю.Г. Косарева и других. В рамках архитектурного направления важным классом однородных вычислительных структур являются систолические, представляющие собой планарную сеть ячеек, основными свойствами которой являются : - однородность ячеек. Любая ячейка выполняет одну и ту же элементарную операцию, например, умножение/ сложение, при этом допускается, что входные и выходные ячейки, называемые граничными или периферийными, могут выполнять другие операции; -регулярность и локальность связей между ячейками, причем каждая ячейка имеет связи только со своими непосредственными соседями:
-параллельность и многоконвейерность выполнения вычислений; -синхронность. За каждый цикл своей работы ячейка осуществляет прием данных, выполнение операции, выдачу результатов и данных, необходимых для дальнейшего выполнения вычислений, при зтом дан-
Є5-
іше ритмично поступают в ячейку, обрабатываются и передаются в соседнюю.
Поскольку систолические структуры состоят из однородных ячеек, то достаточно разработать и выполнить тестирование одного или несколько типов ячеек, что значительно уменьшит время и стоимость проектирования. Таким образом, достоинствами систолических структур является высокая скорость выполнения вычислений и простота проектирования. Однако, по море повышения требований, предъявляемых к систолическим структурам, сложности реализуемых задач архитектурные решения, принимаемые в ходе ручного проектирования, перестали удовлетворять по срокам и качеству проектирования.В связи с тем.что на раннем этапе проектирования отсутствуют формализованные методы синтеза,способные из всего допустимого множества архитектурных решений выбирать оптимальные по заданным критериям, возрастает вероятность возникновения ошибок, что неизбежно сникает качество проектирования. Поэтому особенно актуальным становится задача создания формализованных методов проектирования систолических структур, реализующих определенный класс вычислительных задач, и средств автоматизации, способствующих ускорению процесса принятия проектных решений ыа системотехническом уровне.
До выполнения данной работы состояние проблемы проектирования устройств цифровой фильтрации было таково, что, несмотря на острую практическую потребность в данных устройствах, не были достаточно разработаны алгоритмы и инженерные методики синтеза эквивалентных структур (алгоритмов) канонических рекурсивных цифровых фильтров N-ro порядка, систолических структур, реализующих фильтры по соответствующим им графам потоков сигналов (ГПС) согласно заданным критериям оптимальности, отсутствовали исследования систолических структур цифровых фильтров по точности выполнения вычислений.
11@лью_диссертационной работы является разработка метода проектирования систолических структур для устройств 'цифровой фильтрации, работающих в реальном масштабе времени.
Для достижения поставленной цели в диссертации решаются следующие основные задачи:
-исследование существующих методов проектирования систолических структур для задач цифровой обработки сигналов; -разработка формализованной процедуры и библиотеки алгоритмов оп-
редэления эквивалентных графов потоков сигналов канонических биквадратных звеньев рекурсивных цифровых фальтров с целью построения кз них эквивалентных графов потоков р.«тт?плов цифрспых фЛЛЬї-ров N - го порядка;
-разработка формализованной процедуры и библиотеки алгоритмов определения систолических структур цифровых фильтров по соответствующим им графам потоков сигналов;
-разработка машинно - ориентированной ишганерной методики алгоритмического синтеза цифровых фильтров, позволящей определить множество эквивалентных структур (алгоритмов) канонических рекурсивных цифровых фильтров N - го порядка, про дставляивдх собой каскадное соединение однотипных канонических биквадратных звеньев рекурсивных цифровых фильтров,и найти оптимальные из них по допустимой величине дисперсии шума;
-разработка машиннно - ориентированной инженерной методики структурного синтеза цифровых фильтров,позволящвй определить мнокест-во систолических структур цифровых фильтров на системотехническом уровне и найти оптимальные из них по таким параметрам, как время и точность выполнения вычислений, размер структуры при ограничениях величины конвейерного такта приема / выдачи элементов входного / еыходного потоков данных;
-разработка структуры системы автоматизированного проектирования систолических структур для устройств цифровой фильтрации, целесообразной для практического применения.
Методы исследований. При решении указанных задач в диссертационной работе использованы следующие метода исследования: теория графов, теория множеств, комбинаторный анализ, теория вычислительных систем и специализированных процессоров. Научная, новизна. В диссертации дано новое решение задачи синтеза систолических структур для устройств цифровой фильтрации. Основные научные результаты заключаются в следующем. 1. Разработан машинно - ориентированный метод синтеза систолических структур для устройств цифровой фильтрации, СОСТОЯЩИЙ из алгоритмического синтеза и структурного. Алгоритмический синтез позволяет из множества структур (алгоритмов) цифрового фильтра N - го порядка, эквивалентных в смысле эквивалентности соотвот-ствупдих им передаточных функций, найти малотаумящие структуры по допустимой величине дисперсии шума. Структурный синтез позволяет при отображении найденных малошумящих эквивалентных структур (ал-
горитшв) цифрового (фильтра N - го порядка определить соответствуйте им систолические структуры по точности выполнения вычислений при ограничениях величины конвейерного такта приема / выдачи элементов входного / выходного потоков данных, о также найти оптимальные из них по заданным критериям оптимальности. ?.. Разработана формализованная процедура и библиотека алгоритмов определения эквивалентных канонических структур биквадратных звеньев рокурсивных цифровых фильтров с целью построения из них эквивалентных цифровых фильтров N - го порядка, базирующиеся на различных преобразованиях, графов потоков сигналов, основными из которых являются перенос вершны ветвления в последовательности вершин графа по направлению прохождения сигнала либо против. 3. Разработана формализованная процедура и библиотека алгоритмов определения систолических структур цифровых фильтров на системотехническом уровне по соответствующим им графам потоков сигналов, позволяющие преобразовать графы потоков сигналов цифровых фильтров N - го порядка в графы, вершинам которого соответствуют операции умноаенио/слаяание, выполнить раскраску вершин преобразованных, графов и разметить их связи,определить конвейерный такт приема/выдачи элементов входного/выходного потоков данных, найти полное время формирования выходного потока данных,а также выполнить свертку систолических структур,е соответствии с которой могут быть найдены структуры с меньшим размером. Практическая ценность работы.
-
Разработана машинно - ориентированная инженерная методика алгоритмического синтеза цифровых фильтров, которая обеспечивает получение мокества эквивалентных структур (алгоритмов) заданного цифрового фильтра N - го порядка, представляющего собой каскадное соединение однотипных канонических биквадраных звеньев рекурсивных цифровых фильтров; проверку правильности найденных структур и нахождение оптимальных из них по допустимому значению дисперсии шума.
-
Разработана машинно - ориентированная инженерная методика структурного синтеза цифровых фильтров, обеспечивающая при отображении множества мзлошумящих структур (алгоритмов) цифрового фильтра N - го порядка, эквивалентных заданной, получение множества систолических структур, реализуюздо: заданный цифровой фильтр, по точности выполнения вычислений и нахождение оптимальных из них по времении выполнения вычислений и размеру структуры
при ограничениях величины конвейерного такта приема / Еыдачи элементов входного / выходного потоков данных.
3. Предложена структура системы автоматизированного проектирования скстолігїєсюос структур цифрових фильтров, целесообразная для практического применения, которая обеспечивает выполнение алгоритмического и структурного синтеза цифровых фильтров. Реализация и внедрение. Результаты, полученные автором при выполнении диссертационной работы, были использованы в ОКР 224 / 91, проводимой в специальном конструкторском технологическом бюро с опытном производством Белорусского государственного университета информатики и радиоэлектроники (СКТБ с 011 БГУ ИР), НИР "Исследование путей создания ультра - БИС с программно - перестраиваемой структурой " (шифр "Дума"), выполненной в конструкторском технологическом бюро "Еелмикросистемы" научно - производственного объединения "Интеграл" (КТБ "Бэлмикросистемы" НПО "Интеграл"), о чем подтверждают акта Енедрения и использования. Апробация работа. Основные положения диссертации сбсуздоны на VI - й Всесоюзной школе - семинаре по распараллеливанию обработки информации (Льеов, 1987), V - й Всесоюзной научно - технической конференции по однородным вычислительным системам, структурам и средам (Москва, 1991), конференции по телекоммуникационным и вычислительным системам связи (Москва, 1993).
Публикации. Основные результати диссертационной работы опубликованы в восьми печатных работах.
Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения и содержит 150 страниц основного текста, 95 рисунков и 12 таблиц, перечень использованной научно - техкичес-кой литературы из 142 наименований,„пяти приложений. Основные положения, выносимые на защиту: