Учебное пособие Москва, 2006 ббк 32. 973 Т… icon

Учебное пособие Москва, 2006 ббк 32. 973 Т…



Смотрите также:
Учебное пособие Москва 200 8 удк 004. 738 Ббк 32. 973. 202...
Учебное пособие Москва 2008 удк 004. 738 Ббк 32. 973. 202...
Учебное пособие Находка 2003 удк681. 3+340+339. 3 + 338 ббк 32. 973+67+67. 404+65. 050 В 50...
Сумского государственного университета как учебное пособие для студентов высших учебных...
Учебное пособие 28365942 Москва 2008 ббк 66. 0 П 50...
Учебное пособие москва 2003 ббк 86. 2 Удк 2...
Учебное пособие Москва 2002 ббк 63. 3 /2/ я 73 Рецензент: Иванова А. А...
Учебное пособие Москва 2005 ббк 60. 55 Рецензенты : д ф. н., проф...
Учебное пособие москва 2012 удк 32. 001 Ббк 66. 0...
Учебное пособие Москва 2006 нии гигиены и охраны здоровья детей и подростков гу нцзд рамн ниии...
Учебное пособие Электронный вариант (без рисунков, картин и портретов) москва  2005 ббк 87...
Учебное пособие Издание 2-е, переработанное и дополненное москва юристъ 2 0 0 0 удк 341...



страницы: 1   2   3   4   5   6   7   8   9
вернуться в начало
скачать

y = A x,


где каждый элемент Amn матрицы A в случае ДПФ имеет вид


Amn = exp ( - j 2 (m-1) (n-1) / N), 1 m N, 1 n N.


Вопросы и упражнения по разделу 1.3.

А. Чем отличается дискретизация от квантования? Каковы функции АЦП?

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

В. Какой оператор z-преобразования отображает задержку сигнала?

Г. Приведите матричную форму дискретного преобразования Фурье.


    1. ^ Быстрое преобразование Фурье

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

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

Один из наиболее распространенных способов реализации БПФ основан на идее прореживания во времени. Этот алгоритм наиболее эффективно работает в случае, когда N=2n для некоторого целого n. Если число N четное, анализируемый набор отсчетов сигнала разделяется на две части: первая часть содержит только отсчеты с четными номерами, а вторая - с нечетными. Каждая часть при этом содержит N/2 отсчетов, т.е. происходит декомпозиция исходного дискретного сигнала на два сигнала, представленных укороченной вдвое последовательностью отсчетов. Если число N/2 также четное, к каждой из полученных частей снова применяется та же операция. И так далее до тех пор, пока сигнал не будет представлен нечетным количеством отсчетов или в каждой из частей не будет получен только один отсчет. Таким образом, исходный дискретный сигнал, представленный N отсчетами, преобразуется в N сигналов, каждый из которых представлен одним отсчетом. Процедура декомпозиции исходного сигнала для N=16 иллюстрируется на рис. 1-1.





Рис.1-1. Декомпозиция дискретного сигнала при вычислении БПФ.


На следующем шаге вычисления БПФ для каждой пары сигналов вычисляется спектр. На заключительном шаге вычисления БПФ спектры полученных сигналов объединяются в общий спектр исходного N-отсчетного сигнала.

Для выполнения декомпозиции исходного N-отсчетного сигнала требуется выполнить Log2N шагов декомпозиции. Каждый из этих шагов состоит в переупорядочении отсчетов исходного сигнала. При этом удобно использовать сортировку с инверсией разрядов двоичного представления номеров отсчета [2].

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






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


При объединении спектров операции производятся в порядке, обратном представленному на рис. 1-1. Схема вычисления спектра для каждой пары одноотсчетных дискретных сигналов показана на рис. 1-2. Один из сигналов умножается на соответствующий экспоненциальный коэффициент W матрицы ДПФ, что соответствует получению новой гармоники спектра с удвоенной частотой. Полученная гармоника в одном случае складывается, а в другом вычитается из соответствующего парного сигнала. В результате последовательного применения таких операций формируется N-отсчетная спектральная последовательность исходного сигнала. Показанная на рис. 1-2 схема формирования спектра называется "бабочкой" (butterfly) и обычно считается базовой операцией для оценки эффективности БПФ.

Вычислительная сложность рассмотренного алгоритма составляет Nlog2N пар операций "умножение-сложение". При N = 1024 это позволяет ускорить БПФ более чем в 100 раз. Существуют и другие модификации [1], приводящие к еще более эффективной реализации БПФ.


Вопросы и упражнения по разделу 1.4.

А. Приведите схему декомпозиции дискретного 8-отсчетного сигнала по методу БПФ.

Б. Как оценивается вычислительная сложность БПФ?

В. Приведите и поясните схему базовой операции БПФ.

Г. Оцените коэффициент ускорения преобразования Фурье при N=512.


    1. ^ Цифровая фильтрация сигналов


Под фильтром обычно понимают систему, которая одни частоты пропускает, а другие задерживает. Однако в технике цифровой обработки сигналов понятие фильтра трактуется более широко. Дискретным фильтром называют произвольную систему обработки дискретного сигнала, которая обладает свойствами линейности и стационарности [1]. Существуют также фильтры с переменными параметрами, например, адаптивные фильтры [3], меняющие свои параметры в зависимости от статистических свойств входного сигнала.

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


y(k) =(k-i).


Такие фильтры называются нерекурсивными или трансверсальными. Количество m отсчетов называется порядком фильтра. Структурная схема нерекурсивного фильтра показана на рис. 1-3. Импульсная характеристика нерекурсивного фильтра определяется его коэффициентами h(k) = bk. Так как в реальном устройстве количество линий задержки ограничено, а следовательно, и количество коэффициентов конечно, нерекурсивные фильтры называют также фильтрами с конечной импульсной характеристикой (КИХ -фильтры или FIR-фильтры).

Фильтр, в котором используются также и выходные отсчеты, называется рекурсивным (рис. 1-4). Уравнение рекурсивного фильтра имеет вид

y(k) = (k-i ) -(k-i ).


Наличие в схеме рекурсивного фильтра обратных связей позволяет получить бесконечную импульсную характеристику, поэтому такие фильтры называют БИХ-фильтрами или IIR-фильтрами. Такие фильтры при некоторых условиях могут быть неустойчивыми.

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

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





Рис. 1-3. Нерекурсивный фильтр.


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

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

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






Рис. 1-4. Рекурсивный фильтр.


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

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

  • Вычисляются ДПФ дополненных нулями последовательностей.

  • Вычисленные ДПФ поэлементно перемножаются

  • Вычисляется обратное ДПФ от результата перемножения.

Для повышения эффективности фильтрация осуществляется в частотной области с использованием БПФ.

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

  • шум квантования, возникающий при аналого-цифровом преобразовании;

  • искажения характеристик, происходящие при квантовании коэффициентов цифровых фильтров;

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

  • округление промежуточных результатов вычислений.

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


Вопросы и упражнения по разделу 1.5.

А. Чем отличается рекурсивный фильтр от нерекурсивного? Опишите уравнения для обоих фильтров.

Б. В чем состоит задача проектирования цифровых фильтров? Какие подходы при этом используются?

В. Как выглядит алгоритм фильтрации с применением ДПФ?

Г. Какие технические ограничения влияют на характеристики проектируемых фильтров?


    1. ^ Цифровая обработка изображений


Существует множество задач, в которых результат обработки сигнальной информации, поступающей из внешней среды, должен быть представлен в виде двухмерного или трехмерного изображения. В частности, к такому классу задач относятся задачи визуализации биологических объектов, например, с целью медицинской диагностики [4,5]. Сама процедура получения двухмерного или трехмерного изображения сопряжена с решением сложных технических проблем, связанных с реализацией процедур сканирования исследуемого объекта. Для реализации таких процедур во многих случаях используются фазированные антенные решетки [6]. Результат сканирования должен быть представлен на экране цифрового дисплея в виде двухмерного массива пикселей.

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

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

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

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

Существенными особенностями обработки изображений является двухмерное (или трехмерное) пространственное представление анализируемых сигналов, требующее применения соответствующих модификаций алгоритмов сигнального преобразования. Например, для обработки изображения размером 800 х 600 пикселей в частотной области необходимо сначала дополнить его нулями, получив изображение 1024 х 1024 пикселя. Далее вычисляется БПФ для каждой строки, а затем для каждого столбца. После умножения полученного спектра 1024 х 1024 на требуемый частотный отклик выполняется двухмерное обратное БПФ - сначала по каждой строке, затем по каждому столбцу.

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


Вопросы и упражнения по разделу 1.6.

А. Как представляется результат сканирования биологического объекта?

Б. Какие факторы влияют на информативность изображения биологического объекта?

В. Как влияют особенности двухмерных и трехмерных изображений на процедуру обработки сигналов?

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


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


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

На протяжении более чем полувековой истории развития цифровой вычислительной техники основным мотивом, стимулирующим совершенствование архитектуры вычислительных систем, было стремление повысить их производительность. Начиная от машины ENIAC, содержавшей 19 тыс. ламп, производительность компьютеров росла на порядок каждые пять лет [8,9]. С изобретением транзисторов и интегральных схем постоянный рост технологических возможностей позволял регулярно увеличивать плотность компонентов, реализуемых на одном кристалле и тактовую частоту процессора.

С точки зрения архитектуры вычислительной системы основным предметом вычислительной науки был поиск оптимального соотношения между тремя основными узлами (или комплексами узлов): обрабатывающим устройством (АЛУ или процессором), памятью и интерфейсными узлами, обеспечивающими взаимодействие с внешней средой. С точки зрения развития концепции вычислений главным аспектом было соотношение между потоком команд и потоком данных. С точки зрения пользовательской один из основных моментов состоял в поиске оптимального соотношения между функциями, которые должны быть жестко реализованы в аппаратуре и функциями, которые можно программировать. Наконец, среди различных архитектурных направлений, согласно принципу естественного отбора выживают только такие архитектурно-технические решения, которые обеспечивают совместимость с предшествующими версиями.

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

Один из ключевых моментов построения архитектуры связан с набором процессорных команд и реализацией взаимодействия процессора с памятью. В плане взаимодействия процессора и памяти выделяются два подхода к построению архитектуры. Архитектура фон Неймана предполагает использование общей памяти - как для команд, так и для данных, используя тот факт, что и данные, и команды должны кодироваться двоичным словом определенной длины. Данный подход, предложенный еще на заре зарождения и становления цифровой вычислительной техники, по-прежнему широко применяется при разработке архитектуры процессора, так как он позволяет унифицировать интерфейс обращения к памяти и экономить оборудование. Однако, для некоторых классов задач (включая рассматриваемые здесь системы сигнальной обработки) целесообразно строить раздельное обращение к памяти команд и к памяти данных. Фирма ADI [10] называет такую архитектуру Гарвардской, ссылаясь на тот факт, что ее предложил Айкен, работавший примерно в то же время в Гарвардском университете.

Некоторые исследователи рассматривают дилемму взаимоотношения процессора и памяти в еще более широком концептуальном контексте - в виде соотношения между потоком команд и потоком данных. Так появилась концепция вычислений, управляемых потоком данных (Dataflow architecture [11]) в противовес традиционной архитектуре, ориентированной на поток команд. Такая организация вычислений имеет смысл только в том случае, когда поток данных достаточно хорошо определен. В большинстве современных универсальных вычислительных систем процесс по-прежнему управляется потоком команд, определяемым при программировании. В этом смысле задачи и функции сигнальной обработки также имеют свою специфику. Вычислительный процесс обработки сигналов, как было показано в предыдущей главе, в значительной степени определяется именно потоком данных - дискретной последовательностью отсчетов значений сигнала, поступающих в определенные промежутки времени. При этом поток команд должен быть синхронизирован с потоком данных, чтобы текущий отсчет был обработан или, по крайней мере, сохранен до поступления следующего отсчета.

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

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

Более высокий уровень параллелизма связан с организацией параллельных вычислений на уровне команд. Здесь следует выделить архитектурные решения типа SIMD (Single Instruction - Multiple Data), которые позволяют с помощью одной команды обрабатывать одновременно и независимо несколько потоков данных. Данный подход также хорошо согласуется со спецификой систем сигнальной обработки, в особенности, когда необходима многоканальная обработка однотипных сигналов по единому алгоритму.

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

Тем не менее, наборы команд в различных архитектурах различаются весьма существенно. Одно из направлений, разработанных в 80-е годы прошлого века, было связано с разработкой RISC-процессоров (Reduced Instruction Set Computer) - процессоров с сокращенным набором команд. Разработчики стремились максимально упростить инструкции и операции загрузки команд и данных, а также впервые ввели понятие регистрового файла, позволяющего по возможности сохранять результаты вычисления на кристалле для последующей обработки.

Что касается упрощения инструкций, в последние годы с продолжающимся ростом степени интеграции наблюдается скорее обратная тенденция: применяются инструкции с усложненным набором команд (CISC - Complex Instruction Set Computer) или инструкции с очень длинным командным словом (VLIW - Very Long Instruction Word). Такие инструкции позволяют наряду с традиционными командами реализовать команды SIMD-обработки.

Что касается концепции регистровых файлов, она получила дальнейшее развитие в разработках мультитредовых архитектур [12]. Сама концепция регистрового файла возникла в силу технологической особенностей реализации взаимодействия между процессорами и памятью. Современное состояние микроэлектроники характеризуется растущим разрывом между скоростью обработки данных в микропроцессорах и быстродействием внекристальной оперативной памяти [9]. Обычно время выполнения однотактной команды микропроцессора более чем на порядок меньше времени доступа к памяти вне кристалла. Поэтому часто прибегают к построению многоуровневой иерархической памяти с использованием внутрикристальной кэш-памяти или применению мультитредовой многопроцессорной архитектуры, в которой задержка доступа в память в одном процессе «скрывается» за временем выполнения других процессов [9].

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

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

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

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

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

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

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

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

Одно из направлений развития и построения многопроцессорных систем было построено на основе углубленных теоретических исследований взаимодействия последовательных процессов [13]. В результате был разработан специальный язык параллельного программирования Occam [14] и предложена архитектура многопроцессорной системы, названная транспьютерной архитектурой [15], в которой связи между соседними процессорами строились на основе одноразрядных линков. В последующих версиях одноразрядные линки заменили на 8-разрядные, но проблема межпроцессорного взаимодействия по-прежнему оставалась актуальной: для процессов с интенсивным взаимодействием межпроцессорные связи по линкам были узким местом, и вся ответственность за эффективное использование подобной архитектуры возлагалась на программистов. Именно они должны были так написать программу, чтобы межпроцессорные пересылки были минимизированы.

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

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

Упомянутая выше мультитредовая архитектура является очередной попыткой построения универсальной многопроцессорной системы с эффективным межпроцессорным взаимодействием посредством варьирования общей памяти (с арбитражем между процессорами) и распределенной памятью в виде регистровых файлов. При этом используются новые технологические возможности, позволяющие реализовать фрагменты многопроцессорных систем на одном кристалле. В этом направлении работают многие ведущие производители, включая Intel (IXP1200 с шестью четырехтредовыми процессорами [17]) и IBM (Blue Gene с 32-мя восьмитредовыми процессорами [18]).

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

Иллюстрацией данного факта могут служить результаты испытаний экспериментального варианта мультитредовой архитектуры MTA фирмы Tera [19]. Архитектура MTA предусматривает построение многопроцессорных конфигураций, содержащих до 256 процессоров, каждый из которых способен одновременно обрабатывать до 128 тредов на частоте 255 МГц. При этом переключение с одного треда на другой производится в одном цикле, а взаимодействие обеспечивается через 64 перекрывающихся блока памяти без применения кэширования. Результаты испытаний показали, что при большом количестве тредов (не менее 100) возможно достижение производительности в 2-3 раза превышающей производительность соответствующих конфигураций, построенных на Pentium Pro или Alpha. Однако, при малом количестве тредов производительность тестируемой системы уступает Pentium Pro или Alpha в 5 раз. Проблема остается прежней: как разработать или скомпилировать программу, имеющую не менее 100 тредов? Существующие компиляторы на это пока не способны и проблемы распараллеливания снова ложатся на программистов.

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


Вопросы и упражнения по разделу 2.1.

А. Какие требования предъявляются к архитектуре вычислительного комплекса?

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

В. Какие подходы применяются для распараллеливания вычислений?

Г. Какие проблемы возникают при проектировании многопроцессорных систем и как они решаются?


    1. ^ Требования к элементной базе цифровой обработки сигналов и изображений

Методы и средства обработки сигналов весьма разнообразны и в последние годы особенно интенсивно развиваются. Рассмотренные в предыдущих разделах основные преобразования дискретных и цифровых сигналов далеко не исчерпывают всех методов и алгоритмов, но дают представление о некоторых базовых требованиях, с учетом которых развивается элементная база цифровой сигнальной обработки. Наряду с традиционными методами, основанными на спектральном анализе сигналов, в последние годы все большее распространение получают и относительно новые методы, построенные, например, на вейвлет-преобразованиях [20] или на базе нейросетевых алгоритмов [21].

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

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

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

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

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

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

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

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


Вопросы и упражнения по разделу 2.2.


А. Каковы особенности вычислительных процессов, построенных на основе алгоритмов числовой обработки сигналов?

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

В. Как влияют требования реального масштаба времени на организацию вычислительного процесса?

Г. Какие требования к базовым вычислительным элементам и эффективности их взаимодействия предъявляются с точки зрения системного применения?


    1. ^ Основные характеристики процессоров цифровой обработки сигналов (DSP-процессоров)

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

Средства, ориентированные на мультимедийные приложения, реализованы, в частности, во многих архитектурных решениях фирмы Intel. Расширение системы команд, ориентированное на обработку сигналов и изображений было реализовано уже в микропроцессоре второго поколения Intel 80860. Начиная с Pentium III, основная система команд расширена дополнительными возможностями технологии MMX (Multi Media Extension), обеспечивающими распараллеливание в режиме SIMD. Аналогичные расширения применяются и другими известными фирмами - HP, Motorola, AMD и др. [8].

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

Пока технология универсальных процессоров не достигла такого уровня, чтобы обеспечить сигнальную обработку в реальном масштабе времени с приемлемой стоимостью и качеством, широкое применение находят специализированные процессоры сигнальной обработки. Учитывая растущее разнообразие областей применения, номенклатура и архитектурные принципы их построения варьируются в достаточно широком диапазоне - от простых и дешевых с небольшой разрядностью (12-16 бит) для массового применения в бытовых приборах до мощных многопроцессорных кристаллов с возможностью построения многопроцессорных конфигураций. Краткий обзор наиболее известных моделей приводится в [22].

Несмотря на многообразие DSP-процессоров (Digital Signal Processor), все они реализуют один и тот же относительно небольшой набор базовых характеристик. Это позволяет ввести единообразие при отображении структуры каждого DSP-процессора с тем, чтобы выявить общие черты с другими DSP-процессорами и подчеркнуть отличительные особенности.

На приведенном ниже рис. 2-1 показаны основные узлы типового современного процессора цифровой обработки сигналов.

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

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

  • получение очередного отсчета;

  • умножение на соответствующий коэффициент;

  • сложение с предыдущим результатом,

переход к новому отсчету (модификация указателя циклического буфера).

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

В процессоре TMS320C060 фирмы Texas Instruments можно выполнять в одном конвейере до четырех указанных циклов над числами с фиксированной запятой, что обеспечивает при тактовой частоте 200 МГц производительность до 1600 MIPS. В процессоре TigerSHARC фирмы Analog Devices можно обеспечить выполнение двух таких циклов на частоте 300 МГц.





Рис. 2-1. Основные узлы современного DSP-процессора.


Оба упомянутых выше процессора имеют длинные форматы инструкций (VLIW) и обеспечивают возможность организации вычислений в режиме SIMD. Процессор TigerSHARC имеет длину инструкции 128 разрядов и позволяет выполнять до 4-х инструкций над 32-разрядными данными с фиксированной запятой в режиме SIMD. Кроме того, каждый из двух вычислительных блоков может выполнять параллельно четыре 16-разрядных или восемь 8-разрядных SIMD-операций. Процессор TMS320C060 имеет длину инструкции 256 разрядов и позволяет выполнять до 8 инструкций в режиме SIMD.

^ Критерии и показатели оценки процессоров сигнальной обработки (DSP). В связи с тем, что мультипроцессорные конфигурации, построенные на современных DSP, способны в той или иной степени обеспечить обработку больших потоков сигнальной информации в реальном времени, характеристики архитектуры DSP оказывают весьма существенное влияние на технико-экономические характеристики проектируемых комплексов. Традиционным показателем качества современных микропроцессоров является производительность, которая характеризуется рядом показателей: тактовая частота, количество операций с фиксированной или плавающей запятой (соответственно MIPS и MFLOPS), а в случае сигнальных процессоров используются также специальные показатели скорости выполнения сигнальных операций, например, количество умножений с накоплением (MACS) или количество БПФ в секунду.

Как показывают исследования сигнальных потоков, проиллюстрированные в предыдущей на главе на некоторых типовых задачах медицинской диагностики, реальная вычислительная способность той или иной архитектуры в конкретных приложениях далеко не всегда определяется традиционными бенчмарками, измеренными в MIPS, MFLOPS, MACS и т.п. Это обстоятельство признают и сами ведущие производители процессоров сигнальной обработки. Например, специалисты фирмы Analog Devices рекомендуют при выборе микропроцессорной сигнальной архитектуры принимать во внимание и ряд других перечисленных ниже параметров, которые прямо или косвенно влияют на производительность и эффективность проектируемого комплекса.

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

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

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

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

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

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

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

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

Рассмотрим подробнее процессор ^ TigerSHARC фирмы Analog Devices ADSP-TS101S (рис. 2-2, бенчмарки в табл. 2-1).

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

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

^

Бенчмарки сигнального процессора TigerSHARC® Фирмы Analog Devices


Таблица 2-1.

^ Предельная производительность на частоте 250 MHz

1-разрядные операции

16 млрд. MACS/с

16-разрядные операции

2 млрд. MACS/с

32-разрядные с фиксированной запятой

500 млн. MACS/с

32-разрядные с плавающей запятой

1500 MFLOPS




^ 16-разрядные алгоритмы

Время выполнения
на частоте


250 MHz

Кол-во циклов

256-точечное комплексное БПФ (основание 2)

4,4 мкс

1 100

50-отсчетный FIR на 1024 входах

28,8 мкс

7 200

Единичный FIR MAC (умножение с накоплением)

0,56 нс

0,14

Единичный комплексный FIR MAC

2,28 нс

0,57




^ 32-разрядные алгоритмы

Время выполнения
на частоте 250 MHz


Кол-во циклов

1024-точечное комплексное БПФ (основание 2)

39 мкс

9 750

50- отсчетный FIR на 1024 входах

110 мкс

27 500

Единичный FIR MAC

2,16 нс

0,54

Единичный комплексный FIR MAC

8,64 нс

2,16




Скачать 1,64 Mb.
оставить комментарий
страница2/9
Дата29.09.2011
Размер1,64 Mb.
ТипУчебное пособие, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы: 1   2   3   4   5   6   7   8   9
плохо
  1
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Документы

наверх