AI summaryⓘ
The authors studied how well different ways of organizing tasks (using processes vs. threads) work for sorting large 3D data on many-core computers. They tested various scheduling methods that decide how tasks are shared and balanced among workers. Their experiments showed that thread-based schedulers generally perform best, especially dynamic and guided approaches. However, some process-based schedulers that use pipes to communicate tasks also scale well and are useful in certain scenarios like managing complex workloads or avoiding resource conflicts. Overall, lightweight thread scheduling is best for shared-memory sorting, but process-based methods still have practical advantages in some cases.
process-based schedulingthread-based schedulingmany-core systemsquick-sortshared memoryload balancingpipe-based communicationAIMD schedulingdynamic schedulingcontention management
Authors
Mejgan Dedaj, Argyro Gailla, Theofanis Ioannou, Stamatia Kastrinaki, Hermione Kimpouropoulou, Dimitrios Kontodimos, Kleopatra Kontogianni, Sotirios Kontogiannis, Michail Panagiotidis Kannas, Anastasia Papouda, Anna Maria Sidiropoulou, George Tavridis
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.