Up
細粒度並列処理のための高位合成技術
概要
高位の動作記述からのハードウェアの自動合成を実現する、高位合成技術の研究を進めている。
これまでに、複数定数乗算のための回路を細粒度並列処理の観点から効率的に実現することを目指し、高位における最適化技術の提案とその有効性の検証を行った。
高位合成技術
ハードウェアの高位合成とは、抽象度の高い言語による動作記述を入力として、記述の最適化、 スケジューリング、アロケーション等の処理を実行することにより、アーキテクチャレベルのハードウェア構造を自動合成することである。
我々は自律的再構成可能アーキテクチャの実現においても有用な高位合成手法の可能性を探求している。
これまでに、ビットレベルの並列性，及びハードウェアの再構成可能性を活かせる演算として複数定数乗算を取り上げ、その高位合成の際に現れる最適化問題の計算複雑度の解析を行うとともに、具体的な最適化手法について検討した。
複数定数乗算問題
複数定数乗算問題とは、信号処理、画像処理、数値計算等においてしばしば現れる、複数の定数と変数間の乗算処理に関する演算コスト最小化問題である。
これまでに複数定数乗算問題に付随して定義されるAddition-Shift-Sequence問題 (ASS) という決定問題の計算複雑度を解析し、Vertex Cover問題 (VC) からの変換を行う (図1) ことでASSがNP-完全であることを示した[1]。
これにより最適解を効率的に求めることは困難であることが判断されるため、効率的な近似解法を探求した[2]。
考案した手法では、定数をまず二進表現、或いは signed digit 表現等によって0, 1, -1で表現し、ビットのパターンの頻出度に着目して、複数の定数の中に存在する共通部分表現を探索していく (図2)。
さらに行列積を処理する場合にも適用領域を広げて、その有効性を確認した[3]。
図1: VCからASSへの変換
図2: MCMでの部分表現の共有
参考文献
- [1]
- Matsuura, A. and Nagoya, A.:
Formulation of the Addition-Shift-Sequence Problem and Its Complexity,
Proc. of the 8th International Symposium on Algorithms and
Computation (ISAAC '97), pp. 42-51 (1997).
- [2]
- Matsuura, A., Yukishita, M. and Nagoya, A.:
A Hierarchical Clustering Method for the Multiple Constant
Multiplication Problem,
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E80-A, No. 10, pp. 1767-1773 (1997).
- [3]
- Matsuura, A. and Nagoya, A.:
Bit and Word-Level Common Subexpression Elimination for the Synthesis
of Linear Computations,
IEICE Transactions on Fundamentals of Electronics, Communicat
ions
and Computer Sciences , Vol. E81-A, No. 3, pp. 455-461 (1998).
Contact: 松浦 昭洋;
Email: matsuura@cslab.kecl.ntt.co.jp