Add a post for the new TCG cache modelling plugin
RFC PATCH 1/1 Add a post for the new TCG cache modelling plugin
This post introduces the new TCG plugin cache that's used for cache modelling. This plugin is a part of my GSoC 2021 participation.
---
This initial RFC patch reflects the latest version that I have for the plugin (the multi-core part is not yet reviewed). That's mainly because I think we have settled a plan and design for this part and the missing. This post analyses the approach that we plan on taking and represents the output logs in it's (hopefully) last form.
.../2021-06-15-tcg-cache-modelling-plugin.md | 191 ++++++++++++++++++ screenshots/2021-06-15-cache-structure.png | Bin 0 -> 19675 bytes 2 files changed, 191 insertions(+) create mode 100644 _posts/2021-06-15-tcg-cache-modelling-plugin.md create mode 100644 screenshots/2021-06-15-cache-structure.png
_posts/2021-06-15-tcg-cache-modelling-plugin.md new file +191 -0
@@ -0,0 +1,191 @@ +--- +layout: post +title: "Cache Modelling TCG Plugin" +date: 2021-06-14 06:00:00 +0000 +author: Mahmoud Mandour +categories: [TCG plugins, GSOC] +--- + +TCG plugins provide means to instrument generated code for both user-mode and +full system emulation, including the ability to intercept every memory access +and instruction execution; this post introduces a new TCG plugin that's used to +simulate configurable L1 separate instruction cache and data cache with +simplicity in mind rather than simulate the intricate microarchitectural +details. + +## Overview + +The plugin simulates how L1 user-configured caches would behave when given a +working set defined by a program in user-mode, or system-wide working set. +Subsequently, it logs performance statistics along with the most N +cache-thrashing instructions. + +### Configurability + +The plugin is configurable in terms of: + +* icache size parameters: `arg="I=CACHE_SIZE ASSOC BLOCK_SIZE"` +* dcache size parameters: `arg="D=CACHE_SIZE ASSOC BLOCK_SIZE"` +* Eviction policy: `arg="evict=lru|rand|fifo"` +* How many top-most thrashing insns to log: `arg="limit=TOP_N"` +* How many core caches to keep track of: `arg="cores=N_CORES"` + +### Multicore caching + +Multicore caching is achieved through having independent L1 caches for each +available core. + +In __full-system emulation__, the number of available vCPUs is known to the +plugin at plugin-installation time, so separate caches are maintained for those. + +In __user-space emulation__, the index of the vCPU initiating a memory access +monotonically increases and is limited with however much the kernel allows to +create. The approach used is that we allocate a static number of caches, and fit +all memory accesses into those cores. This is viable having more threads than +cores will result in interleaving those threads between the available cores so +they might thrash each other anyway. + +## Design and implementation + +### General structure + +A generic cache data structure, `struct Cache`, is used to model either an +icache or dcache. For each known core, the plugin maintains an icache and a +dcache. On a memory access coming from a core, the corresponding cache is +interrogated. + +Each cache has a number of cache sets that are used to store the actual cached +locations alongside with metadata that back eviction algorithms. The +structure of a cache with `n` sets, and `m` blocks per sets is summarized in +the following figure: + + + +### Eviction algorithms + +The plugin supports three eviction algorithms: + +* Random eviction +* Least recently used (LRU) +* FIFO eviction + +##### Random eviction + +On a cache miss that requires eviction, a randomly-chosen block is evicted to +make room for the newly-fetched block. + +Using random eviction effectively requires no meta data for each set. + +#### Least recently used (LRU) + +For each set, a generation number is maintained that is incremented on each +memory access and. Current generation number is assigned to the block +currently being accessed. On a cache miss, the block with the least generation +number is evicted. + +#### FIFO eviction + +A FIFO queue instance is maintained for each set. On a cache miss, the evicted +block is the first-in block, and the newly-fetched block is enqueued as the +last-in block. + +## Usage + +An example usage of the plugin with comparing naive matrix multiplication and +blocked matrix multiplication with matrix block size matching the cache block +size: + +``` +./x86_64-linux-user/qemu-x86_64 $(QEMU_ARGS) \ + -plugin ./contrib/plugins/libcache.so,arg="D=8192 4 64",arg="I=8192 4 64" \ + -d plugin \ + -D naive.log \ + ./naive_matmul +``` + +``` +./x86_64-linux-user/qemu-x86_64 $(QEMU_ARGS) \ + -plugin ./contrib/plugins/libcache.so,arg="D=8192 4 64",arg="I=8192 4 64" \ + -d plugin \ + -D blocked.log \ + ./blocked_matmul +``` + +This will run QEMU and attaches the plugin for both programs. Both runs have the +same configuration: + +* dcache: cachesize = 8KBs, associativity = 4, blocksize = 64B. +* icache: cachesize = 8KBs, associativity = 4, blocksize = 64B. +* Default eviction policy is LRU (used for both caches). +* Single core cache + +Running both instances will log the following: + +* naive.log + +``` +core #, data accesses, data misses, dmiss rate, insn accesses, insn misses, imiss rate +0 6832990 272871 3.9934% 15429566 10308 0.0668% + +address, data misses, instruction +0x40000017cf (mm), 262143, movl (%rax, %rsi, 4), %eax +0x40000017a8 (mm), 5293, movl (%rax, %rcx, 4), %ecx +0x40019ad54e, 511, movzwl 6(%rcx), %edi +0x4000001886 (mm), 377, movl (%rax, %rdx, 4), %eax +... +``` + +* blocked.log + +``` +core #, data accesses, data misses, dmiss rate, insn accesses, insn misses, imiss rate +0 7240895 8882 0.1227% 16161159 10058 0.0622% + +address, data misses, instruction +0x400000180c (bmm), 2088, movl (%rax, %rsi, 4), %eax +0x40000017ba (bmm), 980, movl (%rax, %rdx, 4), %edx +0x40000017e5 (bmm), 640, movl (%rax, %rcx, 4), %ecx +0x40019ad54e, 511, movzwl 6(%rcx), %edi +... +``` + +We can note that a mov instrution that belongs to a symbol calls `mm`(in this +case, `mm` is the function that carries out naive matrix multiplication) is the +causing about 96% of the overall instruction caches. On the other hand, in case +of the blocked matrix multiplication data miss rate is much less. + +#### Multi-core caching + +The plugin accepts a `cores=N_CORES` argument that represents the number of +cores that the plugin must keep track of. Memory accesses generated by excess +threads will be served through the available core caches. + +An example usage of the plugin using the `cores` agrument against a program that +creates 4 threads: + +``` +./x86_64-linux-user/qemu-x86_64 $(QEMU_ARGS) \ + -plugin ./contrib/plugins/libcache.so,arg="cores=4" \ + -d plugin \ + -D logfile \ + ./threaded_prog +``` + +This reports out the following: + +``` +core #,data accesses,data misses,dmiss rate,insn accesses,insn misses,imiss rate +0 76739 4195 5.411666% 242616 1555 0.6409% +1 29029 932 3.211106% 70939 988 1.3927% +2 6218 285 4.511835% 15702 382 2.4328% +3 6608 297 4.411946% 16342 384 2.3498% +sum 118594 5709 4.811139% 345599 3309 0.9575% + +address, data misses, instruction +0x40019d254e, 510, movzwl 6(%rcx), %edi +0x40019d24fe, 290, movq 8(%rcx), %rbp +0x4001814304, 238, movq %rdx, (%rcx) +0x40018142e0, 161, movq (%rax), %rcx +0x40018142f9, 159, movq 0x10(%rax), %rdx +... +```
screenshots/2021-06-15-cache-structure.png new file binary +0 -0
Signature · 1 line
2.25.1
Quoted 34 lines · Mahmoud Mandour
This post introduces the new TCG plugin
cachethat's used for cache modelling. This plugin is a part of my GSoC 2021 participation.Signed-off-by Mahmoud Mandour <[email protected]>---
This initial RFC patch reflects the latest version that I have for the plugin (the multi-core part is not yet reviewed). That's mainly because I think we have settled a plan and design for this part and the missing. This post analyses the approach that we plan on taking and represents the output logs in it's (hopefully) last form.
.../2021-06-15-tcg-cache-modelling-plugin.md | 191 ++++++++++++++++++ screenshots/2021-06-15-cache-structure.png | Bin 0 -> 19675 bytes 2 files changed, 191 insertions(+) create mode 100644 _posts/2021-06-15-tcg-cache-modelling-plugin.md create mode 100644 screenshots/2021-06-15-cache-structure.png_posts/2021-06-15-tcg-cache-modelling-plugin.md new file +10
-0@@ -0,0 +1,191 @@ +--- +layout: post +title: "Cache Modelling TCG Plugin" +date: 2021-06-14 06:00:00 +0000 +author: Mahmoud Mandour +categories: [TCG plugins, GSOC] +--- + +TCG plugins provide means to instrument generated code for both user-mode and +full system emulation, including the ability to intercept every
Quoted 1 line
memory access
Try and trim the sentences to be a bit shorter maybe?
"full system emulation. This includes the ability...""
Quoted 2 lines
+and instruction execution; this post introduces a new TCG plugin that's used to
"This post introduces a new TCG plugin that simulates a simple L1 instruction and data cache."
You could expand on why we don't do microarchitectural stuff in a follow up sentence.
Quoted 101 lines
_posts/2021-06-15-tcg-cache-modelling-plugin.md new file +101
-0+simulate configurable L1 separate instruction cache and data cache with +simplicity in mind rather than simulate the intricate microarchitectural +details. + +## Overview + +The plugin simulates how L1 user-configured caches would behave when given a +working set defined by a program in user-mode, or system-wide working set. +Subsequently, it logs performance statistics along with the most N +cache-thrashing instructions. + +### Configurability + +The plugin is configurable in terms of: + +* icache size parameters: `arg="I=CACHE_SIZE ASSOC BLOCK_SIZE"` +* dcache size parameters: `arg="D=CACHE_SIZE ASSOC BLOCK_SIZE"` +* Eviction policy: `arg="evict=lru|rand|fifo"` +* How many top-most thrashing insns to log: `arg="limit=TOP_N"` +* How many core caches to keep track of: `arg="cores=N_CORES"` + +### Multicore caching + +Multicore caching is achieved through having independent L1 caches for each +available core. + +In __full-system emulation__, the number of available vCPUs is known to the +plugin at plugin-installation time, so separate caches are maintained for those. + +In __user-space emulation__, the index of the vCPU initiating a memory access +monotonically increases and is limited with however much the kernel allows to +create. The approach used is that we allocate a static number of caches, and fit +all memory accesses into those cores. This is viable having more threads than +cores will result in interleaving those threads between the available cores so +they might thrash each other anyway. + +## Design and implementation + +### General structure + +A generic cache data structure, `struct Cache`, is used to model either an +icache or dcache. For each known core, the plugin maintains an icache and a +dcache. On a memory access coming from a core, the corresponding cache is +interrogated. + +Each cache has a number of cache sets that are used to store the actual cached +locations alongside with metadata that back eviction algorithms. The +structure of a cache with `n` sets, and `m` blocks per sets is summarized in +the following figure: + + + +### Eviction algorithms + +The plugin supports three eviction algorithms: + +* Random eviction +* Least recently used (LRU) +* FIFO eviction + +##### Random eviction + +On a cache miss that requires eviction, a randomly-chosen block is evicted to +make room for the newly-fetched block. + +Using random eviction effectively requires no meta data for each set. + +#### Least recently used (LRU) + +For each set, a generation number is maintained that is incremented on each +memory access and. Current generation number is assigned to the block +currently being accessed. On a cache miss, the block with the least generation +number is evicted. + +#### FIFO eviction + +A FIFO queue instance is maintained for each set. On a cache miss, the evicted +block is the first-in block, and the newly-fetched block is enqueued as the +last-in block. + +## Usage + +An example usage of the plugin with comparing naive matrix multiplication and +blocked matrix multiplication with matrix block size matching the cache block +size: + +``` +./x86_64-linux-user/qemu-x86_64 $(QEMU_ARGS) \ + -plugin ./contrib/plugins/libcache.so,arg="D=8192 4 64",arg="I=8192 4 64" \ + -d plugin \ + -D naive.log \ + ./naive_matmul +``` + +``` +./x86_64-linux-user/qemu-x86_64 $(QEMU_ARGS) \ + -plugin ./contrib/plugins/libcache.so,arg="D=8192 4 64",arg="I=8192 4 64" \ + -d plugin \ + -D blocked.log \ + ./blocked_matmul +```
_posts/2021-06-15-tcg-cache-modelling-plugin.md line 122
Quoted 10 lines
_posts/2021-06-15-tcg-cache-modelling-plugin.md new file +10
-0+ +This will run QEMU and attaches the plugin for both programs. Both runs have the +same configuration: + +* dcache: cachesize = 8KBs, associativity = 4, blocksize = 64B. +* icache: cachesize = 8KBs, associativity = 4, blocksize = 64B. +* Default eviction policy is LRU (used for both caches). +* Single core cache + +Running both instances will log the following:
Perhaps instead of delving into the logs we could but snippet of the mm function as a block and annotate where the cache drop instructions are.
Quoted 23 lines
_posts/2021-06-15-tcg-cache-modelling-plugin.md new file +23
-0+ +* naive.log + +``` +core #, data accesses, data misses, dmiss rate, insn accesses, insn misses, imiss rate +0 6832990 272871 3.9934% 15429566 10308 0.0668% + +address, data misses, instruction +0x40000017cf (mm), 262143, movl (%rax, %rsi, 4), %eax +0x40000017a8 (mm), 5293, movl (%rax, %rcx, 4), %ecx +0x40019ad54e, 511, movzwl 6(%rcx), %edi +0x4000001886 (mm), 377, movl (%rax, %rdx, 4), %eax +... +``` + +* blocked.log + +``` +core #, data accesses, data misses, dmiss rate, insn accesses, insn misses, imiss rate +0 7240895 8882 0.1227% 16161159 10058 0.0622% + +address, data misses, instruction +0x400000180c (bmm), 2088, movl (%rax, %rsi, 4), %eax
_posts/2021-06-15-tcg-cache-modelling-plugin.md line 155
Quoted 10 lines
_posts/2021-06-15-tcg-cache-modelling-plugin.md new file +10
-0+0x40000017ba (bmm), 980, movl (%rax, %rdx, 4), %edx +0x40000017e5 (bmm), 640, movl (%rax, %rcx, 4), %ecx +0x40019ad54e, 511, movzwl 6(%rcx), %edi +... +``` + +We can note that a mov instrution that belongs to a symbol calls `mm`(in this +case, `mm` is the function that carries out naive matrix multiplication) is the +causing about 96% of the overall instruction caches. On the other hand, in case +of the blocked matrix multiplication data miss rate is much less.
Is this because the cache miss has been pushed to an outer function? I think having the hot inner loop shown as a whole will help show the differences.
Quoted 9 lines
_posts/2021-06-15-tcg-cache-modelling-plugin.md new file +8
-0+ +#### Multi-core caching + +The plugin accepts a `cores=N_CORES` argument that represents the number of +cores that the plugin must keep track of. Memory accesses generated by excess +threads will be served through the available core caches. + +An example usage of the plugin using the `cores` agrument against aprogram that
argument
Quoted 10 lines
_posts/2021-06-15-tcg-cache-modelling-plugin.md new file +10
-0+creates 4 threads: + +``` +./x86_64-linux-user/qemu-x86_64 $(QEMU_ARGS) \ + -plugin ./contrib/plugins/libcache.so,arg="cores=4" \ + -d plugin \ + -D logfile \ + ./threaded_prog +``` +
_posts/2021-06-15-tcg-cache-modelling-plugin.md line 183
Quoted 10 lines
_posts/2021-06-15-tcg-cache-modelling-plugin.md new file +10
-0+This reports out the following: + +``` +core #,data accesses,data misses,dmiss rate,insn accesses,insn misses,imiss rate +0 76739 4195 5.411666% 242616 1555 0.6409% +1 29029 932 3.211106% 70939 988 1.3927% +2 6218 285 4.511835% 15702 382 2.4328% +3 6608 297 4.411946% 16342 384 2.3498% +sum 118594 5709 4.811139% 345599 3309 0.9575% +
You can drop the summary of instructions from here unless you are going to talk about it in more detail.
Quoted 8 lines
+address, data misses, instruction
+0x40019d254e, 510, movzwl 6(%rcx), %edi
+0x40019d24fe, 290, movq 8(%rcx), %rbp
+0x4001814304, 238, movq %rdx, (%rcx)
+0x40018142e0, 161, movq (%rax), %rcx
+0x40018142f9, 159, movq 0x10(%rax), %rdx
+...
+```
And perhaps an brief outro summarising the work and pointing to the patches on list (patchew archive links are good for this).
Quoted 257 lines
screenshots/2021-06-15-cache-structure.png new file binary +0
-0
Signature · 1 line
Alex Bennée