Percolation based synthesis

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Percolation based synthesis

Full text

Pdf (733 KB)

Source

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

Orlando, Florida, United States

Pages: 444 - 449

Year of Publication: 1991

ISBN:0-89791-363-9

Authors

Roni Potasman	Dept. of Electrical and Computer Engineering, University of California, Irvine, CA
Joseph Lis	Information and Computer Science Department, University of California, Irvine, CA
Alexandru Nicolau	Information and Computer Science Department, University of California, Irvine, CA
Daniel Gajski	Information and Computer Science Department, University of California, Irvine, CA

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS : Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 9, Citation Count: 32

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/123186.123333 What is a DOI?

ABSTRACT

A new approach called Percolation Based Synthesis for the scheduling phase of High Level Synthesis (HLS) is presented. We discuss some new techniques (which are implemented in our tools) for compaction of flow graphs beyond basic blocks limits, which can produce order of magnitude speed ups versus serial execution. Our algorithm applies to programs with conditional jumps, loops and multicycle pipelined operations. In order to schedule under resource constraints we start by first finding the optimal schedule (without constraints) and then add heuristics to map the optimal schedule onto the given system. We argue that starting from an optimal schedule is one of the most important factors in scheduling because it offers the user flexibility to tune the heuristics and gives him a good bound for the resource constrained schedule. This scheduling algorithm is integrated with synthesis tool which uses VHDL as input description and produces a structural netlist of generic register-transfer components and a unit based control table as output. We show that our algorithm obtains better results than previously published algorithms.

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.

	AiNi88a	Alexander Aiken , Alexandru Nicolau, Perfect Pipelining: A New Loop Parallelization Technique, Proceedings of the 2nd European Symposium on Programming, p.221-235, March 21-24, 1988
	AiNi88b	A. Aiken , A. Nicolau, Optimal loop parallelization, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.308-317, June 20-24, 1988, Atlanta, Georgia, United States
	AlKe82	J. R. Allen and K. Kennedy. P FC: A program to convert Fortran to parallel form. Technical Report MASC TR 82-6, Rice University, 1982.
	EbNi89	Kemal Ebcioglu , Alexandru Nicolau, A global resource-constrained parallelization technique, Proceedings of the 3rd international conference on Supercomputing, p.154-163, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318807]
	GVDM89	G. Goossens , J. Vandewlle , H. De Man, Loop optimization in register-transfer scheduling for DSP-systems, Proceedings of the 26th ACM/IEEE conference on Design automation, p.826-831, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74384]
	KuWhKa85	S. Y. Kung , Thomas Kailath , Harper J. Whitehouse, VLSI and Modern Signal Processing, Prentice Hall Professional Technical Reference, 1984
	LiGa88	J. Lis and D. Gajski. Synthesis from VHDL. Proc. Intl. Conf. on Computer Design (ICCD), Nov. 1988, pp. 378-381.
	NeChMi84	Y. Neuvo, D. Chengyu and S. K. Mitra. Interpolated Finite impulse Response Filters. IEEE Trans. ASSP, Vol. ASSP-32, No. 3, June 1984.
	Ni85	A. Nicolau. Uniform Parallelism Exploitation in Ordinary Programs. Procs. of ICPP, August 1985.
	NPA88	A. Nicolau, K. Pingali and A. S. Aiken. Fine Grain Compilation for Pipelined Machines. Journal of Supercomputing, August 1988.
	PaGa86	B. M. PangHe and D. D. Gajski. States Synthesis and Connectivity Binding for Microa~chitecture compilation. Proc. of ICCAD ,Nov. 1986, pp. 210-213.
	PaKn89	P. G. Paulin and J. P. Knight. Force-Directed scheduling for the Behavioral Synthesis of ASIC's. IEEE Trans. on CAD, Vol. 8,No. 6, June 1989.
	PaPa88	N. Park and A. C. Parker. Sehwa: A Software Package for Synthesis of Pipelines from Behavioral Specifications. IEEE Trans. on CAD, Vol. 7,No. 3, Ma~ch 1988.
	TjFl70	G. S. Tja~ien and M. J. Fiynn. Detection and p~rallel execution of independent instructions. IEEE Trans. on Computers, Vol. 19, No. 10, October 1970.
	Tr87	H. Tfickey. Fl~mel: A High-Level Haxdwate Compiler. IEEE Trans. on CAD, Vol. CAD-6, No. 2, March 1987.

CITED BY 32

	K. Wakabayashi , H. Tanaka, Global scheduling independent of control dependencies based on condition vectors, Proceedings of the 29th ACM/IEEE conference on Design automation, p.112-115, June 08-12, 1992, Anaheim, California, United States
	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
	Alexandru Nicolau , Roni Potasmann, Incremental tree height reduction for high level synthesis, Proceedings of the 28th conference on ACM/IEEE design automation, p.770-774, June 17-22, 1991, San Francisco, California, United States
	Yuan-Long Jeang , Yu-Chin Hsu , Jhing-Fa Wang , Jau-Yien Lee, High throughput pipelined data path synthesis by conserving the regularity of nested loops, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.450-453, November 07-11, 1993, Santa Clara, California, United States
	Rolf Ernst , Jörg Henkel , Thomas Benner, Hardware-software cosynthesis for microcontrollers, Readings in hardware/software co-design, Kluwer Academic Publishers, Norwell, MA, 2001
	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
	A. Stoll , P. Duzy, High-level synthesis from VHDL with exact timing constraints, Proceedings of the 29th ACM/IEEE conference on Design automation, p.188-193, June 08-12, 1992, Anaheim, California, United States
	U. Prabhu , B. M. Prangrle, Superpipelined control and data path synthesis, Proceedings of the 29th ACM/IEEE conference on Design automation, p.638-643, June 08-12, 1992, Anaheim, California, United States
	David J. Kolson , Alexandru Nicolau , Nikil Dutt, Minimization of memory traffic in high-level synthesis, Proceedings of the 31st annual conference on Design automation, p.149-154, June 06-10, 1994, San Diego, California, United States
	Donald A. Lobo , Barry M. Pangrle, Redundant operator creation: a scheduling optimization technique, Proceedings of the 28th conference on ACM/IEEE design automation, p.775-778, June 17-22, 1991, San Francisco, California, United States
	Apostolos A. Kountouris , Christophe Wolinski, Efficient scheduling of conditional behaviors for high-level synthesis, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.3, p.380-412, July 2002
	Cheng-Tsung Hwang , Yu-Chin Hsu , Youn-Long Lin, Scheduling for functional pipelining and loop winding, Proceedings of the 28th conference on ACM/IEEE design automation, p.764-769, June 17-22, 1991, San Francisco, California, United States
	David J. Kolson , Alexandru Nicolau , Nikil Dutt, Integrating program transformations in the memory-based synthesis of image and video algorithms, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.27-30, November 06-10, 1994, San Jose, California, United States
	Tsing-Fa Lee , Allen C.-H. Wu , Daniel D. Gajski , Youn-Long Lin, An effective methodology for functional pipelining, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.230-233, November 1992, Santa Clara, California, United States
	Wolfgang Ecker, Semi-dynamic scheduling of synchronization-mechanisms, Proceedings of the conference on European design automation, p.374-379, September 18-22, 1995, Brighton, England
	Yaw Fann , Minjoong Rim , Rajiv Jain, Global scheduling for high-level synthesis applications, Proceedings of the 31st annual conference on Design automation, p.542-546, June 06-10, 1994, San Diego, California, United States
	Ramesh Karri , Alex Orailoğlu, ALPS: an algorithm for pipeline data path synthesis, Proceedings of the 24th annual international symposium on Microarchitecture, p.124-132, September 1991, Albuquerque, New Mexico, Puerto Rico
	Hans Achatz, Generating several solutions for the scheduling problem in high-level synthesis, Proceedings of the conference on European design automation, p.66-71, September 18-22, 1995, Brighton, England
	Luiz C. V. Dos Santos , M. J. M. Heijligers , C. A. J. Van Eijk , J. Van Eijnhoven , J. A. G. Jess, A code-motion pruning technique for global scheduling, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.1, p.1-38, Jan. 2000
	Chao Huang , Srivaths Ravi , Anand Raghunathan , Niraj K. Jha, High-level synthesis of distributed logic-memory architectures, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.564-571, November 10-14, 2002, 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
	Christoph Jäschke , Rainer Laur, Resource contrained modulo scheduling with global resource sharing, Proceedings of the 11th international symposium on System synthesis, p.60-65, December 02-04, 1998, Hsinchu, Taiwan, China
	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
	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
	Seda Ogrenci Memik , Ryan Kastner , Elaheh Bozorgzadeh , Majid Sarrafzadeh, A scheduling algorithm for optimization and early planning in high-level synthesis, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.1, p.33-57, January 2005
	Vijay Raghunathan , Srivaths Ravi , Anand Raghunathan , Ganesh Lakshminarayana, Transient power management through high level synthesis, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	Rolf Ernst , Jorg Henkel , Thomas Benner, Hardware-Software Cosynthesis for Microcontrollers, IEEE Design & Test, v.10 n.4, p.64-75, October 1993
	Christoph Jäschke , Friedrich Beckmann , Rainer Laur, Time constrained modulo scheduling with global resource sharing, Proceedings of the conference on Design, automation and test in Europe, p.44-es, January 1999, Munich, Germany
	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
	Wei Zhao , C. A. Papachristou, An evolution programming approach on multiple behaviors for the design of application specific programmable processors, Proceedings of the 1996 European conference on Design and Test, p.144, March 11-14, 1996
	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