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

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

ЛИТВИНСКАЯ Ольга Сергеевна

РАЗРАБОТКА МЕТОДА ВЫБОРА СРЕДСТВ РЕАЛИЗАЦИИ АЛГОРИТМОВ АНАЛИЗА ПОСЛЕДОВАТЕЛЬНЫХ ПОТОКОВ ДАННЫХ В СПЕЦИАЛИЗИРОВАННЫХ СИСТЕМАХ ОБРАБОТКИ ИНФОРМАЦИИ

Специальность 05.13.17- Теоретические основы информатики

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

Пенза 2005

Работа выполнена в Пензенской государственной технологической академии на кафедре "Вычислительные машины и системы".

Научный руководитель — доктор технических наук,

доцент Сальников И. И.

Официальные оппоненты: доктор технических наук,

доцент Михеев М. Ю.; кандидат технических наук, профессор Шашков Б. Д.

Ведущая организация - ФГУП "Радиозавод", г. Пенза.

в " 16 " часов на заседании диссертационного совета КР 212.337.48 при Пензенской государственной технологической академии по адресу: 440605, г. Пенза, пр. Байдукова / ул. Гагарина, 1а /11.

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

Автореферат разослан " " /-/ЯЛ^Я

2005 г.

Ученый секретарь диссертационного совета доктор технических наук, доцент

С. Б. Демин

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

Накопленный опыт по созданию и применению устройств цифровой обработки информации (ЦОИ) позволяет использовать для решения практических задач различные электронные устройства, например, универсальные ЭВМ с перестраиваемой программой или специализированные системы на основе программируемых логических интегральных схем (ПЛИС).

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

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

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

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

Для достижения поставленной цели в работе формулируются и ре-

шаются следующие задачи:

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

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

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

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

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

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

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

Научная новизна полученных результатов заключается в следующем:

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

2. Разработан критерий выбора средств реализации алгоритмов в специализированных системах, дана обобщенная характеристика параметров входного сигнала и алгоритма;

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

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

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

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

Материалы диссертации нашли практическую реализацию при выполнении хоздоговорной НИР "Растр", выполненной по заказу предприятия НИКИРЭТ (г. Заречный Пензенской области).

Результаты диссертационной работы внедрены в ФГУП Научно-исследовательский и конструкторский институт радиоэлектронной техники (НИКИРЭТ).

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

На защиту выносятся следующие положения:

1. Модель и способ получения количественной оценки сложности вычислительных операций;

2. Обобщенная характеристика вычислительного процесса, учитывающая параметры входного сигнала и алгоритма его обработки;

3. Коэффициент реального времени, позволяющий оценить быстродействие алгоритма по времени выполнения операций и времени ввода отсчетов входных данных;

4. Целевая функция на основе обобщенной характеристики и коэффициента реального времени;

5. Метод выбора средства реализации алгоритмов обработки информации в специализированных устройствах и системах;

6. Программное средство решения задачи выбора средства реализации заданных алгоритмов.

Апробация работы. Основные результаты работы докладывались и обсуждались на Всероссийской научно-технической конференции "Современные методы и средства обработки пространственно-временных сигналов", (г. Пенза, 27-28 мая 2003); V Всероссийской научно-тех-

нической конференции "Современные охранные технологии и средства обеспечения комплексной безопасности объектов" (г. Заречный Пензенской области, 18-20 мая, 2004); II Всероссийской научно-технической конференции "Современные методы и средства обработки пространственно-временных сигналов" (г. Пенза, 25-26 мая 2004); III Всероссийской научно-технической конференции "Современные методы и средства обработки пространственно-временных сигналов" (г. Пенза, 24-25 мая 2005); VII Международной конференции "Распознавание 2005" (г. Курск, 4-7 октября 2005).

Публикации. По теме диссертации опубликовано 13 научных работ, из них 6 статьей, 6 тезисов докладов, 1 отчет по НИР.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 61 наименования и двух приложений. Объем работы: 178 страниц текста, 57 рисунков, 14 таблиц, приложение 1 на 7 страницах, приложение 2 на 2 страницах.

СОДЕРЖАНКЕ РАБОТЫ

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

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

Из многообразия средств реализации а лгоритмов ЦОИ выделяются основные:

- программные, с использованием языков программирования высокого уровня и реализуемые на универсальных ЭВМ;

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

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

Программная реализация алгоритмов ЦОИ имеет целый ряд неоспоримых достоинств. Однако затраты на включение ЭВМ в состав различного рода специализированных систем ЦОИ не всегда оправданы.

Достоинством микропроцессорных средств реализации алгоритмов является программируемость функций, т.е. одно и то же АЛУ используется в разных операциях в соответствии с алгоритмом. При этом необходима фаза перестройки АЛУ, что требует определенных временных затрат. Указанное обстоятельство, а также фазы выполнения команды, носящие служебный характер, являются недостатком микропроцессорных средств реализации алгоритмов, влияющим на быстродействие систем ЦОИ.

При использовании программируемой логики программируется структура алгоритма, при этом время выполнения всех операций определяется задержками в отдельных логических блоках ПЛИС.

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

Рвп =Рвп {^2,...,Хт\Ъ,Ъ,...,ут}, (1)

которая будет зависеть от множества параметров [Х1,Х2, -,Хт}, таких как динамический диапазон, количество отсчетов входного сигнала, количество вычислительных операций, время преобразования, а также

от их характеристических свойств {у,, у2,..., ут }, представляющих собой максимальные значения анализируемого параметра. После нормирования каждого параметра из множества {X,, Х2,..., Хт } по множеству

{у,, у2,..., ут }, получены нормированные безразмерные параметры:

Кп>=%- (2)

Целевая функция принимает вид

Рвп =РвП { КП\>КПП->КПт }■ (3)

Множество нормированных параметров объединяется некоторой функцией, которая дает обобщенную характеристику:

ссп = /{*„,Кпт}. (4)

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

(С = {С{<С. КТ}, (5)

где Кдд} - коэффициент, учитывающий вид алгоритма.

График целевой функции р^ имеет вид, представленный на рисунке 1, где коэффициент вида алгоритма -1 соответствует управляющим, Кд= 2 - вычислительным, = 3 - преобразовательным алгоритмам.

Л"пл(М)=3

Зона 3, ШТ

Зона 2, МП

Зона 1,ПС

<

Рисунок 1 - Целевая функция

На рисунке 1 отмечены три зоны - области значений целевой функции, соответствующие средствам реализации: зона 1 - для программных средств реализации (ПС), зона 2 - для микропроцессорных (МП), зона 3 -для программируемой логики (ПЛ). Совокупность зон определяет множество средств реализации алгоритмов ={ПС,МП,ПЛ}. Зоны средств реализации определяются множеством из трех значений интер-

валов, соответственно А^1 £ { Л'Пс\ Амп-Дпл}> гДе Дст - интервал средств реализации моделей алгоритмов. В качестве критерия выбора средства реализации алгоритма используется соотношение между значением целевой функции вычислительного процесса р'^ конкретного алгоритма и целевой функции модели вычислительного процесса р^.

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

период был принят за единицу, т0 = 1, и выполнено сравнение с ним всех остальных времен выполнения различных типов операций Топ. В качестве величины для сравнения предложено использовать отношение Топ к Т0, которое названо коэффициентом сложности операции:

(6)

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

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

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

Рассмотрен используемый подход на примере определения коэффициента сложности операции обращения к памяти. Эта операция харак-

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

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

Рисунок 2 - Структурная схема устройства, реализующего операцию

обращения к памяти

Канал обработки данных включает в себя устройства разрешения ввода/вывода (УРВБ), хранения операндов и операционные блоки (ОБ), выполняющие различные вычислительные операции.

Канал управления - устройство управления (УУ), формирующее как управляющие сигналы, так и адрес ячейки памяти. ТГ - тактовый генератор, вырабатывает тактовую последовательность для синхронной работы всех устройств.

Работа схемы начинается с подачи на вход устройства включения разрешающего сигнала начала операции (НО), инициализирующего работу всей схемы. После этого на вход устройства хранения информационные переменные подаются под управлением разрешающего сигнала РЧ (разрешение чтения), который открывает УРВБ.

После выполнения операции результат записывается в устройство хранения операнда по разрешающему сигналу разрешения записи результата (РЗР). Для записи результата в память УУ формирует адрес ячейки памяти и переключает УРВБ на передачу данных в память. УУ формирует сигнал конца операции (КО), который закрывает устройство включения, тем самым заканчивая работу схемы.

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

Тоя

i тг к ~1 —1 п гл п 1 ,

УУ 1 ! 1 ! »

но ко

P4.P3P i ■

рч ! рч рч рч 3 рзр | рзр

Адрес 1 |

Данные -"-<Опер1> - <6пер2>-¡<Рез-т> -р.

ОБ j 1 1 • -►

: 2Гб,п 1 ' 1 1 Вы полнение *

операций

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

При всех способах реализации память является отдельным устройством. Наибольшим быстродействием обладает статическая память (SRAM),

минимальное время обращения Т0 п к которой достигает 8 н- 10 нс.

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

мер, 100 + 125 МГц, т.е. с периодом Гоп « 8 -И0 не. Время выполнения операций обращения к внешней памяти определяется суммой интервалов, кратных Т0 п:

Топ = Гно + 2ТРЧ + 2ТРЗР + Тко = 6Т0П, (7)

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

= ^ = (8)

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

Для группы операций пересылок данных:

- пересылки из регистра в регистр: Кс0 РР = 1;

- обращение к памяти: Ксо п = 48;

- обращение к стеку: Ксост =48;

-ввод-выводданных: Ксовв =1.

Для группы операций преобразования данных:

-операциисдвигов: Ксосдв = 3;

-логические: Ксодо -2;

- арифметические аддитивные с фиксированной запятой: К(с= 9;

- арифметические аддитивные с плавающей запятой: ^сола = 11 + "п > где "п _ разрядность порядка числа;

- арифметические мультипликативные последовательного перемножения с фиксированной и плавающей запятой соответственно: К(с%% =7 + лмн; у = 9+ пмн, где пШ1 - разрядность сомножителей;

- арифметические мультипликативные матричного перемножения с фиксированной и плавающей запятой соответственно: ^¿ому = 8; К(т) =10

Для группы операций передачи управления:

- условный и безусловный переход: Ксо уп = 8;

-множественный выбор: Ксомв = 6 + 2пмв, где пмв - число ветвей множественного выбора;

- циклы с фиксированным числом повторений: Кс0 ФЦ = 6 + лФЦ, гДе "фц - число шагов в цикле;

-вызовподпрограммы: /<"совпп =6; -возврат из подпрограммы: Л"совип =4.

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

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

- вид преобразования в виде параметра трансформации отсчетов лгт0;

- параметр сложности алгоритма Сдд;

- количество вычислительных операций Л^оп;

- время выполнения операций вычислительного процесса гво. После выполнения нормирования проанализированных параметров

е^^П^Л^С^Л^Гво} по множеству характеристических

свойств У, е {у0, Уп > Уто > Ус > Уоп - Урв } > получено множество безразмерных параметров:

X

Кп, ~ ~~' *п,е | КПй,Кпп,Кпто,Кпс,Кпоп, -/^п.рв|. (9)

У,

Все множество нормированных параметров в виде коэффициентов КП1 предложено связать некоторой функцией - обобщенной характеристикой а^ с использованием весовых коэффициентов:

< = (Ю)

п '=1

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

Коэффициент динамического диапазона входных данных определяется на основе разности между максимальным и минимальным значением входного сигнала £)5 = 5тах - 5тт. В цифровых системах В3

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

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

кпЛ ~

при п0

,вс - "о,вх

2-

'о,вх

-1

п

д,вс

при по вс<по ьх

(И)

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

45.

/-1

(12)

где ЯЛ._Л, - отношение сигнал-шум; 5т1П - минимальное значение входного сигнала.

Коэффициент трансформации отсчетов:

' 1 4

N \ то /

(13)

учитывает вид преобразования входных массивов данных в виде отношения количества отсчетов выходного сигнала результата преобразования Л^ и к количеству отсчетов входного сигнала N[ J:

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

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

^,вых(<,) > при этом Мг0 =1. Алгоритмы преобразования данных выполняют более сложные трансформации отсчетов над массивами данных. В работе рассмотрены следующие виды преобразований:

-моноэлементные, когда один входной сигнал порождает один выходной, то есть £ 1 5/т. При этом А^т0 = 1. Примером такого вида преобразования может служить алгоритм бинаризации входного изображения;

- биэлементные преобразования, когда для получения каждого выходного сигнала используются два входных. Например, алгоритм перемножения двух сигналов. Для таких алгоритмов Мто = 0,5;

- полиэлементные преобразования, когда один выходной сигнал

порождается совокупностью входных отсчетов, то есть т = / {5, ]}. Коэффициент трансформации входных данных будет равен А^то = М у

то есть ЫТ0 «1. Примерами такого преобразования могут быть алгоритмы вычисления среднего значения сигнала, алгоритмы вычисления пространственных характеристик изображений объектов - площади, периметра, координат центра тяжести, координат описанного прямоугольника, момента инерции и т.д.;

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

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

(15)

Сложность алгоритма определяется на основе коэффициентов сложности операций Ксо входящих в алгоритм:

••он

^ал = * Рох\,1

(16)

N.

где-

ОЯ,;

■■ роп^ - оценка вероятности появления/-операции.

Выражение (16) для сложности алгоритма характеризует модель вычислительного процесса, когда неизвестны основные сведения об алгоритме, например, разрядности порядков, число шагов в цикле, количество операций в алгоритме, поскольку эти параметры будут известны лишь для конкретного алгоритма. Поэтому в (13) указана вероятность появления I - операции.

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

К(А)=1ё

п (

_

N.

оп

(17)

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

Коэффициент числа операций в алгоритме оценивается выражением *п,оп=^оп- (18)

Коэффициент реального времени Кп рв, учитывающий заданное время выполнения операций Тт алгоритма по отношению ко времени ввода:

-^Чт.рв —

1

Тво + ^выв 1 + ^ВО

(19)

где Гвв - интервал поступления входных отсчетов, Гвв = Гвыв.

Время Гвв определяется скоростью входного последовательного потока данных. Время выполнения операций Гв0 может быть больше или меньше Гвв.

Если Тво < Тт, то результат формируется в процессе поступления отсчетов входного сигнала с периодом Гвыв = Гвв. Это соответствует режиму реального времени. Если Тпо > Твв, то требуется введение конвейера. При любом соотношении между Гво и Тт результат получается с задержкой:

-минимальной- Гзд тп = 2Тт при Гво < Гвв;

- максимальной - Гзд тах = + 1)ГВВ, и определяется числом ступеней конвейера - А^ск.

Время выполнения алгоритма вычислительного процесса Тм должно быть задано.

Из (19) следует, что чем меньше Тъ0, то есть чем меньше времени отводится на выполнение операций, тем больше Кп рв, и выполнение вычислительного процесса приближается к реальному времени.

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

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

Все нормированные коэффициенты, за исключением коэффициента реального времени, объединены в обобщенную характеристику

1=1

Для каждого вида алгоритма разработана математическая модель вычислительного процесса с целевой функцией р^'

р(М) =1_е~ап кЧл ки рв (21)

На рисунке 4 представлены зависимости целевой функции от обобщенной характеристики модели вычислительного процесса трех видов с различными коэффициентами реального времени. Максимальное значение коэффициента реального времени Кп рв = 1, минимальное принято за 0,05. Отмечены три зоны, соответствующие средствам реализации: зона 1 - программных средств реализации (ПС), зона 2 - микропроцессорных средств (МП) и зона 3 - средств программируемой логики (ПЛ). Совокупность зон определяет множество средств реализации моделей алгоритмов СРМ) = {ПС, МП, ПЛ}.

Рисунок 4 - Зависимости целевой функции от обобщенной характеристики

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

из трех значений интервалов, соответственно е {д^р, , Д^ },

где д™ - интервал средств реализации моделей алгоритмов. В качестве критерия выбора средства реализации заданного алгоритма используется соотношение между значением целевой функции (3^ конкрет-

ного алгоритма вычислительного процесса и целевой функции соответствующей модели вычислительного процесса р'^'. Попадание значения целевой функции конкретного алгоритма р(в*> в соответствующую зону целевой функции модели вычислительного процесса (рисунок 4) определяет средство реализации алгоритмов обработки данных.

Условие попадания в некоторую зону средств реализации представляется в виде

Р'вп'еД^. (22)

В общем виде решение о выборе средства реализации имеет вид Ср(А) = Ср(М) |ПС МП; ПЛ| при р(А) е д(М) > (23)

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

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

Исходными данными для программного средства являются: вид алгоритма, вытекающий из его назначения; алгоритм ЦОИ в виде перечня операций; характеристики входного сигнала; параметры вычислительного средства.

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

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

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

Кпд =1,041-*-7,026, Кпд =0,521 + 4,327, Кпт0 = 0 + 6, Кпс =1,059-5-2,243.

При определении весовых коэффициентов предложено использовать равномерное распределение. При необходимости можно изменить влияние того или иного нормированного коэффициента.

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

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

В приложении 2 приведены документы, подтверждающие внедрение результатов работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

2. Для модели вычислительного процесса обоснован выбор значимых характеристик сигналов и алгоритмов их обработки. Предложено

выражение для обобщенной характеристики а^'модели вычислительного процесса.

3. Обосновано применение коэффициента реального времени Кп рв для оценки быстродействия алгоритма по времени выполнения операций Гво и времени ввода Тт отсчетов входного сигнала.

4. Разработан метод выбора средства реализации исходного алгоритма, основанный на сравнении значения целевой функции ß^ для конкретного вычислительного процесса и значения целевой функции соответствующей модели алгоритма р(в*}.

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

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

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

1. Литвинская О. С. Распределенные системы видеонаблюдения / О.С.Литвинская, И. И. Сальников//Современные технологии безопасности,- М.: ЗАО «Альтаир», 2005. -№ 2. - С. 25-27.

2. Литвинская О. С. Многопараметрическая функция выбора средств реализации алгоритмов цифровой обработки информации / O.G. Литвинская, И.И. Сальников //Современные технологии безопасности,- М.: ЗАО «Альтаир», 2005. - № 3. - С. 28-32.

3. Литвинская О С. Многопараметрическая функция выбора средств реализации алгоритмов обработки информации // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: Материалы 7-й Меж-дунар. конф. "Распознавание 2005". - Курск, 2005. - С. 186-188.

4. Литвинская О. С. Выбор способа реализации систем искусственного интеллекта / О. С. Литвинская, И. И. Сальников /^Искусственный

интеллект в XXI веке: Сборник статей Всерос. науч.-техн. конф. - Пенза: ПДЗ, 2003.-С. 32-34.

5. Литвинская О. С. Реализация параллельных вычислений / О. С. Литвинская, Е.В. Грачева //Искусственный интеллект в XXI веке: Сборник статей Всерос. науч.-техн. конф. - Пенза: ПДЗ, 2003 - С. 59-60.

6. Литвинская О. С. Тенденции развития систем видеонаблюдения/ О.С. Литвинская, И.И. Сальников //Современные методы и средства обработки пространственно-временных сигналов: Сборник статей II Всерос. науч.- техн. конф. - Пенза: ПДЗ, 2004,- С. 129-131.

7. Литвинская О. С. Сравнительный анализ программных и аппаратных средств реализации операций передачи управления в алгоритмах // Информационные технологии и системы в науке, образовании, промышленности: Сборник статей Первой Всерос. науч.-техн. конф., посвященной 45-летию Пензенской государственной технологической академии. - Пенза: ПГТА, 2005,- С. 358-362.

8. Литвинская О. С. Распределенные системы видеонаблюдения / О.С. Литвинская, И. И. Сальников//Современные охранные технологии и средства обеспечения комплексной безопасности объектов: Материалы V Всерос. науч.-техн. конф. - Пенза: Инф.-изд. центр ПГУ,

2004,-С. 220-222.

9. Литвинская О.С. Информационная оценка пространственно-временных сигналов / О.С. Литвинская, И.И. Сальников//Современные методы и средства обработки пространственно-временных сигналов: Материалы III Всерос. науч.-техн. конф. - Пенза: ПДЗ, 2005-С. 3-6.

10. Литвинская О. С. Анализ сложности аппаратной реализации операций передачи управления в алгоритмах преобразования сигналов // Современные методы и средства обработки пространственно-временных сигналов: Материалы III Всерос. науч.-техн. конф. - Пенза: ПДЗ,

2005,-С. 41-44.

11. Литвинская О. С. Аппаратные средства реализации алгоритмов преобразования пространственно-временных сигналов // Современные методы и средства обработки пространственно-временных сигналов: Материалы Ш Всерос. науч.-техн. конф. - Пенза: ПДЗ, 2005. - С. 41-44.

12. Литвинская О.С. Распределенные системы видеонаблюдения / О.С. Литвинская, ИИ. Сальников, С.Н. Борисова// Современные методы и средства обработки пространственно-временных сигналов: Материалы III Всерос. науч.-техн. конф. - Пенза: ПДЗ, 2005 - С. 41—44.

Редактор Л.Ю. Горюнова Корректор А.Ю. Тощева Компьютерная верстка Д.Б. Фатеева, М.В. Недошивиной

Сдано в производство 19.11.05. Формат 60x84 '/16 Бумага типогр. №1. Печать трафаретная. Шрифт Times New Roman Cyr. Усл. печ. л. 1,34. Уч.-изд. л. 1,35. Заказ № 867. Тираж 100.

Пензенская государственная технологическая академия. 440605, Россия, г. Пенза, пр. Байдукова/ул. Гагарина, 1*/11. Лицензия: Серия ИД № 06495 от 26 декабря 2001 г. Internet: http://www.pgta.ru 23

»24345

РНБ Русский фонд

2006-4 26709

i

Введение.

1 Задача выбора средств реализации алгоритмов и анализ цифровых устройств обработки информации.

1.1 Область применения метода выбора средств реализации алгоритмов цифровой обработки информации.

1.2 Цифровые методы и средства реализации алгоритмов обработки сигналов.

1.2.1 Программные средства реализации алгоритмов цифровой обработки информации.

1.2.2 Микропроцессорные средства реализации алгоритмов цифровой обработки информации.

1.2.3 Средства реализации алгоритмов цифровой обработки информации на программируемой логике.

1.3 Виды алгоритмов цифровой обработки информации.

1.3.1 Управляющие алгоритмы.

1.3.2 Вычислительные алгоритмы.

1.3.3 Алгоритмы преобразования данных.

1.3.4 Вычислительный процесс как общее средство реализации

• алгоритма.

1.4 Формат представления потока данных.

1.5 Формирование последовательного потока цифровых данных.

1.5.1 Дискретизация аналогового сигнала по времени.

1.5.2 Квантование входного сигнала по уровню.

1.6 Оценочное время выполнения алгоритма.

1.7 Формулировка подхода к методу выбора и обоснования средства реализации заданного алгоритма обработки данных.

Выводы по разделу

2 Разработка количественных оценок сложности вычислительных операций.

2.1 Определение коэффициента сложности вычислительных операций

2.2 Коэффициент сложности модели операций пересылок данных.

2.2.1 Операции пересылок из регистра в регистр.

2.2.2 Операции обращения к памяти.

2.2.3 Операции обращения к стеку.

2.2.4 Операции ввода-вывода.

2.3 Коэффициент сложности модели операций преобразования данных.

2.3.1 Операции сдвига.

2.3.2 Логические операции.

2.3.3 Арифметические аддитивные операции.

2.3.4 Арифметические мультипликативные операции.

2.4 Коэффициент сложности модели операций передачи управления.

2.4.1 Обобщенная схема реализации операции передачи управления.

2.4.2 Условный и безусловный переход.

2.4.3 Операция множественного выбора.

2.4.4 Операции циклических повторений.

2.4.5 Операции вызова-возврата из подпрограмм.

Выводы по разделу 2.

Модели алгоритмов и метод выбора средства реализации

3.1 Обзор моделей вычислительных процессов.

3.2 Обобщенный параметр модели алгоритмов.

3.3 Частные нормированные параметры входного сигнала.

3.3.1 Динамический диапазон входного сигнала.

3.3.2 Скорость последовательного потока данных.

3.3.3 Преобразование входных данных.

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

3.5 Частные нормированные параметры модели алгоритмов.

3.5.1 Сложность алгоритма.

3.5.2 Число операций алгоритма.

3.5.3 Коэффициент реального времени.

3.6 Метод выбора средств реализации алгоритмов на основе целевой функции модели алгоритма.

Выводы по разделу

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

4.1 Назначение программного обеспечения.

4.2 Структура программного обеспечения.

4.3 Ввод данных.

4.4 Обработка данных.

4.5 Анализ результата.

4.6 Исследование зависимостей нормированных параметров от параметров входного сигнала и алгоритма.

4.6.1 Нормированный коэффициент динамического диапазона.

4.6.2 Нормированный коэффициент последовательного потока данных.

4.6.3 Нормированный коэффициент трансформации отсчетов.

4.6.4 Нормированный коэффициент сложности алгоритма.

4.7 Весовые коэффициенты для нормированных параметров.

4.8 Примеры использования программного обеспечения.

Выводы по разделу 4.

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

Накопленный опыт по созданию и применению устройств цифровой обработки информации (ЦОИ) позволяет использовать для решения практических задач различные электронные устройства, например, универсальные ЭВМ с перестраиваемой программой или специализированные системы на основе программируемых логических интегральных схем (ПЛИС).

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

Обоснованный выбор средств реализации алгоритмов обработки информации имеет существенное значение для устройств и систем, работающих с последовательными сигналами, - телекоммуникационных систем, систем сбора и обработки данных, технического зрения, охраны, отличающихся наличием последовательных каналов связи или последовательных каналов ввода данных. Специализированные системы ЦОИ при эксплуатации работают по фиксированным алгоритмам в отличие от универсальных ЭВМ. Применение специализированных систем ЦОИ обусловлено экономической целесообразностью, например, в телевизионных датчиках с функциями накопления, обнаружения и классификации изображений в системах технического зрения; в датчиках обнаружения и классификации целей в системах целеуказания или в технических системах охраны.

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

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

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

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

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

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

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

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

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

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

Научная новизна полученных результатов заключается в следующем:

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

2. Разработан критерий выбора средств реализации алгоритмов в специализированных системах, обобщенная характеристика параметров входного сигнала и алгоритма.

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

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

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

Реализация и внедрение результатов. Исследования проводились на кафедре «Вычислительные машины и системы» Пензенской государственной технологической академии.

Материалы диссертации нашли практическую реализацию при выполнении хоздоговорной НИР "Растр", выполненной по заказу ФГУП Научно-исследовательский и конструкторский институт радиоэлектронной техники (НИКИРЭТ) (г. Заречный Пензенской области).

Результаты диссертационной работы внедрены в НИКИРЭТ. Полученные в диссертационной работе результаты используются также в учебном процессе кафедры «Вычислительные машины и системы» Пензенской государственной технологической академии при обучении студентов по специальности 230101 "Вычислительные машины, комплексы, системы и сети" в дисциплине «Математическая логика и теория алгоритмов».

На защиту выносятся следующие положения:

1. Модель и способ получения количественной оценки сложности вычислительных операций.

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

3. Коэффициент реального времени, позволяющий оценить быстродействие алгоритма по времени выполнения операций и времени ввода отсчетов входных данных.

4. Целевая функция на основе обобщенной характеристики и коэффициента реального времени.

5. Метод выбора средства реализации алгоритмов обработки информации в специализированных устройствах и системах.

6. Программное средство решения задачи выбора средства реализации заданных алгоритмов.

Апробация работы. Основные результаты работы докладывались и обсуждались на: Всероссийской научно-технической конференции «Современные методы и средства обработки пространственно-временных сигналов», (г.Пенза, 27-28 мая 2003 ); V Всероссийской научно-технической конференции «Современные охранные технологии и средства обеспечения комплексной безопасности объектов» (г. Заречный Пензенской области, 18—20 мая, 2004 ); II Всероссийской научно-технической конференции «Современные методы и средства обработки пространственно-временных сигналов», (г. Пенза, 25-26 мая 2004 ); III Всероссийской научно-технической конференции «Современные методы и средства обработки пространственно-временных сигналов», (г. Пенза, 24-25 мая 2005 ); VII Международной конференции «Распознавание 2005» (г.Курск, 4-7 октября 2005 ).

Публикации. По теме диссертации опубликовано 13 научных работ, из них: 6 статьей, 6 тезисов докладов, 1 отчет rio НИР.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 61 наименования и двух приложений. Объем работы: 178 страниц текста, 57 рисунков, 14 таблиц, приложение А на 7страницах, приложение В на 2 страницах.

Выводы по разделу 4

1. Разработана структура программного обеспечения и выполнено проектирование в среде СУБД Microsoft Access 2003, использующее метод выбора средства реализации алгоритма, обоснованный в данной работе.

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

3. Получены граничные значения нормированных коэффициентов с помощью программного средства.

4. Разработана методика определения весовых коэффициентов, входящих в обобщенную характеристику и позволяющая учесть равномерное влияние всех нормированных коэффициентов на целевую функцию. Значение весовых коэффициентов представлено в таблице 4.7.

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

Заключение

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

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

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

2. Для модели вычислительного процесса обосновано использование значимых характеристик сигналов и алгоритмов их обработки. Предложено выражение для обобщенной характеристики а^ модели вычислительного процесса.

3. Обосновано применение коэффициента реального времени /*Гп?рВ для оценки быстродействия алгоритма по времени выполнения операций Тт и времени ввода Твв отсчетов входного сигнала.

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

А) модели алгоритма р^п .

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

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

1. Смолов В. Б. Функциональные преобразователи информации. -Л.: Энергоиздат, 1981.-272 с.

2. Анисимов Б. В. Аналоговые вычислительные машины / Б. В. Анисгшов, В. Н. Голубкин М.: Высшая школа, 1971. - 356 с.

3. Сальников И. И. Растровые пространственно — временные сигналы в системах технического зрения: Учеб. пособие. Пенза: ЦНТИ, 1999 — 256 с.

4. Информатика: Учебник для вузов / Под ред. Н. В. Макаровой. -М.: Финансы и статистика, 1997. — 528 с.

5. Информатика. Базовый курс. 2-е издание / Под ред. С. В. Симоновича. — СПб.: Питер, 2003. 640 с.

6. Цилькер Б. Я. Организация ЭВМ и систем / Б. Я. Цилькер, С. А. Орлов. -СПб.: Питер, 2004. 668 с.

7. Карпов Ю. Г. Теория автоматов. СПб.: Питер, 2003. - 208 с.

8. Сальников И. И. Микропроцессорные контроллеры. — Пенза: ПГУ, 2005.— 164 с.

9. Савельев А. Я. Основы информатики: Учеб. для вузов. М.:МГТУ им. Н.Э.Баумана, 2001. - 278 с.

10. Сальников И. И. Проектирование цифровых устройств обработки информации на основе ПЛИС: Учеб. пособие. Пенза: ПГУ, 2002.126 с.

11. Лысиков Б. Г. Арифметические и логические основы ЭЦВМ.

12. Минск: Вышейшая школа, 1974. 262 с.

13. Немнюгин С. A Turbo Pascal 7.0:практикум. СПб.: Питер, 2001. - 256 с.

14. Котельников В. А. Теория потенциальной помехоустойчивости.— М.: Госэнергоиздат, 1956. 225 с.

15. Баскаков С. И. Радиотехнические цепи и сигналы: Учеб. Для вузов по специальности «Радиотехника». — М.: Высш. шк., 2000. 357 с.

16. Алфёрова 3. В. Теория алгоритмов. М.: Статистика, 1973. - 368 с.

17. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир, 1989.-233 с.

18. Соловьев Г. Н. Арифметические устройства ЭВМ. М.: Энергия, 1978. — 176 с.18.19,20,21.22,23,24,25,26