1 Introduction↩︎

Process-based scheduling is a central perspective for heavyweight tasks executed in a Single Instruction Multiple Process (SIMP) manner. In prolific forking, the parent process is used if its PID is a first-degree descendant of the parent process, and each child process, before carrying out any assigned computation, increases the contention in an additive manner [1]. In collective forking, the parent process stores the PIDs of all spawned child processes in a vector and sets itself as a subreaper or process group leader for all children [1].

Since process forking uses Copy-on-Write (COW), the use of shared memory segments or shared memory maps is essential for task-data allocations in a SIMP manner [2]. This shared segment is considered critical, and parallel read-writes to the same memory space should be avoided or serialized using mutex locks [2]. According to [1], the bounded n-process collective forking is considered better than the prolific approach in terms of execution time for parallel tensor multiplications executed on x86_64 multi-core CPUs, where n is the number of the system’s available cores.

On ARM quad-core systems, the bounded 100-processes prolific forking performs the best [1]. Furthermore, in [1], experimentation shows that prolific forking performs better for low contention, while collective forking performs better for medium and high contention [3]. Therefore, collective forking is generally better for heavier process workloads, while prolific forking can be better for lighter workloads, especially on ARM [1]. Additionally, a collective scheduling with mutation is a genetic-algorithm (GA) scheduler in which an entire set of jobs is encoded as a collective task set, and the mutation operator randomly changes the assignment or order of selected tasks to explore better machine-load balance, lower completion time, or improved resource utilization [4].

Thread scheduling, in contrast, is more naturally associated with shared-memory execution models. In this work, rather than using the actual OpenMP runtime system, we implement several OpenMP-inspired scheduling policies—such as static, dynamic, and guided chunk allocation—strictly inside our shared-memory framework using POSIX threads and the Boost library [5], [6]. In these OpenMP-inspired policies, work is commonly distributed among threads through scheduling policies such as static, dynamic, and guided, while the runtime schedule allows the actual policy to be selected at execution time through the environment or runtime system [5], [7]. Dynamic scheduling improves load balance by assigning work to threads on demand, whereas guided scheduling starts with larger chunks and gradually reduces them to lower overhead while preserving balance [5], [7], [8].

Beyond these built-in mechanisms, adaptive thread schedulers extend these OpenMP-inspired policies by adjusting chunk sizes or task assignment decisions according to observed runtime behavior, such as thread speed, queue lengths, or processor utilization [9]. In this sense, dynamic and runtime-inspired approaches provide flexibility within this framework, while adaptive schedulers aim to improve robustness and efficiency under irregular workloads, all realized natively via Boost threads [7], [10]. For irregular applications, adaptive schedulers try to reduce both load imbalance and scheduling overhead by dynamically changing chunk sizes and enabling work stealing / task stealing when a worker becomes idle [11]. Towards this direction, Booth and Lane [12] proposed an adaptive self-scheduling method that self-manages chunk size based on a heuristic of workload variance and uses work stealing [11]. At the same time, Guo et al. introduced SLAW [13]. This adaptive work-stealing scheduler selects a scheduling policy at runtime and improves locality by restricting stealing in a structured way [13]. Together, these approaches show that adaptive chunk scheduling combined with stealing mechanisms can improve throughput and robustness compared with fixed scheduling policies, especially for irregular or imbalanced workloads [14].

2 Materials and methods↩︎

Focusing on the characteristics of processes and threads in multi-core systems, this paper evaluates the potential of different process and thread schedulers [1], [3]. The following sections present the experimental schedulers and performance evaluation metrics used in this study.

2.1 Process schedulers↩︎

Process policies primarily adapt to inherent attributes that favor high-performance computations in SIMP [1], [15]. That is a common data memory segment, a common data results segment, and a bounded pool of k processes , typically fewer than the number of CPU cores assigned to a specific workload [1]. Nevertheless, compared with threads, processes are typically heavier-weight execution units because child processes are commonly created via fork(), which uses copy-on-write memory duplication and incurs separate address-space management costs [2]. In contrast, threads execute within a shared address space and therefore usually exhibit lower creation and scheduling overhead [3].

Both the prolific and collective schedulers can be interpreted through a mitosis-like process-creation model, since child processes are created through repeated fork operations. In this analogy, each process fork represents process mitosis, in which a process duplicates itself and creates a new child process.

The difference between the two schedulers lies in their process collection policy. A prolific scheduler keeps only the direct child processes of the original main parent process. Therefore, for (n) direct fork operations issued by the main parent, the prolific scheduler manages (n) direct children and does not manage descendant-generated processes as workers.

A collective scheduler, in contrast, relies on the same mitosis-like forking mechanism, but it may keep the child processes produced during the complete forking evolution, regardless of their parent process. Since (\(n\)) fork levels may generate up to \((2^n)\) total processes, the collective scheduler may manage up to \((2^n - 1)\) child processes. Thus, both schedulers are based on process mitosis, but the prolific scheduler preserves only the main parent’s direct lineage, whereas the collective scheduler manages the wider fork-generated population.

However, gathering processes in the collective scheduler introduces additional complexity because child processes may originate from different parent processes and may therefore have different execution contexts, states, priorities, lifetimes, and resource requirements. Unlike the prolific scheduler, which tracks only the direct children of the main parent process, the collective scheduler must discover, identify, synchronize, and manage a larger and more heterogeneous population of fork-generated processes. This requires additional effort to maintain process identifiers, enforce process group IDs, use subreaper mechanisms, or store process identifiers in shared-memory lists or vectors. As a result, collective process management may increase coordination overhead and introduce synchronization delays, race conditions, orphan or zombie process management issues, and higher memory and CPU costs for termination or barrier synchronization.

The drawback of the prolific scheduler is that it manages only the direct children of the main parent process. This makes the scheduler simpler and easier to control, but it reduces the available degree of parallelism compared with a fully collective fork-generated process population and may lead to underutilization of potential workers.

The assignment of tasks among child processes should be considered part of the mapping policy. Workload decomposition corresponds to the partitioning of the original workload into distinct computational parts, represented here by worker processes. Once the workload has been divided into chunks, the scheduler applies a mapping strategy to assign each task or chunk to a specific child process and, when affinity is enabled, to a specific CPU core. In oversubscribed configurations, where the number of workers \((k)\) exceeds the number of available cores (\(N\)), worker-to-core assignment may follow a round-robin policy.

2.1.1 Bounded prolific scheduler↩︎

The bounded prolific scheduler follows a parent-centric process creation strategy in which the main process directly spawns all worker processes using fork(). Work is distributed cyclically (in a round-robin manner) among workers, assigning task \(i\) to worker \(i \bmod k\), where \(k\) denotes the number of active workers.

Because all workers are created directly by the parent, the process tree remains shallow and easy to manage. However, process creation pressure accumulates on the parent process, potentially increasing contention as the number of workers grows. The scheduler therefore favors workloads with relatively stable and balanced task distributions, where its low coordination overhead can outweigh the cost of centralized process creation.

2.1.2 Bounded collective scheduler↩︎

The bounded collective scheduler extends collective process creation by organizing worker generation under the fork mitosis operation. Instead of spawning workers linearly, each process recursively forks additional workers according to logarithmic expansion levels, reducing the depth of the spawning hierarchy. For \(k\) workers, the scheduler requires approximately \(log_2(k)\) spawning levels. This structure attempts to distribute process-creation overhead more evenly across workers and reduce parent-process contention for large worker counts.

2.1.3 Pipe Process schedulers↩︎

In this paper, an additional process scheduler for streaming workloads to processes via pipes using the producer-bounded consumers (RTP/C) paradigm is also evaluated [6], [16]–[18]. In these schedulers, workload identifiers are streamed dynamically between producer and worker processes through :

• The one-to-one scheduler uses a single communication pipe shared by all worker processes. The parent process writes tasks to the pipe, while workers read and execute the assigned tasks from the same communication channel.

• The one-to-many scheduler uses multiple communication pipes, one for each worker process. The parent process distributes tasks directly to individual workers through dedicated communication channels, allowing independent task assignment and reducing contention among workers.

• The many-to-many scheduler uses separate communication channels for task assignment and completion notifications. Tasks are distributed from the parent process to workers through write pipes, while workers report completion through dedicated done pipes, enabling bidirectional communication and improved scheduling flexibility.

Compared with static process-assignment strategies, pipe-based schedulers introduce additional IPC (Inter-Process Communication) overhead, since task identifiers must be transferred through pipe read/write operations.

However, this extra communication cost may be compensated by improved runtime balancing, especially when the workload is irregular or when workers finish their assigned tasks at different times.

Additionally, all three pipe-based schedulers are strongly affected by the selected chunk size. In this implementation, each task corresponds to one frame of the input tensor, and a chunk represents a group of consecutive frame identifiers streamed through the pipe as a single scheduling unit. Therefore, when \((chunk = 1)\), each worker receives only one frame at a time. This provides the finest scheduling granularity and usually improves load balancing, because idle workers can quickly request new work. However, it also increases the number of pipe transactions, system calls, and scheduling decisions, which may reduce efficiency when the per-frame computation is small or relatively uniform.

Larger chunk values reduce the frequency of communication through the pipes, because each worker receives a batch of frames per read operation rather than a single frame. This lowers IPC and scheduling overhead, improving efficiency when the workload is sufficiently regular. However, if the chunk size becomes too large, load imbalance may appear: some workers may receive heavier batches and continue executing while others become idle. Thus, the chunk parameter creates a trade off between communication overhead and load balance. Pipes architecture visualizations are presented at Figure 1.

2.2 Thread schedulers↩︎

In OpenMP, the schedule clause controls how loop iterations are partitioned into chunks and assigned to the threads of a team [5], [7], [8].

• With static scheduling, iterations are pre-divided into fixed-size chunks and assigned to threads in round-robin order; if no chunk size is given, the iteration space is split into approximately equal-sized chunks, usually minimizing scheduling overhead and working well for regular, balanced loops [5], [8].

• With dynamic scheduling, each thread executes one chunk and then requests another until no work remains; if no static chunk size is provided (making it chunk-based), it defaults to 1, which improves load balance for irregular workloads at the cost of higher runtime overhead [5], [8].

• With guided scheduling, threads also request chunks, but dynamically. Still, the chunk size starts larger and decreases as the number of unassigned iterations shrinks, assigned to the thread that finishes first, again defaulting to one when unspecified. This provides a compromise between the low overhead of static scheduling and the better balance of dynamic scheduling [5], [7].

In chunk-based parallel scheduling, the main scheduling policy may be static or dynamic, while the iteration space or task pool is partitioned into chunks, which are assigned to worker threads or processes; the chunk size may be fixed or adaptively adjusted at runtime based on observed workload behavior [10], [12]. In chunk-stealing policies, tasks are pre-assigned to threads using static allocation [11]. However, threads that finish first steal tasks from the working queues of other threads, mostly in a blind round-robin manner [13], [19].

Adaptive schedulers focus on system attributes and thread-based performance metrics, followed by a probing mechanism that determines the assigned task batches per thread (chunk size) or even increases the number of threads (contention increase) assigned to a specific workload [9], [14], [20].

2.3 AIMD scheduler↩︎

In this paper, the Additive Increase Multiplicative Decrease (AIMD) adaptive scheduler is introduced, following the TCP protocol’s congestion control mechanism [21]–[23]. This scheduler is an adaptive contention-aware window scheduler that controls the number of concurrently active work chunks using an additive-increase, multiplicative-decrease policy. A fixed pool of worker threads is created once, up to the maximum number of available threads or processors, and these workers remain alive throughout the execution. However, the scheduler does not allow all workers to issue work at all times. Instead, it maintains a contention window that limits the number of chunks that may be in flight simultaneously.

The AIMD policy initializes the contention window to a small bootstrap value and then gradually adjusts parallelism by assigning additional chunks as long as the real-time measured EWMA (Exponential Weight Moving Average) raw utilization remains below the configured overload threshold.

For each CPU core i, the probing monitor master process maintains a long-term arithmetic mean utilization over the completed sampling second intervals, updating it at each sample p as per core utilization U_i (p), which is the current p-probed utilization percentage of core i. This produces one persistent mean-utilization value per i core. In Linux, per-core utilization is usually calculated from the cumulative CPU-time counters exported in /proc/stat, specifically from the cpuN lines such as cpu0, cpu1, and so on. These counters are measured in 1/USER_HZ=1/100Hz jiffies (ms=10ms) since boot and include fields such as user, system, idle, and iowait.

To obtain the current utilization of core i at probe p, a monitor reads the cpu_i counters at two consecutive sampling instants, computes the delta for each field, sums the deltas to obtain the total elapsed CPU time, and then divides the busy delta time by that total. At the global many-core level, the monitor builds a combined global utilization metric based on Equation 1 .

\[\text{Ug}_p = a \cdot \max_i(\bar{U}_i) + (1 - a) \cdot \min_i(U_i(p)) \label{eq:utilization95combined}\tag{1}\]

This way it blends the most persistently busy core with the least busy core at the system level. The global utilization is then smoothed with an exponentially weighted moving average according to Equation 2 .

\[U(p) = \beta \bar{U}_p + (1 - \beta) \text{Ug}_p \label{eq:ewma}\tag{2}\]

with the first valid sample initializing the EWMA directly to the combined value. With the chosen parameters \(a=0.7\) and \(\beta=0.8\), the utilization metric gives strong-er weight to the maximum long-term per-core load than to the least-loaded current core, while also applying relatively strong smoothing, resulting in a stable, less sensitive to transient loads response that remains mainly responsive to sustained contention changes.

In this AIMD-based scheduler, the U(p) utilization serves as an immediate feedback signal to deter-mine how many task chunks may be as-signed concurrently to worker threads. If the measured U(p) utilization exceeds a configured overload threshold, the scheduler interprets this as oversubscription or excessive contention and halves the contention window. Otherwise, it applies an additive increase, incrementing the window by one thread.

As a slow-start mechanism in AIMD, when the U(p) function from Equation 2 equals zero, the contention window doubles at each chunk completion up to the processor count N, allowing it to ramp up quickly from an idle state. In this way, the scheduler seeks a stable operating point that maximizes useful concurrency while preventing overload due to excessive simultaneous chunk execution.

2.4 Adaptive chunk scheduler↩︎

To outperform the guided thread scheduler, this paper presents an adaptive chunked scheduler. Its purpose is to determine the size of each assigned chunk by combining guided-style work partitioning with runtime observations of per-thread execution speed. At the beginning, no thread has a timing history, so every thread starts with speed_factor 1̄.0, and the initial chunk is computed only from the remaining tasks as base_chunk = remaining / k, which makes the scheduler initially behave like a guided scheduler [24], [25].

After a thread completes a chunk, its execution time is measured, and the scheduler stores the total time per thread in milliseconds and the total number of chunks finished per thread. The thread’s average time per slice is then computed. It also computes a global average slice time across all threads with available history (global_avg) and then defines the per-thread speed_factor = global_avg / thread_avg.

As a result, faster-than-average threads obtain \(speed\_factor > 1\) and therefore receive larger chunks. In comparison, slower-than-average threads obtain \(speed\_factor < 1\) and receive smaller chunks, according to Equation (3 ).

\[\mathit{chunk} = \mathit{base\_chunk} \cdot \mathit{speed\_factor} \label{eq:adaptive95chunk}\tag{3}\]

with the final chunk always clamped so that \(1 \le \mathit{chunk} \le \mathit{remaining}\). Consequently, this adaptive scheduler starts like guided scheduling, adapts the chunk size based on observed thread speed, and naturally reduces chunk sizes again near the end of execution as the remaining work becomes small, thus preserving lower scheduling overhead than fully dynamic scheduling while improving load balance when thread performance is heterogeneous.

3 Metrics used↩︎

3.1 Performance and Efficiency↩︎

For a fixed workload, the performance \(P\) of an executing workload is defined as the inverse of the execution time \(T\). So, lower runtime for the scheduled workload implies higher performance, \(P = 1/T\), for the implemented policy. Over a set of \(n\) repeated executions, the maximum observed performance is denoted by \(P_{max} = \max_{i}(P_i)\), and the normalized performance or efficiency is computed as \(E_p\) with \(0 \leq E_p \leq 1\). In this context, an efficiency value of 0.8 across 10 or more experiment repetitions can be considered a good, stable performance level, as it indicates that the measured execution remains close to the best observed run.

3.2 Speedup and SEfficiency↩︎

The speedup of a parallel system, denoted by \(\sigma(N)\), is defined as the ratio of the execution time of the serial version to the execution time with \(N\) processors, according to Equation (4 ).

\[\sigma(N) = \frac{T_{serial}}{T_{parallel}(N)} \label{eq:sigma95speedup}\tag{4}\]

Equation (4 ) measures how much faster the parallel implementation of a workload on \(N\) processors is compared to the sequential one. Based on speedup, the parallel speedup efficiency (\(\sigma Efficiency\)) is defined using Equation (5 ).

\[\sigma E(N) = \frac{\sigma(N)}{N} \label{eq:se95efficiency}\tag{5}\]

Equation (5 ) expresses the effectiveness with which the available processors are utilized. An efficiency close to 1 indicates near-ideal processor utilization, while lower values indicate increasing overhead due to communication, synchronization, or load-core imbalance. In practice, \(\sigma Efficiency\) values around 0.8 or higher are usually considered very good; values near 0.6 remain acceptable. However, values below 0.4 indicate limited benefit from further parallelization.

For a system with \(N\) fixed cores, a parallel code is considered to scale well when scheduling \(k=1..K\) threads or processes leads to increasing speedup \(\sigma(k)\) and sufficiently high \(\sigma Efficiency\) (Speedup Efficiency). To provide forced core assignment per \(k\)-thread, processor affinity may be forced in a round-robin manner (if \(K > N\)). In practice, good scalability is observed when the gain from increasing \(k\) remains significant, and efficiency stays above about 0.6, with values near 0.8 indicating very good resource utilization.

3.3 Amdahl law and the effective serialization coefficient↩︎

Amdahl’s law [26] states that the speedup of a parallel program is fundamentally limited by the fraction of the code that must remain executing in a serial manner. If \(\alpha\) denotes the serial portion of mutex synchronizations and atomic operations on the workload and \(1-\alpha\) the parallelizable portion, then the theoretical speedup on \(k=N\) processors is estimated using Equation (6 ).

\[\sigma(N) = \frac{1}{\alpha + \frac{1-\alpha}{N}} \label{eq:amdahl95sigma}\tag{6}\]

This means that even if the number of \(N\) processors increases significantly, the maximum achievable speedup cannot exceed the bound imposed by the serial part of the program. Therefore, Amdahl’s law is widely used to evaluate the scalability limits of parallel codes, and schedulers boosts to estimate how much performance improvement can realistically be obtained from additional computing resources.

When estimating the serial fraction \(\alpha\) from Amdahl’s law, the efficiency relation can be written according to Equation (7 ).

\[\sigma E(k) = \frac{\sigma(k)}{k} = \frac{1}{1 + \alpha(k-1)} \label{eq:se95alpha}\tag{7}\]

which gives the estimate for \(\alpha\) using Equation (8 ).

\[\alpha = \frac{\frac{1}{\sigma E(k)} - 1}{k-1} = \frac{1 - \sigma E(k)}{\sigma E(k)(k-1)} \label{eq:alpha95estimate}\tag{8}\]

However, if the number of scheduled threads or processes \(k\) exceeds the number of available cores \(N\), then \(k\) no longer represents true hardware parallelism (unless affinity is forced), because oversubscription and excessive processing delays introduce context-switching and synchronization overhead. In that case, a better approximation is to use the effective parallelism, \(k_{eff} \approx N\) (more generally, thread affinity applies in a round robin manner and \(k_{eff} = \min(k, N)\)). Then the estimate of the serial fraction from the \(\sigma Efficiency\) is measured at the hardware limit or hardware overutilization. If \(\sigma E(k_{eff})\) is close to 0.8, indicating a relatively small serial fraction and therefore good parallel scalability up to the available \(N\) cores or even above to the \(k_{eff}\) if \(k_{eff} > N\). The \(\alpha\) estimate in that case is better than the \(\alpha\) at \(k = N\).

For consistency, all \(\sigma E(k)\) and \(\alpha(k)\) values reported in the tables of Section 6 are computed using the nominal worker count \(k\) rather than the hardware-effective \(k_{eff}\), even when \(k > N\). This convention reflects software-level parallelism as configured by the user, and intentionally exposes the efficiency collapse caused by oversubscription. The \(k_{eff}\) formulation introduced above should be understood as an alternative interpretive lens rather than the convention applied to the tabulated results.

By construction, the serial fraction \(\alpha\) in Amdahl’s law is bounded in \([0,1]\). The estimator \(\alpha=(1-\sigma E(k))/(\sigma E(k)(k-1))\) used here is the corresponding Karp–Flatt diagnostic [27] and is defined only for \(k \geq 2\). In practice, execution-time variance introduced by operating system interruptions and CPU scheduler decisions occasionally pushes the measured efficiency marginally above \(1.0\), producing small negative values of \(\alpha\) on the order of \(10^{-4}\); these do not indicate super-linear speedup but rather normal measurement noise. Conversely, when the measured speedup satisfies \(\sigma(k) < 1\) (parallel slowdown, typically from oversubscription overhead exceeding the parallelizable gain), the estimator returns formal values \(\alpha > 1\). In both cases the Amdahl decomposition does not hold, and \(\alpha\) should be read as a diagnostic indicator rather than as a meaningful serial fraction; the corresponding rows are retained for transparency.

3.4 Amdahl vs Gustafson serialization coefficient↩︎

Under Amdahl’s law, when the workload is kept fixed, even a small serial fraction can strongly limit scalability; for example, with \(N=24\) and \(\alpha=0.05\) (5% serializable code), the speedup remains far below the ideal value of 24 because the 5% of serial code becomes a bottleneck. In contrast, under Gustafson’s formulation [28], as also mentioned in Equation (9 ).

\[\sigma(N) = N - \alpha_{scaled}(N-1) \label{eq:gustafson}\tag{9}\]

Based on Equation (9 ) when execution time is approximately constant, and the problem size grows proportional to the number of processors, the parallel portion increases, and the speedup can remain close to \(N\). Therefore, Amdahl’s law is the appropriate model for fixed-size workloads, whereas Gustafson’s law better captures scalable parallel computing \(\alpha\) values (\(\alpha_{scaled}\)), when larger problems are solved with more processors. In our experiments, we use a fixed-size workload and test different workload-balancing schedulers [26], [28]. Therefore, the serial portion \(\alpha\) from Amdahl’s law is different from Gustafson’s \(\alpha\). In Amdahl’s law, \(\alpha\) usually represents the serial fraction of the original workload-code. In contrast, in Gustafson’s law, \(\alpha\) means the serial fraction of the execution time on the parallel system.

3.5 Karp-Flatt serialization coefficient↩︎

For the scheduled threads or processes on \(N\) physical cores, the Karp–Flatt metric can be used to detect or indicate scaling collapse [27]. The Karp–Flatt metric (effective serial fraction) can be used as a practical indicator of scaling collapse, provided it is interpreted as an apparent rather than purely algorithmic serial fraction.

Instead of using the oversubscribed software parallelism \(k\), one uses the effective hardware parallelism, \(k_{eff} = \min(k, N) \approx N\), and computes the Karp–Flatt metric according to Equation (10 ).

\[\varepsilon(k_{eff}) = \frac{\frac{1}{\sigma(k_{eff})} - \frac{1}{k_{eff}}}{1 - \frac{1}{k_{eff}}} \approx \alpha \label{eq:karp95flatt}\tag{10}\]

This \(\varepsilon(k_{eff})\) is an approximation for \(k=N\) to the serial part of the executed workload. If this apparent Karp–Flatt fraction increases as \(k\) grows beyond \(N\), then the program is no longer gaining useful parallelism and is instead drowning in overhead, such as context switching, synchronization, scheduling pressure, and load imbalance. This adapted formula is useful for detecting when extra software concurrency stops helping and starts hurting scalability.

3.6 Utilization↩︎

Utilization measures the fraction of the available execution time during which a workload effectively engages a resource. For each task assigned to a thread, the thread utilization can be defined and measured as the fraction of the thread’s observed lifetime during which it is engaged in useful activity. In practice, useful activity includes the user’s execution time (\(T_{user}\)), system/kernel execution time (\(T_{system}\)), and I/O wait time (\(T_{iowait}\)), while the time spent idle, either sleeping or waiting in a queue, is moved to the denominator and treated as non-productive delay. Thus, the utilization of a thread executing a task is expressed using Equation (11 ).

\[U_{thread} = \frac{T_{user} + T_{system} + T_{iowait}}{T_{user} + T_{system} + T_{iowait} + T_{idle}} \label{eq:u95thread}\tag{11}\]

where \(T_{idle}\) represents the total time the thread remains inactive due to sleep state or queue waiting. Therefore, higher utilization values indicate that the assigned task keeps the thread busy for a larger fraction of its lifetime. In contrast, lower values reveal increasing idle overhead and poorer task-to-thread allocation. This utilization metric is used by the AIMD task scheduler to assign, in real time, different batches of workload chunks.

3.7 Many-Core System Utilization↩︎

For a many-core system with \(N\) cores, the overall CPU utilization can be written as the ratio of total active core time to total available core time, using Equation (12 ).

\[U_N = \frac{\sum_{i=1}^{N} T_{active,i}}{N \cdot T_{total}} \label{eq:u95n95simple}\tag{12}\]

expressed using \(M\) processes containing threads on an \(N\)-core system:

\[U_N = \frac{\sum_{i=1}^{M} (T_{user,i} + T_{system,i} + T_{iowait,i})}{N \cdot T_{total}} \label{eq:u95n95processes}\tag{13}\]

That is, Equation 13 can be rewritten as:

\[U_N = \frac{\sum_{i=1}^{M} (T_{user,i} + T_{system,i} + T_{iowait,i})}{N \left( \max_{1 \le i \le M} t_i^{end} - \min_{1 \le i \le M} t_i^{start} \right)} \label{eq:u95n95final}\tag{14}\]

where \(t_i^{start}\) and \(t_i^{end}\) denote the start and end times of process \(i\), respectively.

3.8 Parallel Overhead Time↩︎

Let \(T_1\) the execution time on 1 core, \(T_k\) the execution time using \(k\) threads, with \(k \le N\), \(T_p\) the parallelizable code part as executed in one single core, \(T_p/k\) the execution time on \(k\) threads of the parallelizable code part, \(T_s\) the total execution time of the serial portion of the code, the intrinsic serial fraction of the workload \(\alpha\), \(1-\alpha\) the parallelizable fraction, then, the total parallel overhead \(T_{ov}(k)\) using \(k\) threads can be calculated as follows:

\[T_1 = T_s + T_p, \qquad T_k = T_s + \frac{T_p}{k} + T_{ov}(k) \label{eq:overhead95decomp}\tag{15}\]

with \(T_s = \alpha T_1\), \(T_p = (1-\alpha)T_1\) gives Equation (16 ).

\[T_{ov}(k) = T_k - \left( \alpha T_1 + \frac{(1-\alpha)T_1}{k} \right) \label{eq:overhead95final}\tag{16}\]

Using the measured speedup, the overhead can also be written as:

\[f(k) = \frac{T_{ov}(k)}{T_1} = \frac{1}{\sigma(k)} - \alpha - \frac{1-\alpha}{k} \label{eq:overhead95ratio}\tag{17}\]

Moreover, if \(\varepsilon(k) \ne \alpha\) is the Karp–Flatt metric, then:

\[T_{ov}(k) = T_1 \left( 1 - \frac{1}{k} \right) (\varepsilon(k) - \alpha) \label{eq:overhead95kf}\tag{18}\]

3.9 Distributed Systems Amdahl’s law↩︎

In a distributed system, Amdahl’s law models the speedup by separating the workload into a serial fraction \(\alpha\) and a parallel fraction \(1-\alpha\).

Suppose the system consists of \(P\) distributed nodes, and each node may maintain \(k\) processes or threads through the MPI-based execution model, giving a total of \(P_k = P \times k\) concurrent execution units. Under this assumption, the ideal speedup can be expressed using Equation 19 .

\[\sigma(P_k) = \frac{1}{\alpha + \frac{1-\alpha}{P_k}} \label{eq:dist95amdahl}\tag{19}\]

In practice, however, in distributed environments, \(\alpha\) includes not only strictly sequential computation, but also communication overhead, synchronization delays, message passing, data movement, and load imbalance among MPI processes or threads. If \(T_1\) is the sequential execution time and \(T_{P_k}\) is the execution time using \(P\) nodes with \(k\) MPI processes or threads per node, then the measured speedup is \(\sigma(P_k) = \frac{T_1}{T_{P_k}}\). Rearranging Amdahl’s law gives the effective serial fraction using Equation 20 .

\[\alpha = \frac{\frac{1}{\sigma(P_k)} \cdot P_k - 1}{P_k - 1} = \frac{\frac{P_k}{\sigma(P_k)} - 1}{P_k - 1} \label{eq:dist95alpha}\tag{20}\]

This empirical estimate is closely related to the Karp–Flatt metric, which is calculated using \(k=1\) in Equation 18 , and is particularly useful in distributed systems because it captures the overall non-scalable part of the execution. A small \(\alpha\) indicates efficient parallel execution, whereas an increasing Karp–Flatt \(\alpha\) as the number of nodes, processes, or threads grows suggests that communication and coordination overheads increasingly limit scalability.

3.10 Universal Scalability Law (USL-Gunther)↩︎

For distributed systems, a more realistic scalability model than Amdahl’s law is Gunther’s Universal Scalability Law (USL) [29], [30], since it accounts not only for serialization effects due to racing conditions in critical sections or segments, but also for contention and communication or coherence overheads separately from serialization. If the distributed platform consists of \(P\) nodes and each node maintains \(k\) MPI processes or threads [15], [31], then the total number of parallel execution units is \(N = P \times k\). The measured speedup is defined as \(\sigma(N) = \frac{T_1}{T_N}\), where \(T_1\) is the sequential execution time and \(T_N\) is the execution time with \(N\) workers. According to USL, the speedup is modeled using Equation 21 .

\[\sigma(N) = \frac{N}{1 + \alpha(N-1) + \beta N(N-1)} \label{eq:usl95sigma}\tag{21}\]

where \(\alpha\) represents the contention synchronization cost for shared resources, and \(\beta\) represents the coherence or communication cost among processes/nodes. To estimate these parameters from experimental data, one defines:

\[Y(N) = \frac{N}{\sigma(N)} - 1 \label{eq:usl95y}\tag{22}\]

which leads to the linear form of Equation 23 .

\[\frac{Y(N)}{N-1} = \alpha + \beta N = \frac{\frac{N}{\sigma(N)} - 1}{N-1} \label{eq:usl95linear}\tag{23}\]

Thus, using speedup measurements for different values of \(N\), the parameters \(\alpha\) and \(\beta\) can be obtained either from two measurements or more reliably through linear regression.

When \(\beta = 0\), the USL reduces to Amdahl’s law, while when both \(\alpha \approx 0\) and \(\beta \approx 0\), the system approaches ideal linear scaling. Finally, the distributed overhead time relative to ideal execution is given by Equation 24 .

\[\begin{align} T_{over}(N) &= T_N - \frac{T_1}{N} \\ &= \frac{T_1}{N} \left[ \alpha(N-1) + \beta N(N-1) \right] \end{align} \label{eq:usl95overhead}\tag{24}\]

Therefore in cases where \(\beta > 0\), the speedup for \(N\) processes is calculated Equation 21 .

4 Implementation Details↩︎

All schedulers were implemented in C++ and evaluated on the same row-sorting workload. The input data consist of a three-dimensional tensor of unsigned 8-bit values with dimensions \(F \times H \times W\), where \(F\) denotes the number of frames and each frame contains \(H\) rows of length \(W\). In the experiments, the workload uses tensors of size \(1000 \times 640 \times 640\) and \(10000 \times 640 \times 640\).

Each task corresponds to one frame, and the worker assigned to that task sorts all rows of that frame independently using quick sort. To ensure that all schedulers operate on identical input data, the original tensor is generated once and stored in a System V shared-memory segment. Before each scheduler execution, a separate shared-memory work copy of the original tensor is created. This prevents later schedulers from operating on data already sorted by earlier runs while preserving identical initial input across schedulers.

Although the benchmark executes the schedulers sequentially for measurement isolation, each scheduler internally processes its assigned workload in parallel using multiple worker processes or threads. The use of separate shared-memory copies guarantees that every scheduler operates on the same initial unsorted tensor while avoiding interference between consecutive experimental runs. The tensor is stored in row-major order using the indexing formula \[A[(fH+i)W+j],\]

where \(f\) is the frame index, \(i\) is the row index, and \(j\) is the column index. During sorting, each row is wrapped by a lightweight row view and sorted directly inside the corresponding memory segment without deep-copying the row data. For process-based schedulers, worker processes are created using fork(). The bounded prolific scheduler creates all workers directly from the parent process and assigns frames cyclically, so worker \(w\) executes tasks \(w, w+k, w+2k, \ldots\). CPU (Central Processing Unit) affinity can optionally be enabled, assigning workers to CPUs in a round-robin manner using sched_setaffinity(). Thread schedulers were implemented using Boost threads and shared-memory task distribution structures. Depending on the scheduling policy, workloads were assigned dynamically, through fixed-size chunks, guided chunk allocation, adaptive chunk resizing, or work-stealing mechanisms. All schedulers operated on the same frame-level row-sorting workload and shared-memory tensor representation. The AIMD scheduler additionally maintains a contention window initialized to \(\min(k, N)\), processes frames in chunks of size \(\mathrm{CHUNK} = 4\), halves the window whenever the EWMA utilization exceeds \(95\%\), and reads the EWMA value through a lock-free atomic mirror sampled once every \(32\) chunk completions.

For every scheduler family, the measured execution time begins immediately before the scheduler’s entry point is invoked and ends when the last worker completes its assigned work. Consequently, for process-based schedulers (bounded prolific, bounded collective), the measurement includes all fork() calls and child-process startup; for pipe-based schedulers, it includes pipe creation and the first read/write handshake;and for thread-based schedulers, it includes the creation and startup of the worker-thread pool. Synchronization primitives (mutexes, condition variables, barriers) used during task distribution are likewise included in the measured interval for all three families. One exception applies to the AIMD scheduler: its CPU-utilization monitor is instantiated once before any timed run and shared across repeated executions, so its one-time startup latency is excluded from the reported AIMD runtimes; this avoids penalizing AIMD for a cost unrelated to its scheduling logic. Excluded from all measurements are only the one-time steps that are common to every scheduler and unrelated to the scheduling policy itself: generation of the original tensor and allocation of the shared-memory segments. After each run, the output tensor is verified to ensure that every row is sorted in nondecreasing order.

5 Experimental Scenario↩︎

The experiments were conducted on a server equipped with four Intel Xeon X7460 processors operating at 2.66 GHz, providing a total of 24 physical cores (24 logical processing units). The system was configured with 62 GB of RAM and ran Ubuntu 18.04.6 LTS (Bionic Beaver) with Linux kernel version 4.19.29.

All benchmark applications were compiled using G++ (GCC) version 7.5.0 with the compiler flags ‘-std=c++14 -Wall -Wextra -O3 -fpermissive’, and linked against the Boost.Thread, Boost.System, Boost.Chrono, and POSIX Threads libraries. The experiments were performed on an otherwise idle system to minimize interference from background processes. No explicit CPU affinity was enforced for either processes or threads. Worker placement was managed by the default Linux scheduler, and no CPU pinning or NUMA-aware memory placement techniques were employed.

The evaluated workload consists of row-wise sorting operations on shared-memory tensors of dimensions \(1000 \times 640 \times 640\) and \(10000 \times 640 \times 640\), corresponding approximately to 0.38 GB and 3.81 GB of unsigned 8-bit data, respectively. Although the full memory footprint includes both the original tensor and its work copy (totalling 0.76 GB and 7.64 GB respectively), the reported sizes reflect only the work copy operated on by each scheduler, since the original tensor remains read-only throughout execution.

Each experiment was repeated 10 times to ensure statistical reliability and to account for operating system jitter. The reported execution metrics, including execution time and speedup, were computed using the arithmetic mean of the measured execution times across these 10 repetitions. Using the average execution time provides a realistic representation of the scheduler’s expected performance under typical system conditions. Furthermore, a strict performance threshold of 1% was applied during the comparative analysis. Execution time or speedup differences smaller than 1% fall within the margin of unavoidable environmental noise. Consequently, schedulers with performance differences below this threshold are treated as practically equivalent in those specific configurations.

The experiments evaluate both process-based and thread-based schedulers under different levels of parallelism using varying numbers of worker processes or threads \(k\). Oversubscription refers to configurations in which the number of worker entities exceeds the available logical processing units of the system. Measurements include execution time, speedup \(\sigma(k)\), speedup efficiency \(\sigma_E(k)\), and the estimated serialization factor \(\alpha(k)\). Unless otherwise stated, processor affinity was enabled using sched_setaffinity() in order to study the impact of explicit CPU binding on scheduler scalability, processor contention, and execution stability.

For every scheduler family, the measured execution time begins immediately before the scheduler’s entry point is invoked and ends when the last worker completes its assigned work. Consequently, for process-based schedulers (bounded prolific, bounded collective), the measurement includes all fork() calls and child-process startup; for pipe-based schedulers, it includes pipe creation and the first read/write handshake; and for thread-based schedulers, it includes the creation and startup of the worker-thread pool. Synchronization primitives (mutexes, condition variables, barriers) used during task distribution are likewise included in the measured interval for all three families. One exception applies to the AIMD scheduler: its CPU-utilization monitor is instantiated once before any timed run and shared across repeated executions, so its one-time startup latency is excluded from the reported AIMD runtimes; this avoids penalizing AIMD for a cost unrelated to its scheduling logic. Excluded from all measurements are only the one-time steps that are common to every scheduler and unrelated to the scheduling policy itself: generation of the original tensor and allocation of the shared-memory segments.

This measurement methodology was adopted to ensure that the reported results reflect not only the computational cost of the row-wise sorting workload, but also the practical overhead introduced by each scheduling strategy. Therefore, the comparison captures the end-to-end behavior of each scheduler under realistic execution conditions, including worker creation, task dispatching, inter-process or inter-thread coordination, synchronization, and load-balancing decisions.

5.1 Scenario I. Process parallelism↩︎

Process-based scheduling is evaluated for heavyweight tasks. Prolific forking increases contention additively, while collective forking uses a subreaper/leader model [1]. Due to Copy-on-Write (COW), shared memory is essential for SIMP task allocation. The bounded prolific and bounded collective schedulers with processor affinity are presented in Tables 1 and 2, with corresponding speedup plots in Figures 2 and 3. Their unbounded variants without affinity appear in Tables 3 and 4, with corresponding plots in Figures 4 and 5.

The three pipe-based scheduler designs are presented in Tables 5, 6, and 7, using a chunk size of one, while an indicative scenario examining the optimal chunk size is presented in Tables 8 (for \(L=1000\)) and 9 (for \(L=10000\)) using chunk sizes of \(12\) and \(105\), respectively. Figures 6 (for \(L=1000\)) and [fig:pipes95L10000] (for \(L=10000\)) present the speedup results with respect to \(k\) for chunk sizes of one. The configuration used was 1-byte unsigned 2D tensors with tasks of row sorting using the quick sort method. In these experiments, the number of processes \(k\) is equal to the number of cores \(N\), and strict affinity was enforced, ensuring each process is assigned to a specific core.

In pipe experiments, the chunk size is a critical control parameter as it determines the number of frame identifiers transmitted through a pipe per scheduling operation. A chunk size of one provides the finest granularity for load balancing but increases pipe read/write operations, system calls, and scheduling decisions. Conversely, larger chunks reduce communication overhead by transferring more work per pipe transaction; however, they may introduce tail imbalance if one process receives a heavier workload batch while others become idle. Through extensive experimentation with various chunk sizes, we concluded that the optimal chunk size was \(12\) for the \(L=1000\) scenario and \(105\) for the \(L=10000\) scenario, as these values maximized performance in terms of execution time (ms).

Based on the presented results, several key observations emerge regarding the performance characteristics of the three pipe-based scheduler designs. For the one-to-one scheduler (Table 5), we observe near-ideal scaling up to k=16 for both L=1000 and L=10000, with speedup values of 15.875 and 16.012 respectively, corresponding to efficiency values of 0.992 and 1.001. This indicates excellent parallelization efficiency when the number of processes does not exceed the available cores. However, a significant performance degradation occurs when k exceeds the number of physical cores (N=24), with speedup dropping to approximately 23.6 for k=32, resulting in efficiency values of only 0.738-0.741. This degradation is attributed to processor oversubscription, where multiple processes compete for the same core resources, leading to increased context switching and communication overhead.

The one-to-many scheduler (Table 6) exhibits a distinct performance pattern. For L=1000 with k=24, speedup reaches 22.753 with an efficiency of 0.948, while for L=10000 the corresponding values are 23.270 and 0.970. The most striking observation is the dramatic performance collapse at k=32, where speedup plummets to 15.335 for L=1000 and 15.909 for L=10000, representing efficiencies of only 0.479 and 0.497 respectively. This severe degradation suggests that the one-to-many communication pattern becomes particularly susceptible to resource contention and communication bottlenecks when the system is oversubscribed, likely due to the asymmetric communication patterns where a single producer feeds multiple consumers.

The many-to-many scheduler (Table 7) demonstrates the most robust performance across all configurations. For L=10000, this scheduler achieves nearly perfect scaling up to k=16 with \(\sigma(k)\)=16.004, and maintains high efficiency at k=24. Even under oversubscription at k=32, the many-to-many scheduler maintains speedup of 23.608 with efficiency 0.738, comparable to the one-to-one design but significantly outperforming the one-to-many scheduler. This superior performance can be attributed to the balanced communication patterns inherent in the many-to-many design, which distributes the communication load more evenly across all participating processes.

The comparative analysis in Tables 8 and 9 for k=24 processes with optimized chunk sizes reveals interesting trade-offs. For L=1000 with chunk size 12, all schedulers achieve similar performance, with speedup values ranging from 20.560 to 20.834 and efficiencies between 0.857-0.868, suggesting that larger chunk sizes help amortize communication overhead regardless of the scheduling pattern. For L=10000 with chunk size close to 100, the performance differences become more pronounced: the many-to-many scheduler achieves the highest speedup value of 23.255, closely followed by one-to-one at 23.235 and one-to-many at 23.209. The slightly better performance of the many-to-many scheduler indicates that balanced communication patterns become increasingly beneficial as problem size grows, since a many-to-many communitation allows the producer to balance the tasks in bigger batches (larger chunk sizes) that helps reduce the frequency of communications and provide a more time consuming task-effort per core. This is an indication for a fair task assignment scheduler for heterogenous processing workers.

*Note: Values of \(\sigma E(k) > 1\) (arising when speedup \(\sigma(k) > k\)), observed here and in subsequent configurations, indicate super-linear speedup. This is typically caused by the subdivided workloads fitting more efficiently into lower-level CPU caches (L1/L2) during parallel execution.

The speedup results presented in Figures 6 and [fig:pipes95L10000] for chunk size one visually confirm the trends observed in the tabular data. For both L values, all schedulers show near-linear speedup up to k=16, with the many-to-many scheduler maintaining the best scaling characteristics. The figures clearly illustrate the performance collapse of the one-to-many scheduler at k=32, while the one-to-one and many-to-many schedulers show more graceful degradation. Notably, the performance patterns are remarkably consistent across both L=1000 and L=10000, suggesting that the observed scheduler behavior is primarily determined by the communication patterns and resource allocation strategies rather than the problem size itself. The use of processor affinity ensures that the measured performance reflects the true characteristics of each scheduling design without the confounding effects of process migration.

Based on the comprehensive analysis, the many-to-many (pipe M:M) scheduler emerges as the superior choice for distributed task assignment across all tested configurations. This scheduler consistently demonstrates the most robust performance characteristics, achieving nearly ideal scaling (\(\sigma E(k) \ge 0.982\)) up to the physical core count (k=24) for both problem sizes, and maintaining the highest efficiency (0.969 for L=10000) even under optimized chunk sizes. The many-to-many design’s balanced communication patterns effectively distribute the workload across all participating processes, minimizing bottlenecks and acquiring heterogenous loads. This is particularly evident in the oversubscription scenario (k=32) where the many-to-many scheduler achieves a 48% improvement over the one-to-many scheduler’s performance, demonstrating superior resilience to resource contention.

5.2 Scenario II. Threads parallelism↩︎

Thread scheduling (OpenMP, Pthreads) is tested with \(L = 1000, 10000\) tensors (\(640 \times 640\)) and row sorting (\(N = 24\)). The static, dynamic, guided, chunk, chunk-stealing, AIMD, and adaptive chunk schedulers are presented in Tables 10 through 16 and Figures 7 through 13 with corresponding speedup plots. These figures show how each policy reacts as \(k\) increases from low parallelism to the hardware limit and then into oversubscription. Static scheduling (Table 10 and Figure 7) assigns work in predetermined portions and therefore has very low scheduling overhead, but faces difficulty if some frames take longer to sort. Dynamic scheduling (Table 11 and Figure 8) assigns a new task to a thread whenever it finishes its previous one, improving load balance at the cost of more synchronization between workers. Guided scheduling (Table 12 and Figure 9) begins with larger chunks and gradually decreases the chunk size, in order to combine the low overhead of static scheduling with the balancing behavior of dynamic scheduling. The chunk and chunk-stealing schedulers further test the effect of fixed-size task grouping in the thread family. In the chunk scheduler (Table 13 and Figure 10), frames are assigned in fixed batches, using a chunk size of 10 for \(L=1000\) and a chunk size of 100 for \(L=10000\). Smaller chunks improve balancing but increase mutex lock/scheduler activity, while larger chunks reduce synchronization and thus, risk leaving idle threads near the end. Chunk stealing (Table 14 and Figure 11) starts from chunk-based assignment but allows idle threads to take remaining work from other workers, improving performance under imbalance, while adding queue management and stealing overhead. The AIMD (Table 15 and Figure 12) and adaptive chunk (Table 16 and Figure 13) schedulers extend this idea by changing the amount of active or assigned work according to runtime feedback, but the figures show how this extra control logic doesn’t improve speedup compared to the simpler dynamic and guided approaches in our implementation.

6 Experimental Results and Discussion↩︎

6.1 Process-Based Scheduler Results↩︎

Among the process-based schedulers evaluated in Scenario 5.1, the bounded prolific and bounded collective schedulers both exhibited strong scalability near the hardware parallelism limit. The bounded prolific scheduler achieved the highest process-family result, reaching speedup efficiency close to 0.96 for the larger workload at k = 24. The bounded collective scheduler followed closely, confirming that both fork-based process strategies can scale well when the workload is sufficiently large and the number of workers remains close to the available logical processors.

The bounded prolific scheduler slightly outperformed the collective approach in the reported measurements because its parent-centered process management and cyclic task assignment introduce less coordination overhead. More specifically, for L = 1000, the prolific scheduler was approximately 1.5% better than the collective scheduler, while for L = 10000, it was approximately 2.4% better. Overall, the prolific scheduler was approximately 2% better than the collective scheduler. The collective scheduler distributes process creation more broadly, which can reduce parent-side spawning pressure, but it also requires additional process tracking and synchronization. For the evaluated row-sorting workload, this extra coordination cost slightly reduced its advantage.

The three pipe-based schedulers provide a different process-execution model. Instead of assigning all work statically at process creation time, they stream task identifiers to worker processes through inter-process communication channels. This makes the pipe schedulers more dynamic than the bounded prolific and bounded collective schedulers, but it also introduces pipe read/write overhead and more scheduling decisions during execution. The one-to-one pipe scheduler uses a single shared communication pipe from the producer to all workers. Its advantage is simplicity: the parent writes work identifiers into one channel, and workers consume tasks from that shared stream. However, because all workers compete for the same pipe, contention may appear when the number of workers increases. This design is therefore simple and stable, but less flexible under high concurrency.

The one-to-many pipe scheduler uses one communication pipe per worker. This removes much of the worker-side contention on a single shared pipe because the parent can send work directly to a specific process. Its performance depends strongly on how well the parent distributes chunks among workers. If the distribution is balanced, dedicated pipes reduce communication conflicts. If the distribution is imperfect, however, some workers may finish earlier while others still hold larger remaining chunks.

The relative ranking among pipe schedulers depends on the workload size. For L=1000, the one-to-one pipe scheduler gives the best result among the pipe family, marginally outperforming the many-to-many pipe scheduler at k=24, with a difference of approximately 1.7%. For L=10000, the many-to-many pipe scheduler achieves the best result, marginally outperforming the one-to-one pipe scheduler at k=24,with a difference of approximately 0.1%. Overall, performance differences within the pipe family are small, and the choice between the one-to-one and many-to-many designs depends primarily on the workload size.

The many-to-many pipe scheduler’s advantage in larger workloads (L=10000) comes from using separate communication paths for task assignment and completion notification. Apart from receiving tasks , workers also report when they finish. This feedback gives the parent process a more accurate runtime view of worker availability, allowing it to push new tasks toward idle workers more quickly. As workload size increases, the benefits of this feedback loop outweigh its added IPC complexity. For smaller workloads (L=1000), however, the simpler one-to-one pipe scheduler design avoids the extra coordination overhead and achieves slightly better results.

Chunk size is a central factor in the performance of all three pipe-based schedulers. In this workload, each task corresponds to one tensor frame, and a chunk is a group of consecutive frame identifiers sent through the pipe as one scheduling unit. With a small chunk size, the scheduler has fine-grained control: workers receive smaller batches, finish them quickly, and can be reassigned new work with minimal waiting. This improves load balance, especially when some frames take longer to sort than others. The cost is that the system performs more pipe writes, pipe reads, context switches, and scheduling decisions.

With a larger chunk size, each pipe transaction transfers more useful work. This lowers IPC overhead because the parent communicates less frequently with the workers. Larger chunks can therefore improve performance when the workload is regular and each chunk has similar cost. However, if the chunk becomes too large, load imbalance appears: one worker may receive a heavy batch and continue executing while other workers become idle. Thus, the chunk parameter creates a direct trade off between communication overhead and load-balancing accuracy. The best chunk size is not simply the smallest or largest value; it is the value that keeps pipe traffic low without allowing long idle periods.

Overall, the process-based results show that when the same task size is used per worker, specifically one frame per worker, bounded prolific scheduling is the strongest of the classic fork-based approaches. However, for the pipe implementations, the most important performance factor turned out to be the discovery of the best task size. In the L = 1000 scenario, the best task size was 12 frames per worker, while in the L = 10000 scenario, it was 105 frames per worker. The prolific scheduler wins through simplicity and low coordination overhead, while the many-to-many pipe scheduler wins inside the pipe family because its completion feedback mechanism gives it better runtime adaptability.

6.2 Thread-Based Scheduler Results↩︎

Among the thread-based schedulers evaluated in Scenario 5.2, the dynamic scheduler achieved the strongest overall performance. For L = 1000, the guided scheduler was approximately 0.3% better than the dynamic scheduler. For L = 10000, the dynamic scheduler was approximately 1.4% better than the chunk-steal scheduler.

Dynamic scheduling performs well because threads repeatedly request new work as soon as they finish their previous task. This keeps the worker pool active and limits idle time, especially when the execution cost of individual frames varies. Its main cost is synchronization on the shared scheduling state, but for this workload the overhead remains small enough that the scheduler maintains near-ideal scaling up to the hardware parallelism limit.

Guided scheduling also performs strongly because it starts with larger chunks and gradually reduces chunk size as the remaining work decreases. This reduces scheduling overhead during the early part of execution, while still improving load balance near the end. In practice, guided scheduling behaves like a compromise between static and dynamic scheduling: it avoids the high scheduling frequency of fully dynamic work distribution while still preventing the severe tail imbalance that can appear in purely static assignment.

The static scheduler performs well when the workload is large and regular, but it is less robust when work distribution becomes uneven. Since each thread receives a predetermined portion of the workload, any imbalance in task cost can leave some threads idle while others continue working. This explains why static scheduling can be competitive in some cases but does not match the overall robustness of dynamic scheduling.

The chunk scheduler reduces scheduling overhead by assigning groups of frames at a time. Its behavior depends heavily on the chosen chunk size. Small chunks improve balance but increase scheduling overhead, while large chunks reduce synchronization frequency but risk idle workers near the end of execution. This mirrors the chunk size trade off observed in the pipe schedulers, although the cost here is thread synchronization rather than pipe-based IPC.

The chunk-stealing scheduler attempts to correct imbalance by allowing idle workers to steal work from others. While this improves theoretical load balance, it also introduces queue-management and stealing overhead. For the evaluated row-sorting workload, the extra synchronization cost reduces its practical advantage, although it remains highly competitive for the larger L = 10000 workload.

The guided scheduler and the adaptive chunk scheduler (ACS) produce very similar results throughout the experiments. At \(k=24\), guided reaches \(\sigma=23.497\) for \(L=1000\) and \(\sigma=23.662\) for \(L=10000\), while ACS reaches \(\sigma=23.495\) and \(\sigma=23.565\) respectively. These differences are well within the 1% noise threshold. The reason guided remains competitive is that the evaluated workload — row-wise quicksort on frames of identical dimensions — is sufficiently homogeneous in task cost that the per-thread speed-factor adaptation performed by ACS provides little practical benefit. The source of irregularity is the data-dependent behavior of quicksort (different frames contain differently ordered data and therefore take slightly different times to sort), but this variation is small and not correlated across consecutive frames; as a result, the guided scheduler’s decreasing-chunk strategy already captures most of the available load-balancing gain without the additional measurement and adaptation overhead of ACS.

The AIMD scheduler is introduced as an exploratory, contention-aware policy designed to ensure fairness and prevent system overload over long-running executions in multi-tenant platforms. It regulates concurrency through a contention window controlled by processor-utilization feedback. However, the results show it is generally weaker than the dynamic and guided schedulers for the current benchmark. This underperformance can be attributed to two main factors. First, the experimental scenario executes in an isolated environment without unpredictable external background contention; therefore, the AIMD throttling mechanism occasionally restricts active worker threads when the system could otherwise safely sustain full concurrency, effectively wasting available CPU cycles. Second, to enforce this contention window, the scheduler relies on heavier synchronization mechanisms—specifically condition variables—to continuously block and wake threads based on the number of in-flight chunks. This introduces significant synchronization and wake-up overhead compared to the simple, fast mutex locks used by the dynamic scheduler. Consequently, while AIMD provides a valuable safety mechanism for shared systems, its conservative throttling and synchronization overheads make it suboptimal for dedicated, high-performance batch processing.

6.3 Affinity versus Non-Affinity Execution↩︎

Processor affinity did not consistently produce significant performance improvements across all evaluated configurations. For several workloads, affinity-enabled and non-affinity executions exhibited comparable execution times, suggesting that the Linux scheduler already performs effective runtime load balancing and processor migration for the evaluated workloads. This behavior is consistent with the design of modern work-stealing and process-based schedulers, which are capable of approximating near-optimal core utilization without explicit affinity constraints under low-to-moderate contention.

Nevertheless, affinity remained beneficial in scenarios where execution reproducibility and reduced variability were prioritized over raw throughput. In particular, affinity-enabled configurations demonstrated more consistent worker-to-core placement, which is especially relevant for higher worker counts and process-based schedulers operating under deterministic timing requirements. In oversubscribed configurations, affinity also served to limit unnecessary processor migrations and cache invalidations, thereby preserving cache locality and reducing the associated performance degradation.

6.4 Scalability and Serialization Analysis↩︎

In this work, scalability is defined as the ability of a scheduler to maintain increasing speedup as the contention level approaches the affinity-supported limit. The measured speedup and efficiency values indicate that several schedulers scaled efficiently up to the hardware parallelism limit of N = 24 processing units, with performance gains remaining consistent across increasing worker counts within this range.

As worker counts exceeded the available hardware parallelism, oversubscription effects increasingly introduced synchronization pressure, context-switching overhead, and cache-locality degradation. These factors collectively resulted in reduced parallel efficiency and increased estimated serialization fractions \(\alpha\), reflecting the rising proportion of execution time attributed to non-parallelizable overhead, including lock contention and inter-core communication latency.

Schedulers with lower synchronization and communication overhead generally maintained better scalability under increasing concurrency levels, particularly for the regular frame-level row-sorting workload evaluated in this study.

6.5 Results Summary↩︎

Combining the measurements from Section 5 with the analysis of Sections 6.1 and 6.2, the best schedulers per family and their relative performance are summarized below.

• Best fork-based process scheduler: Bounded prolific.

• Best pipe process scheduler:

  • For \(L=1000\): one-to-one pipe scheduler (small number of low computational tasks).

  • For \(L=10000\): many-to-many pipe scheduler (big number of low and medium computational tasks).

• Best overall process scheduler (fork and pipe combined):

  • For \(L=1000\), \(k=24\): one-to-one pipe (\(\sigma=23.649\)), exceeding bounded prolific (small number of low computational tasks) (\(\sigma=22.394\)) and also marginally exceeding the best thread scheduler (dynamic, \(\sigma=23.421\)).

  • For \(L=10000\), \(k=24\): many-to-many pipe (\(\sigma=23.580\)), exceeding bounded prolific scheduler. (\(\sigma=22.940\)) and also marginally exceeding dynamic (\(\sigma=23.706\) – dynamic scheduler leads at \(L=10000\)).

• Best thread scheduler: dynamic (particularly strong under oversubscription) with guided as a near-equal alternative at \(k=24\).

6.5.0.1 Process-thread schedulers comparison:

• \(k=24\), \(L=1000\): one-to-one pipe (\(\sigma=23.649\)) vs.dynamic (\(\sigma=23.421\)); pipe leads by \(\approx 1.0\%\).

• \(k=24\), \(L=10000\): dynamic (\(\sigma=23.706\)) vs.many-to-many pipe (\(\sigma=23.580\)); thread leads by \(\approx 0.5\%\).

• \(k=32\), \(L=1000\): dynamic (\(\sigma=23.518\)) vs.one-to-one pipe (\(\sigma=23.715\)); pipe leads by \(\approx 0.8\%\).

• \(k=32\), \(L=10000\): dynamic (\(\sigma=23.358\)) vs.many-to-many pipe (\(\sigma=23.608\)); pipe leads by \(\approx 1.1\%\).

These differences are all within or close to the 1% noise threshold, confirming that at hardware parallelism (\(k=24\)) and at modest oversubscription (\(k=32\)), the best pipe schedulers and the best thread schedulers perform essentially on par. The clear differentiation appears only for fork-based process schedulers (bounded prolific and collective), which are substantially outperformed under oversubscription.

6.5.0.2 Process-Pipe schedulers comparison:

• \(k=24\), \(L=1000\): one-to-one pipe is \(\approx 5.6\%\) better than bounded prolific.

• \(k=24\), \(L=10000\): many-to-many pipe is \(\approx 2.8\%\) better than bounded prolific.

• \(k=32\), \(L=1000\): one-to-one pipe is \(\approx 53\%\) better than bounded prolific.

• \(k=32\), \(L=10000\): many-to-many pipe is \(\approx 48.5\%\) better than bounded prolific.

Across all evaluated configurations, dynamic thread scheduling and the best pipe schedulers match each other closely at hardware parallelism (\(k=24\)), and both substantially outperform fork-based process schedulers under oversubscription (\(k=32\)), confirming that lightweight execution units coordinated through dynamic IPC are preferable for the evaluated shared-memory row-sorting workload.

Table 17 presents a consolidated view of the absolute execution times (\(T_1\) and \(T_{24}\)) alongside the achieved speedup for the best-performing process and thread-based schedulers at hardware parallelism (\(k=24\)). While relative metrics like speedup and efficiency highlight the theoretical scalability of each approach, raw execution times provide necessary context regarding the absolute computational scale and the practical impact of system overheads (e.g., process forking, pipe communication, and mutex synchronization). As observed in the absolute parallel runtimes (\(T_{24}\)), the one-to-one pipe scheduler achieves the best overall performance for the smaller workload (\(L=1000\)), finishing marginally faster than the dynamic thread scheduler. Conversely, for the larger workload (\(L=10000\)), the dynamic thread scheduler achieves the lowest absolute execution time, demonstrating superior efficiency and lower overhead as the workload size increases.

6.6 Limitations of the Experimental Workload↩︎

While the evaluated schedulers demonstrate clear performance trends, it is important to acknowledge that these conclusions are drawn from a specific and relatively narrow workload. The experimental scenario relies entirely on row-wise quick-sort operations applied to uniform three-dimensional tensors (where every frame has identical \(640 \times 640\) dimensions).

Because the computational geometry of the assigned tasks is perfectly uniform, the source of workload irregularity is not structural (i.e., varying task sizes), but rather algorithmic. Specifically, the execution time of the quick-sort algorithm is highly data-dependent, varying with the initial permutation and randomness of the values within each row. This introduces fine-grained, unpredictable, stochastic timing variations across frames.

The observed advantage of the dynamic and guided thread schedulers must be interpreted within this context. These schedulers excel here because they effectively smooth out this specific type of data-driven, micro-irregularity without incurring high overhead. For workloads with severe structural irregularities (e.g., sparse matrix processing or processing frames of dynamically varying resolutions), or conversely, for workloads with strictly predictable and constant computational costs (e.g., simple vector addition), the relative performance and ranking of these schedulers might differ. Consequently, broadening these conclusions to entirely different computational patterns remains a subject for future investigation.

7 Conclusion↩︎

This paper compared several process-based, pipe-based, and thread-based schedulers for a shared-memory row-sorting workload on an x86-64 many-core platform using large three-dimensional unsigned 8-bit tensors stored in System V shared memory.

The central finding is that dynamic and guided thread scheduling and selected pipe schedulers (one-to-one for \(L=1000\), many-to-many for \(L=10000\)) perform very close to the ideal speedup up to \(k=24\). At hardware parallelism, the best pipe and best thread schedulers are essentially on par, with differences below 1%. Oversubscription (\(k=32\)) penalizes fork-based process schedulers (bounded prolific and collective) far more strongly than either thread or pipe schedulers: fork-based speedup collapses to roughly \(15\)–\(16\) at \(k=32\), while dynamic threads and one-to-one/many-to-many pipes sustain speedup above \(23\).

Among fork-based process schedulers, bounded prolific slightly outperforms bounded collective due to simpler process management and lower coordination overhead. Pipe schedulers remain competitive and can match or marginally exceed thread schedulers at \(k=24\), particularly with tuned chunk sizes; the many-to-many design benefits from completion feedback at larger workload sizes. Thread-based schedulers are preferable overall because they avoid the heavier costs of process creation and inter-process communication; process and pipe schedulers remain valuable when isolation, explicit communication, or distributed-style execution is required.

Future work includes extending the evaluation to distributed MPI systems, NUMA-aware scheduling strategies, heterogeneous CPU/GPU environments, larger or more irregular workloads, and chunk-based pipe schedulers using chunk sizes greater than one task per communication operation.

References↩︎