Программирование циклических алгоритмов тест программирование циклических алгоритмов

7.5.4Формулировка Циклического планирования

В одноинтервальных и блокирующих формулировках мы не учли того факта. Что график по своей сути является периодическим. Поэтому удобно соединять K вычислительных графов в замкнутый контур. Как показано на рис. 7.18 [24]. Это приведет к периодической формулировке планирования. Которая допускает период планирования. Равный K раз больше. Чем интервал выборки. Эта циклическая формулировка при определенных условиях приведет к максимально быстрому графику. Это наиболее общая формулировка планирования. И она может быть использована для поиска оптимальных по ресурсам расписаний с использованием произвольных ограничений, например. Частоты дискретизации и задержки.

Рис. 7.18. K циклически сцепленных вычислительных графов

Каждый вычислительный график представляет операции и задержки шиммирования и выравнивания в пределах одного интервала выборки. Элементы задержки в критическом контуре заменяются новыми элементами задержки. Представляющими собой задержку T = K T Если требуемая частота дискретизации меньше. Чем период итерации. То в каждый цикл должна быть вставлена соответствующая величина выравнивающей задержки. Чтобы их длина была кратна желаемому периоду дискретизации.

Это может помочь представить графики вычислений, нарисованные на цилиндре окружности. Равной периоду планирования (который кратен периоду выборки. Как было рассмотрено в главе 6).

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

Время вычисления для PE больше чем Tmin или

Критический цикл(циклы) содержит более одного элемента задержки.

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

Минимальный период выборки, используя неограниченное количество ресурсов. Достигается для K = NiCP. Более интересным случаем является получение Tmin при использовании минимального количества ресурсов. Это достигается, если существует только один CP, и выполняется правильное планирование, с

(7.2)

K=mNiCP

где m = целое число. Чтобы найти фактический минимум ресурсов. Необходимо найти наилучшие графики с минимальными ресурсами для всех разумных значений m. Типичные значения для m находятся в диапазоне от 1 до 10.

Если существует несколько CP, то вместо этого планирование должно выполняться для

(7.3)

K=mN1CPN2CP

Как правило, поиск по всем разумным значениям K должен быть выполнен для того. Чтобы найти минимальное расписание ресурсов.

Пример 7.2

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

На рис. 7.19 показано начальное расписание. Полученное путем каскадирования двух вычислительных графиков. Требования к хранению и количеству умножителей и сумматоров остаются такими же. Как и в примере 7.1. Лучший график показан на рис. 7.20. Он получается путем распространения различных типов задержек по всему графу таким образом. Что число одновременных умножений уменьшается. В этом случае мы получаем график. Который требует только двух умножителей и одного сумматора. Число элементов задержки составляет 92/2 = 46 единиц на выборку. Однако некоторые задержки могут быть разделены между ветвями так. Что только 71/2 = для каждого образца требуется 35,5 единиц задержки. Как правило, существует много альтернативных расписаний, требующих одинакового количества PE. Но с различными требованиями к памяти и связи.

Рис. 7.19. Начальный график для двух интервалов выборки

Рис. 7.20. График для двух интервалов выборки

Пример 7.3

Найдите периодическое расписание для решетчатого волнового цифрового фильтра третьего порядка. Используемого в примере 6.5.

В этом случае существует только один критический цикл. Он содержит два сложения, одно умножение и два элемента задержки. Это означает, что минимальный период выборки равен (2Tadd + Tmult)/2. В битовой последовательной арифметике операции конвейеризуются на битовом уровне. Следовательно, Tadd и Tmult-это время (задержка). Необходимое для появления наименее значимого бита на выходе соответствующего PE. Таким образом, Tmult зависит только от длины слова коэффициента и не зависит от длины слова данных. Сложение задержит наименее значимый бит на 1 такт в то время как умножитель вызовет задержку Wc = 4 такта. Таким образом, минимальный период выборки составляет 3 такта.

Как правило, критический цикл на рис.6.30 должен быть по меньшей мере таким же длинным. Как и самое длительное время выполнения любого из PE. Это эквивалентно планированию по крайней мере на пять выборочных периодов. Поскольку множитель требует Wc +  Wd − 1 = 15 тактовых циклов и Tmin = 3 тактовых цикла. Минимальное расписание ресурсов с периодом выборки 3 такта показано на рис .7.21.

Рис. 7.21. Минимальный график ресурсов

Реализация этого графика требует пяти умножителей, 20 сумматоров и 70 D-триггеров. В этом случае множитель соответствует схеме расширения знака. Одному разрядно-последовательному сумматору с неявным D-триггером и одному D-триггеру. Вход и выход фильтра состоят из пяти битовых последовательных потоков. Перекошенных во времени. Реализация с битово-параллельным форматом ввода и вывода может быть реализована с использованием сдвиговых регистров в качестве последовательно-параллельных преобразователей.

На рис. 7.22 более явно показана логическая реализация, основанная на однофазной логике [26]. Расчетное количество устройств составляет 2400 для фильтра с дополнительными 400 транзисторами. Необходимыми для схемы управления. Блок управления реализован с использованием 15-битного сдвигового регистра. Для полного фильтра требуется около 2800 транзисторов. Потребляемая мощность оценивается в 0,8 нДж/образец. Частота дискретизации 35 МГц соответствует тактовой частоте 105 МГц и 30 МВт. Требуемая площадь чипа с использованием 0,8 мкм двойного металлического КМОП—процесса (AMS-Austria Micro Systeme Intern. Gmb) меньше 1,0 мм2.

Рис. 7.22. Логическая реализация

Моделирование, а также измерения показывают. Что эти схемы могут быть синхронизированы на очень высоких скоростях. Тактовые частоты значительно выше 400 МГц возможны при тщательном проектировании схемы. Следовательно. Частота дискретизации более 130 МГц возможна при энергопотреблении около 325 МВт.

Обратите внимание, что на рис .7.22, по-видимому, существует цикл без задержки. Который сделал бы реализацию невозможной. К счастью, это не так. Мы обсудим, как этот вопрос может быть решен в разделе 7.5.5.

Пример 7.4

Найдите периодическое. Максимально быстрое расписание для решетчатого волнового цифрового фильтра третьего порядка. Используемого в примере 6.8. В этом случае мы должны запланировать более шести выборочных интервалов. Минимальное расписание ресурсов для преобразованного алгоритма показано на рис. 7.23. Этот график имеет средний период выборки всего в 2,5 такта. Что является истинным минимумом. Вход и выход фильтра состоят из шести битовых последовательных потоков. Которые смещены во времени.

Рис. 7.23. Максимально быстрый, минимальный ресурс графика

Эта реализация, показанная на рис. 7.24, требует шести умножителей, 30 сумматоров и 78 D-триггеров. Расчетное количество устройств составляет 3000 для фильтра с дополнительными 400 транзисторами для схемы управления. Таким образом. Для полного фильтра требуется около 3400 транзисторов. Требуемая площадь стружки составляет менее 1,2 мм2. Увеличение максимальной скорости приводит к соответствующему увеличению площади. Ожидаемый расход энергии такой же. Как и для фильтра в примере 7.3 с эквивалентными частотами дискретизации.

Рис. 7.24. Логическая реализация

Интересно сравнить эту реализацию с битово-параллельной реализацией. Которая использовала один такт (35 МГц двухфазный такт) на выборку и имела семь битово-параллельных сумматоров переноса-сохранения. Битовая параллельная реализация требует 77 полных сумматоров. В то время как битовая последовательная требует только 36 полных сумматоров и использует только 2,5 такта (400 МГц) на выборку. Это приводит к значительно более высокой скорости. А также меньшей площади чипа и энергопотреблению по сравнению с битово-параллельной реализацией.

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