# Optimal Scheduling Algorithms for Software-Defined Radio Pipelined and Replicated Task Chains on Multicore Architectures

Diane Orhan, Laércio Lima Pilla, Denis Barthou, Adrien Cassagne, Olivier Aumage, Romain Tajan, Christophe Jégo, Camille Leroux

<figure><img src="image_1.png" /></figure>

## To cite this version:

Diane Orhan, Laércio Lima Pilla, Denis Barthou, Adrien Cassagne, Olivier Aumage, et al. Optimal Scheduling Algorithms for Software-Defined Radio Pipelined and Replicated Task Chains on Multicore Architectures. Journal of Parallel and Distributed Computing, In press, pp.105106. 10.1016/j.jpdc.2025.105106. hal-04228117v2

HAL Id: hal-04228117

https://hal.science/hal-04228117v2

Submitted on 14 Mar 2025

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Optimal Scheduling Algorithms for Software-Defined Radio Pipelined and
Replicated Task Chains on Multicore Architectures

Diane Orhan¹,ª,*, Laércio Lima Pilla¹,ª, Denis Barthou¹,ᵇ, Adrien Cassagne¹,ᶜ, Olivier Aumage¹,ª, Romain Tajan¹,ᵈ, Christophe Jégo¹,ᵈ, Camille Leroux¹,ᵈ

ªUniv. Bordeaux, CNRS, Bordeaux INP, INRIA, LaBRI, UMR 5800, 200 avenue de la Vieille Tour, Talence, 33405, France

ᵇBordeaux INP, University of Bordeaux, Talence, 33405, France

ᶜLIP6, Sorbonne Université, CNRS, UMR 7606, 4 place Jussieu, Paris, 75252, France

ᵈUniv. Bordeaux, CNRS, Bordeaux INP, IMS, UMR 5218, 351 Cours de la Libération, Talence, 33405, France

**Abstract**

Software-Defined Radio (SDR) represents a move from dedicated hardware to software implementations of digital communication standards. This approach offers flexibility, shorter time to market, maintainability, and lower costs, but it requires an optimized distribution tasks in order to meet performance requirements. Thus, we study the problem of scheduling SDR linear task chains of sateless and stateful tasks for streaming processing. We model this problem as a pipelined workflow scheduling problem based on pipelined and replicated parallelism on homogeneous resources. We propose an optimal dynamic programming solution and an optimal greedy algorithm named OTAC for maximizing throughput while also minimizing resource utilization. Moreover, the optimality of the proposed scheduling algorithm is proved. We evaluate our solutions and compare their execution times and schedules to other algorithms using synthetic task chains and an implementation of the DVB-S2 communication standard on the AFF3CT SDR Domain Specific Language. Our results demonstrate how OTAC quickly finds optimal schedules, leading consistently to better results than other algorithms, or equivalent results with fewer resources.

**Keywords:** Pipelined workflow scheduling, Replication, Software-Defined Radio, Optimal algorithm, Linear task chains, Streaming.

# 1. Introduction

Digital communication standards have traditionally been implemented on dedicated hardware in order to meet real-time constraints. These implementations achieve high performance and low energy consumption at the expense of flexibility and high development costs [1]. Such issues have been increasing in importance as communications standards, such as the 5G mobile standard, evolved to handle usage profiles in a versatile manner [2], fueling a transition from hardware to software implementations.

Software deployments offer flexibility, maintainability, shorter time to market, and lower costs (e.g., shared hardware). This approach is expressed in **Software-Defined Radio (SDR)**, where components of a digital communication chain responsible for the physical layer (layer 1 in the OSI model) and the media access control sublayer (layer 2) are implemented in software and run on standard processors or reconfigurable hardware [3, 4, 5, 6]. SDR is a growing field with applications in research, industry, and military with a market value of 25B USD in 2022 [7]. One of its main challenges lies in the distribution of its computations over the available hardware (e.g., multicore architecture), in line with required performance.

The computations of digital communications are im-

*Corresponding author: Tel.:+33 5 24 57 41 19
Email address: diane.orhan@inria.fr (Diane Orhan)
plemented as a series of *tasks* connected in a directed
graph (linear *chains*, in our context). These tasks can
be grouped and partitioned in a sequence of stages in a
**pipeline** with each stage using its own core to improve
throughput. Nonetheless, pipelining alone may not be
sufficient to maximally use the available hardware par-
allelism. This limitation can be overcome by **replicating**
some pipeline stages on different cores and distributing
frames in a round-robin fashion among replicas [8]. Still,
replication is limited to stages composed of *stateless*<fnref n="1" /> tasks
only, to ensure consistency with the original sequential
task execution.

The combination of pipelining and replication provides a framework to achieve high throughput [3], and it can also provide economic and (indirect) environmental benefits. For instance, by making the best use of the available multicore hardware on antennas, one may avoid or delay the expenses and emissions related to acquiring new hardware to handle new digital communication standards. However, finding the best schedule is challenging. Automatic approaches have so far been limited to: Applying only pipelining [9, 10] or replication [11]; Using Integer Linear Programming [12, 8, 13], with potential prohibitive computation time; Using heuristics [12, 14] and trading optimality for a faster computation time; Or avoiding these decisions altogether by assigning a single task per thread and leaving the scheduling work to the operating system [15].

We propose a fast, optimal algorithm, named OTAC,
for scheduling pipelined and replicated task chains on
homogeneous computing resources for SDR. The sched-
ule first maximizes throughput and then minimizes the
number of required cores, based on the characteristics of
the communication chain and a given maximum number
of cores. Although we focus on SDR, we believe these
ideas can be useful for other applications, such as large
AI models [16] and high-throughput stream processing
for Astronomy [17, 18]. Our main contributions are the
following:

★ We provide a formulation of this throughput opti-
mization problem, and we propose a (slow) dynamic

programming solution to it (Section 3).

★ We propose a new greedy algorithm named OTAC, and we prove its optimality (Section 4).

★ We evaluate their execution time and their schedules using synthetic task chains and an implementation of the Digital Video Broadcasting – Second Generation (DVB-S2) standard [19] (Section 5).

The remaining sections are organized as follows: Sec-
tion 2 describes related work, and Section 6 provides con-
cluding remarks.

## 2. Context and Related Work

We organize this discussion in four parts: an example
that illustrates the problem, pipelined workflow scheduling
problems, scheduling solutions for other related applica-
tions, and design solutions for SDR.

2.1. Communication Chain and Scheduling Example

Consider the simple case of the SDR digital com-
munication standard (chain) in Figure 1a composed of
*N* = 5 tasks with computations weights (latencies) *w*₁ = 1,
*w*₂ = 3, *w*₃ = 4, *w*₄ = *w*₅ = 2 (this notation is explained
in Section 3). Data is processed by every single task in the
given order of the chain. The whole sequential process-
ing of data by the chain has a latency of 12 units of time
(UT). Our focus is the throughput of the chain, meaning
how much data is processed by unit of time. If only one
resource is allocated to the chain, the throughput will be
1/12 *UT*⁻<fnref n="1" />. The first, second and fifth tasks are stateful
and cannot be replicated, while the third and the fourth
tasks are stateless and replicable. We want to find an op-
timal schedules, using interval mapping, when only 3 or 6
resources are available.

An optimal schedule for 3 resources is found by putting
the first two tasks together in one stage, the third one by
itself, and the last two ones in another stage. We will
note this as (n, r) = ((2, 1, 2), (1, 1, 1)) (see Section 3).
This solution is illustrated in Figure 1b. In this case, the
maximal stage latency is the latency of the second stage
4 *UT* with the second stage, leading to the throughput
*T* = 1/4 *UT*⁻<fnref n="1" />. Any other partition (or using fewer re-
sources) would lead to a lower throughput, so this solution
is optimal.

<footnote n="1">¹Stateless tasks depend only on their current input (e.g., a filter), while stateful tasks are also influenced by their internal state (due to previous inputs).</footnote>
<figure><img src="image_3.png" /><figcaption>(a) Chain composed of 5 tasks. Each box represents a task. The number inside represents its weight (latency). Boxes with solid lines represent stateful tasks, while dashed lines represent stateless tasks.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>(b) Optimal schedule for 3 resources. Vertical lines represent the separation in pipeline stages.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(c) Optimal schedule for 6 resources. Tasks in the third stage $s_3$ are duplicated to represent 2 resources allocated to this stage. Only 5 resources are necessary for the optimal solution.</figcaption></figure>

Figure 1: Example of a task chain and its optimal schedule for 3 and 6 resources.

An optimal schedule using 6 resources is illustrated in Figure 1c. The optimal solution is made by putting the first and the second tasks alone in their stages, the second and fourth in the same stage using two resources (i.e., replication), and the fifth task alone in its stage, i.e. $(n, r) = ((1, 1, 2, 1), (1, 1, 2, 1))$. It leads to a throughput $T = \frac{1}{3}UT^{-1}$. Notice that the second and the third stages have the same maximal weight in this solution. Using an additional resource in the third stage would reduce its weight. However, this would not improve the throughput of the chain, so the optimal solution uses only 5 resources. These optimal solutions can be found by our proposed algorithm named OTAC, as will be shown in Section 4.

## 2.2. Pipelined workflow scheduling problems

Our scheduling problem is related to **pipelined workflow scheduling** problems focused on throughput optimization. A survey by Benoit et al. [20] distinguishes four kinds of parallelism in these problems: (i) *Task parallelism*, two or more independent tasks execute simultaneously on the same data; (ii) *Pipelined parallelism*, two dependent tasks execute on different data; (iii) *Data parallelism*, multiple resources execute the same task on parts of the same data; (iv) *Replicated parallelism*, several copies of a single task operate on different data. In our SDR context, only pipelined and replicated parallelism are

considered. Task parallelism rarely exists in digital communication systems since it adds synchronization overhead at a task granularity, and tasks have low latency (around tens of microseconds). Data parallelism would also require extra synchronization. In our context, pipeline and replicated parallelism are the best choice as they enable throughput improvements.

When *only pipelining is possible (all tasks are stateful)*, the problem becomes a classical chains-to-chains partitioning (CCP) problem with known optimal solutions [21, 9, 22, 10]. For instance, Nicol's algorithm [22, 10] optimally minimizes the period by means of a dichotomic search on the possible maximal stage durations and of a greedy approach to partition the tasks among the pipeline stages. Agrawal, Benoit and Robert [23] propose a dynamic programming solution for this problem while also taking into consideration the communication time between tasks. We provide another dynamic programming solution to our problem, including pipelining and replication, in Section 3.1. Meanwhile, *when replication is possible and all tasks are stateless*, an optimal solution is a single partition with all tasks, replicated among all available resources [11]. However, *no optimal solution has been proposed so far using pipelining and replication when both stateless and stateful tasks are present*.

## 2.3. Scheduling on related applications

In the related context of latency minimization, it is known that pipelining and replication have no positive effect on latency for task chains [11, 20]. For more generic directed acyclic graphs (DAGs), the problem is known to be NP-Complete [24], and heuristics proposed for related objectives and DAGs are usually not applicable directly in our context. For instance, Vydyanathan et al. [25] propose a heuristic for optimizing both latency and resources assigned under throughput constraints using pipelining and replication for application workflows. Nonetheless, the solution assumes that all tasks can be replicated, which is not possible for stateful tasks.

De Matteis et al. [26] provide a heuristic that analyzes and partitions a task graph in order to minimize its latency for streaming task graph. The partition is made accordingly of the data volume between tasks, aiming for balance. This method considers both pipeline parallelism and temporal multiplexing, but no replication.
Pipelining is also present in optimizing training of large
AI models. DAPPLE [16] proposes a scheduling scheme
with both pipeline and data parallelism for training DNN
models. It is based on partitioning stages and mapping
resources, and can be seen as a pipeline planning prob-
lem. Although DAPPLE similarly focuses on throughput,
it does not consider resource minimization. Additionally,
it considers the memory limitations of devices, which is
not considered currently on our problem but could be con-
sidered in the future.

2.4. *Design solutions employed on SDR*

There are multiple frameworks and tools dedicated to
the design and implementation of SDR or signal process-
ing systems. Each framework implements and schedules
tasks in its own way, which has led to different optimiza-
tion solutions.

**GNU Radio** [27] is the most widely used open source
framework in this domain. It provides an extensible li-
brary of signal processing *blocks* (tasks) to be combined
in a flowgraph. In its current implementation (version 3.0),
GNU Radio employs Thread Per Block scheduling [15].
Thus, each task is assigned to its own thread, and thread
management is left to the operating system or to another
runtime such as CEDR [28]. Although simpler, this ap-
proach can lead to performance problems related to lo-
cality, to thread priorities and scheduling policies [15], or
even related to the overhead of managing too many threads
per core [29]. For these reasons, future plans for GNU
Radio 4.0 include the removal of this constraint, allowing
more than one block per thread and better scheduling poli-
cies [29]. In this sense, we believe GNU Radio can benefit
from OTAC in the future.

**StreamIt** is a Domain Specific Language (DSL) that provides an environment for developing SDR chains [30]. Unlike GNU Radio, StreamIt has its own scheduling algorithm built into its compiler [31]. It is based on a greedy algorithm that applies pipelined parallelism (*ver*-tical fusion) when fewer cores than tasks are available, or replicated parallelism (*horizontal fission*) when cores are abundant [31]. Meanwhile, OTAC uses both kinds of parallelism to maximize throughput while minimizing resource utilization.

Kudlur and Mahlke [8] use Integer Linear Program-
ming (ILP) to model the problem of scheduling StreamIt
stream graphs. As ILP is NP-Hard and the model makes

individual decisions for each task, this approach is not
considered scalable [14]. Yi et al. [13] proposed grouping
non-contiguous tasks together into batches that are then
scheduled using ILP. This approach trades optimality for
faster decisions. Che, Panda, and Chatha [12] apply a sim-
ilar ILP formulation but also propose a heuristic that fuses
stateful batches to free resources for replicating the slowest
batches. Gayen et al. [14] avoid batching tasks by relaxing
the ILP formulation into a Mixed Integer Linear Program-
ming format and combining it with a rounding heuristic
in order to accelerate decisions. These approaches have
the drawback of trying to assign all available resources,
which can lead to performance losses due to overhead [14].
Additionally, by bunching together non-contiguous tasks,
communication overhead is increased by having to transfer
data extraneous times between cores. In contrast, OTAC
provides optimal schedules and fast decisions for digi-
tal communication chains, while also avoiding additional
communication overhead.

**Array-OL** is a DSL for processing multidimen-
sional streams for video streaming [32]. Similarly to
StreamIt [31], it leaves the scheduling optimization pro-
cess to its compiler. Nonetheless, one of its main contri-
butions comes from exploring the data parallelism in the
multidimensional streams. This kind of parallelism is not
considered in this work.

Finally, **AFF3CT** [3] is a DSL, whose multi-threaded
runtime **StreamPU** [33] provides pipelined and replicated
parallelism for SDR. When a contiguous sequence of tasks
is assigned to the same pipeline stage, StreamPU's pre-
compiler is able to fuse these tasks to avoid unnecessary
data transfers and synchronization. The designer is re-
sponsible for deciding which tasks belong in each pipeline
stage and which stages are replicated [34]. We overcome
this issue by proposing an automatic and optimal sched-
ule.

3. Problem Definition

The optimization of SDR communication chains'
throughput can be depicted as a pipelined workflow
scheduling problem with special constraints. These prob-
lems can be characterized by their workflow model, system
model, performance model, and mapping strategy [20].

The workflow can be described as a linear chain of *N*
sequential tasks $T = \{\tau_1, \dots, \tau_N\}$, meaning $\tau_i$ can only
execute after $\tau_{i-1}$. This is constrained by the nature of streaming application in which data must be computed by each task, entirely, in a sequential manner from their point of view. A task $\tau_i$ has a computation weight $w_i$ (i.e., its latency). Communication weights are not explicitly considered because we focus on multicore architectures<fnref n="2" /> and interval mapping, which enforces that all (and only) tasks in an interval of task indexes share the same resource [20], leading to a situation that minimizes data transfers. Regarding their execution, tasks are partitioned into two subsets $\mathcal{T}_F$ and $\mathcal{T}_L$ for stateful and stateless tasks. Stateful tasks maintain an internal state that is set by previously seen data, so they cannot be replicated without changing the results of the task chain. For instance, most synchronization tasks are stateful as they have a strong data dependency at the symbol level. Stateless tasks, meanwhile, carry no internal state and can be replicated without side effects. Such is the case of decoder tasks.

Our system is composed of $R$ fully-connected homogeneous resources (e.g., cores). The mapping strategy on our system is known as interval mapping, where $\mathcal{T}$ is partitioned into $k$ contiguous intervals. We call the $i^{th}$ interval in the format $[\tau_b, \tau_e]$ ($b \le e$) a stage noted as $s_i$. A stage is defined as stateless if it contains only stateless tasks, otherwise it is stateful. We define $r_i$ as the number of resources dedicated to $s_i$ verifying $\sum_{i=1}^k r_i \le R$. The weight of stage $s_i$ is defined based on the nature of its tasks and on $r_i$ (Eq. (1)).

Our primary objective is to maximize throughput ($T$). As throughput is inversely proportional to the period (i.e., $T = \frac{B}{P}$, where $P$ represents the period and $B$ represents the amount of data processed per frame), we will refer to this problem as a period minimization problem [20] in the remaining sections. The period $P$ of a solution ($s, r$) with $s = (s_1, \dots, s_k)$ and $r = (r_1, \dots, r_k)$ is given by the greatest weight among all stages (Eq. (2)). Additionally, our secondary objective is to minimize the number of resources assigned to the solution $R'$.

$$w(s_i, r_i) = \begin{cases} \sum_{\tau \in s_i} w_{\tau} & \text{if } s_i \cap \mathcal{T}_F \neq \emptyset, r_i \ge 1, \\ \frac{1}{r_i} \sum_{\tau \in s_i} w_{\tau} & \text{if } s_i \cap \mathcal{T}_F = \emptyset, r_i \ge 1, \\ \infty & \text{otherwise} \end{cases} \quad (1)$$

$$P(s, r) = \max_{i=1,\dots,k} w(s_i, r_i) \quad (2)$$

### 3.1. Optimal Solution using Dynamic Programming

As our first contribution, we provide a dynamic programming-based solution for the aforementioned interval mapping problem. Let $P^*(i, r)$ be the best period achieved when mapping tasks from $\tau_1$ to $\tau_i$ using up to $r$ resources. This can be computed using the recurrence in Eq. (3) with $P^*(0, r) = 0$ and $P^*(i, 0) = \infty$ for $i > 0$.

$$P^*(i, r) = \min_{0 \le j < i} \min_{0 < q < r} \max (P^*(j, q), w([\tau_{j+1}, \tau_i], r-q)) \quad (3)$$

In this recurrence, we find a starting task $\tau_{j+1}$ for the stage finishing at task $\tau_i$ or we map all tasks to the same stage. In all cases, we have to test all distributions of resources between this last stage and the previous ones. In order to find the minimum period with the fewest resources, we have to compute $P^*(N, R')$ for $1 \le R' \le R$ and choose the solution with the minimum period with the smallest value of $R'$ possible. Using dynamic programming, this recurrence can be directly computed in $O(N^2R^2)$ time and $O(NR)$ space. We provide more information about this solution in Appendix A, namely how it can be computed, a proof of its optimality, and information about how its time complexity may be reduced to $O(NR(N+R))$ or $O(NR \log N \log R)$. As we believe that the dynamic programming solution may become too expensive for larger systems and task chains, we provide a faster solution in the next section. We point our readers to [36] for more information on dynamic programming methods.

## 4. Greedy Optimal Solution

As our second contribution, we propose a novel fast optimal solution to our pipelined workflow scheduling problem. Our algorithm builds on the ideas employed for the

<footnote n="2">²On our experimental platform, we estimate that data transfers should take under 10µs for 200kB (as in DVB-S2 — Section 5) through caches using lmbench [35].</footnote>
CCP problem [10] while also handling stateless tasks. We present our new algorithm in Section 4.1 and its optimality proof in Section 4.2. An implementation of our algorithm is freely available online [37].

### 4.1. Optimal maximal-packing for Task chains

OTAC (for *Optimal maximal-packing for TAsk Chains*) is based on two functions, PROBE and SOLVE. PROBE employs a greedy approach to find a solution that respects a target period $P^+$, while SOLVE uses a binary search to set up target periods to PROBE in order to minimize the period $P$ and the resources used $R'$.

PROBE searches a solution with a period equal to or below $P^+$ for the linear chain of $N$ tasks using at most $R$ resources. It achieves this solution by greedily packing the most tasks together in one stage while respecting $P^+$ and without wasting resources that could be better used in the next stage. Algorithm 1 shows how PROBE works in a loop (lines 3–25) creating stages.

While being computed, stage $s_i = [\tau_b, \tau_{e-1}]$ receives the most tasks possible while respecting $P^+$ (lines 5–7). It receives one resource, unless its first task is stateless and has a weight greater than $P$. If $s_i$ is stateful, nothing more is to be done to it (line 9). For stateless stages, otherwise, our novel approach is employed (lines 10–25). Using the insight that the best solution for stateless tasks is to have them all in a single partition [11] using enough resources to respect $P^+$, we try to pack the whole sequence of stateless tasks together (lines 11–12). As this new stage would require $r_i$ resources (line 13), we check if it is possible to cover more tasks with them by limiting $s_i$ to the stateless tasks that fit into $r_i - 1$ resources and leaving the remaining tasks for the next stateful stage $r_{i+1}$. This is done in three steps:

1. We try to construct $s_{i+1}$ with the successor stateful task plus tasks from $s_i$, while respecting $P$ (lines 18–19).

2. If we are able to assign $r_i - 1$ resources to the new $s_i$ while respecting $P$, then we take tasks from $s_{i+1}$ back to $s_i$ that still fit in $r_i - 1$ resources (lines 20–23).

3. Else, $s_i$ remains with $r_i$ resources and all its original stateless tasks (lines 24–25).

After creating all stages, we check if the solution requires at most $R$ resources (lines 26–31). If the solution

<caption>**Algorithm 1 PROBE($P^+$)**</caption>

**Output:** Boolean (TRUE if there is a solution, FALSE otherwise), achieved period $P_{sol}$ or $P^+$, used resources $R_{sol}$, solution $(s, r)$
1: $i \leftarrow 0$ ▶ Current stage index
2: $b \leftarrow 0, e \leftarrow 1$ ▶ Stage in $[\tau_b, \tau_e[$
3: **while** $e \le N$ **do** ▶ Loop to create packings
4: &nbsp;&nbsp;&nbsp;&nbsp;$i \leftarrow i + 1, b \leftarrow e, e \leftarrow b + 1$
5: &nbsp;&nbsp;&nbsp;&nbsp;$s_i \leftarrow [\tau_b, \tau_b]$ ▶ Adds tasks to $s_i$ while they fit
6: &nbsp;&nbsp;&nbsp;&nbsp;**while** $e \le N$ and $w([\tau_b, \tau_e], 1) \le P^+$ **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$s_i \leftarrow [\tau_b, \tau_e], e \leftarrow e + 1$
8: &nbsp;&nbsp;&nbsp;&nbsp;$r_i \leftarrow \lceil \frac{w(s_i, 1)}{P^+} \rceil$ ▶ Resources required for a packing
9: ▶ Has not fitted all tasks and $s_i$ is stateless
9: &nbsp;&nbsp;&nbsp;&nbsp;**if** $e \le N$ and $s_i \cap \mathcal{T}_F = \emptyset$ **then**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**Tries to add other stateless tasks to $s_i$**
10: &nbsp;&nbsp;&nbsp;&nbsp;$f \leftarrow e$
11: &nbsp;&nbsp;&nbsp;&nbsp;**while** $f \le N$ and $\tau_f \in \mathcal{T}_L$ **do**
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$s_i \leftarrow [\tau_b, \tau_f], f \leftarrow f + 1$
13: &nbsp;&nbsp;&nbsp;&nbsp;$r_i \leftarrow \lceil \frac{w(s_i, 1)}{P^+} \rceil$
14: &nbsp;&nbsp;&nbsp;&nbsp;**if** $f > N$ **then** ▶ No more successors
15: &nbsp;&nbsp;&nbsp;&nbsp;$e \leftarrow f$
16: &nbsp;&nbsp;&nbsp;&nbsp;**if** $e \ne f$ **then** ▶ $s_i$ is not the final stage, $\tau_f$ is stateful
17: &nbsp;&nbsp;&nbsp;&nbsp;$s_{\text{temp}} \leftarrow [\tau_f, \tau_f], e \leftarrow f$ ▶ Successor stage
18: &nbsp;&nbsp;&nbsp;&nbsp;**while** $w([\tau_{e-1}, \tau_f], 1) \le P^+$ **do** ▶ Takes pred. tasks
19: &nbsp;&nbsp;&nbsp;&nbsp;$s_i \leftarrow [\tau_b, \tau_{e-2}], s_{\text{temp}} \leftarrow [\tau_{e-1}, \tau_f], e \leftarrow e - 1$
20: &nbsp;&nbsp;&nbsp;&nbsp;**if** $w(s_i, r_i - 1) \le P^+$ **then**
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$r_i \leftarrow r_i - 1$
22: &nbsp;&nbsp;&nbsp;&nbsp;**while** $w([\tau_b, \tau_e], r_i) \le P^+$ **do**
23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$s_i \leftarrow [\tau_b, \tau_e], e \leftarrow e + 1$
24: &nbsp;&nbsp;&nbsp;&nbsp;**else** ▶ No benefit leaving tasks to the successor
25: &nbsp;&nbsp;&nbsp;&nbsp;$e \leftarrow f, s_i \leftarrow [\tau_b, \tau_{e-1}]$
26: $R_{sol} = \sum_{k=1,...,i} r_k$ ▶ Number of resources used
27: **if** $R_{sol} \le R$ **then** ▶ Checks if the solution is valid
28: $P_{sol} \leftarrow \max_{k=1,...,i} w(s_k, r_k)$
29: **Return** (TRUE, $P_{sol}$, $R_{sol}$, $(s, r)$)
30: **else**
31: **Return** (FALSE, $P^+$, $R_{sol}$, $(s, r)$)
**Algorithm 2 SOLVE(N, R)**

**Output:** Minimal period *P*, minimal used resources *R*'</td></tr></table>

1: $P_{\text{min}} \leftarrow \frac{1}{R} \sum_{\tau \in \mathcal{T}} w_{\tau}$

2: $P_{\text{max}} \leftarrow P_{\text{min}} + \max_{\tau \in \mathcal{T}} w_{\tau}$

3: **while** $P_{\text{max}} - P_{\text{min}} \ge \frac{1}{R}$ **do**

4: $P_{\text{mid}} \leftarrow \frac{P_{\text{max}} + P_{\text{min}}}{2}$

5: valid, $P_{\text{sol}}$, $R_{\text{sol}}$, (s, r) $\leftarrow$ PROBE($P_{\text{mid}}$) ▷ valid
is TRUE if a solution was found

6: **if** valid **then**

7: $P \leftarrow P_{\text{sol}}$, $R' \leftarrow R_{\text{sol}}$

8: $P_{\text{max}} \leftarrow P_{\text{sol}}$ ▷ *P can only get smaller*

9: **else**

10: $P_{\text{min}} \leftarrow P_{\text{sol}}$ ▷ *P can only get bigger*

11: **return** *P*, *R*'</td></tr></table>

is valid, the value of $P(s, r)$ is returned. In total, PROBE computes a solution in $O(N)$ time.

PROBE is employed by SOLVE (Algorithm 2) in order to find an optimal solution. It follows a binary search procedure similar to the one used for the CCP problem [10]. Its main difference comes from its stop criterion (line 3). It must consider that the final period may be fractional due to a division of the longest stage by up to *R* resources.

The binary search is done within the limits where an optimal solution can be found. At each iteration, PROBE checks if a solution exists for the middle value between these two limits. If so, then all possible solutions above this value can be discarded from the search. Otherwise, all possible solutions below it can be discarded. The search continues until the stop criterion is met, and the minimal period is returned. Using this value, we can use PROBE function to find the solution (s, r) with minimal period and number of resources.

SOLVE calls PROBE until its stop criterion is met. Given that the range of values considered is equal to $w_{\text{max}} = \max_{\tau \in \mathcal{T}} w_{\tau}$, and that the loop stops when their difference is smaller than $\frac{1}{R}$, this loop is executed $O(\log w_{\text{max}} + \log R)$ times. Combined with the complexity of PROBE, SOLVE computes its solution in $O(\log(w_{\text{max}}R)N)$ time.

## 4.2. Proof of Optimality

Our new optimality proof is built upon the proofs of previous solutions for the CCP problem [9, 22, 10]. They have shown that our kind of SOLVE function always finds

the minimal period, and that the optimal solution lies between our values of $P_{\text{min}}$ and $P_{\text{max}}$ [10].

In this section, we prove that our greedy PROBE function always finds an optimal solution for a given target period, if one exists. We start by introducing the concepts of tight, full, and maximal packings, and prove that maximal packings cover the most tasks with the fewest resources possible. We follow by showing that PROBE always finds maximal packings. We explain that maximal packings are unique and prove that, if solutions exist, there exists a unique solution based solely on maximal packings. Thus, PROBE finds optimal solutions.

Iqbal [21] has proven that our kind of greedy PROBE function always finds a solution for a given target period, if one exists. The proof is based on the idea that, by creating stateful maximal packing (defined in Section 4.2.1), the least amount of work possible is left for the next stages. We extend this idea to also work with stateless maximal packings in order to complete our optimality proof.

### 4.2.1. Packing Concepts

**Definition 1 (Packing).** A stage $(s_i, r_i)$ is a packing for period *P* iff. its weight is smaller than or equal to *P*, i.e., $w(s_i, r_i) \le P$.

**Definition 2 (Tight packing).** A packing $(s_i, r_i)$ is tight for period *P* iff. no resource can be removed, i.e., $w(s_i, r_i - 1) > P$.

**Definition 3 (Full packing).** A packing $([\tau_b, \tau_e], r_i)$ is full for period *P* iff. it cannot include more tasks, i.e., $w([\tau_b, \tau_{e+1}], r_i) > P$.

**Definition 4 (Maximal packing).** A packing $(s_i, r_i)$ is considered maximal for period *P* iff. it is full, tight, and $s_i$ is: (1) stateful; (2) stateless and has no successor; or (3) stateless and there exists a successor stateful stage $s_{i+1}$ such that $(s_{i+1}, 1)$ is a maximal packing.

**Theorem 1.1.** A maximal packing $(s_i, r_i)$ with $s_i = [\tau_b, \tau_e]$ for period *P* always includes the most tasks using the fewest resources.

*Proof.* We split the proof for stateful and stateless stages. For the former, Def. 3 means that the stage includes the most tasks possible. Meanwhile, Def. 2 and Eq. (1) make it that the stage needs only one resource. For the latter, Defs. 3 and 2 specify that no more tasks can be included
nor resources removed. We can prove then that including
more tasks and resources does not improve the solution
by considering three different scenarios for the successor
stage:

1. There is no successor stage, which is trivial.

2. There is a stateless stage, which is impossible by Def. 4. The optimal solution for an interval of stateless tasks is to replicate them using the available resources, not to split them into multiple stages [11].

3. There is a stateful stage $s_{i+1} = [\tau_{e+1}, \tau_f]$ such that $(s_{i+1}, 1)$ is a maximal packing. Together, these stages include $f-b+1$ tasks using $r_i+1$ resources. If $m < f - e$ stateless tasks were to be moved from $s_{i+1}$ to $s_i$, then at least $r_i+1$ resources would be necessary to pack $e+m-b+1$ tasks (Def. 3), which are fewer tasks than before. Furthermore, if both stages were to be merged, the new stage would be stateful and not a packing anymore.

Therefore, stateless maximal packings always include the
most tasks possible using the fewest resources. $\square$

### 4.2.2. Maximal Packings in PROBE

**Theorem 1.2.** PROBE always finds maximal packings.

*Proof.* By Def. 4, maximal packings have to be tight, full, and respect one of three other conditions. Any stage $(s_i, r_i)$ computed by PROBE has a duration $w(s_i, r_i) \le P$. This is ensured by the tests in lines 6, 20, and 22, and by the values of $r_i$ computed in lines 8, 13, and 21, so the stage is a packing. The value of $r_i$ cannot be reduced, so the packing is tight (Def. 2). The tests in lines 6, 11, and 22, and the attribution in line 25 ensure that no more tasks can be added to the packing, so it is full (Def. 3). Finally, the three other conditions for a maximal packing are covered as follows:

1. We verify if $s_i$ is stateful in line 9.

2. We see if $s_i$ is stateless and has no successor in line 14.

3. We check if $s_i$ is stateless and there exists a successor maximal packing ($s_{i+1}, 1$) in lines 16–25. $s_{i+1}$ is ensured to be stateful by the tests in lines 11 and 16 when computing $s_i$. It is ensured to be maximal in the next iteration of the outer loop (lines 3–25) ($s_{i+1}$ meets condition (1) to be maximal).

Consequently, all packings computed by PROBE are maximal. $\square$

### 4.2.3. Optimality of PROBE

Given a starting task $\tau_b$ and a period $P$, there exists a unique maximal packing with consecutive tasks ($[\tau_b, \tau_e], r_i$). This comes naturally from Theorem 1.1 that proves that a maximal packing always includes the most tasks possible using the fewest resources, so it would be absurd to have a better solution with these properties. This idea is employed in Theorem 1.3.

**Theorem 1.3.** If there are valid solutions for a target $P$, then there exists at least a solution $(s^*, r^*)$ with $P(s^*, r^*) \le P$ composed only of maximal packings and that uses a minimal number of resources.

*Proof.* First, if all stages are maximal packings, then, by definition, all stages have $w(s_i, r_i) \le P$, so $P(s^*, r^*) \le P$. Second, for each task $\tau_b$ starting a stage, there is only a single maximal packing for consecutive tasks, so the solution is unique. Third and final, assume there is another solution $(s', r')$ composed only of maximal packings that require fewer resources than $(s^*, r^*)$. They must differ in one of two ways: $(s', r')$ has a stateless stage $(s_i, r'_i)$ with fewer resources than its equivalent in $(s^*, r^*)$; or they have stages starting at different tasks.

The first scenario is a contradiction because $(s_i, r_i)$ must be tight to be maximal, so no solution can take fewer than $r_i$ resources for stage $s_i$. The second scenario is also a contradiction. Indeed, for a stage to start at a different task in both solutions requires a previous stage to have finished at a different task. Moreover, there is only a single maximal packing starting at a given task, so one of the solutions is not composed only of maximal packings. Consequently, the solution is unique and uses a minimal number of resources. $\square$

Given a set of tasks, a number of resources $R$ and a
target period $P$, the obtained solution by PROBE is optimal
for the given input since the maximal packing found has
the minimal number of resources possible.

### 4.2.4. Optimality of the solution

The solution obtained by the whole algorithm is optimal: SOLVE does a binary search on the period $P$ with
PROBE testing if there is a valid solution for each case. The theorem 1.4 is based on that.

**Theorem 1.4.** *Given a linear chain of *N* sequential tasks *T*, the solution found by SOLVE, (s*, r*) has the minimal *P* possible for *R* resources.*

By combining Theorems 1.2 and 1.3, we can conclude that our PROBE function always finds optimal solutions as said by Theorem 1.4. As SOLVE always finds the minimal period, we can conclude that OTAC provides optimal solutions to this pipelined workflow scheduling problem.

# 5. Experimental Evaluation

With the interest of fully exploring OTAC's advantages (i.e., low complexity and optimality), we have organized our experiments in three parts. We first evaluate the execution time of OTAC in comparison to the DP solution (Section 3.1) and other heuristics. We then use simulation to explore the effects of scheduling a thousand different synthetic task chains. We end our experiments with a concrete streaming application use case using an implementation of the Digital Video Broadcasting – Second Generation (DVB-S2) [19] standard on AFF3CT [3].

## 5.1. Experimental Environment

### 5.1.1. Workloads

We use synthetic task chains for our **execution time** and **simulation** experiments. For the former, we generated chains with increasing numbers of tasks ($2^x$ for $1 \le x \le 12$) with a maximum weight of 10000 and a stateless ratio (SR) (i.e., fraction of tasks that are stateless) of 0.2. We compute their schedulers for $R = 128$ resources. For the latter, we generated a thousand task chains of 20 tasks each. Each task has a weight in $\mu$s taken randomly from a uniform distribution in the interval [100, 35000]. These parameters were chosen based on performance measurements and configuration over the original DVB-S2 chain. Additionally, for each chain, we vary their SR between zero and one with a step of 0.1 (i.e. two more tasks are stateless each step). We schedule them over $R = \{5, 10, 15, 20, 25\}$.

Our **concrete use case** is based on a preexisting open-source implementation of **DVB-S2** [38]. DVB-S2 is

<figure><img src="image_6.png" /><figcaption>Figure 2: DVB-S2's reception chain. Task names (adapted from [34]) and weights (rounded values in $\mu$s) are provided. Solid (resp., dashed) lines represent stateful (resp. stateless) tasks.</figcaption></figure>

a standard used for satellite transmission of video contents [19]. This standard is used for broadcasting services and television thanks to its wide range of channel coding and modulation options. We focus on DVB-S2's reception chain, as forward error code decoding is the most compute-intensive part of its process. We illustrate this chain in Figure 2. The task weights were measured in our experimental platform for a frame packet with $I = 16$ frames, processed by each task during each step, and $K = 14232$ information bits transmitted per frame (MODCOD 2) [34]. The signal ratio is fixed to 4 dB. Each execution decodes 1.28 GB of data. We also consider an optimized manual schedule of the reception chain (built for a different multicore machine) as a baseline for comparison.

### 5.1.2. Scheduling Algorithms

For this evaluation, we have chosen to employ algorithms from the state of the art (Nicol) or to adapt ourselves greedy approaches seen in practical contexts (see Section 2.4). We have avoided the ILP approaches proposed in the context of StreamIt due to their complexity and difference in constraints (DAGs instead of chains, general mappings instead of interval mapping). The chosen schedulers (besides DP and OTAC) are the following:

* **Nicol** [22, 10]: optimal algorithm for pipelining-only.

* **RPTm**: inspired by GNU Radio's Thread Per Block scheduler [15], it tries to set one resource per task. If $R < N$, it greedily fuses together the neighboring stages that have the smallest combined weight. Stateless stages are merged together at the end of the algorithm to share resources.
* **RBm:** a recursive-bipartitioning-based scheduler similar to the fusion transformations in StreamIt [31]. It partitions the chain into two parts with similar weight and provides them with a proportional part of the resources. It employs the same merging strategy of RPTm when finishing.

### 5.1.3. Hardware and Software

Experiments were executed on a single server with two 18-core Intel Xeon Skylake Gold 6240 processors at 2.6 GHz, 192 GB of DDR4 DRAM at 2933 MT/s, and 1 TB of local storage with a SATA Seagate ST1000NX0443 at 7.2krpm. This kind of processor is representative to what is found in servers connected to antennas for SDR applications. The server runs CentOS release 7.6.1810 with kernel 3.10.0-957.el7.x86_64. We used AFF3CT v3.0.2, StreamPU v1.5.0, GCC v12.2.0, and Python v3.8.0. For the DVB-S2 experiments, threads were pinned using `hwloc v2.7.0`.

## 5.2. Execution Time Results

The execution time of the schedulers plays a role for scalability (future longer chains and larger platforms) and flexibility (for the adaptation of SDR systems to meet different needs at run time). Figure 3 shows the execution times according to the number of tasks for all aforementioned algorithms. Each point represent the average times obtained over thirty randomly generated chains. Error bars represent their standard deviation.

At a first glance, we can notice that DP's execution time grows quickly with the number of tasks. Its time complexity in $O(N^2R^2)$ makes it prohibitive to quickly compute schedules for SDR chains. For instance, all other algorithms take four orders of magnitude less time to execute for $N = 64$ (where we have stopped its measurements). Meanwhile, OTAC finds the same optimal solutions under 5 ms. For comparison with our use case (Section 5.4), this would allow OTAC to compute a schedule in the time one frame is processed, making it compatible with SDR's real-time constraints.

Among the other schedulers, the only one to surpass the one second barrier is RPTm. As the number of tasks exceeds the number of resources ($R = 128$), the fusion operation after the algorithm has to enumerate every possible stage merger and find the one with minimal weight, which leads to the increased execution time.

<figure><img src="image_7.png" /><figcaption>Figure 3: Execution time of schedulers (in s) in function of $N$ for $R=128$ and $SR=0.2$.</figcaption></figure>

As these results have shown, OTAC achieves execution times that are competitive with non-optimal heuristics and compatible with SDR's needs. We move next to a comparison of their schedules.

## 5.3. Simulation Results

### 5.3.1. Optimal Solutions

Our simulation experiments aim at comparing schedulers in terms of throughput and resource utilization. As expected, OTAC always obtained the maximum throughput with minimal resource utilization. We summarize the 55000 schedules per algorithm in Figure 4 in comparison to OTAC. Each row holds the results for a given scheduler. Each figure presents the results for a given $R$. Each column in a figure counts the number of **optimal** schedules, schedules with maximal throughput that use resources in **excess**, and **suboptimal** schedules, adding up to 1000 schedules.

Figure 4 provides several insights on the schedulers' behavior. RPTm finds more solutions with **maximal throughput** (**optimal** + **excess**) as the number of available resources increases. In general, it is easier to find the best solutions when fewer stages have to be merged due to a lack of resources. RPTm tends to find fewer maximal throughput solutions when SR increases. RPTm bases the number of replicas of a pipeline stage on the number of stateless tasks in it (instead of the tasks' weights), leading to suboptimal schedules.

RBm behaves similarly to RPTm in many ways: merging improves performance, fewer maximal throughput solutions are found when SR increases, optimal solutions are found when all tasks are stateless. In the tested scenarios, RBm is less effective than RPTm in general, except for the cases with very few resources ($R = 5$). Here, RBm is
<figure><img src="image_8.png" /><figcaption>Figure 4: Simulation: number of solutions of different qualities for different schedulers, *R*, and *SR* compared to OTAC. *Optimal* means maximum throughput with minimum resources. *Excess* means maximum throughput with extra resources.</figcaption></figure>

able to find 2074 optimal solutions (18.9% of the cases) whereas RPTm only finds 1393 (12.7%). These results are biased by the 1000 optimal solutions found when all tasks are stateless.

Nicol shows a very different behavior. Firstly, it tends to find optimal solutions less often when *R* increases. With more resources, the potential for performance gains through replication is higher. This also explains the decrease in optimal solutions found with the increase in SR (with zero optimal solutions for SR = 1.0). Still, in situations where pipelining is more important than replication (few resources or low SR), Nicol finds optimal solutions. For instance, for *R* = 5, Nicol finds all optimal solutions for SR < 0.5, and about 97.7% of them for scenarios in this SR range and *R* = 10.

Overall, these results quantify how difficult it can be to find an optimal schedule when pipelining and replication are involved, but they do not qualify how good or bad the other schedules are. We explore this in the next sections.

### 5.3.2. Resources Used

We study the different numbers of resources used by OTAC, RBm, and Nicol for *R* = 20 and SR = 0.5 and 0.9 in Figure 5. In these histograms, each bar counts the number of optimal, excess, and suboptimal solutions found with a given number of resources. RPTm is not illustrated, as it always used 20 resources.

When considering the solutions obtained with OTAC, it is noticeable that most solutions require fewer than 20 resources. For SR = 0.5 (resp., 0.9), OTAC uses an average of 14.8 (resp., 16.3) resources, with only 23 (resp., 330) schedules using all 20 resources available. When the SR is higher, OTAC profits from the higher replication potential and ends up using more resources for a higher throughput.

RBm tends to use more resources than necessary. For SR = 0.5, it uses an average of 18.4 resources, while only achieving 431 maximal throughput solutions. This represents about 3.6 (24.3%) more resources than OTAC. For SR = 0.9, these values increase to an average of 19.7
resources for 461 maximal throughput solutions.

Nicol tends to underutilize resources. As shown in Figure 5, it computes the same schedule regardless of SR. On average, Nicol uses 14.2 resources here. This leads to 516 maximal throughput solutions for SR = 0.5, but only 92 such solutions for SR = 0.9.

These results reinforce the importance of scheduling with the right number of resources: too many resources lead to wastage, while too few lead to suboptimal throughput.

### 5.3.3. Throughput Achieved

Considering that each task processes only one frame at a time (differently from DVB-S2), we explore the throughput achieved for the task chains with SR = 0.5 in two scenarios: with *R* = 10 and *R* = 20. We illustrate these results in Figure 6, where the figures on the left represent the throughput of OTAC in frames per second (FPS), while the other figures represent the throughput difference

between OTAC and other schedulers<fnref n="3" />. We can see that the average throughput obtained by OTAC increases when more resources are available (from 223 to 315 FPS — a factor of 1.41). While it uses almost all resources for scheduling tasks when *R* = 10, the situation changes when *R* = 20 (see Figure 5). As schedules become more limited by the stateful tasks' weights, the results become more concentrated to the left of the histogram.

RBm finds the fewest maximal throughput solutions in both scenarios, while showing a broad distribution of performance losses, with an average of 57.17 and 62.38 fewer FPS than OTAC for *R* = 10 and 20, respectively, when only considering suboptimal solutions. These differences improve to 56.42 and 35.49 fewer FPS when all solutions are considered, which is still 11% less FPS at best.

Nicol found 804 optimal solutions when *R* = 10, leading to a low count of suboptimal solutions. It achieved an average of 14.36 fewer FPS than OTAC on its suboptimal solutions, and an average of 2.80 fewer FPS over all schedules. Yet, these differences increased to 31.41 and 15.20 when *R* = 20 (about 5% fewer than OTAC).

Finally, RPTm shows an improving performance with the increase in the number of resources. It achieved an average of 21.52 fewer FPS than OTAC for suboptimal solutions, and of 18.40 fewer FPS over all solutions for *R* = 10. These differences change to 31.50 and 7.59 fewer FPS when *R* = 20. Although the range and magnitude of the performance differences increase when more resources are available, more solutions achieve maximal throughput (from 145 to 759), leading to a smaller average difference. Still, in the case of RPTm, these improvements come at the cost of resource wastage.

**Overall, our simulation results have highlighted how arbitrarily easy or difficult it can be for other schedulers to find optimal solutions.** The quality of their solutions strongly depends on the characteristics of the task chain and the number of resources available, while OTAC is able to handle all scenarios optimally. The next section explores how these points translate to a real communication chain.

<figure><img src="image_9.png" /><figcaption>Figure 5: Simulation: histograms of number of resources used ($R'$) for the schedules from OTAC, RB, RBm, and Nicol for *R* = 20 and SR = 0.5 (left) and 0.9 (right). Vertical axes at different scales.</figcaption></figure>

<footnote n="3">³Considering suboptimal schedules only, as maximal throughput schedules would only increase the bar at zero.</footnote>
<figure><img src="image_10.png" /><figcaption>Figure 6: Simulation: histograms of throughput in terms of frames per second achieved by OTAC (left) for *R* = 10 and *R* = 20 and SR = 0.5; throughput difference between OTAC and RPTm, RBm, and Nicol for the instances where they find suboptimal schedules. Axes at different scales depending on the histogram.</figcaption></figure>

## 5.4. DVB-S2 Standard Results

Figure 7 shows the results obtained for DVB-S2's reception chain. Full lines represent the simulated maximum throughput each scheduler could achieve based without overhead. Dotted lines represent the average throughput obtained with different numbers of resources over ten executions. A few points are missing for RBm (*R* = {10, 11, 14, 15, 16}) because its schedules were not achievable. Some successive tasks in DVB-S2 must remain in the same pipeline stage. But, as this constraint is not visible at the scheduler level, RBm is unable to enforce this rule. Additionally, as the maximum throughput achievable by all schedulers plateaus after a certain number of resources (e.g., at *R* = 18 for OTAC), we limited our experiments to fewer than 36 resources in most cases to avoid overloading the server.

Figure 7 shows that OTAC and RBm achieve the highest throughput, while RPTm and Nicol find suboptimal schedules. The hand-tuned baseline achieves a performance similar to OTAC but requires almost twice more resources. We can also notice a 7% gap between the best expected throughput (47.17 Mbps) and the one achieved by OTAC with *R* = 18 (43.86 Mbps, on average). Among the sources of this gap is the synchronization overhead of managing a pipelined and replicated task chain, not

explicitly considered in our model.

Table 1 provides more details about the best results achieved by the different algorithms. We use the notation $|s|$ to represent the number of tasks in each stage. We include here the simulated throughput, and also their average and median values. Nicol achieves the lowest throughput by not replicating the task with the highest weight (34183.9 µs in Figure 2). Meanwhile, OTAC, RBm and the baseline are limited by the highest weight

<figure><img src="image_11.png" /><figcaption>Figure 7: DVB-S2: throughput in Mbps as a function of the number of available resources for different schedulers.</figcaption></figure>
<table><caption>Table 1: DVB-S2: Best schedules, throughput (Mbps), and number of resources for the different algorithms.</caption><thead><tr><th>(|s|, r)</th><th>Sim. T</th><th>T<sub>avg</sub></th><th>T<sub>med</sub></th><th>R / R*</th></tr></thead><tbody><tr><td><strong>OTAC</strong><br>(4.1.5.7.2), (1.1,1,14,1))</td><td>47.17</td><td>43.86</td><td>43.95</td><td>18 / 18</td></tr><tr><td><strong>RPTm</strong><br>(1.1,1,1,1,1,1,1,2.8.1),<br>(1.1,1,1,1,1,1,1,1,8.1))</td><td>26.21</td><td>25.26</td><td>25.23</td><td>18 / 18</td></tr><tr><td><strong>RBm</strong><br>(1.2,1,1,1,1,1,1,2.8.1),<br>(1.1,1,1,1,1,1,1,1,15.1))</td><td>47.17</td><td>43.98</td><td>44.01</td><td>25 / 24</td></tr><tr><td><strong>Nicol</strong><br>(15.1,1.2), (1.1,1,1))</td><td>6.66</td><td>6.58</td><td>6.58</td><td>4 / 4</td></tr><tr><td><strong>Baseline</strong><br>(1.3,1.3,3.2.5.1),<br>(1.1,1,1,1,1,1,28.1))</td><td>47.17</td><td>42.3</td><td>44.58</td><td>35 / 35</td></tr></tbody></table>

among stateful tasks (4861 µs), leading to a 7x higher throughput.

When comparing the best solutions found by the algorithms using the Mann-Whitney U test with 5% confidence, we cannot say that OTAC and RBm perform differently (p-value = 0.73), in spite of RBm using 6 more resources (33% in excess). OTAC and the baseline show statistically different results (p-value = 0.009), with the baseline achieving a median throughput 0.6 Mbps above OTAC. As OTAC only replicates the fourth pipeline stage enough so that its weight (4790.8 µs) is below the one of its second stage, we believe its solution to be more sensitive to fluctuations in task latency. However, this difference does not justify the 17 extra resources used by the baseline.

## 6. Concluding Remarks

In this article, we considered the problem of scheduling pipelined and replicated task chains on homogeneous computing resources for SDR applications. Based on the state of these tasks, we have proposed a dynamic programming-based optimal solution, and OTAC, a greedy scheduler that maximizes throughput while minimizing resource usage. We have shown that OTAC finds solutions in $O(\log(w_{max}P)N)$, and we have proved its optimality.

Through an extensive experimental evaluation using both simulation and the DVB-S2 communication standard, we have shown how OTAC outperforms other strategies. Our simulation results have highlighted how arbitrarily easy or difficult it can be for other schedulers to find optimal solutions, while OTAC always does so. The experiments with DVB-S2 have shown that OTAC achieves

almost 44 Mbps over 18 cores, which is 7% from the limit without overhead, while it uses down to 51% of the resources of a hand-tuned solution. The execution time of OTAC is competitive compared to other algorithms and much smaller than the DP solution.

For SDR systems, OTAC focuses on pipelined workflow scheduling problems for linear task chains, a limited aspect of these systems. It assumes that resources are identical, so it cannot benefit from more heterogeneous platforms. Finally, OTAC has been evaluated as an offline method, but a more dynamic approach for dynamic weight remains possible, combining a detection of non-optimality with a quick re-execution of OTAC.

We thus plan to investigate how to adapt OTAC, or propose new solutions, to different shapes of task graphs and for heterogeneous platforms (e.g., uniform resources with various clock frequencies or platforms with accelerators). We aim to integrate communication weights in our model to handle more distributed environments. Finally, we will study the problem of scheduling multiple task chains over shared resources with different optimization objectives (e.g., maximum sum of throughput, max-min fairness).

## Appendix A. Details Regarding our Optimal Solution using Dynamic Programming

In this section, we elaborate on different aspects regarding the optimal solution mentioned in 3.1. We start by displaying a standard implementation of the dynamic programming scheme that can be computed in $O(N^2R^2)$ time and $O(NR)$ space for $N$ tasks and $R$ resources in Appendix A.1. We then provide a short proof of this algorithm's optimality in Appendix A.2. We finish by discussing some optimization possibilities to reduce the complexity of this solution in Appendix A.3, and showing how this optimized version performs against the standard dynamic programming implementation and OTAC in Section Appendix A.4.

### Appendix A.1. Standard Dynamic Programming Implementation

We provide a dynamic programming implementation of Eq. (3) (Section 3.1) in Algorithm 3. It employs three support matrices to build a solution: Time, Interval, and
a smaller period for two reasons: it would require having
a value for the period that is smaller than the minimum of
all possible solution, or a suboptimal $P^*(j, q)$. Therefore,
the solution is optimal in regards of its period.

Regarding the number of resources used, Algorithm 3's
support matrices only stores solutions that use the small-
est number of resources possible for a given period (line
17). It also returns the solution that achieves the optimal
period using the fewest resources possible (line 22 with
increasing numbers of resources), therefore the solution is
also optimal in the number of resources used.
□

**Theorem 1.7.** *DP achieved optimal solutions regarding the period achieved and the number of cores used.*

*Proof.* Lemmas 1.5 and 1.6 prove the optimality of the
base case and the inductive step, so DP is optimal. $\square$

Appendix A.3. *Dynamic Programming Optimization*

Considering that $P^*(i, r)$ represents the best period achieved when mapping tasks from $\tau_1$ to $\tau_i$ using up to $r$ resources, we can analyze its behavior to avoid useless computation in Algorithm 3. More precisely, we can see that $P^*(.,)$ (and its equivalent $Time[][]$) monotonically increases with an increase in its first term and it monotonically decreases with an increase in its second term. This can be easily rationalized: considering more tasks (first term) can only lead to equal or larger periods, while considering more resources (second term) can only lead to equal or smaller periods. Using these properties, we can reduce the search in the whole of a $O(NR)$ space of previous solutions to a path in this space can considers only up to $O(N + R)$ solutions, leading to a final time complexity in $O(NR(N + R))$ instead of the previous $O(N^2R^2)$ one. We provide some insights of how this can be done next.

When computing $P^*(i, r)$, two factors play a role in the achieved period for a given solution that start its last stage at task $\tau_{j+1}$ with $r-q$ resources (Eq. (3)), namely $P^*(j, q)$ and $w([\tau_{j+1}, \tau_i], r-q)$. We will refer to them here as the previous stages' best period and the weight of the last stage, respectively. In order to minimize the maximum value between these two factors, two options are possible. If the previous stages' best period is the limiting factor, we can try to move one task from the previous stages to the last stage (i.e., decrease $j$ by one) in order to reduce its value. This has the potential side effect of increasing the weight

of the last stage, as it will now include an additional task.
Meanwhile, if the weight of the last stage is the limiting
factor, we can try to move one resource from the previous
stages to the last stage (i.e., decrease $q$ by one), with the
potential side effect of increasing the previous stages' best
period. Using these properties, we could substitute part of
the main loop in Algorithm 3 (lines 13–20) to start a search
for the minimal period with $j = i - 1$ and $q = r - 1$, and
update these indexes based on the values of the previous
stages' best period and the weight of the last stage. The
search can stop if the values of the two factors are equal
(i.e., no improvement to their maximum value will happen
by shifting weights around), or when $j < 1$ or $q < 1$.
Finally, it may be possible to transform this sequential
search to a binary search, which would further reduce the
time complexity of the algorithm to $O(NR \log N \log R)$.

Appendix A.4. *Execution Time Results*

The execution time of the dynamic programming algo-
rithms is a good indicator for their scalability regarding
the chain parameters. Figure A.1 shows the execution
time in function of the chain length, between 1 and 8192
tasks with a constant number of resources *R* = 128 for
the dynamic programming algorithm (DP), the optimized
dynamic programming algorithm optimized (DP+ from
Appendix A.3) and OTAC. This experiment is similar to
the one in Section 5.2 but here we only consider optimal
algorithms. Each point represents the average time among
20 random generated chains with a stateful ratio (SR) of
0.2. The error bar represents the standard deviation.

<figure><img src="image_12.png" /><figcaption>Figure A.1: Execution time (in s) of schedulers DP, DP optimized (DP+) and OTAC in function of the chain length N for R=128.</figcaption></figure>
In the same way as in Figure 3, DP's execution time grows quicker than the other two algorithms. We also choose not to go further than *N* = 64 tasks as it would take more than 10³ s per iteration. DP+'s execution time also grows quicker than OTAC but in a relatively slower pace than DP. For instance, at *N* = 64 DP takes in average 87s while DP+ takes 0.120s and OTAC 0.001s.

## References

[1] M. Palkovic, J. Declerck, P. Raghavan, A. Dejonghe, L. Van der Perre, Dart - a high level software-defined radio platform model for developing the runtime controller, in: 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2011, pp. 1617–1620.

[2] ETSI 3GPP - TS 38.212, Multiplexing and Channel Coding (2018).

[3] A. Cassagne, R. Tajan, O. Aumage, C. Leroux, D. Barthou, C. Jégo, A DSEL for high throughput and low latency software-defined radio on multicore CPUs, Concurrency and Computation: Practice and Experience 35 (23) (2023) e7820.

[4] A. Karlsson, J. Sohl, J. Wang, D. Liu, ePUMA: A unique memory access based parallel DSP processor for SDR and CR, in: 2013 IEEE Global Conference on Signal and Information Processing, 2013, pp. 1234–1237.

[5] B. Le Gal, C. Jego, High-Throughput Multi-Core LDPC Decoders Based on x86 Processor, IEEE Transactions on Parallel and Distributed Systems 27 (5) (2016) 1373–1386.

[6] M. R. Maheshwarappa, M. Bowyer, C. P. Bridges, Software Defined Radio (SDR) architecture to support multi-satellite communications, in: 2015 IEEE Aerospace Conference, 2015, pp. 1–10.

[7] G. V. Research, Software defined radio market size, share & trends analysis report by type (general purpose radio, tetra), by component, by frequency band, by platform, by end-use, by region, and segment forecasts, 2023 - 2030, https://www.grandviewresearch.com/industry-analysis/software-defined-radio-sdr-market (2024).

[8] M. Kudlur, S. Mahlke, Orchestrating the Execution of Stream Programs on Multicore Platforms, in: Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’08, Association for Computing Machinery, New York, NY, USA, 2008, p. 114–124.

[9] S. Bokhari, Partitioning problems in parallel, pipeline, and distributed computing, IEEE Transactions on Computers 37 (1) (1988) 48–57.

[10] A. Pınar, C. Aykanat, Fast optimal load balancing algorithms for 1D partitioning, Journal of Parallel and Distributed Computing 64 (8) (2004) 974–996.

[11] A. Benoit, Y. Robert, Complexity results for throughput and latency optimization of replicated and data-parallel workflows, Algorithmica 57 (4) (2010) 689–724.

[12] W. Che, A. Panda, K. S. Chatha, Compilation of stream programs for multicore processors that incorporate scratchpad memories, in: Design, Automation & Test in Europe Conference & Exhibition, 2010, pp. 1118–1123.

[13] Y. Yi, W. Han, X. Zhao, A. T. Erdogan, T. Arslan, An ILP formulation for task mapping and scheduling on multi-core architectures, in: Design, Automation & Test in Europe Conference & Exhibition, 2009, pp. 33–38.

[14] N. Gayen, J. Ax, M. Flasskamp, C. Klarhorst, T. Jungeblut, M. Tang, W. Kelly, Scalable Mapping of Streaming Applications onto MPSoCs Using Optimistic Mixed Integer Linear Programming, in: 2018 26th Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP), 2018, pp. 348–352.

[15] B. Bloessl, M. Müller, M. Hollick, Benchmarking and Profiling the GNU Radio Scheduler, in: 9th GNU Radio Conference (GRCon 2019), GNU Radio Foundation, Huntsville, AL, 2019.
[16] S. Fan, Y. Rong, C. Meng, Z. Cao, S. Wang, Z. Zheng, C. Wu, G. Long, J. Yang, L. Xia, L. Diao, X. Liu, W. Lin, Dapple: a pipelined data parallel approach for training large models, in: Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '21, Association for Computing Machinery, New York, NY, USA, 2021, p. 431-445.

[17] M. D. Cranmer, B. R. Barsdell, D. C. Price, J. Dowell, H. Garsden, V. Dike, T. Eftekhari, A. M. Hegedus, J. Malins, K. S. Obenberger, F. Schinzel, K. Stovall, G. B. Taylor, L. J. Greenhill, Bifrost: A python/c++ framework for high-throughput stream processing in astronomy, Journal of Astronomical Instrumentation 06 (04) (2017) 1750007.

[18] J. Vaubaillon, C. Loir, C. Ciocan, M. Kandeepan, M. Millet, A. Cassagne, L. Lacassagne, P. Da Fonseca, F. Zander, D. Buttsworth, S. Loehle, J. Toth, S. Gray, A. Moingeon, N. Rambaux, A 2022 τ-herculid meteor cluster from an airborne experiment: automated detection, characterization, and consequences for meteoroids, Astronomy &amp; amp; Astrophysics 670 (2023) A86.

[19] ETSI EN 302 307 V1.2.1, Digital Video Broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications (DVB-S2) (2009).

[20] A. Benoit, U. V. Çatalyürek, Y. Robert, E. Saule, A Survey of Pipelined Workflow Scheduling: Models and Algorithms, ACM Comput. Surv. 45 (4) (08 2013).

[21] M. A. Iqbal, Approximate algorithms for partitioning and assignment problems, Tech. rep. (1986).

[22] D. Nicol, Rectilinear Partitioning of Irregular Data Parallel Computations, Journal of Parallel and Distributed Computing 23 (2) (1994) 119-134.

[23] K. Agrawal, A. Benoit, Y. Robert, Mapping linear workflows with computation/communication overlap, in: 2008 14th IEEE International Conference on Parallel and Distributed Systems, 2008, pp. 195-202.

[24] Y.-K. Kwok, I. Ahmad, Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors, ACM Comput. Surv. 31 (4) (1999) 406-471.

[25] N. Vydyanathan, U. V. Catalyurek, T. M. Kurc, P. Sadayappan, J. H. Saltz, Toward Optimizing Latency Under Throughput Constraints for Application Workflows on Clusters, in: A.-M. Kermarrec, L. Bougé, T. Priol (Eds.), Euro-Par 2007 Parallel Processing, Springer Berlin Heidelberg, Berlin, Heidelberg, 2007, pp. 173-183.

[26] T. De Matteis, L. Gianinazzi, J. de Fine Licht, T. Hoefler, Streaming task graph scheduling for dataflow architectures, in: Proceedings of the 32nd International Symposium on High-Performance Parallel and Distributed Computing, HPDC '23, Association for Computing Machinery, New York, NY, USA, 2023, p. 225-237.

[27] G. Radio, GNU Radio - the Free and Open Software Radio Ecosystem (2023). URL https://github.com/gnuradio/gnuradio

[28] J. Mack, S. Gener, A. Akoglu, J. Holtom, A. Chiriyath, C. Chakrabarti, D. Bliss, A. Krishnakumar, A. Goksoy, U. Ogras, GNU Radio and CEDR: Runtime Scheduling to Heterogeneous Accelerators, in: Proceedings of the GNU Radio Conference, Vol. 7, 2022.

[29] J. Morman, M. Lichtman, M. Müller, The Future of GNU Radio: Heterogeneous Computing, Distributed Processing, and Scheduler-as-a-Plugin, in: IEEE Military Communications Conference, 2022, pp. 180-185.

[30] S. A. William Thies, Michal Karczmarek, StreamIt: A Language for Streaming Applications, Lecture Notes in Computer Science (2002).

[31] M. I. Gordon, W. Thies, M. Karczmarek, J. Lin, A. S. Meli, A. A. Lamb, C. Leger, J. Wong, H. Hoffmann, D. Maze, S. Amarasinghe, A Stream Compiler for
Communication-Exposed Architectures, SIGPLAN
Not. 37 (10) (2002) 291–303.

[32] C. Glitia, P. Dumont, P. Boulet, Array-OL with delays, a domain specific specification language for multidimensional intensive signal processing, Multidim. Systems and Signal Processing 21 (2010).

[33] A. Cassagne, R. Tajan, O. Aumage, D. Barthou, C. Leroux, C. Jégo, StreamPU: A DSEL for high throughput and low latency software-defined radio on multicore CPUs, Wiley Concurrency and Computation: Practice and Experience (CCPE) 35 (23) (2023) e7820. doi:10.1002/cpe.7820. URL https://github.com/aff3ct/streampu

[34] A. Cassagne, M. Léonardon, R. Tajan, C. Leroux, C. Jégo, O. Aumage, D. Barthou, A flexible and portable real-time DVB-S2 transceiver using multicore and SIMD CPUs, in: 2021 11th International Symposium on Topics in Coding (ISTC), 2021, pp. 1–5.

[35] L. W. McVoy, C. Staelin, et al., Lmbench: Portable tools for performance analysis., in: USENIX annual technical conference, San Diego, CA, USA, 1996, pp. 279–294.

[36] M. Naghibzadeh, New generation computer algorithms, Available on Amazon (2021).

[37] D. Orhan, A. Cassagne, OTAC: source code (2025). URL https://github.com/aff3ct/streampu/tree/develop/src/Scheduler/OTAC

[38] A. Cassagne, M. Léonardon, R. Tajan, C. Leroux, DVB-S2 SDR transceiver (2023). URL https://github.com/aff3ct/dvbs2