Heuristic tradeoffs between latency and energy consumption in register assignment

ABSTRACT

One of the challenging tasks in code generation for embedded systems is register allocation and assignment, wherein one decides on the placement and lifetimes of variables in registers. When there are more live variables than registers, some variables need to be spilled to memory and restored later. In this paper we propose a policy that minimizes the number of spills — which is critical for portable embedded systems since it leads to a decrease in energy consumption. We argue however, that schedules with a minimal number of spills do not necessarily have minimum latency. Accordingly, we propose a class of policies that explore tradeoffs between assignments leading to schedules with low latency versus those leading to low energy consumption and show how to tune them to particular datapath characteristics. Based on experimental results we propose a criterion to select a register assignment policy that for 99% of the cases we considered minimizes both latency and energy consumption associated with spills to memory.

REFERENCES

• 1: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 2: G. Chaitin et al. Register allocation via coloring. Computer Languages, 6:47-57, Jan. 1981.
• 3: P. Paulin et al. FlexWare: A flexible firmware development environment for embedded systems. In Code Generation for Embedded Processors, pages 67-84. KAP, 1995.
• 4: S. Rixner et. al. Register organization for media processing. In 6th International Symposium on High-Performance Computer Architecture, 2000.
• 5: Silvina Hanono , Srinivas Devadas, Instruction selection, resource allocation, and scheduling in the AVIV retargetable code generator, Proceedings of the 35th annual conference on Design automation, p.510-515, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277184]
• 6: Margarida F. Jacome , Gustavo de Veciana, Lower bound on latency for VLIW ASIP datapaths, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.261-269, November 07-11, 1999, San Jose, California, United States
• 7: David J. Kolson , Alexandru Nicolau , Nikil Dutt , Ken Kennedy, Optimal register assignment to loops for embedded code generation, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.2, p.251-279, April 1996 [doi>10.1145/233539.233542]
• 8: F. J. Kurdahi , A. C. Parker, REAL: a program for REgister ALlocation, Proceedings of the 24th ACM/IEEE conference on Design automation, p.210-215, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37920]
• 9: Clifford Liem, Retargetable Compilers for Embedded Core Processors: Methods and Experience in Industrial Applications, Kluwer Academic Publishers, Norwell, MA, 1997
• 10: Peter Marwedel , Gert Goossens, Code Generation for Embedded Processors, Kluwer Academic Publishers, Norwell, MA, 1995
• 11: B. R. Rau, V. Kathail, and S. Aditya. Machine-description driven compilers for epic processors. Technical report, Hewlett-Packard Laboratories, 1998.
• 12: Philip Sweany , Steven Beaty, Post-compaction register assignment in a retargetable compiler, Proceedings of the 23rd annual workshop and symposium on Microprogramming and microarchitecture, p.107-116, November 27-29, 1990, Orlando, Florida, United States

INDEX TERMS

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

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

General Terms:
Design, Management