Loop optimization in register-transfer scheduling for DSP-systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Loop optimization in register-transfer scheduling for DSP-systems

Full text

Pdf (793 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 26th ACM/IEEE Design Automation Conference table of contents

Las Vegas, Nevada, United States

Pages: 826 - 831

Year of Publication: 1989

ISBN:0-89791-310-8

Authors

G. Goossens	IMEC Laboratory, Kapeldreef 75, B-3030 Leuven, Belgium
J. Vandewlle	Laboratory, Katholieke Universiteit, K. Mercierlaan 94, B-3030 Leuven, Belgium
H. De Man	IMEC Laboratory, Kapeldreef 75, B-3030 Leuven, Belgium and Laboratory, Katholieke Universiteit, K. Mercierlaan 94, B-3030 Leuven, Belgium

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS\TCDA : TC Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 19, Citation Count: 39

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/74382.74384 What is a DOI?

ABSTRACT

In this paper, we discuss a control-flow transformation called loop folding, during the scheduling of register-transfer code for DSP-systems. Loop folding is functionally equivalent to data-path pipelining. An iterative loop-folding procedure, implemented in the CATHEDRAL II compiler, is presented. This technique may significantly improve the utilization of parallel hardware, available in a data path.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	E.G. Coffman Jr, "Computer and job scheduling theory", J. Wiley and Sons, New York, 1976.
	2	H. DeMan , J. Rabaey , J. Vanhoof , G. Goossens , P. Six , L. Claesen, CATHEDRAL II—a computer-aided synthesis system for digital signal processing VLSI systems, Computer-Aided Engineering Journal, v.5 n.2, p.55-66, April 1988
	3	S. Devadas, A.R. Newton, "Data path synthesis from behavioral descriptions : an algorithmic approach", Proc. IEEE {SCAS, pp, 398-401, Philadelphia, May 1987,
	4	A. Fettweis, "Realizability of digital filter networks", Arch. .f~r Elektr. Ubertr., Vol. 30, pp. 90-96, Feb. 1976.
	5	G. Goossens et al., "An efficient microcode-compiler for custom DSP-processors', Proc. IEEE ICCAD, pp. 24-27, Santa Clara, Nov. 1987.
	6	G. Goossens etal., "Optimization-based synthesis of multiprocessor chips for digital signal processing, with CATHB- DRAL Ir', Proc. fnternat. Workshop ore Log. and Arch. $ynth. for Sil. Compilers, Grenoble, May 1988.
	7	G. Goossens et al., "An efficient microcode-compiler for application-specific DSP-processors", Submitted }or publication, 1989.
	8	E.M. Girczyc, "Loop winding- a data flow approach to functional plpellning", Proe. IEEE I8CA$, pp. 382-385, Philadelphia, May 1987.
	9	J.K. Lenstra, A.H.G. Rinnooy Kan, "Sequencing and scheduling", in : M. O'h Eigeartaigh etal. (ed.), "Combinatorial optimization : annotated bibliographies", J. Wiley, Chlchester, 1985.
	10	B.M.Pangrle, D.D. Gajskl, "Design tools for intelligent silicon compilation", IEEE Tr. on CAD/ICAS, Vol. CAD-6, No. 6, pp. 1098-1112, Nov. 1987.
	11	N. Park, A.C. Parker, "SI~HWA : a software package for synthesis of pipelines from behavioral specifications", IEEE Tr. CAD/ICAS, Vol. CAD-7, No. 3, pp. 356-370, March 1988.
	12	P. G. Paulin , J. P. Knight, Force-directed scheduling in automatic data path synthesis, Proceedings of the 24th ACM/IEEE conference on Design automation, p.195-202, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37918]
	13	C. D. Polychronopoulos, Compiler Optimizations for Enhancing Parallelism and Their Impact on Architecture Design, IEEE Transactions on Computers, v.37 n.8, p.991-1004, August 1988 [doi>10.1109/12.2249]
	14	L. Rabiner, B. Gold, "Theory and applications o} digital signal procensiug", Prentice Hall, Englewood Cliffs, 1975.
	15	W. Rosenstiel, R. Camposano, "Synthesizing circuits from behavioural level specifications", Proc. 7th Internat. Syrup. CHDZ Tokyo, 1985.
	16	D. E. Thomas , E. M. Dirkes , R. A. Walker , J. V. Rajan , J. A. Nestor , R. L. Blackburn, The system architect's workbench, Proceedings of the 25th ACM/IEEE conference on Design automation, p.337-343, June 12-15, 1988, Atlantic City, New Jersey, United States
	17	H. Trickey, "FLAMEL : a high-level hardware compiler", IEEE Tr. CAD/ICAS, Vol. CAD-6, No. 2, pp. 259-269, March 1987.
	18	C.J. Tseng, D.P. Siewiorek, "Automated synthesis of data paths in digital systems", IEEE Tr. CAD/ICAS, pp. 379- 395, July 1986.
	19	J. Vanhoof et al., "A knowledge-based CAD system for synthesis of multi-processor digital signal processing chips", Proe. IFIP lntevnat. Conf. VLSI, pp. 41-56, Vancouver, Aug. 1987.

CITED BY 39

	Cheng-Tsung Hwang , Yu-Chin Hsu , Youn-Long Lin, Optimum and heuristic data path scheduling under resource constraints, Proceedings of the 27th ACM/IEEE conference on Design automation, p.65-70, June 24-27, 1990, Orlando, Florida, United States
	Rumi Zahir , Wolfgang Fichtner, Specification of timing constraints for controller synthesis, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
	Haigeng Wang , Nikil Dutt , Alexandru Nicolau, Harmonic scheduling of linear recurrences for digital filter design, Proceedings of the conference on European design automation, p.396-401, November 1992, Congress Centrum Hamburg, Hamburg, Germany
	D. Lanneer , F. Catthoor , G. Goossens , M. Pauwels , J. Van Meerbergen , H. De Man, Open-ended system for high-level synthesis of flexible signal processors, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
	Roni Potasman , Joseph Lis , Alexandru Nicolau , Daniel Gajski, Percolation based synthesis, Proceedings of the 27th ACM/IEEE conference on Design automation, p.444-449, June 24-27, 1990, Orlando, Florida, United States
	Steve Haynal , Forrest Brewer, Automata-Based Symbolic Scheduling for Looping DFGs, IEEE Transactions on Computers, v.50 n.3, p.250-267, March 2001
	Daehong Kim , Kiyoung Choi, Power-conscious high level synthesis using loop folding, Proceedings of the 34th annual conference on Design automation, p.441-445, June 09-13, 1997, Anaheim, California, United States
	Donald A. Lobo , Barry M. Pangrle, Generating pipelined datapaths using reduction techniques to shorten critical paths, Proceedings of the conference on European design automation, p.390-395, November 1992, Congress Centrum Hamburg, Hamburg, Germany
	Haigeng Wang , Nikil Dutt , Alexandru Nicolau , Kai-Yeung Sunny Siu, High-level synthesis of scalable architectures for IIR filters using multichip modules, Proceedings of the 30th international conference on Design automation, p.336-342, June 14-18, 1993, Dallas, Texas, United States
	P. R. Panda , F. Catthoor , N. D. Dutt , K. Danckaert , E. Brockmeyer , C. Kulkarni , A. Vandercappelle , P. G. Kjeldsberg, Data and memory optimization techniques for embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.2, p.149-206, April 2001
	Maria-Cristina V. Marinescu , Martin Rinard, High-level automatic pipelining for sequential circuits, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada
	M. Jacome , G. de Veciana , C. Akturan, Resource constrained dataflow retiming heuristics for VLIW ASIPs, Proceedings of the seventh international workshop on Hardware/software codesign, p.12-16, March 1999, Rome, Italy
	Smita Bakshi , Daniel D. Gajski, Performance-constrained hierarchical pipelining for behaviors, loops, and operations, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.1, p.1-25, Jan. 2001
	Y. G. DeCastelo-Vide-e-Souza , M. Potkonjak , Alice C. Parker, Optimal ILP-based approach for throughput optimization using simultaneous algorithm/architecture matching and retiming, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.113-118, June 12-16, 1995, San Francisco, California, United States
	B. Mesman , M. Strik , A. H. Timmer , J. L. van Meerbergen , J. A. G. Jess, A constraint driven approach to loop pipelining and register binding, Proceedings of the conference on Design, automation and test in Europe, p.377-383, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Miodrag Potkonjak , Mani Srivastava, Rephasing: a transformation technique for the manipulation of timing constraints, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.107-112, June 12-16, 1995, San Francisco, California, United States
	Daehong Kim , Dongwan Shin , Kiyoung Choi, Low power pipelining of linear systems: a common operand centric approach, Proceedings of the 2001 international symposium on Low power electronics and design, p.225-230, August 2001, Huntington Beach, California, United States
	Rainer Leupers, Code generation for embedded processors, Proceedings of the 13th international symposium on System synthesis, September 20-22, 2000, Madrid, Spain
	Cagdas Akturan , Margarida F. Jacome, FDRA: a software-pipelining algorithm for embedded VLIW processors, Proceedings of the 13th international symposium on System synthesis, September 20-22, 2000, Madrid, Spain
	Liang-Fang Chao , Andrea LaPaugh, Rotation scheduling: a loop pipelining algorithm, Proceedings of the 30th international conference on Design automation, p.566-572, June 14-18, 1993, Dallas, Texas, United States
	Maurizio Valle , Daniele Caviglia , Marco Cornero , Giovanni Nateri , Luciano Briozzo, A VHDL-based design methodology: the design experience of a high performance ASIC chip, Proceedings of the conference on European design automation, p.664-669, September 19-23, 1994, Grenoble, France
	Cagdas Akturan , Margarida F. Jacome, RS-FDRA: a register sensitive software pipelining algorithm for embedded VLIW processors, Proceedings of the ninth international symposium on Hardware/software codesign, p.67-72, April 2001, Copenhagen, Denmark
	Bart Mesman , Marino T. J. Strik , Adwin H. Timmer , Jef L. van Meerbergen , Jochen A. G. Jess, Constraint analysis for DSP code generation, Proceedings of the 10th international symposium on System synthesis, p.33-40, September 17-19, 1997, Antwerp, Belgium
	Gert Goossens , Johan Van Praet , Dirk Lanneer , Werner Geurts , Augusli Kifli , Clifford Liem , Pierre G. Paulin, Embedded software in real-time signal processing systems: design technologies, Readings in hardware/software co-design, Kluwer Academic Publishers, Norwell, MA, 2001
	Bart Mesman , Adwin H. Timmer , Jef L. van Meerbergen , Jochen A. G. Jess, Constraint analysis for DSP code generation, Readings in hardware/software co-design, Kluwer Academic Publishers, Norwell, MA, 2001
	Nelson Luiz Passos , Edwin Hsing-Mean Sha , Steven C. Bass, Loop pipelining for scheduling multi-dimensional systems via rotation, Proceedings of the 31st annual conference on Design automation, p.485-490, June 06-10, 1994, San Diego, California, United States
	Carlos Alba-Pinto , Bart Mesman , Jochen Jess, Constraint satisfaction for relative location assignment and scheduling, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	Reinaldo A. Bergamaschi , Raul Camposano , Michael Payer, Area and performance optimizations in path-based scheduling, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
	David J. Mallon , Peter B. Denyer, A new approach to pipeline optimisation, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
	Nelson Luiz Passos , Edwin Hsing-Mean Sha, Achieving Full Parallelism Using Multidimensional Retiming, IEEE Transactions on Parallel and Distributed Systems, v.7 n.11, p.1150-1163, November 1996
	Anatoly Prihozhy, Net Scheduling in High-Level Synthesis, IEEE Design & Test, v.13 n.1, p.26-35, March 1996
	Cagdas Akturan , Margarida F. Jacome, CALiBeR: a software pipelining algorithm for clustered embedded VLIW processors, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	Minjoong Rim , Rajiv Jain, Valid Transformations: A New Class of Loop Transformations for High-Level Synthesis and Pipelined Scheduling Applications, IEEE Transactions on Parallel and Distributed Systems, v.7 n.4, p.399-410, April 1996
	Karam S. Chatha , Ranga Vemuri, Hardware-Software partitioning and pipelined scheduling of transformative applications, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.10 n.3, p.193-208, June 2002
	Reinaldo A. Bergamaschi, Behavioral network graph: unifying the domains of high-level and logic synthesis, Proceedings of the 36th ACM/IEEE conference on Design automation, p.213-218, June 21-25, 1999, New Orleans, Louisiana, United States
	U. Holtmann , R. Ernst, Combining MBP-speculative computation and loop pipelining in high-level synthesis, Proceedings of the 1995 European conference on Design and Test, p.550, March 06-09, 1995
	M. Rahmouni , A. A. Jerraya, PPS: a pipeline path-based scheduler, Proceedings of the 1995 European conference on Design and Test, p.557, March 06-09, 1995
	Michael Sheliga , Nelson Luiz Passos , Edwin Hsing-Mean S' ha, Fully Parallel Hardware/Software Codesign for Multi-Dimensional DSP Applications, Proceedings of the 4th International Workshop on Hardware/Software Co-Design, p.18, March 18-20, 1996
	Sumit Gupta , Nikil Dutt , Rajesh Gupta , Alexandru Nicolau, Loop Shifting and Compaction for the High-Level Synthesis of Designs with Complex Control Flow, Proceedings of the conference on Design, automation and test in Europe, p.10114, February 16-20, 2004