This paper presents an optimization algorithm for reducing instruction cache misses. The algorithm uses profile information to reposition programs in memory so that a direct-mapped cache behaves much like an optimal cache with full associativity and full knowledge of the future. For best results, the cache should have a mechanism for excluding certain instructions designated by the compiler. This paper first presents a reduced form of the algorithm. This form is shown to produce an optimal miss rate for programs without conditionals and with a tree call graph, assuming basic blocks can be reordered at will. If conditionals are allowed, but there are no loops within conditionals, the algorithm does as well as an optimal cache for the worst case execution of the program consistent with the profile information. Next, the algorithm is extended with heuristics for general programs. The effectiveness of these heuristics are demonstrated with empirical results for a set of 10 programs for various cache sizes. The improvement depends on cache size. For a 512 word cache, miss rates for a direct-mapped instruction cache are halved. For an 8K word cache, miss rates fall by over 75%. Over a wide range of cache sizes the algorithm is as effective as increasing the cache size by a factor of 3 times. For 512 words, the algorithm generates only 32% more misses than an optimal cache. Optimized programs on a direct-mapped cache have lower miss rates than unoptimized programs on set-associative caches of the same size.

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	Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982  [doi>10.1145/356887.356892]
	2	Horowitz, M., Chow, P., et. al., "MIPS-X: A 20 MIPS Peak, 32-Bit Microprocessor with On- Chip Cache", IEEE Journal of Solid-State Circuits, Vol. SC-22, No. 5, October, 1987, pp. 790-799.
	3	Agarwal, A., Chow, P., Horowitz, M., Acken, J., Salz, A., and Hennessy, J., "On-Chip Instruction Caches for High Performance Processors", Proc. of the Conference on Advanced Research in VLS{, Losleben, P.,ed., Stanford University, Stanford, Ca, March 1987.
	4	Mark Donald Hill , Alan Jay Smith, Aspects of cache memory and instruction buffer performance, 1987
	5	S. Prybylski , M. Horowitz , J. Hennessy, Performance tradeoffs in cache design, Proceedings of the 15th Annual International Symposium on Computer architecture, p.290-298, May 30-June 02, 1988, Honolulu, Hawaii, United States
	6	Brian W. Kernighan, Optimal Sequential Partitions of Graphs, Journal of the ACM (JACM), v.18 n.1, p.34-40, Jan. 1971  [doi>10.1145/321623.321627]
	7	Hatfield, D.J., and Gerald, j., "Program Restructuring for Virtual Memory", IBM Systems J., Vol. 10, No. 3, 1971, pp. 168-192.
	8	Domenico Ferrari, Improving locality by critical working sets, Communications of the ACM, v.17 n.11, p.614-620, Nov. 1974  [doi>10.1145/361179.361195]
	9	Ferrari, D., "The Improvement of Program Behavior", Computer, Vol. 9, No. 11, Nov., 1976, pp. 39-47.
	10	Baer, J.L., and Caughey, R., "Segmentation and Optimization of programs from Cyclic Structure Analysis ", Proc. AFIPS, 1972, pp. 23-36.
	11	S. J. Hartley, Compile-Time Program Restructuring in Multiprogrammed Virtual Memory Systems, IEEE Transactions on Software Engineering, v.14 n.11, p.1640-1644, November 1988  [doi>10.1109/32.9051 ]
	12	Janet Fabri, Automatic storage optimization., 1979
	13	Abu-Sufrah, W., "Identifying Program Localities at the Source Level", Technical Report UIUCDCS -R-82-1108, Dept. of Computer Science, Univ. of Illinois, October 1982.
	14	Khalid Omar Thabit, Cache management by the compiler, 1982
	15	Chow, F., "Private Communication".
	16	Alan D Samples , Paul N. Hilfinger, Code Reorginazation for Instruction Caches, University of California at Berkeley, Berkeley, CA, 1988
	17	Belady, L.A., "A Study of Replacement Algorithms for a Virtual-Storage Computer ", IBM Systems J., Vol. 5, No. 2, 1966, pp. 78-101.

• Data structures for quadtree approximation and compression Communications of the ACM   28, 9
  Hanan Samet
  
  
• A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
  Kim S. Lee ,  Huizhu Lu ,  D. D. Fisher
  
  
• Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM   34, 12
  Ellen Francik ,  Susan Ehrlich Rudman ,  Donna Cooper ,  Stephen Levine
  
  
• The GemStone object database management system Communications of the ACM   34, 10
  Paul Butterworth ,  Allen Otis ,  Jacob Stein
  
  
• An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE conference on Design automation
  Gwo-Dong Chen ,  Daniel D. Gajski
  
  

• Architectural Support for Programming Languages and Operating Systems
  Proceedings of the third international conference on Architectural support for programming languages and operating systems
  
  1989 , Boston, Massachusetts, United States