Up

High-Level Synthesis for Fine-Grained Parallel Processing

Abstract

We are researching high-level synthesis technologies which synthesizes hardware from behavioral descriptions. We proposed optimization techniques for the synthesis of multiple constant multiplications and showed their effectiveness in terms of fine-grained parallel processing.

High-Level Synthesis

High-level synthesis is a methodology for automatically synthesizing hardware at the architectural level. First, a behavioral description is given as input and optimized with compiler techniques. Subsequently, phases such as scheduling, allocation and binding are applied. We have since examined the potential of such a methodology, aiming at autonomous reconfigurable architecture. We have analyzed the computational complexity of an optimization problem that emerges for the synthesis of multiple constant multiplications in the bit level, and also proposed efficient algorithms for solving the optimization problem.

The Multiple Constant Multiplication Problem

A constant multiplication is the multiplication of a variable with a single constant. The Multiple Constant Multiplication (MCM) problem is a cost minization problem in which cost is defined as the number of additions/subtractions and shifts to execute constant multiplications. Such computations appear in applications such as signal and image processing, numerical computation and coding theory. We defined the Addition-Shift-Sequence (ASS) problem, which is a decision problem associated with the MCM problem, and proved that ASS is NP-complete[1]. The transformation is executed from the Vertex Cover (VC) problem to ASS(Fig. 1). We then developed a method that exploits common subexpressions latent among constants in the bit level(Fig. 2)[2]. This method is extended to deal with matrix products[3].

Fig. 1: Transformation from VC to ASS
Fig. 1: Transformation from VC to ASS

Fig. 2: Subexpression Sharing in MCM
Fig. 2: Subexpression Sharing in MCM

References

[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: Akihiro Matsuura; Email: matsuura@cslab.kecl.ntt.co.jp