A new viewpoint on code generation for directed acyclic graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A new viewpoint on code generation for directed acyclic graphs

Full text

Pdf (662 KB)

Source

ACM Transactions on Design Automation of Electronic Systems (TODAES) archive
Volume 3 , Issue 1 (January 1998) table of contents

Pages: 51 - 75

Year of Publication: 1998

ISSN:1084-4309

Authors

S. Liao	Synopsys, Inc.
K. Keutzer	Synopsys, Inc.
S. Tjiang	Synopsys, Inc.
S. Devadas	Massachusetts Institute of Technology

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 46, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

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

ABSTRACT

We present a new viewpoint on code generation for directed acyclic graphs (DAGs). Our formulation is based on binate covering, the problem of satisfying, with minimum cost, a set of disjunctive clauses, and can take into account commutativity of operators and of the machine model. An important contribution of this work is a set of necessary and sufficient conditions for a valid schedule to be derived, based on the notion of worms and worm-partitions. This set of conditions can be compactly expressed with clauses that relate scheduling to code selection. For the case of one-register machines, we can derive clauses that lead to generation of optimal code for the DAG. Recent advances in exact binate covering algorithms allows us to use this strategy to generate optimal code for large basic blocks. The optimal code generated by our algorithm results in significant reductions in overall code size.

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	A. V. Aho , S. C. Johnson , J. D. Ullman, Code Generation for Expressions with Common Subexpressions, Journal of the ACM (JACM), v.24 n.1, p.146-160, Jan. 1977 [doi>10.1145/321992.322001]
	2	BRAYTON, R. K. AND SOMENZI, F. 1989. Boolean relations and the incomplete specification of logic networks. In Proceedings of the 1989 International Conference on Computer-Aided Design (Santa Clara, CA, Nov. 1989), 316-319.
	3	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	4	Olivier Coudert, On solving covering problems, Proceedings of the 33rd annual conference on Design automation, p.197-202, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240555]
	5	Olivier Coudert , Jean Chritophe Madre, New ideas for solving covering problems, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.641-646, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217603]
	6	GIMPEL, J. 1967. The minimization of TANT networks. IEEE Trans. Electr. Comput. EC-16, 1 (Feb.), 18-38.
	7	GRASSELLI, A. AND LUCCIO, F. 1965. A method for minimizing the number of internal states in incompletely specified machines. IEEE Trans. Electr. Comput. EC-14, 3 (June), 350-359.
	8	Stan Yi-Huang Liao , Srinivas Devadas, Code generation and optimization for embedded digital signal processors, 1996
	9	Stan Liao , Srinivas Devadas, Solving covering problems using LPR-based lower bounds, Proceedings of the 34th annual conference on Design automation, p.117-120, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266046]
	10	Stan Liao , Srinivas Devadas , Kurt Keutzer , Steven Tjiang , Albert Wang, Storage assignment to decrease code size, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.235-253, May 1996 [doi>10.1145/229542.229543]
	11	Keith Paton, An algorithm for finding a fundamental set of cycles of a graph, Communications of the ACM, v.12 n.9, p.514-518, Sept. 1969 [doi>10.1145/363219.363232]
	12	Richard L. Rudell , Alberto Sangiovanni-Vincentelli, Logic synthesis for vlsi design, 1989
	13	TEXAS INSTRUMENTS. 1993. TMS320C2x User's Guide. Revision C.
	14	J. van Leeuwen, Graph algorithms, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	15	Robert Wilson , Robert French , Christopher Wilson , Saman Amarasinghe , Jennifer Anderson , Steve Tjiang , Shih Liao , Chau Tseng , Mary Hall , Monica Lam , John Hennessy, The SUIF Compiler System: a Parallelizing and Optimizing Research Compiler, Stanford University, Stanford, CA, 1994
	16	ZIVOJNOVIC, V., VELARDE, J. M., AND SCHLAGER, C. 1994. DSPstone" A DSP-oriented benchmarking methodology. In Proceedings of the Fifth International Conference on Signal Processing Applications and Technology, Miller Freeman, San Francisco, CA.

CITED BY 2

	Praveen K. Murthy , Shuvra S. Bhattacharyya, A Buffer Merging Technique for Reducing Memory Requirements of Synchronous Dataflow Specifications, Proceedings of the 12th international symposium on System synthesis, p.78, November 01-04, 1999
	David Ryan Koes , Seth Copen Goldstein, Near-optimal instruction selection on dags, Proceedings of the sixth annual IEEE/ACM international symposium on Code generation and optimization, April 05-09, 2008, Boston, MA, USA