[valgrind] [Bug 380942] Experimental: add MESI protocol simulation to Callgrind

[Julian Seward]

https://bugs.kde.org/show_bug.cgi?id=380942

Julian Seward  changed:

   What|Removed |Added

 Attachment #105965|0   |1
is obsolete||

--- Comment #3 from Julian Seward  ---
Created attachment 156636
  --> https://bugs.kde.org/attachment.cgi?id=156636=edit
valgrind-bug380942-Callgrind-MESI.diff-2023Feb23-rebased

Here's the same patch rebased to V sources of 23 Feb 2023.  --fair-sched=yes
has been hardwired (see comment 1) and the scheduling quantum has been reduced
from 1200 to 800, for safety.

TL;DR to build is now:

  git clone https://sourceware.org/git/valgrind.git mesi2023
  cd mesi2023
  patch -p1 < valgrind-bug380942-Callgrind-MESI.diff-2023Feb23-rebased
  ./autogen.sh
  ./configure --prefix=`pwd`/Inst --enable-only64bit
  make -j 8 all
  make -j 8 install

To run:

  /path/to/mesi2023/Inst/bin/valgrind \
 --tool=callgrind --simulate-mesi=yes 
  kcachegrind callgrind.out.

See comment 1 for more details on the RFO events.  These are the "requests for
ownership" (cache line transfers) which contain the info of interest here.

-- 
You are receiving this mail because:
You are watching all bug changes.

[valgrind] [Bug 380942] Experimental: add MESI protocol simulation to Callgrind

[Josef Weidendorfer]

https://bugs.kde.org/show_bug.cgi?id=380942

Josef Weidendorfer  changed:

   What|Removed |Added

 Status|UNCONFIRMED |ASSIGNED
 Ever confirmed|0   |1

--- Comment #2 from Josef Weidendorfer  ---
Nice!

State transitions look good.
Getting read of the empty Ir simulation can be done after merging.

But to really distinguish between true and false sharing, remembering the last
access is not really enough. It may identify true sharing as false sharing.

E.g. multiple accesses from the same thread could cover all of a cache line,
yet it is identified as false sharing if the first access of another thread
does not overlap with the last access of the original thread.

The real solution would be to maintain a bitmap (on a 64-bit architecture,
using a 64-bit integer for a cacheline size of 64 bytes is a perfect match).
Updating the bitmap may be slightly slower, but checking for overlap is
just an AND operation.
I actually do that in the simulator for "cache use"; we can copy it from
there.

-- 
You are receiving this mail because:
You are watching all bug changes.

[valgrind] [Bug 380942] Experimental: add MESI protocol simulation to Callgrind

[Julian Seward]

https://bugs.kde.org/show_bug.cgi?id=380942

--- Comment #1 from Julian Seward  ---
Created attachment 105965
  --> https://bugs.kde.org/attachment.cgi?id=105965=edit
Initial implementation

Here's an initial implementation.  Some notes:

* You *must* use --fair-sched=yes.  If you don't, you'll get garbage
  results and no warning.

* The implementation reduces SCHEDULING_QUANTUM from 10 to 1200,
  so as to give reasonable pseudo-parallel interleaving of threads.
  That is a fine enough interleaving to pick up more than 90% of all
  RFOs from execution of parallel layout algorithms in Firefox.  If
  you have very frequent cache line transfers then you may need to
  set this even lower to get accurate stats.

* The reduction in SCHEDULING_QUANTUM makes Valgrind run more slowly,
  although not catastrophically so.

* This doesn't really simulate the MESI protocol directly.  Instead
  it keeps track of which thread has most recently accessed each
  cache line sized piece of memory, and observes transfers of ownership
  between these cache line sized pieces of memory.

* As a result you can simulate MESI (like) behaviour for any number of
  threads.  It's unrelated to the hardware in your machine.  The line
  size is currently hardwired to 64 bytes.

* Use the flag --simulate-mesi=yes.  You can't use any of the other
  Callgrind simulation facilities (caches, branches, prefetchers etc)
  at the same time.

* The simulation tries to distinguish between true and false sharing.

* This is all very experimental.  It's not really clear whether the RFO
  detection and the true-vs-false sharing detection reflect reality
  accurately enough to be useful.

* 4 different kinds of costs are computed:
 RFOr  -- requests for ownership (transfers) due to reads
 RFOw  -- RFOs due to writes
 RFOrTrue  -- RFOs due to reads, with true sharing
 RFOwTrue  -- RFOs due to writes, with true sharing

* You can display the results in KCachegrind in the normal way.

* Although it is not necessary, it is useful to program the following
  formulas into KCachegrind:

 RFO = RFOr + RFOw  -- total number of RFOs

 RFOTrue = RFOrTrue + RFOwTrue  -- total number of RFOs from true sharing

 RFOFalse = RFOr + RFOw - RFOrTrue - RFOwTrue
-- total number of RFOs from false sharing

-- 
You are receiving this mail because:
You are watching all bug changes.