Abstract
In this paper, we present an incremental synthesis procedure for a class of data path synthesis problems in which synthesis is carried out in a control step by control step fashion. The synthesis problems are classified according to the type of input dataflow graph (scheduled or unscheduled) and the type of storage units used (individual registers, single-port memory units, or multi-port memory units). These problems are solved optimally by employing either a network flow or 0–1 integer linear programming formulation. Experimental results on a number of benchmark problems are provided to demonstrate the effectiveness of the incremental synthesis algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D. Gajski, N. Dutt, A. Wu., and S. Lin (Eds.),High-Level Synthesis—Introduction to Chip and System Design, Kluwer Academic Publishers, 1992.
C.Y. Huang, Y.S. Chen, Y.L. Lin, and Y.C. Hsu, “Data path allocation based on bipartite weighted matching,”Proc. 27th DAC, pp. 499–504, 1990.
M. Rim, R. Jain, and R.D. Leone, “Optimal allocation and binding in high-level synthesis,”Proc. 29th DAC, pp. 120–123, 1992.
B.M. Pangrle, “Splicer: A heuristic approach to connectivity binding,”Proc. 25th DAC, pp. 536–541, 1988.
M. Balakrishnan and P. Marwedel, “Integrated scheduling and binding: A snthesis approach for design space exploration,”Proc. 26th DAC, pp. 68–74, 1989.
R.J. Cloutier and D.E. Thomas, “The combination of scheduling, allocation, and mapping in a single algorithim,”Proc. 27th DAC, pp. 71–76, 1990.
P.G. Paulin and J.P. Knight, “Scheduling and binding algorithms for high-level synthesis,”Proc. 26th DAC, pp. 1–6, 1989.
S. Devadas and A.R. Newton, “Algorithm for hardware allocation in data path synthesis,”IEEE Trans. on CAD, Vol. 8, No. 7, pp. 768–781, 1989.
T. Kim and C.L. Liu, “Utilization of multiport memories in data path synthesis,”Proc. 30th DAC, pp. 298–302, 1993.
I. Ahmad and C.Y. Roger Chen, “Post-process for data path synthesis using multiport memories,”Proc. ICCAD/91, pp. 276–279, 1991.
M. Balakrishnan et al., “Allocation of multiport memories in data path synthesis,”IEEE Trans. on CAD, Vol. 7, No. 4, pp. 536–540, 1988.
R.E. Tarjan,Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics, 1983.
C.-J. Tseng and D. Siewiorek, “Automated synthesis of data path in digital systems,”IEEE Trans. on CAD, Vol. 5, No. 3, pp. 379–395, 1986.
F.J. Kurdahi and A.C. Parker, “REAL: A program for register allocation,”Proc. 24th DAC, pp. 80–85, 1987.
T. Kim,Scheduling and Allocation Problems in High-Level Synthesis, Ph.D. Thesis, The University of Illinois, 1993.
T. Kim, J.W.S. Liu, and C.L. Liu, “A scheduling algorithm for conditional resource sharing,”Proc. ICCAD'91, pp. 84–87, 1991.
M. Rim et al., “Optimal allocation and binding in high-level synthesis of VLSI digital systems,” Tech. Report, Dept. of Electrical and Computer Engineering, University of Wisconsin-Madison, 1991.
P.G. Paulin and J.P. Knigh, “High-level synthesis benchmark results using a global scheduling algorithm,” inLogic and Architecture Synthesis for Silicon Compilers, North-Holland, pp. 211–229, 1989.
A.C. Parker, J. Pizarro, and M.J. Mlinar, “MAHA: A program for data path synthesis,”Proc. 23rd DAC, pp. 461–466, 1986.
R.A. Bergamaschi, R. Camposano, and M. Payer, “Area and performance optimization in path-based scheduling,”Proc. 2nd EDAC'91, pp. 304–310, 1991.
K. Wakabayashi and H. Tanaka, “Global scheduling independent of control dependencies based on condition vectors,”Proc. 29th DAC, pp. 112–115, 1992.
B. Haroun and B. Sajjadi, “ILP synthesis of signal processing architectures with Minimum structural complexity,”Proc. Custom Integrated Circuits Conference, pp. 237–240, 1994.
F.S. Tsai and Y.C. Hsu, “STAR: An automatic data path allocator,”IEEE Trans. on CAD, Vol. 11, No. 9, pp. 1053–1064, 1992.
C.T. Hwang, J.H. Lee, and Y.C. Hsu, “A formal approach to the scheduling problem in high level synthesis,”IEEE Trans. on CAD, Vol. 10, No. 4, pp. 464–475, 1991.
L. Stok,Architectural Synthesis and Optimization of Digital Systems, Ph.D. Thesis, Eindhoven University of Technology, the Netherlands, 1991.
B.S. Haroun and M.I. Elmasry, “Architecture synthesis for DSP silicon compiler,”IEEE Trans. on CAD, Vol. CAD-8, No. 4, pp. 431–447, 1989.
G. Krishnamoorthy and J.A. Nester, “Data path allocation using an extended binding model,”Proc. 29th DAC, pp. 279–284, 1992.
L. Stok, “Interconnection optimisation during data path allocation,”Proc. 1st EDAC, pp. 141–145, 1990.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kim, T., Liu, C.L. An integrated algorithm for incremental data path synthesis. J VLSI Sign Process Syst Sign Image Video Technol 12, 265–285 (1996). https://doi.org/10.1007/BF00924989
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF00924989