Force-directed scheduling in automatic data path synthesis

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Force-directed scheduling in automatic data path synthesis

Full text

Pdf (946 KB)

Source

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

Miami Beach, Florida, United States

Pages: 195 - 202

Year of Publication: 1987

ISBN:0-8186-0781-5

Authors

P. G. Paulin	Dept. 5L40, Bell-Northern Research, P.O.Box 3511, Stn C, Ottawa, ONT. K1Y 4H7
J. P. Knight	Carleton University, Colonel By Dr, Ottawa, ONT. K1S 5B6

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 55, Citation Count: 46

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

ABSTRACT

The HAL system performs data path synthesis using a new scheduling algorithm that is part of an interdependent scheduling and allocation scheme. This scheme uses an estimate of the hardware allocation to guide and optimize the scheduling subtask. The allocation information includes the number, type, speed and cost of hardware modules as well as the associated multiplexer and interconnect costs. The iterative force-directed scheduling algorithm attempts to balance the distribution of operations that make use of the same hardware resources: Every feasible control step assignment is evaluated at each iteration, for all operations. The associated side-effects on all the predecessor and successor operations are taken into account. All the decisions are global. The algorithm has O(n8 complexity. We review and compare existing scheduling techniques. Moderate and difficult examples are used to illustrate the effectiveness of the approach.

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	O.D. Gajski, N.D. Dutt and B.M. Pangrle, "Silicon Compilation (Tutorial)*, Proceedings of the TEEE 1986 Custom Integrated Circu\|ts Conference, Rochester NY, May 1986, pp. 102-110.
	2	Alice C. Parker , Jorge T. Pizarro , Mitch Mlinar, MAHA: a program for datapath synthesis, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.461-466, July 1986, Las Vegas, Nevada, United States
	3	Nohbyung Park , Alice Parker, Synthesis of optimal clocking schemes, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.489-495, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317933]
	4	E.F. Girczyc and d.P. Knight, "An ADA to Standard Cell Hardware Compiler Based on Graph Grammars and Scheduling", Proc. of the IEEE International Conference on Computer Design (ICCD), October 1984, pp. 726-731.
	5	P. G. Paulin , J. P. Knight , E. F. Girczyc, HAL: a multi-paradigm approach to automatic data path synthesis, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.263-270, July 1986, Las Vegas, Nevada, United States
	6	P.G. Paulin, d.P. Knight, "Extended Design-Space Exploration in Automatic Oata Path Synthesis", Proceedings of the 1986 Canadian Conference on VLSI, October 1986, pp. 221-226.
	7	Timothy Blackman , Jeffrey Fox , Christopher Rosebrugh, The Silc silicon compiler: language and features, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.232-237, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317864]
	8	C. Tseng, D.P. Siewiorek, "Automated Synthesis of Data Paths in Digital Systems", IEEE Transactions on CAD, duly 1986, pp. 379-395.
	9	S. Davidson eta\|, MSome Experiments in Local Microcode Compaction for Horizontal Machines", IEEE Transactions on Computers, duly 1981, pp. 460-477.
	10	Peter Marwedel, A new synthesis for the MIMOLA software system, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.271-277, July 1986, Las Vegas, Nevada, United States
	11	S. Y. Kung , Thomas Kailath , Harper J. Whitehouse, VLSI and Modern Signal Processing, Prentice Hall Professional Technical Reference, 1984
	12	d, Nestor, D.E. Thomas, "Behavioral Synthes~s with Interfaces", Proceedings of the IEEE ICCAD-86 (International Conference on CAD), November t986, pp. 112-115.
	13	B.M. Pangrle, O.O. GaJskl, "State Synthesis and Connectivity Binding for Microarchttecture Compilation", Proceedings of the IEEE ICCAD-86, November lg86, pp. 210-213.
	14	Michael C. McFarland, Using bottom-up design techniques in the synthesis of digital hardware from abstract behavioral descriptions, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.474-480, July 1986, Las Vegas, Nevada, United States
	15	Nohbyung Park , Alice Parker, Sehwa: a program for synthesis of pipelines, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.454-460, July 1986, Las Vegas, Nevada, United States
	16	P.G. Paulin, d.P. Knight, "Scheduling and Allocation for Plpellned ASICs", Submitted to the TEEE International Conference on Computer Design (ICCD "87). Awaiting acceptance,
	17	H.Trtckey, "Flamel: A High-Level Hardware Compiler", IEEE Transactions on CAD, March 1987, pp.259-269.

CITED BY 46

	F. Monteiro , B. Rouzeyre , G. Sagnes, High level synthesis: a data path partitioning method dedicated to speed enhancement, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
	Shih-Hsu Huang , Chun-Hua Cheng, An ILP Approach to the Simultaneous Application of Operation Scheduling and Power Management, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.1, p.375-382, January 2008
	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
	Gaetano Borriello , Ewald Detjens, High-level synthesis: current status and future directions, Proceedings of the 25th ACM/IEEE conference on Design automation, p.477-482, June 12-15, 1988, Atlantic City, New Jersey, United States
	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
	Biswadip Mitra , Preeti Panda , P. Pal Chaudhuri, Estimating the Complexity of Synthesized Designs from FSM Specifications, IEEE Design & Test, v.10 n.1, p.30-35, January 1993
	Albert E. Casavant, MIST—a design aid for programmable pipelined processors, Proceedings of the 31st annual conference on Design automation, p.532-536, June 06-10, 1994, San Diego, California, United States
	Jayanta Roy , Nand Kumar , Rajiv Dutta , Ranga Vemuri, DSS: A Distributed High-Level Synthesis System, IEEE Design & Test, v.9 n.2, p.18-32, April 1992
	Abdelhakim Safir , Bertrand Zavidovique, Towards a global solution to high level synthesis problems, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
	M. Balakrishnan , P. Marwedel, Integrated scheduling and binding: a synthesis approach for design space exploration, Proceedings of the 26th ACM/IEEE conference on Design automation, p.68-74, June 25-28, 1989, Las Vegas, Nevada, United States
	In-Cheol Park , Chong-Min Kyung, Fast and near optimal scheduling in automatic data path synthesis, Proceedings of the 28th conference on ACM/IEEE design automation, p.680-685, June 17-22, 1991, San Francisco, California, United States
	Nand Kumar , Srinivas Katkoori , Leo Rader , Ranga Vemuri, Profile-Driven Behavioral Synthesis for Low-Power VLSI Systems, IEEE Design & Test, v.12 n.3, p.70-84, September 1995
	W. F. J. Verhaegh , E. H. L. Aarts , J. H. M. Korst , P. E. R. Lippens, Improved force-directed scheduling, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
	Douglas M. Grant , Peter B. Denyer, Memory, control and communications synthesis for scheduled algorithms, Proceedings of the 27th ACM/IEEE conference on Design automation, p.162-167, June 24-27, 1990, Orlando, Florida, United States
	Christos Papachristou , Haidar Harmanani , Mehrdad Nourani, An approach for redesigning in data path synthesis, Proceedings of the 30th international conference on Design automation, p.419-423, June 14-18, 1993, Dallas, Texas, United States
	W. F. J. Verhaegh , P. E. R. Lippens , E. H. L. Aarts , J. H. M. Korst , A. van der Werf , J. L. van Meerbergen, Efficiency improvements for force-directed scheduling, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.286-291, November 1992, Santa Clara, California, United States
	A. H. Timmer , J. A. G. Jess, Exact scheduling strategies based on bipartite graph matching, Proceedings of the 1995 European conference on Design and Test, p.42, March 06-09, 1995
	Ranga Vemuri , Nand Kumar , RaghVutukuruu , Prasad Subba Rao , Praveen Sinha , Ning Ren , Paddy Mamtora , Ram Mandayam , Ram Vemuri , Jayanta Roy, An Integrated Multicomponent Synthesis Environment for MCMs, Computer, v.26 n.4, p.62-74, April 1993
	N.-S. Woo , H. Shin, A technology-adaptive allocation of functional units and connections, Proceedings of the 26th ACM/IEEE conference on Design automation, p.602-605, June 25-28, 1989, Las Vegas, Nevada, United States
	P. Gutberlet , H. Krämer , W. Rosenstiel, CASCH: a scheduling algorithm for "high level"-synthesis, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
	Forrest Brewer , Barry Pangrle , Andrew Seawright, Interconnection synthesis with geometric constraints, Proceedings of the 23rd annual workshop and symposium on Microprogramming and microarchitecture, p.158-165, November 27-29, 1990, Orlando, Florida, United States
	Gang Wang , Wenrui Gong , Brian DeRenzi , Ryan Kastner, Design space exploration using time and resource duality with the ant colony optimization, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	Doug Baldwin , Hamilton Hitchings, Constraint sensitive scheduling in RASP, ACM SIGDA Newsletter, v.21 n.2, p.50-59, Oct. 1991
	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
	Shuqing Zhao , Daniel D. Gajski, Defining an Enhanced RTL Semantics, Proceedings of the conference on Design, Automation and Test in Europe, p.548-553, March 07-11, 2005
	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
	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
	Viktor S. Lapinskii , Margarida F. Jacome , Gustavo A. de Veciana, High-quality operation binding for clustered VLIW datapaths, Proceedings of the 38th conference on Design automation, p.702-707, June 2001, Las Vegas, Nevada, United States
	Mario Schölzel, Interactive presentation: Time-constrained clustering for DSE of clustered VLIW-ASP, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
	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
	Rehab F. Abdel-Kader, Resource-constrained loop scheduling in high-level synthesis, Proceedings of the 43rd annual southeast regional conference, March 18-20, 2005, Kennesaw, Georgia
	Ronald Scrofano , Ling Zhuo , Viktor K. Prasanna, Area-efficient arithmetic expression evaluation using deeply pipelined floating-point cores, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.16 n.2, p.167-176, February 2008
	Gang Wang , Wenrui Gong , Ryan Kastner, Instruction scheduling using MAX-MIN ant system optimization, Proceedings of the 15th ACM Great Lakes symposium on VLSI, April 17-19, 2005, Chicago, Illinois, USA
	Gang Wang , Wenrui Gong , Brian Derenzi , Ryan Kastner, Exploring time/resource trade-offs by solving dual scheduling problems with the ant colony optimization, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.12 n.4, p.46-es, September 2007
	H. Harmanani , C. Papachristou , S. Chiu , M. Nourani, SYNTEST: an environment for system-level design for test, Proceedings of the conference on European design automation, p.402-407, November 1992, Congress Centrum Hamburg, Hamburg, Germany
	Nikil D. Dutt , Daniel D. Gajski, Design Synthesis and Silicon Compilation, IEEE Design & Test, v.7 n.6, p.8-23, November 1990
	Rahul Nagpal , Y. N. Srikant, Integrated temporal and spatial scheduling for extended operand clustered VLIW processors, Proceedings of the 1st conference on Computing frontiers, April 14-16, 2004, Ischia, Italy
	Katherine E. Coons , Xia Chen , Doug Burger , Kathryn S. McKinley , Sundeep K. Kushwaha, A spatial path scheduling algorithm for EDGE architectures, ACM SIGPLAN Notices, v.41 n.11, November 2006
	P. G. Paulin , J. P. Knight, Scheduling and binding algorithms for high-level synthesis, Proceedings of the 26th ACM/IEEE conference on Design automation, p.1-6, June 25-28, 1989, Las Vegas, Nevada, United States
	Katherine E. Coons , Behnam Robatmili , Matthew E. Taylor , Bertrand A. Maher , Doug Burger , Kathryn S. McKinley, Feature selection and policy optimization for distributed instruction placement using reinforcement learning, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada
	R. Camposano, From Behavior to Structure: High-Level Synthesis, IEEE Design & Test, v.7 n.5, p.8-19, September 1990
	Satish Pillai , Margarida F. Jacome, Compiler-Directed ILP Extraction for Clustered VLIW/EPIC Machines: Predication, Speculation and Modulo Scheduling, Proceedings of the conference on Design, Automation and Test in Europe, p.10422, March 03-07, 2003
	Michael C. McFarland , Alice C. Parker , Raul Camposano, Tutorial on high-level synthesis, Proceedings of the 25th ACM/IEEE conference on Design automation, p.330-336, June 12-15, 1988, Atlantic City, New Jersey, United States
	Christos A. Papachristou , Scott Chiu , Haidar Harmanani, A data path synthesis method for self-testable designs, Proceedings of the 28th conference on ACM/IEEE design automation, p.378-384, June 17-22, 1991, San Francisco, California, United States
	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
	Viktor S. Lapinskii , Margarida F. Jacome , Gustavo A. De Veciana, Cluster assignment for high-performance embedded VLIW processors, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.3, p.430-454, July 2002