{"id":"a9c1aa40-9a46-4c4b-b8fa-7226e782df79","arxiv_id":"2502.05293","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Replacing GNU OpenMP's lock-based task queue and centralized barrier with lockless structures yields up to 1522.8x speedups on fine-grained task benchmarks, plus NUMA-aware load balancing.","lead":"This paper replaces GNU OpenMP's lock-based task queue and centralized barrier with a lockless queue, a distributed tree barrier, and NUMA-aware load balancing, reporting up to 1522.8x speedups on fine-grained task benchmarks. It matters because GNU OpenMP is the default OpenMP implementation in GCC and currently performs poorly on many-core machines with very small tasks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The distributed tree barrier in Sec. III-B replaces GOMP's global task-count check with local gather conditions, but no proof or stress test shows those conditions guarantee that no task can still be created or enqueued before release; every headline speedup depends on this termination correctness.","rationale":"I read the paper as making two intertwined claims: XQueue plus the distributed tree barrier removes GOMP's synchronization bottleneck (yielding up to 1522.8x), and the DLB strategies add up to 4x on top of XGOMPTB. Both claims are measured, not proven, and the measurement infrastructure is not released. The single most load-bearing point is the correctness of the tree barrier's termination condition, because if it is unsound every speedup number is meaningless even when the benchmark timings are accurate. The reader's weakest_assumption identified exactly this point, and I agree with it. I considered the alternative that the DLB parameter fitting or the NQueens table contradiction is more central, but those affect only the secondary 4x claim and are partially mitigated by the Fig. 11 guideline-based runs and the redundant STRAS/Sort evidence. The tree barrier is load-bearing for the primary 1522.8x claim as well.\n\nI do not escalate the verdict to REJECT: the barrier design is plausible, the paper describes the intended invariant clearly, and the claimed speedups are consistent with known GOMP scalability failures on fine-grained tasks (the paper's own Fig. 1 shows GOMP taking 1000x longer than LOMP/XLOMP on several BOTS benchmarks). No internal inconsistency forces the barrier to be wrong. But the absence of any correctness argument or artifact means the central claim cannot be fully verified from the text, so CONDITIONAL remains the right verdict. The concrete debug-assertion test would settle whether the local gather conditions actually imply global quiescence; until that test or a proof is supplied, the barrier correctness concern is unresolved.","tokens_in":20351,"tokens_out":6669,"duration_ms":77012,"concrete_test":"Retain the original global atomic task count in a debug assertion build (not used for synchronization) and run all nine BOTS benchmarks at 24/64/96/128/192 threads, plus a randomized stress generator that creates many short tasks with dependencies and remote pushes. At the instant each worker is released from the new tree barrier, assert that the global task count is zero and that every worker's master and auxiliary XQueues are empty. Any violation is a concrete counterexample to the Sec. III-B termination conditions. Complement this with a small TLA+ or C++ model of the binary-tree gather/release under arbitrary interleavings of remote enqueue operations; if the model finds a reachable state in which a worker releases with a non-empty queue or while another worker can still enqueue, the barrier is unsound as described.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central speedup claims (up to 1522.8x for XGOMPTB, and the DLB results built on XGOMPTB) all depend on the correctness of the new distributed tree barrier termination condition in Sec. III-B. The original GOMP barrier releases only when the last worker has entered and the global task count is zero. The replacement gathers a worker when: (i) all workers have entered the barrier; (ii) the worker is idle; (iii) the worker's current task has no unfinished dependencies; and (iv) all children barriers are gathered. No proof, model check, or stress test is provided that these local conditions imply the global invariant that no task exists anywhere and none can be created.\n\nThis is not a pedantic concern: XQueue is explicitly a multi-producer/multi-consumer structure, so any worker can push a task into any other worker's auxiliary queue at any scheduling point, and the proposed NA-RP/NA-WS load balancers deliberately migrate tasks between workers. The barrier's safety rests on the unstated assumption that once all workers are idle and have no unfinished dependencies, no worker can subsequently enqueue work. That is precisely the invariant the barrier is supposed to enforce, and the paper removes the global counter that previously checked it. If a worker reports 'idle' or 'children gathered' based on stale local state while another worker is about to push a task into its queue, the released worker can miss that task, producing lost work, deadlock, or silently incorrect results. Because there is no artifact or verification, the reader cannot distinguish a correct barrier from one that merely passes the reported benchmarks.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes three optimizations to GNU OpenMP (GOMP) for fine-grained task parallelism on many-core NUMA systems: (1) integration of XQueue, a lock-less MPMC task queue, replacing GOMP's priority queue and global task lock; (2) a hybrid lock-free/lock-less distributed tree barrier to replace GOMP's centralized barrier; and (3) two NUMA-aware lock-less dynamic load balancing strategies, NA-RP and NA-WS. The authors evaluate the resulting XGOMP and XGOMPTB runtimes on nine BOTS benchmarks on a 192-core Intel Skylake machine and claim speedups over GOMP of up to 1522.8x, with additional up-to-4x gains from the load balancers over XGOMPTB. They also present profiling tools, parameter-tuning guidelines, and a Proof-of-Space blockchain application case study.","tokens_in":20651,"tokens_out":7237,"duration_ms":69190,"significance":"If the results are substantiated, the paper would demonstrate that GOMP's synchronization overhead is the dominant cost for fine-grained tasking on many-core systems and that a lock-less queue, distributed tree barrier, and NUMA-aware load balancing can remove that cost. The XQueue integration and the proposed DLB strategies are concrete and potentially useful engineering contributions, and the paper includes a real application (PoSp) plus profiling infrastructure. Credit is due for evaluating against external GOMP, LOMP, and XLOMP baselines, which makes the main XGOMPTB comparisons non-circular. However, the significance is conditional: the central correctness invariant of the distributed tree barrier is unproven, the DLB gains are selected from per-benchmark parameter sweeps, and the empirical claims rest on a single machine with no released artifact or raw data. These issues must be resolved before the headline speedups can be considered reliable.","major_comments":[{"comment":"The safe-release invariant of the distributed tree barrier is not established. The paper replaces GOMP's centralized barrier, which releases only when the last worker has entered and the global task count is zero, with a tree barrier whose gather conditions are (i) all workers entered, (ii) the worker is idle, (iii) the current task has no unfinished dependencies, and (iv) all children barriers are gathered. Because XQueue is explicitly MPMC and the NA-RP/NA-WS strategies in Section IV can push or steal tasks into arbitrary workers' auxiliary queues, it is possible for a worker that has reported 'idle' to receive a task from another worker before the root completes the release. The paper provides no proof, model check, or stress test that these local conditions imply the global invariant that no task exists and none can be created. Since every headline speedup in Figs. 4 and 5 depends on this barrier releasing correctly, this is a load-bearing gap. Please add a formal correctness argument or, failing that, a randomized dependency-coupled stress test with assertion checks.","section":"Section III-B"},{"comment":"The NQueens discussion is internally contradictory. The text states 'For NQueens, NA-RP is the best performing strategy' and then, in the same subsection, 'We see in Table II that NA-RP yields the worst average performance.' Table II reports NQueens NA-RP 26.5 s versus NA-WS 23.2 s, and Table III reports SLB 23.8 s, so on the reported averages NA-RP is not the best strategy. The subsequent explanation invoking profiling overhead is not supported by any presented data. Please correct the prose and reconcile the figure and table numbers.","section":"Section VI-B1 and Table II"},{"comment":"The DLB speedups are selected maxima over per-benchmark parameter sweeps. For each benchmark, the authors sweep Nvictim, Nsteal, Tinterval, and Plocal and then report the best configuration; the 'up to 4x' claim is therefore a best-case fitted value, not a prediction of expected behavior. Table I shows that the optimal parameters vary widely across benchmarks, and the tuning guidelines in Section VIII are derived from the same data used to select those optima. The paper should either validate the guidelines on held-out benchmarks or inputs, or report the full distribution of configuration results and a sensitivity analysis. Without this, the DLB comparison risks overfitting and does not support the strength of the claimed gains.","section":"Section VI-B and Table I"},{"comment":"The request construction 'newReq ← (tidi << 40) & round' cannot encode a request as described. With the 40-bit round occupying bits 0-39 and the 24-bit worker ID in bits 40-63, the bitwise AND of the shifted ID with the round value is identically zero. This should be a bitwise OR (or an explicit bit-field merge). As printed, the lock-less messaging protocol is not well defined, and the victim logic in Algorithm 2 cannot operate as described.","section":"Section IV-B, Algorithm 1"},{"comment":"The empirical claims are not reproducible from the manuscript. The paper reports speedups of up to 1522.8x based on BOTS measurements on a single machine, with no released code, no released raw data, and no reported variance for most of the central comparisons (Figs. 4-6). The statement in Section VI that the larger and smaller experiments 'yield similar results' is not accompanied by data. Given the magnitude of the claims, the authors should provide an artifact (code, scripts, raw logs, and configurations) and at least confidence or variance information for the main speedup figures.","section":"Section VI and reproducibility"}],"minor_comments":[{"comment":"The caption reads 'A-WS (work-stealing)' but the strategy is named NA-WS throughout the paper.","section":"Figure 10 caption"},{"comment":"The definition of Ssteal mixes Nvictim, Nsteal, and a log-scaled Tinterval, but the units and the intended meaning of 'steal size' for NA-RP versus NA-WS are not clarified; please define the quantity precisely and explain why this combination is a meaningful independent variable.","section":"Equation (1) and Section VIII"},{"comment":"Table II reports average times that appear inconsistent with the bars in Figure 7 (e.g., Fib NA-RP 9.9 s in Table II versus the corresponding bar in Figure 7). Please reconcile the two presentations or explain the difference.","section":"Table II and Figure 7"},{"comment":"The claim that the hybrid tree barrier 'yields a theoretical lower bound of half the atomic memory access operations' is asserted without a model or derivation; please provide the counting argument and state the assumptions.","section":"Section III-B"},{"comment":"The symbol ctidthief is used before it is introduced, and the relationship between req, round, and the 64-bit request cell layout is not fully defined; please define all bit-field sizes and variable scopes where the algorithms are first presented.","section":"Section IV-B, Algorithms 1-3"},{"comment":"Entries such as 'Best Ssteal 100-101' are ambiguous; they presumably mean 10^0-10^1, but the exponent formatting should be explicit.","section":"Table IV"}],"recommendation":"major_revision","confidential_remarks":"The paper's claims are much larger than what the current evidence supports, but the core direction is plausible and potentially valuable. I would not recommend rejection; rather, acceptance should be conditioned on an artifact release and on closure of the barrier-correctness gap. I also recommend asking the authors to clarify the novelty boundary with respect to their prior X-OpenMP work and to other recent lock-less OpenMP runtime proposals, because the phrase 'first lock-less NUMA-aware DLB for OpenMP' needs a precise comparison point."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth reading and worth a serious referee, but the 1522.8x and 4x numbers are not yet established: the tree barrier's termination condition has no correctness argument, and the DLB gains are best-case fits from parameter sweeps.\n\nWhat is new: XQueue integrated into GNU OpenMP, a hybrid lock-free/lock-less tree barrier, and two NUMA-aware lock-less load-balancing strategies. That's a coherent and non-trivial engineering package, and the profiling tools give a real picture of where GOMP loses cycles. The PoSp application is a good sanity check. The writing is clear and the algorithms are described at a level that would let someone reimplement them.\n\nThe load-bearing soft spot is the barrier. The original GOMP barrier waits on a global task count; the new tree barrier releases when a worker is idle, its current task has no dependencies, and the children subtrees are gathered. But XQueue is explicitly MPMC, and NA-RP/NA-WS migrate tasks across workers. Nothing in the paper proves that once all workers have entered the barrier, no task is left in some auxiliary queue or in flight. The absence of a global counter means a worker could enter the barrier after its queue is empty, then another worker (just before entering) pushes a task to that queue, and the barrier releases leaving the task unexecuted. The benchmarks may well be correct, but that's empirical evidence, not a correctness argument. This needs either a proof, a model check, or a stress test with adversarial task creation patterns. Right now the central speedup rests on an unverified invariant.\n\nThis is not the only soft spot. The DLB numbers are per-benchmark best-case settings from sweeps over Nvictim, Nsteal, Tinterval, Plocal; the 'up to 4x' is a fitted maximum, not a predictive claim. The tuning guidelines in Section VIII are derived from the same benchmarks, so they are more post-hoc rationalization than validation. The NQueens prose in Section VI-B contradicts Table II -- the text says NA-RP is best, but Table II shows NA-WS faster and the text itself admits NA-RP gives the worst average with profiling on. That kind of inconsistency makes it hard to trust the claims without the artifact. There's no code or data release, so none of this is independently checkable.\n\nWho should read this: anyone working on OpenMP runtimes, task-parallel scheduling, or NUMA-aware scheduling on large many-core systems. It's an engineering paper with useful ideas and a plausible central claim. It should get a serious referee, but I would send it back for major revision, asking for a correctness argument for the barrier, released code/data, and a sharper distinction between fitted configurations and predictions.","headline":"A solid engineering contribution with a plausible central claim, but the headline speedups rest on an unverified barrier invariant and fitted DLB parameters; worth a serious referee, not yet worth citing.","tokens_in":21257,"tokens_out":6797,"would_cite":false,"duration_ms":55997,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that replacing GNU OpenMP's global task lock and centralized barrier with a lock-less task queue and a distributed tree barrier removes the dominant synchronization cost of fine-grained tasking, yielding up to 1522.8x…","keywords":["fine-grained tasking","GNU OpenMP","lock-less queue","distributed tree barrier","dynamic load balancing","NUMA-aware scheduling","work stealing"],"falsifier":"Instrument the runtime to record, for each worker, the barrier-exit timestamp and the global task count plus any pending dependency counters, then run the nine BOTS workloads at 192 threads. If any worker exits the team barrier while the global task count is nonzero, while a dependency on any in-flight task remains unresolved, or while any other worker has not yet reached the barrier and could still enqueue new work, the gather conditions are insufficient and the central claim collapses.","tokens_in":20134,"feed_emoji":"⚡","tokens_out":5053,"duration_ms":45894,"temperature":0.7,"pith_summary":"This paper tries to establish that GNU OpenMP's poor scaling on many-core machines is caused by synchronization overhead in the runtime — specifically a single global task lock and a centralized barrier guarded by an atomic counter — and that replacing those structures with lock-less alternatives makes fine-grained tasking practical at 192 threads. On the Barcelona OpenMP Task Suite benchmarks, the authors report speedups up to 1522.8x over stock GNU OpenMP using only the queue and tree barrier, and up to 4x additional improvement from their two NUMA-aware dynamic load-balancing strategies. The paper also contributes a lock-less inter-thread messaging protocol, per-thread profiling tools, and tuning guidance linking task size and steal size to the best strategy. A sympathetic reader would take the central claim as: synchronization, not the task graph, is the bottleneck for fine-grained OpenMP tasks.","feed_headline":"Lock-less redesign makes GNU OpenMP up to 1,522x faster","feed_subtitle":"Replacing the global task lock and centralized barrier unlocks fine-grained parallel tasks on 192-core systems.","key_machinery":"The load-bearing mechanism is a combination of two lock-less data structures. XQueue replaces GOMP's global priority queue: each worker has one master SPSC queue and one auxiliary SPSC queue per other worker; producers round-robin push task pointers to target queues, consumers drain their master queue then auxiliaries, and no atomic instructions are used, only cache-friendly reads and writes. The distributed tree barrier organizes workers in a binary tree; a worker is gathered when all workers have entered the barrier, the worker is idle, its current task has no unfinished dependencies, and all of its children are gathered, and it then atomically sets a per-parent complete flag, with release performed as a lock-less tree broadcast of flags. Around these, the lock-less messaging protocol uses a 64-bit request cell (40-bit round number plus 24-bit worker ID) and a round cell per victim so thieves can ask a victim to redirect or hand over tasks without locks or atomics; the victim validates the request by matching round numbers and increments its round after handling.","core_discovery":"The authors claim that the dominant cost in GNU OpenMP for fine-grained, short-running tasks is not the task computation itself but the runtime's synchronization: a single global priority task queue protected by a global task lock, and a centralized team barrier that atomically tracks a global task count. They integrate XQueue, a lock-less multi-producer/multi-consumer queue in which each worker owns an SPSC master queue and per-worker auxiliary queues with round-robin push, into GOMP, converting the global count to an atomic and removing the lock. They then replace the centralized barrier with a hybrid distributed tree barrier that gathers lock-free and releases lock-less, with a theoretical lower bound of half the atomic memory operations. On 192 cores, XQueue alone gives up to 96.5x over GOMP, and the queue plus tree barrier gives up to 1522.8x for NQueens. Finally, two lock-less NUMA-aware load-balancing strategies — redirect push (NA-RP) and batch work stealing (NA-WS) — communicate via lock-less request and round cells and improve performance up to 4x over the static round-robin XQueue schedule, with substantial gains in task locality.","pith_inferences":["Editorial inference: if the barrier's correctness premise holds, the same lock-less queue-plus-tree-barrier recipe could be ported to other lock-based OpenMP runtimes, since nothing in the design is specific to GCC's internals.","Editorial inference: the headline 1522.8x figure is a single-benchmark, single-machine upper bound; on workloads with large tasks or low lock contention the gains shrink considerably, so expected speedups should be predicted from task-size histograms rather than from the headline number.","Editorial inference: the tree barrier's correctness is asserted by design rather than proven, so a randomized dependency-DAG stress test or a formal model of the gather conditions would directly test whether the speedups hide a correctness assumption.","Editorial inference: the lock-less messaging protocol uses a 40-bit round number per victim, so after 2^40 handled requests the round wraps; on extremely long-running fine-grained workloads that wrap is a concrete scalability limit worth testing."],"forward_implications":["With XGOMPTB, fine-grained workloads that were more than 1000x slower in stock GOMP become practical at 192 threads, so OpenMP task directives can now be used for tasks lasting tens of cycles without paying prohibitive runtime overhead.","The distributed tree barrier's theoretical lower bound of half the atomic memory access operations means barrier cost scales with tree depth and per-node flags rather than with a single contended global counter.","NA-RP is best for large tasks (above roughly 10^4 rdtscp cycles) and can deliver about 4x over static load balancing, while NA-WS improves all nine tested benchmarks and is described as a well-rounded, less sensitive default.","The tuning guidelines in Table IV let practitioners choose a strategy, NUMA-local probability, and steal size from measured task size, with the observed pattern that small tasks want small steal sizes and full NUMA locality.","The PoSp case study shows a 195x throughput gain at batch size 1 and a 32% peak-throughput gain over stock GOMP when batch sizes are chosen optimally."],"supporting_citations":[{"why":"Supplies XQueue, the lock-less MPMC queue from prior work that XGOMP integrates into GOMP to remove the global task lock.","marker":"[4]"},{"why":"Supplies the Barcelona OpenMP Task Suite benchmarks used as the evaluation workload for all reported speedups.","marker":"[8]"},{"why":"Provides the prior XQueue work-stealing design whose messaging ideas the paper extends with NUMA-aware victim selection and batch steals.","marker":"[10]"},{"why":"Provides the conditionally random victim selection strategy adopted in the lock-less messaging protocol.","marker":"[11]"},{"why":"Defines work time inflation, which the paper invokes to explain why scaling remains sublinear after synchronization is removed.","marker":"[14]"},{"why":"Supplies the Chia blockchain specification that defines the Proof-of-Space workload used as the real-world application test.","marker":"[17]"}],"fun_headline_variants":["Lock-less GNU OpenMP hits 1,522x on fine-grained tasks","Redesigning GNU OpenMP: 1,522x speedup via lock-free sync","XQueue and tree barrier: GNU OpenMP 1,522x faster","NUMA-aware load balancing boosts GNU OpenMP 4x more"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole result rests on the unproven assumption that the tree barrier's four gather conditions correctly detect when every task is finished, so a worker never leaves the barrier while another worker could still create work.","fun_headline_variants_meta":{"raw":{"variants":["Lock-less GNU OpenMP hits 1,522x on fine-grained tasks","Redesigning GNU OpenMP: 1,522x speedup via lock-free sync","XQueue and tree barrier: GNU OpenMP 1,522x faster","NUMA-aware load balancing boosts GNU OpenMP 4x more"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000163,"raw_usage":{"total_tokens":1261,"prompt_tokens":983,"completion_tokens":278,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":599,"completion_tokens_details":{"reasoning_tokens":194}},"tokens_in":599,"tokens_out":278,"duration_ms":2883,"temperature":1.0,"reasoning_tokens":194,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T19:52:34.725103+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Instrument the runtime to record, for each worker, the barrier-exit timestamp and the global task count plus any pending dependency counters, then run the nine BOTS workloads at 192 threads. If any worker exits the team barrier while the global task count is nonzero, while a dependency on any in-flight task remains unresolved, or while any other worker has not yet reached the barrier and could still enqueue new work, the gather conditions are insufficient and the central claim collapses.","supporting_citations":[{"cited_title":"Enabling extremely fine-grained parallelism via scalable concurrent queues on modern many-core architectures,","cited_arxiv_id":null,"evidence_quote":"Supplies XQueue, the lock-less MPMC queue from prior work that XGOMP integrates into GOMP to remove the global task lock."},{"cited_title":"Barcelona OpenMP Tasks Suite: A set of benchmarks targeting the exploitation of task parallelism in OpenMP,","cited_arxiv_id":null,"evidence_quote":"Supplies the Barcelona OpenMP Task Suite benchmarks used as the evaluation workload for all reported speedups."},{"cited_title":"X-OpenMP — eXtreme fine-grained tasking using lock-less work stealing,","cited_arxiv_id":null,"evidence_quote":"Provides the prior XQueue work-stealing design whose messaging ideas the paper extends with NUMA-aware victim selection and batch steals."},{"cited_title":"Charac- terizing and mitigating work time inflation in task parallel programs,","cited_arxiv_id":null,"evidence_quote":"Defines work time inflation, which the paper invokes to explain why scaling remains sublinear after synchronization is removed."},{"cited_title":"The chia network blockchain,","cited_arxiv_id":null,"evidence_quote":"Supplies the Chia blockchain specification that defines the Proof-of-Space workload used as the real-world application test."}],"review_version":1}