Is negative scaling on fine-grained CPU-only tasks expected for Legion?

[Tomyk9991]

Context

Comparing Legion with another task-based runtime. I've been benchmarking both systems on the same machine and would like to confirm whether the scaling behaviour I'm seeing is expected, or whether I'm misconfiguring something on my side.

Setup

• Hardware: single node, AMD EPYC 7282 (2 sockets, 64 logical CPUs), 125 GB RAM
• Legion: 25.09.0, built in Release (-O3 -DNDEBUG), with hwloc enabled
• Realm: built separately, Release, installed and linked via find_package
• Launch: one process per node, -ll:cpu N -ll:util 1 -ll:bgwork 1, pinned with taskset -c 0-(N+1) so that every worker/utility/bgwork thread gets its own core
• Verification: every benchmark result is checked against a precomputed reference value

Benchmarks

Four benchmarks, all with identical algorithms and parameters on both systems:

1. Fibonacci — recursive task splitting, cutoff = n/2 (very fine-grained, ~33M tasks at n=50)
2. N-Queens — recursive backtracking, spawn-then-prune (fine-grained)
3. Synthetic checksum — one task per point, ~1M work iterations per task (coarse-grained)
4. LCS — longest common subsequence, deep task trees

Observed scaling (median of 5 runs, speedup from 1 worker to 32 workers)

Benchmark	Legion speedup ll:cpu N (1→32)
Fibonacci	0.54× (gets slower)
N-Queens	0.22× (gets slower)
Synthetic (coarse)	3.5× (scales)
LCS	0.30× (gets slower)

So Legion scales positively only on the coarse-grained benchmark, and negatively on all fine-grained ones.

What I'd like to confirm

1. Is this negative scaling on fine-grained, CPU-only tasks expected for Legion/Realm? I understand Realm has a per-task overhead floor (I recall the ~50 µs figure from Task Bench discussions), and that more workers can increase contention on the runtime's internal structures (completion queues, dependence analysis, locks). Is that the right way to think about it?
2. Is there anything in my configuration that would make this worse than it should be — e.g. the -ll:util 1 -ll:bgwork 1 choice, the single-process-per-node setup, or the taskset pinning?

Thanks in advance for any clarification.

The benchmark implementations can be found here:
The upload for cpp files didn't work, so I pasted them in pastebin.
Fib
N-Queens
Syntetic
LCS

[lightsighter]

A few comments:

• Legion's minimum effective task granularity is nominally around 1ms of compute (100us if tracing is used, which none of these programs is currently doing). None of your task bodies here are going to be anywhere close to 1ms of compute time given how they are currently written on most machines. You need to make your tasks coarser grained in order to use Legion efficiently. You can probably get away with non-leaf tasks that spawn sub-tasks taking <1ms, but the leaves definitely need to be around 1ms minimum unless your program has traceable regions of code.
• There are lots of Legion anti-patterns in how you've written these programs including significant amounts of unnecessary blocking behavior. I would recommend running with -lg:warn and fixing all the performance warnings that the runtime raises before doing any performance measurements.
• None of these programs have a custom mapper. The whole point of using a programming system like Legion which provides a custom mapper interface is so that you can tune the mapping of tasks and data for a particular application and a particular machine. The default mapper provides primitive heuristics for getting things working but should never be used in any Legion performance measurements as you've done here. It should be easy these days to take your favorite LLM and have it look at both the application code as well as the specs on the target machine and have it synthesize a custom mapper tailor made for that particular application running on that specific machine. You should have a unique mapper for every application-machine pair.
• If you're unsure why your performance is slow you should make a profile and let it analyze the performance data. Most likely it will become obvious why your mapper is doing something dumb or your tasks are not coarse enough by looking at profiles. If you need help interpreting them you can attach them here and we'll help you decipher them.