Развертывание (реализация DSP)

Развертывание — это метод преобразования дублирования функциональных блоков для увеличения пропускной способности программы DSP таким образом, чтобы сохранить ее функциональное поведение на выходах. Разворачивание было впервые предложено Кешабом К. Пархи и Дэвидом Г. Мессершмиттом в 1989 году. ^{[ 1 ]}^{[ 2 ]} Развертывание в общей программе известно как развертывание цикла .

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

Пример

Для программы DSP $\scriptstyle y(n)=ay(n-9)+x(n)$ , заменив индекс $\scriptstyle n$ к $\scriptstyle 2k$ может привести к $\scriptstyle y(2k)=ay(2k-9)+x(2k)$ . Аналогично, заменив индекс $\scriptstyle n$ к $\scriptstyle 2k+1$ также может привести к тому, что $\scriptstyle y(2k+1)=ay(2k-8)+x(2k+1)$ .

Следовательно, мы преобразуем программу в следующую программу, которая получает 2 входных данных. $\scriptstyle x$ и произвести 2 вывода $\scriptstyle y$ в каждый момент времени.

y(2k)=ay(2k-9)+x(2k)

y(2k+1)=ay(2k-8)+x(2k+1)

Алгоритм раскладывания

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

В J -развёрнутом DFG для каждого узла U в исходном DFG существует J узлов в преобразованном DFG с той же функцией, что и U . Для каждого ребра в исходном DFG существует J ребер в преобразованном DFG, но его задержка составляет всего 1/ J раза по сравнению с исходной.

Формат ввода DFG

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

Алгоритм раскладывания

Учитывая фактор развертывания J

Для каждого узла U в исходном DFG сначала дублируем функциональные блоки J как U ₀ , U ₁ , ..., U _{J − 1} ,
Для каждого ребра U стрелка → V с задержками w в исходном DFG мы создаем ребра на преобразованном графе с помощью U _i стрелка → V _{( i + w )% J} с $\scriptstyle \lfloor {\frac {i+w}{J}}\rfloor$ для i = 0, 1, ... J − 1.

На следующем графике показан процесс работы алгоритма. Исходный DFG состоит из 2 узлов и 1 ребра с 37 задержками. В процессе развертывания используется J в качестве коэффициента развертывания = 4. Алгоритм сначала дублирует узлы U и V до 4 узлов U и 4 V. узлов Затем он выполняет переподключение на узлах с соответствующими задержками, например, U ₂ подключается к V с индексом (2 + 37)%4 = 3. Кроме того, задержка на фронте от U ₁ до V ₂ составляет $\scriptstyle \lfloor {\frac {37+1}{4}}\rfloor =9$ , и задержка на фронте от U ₃ до V ₀ равна $\scriptstyle \lfloor {\frac {37+3}{4}}\rfloor =10$ .

Следующий график представляет собой еще один пример, показывающий алгоритм разворачивания. Обратите внимание, что если задержка меньше, чем коэффициент развертывания J , J -развернутый DFG создаст ребро с задержкой 0, но соответствующий край которого в исходном DFG может быть ненулевым краем. Следовательно, процесс свертывания может привести к созданию фронта с нулевой задержкой для увеличения самого длинного пути в DFG. ((PS на рис. внизу справа — это T2, а не T1))

Характеристики

Развертывание сохраняет количество элементов задержки в DFG.

Это свойство сохраняется, поскольку сумма развернутого DFG равна

\left\lfloor {\frac {w}{J}}\right\rfloor +\left\lfloor {\frac {w+1}{J}}\right\rfloor +\left\lfloor {\frac {w+2}{J}}\right\rfloor +\cdots +\left\lfloor {\frac {w+J-1}{J}}\right\rfloor =w.

Следовательно, преобразование может увеличить пропускную способность в J раз, но ресурс элемента задержки не увеличится.

Критический путь и изменение времени

Когда w < J , рассмотрим путь с задержками w в исходной DFG, J -развертывание этого пути приводит к (Jw) путям без задержек и пути w с 1 задержкой. Если все пути в исходном DFG имеют задержку, превышающую J , критический путь развернутого DFG такой же, как критический путь его исходного DFG. Следовательно, преобразованный DFG увеличивает свою пропускную способность в J раз. Однако если существует путь с задержкой меньше J , новый путь будет создан без задержки. Следовательно, критический путь будет потенциальным на таком пути, который отличается от исходного критического пути и таким образом, что комбинационная задержка, следовательно, увеличится. В таком случае его пропускная способность не увеличится в J раз.

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

Раскладывание для малой мощности

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

Приложения

Параллельная обработка на уровне слов

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

Параллельная обработка на уровне битов

Последовательная обработка битов: один бит обрабатывается за такт, а полное слово обрабатывается за W тактов.
Побитовая параллельная обработка: одно слово из W бит обрабатывается за каждый такт.
Последовательно-цифровая обработка: N бит обрабатываются за такт, а слово обрабатывается за такт W/N. Параметр N называется размером разряда.

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

Краткое содержание

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

См. также

Ссылки

^ К.К. Пархи и Д.Г. Мессершмитт, «Полностью статическое и оптимальное по скорости планирование итеративной программы потока данных посредством оптимального развертывания», Proc. Международной конференции. о параллельной обработке, 1989, стр. 1–209 – 1–216.
^ К.К. Пархи и Д.Г. Мессершмитт, «Статическое планирование с оптимальной скоростью итеративных потоков данных посредством оптимального развертывания», IEEE Trans. на компьютерах, Vol. 40(2), февраль 1991 г., стр. 178-195, https://doi.org/10.1109/12.73588.

[1] К.К. Пархи и Д.Г. Мессершмитт, «Полностью статическое и оптимальное по скорости планирование итеративной программы потока данных посредством оптимального развертывания», Proc. Международной конференции. о параллельной обработке, 1989, стр. 1–209 – 1–216.

[2] К.К. Пархи и Д.Г. Мессершмитт, «Статическое планирование с оптимальной скоростью итеративных потоков данных посредством оптимального развертывания», IEEE Trans. на компьютерах, Vol. 40(2), февраль 1991 г., стр. 178-195, https://doi.org/10.1109/12.73588.

[ 1 ]

[ 2 ]