1

# Pipeflow: An Efficient Task-Parallel Pipeline Programming Framework using
Modern C++

Cheng-Hsiang Chiu  Dept. of ECE, University of Utah<EMAIL_ADDRESS>,
Tsung-Wei Huang  Dept. of ECE, University of Utah<EMAIL_ADDRESS>,
Zizheng Guo  Dept. of CS, Peking University<EMAIL_ADDRESS>and  Yibo Lin
Dept. of CS, Peking University<EMAIL_ADDRESS>
###### Abstract.

Pipeline is a fundamental parallel programming pattern. Mainstream pipeline
programming frameworks count on data abstractions to perform pipeline
scheduling. This design is convenient for data-centric pipeline applications
but inefficient for algorithms that only exploit task parallelism in pipeline.
As a result, we introduce a new task-parallel pipeline programming framework
called Pipeflow. Pipeflow does not design yet another data abstraction but
focuses on the pipeline scheduling itself, enabling more efficient
implementation of task-parallel pipeline algorithms than existing frameworks.
We have evaluated Pipeflow on both micro-benchmarks and real-world
applications. As an example, Pipeflow outperforms oneTBB 24% and 10% faster in
a VLSI placement and a timing analysis workloads that adopt pipeline
parallelism to speed up runtimes, respectively.

††conference: ACM Symposium on High-Performance Parallel and Distributed
Computing; June 27–July 1, 2022; Minneapolis, Minnesota, USA††doi:
††copyright: none††copyright: none

##  1\. Introduction

#### Motivation:

Pipeline is a fundamental parallel pattern to model parallel executions
through a linear chain of stages. Each stage processes a data token after the
previous stage, applies an abstract function to that data token, and then
resolves the dependency for the next stage. Multiple data tokens can be
processed simultaneously across different stages whenever dependencies are
met. For example, in circuit simulation, some operations on a gate (e.g.,
NAND, OR, AND) do not depend on other gates and thus can be done at multiple
logic levels simultaneously, while operations at the same levels require
processing prior levels first (Huang et al., 2021). As modern computing
applications continue to adopt pipeline parallelism in various forms, there is
always a need for new pipeline programming frameworks to streamline the
implementation complexity of pipeline algorithms.

#### Limitation of state-of-art approaches:

Recent years have seen much research on pipeline programming frameworks to
assist developers in implementing pipeline algorithms without worrying about
scheduling details. Some famous frameworks are oneTBB (TBB, eTBB), FastFlow
(Aldinucci et al., 2017), GrPPI (del Rio Astorga et al., 2017), Cilk-P (Lee et
al., 2015), SPar (Griebler et al., 2017), and HPX-pipeline (Kaiser et al.,
2014). While each of these frameworks has its pros and cons, a common design
philosophy is to achieve transparent pipeline scheduling using data
abstractions. This design is convenient for data-centric pipeline
applications, but it also brings three limitations: 1) Users are forced to
design their pipeline algorithms in the center of data. As we shall give a
concrete example, many applications exhibit pipeline parallelism among tasks
rather than data. 2) Under this circumstance, users need to sort out a data
mapping strategy between applications and frameworks to perform pipeline
scheduling, although such mapping is totally redundant. 3) Existing frameworks
have very limited composability with other types of parallelism, such as task
graphs which have become essential to many irregular parallel algorithms.

#### Key insights and contributions:

After years of research, we have arrived at the key conclusion that data
abstraction and task scheduling should be decoupled from each other in
programming pipeline parallelism. Consequently, we introduce in this paper
Pipeflow, a new task-parallel pipeline programming framework to overcome the
limitations of existing ones. We establish Pipeflow atop the open-source task
graph programming system, Taskflow, developed by Huang et al. (Huang et al.,
2022), to leverage its powerful tasking infrastructure. As Taskflow is being
used by several important research projects (Ajayi et al., 2019; Xu et al.,
2019; Lin et al., 2020), building Pipeflow on top will not only benefit
existing users but also allow us to gain timely feedback from the Taskflow
community. We summarize our contributions as follows:

  * •

Programming Model. We have introduced a new C++ programming model for
developers to create a pipeline scheduling framework. Unlike existing models,
we do not provide yet another data abstraction but a flexible framework for
users to fully control their application data atop a task-parallel pipeline
scheduling framework.

  * •

Task Composition. We have introduced a composable interface to enable seamless
integration of Pipeflow into Taskflow. Users can combine pipeline tasks with
all existing task types of Taskflow to express a large parallel workload in a
single end-to-end task graph.

  * •

Scheduling Algorithm. We have introduced a lightweight scheduling algorithm to
schedule stage tasks across parallel lines. Our algorithm formulates the
pipeline scheduling into a task graph and thus can efficiently solve the
scheduling problem with dynamic load balancing using Taskflow’s work-stealing
runtime.

#### Experimental methodology and artifact availability:

We have evaluated Pipeflow on both micro-benchmarks and real-world
applications. As an example, Pipeflow outperforms oneTBB 24% and 10% faster in
a VLSI placement and a timing analysis workloads that adopt pipeline
parallelism to speed up runtimes, respectively. Pipeflow is open-source and
available in Taskflow as an algorithm module (Tas, flow).

#### Limitations of the proposed approach:

Like all programming frameworks, Pipeflow is not perfect. Specifically, our
design choice sacrifices the expressiveness for data-parallel pipeline
applications, as users need to explicitly manage data storage using Pipeflow’s
runtime methods. Yet, our experience leads us to believe that this challenge
can be mitigated by deriving an application-dependent data abstraction from
our pipeline programming interface.

##  2\. Background

We first review mainstream pipeline models and detail the motivation of
Pipeflow. We then argue that a new task-parallel pipeline programming model is
needed for many important industrial and research areas, e.g., circuit design.

###  2.1. Pipeline Basics

Pipeline parallelism is commonly used to parallelize various applications,
such as stream processing, video processing, and dataflow systems. These
applications exhibit parallelism in the form of a linear pipeline, where a
linear sequence of abstraction functions, namely stages, $F=\langle
f_{1},f_{2},\cdots,f_{j}\rangle$, is applied to an input sequence of data
tokens, $D=\langle d_{1},d_{2},\cdots,d_{i}\rangle$. A linear pipeline can be
thought of a loop over the data tokens of $D$. Each iteration $i$ processes an
input token $d_{i}$ by applying the stage functions $F$ to $d_{i}$ in order.
Depending on the number of parallel lines, $L=\langle
l_{1},l_{2},\cdots,l_{k}\rangle$, to process data tokens, parallelism arises
when iterations overlap in time. For instance, the execution of token $d_{i}$
at stage $f_{j}$ of line $l_{k}$, denoted as $f^{k}_{j}$($d_{i}$), can overlap
with $f^{k+1}_{j-1}$($d_{i+1}$). A stage can be a parallel type or a serial
type to specify whether $f^{k}_{j}$($d_{i}$) can overlap with
$f^{k+1}_{j}$($d_{i+1}$) or not. Figure 1 shows the dependency diagram of a
3-stage (serial-parallel-serial) pipeline.

Figure 1.  Dependency diagram of a 3-stage (serial-parallel-serial) pipeline.
Each node represents a task that applies a stage function to a token. Each
edge represents a dependency between two tasks.

Mainstream pipeline programming libraries employ data-centric models. Users
declare input and output data types for each stage using library-specific data
abstractions (e.g., template instantiation). Taking oneTBB (TBB, eTBB) for
example, Listing 1 implements Figure 1 using four parallel lines and a series
of callable objects called filter, where each filter receives an input data,
performs work on that data, and then produces a result for the next filter. To
support arbitrary application data types, libraries typically leverage dynamic
polymorphism to allocate and convert data from a generic type (e.g., void*,
std::any) to an application type. To further minimize the allocation cost,
some libraries, such as oneTBB (TBB, eTBB), have implemented specialized
object allocators and buffer structures to handle temporary results between
stages.

⬇

tbb::parallel_pipeline(4, // four parallel lines

tbb::make_filter<void,float>(

tbb::filter_mode::serial_in_order,

[&](tbb::flow_control& fc)-> float {

if( data.ready() ) {

return data.get();

} else {

fc.stop();

return 0.0f; // dummy data

}

}

) &

tbb::make_filter<float, std::string>(

tbb::filter_mode::parallel,

[&](float p) { return make_string(p); }

) &

tbb::make_filter<std::string,void>(

tbb::filter_mode::serial_in_order,

[&](std::string x) { std::cout << x; }

)

);

Listing 1: oneTBB code of Figure 1, assuming a void-float-string-void data
transformation.

###  2.2. Pipeline Parallelism in CAD Algorithms

Pipeflow is motivated by our research projects on developing parallel timing
analysis algorithms for very large scale integration (VLSI) computer-aided
design (CAD). Timing analysis is a critical step in the overall CAD flow
because it validates the timing performance of a digital circuit. As design
complexity continues to grow exponentially, the need to efficiently analyze
the timing of large designs has become the major bottleneck to the design
closure flow. For instance, generating a comprehensive timing report (e.g.,
pessimism removal, hundreds of corners, etc.) for a multi-million-gate design
can take several hours to finish (Kahng, 2018). To reduce the long analysis
runtime, recent years have seen increasing adoptions of manycore parallelism
by new timing analysis algorithms (Ajayi et al., 2019).

Figure 2.  Parallel timing propagations using pipeline (Huang et al., 2021).
Linearly dependent timing data (e.g., slew, delay, arrival time) is updated
across graph nodes in a pipeline fashion.

The most widely used strategy, including commercial timers, to parallelize
timing analysis is pipeline. Figure 2 illustrates this strategy using forward
timing propagation as an example (Huang et al., 2021). The circuit graph is
first levelized into a level list using topological sort. Nodes at the same
level are independent of each other and can run in parallel. Each node runs a
sequence of linearly dependent propagation tasks, including parasitics (RCP),
slew (SLP), delay (DLP), arrival time (ATP), jump points (JMP), and common
path pessimism reduction (CRP) to update its timing data from a custom circuit
graph data structure. Different propagation tasks can overlap across different
levels using pipeline parallelism.

In fact, this type of task-parallel pipeline strategy is ubiquitous in many
parallel CAD algorithms, such as logic simulation and physical design, because
computations frequently depend on circuit networks. We have observed three
important properties that make mainstream pipeline programming frameworks fall
short of our need: 1) Unlike the typical data-parallel pipeline, the pipeline
parallelism in many CAD algorithms is driven by tasks rather than data. 2)
Data is not directly involved in the pipeline but the graph data structure
crafted by a custom algorithm. 3) From user’s standpoint, the real need is a
pipeline scheduling framework to help schedule and run tasks on input tokens
across parallel lines, while leaving data management completely to
applications; in our experience, users disfavor another library data
abstraction to perform pipeline scheduling, as it often incurs development
inconvenience and unnecessary data conversion overheads.

##  3\. Pipeflow

Inspired by the need of parallel CAD algorithms, Pipeflow introduces a new
task-parallel pipeline programming model for users to create a pipeline
scheduling framework without data abstraction. We establish Pipeflow atop the
open-source parallel task graph programming system, Taskflow (Huang et al.,
2022), because it has been successfully adopted by many important CAD projects
under the DARPA IDEA program (Ajayi et al., 2019; Xu et al., 2019; Lin et al.,
2020). In this section, we will first give a brief introduction about Taskflow
and then dive into the technical details of Pipeflow.

###  3.1. State of the Art: Taskflow

Taskflow is a general-purpose parallel and heterogeneous programming system
using modern C++ (Huang et al., 2022). Taskflow introduces a new control
taskflow graph (CTFG) model that enables end-to-end implementation of task
graph parallelism coupled with in-graph control flow. A CTFG consists of
several task types, such as static task, dynamic task, condition task, module
task, runtime task, and so on. Figure 3 shows a CTFG of iterative tasking,
implemented in Listing 2. The loop continuation condition is implemented by a
single condition task, cond, that precedes two static tasks, body and done.
When cond returns 0, the execution loops back to body. When cond returns 1,
the execution moves onto done and stops. This example uses four tasks to
implement a tasking loop of 100 iterations.

Figure 3. A Taskflow graph of iterative control flow using one condition task
and three static tasks.

⬇

tf::Taskflow taskflow;

tf::Executor executor;

int i;

auto [init, body, cond, done] = taskflow.emplace(

[&](){ i=0; },

[&](){ i++; },

[&](){ return i<100 ? 0 : 1; },

[&](){ std::cout << ”done”; }

);

init.precede(body);

body.precede(cond);

cond.precede(body, done);

executor.run(taskflow).wait();

Listing 2: Taskflow program of Figure 3.

Another powerful feature of Taskflow is composable tasking. Composable tasking
enables users to define task hierarchies and compose large task graphs from
modular and reusable algorithm blocks that are easier to optimize. Figure 4
gives an example of a Taskflow graph using composition. The top-level taskflow
defines one static task C that runs before a dynamic task D that spawns two
dependent tasks D1 and D2. Task D precedes a module task E composed of a
taskflow of two dependent tasks A and B. Listing 3 shows the Taskflow code of
Figure 4. It declares two taskflows, taskflow1 and taskflow2. The second
taskflow defines a module task that is composed of the first taskflow,
preceded by task D. A module task does not own the taskflow but maintains a
soft mapping to the taskflow. Users can create multiple module tasks from the
same taskflow, but they must not run concurrently.

Figure 4. An example of taskflow composition.

⬇

tf::Taskflow taskflow1, taskflow2;

auto [A, B] = taskflow1.emplace(

[] () { std::cout << ”TaskA”; },

[] () { std::cout << ”TaskB”; }

);

auto [C, D] = taskflow2.emplace(

[] () { std::cout << ”TaskC”; },

[] (tf::Subflow& sf) {

std::cout << ”TaskD”;

auto [D1, D2] = sf.emplace(

[] () { std::cout << ”D1”; },

[] () { std::cout << ”D2”; }

);

D1.precede(D2);

}

);

auto E = taskflow2.composed_of(taskflow1);

A.precede(B);

C.precede(D);

D.precede(E);

Listing 3: Taskflow code of Figure 4.

#### Integration with Taskflow:

Pipeflow leverages conditional tasking and composable tasking to implement the
pipeline algorithm in a module task. Unlike existing pipeline programming
frameworks that often operate in a standalone programming environment,
Pipeflow is designed to work seamlessly with Taskflow. We make this
architecture-level decision for three reasons: First, the tasking patterns of
parallel CAD algorithms are massive and irregular. Pipeline is just one part
and needs to work with other tasks, such as graph traversal and control flow,
to compose the whole application algorithm. Second, integrating Pipeflow into
Taskflow enables a unified scheduling runtime with dynamic load balancing and
improved inter-operability with other Taskflow tasks. Third, from the ease of
use standpoint, existing Taskflow users need not to learn a different set of
application programming interface (API) but the scheduling concept of Pipeflow
to implement pipeline algorithms. While Pipeflow is primarily designed as an
algorithm module of Taskflow, we believe many of our ideas are applicable to
other task-based parallel programming frameworks.

###  3.2. Programming Model

Pipeflow leverages modern C++ and template techniques to strike a balance
between expressiveness and generality. Listing 4 shows the Pipeflow
counterpart of the oneTBB code in Listing 1 that implements the pipeline in
Figure 1. There are three steps to create a Pipeflow application, 1) define
the pipeline structure using template instantiation, 2) define the data
storage, if needed, and 3) define the pipeline task using taskflow
composition. Users define the number of parallel lines and the abstract
function of each stage in a tf::Pipeline object. For each stage, users define
the stage type and a pipe callable using tf::Pipe. A stage can be either a
serial type (tf::PipeType::SERIAL) or a parallel type
(tf::PipeType::PARALLEL). The pipe callable takes an argument of tf::Pipeflow
type which is created by the scheduler at runtime. A tf::Pipeflow object
represents a scheduling token and contains several extensible methods for
users to query the runtime statistics of that token, including the line, pipe,
and token numbers. In Pipeflow, pipe and stage are interchangeable.

⬇

tf::Taskflow taskflow;

tf::Executor executor;

const size_t num_lines = 4;

std::variant<float, std::string> dtype;

std::array<dtype, num_lines> buf;

tf::Pipeline pl(num_lines,

tf::Pipe{tf::PipeType::SERIAL,

[&](tf::Pipeflow& pf) {

if ( !data.ready() ) {

pf.stop();

} else {

buf[pf.line()] = data.get();

}

}

},

tf::Pipe{tf::PipeType::PARALLEL,

[&](tf::Pipeflow& pf) {

buf[pf.line()] =

make_string(std::get<0>(buf[pf.line()]));

}

},

tf::Pipe{tf::PipeType::SERIAL,

[&](tf::Pipeflow& pf) {

std::cout << std::get<1>(buf[pf.line()]);

}

}

);

auto pipeline = taskflow.composed_of(pl);

executor.run(taskflow).wait();

Listing 4: Pipeflow code of Figure 1.

Pipeflow does not have any data abstraction but gives applications full
control over data management. In our example, since the first and the second
pipes generate float and std::string outputs, respectively, we create a one-
dimensional (1D) array, buf, to store data in a uniform storage using
std::variant<float, std::string>. The dimension of the array is equal to the
number of parallel lines, as Pipeflow schedules only one token per line. Each
entry buf[i] stores the data that is being processed at line $i$, which can be
retrieved by tf::Pipeflow::line. This organization is very space-efficient
because we use only 1D array to represent data processing in a two-dimensional
(2D) scheduling map. Additionally, by delegating data management to
applications, we can avoid dynamic data conversion between the library and the
application, which typically counts on virtual function calls to convert a
generic type (e.g., void*, std::any) to an arbitrary user type (TBB, eTBB;
Aldinucci et al., 2017).

Based on the above pipeline structure and data layout, we instantiate a
tf::Pipeline object, pl. This template-based design enables the compiler to
optimize each pipe type, such as using fixed-layout functor to store the
callable and its captured data. Finally, we create a pipeline module task
pipeline with pl using the taskflow composition method composed_of and submit
this taskflow to an executor to run the pipeline.

⬇

using P =

tf::Pipe<std::function<void(tf::Pipeflow&)>>;

std::vector<P> p(6, create_pipe()); // pipes

tf::ScalablePipeline pl(4, p.begin(), p.end());

taskflow.composed_of(pl);

executor.run(taskflow).wait();

p.resize(3);

pl.reset(p.begin(), p.end());

executor.run(taskflow).wait();

Listing 5: Scalable pipeline model in Pipeflow to accept variable assignments
of pipes.

tf::Pipeline requires instantiation of all pipes at the construction time.
While this design gives compilers freedom to optimize the layout of each pipe
type, it prevents applications from varying the pipeline structure at runtime;
for instance, the number of pipes might depend on the problem size, which can
be runtime variables. To overcome this limitation, Pipeflow provides a
scalable alternative, tf::ScalablePipeline, to allow variable assignments of
pipes using range iterators. In Listing 5, we create a scalable pipeline, pl,
from a vector of six pipes. After the first run, we reset pl to another range
of three pipes for the next run. A scalable pipeline is thus more flexible for
applications to create pipeline scheduling framework with dynamic structures.

###  3.3. Pipeline Task Composition

A key advantage of Pipeflow is its composability with Taskflow. By
encapsulating a pipeline in a module task, we enable seamless integration with
all existing task types in Taskflow. This result largely facilitates the
implementation of complex pipeline applications that require intensive
interaction with different types of task parallelism. Figure 5 shows a
Taskflow graph that emulates a data streaming application using a pipeline
module task and a condition task. The condition task is used to decide if the
pipeline needs to be run again depending on the application control flow.
Listing 6 shows the Taskflow code of Figure 5, using the pipeline task in
Listing 4. When the condition task cond returns 0, it informs the scheduler to
rerun the pipeline task pl, or proceeds to done to stop the program otherwise.

Figure 5. A Taskflow graph of an iterative streaming application using one
pipeline module task, one condition task, and one static task.

⬇

auto cond = taskflow.emplace([&](){

if ( data.ready() ) {

std::cout << ”rerun the pipeline”;

return 0;

} else {

return 1;

}

});

auto done = taskflow.emplace([&](){

std::cout << ”stop”;

});

pipeline.precede(cond);

cond.precede(pipeline, done);

Listing 6: Taskflow code of Figure 5 using the pipeline of Listing 4.

Figure 6 demonstrates another common application that embeds task graph
parallelism inside a pipeline. The pipeline consists of three serial stages
and four parallel lines. Each scheduled token runs a taskflow that implements
a stage algorithm in the pipeline. The three taskflows are self-explanatory.
Different taskflows can overlap across different lines, but only one taskflow
runs on the same stage due to the serial type. Listing 7 implements Figure 6.
We create a 1D array, buf, to store the three taskflows (defined elsewhere).
In each stage, we obtain its taskflow at buf[pf.pipe()], submit it to the
executor, and wait until the execution finishes. As we need only four tokens,
the first pipe stops the scheduler at the fifth.

Figure 6. A pipeline of embedded taskflows. Each taskflow implements a
parallel algorithm at a stage in the pipeline.

⬇

tf::Taskflow taskflow;

tf::Executor executor;

const size_t num_lines = 4;

const size_t num_pipes = 3;

std::array<tf::Taskflow, num_pipes> buf;

tf::Pipeline pl(num_lines,

tf::Pipe{tf::PipeType::SERIAL,

[&](tf::Pipeflow& pf) {

if (pf.token() == 4) {

pf.stop();

return;

}

executor.run(buf[pf.pipe()]).wait();

}

},

tf::Pipe{tf::PipeType::SERIAL,

[&](tf::Pipeflow& pf) {

executor.run(buf[pf.pipe()]).wait();

}

},

tf::Pipe{tf::PipeType::SERIAL,

[&](tf::Pipeflow& pf) {

executor.run(buf[pf.pipe()]).wait();

}

}

);

auto init = taskflow.emplace([](){

std::cout << ”init”;

});

auto pipeline = taskflow.composed_of(pl);

auto done = taskflow.emplace([](){

std::cout << ”stop”;

});

init.precede(pipeline);

pipeline.precede(done);

executor.run(taskflow).wait();

Listing 7: Pipeflow and Taskflow code of Figure 6.

###  3.4. Scheduling Algorithm

Pipeflow leverages Taskflow’s work-stealing runtime to design an efficient
scheduling algorithm with dynamic load balancing. As Pipeflow does not touch
data abstraction, we can simplify the pipeline scheduling problem to deciding
which task to run at which pipe and line. Similar to oneTBB, the key idea of
our scheduling algorithm is to enable only one scheduling token per line and
process all tokens in a circular fashion across all parallel lines. Based on
the idea, we formulate the pipeline scheduling into a lightweight Taskflow
graph where 1) one task deals with a scheduling token per line and 2) each
task decides which task to run on its next line and pipe using simple atomic
operations.

Pipeflow creates a taskflow for each pipeline module task using one condition
task and multiple runtime tasks one per line. A runtime task is a task type in
Taskflow for users to interact with the executor (Huang et al., 2022), such as
scheduling a task in the graph. The condition task decides which runtime task
to run when the pipeline starts. A runtime task deals with a scheduling token
at a line and will create a pipeflow object (of type tf::Pipeflow) to pass to
the pipe callable. Figure 7 shows the taskflow of the pipeline module task in
Listing 7. As there are four parallel lines, the task graph consists of one
condition task, cond, and four runtime tasks, rt-0, rt-1, rt-2, and rt-3.
Ultimately, only five tasks are used to run the pipeline, even though the
execution can involve many scheduling tokens.

Figure 7. The Taskflow graph of the pipeline module task in Listing 7.

Algorithm 1 implements the construction of the Taskflow graph for a pipeline.
First, we define the condition task to return on the index of the next task
(line 1). Since the pipeline is running in a circular fashion, the index is
equal to the remainder of the total number of scheduled tokens divided by the
number of parallel lines. Next, we define the runtime task using
build_runtime_task for each line (line 1) and specify the dependency between
each runtime task and the condition task (line 1).

global: $num\\_tokens$: the number of tokens

global: $num\\_lines$: the number of lines

global: $tasks$: a vector of tasks

1

2$tasks[0]\leftarrow create\\_condition\\_task($
$[]()\\{\textnormal{{return}}\>num\\_tokens\%num\\_lines$});

3 foreach  _line $l\in num\\_lines$_ do

4 $build\\_runtime\\_task(l)$ ;

5 $tasks[0]$.precede($tasks[l+1]$);

6 end foreach

Algorithm 1 build_task_graph()

global: $pipeflows$: a vector of Pipeflow objects

global: $jcs$: a 2D array of join counters

global: $num\\_tokens$: the number of tokens

global: $num\\_lines$: the number of lines

global: $num\\_pipes$: the number of pipes

global: $tasks$: a vector of tasks in Algorithm 1

Input: $l$: an integer

1

2$pf\leftarrow pipeflows[l]$;

3 $AtomStore($ $lines[pf.line][pf.pipe].jc,jc\\_of\\_pf.type)$;

4 if  _$pf.pipe==0$_ then

5 $pf.token\leftarrow num\\_tokens$;

6 invoke_pipe_callable($pf.pipe$, $pf$);

7 if  _$pf.stop==$ True_ then

8 return;

9 end if

10 $Increment(num\\_tokens)$;

11

12 end if

13if  _$pf.pipe$ != $0$_ then

14 invoke_pipe_callable($pf.pipe$, $pf$);

15

16 end if

17

18$curr\\_pipe\leftarrow pf.pipe$;

19 $next\\_pipe\leftarrow(pf.pipe+1)\%num\\_pipes$;

20 $next\\_line\leftarrow(pf.line+1)\%num\\_lines$;

21 $pf.pipe\leftarrow next\\_pipe$;

22 $next\\_tasks=\\{\\}$;

23 if  _$curr\\_pipe$ is SERIAL and
$AtomDec(lines[next\\_line][curr\\_pipe].jc)==0$_ then

24 $next\\_tasks$.insert($1$);

25 end if

26if  _$AtomDec(lines[pf.line][next\\_pipe])==0$_ then

27 $next\\_tasks$.insert($0$);

28 end if

29

30if  _next_task. $size==2$_ then

31 call_scheduler($tasks[next\\_line+1]$);

32 goto Line 2;

33 end if

34

35if  _next_task. $size==1$_ then

36 if  _next_task $[0]==1$_ then

37 $pf\leftarrow pipeflows[next\\_line]$;

38 end if

39 goto Line 2;

40 end if

Algorithm 2 build_runtime_task($l$)

Algorithm 2 implements build_runtime_task. When a runtime task is scheduled,
we need to know which stage at which line for the scheduling token to work. We
keep the line and stage information in a Pipeflow object. Each runtime task
owns a Pipeflow object pf of a specific line (line 2). Once a scheduling token
is done, there are two cases for its runtime task to proceed: 1) for a
parallel type, the runtime task moves to the next stage at the same line; 2)
for a serial type, the runtime task additionally checks if it can move to the
next line. To carry out such a dependency constraint, each stage keeps a join
counter of an atomic integer to represent its dependency value. The values of
a serial stage and a parallel stage can be up to 2 and 1, respectively. We
create a 2D array jcs to store the join counter of each stage at each line.
Line 2 initializes these join counters to either 2 or 1 based on the
corresponding stage types that are enumerated on integer constants, 2 (serial)
and 1 (parallel). At the first stage (line 2), the Pipeflow object updates its
token number (line 2) and checks if the pipe callable requests to stop the
pipeline (lines 2:2). If continued, we increment the number of scheduled
tokens by one (line 2). For other stages, we simply invoke the pipe callables
(lines 2:2).

After the pipe callable returns, we update the join counters based on the
stage type and determine the next possible tasks to run (lines 2:2). When the
join counter of a stage becomes 0, we bookmark this stage as a task to run
next (line 2 and line 2). If two tasks exist (line 2), the current runtime
task informs the scheduler to call a worker thread from the executor to run
the task at the next line (line 2) and reiterates itself on the next pipe
(line 2). The idea here is to facilitate data locality as applications tend to
deal with the next stage as soon as possible. If there is only one task
available, the current runtime task directly runs the next task with the
updated pf object (lines 2:2).

Figure 8. The scheduling diagram of the pipeline in Listing 7. Each line runs
one scheduling token. Multiple lines overlap tokens in a circular fashion.

Figure 8 illustrates our scheduling algorithm using the pipeline in Listing 7.
Since the pipeline runs in a circular fashion, there are four dependencies
(dashed edges) from the last stages to the first stages, and one dashed edge
from the first stage of the last line to the first stage of the first line.
Each line runs only one scheduling token. Multiple lines overlap tokens in a
circular fashion. Compared to existing algorithms, such as oneTBB (TBB, eTBB),
that count on non-trivial synchronization between tasks and internal data
buffers, our algorithm focuses on the task parallelism itself and thus largely
reduces the scheduling complexity of pipeline using simple atomic operations.
We draw the following lemmas and sketch their proofs to justify the
correctness of our scheduling algorithm:

###### Lemma 0.

Only one runtime task runs a pipe callable ( line 2 and line 2 in Algorithm 2)
on a scheduling token.

###### Proof.

Assuming there are two runtime tasks running the same pipe callable, this
means one runtime task reiterates its execution from the previous stage and
the other runtime task comes from the previous line. In a parallel stage, this
is not possible as there is no dependency from the previous line; only one
runtime task decrements the join counter to 0 (line 2 in Algorithm 2). In a
serial stage, this is also not possible because the dependency is resolved
using atomic operations; only one runtime task will acquire the zero value of
the join counter (line 2 in Algorithm 2). ∎

###### Lemma 0.

The scheduler does not miss any stage.

###### Proof.

We consider the situation where one runtime task moves to the next line (line
2 in Algorithm 2) instead of the next stage at the same line. Under this
circumstance, we need to make sure one runtime task will run that next stage.
Take Figure 8 for example, suppose a runtime task finishes token 4t+1 at stage
1 and precedes to token 4t+2 on stage 1, meaning that the join counter of
token 4t+1 at stage 2 is not 0 yet. Another runtime task that works on token
4t+0 at stage 2 will eventually decrement the join counter to run it (line 2
in Algorithm 2) or invoke another worker thread to run it (line 2 in Algorithm
2). ∎

##  4\. Experimental Results

We evaluate the performance of Pipeflow on two fronts: micro-benchmarks and
two real-world industrial CAD applications. We study the performance across
runtime, memory (RSS), and throughput. We do not use conventional pipeline
benchmarks as their sizes are relatively small compared to CAD (e.g., 6 pipes
in ferret(Bosilca et al., 2013)). The runtime difference between Pipeflow and
the baseline is not obvious on small pipelines. We compiled all programs using
clang++ v10 with C++17 standard -std=c++17 and optimization flag -O3 enabled.
We run all the experiments on a Ubuntu Linux 5.3.0-64-generic x86 machine with
40 Intel Xeon CPU cores at 2.00 GHz and 256 GB RAM. Each application thread
corresponds to one CPU core. All data is an average of five runs.

###  4.1. Baseline

Given a large number of pipeline programming frameworks, it is infeasible to
compare Pipeflow with all of them. Each of them has its pros and cons and
dominates certain applications. Since Pipeflow is inspired by our CAD
applications, we select oneTBB Parallel Pipeline (v2021.5.0) (TBB, eTBB) as
our baseline, which has been widely used in the CAD community. We believe this
selection is sufficient and fair to highlight the advantage of Pipeflow,
considering the similar tasking infrastructure between oneTBB and Pipeflow.
For oneTBB pipelines, we pass a nominal integer between successive stages
(i.e., tbb::filter), because oneTBB does not allow void type but implements a
specialized memory allocator to hold intermediate results returned by stages.

###  4.2. Micro-benchmarks

The purpose of micro-benchmarks is to measure the pure scheduling performance
of Pipeflow without much computation bias from the application. We compare the
runtime and memory between Pipeflow and oneTBB for completing pipelines of
different numbers of serial stages, scheduling tokens, and threads. We do not
use parallel stages as the callable of a parallel pipe can be absorbed into
the previous serial pipe. Each stage performs a nominal work of constant space
and time complexity and forwards the scheduling token to the next stage.

$2^{0}$$2^{3}$$2^{6}$$2^{9}$$2^{12}$$2^{15}$$0$$2$$4$$6$Number of Scheduling
TokensRatio (%)Runtime Improvement

$2^{0}$$2^{3}$$2^{6}$$2^{9}$$2^{12}$$2^{15}$$6$$6.5$$7$$7.5$$8$Number of
Scheduling TokensMaximum RSS (MB)MemoryPipeflowoneTBB

Figure 9. Runtime (improvement of Pipeflow over oneTBB) and memory performance
at different numbers of scheduling tokens using 16 threads, 80 parallel lines,
and 80 serial stages.

Figure 9 draws the runtime improvement of Pipeflow over oneTBB and memory data
under different numbers of scheduling tokens. Here, we use 16 threads, which
produce the best performance for both, to run a pipeline of 80 serial stages
and 80 parallel lines. With more token numbers ($>$256), Pipeflow is
consistently better than oneTBB, despite the slight improvement ($<$1%). When
the number of scheduling tokens is small, the variation is large (e.g., up to
6% improvement at 32 tokens). This is because when oneTBB starts the pipeline,
it requires expensive set-up time on the data buffers, whereas Pipeflow can
immediately start the task scheduling. Yet, as we increase the number of
tokens, such cost can be amortized. In terms of memory, oneTBB is always
higher than Pipeflow (e.g., 21% at 65K tokens) since we do not manage any data
buffers but focus on the task scheduling itself.

$0$$20$$40$$60$$80$$-10$$-5$$0$Number of StagesRatio (%)Runtime Improvement

$0$$20$$40$$60$$80$$6$$6.5$$7$$7.5$Number of StagesMaximum RSS
(MB)MemoryPipeflowoneTBB

Figure 10. Runtime (improvement of Pipeflow over oneTBB) and memory
performance at different numbers of serial stages using 16 threads and 65K
scheduling tokens. The number of parallel lines equals the number of the
stages.

Figure 10 draws the runtime and memory performance using 16 threads to
schedule 65K tokens through different numbers of stages, where the number of
parallel lines is equal to the stage count. We observe that Pipeflow is
consistently faster than oneTBB when the number of stages is larger than 16,
despite the difference being slight ($<$1%). At 8 stages, the available task
parallelism is smaller than the given thread parallelism, and oneTBB is faster
in this scenario. This is due to Taskflow’s scheduling algorithm. Taskflow
always keeps one thread busy in stealing while there is an active worker. When
the available task parallelism is scarce, the scheduling cost becomes
expensive. Yet, this problem can be mitigated by users selecting the right
line number in their pipeline applications. For instance, beyond 8 stages,
Pipeflow starts to outperform oneTBB. In terms of memory, we can clearly see
the difference between Pipeflow and oneTBB (e.g., 19% at 80 stages). As we
increase the number of stages, oneTBB needs more space for internal data
buffers, whereas Pipeflow delegates the data management completely to
applications.

$0$$10$$20$$30$$40$$0$$100$$200$$300$Number of CoresRuntime
(s)RuntimePipeflowoneTBB$0$$1$$2$$3$$4$Improvement Ratio (%)

$0$$10$$20$$30$$40$$6$$7$$8$$9$Number of CoresMaximum RSS
(MB)MemoryPipeflowoneTBB

Figure 11. Runtime and memory performance at differents number of threads
running 65K tokens on a pipeline of 80 stages and 80 parallel lines. The bars
illustrate the runtime improvement of Pipeline over oneTBB.

Figure 11 shows the runtime and memory results at different numbers of threads
to run 65K tokens on a pipeline of 80 stages and 80 parallel lines. Both
Pipeflow and oneTBB scale equally well as the number of cores increases. At
each point, we observe a small win of Pipeflow. For instance, at 32 cores,
Pipeflow is 4.3% faster than oneTBB. In terms of memory, both Pipeflow and
oneTBB use more memory with more threads. However, there remains a clear gap
between Pipeflow and oneTBB (e.g., 22% less by Pipeflow at 40 cores).

$2$$4$$6$$8$$10$$0.5$$0.6$$0.7$$0.8$$0.9$$1$Number of CorunsThroughputCorun (8
Stages)PipeflowoneTBB

$2$$4$$6$$8$$10$$0.2$$0.4$$0.6$$0.8$$1$Number of CorunsThroughputCorun (80
Stages)PipeflowoneTBB

Figure 12. Throughput of corunning micro-benchmark programs with 8 and 80
stages.

Figure 12 compares the throughput by corunning the same program up to 10
times. We use the weighted speedup to measure the system throughput, which is
the sum of the individual speedup of each process over a baseline execution
time (Ding et al., 2012). A throughput of one implies that the corun
throughput is the same as if those processes run consecutively. On the left,
the pipeline has 8 stages and 8 parallel lines. On the right, the pipeline has
80 stages and 80 parallel lines. Both of them run 65K scheduling tokens using
40 threads. The experiment emulates a server-like environment where different
pipeline applications compete for the same resources. We can see that Pipeflow
outperforms oneTBB in most coruns. For example, at 10 coruns, Pipeflow is 1.1
$\times$ and 1.5$\times$ better than oneTBB with 8 and 80 stages,
respectively.

$20$$40$$60$$80$$10$$20$$30$Number of StagesRuntime (s)Runtime (16
Cores)PipeflowoneTBB

$20$$40$$60$$80$$194$$194.5$$195$$195.5$$196$Number of StagesMaximum RSS
(MB)Memory (16 Cores)PipeflowoneTBB

$20$$40$$60$$80$$10$$12$$14$$16$$18$$20$Number of StagesRuntime (s)Runtime (32
Cores)PipeflowoneTBB

$20$$40$$60$$80$$194.5$$195$$195.5$$196$$196.5$Number of StagesMaximum RSS
(MB)Memory (32 Cores)PipeflowoneTBB

$20$$40$$60$$80$$10$$12$$14$$16$$18$Number of StagesRuntime (s)Runtime (40
Cores)PipeflowoneTBB

$20$$40$$60$$80$$195$$196$$197$$198$Number of StagesMaximum RSS (MB)Memory (40
Cores)PipeflowoneTBB

Figure 13. Runtime and memory comparisons between Pipeflow and oneTBB to
complete a design of 1.5M nodes and 3.5M edges with different numbers of
serial stages.

###  4.3. VLSI Circuit Timing Analysis Algorithm

We applied Pipeflow to solve a VLSI static timing analysis (STA) problem. The
goal is to analyze the timing landscape of a circuit design and report
critical paths that do not meet the given constraints (e.g., setup and hold).
As presented in Figure 2, modern STA engines leverage pipeline parallelism to
speed up the timing propagations. However, nearly all of them count on OpenMP-
based loop parallelism with layer-by-layer synchronization (Huang et al.,
2021). With Pipeflow, we can directly formulate the problem as a task-parallel
pipeline to improve task asynchrony. As the analysis complexity continues to
increase, more analysis tasks (e.g., RC, delay calculators, pessimism
reduction) are incorporated into each node in the STA graph. These tasks can
be encapsulated in a sequence of stage functions to overlap in graph across
parallel lines. We modify a large circuit design of 1.5M nodes and 3.5M edges
from (Huang et al., 2021) and study the performance under different stage
counts. Each node has a stage task to calculate delay values at a specific
configuration using 2D matrix multiplication.

Figure 13 compares the runtime and memory between Pipeflow and oneTBB up to 80
stages. We use 80 parallel lines for all experiments; we do not observe much
difference in other numbers of parallel lines as both Taskflow and oneTBB have
an adaptive work-stealing strategy to balance the number of running threads
with dynamic task parallelism. In general, Pipeflow outperforms oneTBB at
large stage numbers. For example, using 40 cores and 72 stages, Pipeflow is
10% faster than oneTBB. In terms of memory usage, Pipeflow is always better
than oneTBB regardless of the number of stages and cores. Pipeflow consumes
less memory than oneTBB does because all stage tasks perform computations
directly on a global graph data structure captured in the pipe callable. The
data passing interface between successive stages in oneTBB thus becomes a
significant yet unnecessary overhead.

$2$$4$$6$$8$$10$$0.4$$0.6$$0.8$$1$Number of CorunsThroughputCorun (8
stages)PipeflowoneTBB

$2$$4$$6$$8$$10$$0.2$$0.4$$0.6$$0.8$$1$Number of CorunsThroughputCorun (80
Stages)PipeflowoneTBB

Figure 14. Throughput of corunning the STA program.

Next, we compare the throughput by corunning the same program up to 10 times.
Corunning an STA program is very common for reporting the timing data of a
design at different input library files (Kahng, 2018). The effect of pipeline
scheduling propagates to all simultaneous processes. Hence, throughput is a
good measurement for the inter-operability of a pipeline-based STA algorithm.
We corun the same analysis program up to 10 processes that compete for 40
cores. Again, we use the weighted speedup to measure the throughput. Figure 14
plots the throughput across 10 coruns at 8 and 80 stages. We can see that
Pipeflow outperforms oneTBB at all coruns. For instance, at 10 coruns,
Pipeflow is 1.7$\times$ and 1.2 $\times$ better than oneTBB with 8 and 80
stages, respectively.

###  4.4. VLSI Detailed Placement Algorithm

We applied Pipeflow to solve a VLSI detailed placement problem. Detailed
placement is a critical step in physical optimization. The goal is to optimize
the interconnect among millions of logic gates or instances for improved
timing and power. Connected instances are grouped to a net with interconnect
modeled in Manhattan distance. We consider the detailed placement algorithm in
DREAMPlace (Lin et al., 2020), namely local reordering. The algorithm decides
an optimal order of four consecutive instances in a window of a placement row
that produces minimum interconnect wirelength. We can parallelize the
reordering algorithm using pipeline. Each row corresponds to a parallel stage
that finds the best ordering of cells in a window from the top to the bottom.
The scheduling tokens sweep through all windows from the left to the right.
Figure 15 illustrates the algorithm.

Figure 15.  Parallel local reordering algorithm using pipeline. Reordering
cells in window 1 of row 1 (R1W1) cannot run in parallel with R2W1 due to the
vertical dependency D–E. However, R1W1 can overlap with R2W2 despite D–F,
because the algorithm deals with Manhattan distance for wirelength. We can
always assume that F is fixed on the right of window 1 within the view of
R1W1. Thus, we update vertical windows in a linear pipeline, R1$\to$R2$\to$R3.

$1$$8$$16$$24$$32$$40$$1{,}000$$2{,}000$$3{,}000$$4{,}000$Number of
CoresRuntime (s)Runtime (adaptec1)PipeflowoneTBB

$1$$8$$16$$24$$32$$40$$165.5$$166$$166.5$$167$$167.5$$168$Number of
CoresMaximum RSS (MB)Memory (adaptec1)PipeflowoneTBB

$1$$8$$16$$24$$32$$40$$1$$2$$3$$4$$5$$\cdot 10^{4}$Number of CoresRuntime
(s)Runtime (bigblue4)PipeflowoneTBB

$1$$8$$16$$24$$32$$40$$1.61$$1.62$$1.63$$1.64$Number of CoresMaximum RSS
(GB)Memory (bigblue4)PipeflowoneTBB

Figure 16. Runtime and memory data of the pipeline-based placement algorithm
for two industrial designs, adaptec1 (890 stages) and bigblue4 (2694 stages).

Figure 16 compares the runtime and memory data between Pipeflow and oneTBB for
two industrial designs, adaptec1 and bigblue4. adaptec1 is a medium design
with 211K instances and 221K nets (instance dependencies), defining 890 stages
for 890 placement rows and 10692 windows. bigblue4 is a large design with 2.1M
instances and 2.2M nets, defining 2694 stages for 2694 placement rows and
32190 columns. Both Pipeflow and oneTBB scale with increasing numbers of
cores, whereas Pipeflow always outperforms oneTBB 3–24%. For instance, in
bigblue4 (40 cores), Pipeflow finishes the placement algorithm in 6131
seconds, whereas oneTBB needs 8213 seconds. Such improvement is significant as
practical design closure process can invoke millions of placement iterations
to optimize the physical layout. Likewise, Pipeflow outperforms oneTBB in
memory usage. The difference is slight (about 1%) because most memory is taken
by the placement problem itself, including the data structure of rows and
instances.

###  4.5. Insight from the CAD Algorithm Developers

As an experienced parallel CAD researcher, Pipeflow has assisted us to
overcome many programming challenges. In the previous two experiments, the
data is explicitly managed by the application algorithms and does not go
through any data abstraction layers of oneTBB. The real need is a task-
parallel pipeline programming framework that 1) gives us full control over
data and 2) allows us to probe each scheduled task. For instance, when
implementing the placement algorithm, we capture the row data from a global
database in each pipe callable and use the pipeflow variable to get the line
numbers of a scheduled task to index its window locations. However, oneTBB has
abstracted these components out, and we have to implement another mapping
strategy to get these data from each filter. Similar problems exist in other
libraries too.

##  5\. Related Work

#### Pipeline programming models

have received intensive research interest. Most of them are data-centric using
static template instantiation or dynamic runtime polymorphism to model data
processing in a pipeline. To name a few popular examples: oneTBB (TBB, eTBB)
and TPL (Leijen et al., 2009) require explicit definitions of input and output
types for each stage; GrPPI (del Rio Astorga et al., 2017) provides a
composable abstraction for data- and stream-parallel patterns with a pluggable
back-end to support task scheduling; FastFlow (Aldinucci et al., 2017) models
parallel dataflow using pre-defined sequential and parallel building blocks;
TTG (Bosilca et al., 2020) focuses on dataflow programming using various
template optimization techniques; SPar (Griebler et al., 2017; Loff et al.,
2021; Hoffman et al., 2022; Griebler et al., 2019) analyzes annotated
attributes extracted from the data and stream parallelism domain, and
automatically generates parallel patterns defined in FastFlow; Proteas
(Mastoras and Gross, 2018a) introduces a programming model for directive-based
parallelization of linear pipeline; (Vogel et al., 2021a; Vogel et al., 2021b)
propose self-adaptive mechanism to decide the degree of parallelism and
generate the pattern compositions in FastFlow. These programming models,
however, constrain users to design pipeline algorithms using their data
models, making it difficult to use especially for applications that only need
pipeline scheduling atop custom data structures.

#### Existing pipeline scheduling algorithms

typically co-design task scheduling and buffer structures to strive for the
best performance. For instance, oneTBB (TBB, eTBB) defines a per-stage buffer
counter to synchronize data tokens among stages and lines, coupled with a
small object allocator to minimize the data allocation overhead; GRAMPS
(Sanchez et al., 2011) designs a buffer manager with per-thread fix-sized
memory pools to dynamically allocate new data and release used ones; FastFlow
(Aldinucci et al., 2017) design a lock-free queue with a mechanism to transfer
data ownership between senders and receivers, but this method can incur
imbalanced load and requires non-trivial back-pressure management; HPX (Kaiser
et al., 2014) counts on a channel data structure and standard future objects
to pass data around tasks, but the creation of share states becomes expensive
when the pipeline is large; Cilk-P (Lee et al., 2015) employs per-stage queues
coupled with two counter types to track static and dynamic dependencies of
each node, but it targets on-the-fly pipeline parallelism which is orthogonal
to our focus; FDP (Suleman et al., 2010) proposes a learning-based mechanism
to adapt scheduling to an environment, but it requires expensive runtime
profiling that may not work well for highly irregular applications like CAD.
In terms of load balancing, most pipeline schedulers leverage work stealing,
which has been reported with better performance than static policies (Hoffmann
et al., 2004; Navarro et al., 2009; Sanchez et al., 2011; Lee et al., 2015;
Leiserson, 2010; Blumofe et al., 1995). However, for some special cases, such
as fine-grained load-imbalanced pipelines, static policies perform comparably.
For example, Pipelight (Mastoras and Gross, 2019b) implements a load balancing
technique based on two static scheduling algorithms, DSWP (Ottoni et al.,
2005; Rangan et al., 2008; Raman et al., 2008) and LBPP (Kamruzzaman et al.,
2013); Pipelite (Mastoras and Gross, 2019a) and URTS (Mastoras and Gross,
2018b) introduce dynamic schedulers using ticket-based synchronization and
directive-based model language for linearpipelines, respectively. While co-
designing task scheduling and buffer structures has certain advantages for
data-centric pipeline (e.g., data locality), the cost of managing data can be
significant yet unnecessary, especially for applications that only exploit
task parallelism in pipeline.

##  6\. Conclusion

We have introduced Pipeflow, an efficient C++ pipeline programming framework
atop the Taskflow system. We have designed a new task-parallel programming
model that separates data abstraction and task scheduling. By focusing on the
pipeline tasking, we have introduced a simple yet efficient scheduling
algorithm based on Taskflow’s work-stealing runtime with dynamic load
balancing. We have evaluated the performance of Pipeflow on micro-benchmarks
and real applications. For example, Pipeflow outperforms oneTBB 24% and 10%
faster in a VLSI placement and a timing analysis workloads that adopt pipeline
parallelism to speed up runtimes, respectively. Our future work plans to apply
Pipeflow to more CAD applications and bring interdisciplinary ideas to the HPC
domain.

## References

  * (1)
  * TBB (eTBB) Intel oneTBB.  https://github.com/oneapi-src/oneTBB
  * Tas (flow) Taskflow.  https://github.com/taskflow/taskflow
  * Ajayi et al. (2019) Tutu Ajayi, Vidya A. Chhabria, Mateus Fogaça, Soheil Hashemi, Abdelrahman Hosny, Andrew B. Kahng, Minsoo Kim, Jeongsup Lee, Uday Mallappa, Marina Neseem, Geraldo Pradipta, Sherief Reda, Mehdi Saligane, Sachin S. Sapatnekar, Carl Sechen, Mohamed Shalan, William Swartz, Lutong Wang, Zhehong Wang, Mingyu Woo, and Bangqi Xu. 2019.  Toward an Open-Source Digital Flow: First Learnings from the OpenROAD Project. In _ACM/IEEE DAC_.
  * Aldinucci et al. (2017) Marco Aldinucci, Marco Danelutto, Peter Kilpatrick, and Massimo Torquati. 2017.  _FastFlow: High-Level and Efficient Streaming on Multicore_.  John Wiley and Sons, Ltd, Chapter 13, 261–280.
  * Blumofe et al. (1995) Robert Blumofe, Christopher Joerg, Bradley Kuszmaul, Charls Leiserson, Keith Randall, and Yuli Zhou. 1995.  Cilk: An Efficient Multithreaded Runtime System. In _ACM PPOPP_. 207–216.
  * Bosilca et al. (2013) G. Bosilca, A. Bouteiller, A. Danalis, M. Faverge, T. Herault, and J. J. Dongarra. 2013.  PaRSEC: Exploiting Heterogeneity to Enhance Scalability.  _Computing in Science Engineering_ 15, 6 (2013), 36–45.
  * Bosilca et al. (2020) G. Bosilca, R.J. Harrison, T. Herault, M.M. Javanmard, P. Nookala, and E.F. Valeev. 2020\.  The Template Task Graph (TTG) - an emerging practical dataflow programming paradigm for scientific simulation at extreme scale. In _IEEE/ACM ESPM2_. 1–7.
  * del Rio Astorga et al. (2017) David del Rio Astorga, Manuel F. Dolz, Javier Fernández, and J. Daniel García. 2017.  A Generic Parallel Pattern Interface for Stream and Data Processing. In _Concurrency and Computation: Practice and Experience_.
  * Ding et al. (2012) Xiaoning Ding, Kaibo Wang, Phillip B. Gibbons, and Xiaodong Zhang. 2012.  BWS: balanced Work Stealing for Time-sharing Multicores. In _ACM EuroSys_. 365–378.
  * Griebler et al. (2017) Dalvan Griebler, Marco Danelutto, Massimo Torquati, and Luiz Gustavo Fernandes. 2017.  SPar: A DSLfor High-Level and Productive Stream Parallelism. In _Parallel Processing Letters_ , Vol. 27.
  * Griebler et al. (2019) Dalvan Griebler, Renato B. Hoffmann, Marco Danelutto, and Luiz Gustavo Fernandes. 2019.  High-Level and Productive Stream Parallelism for Dedup, Ferret, and Bzip2. In _The Journal of Parallel Programming_.
  * Hoffman et al. (2022) Renato B. Hoffman, Junior Loff, Dalvan Griebler, and Luiz Gustavo Fernandes. 2022.  OpenMP as Runtime for Providing High-Level Stream Parallelism on Multi-Cores. In _The Journal of Supercomputing_.
  * Hoffmann et al. (2004) Ralf Hoffmann, Matthias Korch, and T. Rauber. 2004.  Performance Evaluation of Task Pools Based on Hardware Synchronization. In _ACM Supercomputing_.
  * Huang et al. (2021) Tsung-Wei Huang, Guannan Guo, Chun-Xun Lin, and Martin Wong. 2021\.  OpenTimer 2.0: A New Parallel Incremental Timing Analysis Engine.  _IEEE TCAD_ 40, 4 (2021), 776–789.
  * Huang et al. (2022) Tsung-Wei Huang, Dian-Lun Lin, Chun-Xun Lin, and Yibo Lin. 2022\.  Taskflow: A Lightweight Parallel and Heterogeneous Task Graph Computing System. In _IEEE TPDS_ , Vol. 33. 1303 – 1320.
  * Kahng (2018) Andrew B. Kahng. 2018\.  Reducing Time and Effort in IC Implementation: A Roadmap of Challenges and Solutions. In _IEEE/ACM DAC_.
  * Kaiser et al. (2014) Hartmut Kaiser, Thomas Heller, Bryce Adelstein-Lelbach, Adrian Serio, and Dietmar Fey. 2014\.  HPX: A Task Based Programming Model in a Global Address Space _(PGAS)_. 6:1–6:11.
  * Kamruzzaman et al. (2013) M. Kamruzzaman, S. Swanson, and D. M. Tullsen. 2013\.  Load-Balanced Pipeline Parallelism. In _IEEE SC_. 1–12.
  * Lee et al. (2015) I-Ting Angelina Lee, Charles E. Leiserson, Tao B. Schardl, Zhunping Zhang, and Jim Sukha. 2015\.  On-the-Fly Pipeline Parallelism.  _ACM Trans. Parallel Comput._ 2, 3 (2015).
  * Leijen et al. (2009) Daan Leijen, Wolfram Schulte, and Sebastian Burckhardt. 2009\.  The Design of a Task Parallel Library. In _ACM OOPSLA_. 227–241.
  * Leiserson (2010) Charles E. Leiserson. 2010\.  The Cilk++ concurrency platform.  _The Journal of Supercomputing_ 51, 3 (01 Mar 2010), 244–257.
  * Lin et al. (2020) Yibo Lin, Zixuan Jiang, Jiaqi Gu, Wuxi Li, Shounak Dhar, Haoxing Ren, Brucek Khailany, and David Z. Pan. 2020\.  DREAMPlace: Deep Learning Toolkit-Enabled GPU Acceleration for Modern VLSI Placement.  _tcad_ (June 2020).
  * Loff et al. (2021) Junior Loff, Renato B. Hoffman, Dalvan Griebler, and Luiz Gustavo Fernandes. 2021.  High-Level Stream and Data Parallelism in C++ for Multi-Cores. In _SBLP_. 41–48.
  * Mastoras and Gross (2018a) Aristeidis Mastoras and Thomas R. Gross. 2018a.  Understanding parallelization Tradeoffs for Linear Pipelines. In _ACM PMAM_. 1–10.
  * Mastoras and Gross (2018b) Aristeidis Mastoras and Thomas R. Gross. 2018b.  Unifying Fixed Code Mapping, Communication, Synchronization and Scheduling Algorithms for Efficient and Scalable Loop Pipelining. In _IEEE TPDS_ , Vol. 29. 2136–2149.  Issue 9.
  * Mastoras and Gross (2019a) Aristeidis Mastoras and Thomas R. Gross. 2019a.  Efficient and Scalable Execution of Fine-Grained Dynamic Linear Pipelines. In _ACM TACO_ , Vol. 16. 1–26.  Issue 2.
  * Mastoras and Gross (2019b) Aristeidis Mastoras and Thomas R. Gross. 2019b.  Load-balancing for load-imbalanced fine-grained linear pipelines. In _Parallel Computing_ , Vol. 29. 2136–2149.  Issue 9.
  * Navarro et al. (2009) Angeles Navarro, Rafael Asenjo, Siham Tabik, and Calin Cascaval. 2009.  Load Balancing Using Wok-Stealing for Pipeline Parallelism in Emerging Applications. In _ACM ICS_. 517–518.
  * Ottoni et al. (2005) Guilherme Ottoni, Ram Rangan, Adam Stoler, and David I. August. 2005.  Automatic Thread Extraction with Decoupled Software Pipelining. In _IEEE/ACM MICRO_. 105–118.
  * Raman et al. (2008) Easwaran Raman, Guilherme Ottoni, Arun Raman, Matthew J. Bridges, and David I. August. 2008.  Parallel-Stage Decoupled Software Pipelining. In _IEEE/ACM CGO_. 114–123.
  * Rangan et al. (2008) Ram Rangan, Neil Vachharajani, Guilherme Ottoni, and David I. August. 2008.  Performance Scalability of Decoupled Software Pipelining. In _ACM TACO_ , Vol. 5. 1–25.  Issue 2.
  * Sanchez et al. (2011) Daniel Sanchez, David Lo, Richard M. Yoo, Jeremy Sugerman, and Christos Kozyrakis. 2011.  Dynamic Fine-Grain Schedulig of Pipeline Parallelism. In _IEEE PACT_. 22–32.
  * Suleman et al. (2010) M. Aater Suleman, Moinuddin K. Qureshi, Khubaib, and Yale N. Patt. 2010.  Feedback-Directed Pipeline Parallelism. In _IEEE PACT_. 147–156.
  * Vogel et al. (2021a) Adriano Vogel, Dalvan Griebler, and Luiz Gustavo Fernandes. 2021a.  Providing high-level self-adaptive abstractions for stream parallelism on multicores. In _SPE_ , Vol. 51. 1194–1217.  Issue 6.
  * Vogel et al. (2021b) Adriano Vogel, Gabriele Mencagli, Dalvan Griebler, Marco Danelutto, and Luiz Gustavo Fernandes. 2021b.  Towards ON-the-fly Self-Adaptation of Stream Parallel Patterns. In _IEEE PDP_.
  * Xu et al. (2019) B. Xu, K. Zhu, M. Liu, Y. Lin, S. Li, X. Tang, N. Sun, and D. Z. Pan. 2019.  MAGICAL: Toward Fully Automated Analog IC Layout Leveraging Human and Machine Intelligence: Invited Paper. In _IEEE/ACM ICCAD_. 1–8.