Skip to contentSkip to conversation

Add a post for the new TCG cache modelling plugin

RFC PATCH Superseded Mahmoud Mandour 2 participants 2 messages Jun 15, 2021

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

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
new file mode 100644
index 0000000..ca9694a
@@ -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:
+
+![cache structure](/screenshots/2021-06-15-cache-structure.png)
+
+### 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
new file mode 100644
index 0000000000000000000000000000000000000000..82a9dc07710e3d9be738d20c675c69aa90a48942
GIT binary patch
Signature · 1 line
2.25.1
#1 lore raw
Quoted 34 lines · Mahmoud Mandour

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 +10 -0
new file mode 100644
index 0000000..ca9694a
@@ -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:
+
+![cache structure](/screenshots/2021-06-15-cache-structure.png)
+
+### 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 a

program 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
new file mode 100644
index 0000000000000000000000000000000000000000..82a9dc07710e3d9be738d20c675c69aa90a48942
GIT binary patch
Signature · 1 line
Alex Bennée