    
Раздел: Документация
0 ... 40 41 42 43 44 45 46 ... 78 Соотношение между входными Рис- 15.3. Вращение и выходными величинами Гивенса
Из рис. 15.2 следует, что некоторые Г-вершины (состояния фильтра) на последующем цикле уже готовы для обработки, в то время как нужда в других вершинах текущего цикла возникает только на очень поздней стадии. Отсюда следует, что очередной цикл может начаться в то время, как текущий еще не полностью завершен. В этом суть конвейеризации. Этот эффект может быть учтен в графе предшествования путем присваивания ненулевых -уровней заключительным Г-вершинам почти тем же способом, что и ранее, т.е. аналогично присвоению Л-уровней начальным /"-вершинам.. Вершины цикла и, для которых вычисления завершены, становятся начальными Г-вершинами цикла и + 1, и можно обновить их 2?-уровни, вычитая длину цикла п. Таким образом могут получаться отрицательные /j-уровни. Они показывают время, оставшееся для выполнения (и + 1)-го цикла нового состояния, до завершения и-го цикла. Эта информация используется для сжатия нового цикла. После нескольких повторений этой процедуры устанавливается минимальный такт конвейера, равный длине критического пути, который становится периодом графа предшествования. Распределения в этом периоде могут быть выполнены в основном тем же способом, что и в исходном графе. Результаты работы этой процедуры приведены на рис. 15.3 (в этом примере конвейеризация не дает больших улучшений: время цикла уменьшается от 85 до 80 с повышением производительности в 85/80 раз). Оценка минимального периода времени работы конвейера (минимального такта конвейера) часто может быть получена нахождением длины критического пути между данным состоянием и последующим (такой путь не обязательно должен существовать, но в истинно рекурсивных ситуациях часто он существует) . Такой путь нельзя нарушать во время сжатия. После построения диаграммы предшествования и исследования возможности параллелизма или конвейерности необходимо распределить операции на имеющуюся аппаратуру. Эта процедура распределения и планирования не является столь же простой, как построение диаграммы предшествования. На эту тему имеется обширная литература (см., например, [8 - 10]). Более того, эта проблема оказывается в общем случае NP-полной. Тем не менее в частных случаях могут быть сконструированы алгоритмы и может быть осуществлен эвристический (но, возможно, не оптимальный) выбор на основе диаграммы предшествования. Вопрос о назначении операций процессорам разделяется на две основные части, которые можно изложить независимо. 1.В какой последовательности операции должны назначаться процессору? В какое время должно осуществляться назначение? Если несколько операций готовы для назначения, какая будет выбрана первой? 2.В каком процессоре должна быть размещена операция, минимизирующая время обмена данными и количество передаваемой информации между процессорными элементами? Следующие стандартные допущения облегчают решение: 1)обмен данными не требует никакого времени; 2)интерес представляет минимизация связей между процессорами; 3)желательно минимизировать время выполнения операций. Вопрос о том, "когда" планировать данную вершину (на исполнение), был исследован в работе [8]. Оптимальное решение может быть найдено при исчерпывающем длительном поиске. Простой, близкий к оптимальному алгоритм, предложенный в [9], сводится к следующему: 1)вершина должна быть назначена как можно раньше; 2)приоритет имеет вершина с самым меньшим значением L -уровня. Этот алгоритм может привести к ошибкам планирования, так как иногда полезнее выполнить раньше более поздние, но более срочные операции. Алгоритм может быть усовершенствован добавлением следующего правила: Если данная операция /, которая готова для назначения, в действительности задерживает более позднюю операцию с меньшим значением А,-уровня (следовательно, более срочную операцию), операция i должна быть отменена. Следующим вопросом является "где" (в каком процессоре) выполнять операцию. Если желательно минимизировать время, теряемое при обмене данными, то важной становится минимизация числа пересылок между процессорными элементами. Здесь опять хороший эвристический алгоритм является предпочтительнее исчерпывающего поиска. Согласно такому алгоритму операции будут назначаться на основе меры близости операции и процессора. Проблемой является определение корректной меры близости. В расчет должно приниматься: 1)число путей, связывающих один процессор с другим, как входящих, так и выходящих; 2)вес каждого процессора. Число путей от одной операции к другой (даже путей, связывающих операции в разных циклах) можно эффективно определить по графу инциденций (см. [10]). В данном методе вычисляются числа С« и Tt, где C\j - число путей между вершинами / и у", а Т{ - полное число путей, начинающихся в вер-•шине i. Хорошей мерой близости является близость = Су/7} +Cfi/T,.(15.3) Назначение, которое было сделано автоматически на основе этой меры для алгоритма, схема которого приведена на рис. 15.1, показано на рис. 15.2. Опыт показывает, что качество результатов машинного назначения лучше, чем при ручной работе. 15.3. параллельно и конвейерные ортогональные фильтры В общем случае глобально ортогональные фильтры при реализации их каскадным способом имеют весьма полезное свойство: низкую чувствительность в полосе пропускания и в полосе затухания. В этом смысле они сущест- 263 веяно лучше каскадных фильтров, даже если соединяемые в каскад элементы реализованы ортогональным методом [11]. Однако за эти их свойства платится большая цена, поскольку едва ли возможны параллелизм и конвейерность в минимальной реализации. К счастью, при использовании неминимальных версий фильтров, как будет показано, возможно получение высокой пропускной способности путем организации конвейера с сохранением в то же время глобальной ортогональности. В глобально ортогональном фильтре могут использоваться только ортогональные преобразования, наиболее элементарным из которых является вращение Гивенса, условно показанное на рис. 15.3. Введение сумматоров и мультиплексоров недопустимо, так как такие операции неортогональны (приемлемы только ветвления в самом конце). Образцом глобально ортогонального фильтра является формирующий фильтр Левинсона (рис. 15.4). Этот фильтр реализует авторегрессионную передаточную функцию и может быть легко конвейеризован, как показано на диаграмме предшествования на рис. 15.5, где изображены два конвейерных цикла. Если каждое ортогональное преобразование осуществляется за один такт, то достигается пропускная способность в один отсчет за два такта. Эта структура хорошо реализуется с помощью вращения по алгоритму CORDIC. В случае, когда используется конвейерный алгоритм CORDIC, описанный в разд. 15.4, пропускная способность в один отсчет за такт может быть получена в мультиплексном режиме. Для высококачественных избирательных фильтров, которые используются в системах электросвязи, необходима реализация ортогонального БИХ-фильтра. В [4,5] было показано, что любая передаточная функция может быть реализована путем соединения элементов трех типов, схемы которых приведены на рис. 15.6. Пример общей схемы, полученной каскадным соединением секций, показан на рис. 15.7 (это схема ортогональной реализации эллиптического фильтра 9-го порядка). Диаграмма предшествования, соответствующая схеме на рис. 15.7, приведена на рис. 15.8. По ней легко определить, что невозможно организовать конвейерную обработку для фильтра этого типа, так как имеется критический путь из одного состояния в то же самое состояние в следующем цикле (в примере критический путь ведет из состояния 1 в состояние 1). Средством преодоления этой ситуации является замена основных секций (см. рис. 15.6) совокупностью возможно более избыточных, полученных путем каскадного соединения элементов типа II или типа III, за которыми следует фиктивный элемент типа I (рис. 15.9). Таким образом преимущества конвейерной схемы на элементах Левинсона переносятся на другие элементы (рис. 15.10). Может показаться странным, что простейшая модификация основного элемента приводит к конвейерной организации фильтра. Однако из диаграммы предшествования на рис. 15.11 следует, что наиболее длинный критический путь между состоянием и его следующим значением равен 6 вместо 18, а коэффициент повышения производительности этого типа фильтра достигает 18/6. Для фильтров больших порядков это повышение производительности становится весьма эффективным: минимальная версия будет иметь критический путь длиной 2«+2 (где п - порядок фильтра), в то время как длина для неми- I
ЧИ-4. 5--т-*- Рис. 15.4. Формирующий фильтр Левинсона Вход ГТ Т2 Рис. 15.5. Диаграмма предшествования для формирующего фильтра Левинсона, показывающая возможность организации конвейерной обработки. Если вращение Гивенса выполняется в виде конвейерного алгоритма CORDIC, то может быть достигнута пропускная способность в один отсчет за такт в мультиплексном режиме  Выход
 б)в) Рис. 15.6. Элементы, являющиеся составными частями глобального ортогонального фильтра при каскадном способе реализации: Г тип I AR-секция; б - тип II, действительная секция Ьго порядка; в - тип III, действительная секция 2-го порядка    Рис. 15.9. Избыточные ортогональные ячейки, удобные для конвейерной организации произвольной передаточной БИХ-функции: а - тип I; AR-элемент; б - тип II, конвейерный действительный элемент 1-го порядка; в - тип III, конвейерный действительный элемент 2-го порядка. 0 ... 40 41 42 43 44 45 46 ... 78 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
