Search
Aim of today's class is to deepen knowledge about cache, to clarify and to show example of time and spatial locality principle. Try to optimize cache parameters.
Consider following example:
#define s0 $16 #define s1 $17 #define s2 $18 .globl array .data .align 2 array: .word 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 .text .globl start .ent start start: la s0, array // load address of the first value in array to register s0 addi s1, $0, 3 // Number of cycle repetitions (number of iterations) nop // Why nop here? Try to remove it. Will it have any influence on hit rate? loop: beq s1,$0, end lw s2, 0(s0) // Read 0th value in array lw s2, 4(s0) // Read 1st value in array (4/4 = 1) lw s2, 36(s0) // Read 9th value (36/4=9) lw s2, 40(s0) // Read 10th value (40/4=10) addi s1, s1, -1 j loop end: nop end_loop: //Final infinite loop j end_loop
Now consider instruction and data cache with size of 8 words (1 word = 4B) each. The cache is word-aligned – it means that address of the first byte in word is divisible by 4. Replacement policy is LRU (lease recently used). Fill-in following table for instruction and data cache. Study in details execution of the above program and study accesses into memory and cache.
Data cache:
Instruction cache:
In the second exercise, you had been assigned the task to implement a program that computes the sum of two vectors each of four elements. Modify the program to work with vectors of 16 words each. Locate the three vectors exactly one after another. Set the cache parameters to 4 sets with four-word blocks and associativity 2 (32 = 4 x 4 x 2). Select LRU replacement policy and write-back. Set burst access time to 2. Observe the behavior if the target vector matches one of the input ones. Repeat when there are three independent vectors. Continue evaluation with 4 words inserted between the second and third vector. Change the cache parameters to (32 = 2 x 4 x 4).
Describe observed behavior and results.
Note. Because write-back policy is used, do not forget to include final instruction cache 9, 0 to flush cache to main memory and clean cache, enable next line in Makefile ARCHFLAGS += -march=mips3 to specify MIPS architecture variant which allows cache instruction.
Take the program from the last class (selection sort) and cache with size of 8 words. Is there any replacement policy which you expect to perform better that others? Consider both data and instruction cache. Verify your conclusions with simulation.
Command line version of the simulator can be used to sped-up evaluation of different cache parameters.
qtmips_cli --i-cache lru,4,1,1 --d-cache lru,4,2,4,wb --burst-time 2 --dump-cache-stats --dump-range pole,60,sorted-data.dat selection-sort
Parameters –i-cache and –d-cache specify configuration of cache memories the same way as for graphical version. –burst-time specifies sequential reads/writes access time 2 cycles, –dump-cache-stats command the emulator to dump statistic at program exit (when execution reaches break instruction). –dump-range allows to dump some memory range as word per line (address can be specified as label). Complete list of parameters is listed when –help parameter is specified.
–i-cache
–d-cache
–burst-time
–dump-cache-stats
break
–dump-range
–help
Additional questions:
Implement C/C + + program, which prints parameters of cache memory of your processor (processor on which is program executed) and size of virtual memory page. Use library function sysconf, and parameters _SC_PAGESIZE, _SC_LEVEL1_DCACHE_LINESIZE etc. COmplete list of parameters supported by GNU C library (GLIBC) can be obtained from library header file bits/confname.h. Parameters are documented in the section Constants for Sysconf of library manual.
_SC_PAGESIZE
_SC_LEVEL1_DCACHE_LINESIZE
Compare results which are obtained by by read of pseudo-filesystems exported by operating system kernel. Use commands
cat /proc/cpuinfo cat /sys/devices/system/cpu/cpu0/cache/index0/size find /sys/devices/system/cpu/cpu0/cache/ -type f -maxdepth 2 -print -exec cat '{}' ';'
Other options are commands lscpu, sudo dmidecode if you have administrator rights.
lscpu
sudo dmidecode
Re-implement program selection from previous seminaries to C/C++ language. Determine hit rate in the first level instruction and data cache. Continue with hit rate of the last level cache – when you run the program on the computer in KN:2 laboratory. How many accesses to data cache is used? How many instructions have been executed? Try to change optimization level specified in compilation command.
Advices:The cachegrind tool allows to evaluate how program access memory and caches.
valgrind --tool=cachegrind ./a.out
cg_annotate filename ~/main.cpp
Remark: If not enough time is left, you can use bubble sort algorithm from the third seminar.
Example of the program output follows: