Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We present a technique for task response time improvement based on the concept of code motion from the software domain. Relaxed Operation Motion (ROM) is a simple yet powerful approach for performing safe and useful operation motion from heavily executed portions of a design task to less visited segments. We introduce here our algorithm, how it differs from other code motion approaches, and its application to the embedded systems domain. Results of our investigation indicate that cost-guided operation motion has the potential to improve task response time significantly.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Felice Balarin , Massimiliano Chiodo , Paolo Giusto , Harry Hsieh , Attila Jurecska , Luciano Lavagno , Claudio Passerone , Alberto Sangiovanni-Vincentelli , Ellen Sentovich , Kei Suzuki , Bassam Tabbara, Hardware-software co-design of embedded systems: the POLIS approach, Kluwer Academic Publishers, Norwell, MA, 1997
• 3: Walid Dabbous , Sean O'Malley , Claude Castelluccia, Generating efficient protocol code from an abstract specification, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.60-72, August 28-30, 1996, Palo Alto, California, United States [doi>10.1145/248156.248163]
• 4: Max Hailperin, Cost-optimal code motion, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1297-1322, Nov. 1998 [doi>10.1145/295656.295664]
• 5: Kam, J.B.; Ullman, J.D., "Monotone Data Flow Analysis Frameworks", Acta Informatica, 1977, pp. 305-307.
• 6: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, ACM SIGPLAN Notices, v.27 n.7, p.224-234, July 1992 [doi>10.1145/143103.143136]
• 7: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Optimal code motion: theory and practice, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1117-1155, July 1994 [doi>10.1145/183432.183443]
• 8: Microsoft Research: Decision Theory & Adaptive Systems Group at: http://research.microsoft.com/msbn/default.htm
• 9: E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
• 10: Bassam Tabbara , Alberto L. Sangiovanni-Vincentelli, Function/architecture optimization and co-design of embedded systems, 2000
• 11: Tabbara, B.; Tabbara, A.; Sangiovanni-Vincentelli, A., "Hardware and Software Representation, Optimization, and Co-synthesis for Embedded Systems", Technical Report UCB/ERL MOO/7, January 2000.
• 12: Kishar Shridharbhai Trivedi, Probability and Statistics with Reliability, Queuing and Computer Science Applications, Prentice Hall PTR, Upper Saddle River, NJ, 1982
• 13: Tim A. Wagner , Vance Maverick , Susan L. Graham , Michael A. Harrison, Accurate static estimators for program optimization, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.85-96, June 20-24, 1994, Orlando, Florida, United States [doi>10.1145/178243.178251]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING

General Terms:
Algorithms, Design, Management

Keywords:
(cost-based) code motion, optimization, response time