6. Optimization of Memory Access
Society for Industrial and Applied Mathematics eBooks · 2001
As has already been stressed several times in this book, memory access is the major bottleneck on machines with a memory hierarchy. Therefore, optimizing the memory access has the largest potential for performance improvements. While floating point optimization can speed up a program by a factor of 2 for in-cache data, memory access optimization can easily lead to performance improvements by a factor of 10 or more for out of cache data. In this chapter we discuss issues pertinent to memory access optimization. For readability, many examples will present loop structures that were not unrolled or otherwise optimized according to the principles put forward in the previous chapter. When timings are presented, the floating point optimizations are done by hand or by invoking the compiler with appropriate options. 6.1 An illustration of the memory access times on RISC machines Memory access times vary widely depending on how memory is accessed. This can be illustrated by a very simple copy routine “memory-test,” listed in section A.4 of the appendix. We measure the time required for repeatedly copying elements separated by different strides (stride is the distance, measured in words, between two memory locations consecutively accessed by a code) in data sets of different sizes. The copying is repeated many times in order to gather meaningful statistics. After the first copy the data, or fractions of it, are in cache for the successive copy steps. The performance figures obtained from this program are shown in Table 6.1 for an IBM 590. The first column gives the number of cycles necessary to access the data with unit stride. For small data sets, the stride-1 performance is poor due to the significant overhead of the short loops.