REVIEW 3 major objections 6 minor 33 references
For shared-memory row sorting on a 24-core machine, lightweight dynamic and guided threads beat process schedulers, while pipe-based process designs scale best among the heavyweight options.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · grok-4.5
2026-07-11 13:00 UTC pith:4MQDFV4S
load-bearing objection Solid empirical ranking of process vs thread schedulers on one 24-core platform and one uniform quicksort workload; useful tables, honest limits, no load-bearing flaw. the 3 major comments →
Performance evaluation of scheduling tasks in many-core systems utilizing processes and threads
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
On a 24-core x86-64 platform running row-wise quicksort of large shared-memory tensors, dynamic and guided thread schedulers achieve the highest overall performance and near-ideal speedup at the hardware limit, while among process schedulers the pipe-based designs (one-to-one for smaller loads, many-to-many for larger loads) scale best and substantially outperform fork-based prolific and collective schedulers once oversubscription begins.
What carries the argument
Side-by-side evaluation of two families of schedulers on the same shared-memory tensor: fork-based and three pipe-based process designs versus OpenMP-style and adaptive thread policies (including an AIMD contention window driven by EWMA CPU utilization), all measured by speedup, efficiency, and estimated serial fraction on identical 1000- and 10000-frame workloads.
Load-bearing premise
The ranking obtained on a single, structurally uniform but data-dependent quicksort workload of identical frames is taken to speak for many-core shared-memory scheduling more generally.
What would settle it
Repeat the identical experiment on a structurally irregular workload (for example sparse-matrix tasks or frames of widely varying size) or on a perfectly regular constant-cost kernel; if the relative order of dynamic/guided threads, pipe process schedulers, and fork-based schedulers reverses, the claimed preference for lightweight threads no longer holds.
If this is right
- Shared-memory row-sorting codes on multi-core CPUs should default to dynamic or guided thread scheduling rather than process forking.
- When process isolation or explicit IPC is required, many-to-many pipes with carefully tuned chunk size give the best scaling among process options.
- AIMD-style utilization feedback can be kept as a safety mechanism for multi-tenant or long-running settings even if it is not the fastest pure-batch scheduler.
- Oversubscription hurts fork-based process schedulers far more than either threads or pipe-based process designs.
- Chunk size is the dominant tuning knob for every pipe-based process scheduler.
Where Pith is reading between the lines
- The same pipe patterns could transfer almost unchanged to MPI-style distributed producer-consumer task farms once the shared-memory tensor is replaced by message-passing.
- Because the workload irregularity is only data-dependent, the paper under-states how much adaptive-chunk or work-stealing policies might gain on genuinely heterogeneous task graphs.
- The AIMD contention window is essentially a soft admission controller; the same feedback loop could be reused for power or thermal throttling without changing the rest of the scheduler.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper empirically ranks process-based (bounded prolific, bounded collective, and three pipe producer-consumer designs) and thread-based (static, dynamic, guided, chunk, chunk-stealing, adaptive-chunk, and AIMD) schedulers on a 24-core x86-64 shared-memory platform for a memory-intensive row-wise quicksort workload on large 3-D tensors (L=1000 and L=10000 frames of 640 imes640). Using ten-run averages, an explicit 1% noise threshold, Amdahl/Karp–Flatt diagnostics, and absolute times (Table 17), it reports that dynamic and guided threads achieve near-ideal speedup (σ≈23.4–23.7) at k=24, that pipe schedulers are the strongest process family (one-to-one for L=1000, many-to-many for L=10000), and that fork-based prolific/collective designs collapse under modest oversubscription (k=32). AIMD and adaptive-chunk policies are presented as contention-aware alternatives that underperform the simpler dynamic/guided policies on this isolated benchmark.
Significance. If the ranking holds, the work supplies a concrete, platform-grounded comparison of process versus thread scheduling for shared-memory many-core systems and documents that lightweight dynamic/guided threads remain preferable for homogeneous frame-level work while pipe-based IPC can match them and far outperform classic fork-based process pools under oversubscription. Strengths include the systematic coverage of both process and thread families, the explicit measurement protocol (ten-run means, 1% equivalence threshold, inclusion of creation/IPC overhead), the absolute-time Table 17, and the candid §6.6 limitation statement. The AIMD and adaptive-chunk designs are original contributions even if they do not win on this workload. The principal limitation is that the ranking is demonstrated only for one structurally uniform, data-dependent quicksort workload on one 24-core machine; broader claims about many-core scheduling therefore rest on that envelope.
major comments (3)
- §6.6 and the abstract/conclusion: the central ranking is internally consistent with Tables 5–16 and 17 for the stated platform and workload, yet the abstract and §7 still frame the result as guidance for “many-core shared-memory systems” and “distributed-style heterogeneous workload management.” Because the paper itself notes that structural irregularity or constant-cost tasks could reorder the rankings, the abstract and conclusion should be tightened to the evaluated envelope (24-core x86-64, identical-frame row-wise quicksort) so that the generalization claim does not outrun the evidence.
- Tables 1–16 and §5: all reported σ(k), σE(k) and α(k) are ten-run arithmetic means with no standard deviations, confidence intervals, or min/max ranges. Given the explicit 1% noise threshold used for equivalence claims (e.g., pipe vs. dynamic differences of ~0.5–1%), the absence of dispersion measures leaves open whether those differences are statistically distinguishable from run-to-run jitter. Adding error bars or at least reporting the observed coefficient of variation would make the ranking claims fully load-bearing.
- §2.3 (Eqs. 1–2) and §4: the AIMD free parameters (a=0.7, β=0.8, 95% overload threshold, CHUNK=4, probe every 32 completions) and the pipe/thread chunk sizes (12/105, 10/100) are hand-chosen without a sensitivity study. While they do not underwrite the headline dynamic/guided vs. pipe vs. fork ranking, they do affect the secondary claim that AIMD/adaptive policies are “valuable for contention-aware execution.” A short sensitivity paragraph or appendix would strengthen that secondary claim.
minor comments (6)
- Table 5 note and several rows: super-linear speedups (σE>1) are attributed to cache effects; a brief quantitative check (e.g., LLC miss rates or working-set size relative to L2/L3) would make the explanation more convincing.
- §5 vs. §5.1: the text first states “No explicit CPU affinity was enforced” and later “Unless otherwise stated, processor affinity was enabled.” Clarify which tables/figures used affinity and which did not.
- Figures 2–14: axis labels and legends are readable in the manuscript source but would benefit from larger fonts and consistent y-axis ranges when comparing process vs. thread families.
- §3.3: the discussion of negative α values (measurement noise) and α>1 (slowdown) is useful; consider flagging those rows explicitly in the tables (e.g., with a footnote) rather than only in the prose.
- References: several self-citations to prior process-forking work are appropriate background; ensure the arXiv/SSRN preprints are updated to final versions if available.
- Reproducibility: no public code or data artifacts are mentioned. Depositing the scheduler implementations and the tensor-generation seed would substantially increase the paper’s long-term value.
Circularity Check
No significant circularity: empirical wall-clock rankings on a fixed workload are self-contained and do not reduce to fitted inputs or load-bearing self-citations.
full rationale
The paper is an experimental systems evaluation, not a first-principles derivation. All headline claims (dynamic/guided threads best overall; pipe-based processes best among process designs; fork-based prolific/collective collapse under oversubscription) rest on measured arithmetic-mean execution times of a row-wise quicksort workload on identical shared-memory tensors, converted to speedup σ(k) = T_serial / T_parallel(k) and efficiency. No free parameter is fitted to a data subset and then re-labeled a prediction; chunk sizes (12/105) and AIMD constants (a=0.7, β=0.8, 95 % threshold) are hand-tuned but affect only secondary policies and are disclosed. Self-citations ([31] on prior forking, [20–23] on adaptive load-balancing) supply background motivation and do not underwrite the measured speedups or rankings. Amdahl/Karp–Flatt α estimates are pure post-hoc diagnostics from the same measured σ(k). The interpretive remark that AIMD remains valuable for multi-tenant platforms is an extrapolation outside the idle-machine data, not a circular reduction. The derivation chain is therefore self-contained against the reported tables; score 0 is warranted.
Axiom & Free-Parameter Ledger
free parameters (5)
- AIMD EWMA weights a, β =
a=0.7, β=0.8
- AIMD overload threshold =
95%
- AIMD chunk size and probe interval =
CHUNK=4, probe every 32
- pipe optimal chunk sizes =
12 (L=1000), 105 (L=10000)
- thread chunk sizes for chunk/chunk-steal =
10 / 100
axioms (4)
- standard math Amdahl's law and Karp-Flatt metric correctly diagnose serial fraction and overhead for fixed-size workloads
- domain assumption The Linux CFS scheduler plus optional sched_setaffinity provides a fair and reproducible placement baseline
- ad hoc to paper Row-wise quicksort on identical-size frames is a representative memory-intensive irregular workload for many-core scheduler comparison
- domain assumption Copy-on-write fork plus System-V shared memory is the appropriate process model for SIMP tensor work
invented entities (2)
-
AIMD contention-window scheduler driven by EWMA of blended max/min core utilization
no independent evidence
-
Adaptive chunk scheduler with per-thread speed factor = global_avg / thread_avg
no independent evidence
read the original abstract
This study assesses the scalability of process-based and thread-based schedulers for many-core shared-memory systems using a memory-intensive row-wise quick-sort workload on large three-dimensional tensors. The process-based evaluation considers bounded prolific, bounded collective, and three pipe-based producer-consumer schedulers: one-to-one, one-to-many, and many-to-many. These pipe schedulers dynamically stream task identifiers to worker processes, exchanging increased inter-process communication overhead for enhanced runtime load balancing and flexible chunk-based task dispatching. The thread-based evaluation examines static, dynamic, guided, chunk-based, chunk-stealing, adaptive chunk, and AIMD adaptive scheduling strategies. The AIMD scheduler employs an additive-increase multiplicative-decrease policy inspired by TCP congestion control, utilizing an exponentially weighted moving average (EWMA) of CPU utilization to regulate a contention window that limits the number of concurrently active chunks. The adaptive chunk scheduler further modifies chunk size based on observed per-thread execution speed. Experimental results on a 24-core x86-64 platform indicate that thread schedulers deliver the highest overall performance, with dynamic and guided scheduling yielding the most favorable practical outcomes. Among process schedulers, pipe-based designs demonstrate the strongest scalability, with one-to-one pipes excelling for smaller workloads and many-to-many pipes preferred for larger workloads. In summary, lightweight thread scheduling is optimal for shared-memory row sorting, while AIMD/adaptive scheduling and pipe-based process scheduling remain valuable for contention-aware execution, explicit inter-process coordination, and distributed-style heterogeneous workload management.
Figures
Reference graph
Works this paper leans on
-
[1]
Compiler-assisted, adaptive runtime system for the support of OpenMP in embedded multicores,
S. N. Agathos, V . V . Dimakopoulos, and I. K. Kas- meridis, “Compiler-assisted, adaptive runtime system for the support of OpenMP in embedded multicores,”Parallel Computing, vol. 110, p. 102895, May 2022. [Online]. Available: https://www.sciencedirect.com/science/article/ pii/S0167819122000035 2, 5
2022
-
[2]
Adaptive Thread Scheduling in Chip Multiprocessors,
I. Akturk and O. Ozturk, “Adaptive Thread Scheduling in Chip Multiprocessors,”International Journal of Parallel Programming, vol. 47, no. 5-6, pp. 1014–1044, Dec
-
[3]
Available: http://link.springer.com/10.1007/ s10766-019-00637-y 2, 5
[Online]. Available: http://link.springer.com/10.1007/ s10766-019-00637-y 2, 5
-
[4]
Validity of the single processor approach to achieving large-scale computing capabilities,
G. M. Amdahl, “Validity of the single processor approach to achieving large-scale computing capabilities,” inProceed- ings of the April 18–20, 1967, Spring Joint Computer Con- ference, ser. AFIPS ’67 (Spring). Association for Comput- ing Machinery, 1967, pp. 483–485. 6, 7
1967
-
[5]
Scheduling multi- threaded computations by work stealing,
R. D. Blumofe and C. E. Leiserson, “Scheduling multi- threaded computations by work stealing,”Journal of the ACM, vol. 46, no. 5, pp. 720–748, Sep. 1999. [Online]. Available: https://doi.org/10.1145/324133.324234 2, 5
-
[6]
An adaptive self-scheduling loop scheduler,
J. D. Booth and P. A. Lane, “An adaptive self-scheduling loop scheduler,”Concurrency and Computation: Practice and Experience, vol. 34, no. 6, p. e6750, 2022. 2, 5
2022
-
[7]
D. P. Bovet and M. Cesati,Understanding the Linux Kernel, 3rd ed. Sebastopol, CA: O’Reilly Media, 2005. 2, 3
2005
-
[8]
Analysis of the increase/decrease algorithms for congestion avoidance in computer networks,
D.-M. Chiu and R. Jain, “Analysis of the increase/decrease algorithms for congestion avoidance in computer networks,” Computer Networks and ISDN Systems, vol. 17, no. 1, pp. 1– 14, 1989. [Online]. Available: https://doi.org/10.1016/0169- 7552(89)90019-6 5
doi:10.1016/0169- 1989
-
[9]
Evaluation of OpenMP Task Scheduling Algorithms for Large NUMA Ar- chitectures,
J. Clet-Ortega, P. Carribault, and M. P ´erache, “Evaluation of OpenMP Task Scheduling Algorithms for Large NUMA Ar- chitectures,” inEuro-Par 2014 Parallel Processing, F. Silva, I. Dutra, and V . Santos Costa, Eds. Cham: Springer Inter- national Publishing, 2014, pp. 596–607. 5
2014
-
[10]
Co-operating sequential processes,
E. W. Dijkstra, “Co-operating sequential processes,” in Programming Languages: NATO Advanced Study Institute, Lectures Given at a Three Weeks Summer School Held in Villard-le-Lans, 1966, F. Genuys, Ed. London: Academic Press, 1968, pp. 43–112. [Online]. Available: https://pure.tue.nl/ws/files/4279816/344354178746665.pdf 3
arXiv 1966
-
[11]
Gropp, E
W. Gropp, E. Lusk, and A. Skjellum,Using MPI: Portable Parallel Programming with the Message-Passing Interface, 2nd ed. Cambridge, MA: MIT Press, 1999. 2, 8
1999
-
[12]
A simple capacity model of massively parallel transaction systems,
N. J. Gunther, “A simple capacity model of massively parallel transaction systems,” inProceedings of the 19th In- ternational Computer Measurement Group Conference, San Diego, CA, USA, 1993, pp. 1035–1044. [Online]. Available: https://www.perfdynamics.com/Papers/njgCMG93.pdf 8
1993
-
[13]
A General Theory of Computational Scalability Based on Rational Functions,
——, “A General Theory of Computational Scalability Based on Rational Functions,” Aug 2008, arXiv:0808.1431 [cs]. [Online]. Available: http://arxiv.org/abs/0808.1431 8
Pith/arXiv arXiv 2008
-
[14]
Slaw: A scalable locality-aware adaptive work-stealing scheduler,
Y . Guo, J. Zhao, V . Cave, and V . Sarkar, “Slaw: A scalable locality-aware adaptive work-stealing scheduler,” inPro- ceedings of the 24th IEEE International Parallel and Dis- 20 tributed Processing Symposium (IPDPS), 2010, pp. 1–12. 2, 5
2010
-
[15]
Reevaluating amdahl’s law,
J. L. Gustafson, “Reevaluating amdahl’s law,”Communica- tions of the ACM, vol. 31, no. 5, pp. 532–533, 1988. 7
1988
-
[16]
Communicating sequential processes,
C. A. R. Hoare, “Communicating sequential processes,” Communications of the ACM, vol. 21, no. 8, pp. 666–677, Aug. 1978. [Online]. Available: https://doi.org/10.1145/ 359576.359585 3
arXiv 1978
- [17]
-
[18]
Congestion avoidance and control,
V . Jacobson, “Congestion avoidance and control,” in Proceedings of ACM SIGCOMM, 1988, pp. 314–329. [Online]. Available: https://dl.acm.org/doi/10.1145/52324. 52356 5
-
[19]
The real-time producer/consumer paradigm: A paradigm for the construction of efficient, predictable real- time systems,
K. Jeffay, “The real-time producer/consumer paradigm: A paradigm for the construction of efficient, predictable real- time systems,” inProceedings of the 1993 ACM Symposium on Applied Computing. ACM, 1993, pp. 796–804. 3
1993
-
[20]
Measuring parallel processor performance,
A. H. Karp and H. P. Flatt, “Measuring parallel processor performance,”Communications of the ACM, vol. 33, no. 5, pp. 539–543, 1990. 7
1990
-
[21]
A probing al- gorithm with adaptive workload load balancing capabilities for heterogeneous clusters,
S. Kontogiannis and A. Karakos, “A probing al- gorithm with adaptive workload load balancing capabilities for heterogeneous clusters,”Journal of Computing, vol. 3, pp. 107–116, Jan 2011. [Online]. Available: https://www.researchgate.net/publication/ 3841626 A probing algorithm with Adaptive Workload Load Balancing capabilities for heterogeneous clusters 5
2011
-
[22]
Measuring transport protocol potential for energy efficiency,
S. Kontogiannis, L. Mamatas, I. Psaras, and V . Tsaous- sidis, “Measuring transport protocol potential for energy efficiency,” inWired/Wireless Internet Communications. Berlin, Heidelberg: Springer, 2005, pp. 333–342. [Online]. Available: https://doi.org/10.1007/11424505 32 5
-
[23]
ALBL: An adaptive load balancing algorithm for distributed web systems,
S. Kontogiannis and A. Karakos, “ALBL: An adaptive load balancing algorithm for distributed web systems,” International Journal of Communication Networks and Distributed Systems, vol. 13, no. 2, pp. 144–168, 2014. [Online]. Available: https://doi.org/10.1504/IJCNDS.2014. 064041 5
-
[24]
A probing algorithm with Adaptive Workload Load Balancing capabilities for heterogeneous clusters,
S. Kontogiannis and A. S. Karakos, “A probing algorithm with Adaptive Workload Load Balancing capabilities for heterogeneous clusters,”Journal of Computing, vol. 3, no. 7, pp. 107–116, Jul. 2011. [Online]. Available: https: //www.researchgate.net/profile/S-Kontogiannis/publication/ 236648853 A probing algorithm with Adaptive Workload Load Balancing capabi...
arXiv 2011
-
[25]
Advanced scheduling with genetic algo- rithms in supply networks,
A. Lawrynowicz, “Advanced scheduling with genetic algo- rithms in supply networks,”Journal of Manufacturing Tech- nology Management, vol. 22, no. 6, pp. 748–769, 2011. 2
2011
-
[26]
[Online]
Message Passing Interface Forum,MPI: A Message-Passing Interface Standard, Version 4.1, MPI Forum, Nov 2023. [Online]. Available: https://www.mpi-forum.org/docs/mpi- 4.1/mpi41-report.pdf 8
2023
-
[27]
Fair adaptive parallelism for concurrent transactional memory applications,
A. Mohtasham and J. Barreto, “Fair adaptive parallelism for concurrent transactional memory applications,” inProceed- ings of the 27th ACM Symposium on Parallelism in Algo- rithms and Architectures, ser. SPAA ’15. Association for Computing Machinery, 2015, pp. 68–70. 2, 5
2015
-
[28]
A comparative study of openmp scheduling algorithm selec- tion strategies,
J. H. Muller Korndorfer, A. Mohammed, A. Eleliemy, Q. Guilloteau, R. Krummenacher, and F. M. Ciorba, “A comparative study of openmp scheduling algorithm selec- tion strategies,”IEEE Access, vol. 13, pp. 151 216–151 234,
-
[29]
Openmp application programming interface version 5.2,
OpenMP Architecture Review Board, “Openmp application programming interface version 5.2,” OpenMP Archi- tecture Review Board, Nov 2021. [Online]. Available: https://www.openmp.org/wp- content/uploads/OpenMP- API-Specification-5-2.pdf 2, 4
2021
-
[30]
A comparison of processes and threads cre- ation,
M. Sysel, “A comparison of processes and threads cre- ation,” inSoftware Engineering Perspectives in Intelligent Systems, ser. Advances in Intelligent Systems and Comput- ing, R. Silhavy, P. Silhavy, and Z. Prokopova, Eds., vol
-
[31]
Springer, Cham, 2020, pp. 990–997. 2, 3
2020
-
[32]
Automatic openmp loop scheduling: A combined compiler and runtime approach,
P. Thoman, K. Raffenetti, and T. Fahringer, “Automatic openmp loop scheduling: A combined compiler and runtime approach,” inOpenMP in a Heterogeneous World, ser. Lec- ture Notes in Computer Science. Springer, 2012. 2, 4
2012
-
[33]
Investigating High- Performance Computing of Matrix Multiplications us- ing Processes, Threads, OpenMP, and MPI: A Case Study of Experiments on X86, ARM, and ARM Clus- ters,
A. Vasileiadou, V . Gkenoudi, N. Kiose, A. Kon- stantinopoulou, G. Michou, M. Psaropa, K. Spanoudaki, M. Tsoumani, and S. Kontogiannis, “Investigating High- Performance Computing of Matrix Multiplications us- ing Processes, Threads, OpenMP, and MPI: A Case Study of Experiments on X86, ARM, and ARM Clus- ters,” Rochester, NY , Jul 2025. [Online]. Available...
2025
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.