    
Раздел: Документация
0 ... 41 42 43 44 45 46 47 ... 78  £££с£££ЯИШ~ "™ Фильхра 9-ГО порядка Вход j у т 5 в VVV  нимальных версий остается равной 6 и в результате производительность повышается в (2«+2)/6 раз. Если желаемой производительностью является один ртсчет за такт, то нужно использовать конвейерный модуль алгоритма CORDIC, с помощью которого осуществляется конвейерная организация на уровне разрядов. С помощью таких модулей, имеющих двойной конвейер, получаются модульные схемы любых передаточных функций. 15.4. МОДУЛЬ АЛГОРИТМА CORDIC С ДВОЙНЫМ КОНВЕЙЕРОМ Чтобы повысить производительность как ортогонального фильтра, так и матрицы процессоров для выполнения алгоритма CORDIC, необходимо использовать модуль выполнения алгоритма CORDIC с двойным конвейером. Термин "двойной конвейер" означает, что не только последовательность вращений конвейеризована на алгоритмическом уровне, но и операции внутри каждого уровня алгоритма CORDIC конвейеризованы на уровне отдельных разрядов. Это усовершенствование вместе с представлением угла в виде кодовой последовательности элементарных вращений позволит выполнять алгоритм CORDIC достаточно быстро для достижения пропускной способности в один отсчет за такт. Для иллюстрации основных идей обратим внимание на случай, при котором алгоритм CORDIC используется исключительно для нормальных (а не гиперболических) вращений. Более общий случай рассмотрен в [12]. Типичной операцией г-го уровня алгоритма CORDIC является элементарная операция поворота на угол 6t (где tg в{ = 2"): х =х- о(2~{ ,(15.4) где Of =±1. Начальный угол поворота всегда равен ±90°, что соответствует значению о0 = ± 1 - Последовательность аг(/=0, ...,«) представляет угол и может быть использована как код его значения. Характерными являются операции двух типов: первая, в которой дан двумерный вектор и должна быть вычислена последовательность углов и норма, и вторая, когда данная последовательность о,- используется для вращения данного вектора на угол, представляемый этой последовательностью. В подавляющем большинстве алгоритмов обработки сигналов сам угол не представляет интереса и код о,- никогда не выводится из машины. Операции (15.4) "не нормализованы". Конечный результат (после прохождения п стадий конвейерной обработки) является слишком большим благодаря коэффициенту 1 Сй, где Кп зависит только от длины слова п. Коэффициент Кп может быть представлен в виде произведения Кп= П(1-£,2-), где е,- = ОД. Вычисление произведения [ху]т на (1 - е, 2 ) имеет ту же трудоемкость и требует такого же аппаратного обеспечения, что и (15.4)Г -X - -X £- 2 / = у-е,-2- (15.5) Нормализация может быть выполнена либо после завершения всех операций (15.4), либо между ними. Как будет показано далее, промежуточная нормализация (15.5) и операция (15.4) позволяют уменьшить общую продолжительность выполнения последовательности шагов алгоритма CORDIC. Основная конфигурация /-го этапа схемы алгоритма CORDIC приведена на рис. 15.12. Конвейер для алгоритма CORDIC будет представлять собой каскадное соединение этих схем. Это и есть упомянутый ранее конвейер макроуровня. Имеется много способов реализации сумматоров, входящих в схему на рис. 15.12. Если следовать концепции матричного умножения, то каждый сумматор принимает вид линейной структуры из полных сумматоров (ПС) с переносом, переходящим от одного сумматора к другому. Такая структура матричного умножителя имеет преимущества, так как перенос на одном уровне образует конвейер с переносом на следующем уровне или может быть даже передан на следующий уровень. Здесь же, однако, из-за наличия сдвиговых регистров нельзя передать перенос следующего уровня параллельно с предыдущим. Например, как видно из рис. 15.12, регистр г" сумматора 1 выдает г-й разряд у на вход сумматора 1 и перенос может распространяться только после того, как перенос при вычислении у на предыдущем уровне достигнет положения 1-го разряда. Отсюда следует, что прямая реализация схемы рис. 15.12 в виде полного одноразрядного сумматора будет приводить к общей логической глубине, равной и+/, одноразрядных сумматоров на уровень (схему). Так как последовательности схем связаны конвейерным способом друг с другом, то общую задержку определяет последний уровень (/ = п - 1). Общая логическая глубина в расчете на одну секцию с нормализацией может быть уменьшена до и изменением схемы соединения сдвигового регистра и сумматора. Общая идея выполнения арифметических операций в дополни- ~\ Регистр i Сумматор apj\£ ли лгу Сумматор/ Регистр i , V Сумматор1 т wpj\ Сумматор Регостр i Вращение j Регистр i 7 Нормализация j Рис. 15.12: Схема i-то этапа конвейерного алгоритма CORDIC Регистр i SC SC SC SC ш ТтТ ш Схема выбора т ПС ПС ПС ПС i разрядов Т I * Рис. 15.13- Конвейерный модуль из сумматора и сдвиговых регистров для случая до-полнительного кода с и - 8 и i - 4 г,юн \уло\ хгт у2т х3т Ml! 6Л21 6„1ги-Г] б,[3) бп\П+2\ у3\г\ х4т 60[3] [/7+21 ш 6Л5] бЛп+Ь] Рис. 15.14. Волновая векторная структура для алгоритма CORDIC с поразрядной конвейерной организацией между модулями. Значения моментов времени, относящиеся к алгоритму, показаны в скобках тельном коде приведена на рис. 15.13. Обозначим/ старших разрядов числах как Гх1; тогда в зависимости от значения знакового разряда у и переноса с из оставшихся полных сумматоров (ПС) старшие / разрядов результата могут быть равны или ПхЛ, или Гх1 + 1, или ПхЛ - 1. Схемы, обозначенные как блоки SC, непосредственно вычисляют эти три величины. Они примерно равноценны полусумматорам, так как состоят из двух независимых полусумматоров. Согласно этим схемам результаты передаются по конвейеру одновременно с получением х. Когда получаются значения sy и с (они получаются в схеме, которая представляет собой конвейер, связанный с у), выбирается одно из трех возможных значений (ПхЛ, ПхЛ + 1, ГхП -1) и результат 271 поступает на выход. Результат получается с задержкой на время работы одного ПС после получения х и j>. Схема, показанная на рис. 15.13, обычно используется вместо сумматоров с нормализацией (см. рис. 15.12) и может быть, следовательно, использована в другом месте конвейера. Возможно много вариантов основного решения: например, вариант, в котором перенос сдвигается на следующий уровень. При таком варианте внутренняя нормализация занимает мало времени, но приводит к дополнительным затратам на оборудование (дополнительные схемы ПС и SC на каждый уровень). Для гиперболического случая можно следовать некоторой общей стратегии [12]. Двойной конвейер для выполнения алгоритма CORDIC можно осуществить на каждом уровне. Это допускает конвейерную организацию на уровне разрядов между модулями, как показано на рис. 15.14 для случая линейного волнового процессора, где первый модуль вычисляет угол, закодированный последовательностью {<т,}, которая распространяется по остальным модулям. Это является основной операцией в QU-разложении или при определении собственных значений на основе вращений Гивенса. 15.5. ЗАКЛЮЧЕНИЕ Для обеспечения высокой производительности без потери качества при проектировании высококачественных фильтров и разработки алгоритмов обработки сигналов требуются методы планирования задач. Центральную роль при этом играют исчисление на графах предшествования и процедуры назначения задач. Корректное применение метода показывает, что с его помощью можно достичь в мультиплексном режиме производительности, равной одному отсчету на такт, если используются конвейерные модули на уровне разрядов, такие, как конвейерный алгоритм CORDIC. В методологии структурного проектирования разложение алгоритма на функциональные элементы, работающие параллельно или в конвейерном режиме, оказывается существенным шагом, который может быть повторен на последовательных уровнях абстракции. Получается отображение алгоритмического описания самого верхнего уровня на структуру кремниевого кристалла последовательным применением параллельно-конвейерных распределений работ. Например, на рис. 15.11 функциональными элементами являются элементы выполнения алгоритма CORDIC, которые сами имеют конвейерную организацию; в то же время внутренняя организация алгоритма CORDIC тоже имеет конвейерную структуру. Переход с верхнего уровня абстракции на менее высокий выполняется путем исключения из рассмотрения (распределенной) структуры управления, которая связывает воедино отдельные элементы. На каждом уровне можно различить два подуровня: функциональный, описывающий цели, которые должны достигаться при разработке устройства, и реализационный, который задает диаграмму реализации, соответствующую этому уровню. Например, на уровне алгоритмического описания, рис. 15.10 представляет собой функциональную схему, в то время как рис. 15.11 схему ее реализации. Переход от функционального описания к реализации производится путем параллельно-конвейерного распределения (операций по процессорам). При переходе на один уровень вниз диаграмма на рис. 15.11 становится функциональной и схема ее реализации описывает, как действительно выполнено устройство (CORDIC) и как передаются данные между модулями (по шинам) (см. рис. 15.14). Как продолжение можно говорить о логическом уровне, уровне схем и, наконец, об уровне аппаратуры. Говоря о реализации общего конвейерного алгоритма CORDIC, уместно сделать следующее замечание. На рис. 15.14 показано, что возможна конвейерная организация вращения и нормализации на одном уровне почти без потери времени на нормализацию. Можно подумать, что эта же техника может быть использована для конвейерного исполнения схем CORDIC, как в матричном умножителе. Однако это не так. Механизм передачи алгоритма CORDIC не позволяет образовывать общий конвейер, хотя несколько отдельных секций и могут быть объединены в конвейер. При данных ограничениях алгоритма CORDIC интересной темой исследования является сравнение его достоинств с достоинствами способа реализации умножителя, удовлетворяющего требованию максимальной производительности. Применение модуля CORDIC в волновых процессорных матрицах [13] также исследовалось совместно Делфтским технологическим университетом и Университетом Южной Калифорнии. СПИСОК ЛИТЕРАТУРЫ [I]A. Fettweis, "Digital Filter Structures Related to Classical Filter Networks," Arch. Elektr. Uebertrag., 25:79-89(1971). [2] E. Deprettere and P. Dewilde, "Orthogonal Cascade Realization of Real Multiport Digital Filters," Circuit Theory Appl., c?:245-272 (1980). [3] R. Nouta, "Studies in Wave Digital Filter Theory and Design," Ph.D. thesis, Delft University of Technology, 1980. [4] E. Deprettere and P. Dewilde, "Orthogonal Cascade Realization of Real Multiport Digital Filters," Circuit Theory Appl., «:245-272 (1980). [5] P. Dewilde, "Stochastic Modeling with Orthogonal Filters," in Outils et modiles mathimatiques pour I automat <que, Ianalyse de systimes et le traitement du signal, Vol. 2, CNRS, Paris, 1982, pp. 331-398. [6] P. Dewilde and H. Dym, "Schur Recursions, Error Formulas and Convergence of Rational Estimators for Stationary Stochastic Sequences," IEEE Trans. Inf. Theory, /T-27(4):446-461 (July 1981). [7] R. S. Martens, "Een hulp voor het Optimaal Implementeren van Digitate Filters in Parallelle Hardware," Delft University of Technology, Network Theory Tech. Rep. 30, 1980. [8] С. V. Ramamoorty, К. M. Chandy, and M. J. Gonzales, "Optimal Scheduling Strategies in a Multiprocessor System," IEEE Trans. Comput., C-2/(2):137 146 (Feb. 1972). [9] Т. C. Hu, "Parallel Sequencing and Assembly Line Problems," Oper. Res., 9:841-848 (Nov. 1961). [10] D. M. Schuler and E. G. Ulrich, "Clustering and Linear Placement," Proc. ACM IEEE Design Autom. Workshop, June 26-28,1972, Dallas, pp. 250-256. [II]R. A. Roberts and С. T. Mullis, "Digital Signal Processing Structures for VLSI," Proceedings, USC Workshop on "VLSI and Modern Signal Processing," pp. 83-88. 0 ... 41 42 43 44 45 46 47 ... 78 |
