toplevel cache locality and limiting number of threads for a particular task list
- Dominant language
- Macaulay2
- Stars
- 435
- Forks
- 297
- Avg merge
- 4d 20h
- Merged PRs (30d)
- 11
Description
First, it seems like cache locality of top-level code is very poor.
Here is an observation: say I'm on a server with 196 cores, I could:
- delegate a gb computation to all 196 cores, and they'll start using %100 of cpu cycles until the task is done, in roughly 1/196th the time.
- delegate a trivial task, say updating a hash table, to all cores, and suddenly the task takes _longer_ than if I had assigned it to only 8 cores!
In this case, 8 happened to be the number of coupled cores that **share L3 cache**.
For instance, here's the output of `lstopo` on a server with 196 cores and 755GB memory total, but note that there are 2 sockets, each with:
- 8 NUMA nodes, each close to only 94GB of the memory shared between:
- 3 dies, each with 32MB L3 cache shared between:
- 8 cores with individual L2 and L1 caches.
Hence why running 196 gb threads is totally fine because they copy some data to their corner and get busy with it, but updating the same hash table with 196 tasks is slow because they need to pass around data constantly, whereas a 8 threads can take care of the whole thing without much waste.
On a personal laptop there's probably a single NUMA node and all cores share L3 cache so none of this is relevant.
---
All this brings me to ask the following: **I'd like a way to run certain tasks with 196 cores and others with only 8 cores at a time**. Increasing/decreasing allowableThreads doesn't seem to be a great option, partially because of #4177, but mostly because I might want to run say 128 cores doing gb and 8 cores updating a hash table at the same time.
A crude way of doing this is something like:
```m2
scan(pack_8 L, ell -> taskResult \
apply(ell, i -> schedule(() -> ht#i = f(i))))
```
but you can see how horrible this looks ...
---
Aside from that, I wonder what are other places that we should be mindful of L3 cache locality. e.g. I wonder if there is any particular bdwgc fine-tuning that's worth considering.
All this information is easy to get from C api functions (e.g. read `man lstopo` and `man hwloc`), so it could perhaps be automatic. For instance, maybe we should set the default allowableThreads based on number of cores sharing L3 cache (or half if all cores share L3 cache).
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by reviewing the allowableThreads and schedule entry points, along with the proposed scan/apply pattern and the C API, hwloc, and bdwgc references. Done would require a defined design for per-task thread limits that supports concurrent tasks with different limits, plus evidence that it improves cache locality without relying on global allowableThreads changes.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c
- Domain
- performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100