Code placement techniques for cache miss rate reduction

ABSTRACT

In the design of embedded systems with cache memories, it is important to minimize the cache miss rates to reduce power consumption of the systems as well as improve the performance. In this article, we propose two code placement methods ( a simplified method and a refined one) to reduce miss rates of instruction caches. We first define a simplified code placement problem without an attempt to minimize the code size. The problem is formulated as an integer linear programming (ILP) problem, by which an optimal placement can be found. Experimental results show that the simplified method reduces cache misses by an average of 30% (max. 77%). However, the code size obtained by the simplified method tends to be large, which inevitably leads to a larger memory size. In order to overcome this limitation, we further propose a refined code placement method in which the code size provided by the system designers must be satisfied. The effectiveness of the refined method is also demonstrated.

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: FISHER, J.A. 1981. Trace scheduling: A technique for global microcode compaction. IEEE Trans. Comput. C-30, 7 (July), 478-490.
• 3: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 4: W. W. Hwu , P. P. Chang, Achieving high instruction cache performance with an optimizing compiler, Proceedings of the 16th annual international symposium on Computer architecture, p.242-251, April 1989, Jerusalem, Israel
• 5: Yau-Tsun Steven Li , Sharad Malik , Andrew Wolfe, Performance estimation of embedded software with instruction cache modeling, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.380-387, November 05-09, 1995, San Jose, California, United States
• 6: LIU, D. AND SVENSSON, C. 1994. Power consumption estimation in CMOS VLSI chips. IEEE J. Solid-State Circuits 29, 6 (June), 663-670.
• 7: Peter Marwedel , Gert Goossens, Code Generation for Embedded Processors, Kluwer Academic Publishers, Norwell, MA, 1995
• 8: S. McFarling, Program optimization for instruction caches, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.183-191, April 03-06, 1989, Boston, Massachusetts, United States
• 9: Scott McFarling, Procedure merging with instruction caches, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.71-79, June 24-28, 1991, Toronto, Ontario, Canada
• 10: Preeti Ranjan Panda , Nikil D. Dutt , Alexandru Nicolau, Memory Organization for Improved Data Cache Performance in Embedded Processors, Proceedings of the 9th international symposium on System synthesis, p.90, November 06-08, 1996
• 11: CORPORATE SPARC International, Inc., The SPARC architecture manual: version 8, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 12: Andrew Wolfe, Software-based cache partitioning for real-time applications, Journal of Computer and Software Engineering, v.2 n.3, p.315-327, 1994

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Languages and compilers; Optimization

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Design, Performance

Keywords:
code placement, instruction cache, integer linear programming