展開（DSP実装）

アンフォールディングとは、 DSPプログラムのスループットを向上させるために、機能ブロックを複製することで、出力における機能的な動作を維持する変換手法です。アンフォールディングは、1989年にKeshab K. ParhiとDavid G. Messerschmittによって初めて提案されました。 [ 1 ] [ 2 ]一般的なプログラムにおけるアンフォールディングは、ループアンローリングとして知られています。

アンフォールディングは、高速かつ低消費電力のASICアーキテクチャの設計に応用できます。例えば、プログラムを展開することで隠れた並行性を明らかにし、プログラムをより短い反復周期でスケジュールすることで、実装のスループットを向上させることができます。また、ワードレベルまたはビットレベルでの並列処理にも応用できます。このように変換された回路は、スループットを向上させ、消費電力を削減することができます。

例

DSPプログラムの場合、インデックスを に置き換えると の結果になる可能性があります 。同様に、インデックスを に置き換えるとの結果になる可能性があります 。 y（n）＝1つのy（n−9）+×（n）{\displaystyle \scriptstyle y(n)=ay(n-9)+x(n)}n{\displaystyle \scriptstyle n}2け{\displaystyle \scriptstyle 2k}y（2け）＝1つのy（2け−9）+×（2け）{\displaystyle \scriptstyle y(2k)=ay(2k-9)+x(2k)}n{\displaystyle \scriptstyle n}2け+1{\displaystyle \scriptstyle 2k+1}y（2け+1）＝1つのy（2け−8）+×（2け+1）{\displaystyle \scriptstyle y(2k+1)=ay(2k-8)+x(2k+1)}

したがって、プログラムを、2 つの入力を受け取り、毎回 2 つの出力を生成する次のプログラムに変換します。×{\displaystyle \scriptstyle x}y{\displaystyle \scriptstyle y}

y（2け）＝1つのy（2け−9）+×（2け）{\displaystyle y(2k)=ay(2k-9)+x(2k)}
y（2け+1）＝1つのy（2け−8）+×（2け+1）{\displaystyle y(2k+1)=ay(2k-8)+x(2k+1)}

展開アルゴリズム

データフローグラフ（DFG）形式のDSPプログラムと展開係数Jが与えられた場合、展開処理は、DSP機能を維持しながら、機能ブロックを複製し、再接続することで、DSPプログラムを新しいプログラムに変換します。係数Jを用いて実行されたプログラムを、J展開DFG と呼びます。

J展開DFGでは、元のDFGの各ノードUに対して、変換後のDFGにはUと同じ機能を持つJ 個のノードが存在します。元のDFGの各エッジに対して、変換後のDFGにはJ 個のエッジがありますが、その遅延は元の DFGの 1/ J倍です。

入力形式 DFG

データフローグラフはラベル付きの有向グラフです。各ノードにはその機能を示すタイプがラベル付けされ、各エッジには遅延を示す数値がラベル付けされます。

展開アルゴリズム

展開因子Jを与えられた

  • 元のDFGの各ノードUについて、まずJ個の機能ブロックをU 0 , U 1 , ..., U J − 1として複製します。
  • 元のDFGでw遅延を持つ各エッジU arrow → Vに対して、 i = 0, 1, ... J − 1のU i arrow → V ( i + w )% Jによって変換されたグラフ上にエッジを作成します。⌊私+わJ⌋{\displaystyle \scriptstyle \lfloor {\frac {i+w}{J}}\rfloor }

次のグラフは、アルゴリズムのプロセスを示しています。元のDFGは2つのノードと1つのエッジで構成され、遅延は37個です。展開プロセスでは、 J  = 4を展開係数として使用します。アルゴリズムはまず、ノードUとVを4つのUノードと4つのVノードに複製します。次に、対応する遅延を持つノードの再接続を実行します。例えば、 U 2 はインデックス(2 + 37)%4 = 3でVに接続します。さらに、エッジU 1からV 2への遅延は、エッジU 3からV 0への遅延は です。 ⌊37+14⌋＝9{\displaystyle \scriptstyle \lfloor {\frac {37+1}{4}}\rfloor =9}⌊37+34⌋＝10{\displaystyle \scriptstyle \lfloor {\frac {37+3}{4}}\rfloor =10}

以下のグラフは、展開アルゴリズムを示す別の例です。展開係数Jよりも小さい遅延がある場合、J展開されたDFGは遅延が0のエッジを作成しますが、元のDFGでは対応するエッジが非ゼロのエッジである可能性があることに注意してください。したがって、折り畳み処理によって遅延が0のエッジが作成され、DFG内の最長経路が増加する可能性があります。((PS：右下の図はT1ではなくT2です))

プロパティ

  • 展開すると、DFG 内の遅延要素の数が保持されます。

この性質は、展開されたDFGの合計が

⌊わJ⌋+⌊わ+1J⌋+⌊わ+2J⌋+⋯+⌊わ+J−1J⌋＝わ。{\displaystyle \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の場合、元の DFG でw 個の遅延があるパスを考えます。このパスをJ展開すると、遅延のない (Jw) 個のパスと、遅延が 1 個のw個のパスが生成されます。元の DFG のすべてのパスの遅延がJより大きい場合、展開された DFG のクリティカル パスは、元の DFG のクリティカル パスと同じになります。したがって、変換された DFG ではスループットがJ倍に増加します。ただし、遅延がJ未満のパスがある場合は、遅延のない新しいパスが作成されます。したがって、元のクリティカル パスとは異なるパスでクリティカル パスが発生する可能性があり、組み合わせ遅延が増加します。このような場合、スループットはJ倍に増加しません。

このような問題を解決するために、元の DFG でリタイミングを実行し、遅延がJよりも大きいすべてのパスを許可することができます。

低消費電力で展開

アンフォールディングは並列処理の一般的なケースであり、パイプライン化や並列化技術と同様に低消費電力特性を備えています。元の回路に比べて容量はJ倍になりますが、その容量を充電する時間は1/J倍です。さらに、充電時間は電源電圧の反比例関係にあります。したがって、電源電圧を下げることで、J倍の容量を1/J倍の時間で変化させることができます。最終的に、消費電力は電源電圧の低下の2乗となり、アンフォールディング回路は消費電力を削減できます。

アプリケーション

ワードレベルの並列処理

アンフォールディング変換は、ワードシリアルアーキテクチャからワードパラレルアーキテクチャを設計するために使用できます。以下は、ワードシリアルアーキテクチャからワードパラレルアーキテクチャへの変換例です。

ビットレベルの並列処理

  • ビットシリアル処理: 1 ビットがクロック サイクルごとに処理され、完全なワードはWクロック サイクルで処理されます。
  • ビット並列処理: Wビットの 1 ワードがクロック サイクルごとに処理されます。
  • ディジットシリアル処理：クロックサイクルごとにNビットが処理され、1ワードはW/Nクロックサイクルで処理されます。パラメータNはディジットサイズと呼ばれます。

このようにして、展開によりアーキテクチャ探索を実行し、システム内の最適な実装を見つけることができます。

まとめ

アンフォールディング変換は、 DFGで記述されたデジタル信号処理システムにおける隠れた並行性を解明することができます。したがって、アンフォールディングは、機能ブロックを複製することでシステムのスループットを向上させるために使用できますが、遅延要素を増加させることはありません。パス上の遅延を適切に処理（リタイミングなど）すれば、各機能ブロックの複製数であるJ倍のスループットを向上させることができます。このような変換技術は、高速アプリケーションや低消費電力アプリケーションに使用できるワールド並列アーキテクチャの生成に適用できます。したがって、アンフォールディングは、面積、スループット、消費電力のバランスをとるのに適した技術です。

参照

参考文献

  1. ^ KK ParhiとDG Messerschmitt、「最適展開による反復データフロープログラムの完全静的レート最適スケジューリング」、並列処理に関する国際会議論文集、1989年、pp. 1-209 – 1-216
  2. ^ KK Parhi、DG Messerschmitt、「最適展開による反復データフロープログラムの静的レート最適スケジューリング」、IEEE Trans. on Computers、Vol. 40(2)、1991年2月、pp. 178-195、 https://doi.org/10.1109/12.73588
「 https://en.wikipedia.org/w/index.php?title=Unfolding_(DSP_implementation)&oldid=1122741444」より取得