Power optimization using divide-and-conquer techniques for minimization of the number of operations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Power optimization using divide-and-conquer techniques for minimization of the number of operations

Full text

Pdf (278 KB)

Source

ACM Transactions on Design Automation of Electronic Systems (TODAES) archive
Volume 4 , Issue 4 (October 1999) table of contents

Pages: 405 - 429

Year of Publication: 1999

ISSN:1084-4309

Authors

Inki Hong	Univ. of California, Los Angeles
Miodrag Potkonjak	Univ. of California, Los Angeles
Ramesh Karri	Univ. Massachusetts at Amherst, Amherst

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 90, Citation Count: 0

Additional Information:

abstract references 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/323480.323489 What is a DOI?

ABSTRACT

We introduce an approach for power optimization using a set of compilation and architectural techniques. The key technical innovation is a novel divide-and-conquer compilation technique to minimize the number of operations for general computations. Our technique optimizes not only a significantly wider set of computations than the previously published techniques, but also outperforms (or performs at least as well as other techniques) on all examples. Along the architectural dimension, we investigate coordinated impact of compilation techniques on the number of processors which provide optimal trade-off between cost and power. We demonstrate that proper compilation techniques can significantly reduce power with bounded hardware cost. The effectiveness of all techniques and algorithms is documented on numerous real-life designs.

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	David F. Bacon , Susan L. Graham , Oliver J. Sharp, Compiler transformations for high-performance computing, ACM Computing Surveys (CSUR), v.26 n.4, p.345-420, Dec. 1994 [doi>10.1145/197405.197406]
	2	BANERJEE, U., EIGENMANN, R., NICOLAU, A., AND PADUA, D.A. 1993. Automatic program parallelization. Proc. IEEE 81, 2 (Feb.), 211-243.
	3	BHATTACHARYYA, S. S., BUCK, J. T., HA, S., AND LEE, E.A. 1993. A scheduling framework for minimizing memory requirements of multirate signal processing algorithms expressed as dataflow graphs. In VLSI Signal Processing VI IEEE Press, Piscataway, NJ, 188-196.
	4	CHANDRAKASAN, A. P., SHENG, S., AND BRODERSEN, R. W. 1992. Low-power CMOS digital design. IEEE J. Solid-State Circuits 27, 4 (Apr. 1992), 473-484.
	5	CHANDRAKASAN, A. P., SRIVASTAVA, M., AND BRODERSEN, R.W. 1994. Energy efficient programmable computation. In Proceedings of the 7th International Conference on VLSI Design 261-264.
	6	CHATTERJEE, A. AND ROY, R. K. 1994. Synthesis of low power DSP circuits using activity metrics. In Proceedings of the 7th International Conference on VLSI Design 265-270.
	7	CHANDRAKASAN, A. P., POTKONJAK, M., MEHRA, R., RABAEY, J., AND BRODERSEN, R. W. 1995. Optimizing power using transformations. IEEE Trans. Comput.-Aided Des. 14, 1 (1995), 13-32.
	8	Anantha Chandrakasan , Isabel Yang , Carlin Vieri , Dimitri Antoniadis, Design considerations and tools for low-voltage digital system design, Proceedings of the 33rd annual conference on Design automation, p.113-118, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240540]
	9	Sujit Dey , Miodrag Potkonjak , Steven G. Rothweiler, Performance optimization of sequential circuits by eliminating retiming bottlenecks, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.504-509, November 1992, Santa Clara, California, United States
	10	EL-KAREH, B., CHEN, B., AND STANLEY, T. 1995. Silicon on insulator--an emerging highleverage technology. IEEE Trans. Compon., Packaging, Manuf. Technol. 18, 1, 187-194.
	11	G. C. Fox , J. G. Koller, Code generation by a generalized neural network: general principles and elementary examples, Journal of Parallel and Distributed Computing, v.6 n.2, p.388-410, April 1989 [doi>10.1016/0743-7315(89)90066-X]
	12	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	13	Laurence Goodby , Alex Orailoglu , Paul M. Chau, Microarchitectural Synthesis of Performance-Constrained, Low-Power VLSI Designs, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.323-326, October 10-12, 1994
	14	GUERRA, L., POTKONJAK, M., AND RABAEY, J. 1994. System-level design guidance using algorithm properties. In Proceedings of the IEEE Workshop on VLSI Signal Processing VII IEEE Press, Piscataway, NJ, 73-82.
	15	HOANG, P. D. AND RABAEY, J. M. 1993. Scheduling of DSP programs onto multiprocessors for maximum throughput. IEEE Trans. Signal Process. 41, 6, 2225-2235.
	16	HUANG, S. H. AND RABAEY, J. M. 1994. Maximizing the throughput of high performance DSP applications using behavioral transformations. In EDAC '94 (EDAC '94, 1994) 25-30.
	17	IPPOSHI, T., IWAMATSU, T., YAMAGUCHI, Y., UEDA, K., MORINAKA, H., MASHIKO, K., INOUE, Y., AND Hmno, T. 1995. An advanced 0.5 mu m CMOS/SOI technology for practical ultrahigh-speed and low-power circuits. In Proceedings of the International Conference on SOI 46-47.
	18	Zia Iqbal , Miodrag Potkonjak , Sujit Dey , Alice Parker, Critical path minimization using retiming and algebraic speed-up, Proceedings of the 30th international conference on Design automation, p.573-577, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165046]
	19	KAM, J. B. AND ULLMAN, J. D. 1997. Monotone data flow analysis frameworks. Acta Inf. 7, 305-317.
	20	KIRKPATRICK, S., GELATT, C. D., JR., AND VECCHI, M. P. 1983. Optimization by simulated annealing. Science 220, 4598 (May), 671-680.
	21	David C. Ku , Giovanni De Micheli, High level synthesis of ASICs under timing and synchronization constraints, Kluwer Academic Publishers, Norwell, MA, 1992
	22	LANDMAN, P. E. AND RABAEY, g. 1996. Activity-sensitive architectural power analysis. IEEE Trans. Comput.-Aided Des. 15, 6, 571-587.
	23	LEE, E. AND MESSERSCHMITT, D. 1987. Synchronous data flow. Proc. IEEE 75, 9, 1235-1245.
	24	LEE, E. A. AND PARKS, T. M. 1995. Dataflow process networks. Proc. IEEE 83, 5 (May), 773-801.
	25	Mike Tien-Chien Lee , Masahiro Fujita , Vivek Tiwari , Sharad Malik, Power analysis and minimization techniques for embedded DSP software, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.1, p.123-135, March 1997 [doi>10.1109/92.555992]
	26	LEISERSON, C. E. AND SAXE, J. B. 1991. Retiming synchronous circuitry. Algorithmica 6, 1, 5-35.
	27	Henry Massalin, Superoptimizer: a look at the smallest program, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.122-126, October 1987, Palo Alto, California, United States
	28	Renu Mehra , Jan Rabaey, Exploiting regularity for low-power design, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.166-172, November 10-14, 1996, San Jose, California, United States
	29	Keshab K. Parhi , David G. Messerschmitt, Static Rate-Optimal Scheduling of Iterative Data-Flow Programs Via Optimum Unfolding, IEEE Transactions on Computers, v.40 n.2, p.178-195, February 1991 [doi>10.1109/12.73588]
	30	Keshab K. Parhi, High-level algorithm and architecture transformations for DSP synthesis, Journal of VLSI Signal Processing Systems, v.9 n.1-2, p.121-143, Jan. 1995 [doi>10.1007/BF02406474]
	31	Miodrag Potkonjak , Jan Rabaey, Maximally fast and arbitrarily fast implementation of linear computations, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.304-308, November 1992, Santa Clara, California, United States
	32	POTKONJAK, M., SRIVASTAVA, M., AND CHANDRAKASAN, A. P. 1996. A. P. Multiple constant multiplications: efficient and versatile framework and algorithms for exploring common subexpression elimination. IEEE Trans. Comput.-Aided Des. 15, 2, 151-165.
	33	J. M. Rabaey , C. Chu , P. Hoang , M. Potkonjak, Fast Prototyping of Datapath-Intensive Architectures, IEEE Design & Test, v.8 n.2, p.40-51, April 1991 [doi>10.1109/54.82037]
	34	Anand Raghunathan , Niraj K. Jha, Behavioral Synthesis for low Power, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.318-322, October 10-12, 1994
	35	Ron Schneiderman, Wireless Personal Communications: The Future of Talk, IEEE Press, Piscataway, NJ, 1994
	36	Michael Sheliga , Edwin Hsing Mean Sha, Global node reduction of linear systems using ratio analysis, Proceedings of the 7th international symposium on High-level synthesis, p.140-145, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
	37	SINGH, D., RABAEY, J., PEDRAM, M., CATTHOOR, F., RAJGOPAL, S., SEHGAL, N., AND MOZDZEN, T. 1995. Power conscious CAD tools and methodologies: A perspective. Proc. IEEE 83, 4 (Apr.), 570-594.
	38	SRIVASTAVA, M. B. AND POTKONJAK, M. 1994. Transforming linear systems for joint latency and throughput optimization. In EDAC '94 (EDAC '94, 1994) 267-271.
	39	Mani Srivastava , Miodrag Potkonjak, Power optimization in programmable processors and ASIC implementations of linear systems: transformation-based approach, Proceedings of the 33rd annual conference on Design automation, p.343-348, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240583]
	40	Andrew S. Tanenbaum , Hans van Staveren , Johan W. Stevenson, Using Peephole Optimization on Intermediate Code, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.21-36, Jan. 1982 [doi>10.1145/357153.357155]
	41	TARJAN, R. E. 1972. Depth first search and linear graph algorithms. SIAM J. Comput. 1, 2 (1972), 146-160.
	42	Vivek Tiwari , Sharad Malik , Andrew Wolfe, Power analysis of embedded software: a first step towards software power minimization, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.2 n.4, p.437-445, Dec. 1994 [doi>10.1109/92.335012]
	43	Proceedings of the 1995 conference on Asia Pacific design automation (CD-ROM), August 1995
	44	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
	45	WALKER, R. AND CAMPOSANO, R. 1991. A Survey of High-Level Synthesis Systems. Kluwer Academic Publishers, Hingham, MA.
	46	Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]
	47	D. Whitfield , M. L. Soffa, An approach to ordering optimizing transformations, ACM SIGPLAN Notices, v.25 n.3, p.137-146, Mar. 1990
	48	M. E. Wolf , M. S. Lam, A Loop Transformation Theory and an Algorithm to Maximize Parallelism, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.452-471, October 1991 [doi>10.1109/71.97902]