# BottleMod: Modeling Data Flows and Tasks for Fast Bottleneck Analysis

Ansgar Lößer<EMAIL_ADDRESS>0000-0002-7627-9664 TU
DarmstadtGermany ,  Joel Witzke<EMAIL_ADDRESS>0000-0002-0831-8078 Zuse
Institute BerlinGermany ,  Florian Schintke<EMAIL_ADDRESS>0000-0003-4548-788X Zuse Institute BerlinGermany and  Björn Scheuermann
<EMAIL_ADDRESS>TU DarmstadtGermany

(2022)

###### Abstract.

In the recent years, scientific workflows gained more and more popularity. In
scientific workflows, tasks are typically treated as black boxes. Dealing with
their complex interrelations to identify optimization potentials and
bottlenecks is therefore inherently hard. The progress of a scientific
workflow depends on several factors, including the available input data, the
available computational power, and the I/O and network bandwidth. Here, we
tackle the problem of predicting the workflow progress with very low overhead.
To this end, we look at suitable formalizations for the key parameters and
their interactions which are sufficiently flexible to describe the input data
consumption, the computational effort and the output production of the
workflow’s tasks. At the same time they allow for computationally simple and
fast performance predictions, including a bottleneck analysis over the
workflow runtime. A piecewise-defined bottleneck function is derived from the
discrete intersections of the task models’ limiting functions. This allows to
estimate potential performance gains from overcoming the bottlenecks and can
be used as a basis for optimized resource allocation and workflow execution.

††copyright: acmcopyright††journalyear: 2022††doi: XXXXXXX.XXXXXXX

###### Acknowledgements.

This work received funding from the Sponsor German Research Foundation (DFG)
https://www.dfg.de/, Grant #CRC 1404: _FONDA: Foundations of Workflows for
Large-Scale Scientific Data Analysis_ (Leser et al., 2021).

##  1\. Introduction

Many scientific fields have a growing need for computationally intensive data
analysis, from genome analysis to satellite image processing. Such complex
analysis processes are often referred to as scientific workflows. A scientific
workflow consists of multiple processing steps, so-called tasks. Tasks can
depend on the results of other tasks, creating a dependency graph between
them.

Often, a single task is simply the execution of a program on one or more
specific set(s) of input data, creating one or more outputs, which may then
form input(s) of subsequent tasks. Such tasks can have very different temporal
I/O behavior. An intuitive example of this is video processing: Reversing a
video file needs complete input before it can start outputting data. Other
operations work on the data sequentially in order, like re-encoding a video:
they can begin producing output while the input is still incomplete. If a
video reversal task follows after some other task $X$, then $X$ must complete
before the reversal task can start with its work. A re-encoding task in the
same position within a workflow, on the other hand, could well run in parallel
to $X$—at least if task $X$ outputs data before its own completion and to the
extent to which (a) computation power and (b), if applicable, network capacity
for the data transfer between the two tasks are available. All these factors
determine whether, for instance, pipelined processing in a specific part of a
workflow is a viable option for accelerating the execution or not.

Similar patterns exist on the output side: A video reversal task can only
start when the input data is complete, but it can output continuously while
the task is progressing; a task which, for instance, counts occurrences of
specific patterns in a video and outputs the total number for each pattern
will only be able to start outputting results after the entire video has been
processed. Other, almost arbitrary dependencies of input and output behavior
over the course of execution of a task are easily conceivable, and a large
variety of behaviors exists in virtually any field in which scientific
workflows are applied.

Even if the behavior of individual tasks is usually reasonably simple, the
interdependencies can quickly become complex. Depending on the data input and
output behaviour of predecessor and successor tasks in the workflow, very
different execution behaviour and very different resource utilization over
time will result. How to understand and analyze these interdependencies given
the structure of a specific workflow? How to model them appropriately? How to
draw conclusions from them? These are the questions we are tackling here.

We propose a way to model a task’s I/O behavior over computation time in an
abstract way. We show how, based on such models, one can derive and predict
the overall progress of the workflow, as well as the structure of the
bottlenecks limiting the execution performance. The models are modular and
allow the combination of task models to express chains of tasks or even
complete scientific workflows. They are simple, yet flexible enough to
describe a wide range of task behaviors. And they are constructed in a way
that allows for quick and lightweight computations. The algorithm which we
propose to do so operates in a quasi-symbolic way on models that are given by
piecewise-defined functions. It is inspired by discrete-event simulation and
considers only those points in time where the involved functions change to the
next piece. This is a novel take on modeling the execution behavior of
scientific workflows. It scales much more favourably than any existing
approach, and therefore also allows, e. g., for repeated evaluation during a
workflow execution, adapting the predictions to live measurements.

The resource management for workflow execution—i. e., an operating system in
conjunction with a workflow execution environment like e. g., Nextflow
(Tommaso et al., 2017) with Kubernetes (Foundation, 2022)—can make more
informed decisions if it knows the bottlenecks and the potential performance
gain when they are resolved. The specific construction of a scheduler that
makes use of the modeling approach proposed here is out of scope for this
work. Nevertheless, one possible application of runtime predictions from task
I/O models is to determine the potential performance gain and upcoming
resource demand when the resource allocation is changed. This allows, for
instance, for a comparison of different scheduling options.

We introduce our formal model for tasks and their execution in Sect. 2; It
describes the relations between input, output, and resources. Based on this
model, we analyze individual tasks and the combination of tasks to form
workflows, their progress, their bottlenecks, and the actual resource
utilization in Sect. 3. We discuss the practical application of the approach
and the challenges and tradeoffs involved in Sect. 4. An evaluation with an
example workflow confirms the model’s ability to predict real-world executions
in Sect. 5. A basic performance comparison to an existing modeling approach is
given in Sect. 6.

##  2\. Modeling a Process Execution

This paper introduces BottleMod, a way of modeling the execution of a
scientific workflow’s task as a so-called _process_ in a generic mathematical
fashion. A _process_ can also be used to model other events. An example is a
data transfer over the network, as demonstrated later in Sect. 5.

Predicting the behavior of a task needs process-specific and execution-
environment-specific knowledge. While a developer might know how a specific
program works, the amount of resources available for the execution is
typically unknown during development. On the other hand, the execution
environment or the corresponding system administrator might have detailed
knowledge about the available resources and how they will be allocated to the
tasks. However, they do not know how the tasks work. BottleMod is designed to
distinguish between the process-specific requirements and execution-specific
resource allocation. This separation enables different parties to describe the
requirements and resource allocation, resolving the issue. The information for
the task model could either be statically annotated, measured, or learned from
other executions of the same task. In the long run, BottleMod could be used
for modeling, simulation, and analysis, providing valuable information for
resource allocation and helping a dynamic scheduler with short- to midterm
decisions. Also, the result visualization could be helpful in understanding
how bottlenecks in an early stage can influence the execution later.

We model processes by their _data_ and _resource_ demands. Here, each process
can have an arbitrary number of data and resource requirements.

  1. (1)

_Data_ is the input data directly available to the process. Input data can be
stored for later usage. The model assumes that an unlimited amount of data can
be stored, and that stored data does not expire.

  2. (2)

_Resources_ cannot be stored. Unused resources will not yield an advantage for
the execution but are just gone. Therefore, resources help modeling the CPU
time an application needs or the data rate of a link used for a data transfer.

These requirements are defined by _requirement_ functions for each resource
and input data per process. The functions describe how much of which input
data or resource the process will need to progress until a certain point,
measured by an abstract _progress_ metric. Accordingly, these functions are
always monotonically increasing. While requirement functions describe the
requirements of a process, so-called _input_ functions for a process define
the amount of available data input and available resource at each point in
time. Notice that contrary to the data input, the allocated amount of a
resource can be lowered during execution.

These functions contain all the necessary information to derive a _progress_
function, describing the progress of the process over time—representing its
execution. _Output_ functions map the process’s progress to the amount of data
generated, enabling to calculate at which point in time how much usable output
data is generated. The dimensions for all these functions can be chosen
freely, given they are consistent for those interacting.

###  2.1. Progress Metric

The progress metric $p$ defines how far the process has progressed. This
metric does not need to relate to any resource or the estimated time to
complete the process. It is completely arbitrary and chosen by the developer
of the model. The progress metric must only be consistent inside a single
process, i.e., all process-describing functions for the same process must use
the same progress metric.

###  2.2. Requirement Functions

A requirement ($\mathcal{R}$) function describes how much input a process
needs to achieve a certain progress. This relation corresponds to the
requirements of a process independent of its execution environment. Typically,
defining the process’s needs would be characterized by the amount of data or
resources needed at a specific time. However, such a direct definition would
couple a process’s own attributes with execution-environment-specific
ones—including the availability of data and the resource allocation.
Requirement functions are time-independent but only provide the input-to-
progress relation to separate the process’s requirements and allocated
resources. Therefore, our approach is quite unconventional.

####  2.2.1. Data Requirement Functions

A _data_ requirement function defines the data requirement of a process. For
each $k\in\\{1,\ldots,K\\}$, where $K$ is the number of relevant data inputs,
the mathematical function $\mathcal{R}_{Dk}(n_{Dk})$ maps the amount of data
input needed $n_{Dk}$ (in bytes, for example) to the maximum possible progress
the process can make given there are no other limitations. Those functions
must be monotonically increasing since the possible progress cannot decrease
when more input data becomes available.

_$\mathcal{R}_{\mathit{Dstream}}(i)$__$\mathcal{R}_{\mathit{Dburst}}(i)$__$\mathcal{R}_{\mathit{Rstream}}(p)$__$\mathcal{R}_{\mathit{Rburst}}(p)$_
Figure 1. Exemplary requirement functions. Part (a): common _data_ requirement
functions, where ‘stream’ is a data requirement function modeling a process
that can progress with every new byte of the data dependency’s input $i$ read
(akin to stream processing). In contrast, ‘burst’ is a data input where all
data must first be read entirely by the process before progress can be made.
Part (b): common _resource_ requirement functions. Here, ‘stream’ shows a
resource needed continuously to let the process make progress $p$. ‘Burst’
shows a resource only required at the beginning, e.g., for a process that
needs all its CPU time before it progresses at all.

Two examples of such functions $\mathcal{R}_{Dk}(n_{Dk})$ are shown in Figure
1 (a). Simply reencoding a video would need just a little bit of input data
for the process to start making progress. This would correlate to the function
type displayed by ‘stream’. Reversing a video needs all input data before any
progress can be made and would, therefore, correspond to ‘burst’.

####  2.2.2. Resource Requirement Functions

_Resource_ requirement functions work similarly to data requirement functions.
For each resource $\ell\in\\{1,\ldots,L\\}$, where $L$ is the number of
relevant resources, the mathematical function $\mathcal{R}_{R\ell}(p)$ yields
the amount of resource needed (in a resource-dependent unit such as CPU
cycles, transferred bytes, …) at the progress $p$ of the process.

While the data requirement functions limit the maximum progress of a process,
resources may only limit the progression speed. When using CPU time as an
example, a resource function would define how much CPU time (y-axis) is needed
to progress to a particular execution point (x-axis). I.e., if the process
requires the same amount of CPU time to progress, e.g., reencoding a video,
the corresponding resource requirement function would be a linear function
with a constant slope (as seen as ‘stream’ in Figure 1 (b)). Another example
would be a process that needs all the CPU time before it can progress. Such an
example is displayed as ‘burst’ in Figure 1 (b).

###  2.3. Input Functions

Requirement functions alone do not suffice to model a process’s actual
execution. Additionally, other functions are needed for both the $K$ required
data inputs and the $L$ relevant resources a process uses. The data input
function $I_{Dk}(t)$ and the resource input function $I_{R\ell}(t)$ relate the
real-time $t$ to the available amount of input data and resources for any
point in time.

These functions are not directly related to the process itself but describe a
particular execution environment, e.g., CPU time assigned by a scheduler,
input data the process depends on from a network link, or a previous process.

Similar to the data requirement functions, the data input functions
$I_{Dk}(t)$ describe how much input data is available at which point in time.
They are monotonically increasing as input data provided once are not lost
since all data are storable.

Resource input functions $I_{R\ell}(t)$, on the other hand, are neither
accumulative nor necessarily monotonically increasing. They denote the
resource amount per time unit available at the time $t$. For example, if a
process is assigned the same amount of a CPU resource over time, the
corresponding resource allocation function $i_{R\ell}=I_{R\ell}(t)$ would be a
constant function. It would denote that a fixed number $i_{R\ell}$ of CPU
cycles per time unit is allocated to the process’s execution at every point in
time.

###  2.4. Data Output Functions

The above functions already contain enough information to determine the
execution behavior of the process, including execution time, resource, and
data usage. Deriving this information is possible by calculating the progress
function, which defines the progress made over time and is described in Sect.
3. This still does not define how much data the process generates. To conclude
this, data output functions are needed.

Data output functions $o_{m}=O_{m}(p)$ define for each $m\in\\{1,\ldots,M\\}$,
where $M$ is the number of data outputs, how much data $o_{m}$ is already
generated (y-axis) at a certain progress $p$ (x-axis). They resemble inverted
data requirement functions. In combination with the calculated progress
function of a process, data output functions are used to determine how much
data is generated at which point in time. This output is particularly useful
since it is identical to data input functions and, therefore, can be used as
an input in a successor process, which is explained in more detail in Sect.
3.4.

##  3\. Deducing the Behavior of a Process

Data Resource 1 Resource L $i_{D1}=I_{D1}(t)$ _data input function_
$p_{D1}=\mathcal{R}_{D1}(n_{D1})$ _data requirement fun._

combine

_map data req. to time according to input_ $P_{D1}(t)$ _data progress fun._
Data 1

…

$\forall k\in\\{1,\ldots,K\\}$ $i_{DK}=I_{DK}(t)$
$p_{DK}=\mathcal{R}_{DK}(n_{DK})$

combine

$P_{DK}(t)$ Data K

slowest progress per time (§3.1)

$P_{D}(t)$ $i_{R1}=I_{R1}(t)$ _resource allocation fun._
$n_{R1}=\mathcal{R}_{R1}(p)$ _resource requirement fun._

…

$\forall\ell\in\\{1,\ldots,L\\}$ $i_{RL}=I_{RL}(t)$
$n_{RL}=\mathcal{R}_{RL}(p)$ Resources

impose resource limitations (§3.2)

$P(t)$ Figure 2. Overview of the steps required to calculate the progress
function for a process. The data input functions $I_{Dk}(t)$ and data
requirement functions $\mathcal{R}_{Dk}(n_{Dk})$ are combined to calculate the
maximum possible progress $P_{Dk}(t)$ regarding a certain data input
$k\in\\{1,\ldots,K\\}$. Taking the minimum of this progress over all data
inputs yields the maximum possible progress data-wise $P_{D}(t)$. Together
with all resource allocation functions $I_{R\ell}(t)$ and all resource
requirement functions $\mathcal{R}_{R\ell}(p)$ ($\ell\in\\{1,\ldots,L\\}$) we
can calculate the overall progress function $P(t)$. The iterative algorithm
for the calculation is described in Sect. 3.2.

Combining the process-specific requirement functions and execution-specific
input functions allows for calculating the time a process needs to achieve
progress. The amount progress a process makes until a point in time $t$ is
represented by the _progress_ function $P(t)$. In this model, a process
finishes when the maximum progress is reached. Analyzing a process’s execution
corresponds to calculating the progress function of that process.

Calculating the progress function happens in two steps (Figure 2). First, the
data limitations are combined to deduce the maximum progress possible
regarding all process data inputs. Then, the effects of resource limits are
taken into account to infer the process’s overall progress.

###  3.1. Data Progress

For every pair of a data requirement function $\mathcal{R}_{Dk}(n_{Dk})$ and
its respective data input function $I_{Dk}(t)$, we calculate a corresponding
data progress function $P_{Dk}(t)$. This function defines the maximum progress
limited by the specific data input $k$ over time. Since
$\mathcal{R}_{Dk}(n_{Dk})$ specifies the possible progress with a given amount
of input data, and $I_{Dk}(t)$ defines the available input data at a given
time, $P_{Dk}(t)$ can be calculated as follows:

(1) $P_{Dk}(t)=\mathcal{R}_{Dk}(I_{Dk}(t)),\quad\forall k\in\\{1,\ldots,K\\}$

These individual data progress functions (see Figure 3 for an example) are
combined into a function $P_{D}(t)$ that defines the maximum possible progress
based on all data inputs. Since the actual progress can never be higher than
the lowest of the data progress functions, $P_{D}(t)$ can be generated by
section-wise choosing the function that yields the lowest value (solid line in
Figure 3). We denote this selection as $\min$ in:

(2) $P_{D}(t)=\min(P_{D1}(t),\ldots,P_{DK}(t))$

The overall progress $P(t)$ is not only limited by the data progress but also
by the resources. Therefore, the data progress imposes an upper limit on the
overall progress:

(3) $P(t)\leq P_{D}(t)$

Data Resource 1 Resource L _$P_{D}(t)$ (solid line)__limited by:_ data2
_limited by:_ data1data0 _dashed lines: input data availability over time_
Figure 3. Example of data progress functions. Based on the data output and
data input functions, three data progress functions are shown. ‘Data0’
increases linearly, ‘data1’ starts with 20 % of available input and later
jumps to 100 %, and ‘data2’ increases quadratic over time. The dotted lines
show the maximum possible progress $P_{Dk}(t)$ for the specific data input
$k$, while the solid line shows $P_{D}(t)$, the maximal overall possible data
progress. The background colors correspond to the data input that is currently
the lowest and clearly indicate which data input keeps the process from making
more progress.

###  3.2. Impose Resource Limitations

Data Resource 1 Resource L _$P(t)$ (solid line)__limited by:_
data2resource2data1 _progress limited by:_ resource0resource1data0 _dashed
lines: input data availability over time_ _dashed lines: available, assigned
resources_ _solid lines: actually needed resources_ _The lowest line is the
scarcest data input. If it is 0, the particular data source is the limiting
factor (or it is fully consumed)._ __ Figure 4.  Top: Final progress function
$P(t)$ (solid) along with data-based progress functions $P_{Dk}(t)$ (dashed).
The color of $P(t)$ and the background indicate the input data or resource
that limits the progress in this section. Mid: Resource consumption
$P^{\prime}(t)\cdot\mathcal{R}_{R\ell}^{\prime}(P(t))$ (solid) and assigned
resources $I_{R\ell}(t)$ (dashed) for the three resources of the example.
Bottom: Buffered input data from the process not yet used,
$I_{Dk}(t)-\mathcal{R}_{Dk}^{-1}(P(t))$.

Calculating the maximum possible progress considering resource demands is more
complex than the deduction of data progress, as resources are not storable.

According to our model, the derivative of $\mathcal{R}_{R\ell}(p)$ defines for
a process the amount of a resource $\ell$ needed to achieve the $p$-th
progress, while $P(t)$ defines the achieved progress over time. In turn,
$\mathcal{R}_{R\ell}^{\prime}(P(t))$ results in a _resource per progress_
metric, describing the needed amount of a resource to generate a marginal
amount of progress at time $t$. This expression defines how expensive progress
is at time $t$ (e.g., how much CPU time per progress is needed for every
additional progress unit). The required amount of each resource also depends
on the progress speed, which is defined by the derivative $P^{\prime}(t)$. The
resource amount a process needs at time $t$ is thus:

(4) $P^{\prime}(t)\cdot\mathcal{R}^{\prime}_{R\ell}(P(t))$

As long as this function does not exceed $I_{R\ell}(t)$, there is no
limitation by the resource as the amount of available resources always
surpasses or satisfies the demand. In such a case, only the data limitation
would apply so that $P(t)$ would equal $P_{D}(t)$, which corresponds to the
maximum possible data progress (Sect. 3.1).

When the amount of resources needed is greater than the amount provided, the
progress has to slow down. To determine how much the progress has to be slowed
down, the _speedup_ metric $S_{R\ell}(t)$ is used, which is given by:

(5)
$S_{R\ell}(t)=\frac{I_{R\ell}(t)}{P^{\prime}(t)\cdot\mathcal{R}_{R\ell}^{\prime}(P(t))}$

If the speedup is greater than $1$, the progress could be faster according to
this resource. If the speedup is less than $1$, the progress is faster than
the allocation of this resource allows. In such a case, $P(t)$ has to be
adjusted by the ‘speedup’ factor.

To impose such limitations, we first assume that $P(t)$ equals $P_{D}(t)$.
Afterward, $S_{R\ell}(t)$ is calculated for each of the $L$ resources. These
speedup functions are combined into one function using the minimum. This
combination follows the approach in equation (2) for single data inputs. We
then identify the first position where the combined speedup function drops
below $1$ and call this position $t_{x}$. It is the first time a _resource_
limits progress. Therefore, the progress function is assumed to be correct up
to $t_{x}$. The combined speedup function helps to determine the new progress
function. It is updated as follows:

(6)
$P(t)=\min\Big{(}P_{D}(t),\int{P^{\prime}(t)\cdot\min_{\forall\ell\in\\{1,\ldots,L\\}}{\big{(}S_{R\ell}(t)\big{)}}~{}dt}\Big{)}$

The maximum progress still is limited by $P_{D}(t)$, and the maximum slope of
the progress has to be adjusted by the minimum of all limiting speedup factors
$S_{R\ell}(t)$.

Since all $S_{R\ell}(t)$ depend on $P(t)$ themselves as seen in (5),
calculating $P(t)$ is tantamount for solving a differential equation. Whether
this is possible and how difficult it is to solve depends on the actual
functions, especially $\mathcal{R}_{R\ell}(p)$.

Instead of solving the differential equation in one step, it is possible to
use an iterative approach. The speedup factors are calculated based on the
last $P(t)$ and applied to it as seen in (6). After one iteration,
$P_{\mathit{new}}(t)$ will not be limited at $t_{x}$ anymore. Since
$P_{\mathit{new}}(t)$ might differ from $P(t)$ after $t_{x}$, a new resource
limitation can occur. In $P_{\mathit{new}}(t)$ certain positions after $t_{x}$
might be limited heavier than needed because the limitation itself is based on
the former $P(t)$. $P_{\mathit{new}}(t)$ might not have a certain resource
limitation where the former had one. That is compensated as the multiplication
by the speedup factor will speed up the progress in such locations.

If $P_{\mathit{new}}(t)$ is now assumed to be the progress function and the
above steps are repeated, $t_{x}$ will be greater than last time—guaranteeing
progress in resolving the equation. This iterative algorithm, also shown in
Algorithm 1, can be used to change $P(t)$ until it is stable, i.e., it remains
the same when going through the procedure described above. These arguments
also imply that the combined minimum of the speedup factors is never smaller
than $1$. An example of such a result can be seen in Figure 4.

1

2

3$P_{D}\leftarrow\textnormal{\text{min}}(P_{D1},\ldots,P_{DK})$;

4 $P\leftarrow null$;

5 $P_{\mathit{new}}\leftarrow P_{D}$;

6

7while  _$P_{\mathit{new}}\neq P$_ do

8 $P\leftarrow P_{\mathit{new}}$;

9 for  _$\ell$ in $1,\ldots,L$_ do

10 $S_{R\ell}\leftarrow
I_{R\ell}/(P_{\mathit{new}}^{\prime}\cdot\mathcal{R}_{R\ell}^{\prime}(P_{\mathit{new}}))$;

11

12 end for

13 $S_{lim}\leftarrow\textnormal{\text{min}}(S_{R1},\ldots,S_{RL})$;

14
$P_{\mathit{new}}\leftarrow\textnormal{\text{min}}(P_{D},\textnormal{\text{Integrate}}(P_{\mathit{new}}^{\prime}\cdot
S_{lim}))$;

15

16 end while

Algorithm 1 Impose Resource Limitations

The disadvantage of the iterative approach is that it may iterate over every
$t$, which is not tractable in a practical implementation. Simplification of
the algorithm by limiting the functions’ complexity, as shown in Sect. 4, is a
method to overcome that issue. However, the above algorithm (shown in
Algorithm 1) shows a possible way that theoretically works on any generic
function type.

###  3.3. Additional Simulation Information

The final progress function $P(t)$ of a task predicts how a process will
behave at a particular time. Besides allowing to derive when a process starts
or finishes outputting its results through its output functions $O_{Dm}$
(Sect. 2.4), the progress function implicitly indicates the used fraction of a
given resource and the amount of buffered input data.

####  3.3.1. Resource Usage

As described in Sect. 3.2, the term
$P^{\prime}(t)\cdot\mathcal{R}_{R\ell}^{\prime}(P(t))$ yields how much of a
specific resource $\ell$ is needed at a particular time. For our example, the
resource usage function is shown in Figure 4. Since the actual progress
function $P(t)$ is known after the analysis, it is possible to use this term
to calculate the resource consumption. The following term defines the relative
resource usage for a specific resource $\ell$.

(7)
$\frac{P^{\prime}(t)\cdot\mathcal{R}_{R\ell}^{\prime}(P(t))}{I_{R\ell}(t)}$

This function expresses how much of the allocated amount of a resource is
used. The resource usage will always be between $0$ and $1$. If the function
is above $1$ at any point, it is either a rounding error or the implementation
of the algorithm described in Sect. 3.2 is incorrect. Note that $I_{R\ell}(t)$
can be $0$ if nothing of the resource is allocated for the process at time
$t$.

Whenever the resource usage equals the resource input function (relative
resource usage of $1$ or resource allocation $I_{R\ell}(t)$ is $0$ while
$\mathcal{R}_{R\ell}^{\prime}(P(t))\neq 0$), the resource is a bottleneck.
Providing more of that resource (increasing $I_{R\ell}(t)$) _could_ speed up
the progress if no other resource or data input is limiting the progress at
the same time. Changing the input function for a point in time $t_{y}$ results
in a change in $P(t)$ and, therefore, also may change the resource usage. In
other words, changing any input function starting at $t_{y}$ might completely
change the progress and the resource usage for all resources after $t_{y}$.

Similar to the relative resource usage (7), other metrics can be calculated.
Examples are the ‘ _amount of allocated but unused resource_ ’ or ‘ _amount of
resources needed so that only the data inputs impose a bottleneck_ ’.

####  3.3.2. Buffered Data

The evaluation of the data usage of a process works similarly. In this case,
we need to find the inverse of the data output function. If this is possible,
$\mathcal{R}_{Dk}^{-1}(P(t))$ defines how much data was consumed by the
process until $t$. The amount of unused buffered data can be calculated using
the following term:

(8) $I_{Dk}(t)-\mathcal{R}_{Dk}^{-1}(P(t))$

The term (8) defines the amount of data provided in advance but not yet used
by the process. Figure 4 shows this metric for our example. Such a metric
could help a scheduler to throttle the data input. This capabilty could be
helpful when allocating the resources of a previous process that generates
this input data, a previous process whose output is the data dependency in
question.

###  3.4. Combining Processes

After calculating the progress function, the data output functions can be used
to calculate how much data $o_{m}$ is generated until which point in time for
a data output $m$:

$O_{m}(P(t))$

The resulting function has the same properties as a data input function. With
this property, multiple processes can be chained by using this function as a
data input function of a following process. That way, $O_{m}(P(t))$ of the
process in the chain becomes $I_{Dk}(t)$ of the next process we investigate. A
process can depend on several other processes, and the data output of one
process can be an input function for multiple others. Complex workflows can be
modeled using this approach. Cyclic dependencies are a potential limitation in
the current model. As long as the dependency graph of all processes is
acyclic, each process can be analyzed in sequential order on its own.

This modularity is beneficial when modeling a workflow with its data
transfers. Since moving the data can be a severe bottleneck, taking this into
account can be important for an accurate analysis. A process that models a
network transfer is quite similar to a process that models the execution of a
program. Such a process would typically have one data input representing the
data that should be transmitted. Additionally, it would have one resource that
models the data rate of the connection instead of, e.g., the CPU time. The
input and the output could be connected to other processes. Like a scheduler
allocates CPU usage and guarantees that the sum does not exceed the available
CPU time, the input functions for transfer processes that share a network link
would have to be managed accordingly. The chaining also allows the modeling of
more sophisticated properties, such as the informed prioritization of data
streams that share a network bottleneck. It also enables the modeling of many
throughput-limited systems. Other examples are network topologies or the
throughput of reading from a storage device.

##  4\. BottleMod Implementation

When implementing the above model, a central question is how to represent and
model the mathematical functions. Simple functions, e.g., constants, enable
easier operations but limit the expressiveness to model task behavior.
Supporting any function gives much freedom in modeling tasks and resource
allocations but makes the implementation difficult and might result in slow
analysis. To evaluate the ideas of this paper, the model presented above was
implemented based on _piecewise polynomials_ , which define a function in
several pieces, with each piece described as a polynomial. This approach
enables the modeling of non-linear functions, hard edges, and jumps in
functions. Of course, data functions and resource requirement functions must
still be monotonically increasing across and in all its pieces.

Using an implementation for piecewise-defined polynomial functions such as
PPoly from scipy (developers, 2022) might induce problems. Sect. 3.2 has shown
that the division operation on functions is required. The result of the
division might not be a (piecewise-defined) polynomial function itself and may
therefore not be representable in a framework such as PPoly. Even enabling
negative exponents will not solve the problem since the derivative of these
extended polynomials might result in logarithmic expressions. These could be
used as a divisor again, making fully supporting polynomial functions here
difficult and expensive.

One way to counteract the problem is to extend the representation of functions
for logarithmic terms. We overcame this issue by restricting the resource
requirement functions $\mathcal{R}_{R\ell}(p)$ to be piecewise-linear
functions, which is the most typical way resources are provided in practice
anyway. That also enables another way of solving the mathematical problem from
Sect. 3.2, which ensures that the speedup function $S_{R\ell}(t)$, defined in
(5), is always smaller than $1$ for every resource $\ell$. This equation can
then be simplified as:

$\displaystyle 1$
$\displaystyle\leq\min_{\forall\ell\in\\{1,\ldots,L\\}}\left(\frac{I_{R\ell}(t)}{P^{\prime}(t)\cdot\mathcal{R}_{R\ell}^{\prime}(P(t))}\right)$
(9) $\displaystyle P^{\prime}(t)$
$\displaystyle\leq\min_{\forall\ell\in\\{1,\ldots,L\\}}\left(\frac{I_{R\ell}(t)}{\mathcal{R}_{R\ell}^{\prime}(P(t))}\right)$

Since the resource requirement functions are piecewise-linear and only their
derivative is used, the divisor in (9) is piecewise-constant. Therefore, the
result of the division is still representable by a piecewise polynomial. It
also means that for a specific range in time, where the resource requirement
function has a constant slope, the calculation of $P^{\prime}(t)$ does not
directly depend on the value of $P(t)$. That lets us easily calculate the
maximum progress slope without solving a differential equation or iterating
over every $t$. The algorithm iterates over the pieces of the resource
requirement functions, calculates the maximum progress, updates $P(t)$
accordingly (which might change the later behavior of that function), and
starts the next iteration. This approach is easier to implement than the
generic solution presented in Sect. 3.2. The adapted algorithm is shown in
Algorithm 2.

1

2

3

4$P_{D}\leftarrow\textnormal{\text{min}}(P_{D1},\ldots,P_{DK})$;

5 $P\leftarrow P_{D}$;

6 $cur\leftarrow 0$;

7

8while  _$P(cur) <outputSize$_ do

9 $next\leftarrow\infty$;

10
$maxSpeed\leftarrow\textnormal{\text{min}}(\frac{I_{R1}}{\mathcal{R}_{R1}^{\prime}(P)},\ldots,\frac{I_{RL}}{\mathcal{R}_{RL}^{\prime}(P)})$;

11 if  _$P^{\prime}(cur) >maxSpeed(cur)$ or $P^{\prime}(cur)=maxSpeed(cur)$
and $P^{\prime\prime}(cur)>0$_ then

12 $P_{\mathit{new}}\leftarrow\textnormal{\text{Integrate}}(maxSpeed)$;

13
$maxSpeed\leftarrow\textnormal{\text{min}}(\frac{I_{R1}}{\mathcal{R}_{R1}^{\prime}(P_{\mathit{new}})},\ldots,\frac{I_{RL}}{\mathcal{R}_{RL}^{\prime}(P_{\mathit{new}})})$;

14 $next\leftarrow\textnormal{\text{NextLimitChg}}(P,P_{D},maxSpeed)$;

15 $P[cur\ldots next]\leftarrow P_{\mathit{new}}$;

16

17 else

18 $next\leftarrow\textnormal{\text{NextLimitChg}}(P,P_{D},maxSpeed)$;

19

20 end if

21

22 $cur\leftarrow next$;

23

24 end while

Algorithm 2 Practically Impose Resource Limitations

Note that the pseudocode detects gaps in $P(t)$ by ‘NextLimitChg’ and assumes
that the slope at gaps is infinite. In a practical implementation with PPoly,
such gaps with infinite slope are not easily recognized but must be detected
by piece borders instead. As iterations will often have a piece border as
$cur$, concrete values like $P(cur)$ and $P^{\prime}(cur)$ or also
$maxSpeed(cur)$ are mathematically problematic. As the algorithm iterates with
increasing $t$ the relevant value is the one using the piece that is also used
with increasing $t$ (the piece on the ‘right’ not the ‘left’ one).

The performance of calculating the progress of a process depends not only on
the amount of data and resource dependencies but also on the actual
requirement and input functions of those dependencies. More sections in a
piecewise function result in more iterations and operations. The complexity
further depends on the number of changes of the limiting factor. The more
often the limiting factor (a concrete input data or resource dependency)
changes, the more iterations are needed.

Also, the order of the polynomials is critical since most operations become
more complex when using higher-order polynomials, especially the operation of
finding the roots.

For many typical situations, even piecewise-linear functions are sufficient.
Finding the roots with them is simpler and can be done without precision loss
because only rational numbers are needed. Another advantage is the possibility
to invert (piecewise-defined) linear functions as long as their slope is non-
zero.

We implemented the proposed model in Python. The piecewise-defined polynomial
functions were implemented by using and extending the PPoly class from SciPy
(developers, 2022).

##  5\. Evaluation

To evaluate the proposed model, we modeled a small workflow and executed it
under different circumstances. The measured execution times are then compared
with the predictions of our BottleMod implementation.

###  5.1. Example Workflow

The example workflow is illustrated in Figure 5. The three tasks of the
workflow are single processes of the versatile video tool ffmpeg (Bellard and
the FFmpeg contributors, 2022) with each having a different job:

Data Resource 1 Resource L VM 1VM 2Task 1 _ffmpeg: reverse_ Task 2 _ffmpeg:
rotate_ Task 3 _ffmpeg: join_ _shared link_ _100 MBit/s_ _netfilter_ Storage
_(ramdisk)_ 1.1 GB file _ $\leftarrow$wget+named pipes_ _http_ 1.12 GB file
Figure 5. DAG of the demonstration workflow. The two inputs of task 1 and task
2 share a common bottleneck in form of a shared network link.

  * •

Task 1 reverses the input video. It has to read and decode the total input
video file before it can output the first byte of the reversed and encoded
video. The encoded and reversed output video is much smaller than the input
video due to encoding parameters. This task should represent a typical read-
process-write process.

  * •

Task 2 rotates the input video. That is just a change in the video container’s
metadata, and the task does not need to reencode the rotated video. As only
metadata is changed and the actual video content is just copied, the task
operates in a stream-processing way, writing the output concurrently to
reading new input. Almost no CPU time is needed for that.

  * •

Task 3 takes two input video files and writes their included video streams in
a single output video file. As in task 2, the operation is done as stream
processing without re-encoding and needs almost no CPU time.

The command lines for the three tasks used in this evaluation can be seen in
the appendix Sect. A.

All tasks run on the same system. Although only task 1 needs a considerable
amount of CPU time, the encoding part was limited to two cores by the command
line option ‘\--threads 2’ to make sure that CPU time explicitly does not act
as an additional shared bottleneck on the eight core system. System memory was
also available in abundance to support the concurrent execution of all tasks.

If the input file is available locally and resides in a ramdisk, the execution
of task 1 produces an 80 MB video file in 108 seconds. Reading the input file
and decoding it for later reversal takes 26 seconds. In the remaining 82
seconds, the result is encoded and written. The execution of task 2 takes 5
seconds and task 3 needs 3 seconds. Task 2 and 3 are limited purely by IO
speed and need negligible CPU time.

Both task 1 and task 2 retrieve their input videos from the same remote
webserver. The input for both task 1 and task 2 is the same video file, which
resides in a ramdisk of the webserver. However, it is downloaded independently
for both tasks. The video is a 5 minute long full HD clip with a total size of
about 1.1 GB (exactly 1,137,486,559 bytes). Using the whole 100 Mbit/s-link
during workflow execution, a direct download of the video takes 89 seconds,
meaning the net data rate is roughly 97.51 Mbit/s.

The systems that run the workflow and the webserver are virtual machines
virtualized with VMware on the same host connected to the same network. The
host uses a Ryzen 2700X CPU, which had all cores fixed at 4.0 GHz and its
turbo disabled, and 48 GB of main memory. Two cores with 4 GB main memory were
assigned to the webserver VM, and eight cores with 32 GB were assigned to the
workflow VM.

The bandwidth limitation of both connections accessing the webserver was
achieved using netfilter (Russell and netfilter contributors, 2022) via
nftable’s ‘limit rate’ statement. The sum of both limits was 100 Mbit/s. Since
task 1 first completely downloads the video and processes it afterwards, the
remote link was not directly used as input for ffmpeg. Instead, wget downloads
the file to a named pipe with a buffer size set to 256 MB, which is used as
input for ffmpeg. That way, the network limit of task 2 can be adjusted to the
whole 100 Mbit/s when wget terminates. The overall execution time for the
workflow differs depending on the starting limits of both connections. The
netfilter commands to handle the bandwidth limitation can be found in the
appendix Sect. A.

Task 1 and 2 write their output data each into temporary files which serve as
input for task 3. Task 3 is started after both task 1 and 2 are completed.
Task 1 and 2 as well as the download with wget for task 1 are started at the
same time.

This setup simulates a workflow with two typical ways of data consumption
(represented by task 1 and task 2) and two potential bottlenecks: (i) the
network link and (ii) the CPU resource of task 1. Only the network link
limitation is a shared bottleneck. Therefore, no special scheduling had to be
implemented and the evaluation remains comprehensible by only having one
shared bottleneck.

###  5.2. Model

Figure 6.  Measured I/O activity over time for the isolated execution of
evaluation tasks 1 and 2 with input data available on a local disk. Task 1
does not start generating output until the whole input has been read. Task 2
shows the behavior of a typical streaming task: output and input behave
similarly. If input rises faster, e.g., because the file is still in the
cache, as it happened here in the beginning, the output is generated faster as
well.

The workflow was modeled using the proposed framework. Each ffmpeg task is
represented by a model process. Additionally, two processes model the download
from the webserver preceeding the processes for tasks 1 and 2 respectively,
adding up to five processes in total. The download processes depend on one
data input, which is the file on the webserver, and one resource, i.e., the
data rate.

All requirement functions for data and resources in the evaluation model
belong to the common types shown in Figure 1. The more accurate the functions
used in the model are, the better the results will reflect the reality and the
better the analysis provided by BottleMod will be. As the workflow was
developed just for this evaluation, the tasks were investigated and the
requirement functions were known well. Similary in real world settings tasks
may be annotated by their authors to provide insight about their behavior,
maybe even directly stating their requirement functions. Alternatively
executions of such tasks can be logged and the requirement functions can be
derived from such logs. However, that is part of future work.

The I/O activity of task 1 and task 2 was monitored using BPF (eBPF Developers
and Committee, 2022) and is visualized in Figure 6. The tasks were executed
outside of the workflow with the input data available on a local disk. The
data requirement functions $\mathcal{R}_{Dk}(n_{Dk})$ for all streaming
processes are proportional functions with a slope of _outputSize / inputSize_.
These are the data requirement functions of the download processes and the
processes for tasks 2 and 3, where the latter has two such functions—one per
data dependency. For the process representing task 1, the data requirement
function consists of two constant pieces. The first being 0 until (but
excluding) the last input byte. The process’s _outputSize_ is used as a
constant function for the last byte, modeling that all progress can be made
when all input bytes have been read.

The resource requirement functions $\mathcal{R}_{R\ell}(p)$ are linear
functions with only one piece for every process in the evaluation model. For
the processes representing the tasks, we took the CPU time measure in a local
execution (in CPU seconds) and spread that evenly among the whole progress.
So, the linear function has a slope of _executionTime / outputSize_. For the
download processes, the resource requirement function was simply set to a
linear function with a slope of $1$, since every output byte needs the link
capacity to transfer one byte (e.g., 1 MByte/s for 1 ms or 1 Byte/s for 1
second).

For both download processes, the data input function $I_{D}(t)$ was constant
and equalling the video files size of 1.1 GB as the file is entirely available
on the webserver from the beginning of the workflow execution. The data input
functions for the processes representing the tasks are the result functions
$O(P(t))$ of their predecessor processes. So, for tasks 1 and 2, the data
input functions are the results of their corresponding download processes, and
the two data input functions for task 3 are the result functions of tasks 1
and 2, respectively. As resource input functions $I_{R}(t)$, the processes
representing the tasks got a constant function set to $1$, meaning that in
every real-time second, the process could make progress for one CPU second.
Along with the resource requirement functions, as specified above, the
BottleMod analysis would match the measured execution times if the tasks’
processes would be analyzed in isolation and without limiting data inputs. The
process of task 1’s download gets assigned the specified portion of the
maximum data rate. After analyzing that process, the consumed data rate is set
for the process retrospectively. That does not influence the progress as
setting the resource input to the actually consumed amount does not introduce
any bottleneck. However, it allows assigning the other download process the
rest, meaning the difference between the known maximum data rate and the data
rate of task 1’s download process. Doing that, the cumulatively assigned data
rate for the shared link stays at or below its maximum. As maximum data rate,
the measured net data rate of 97.51 Mbit/s is used in the model.

For the evaluation every process only has one output and, therefore, one
assigned output function. For every process the identity function $O(p)=p$ was
used. The metric for progress is thus the generated amount of output data (in
bytes) for these processes.

As task 3 starts when both task 1 and 2 are finished it has its input data
completely available from its beginning. Therefore it does not depend on the
actual result functions of the processes for task 1 and 2, but only on the
time after which both task 1 and 2 are finished. Task 3’s analysis starts at
that time and the end time denotes the finish of the whole workflow execution.

###  5.3. Results

Figure 7. Total execution time in seconds predicted by BottleMod for 600
different prioritizations (orange, solid line). Measured execution time
(averages over 10 executions with min/max deviation as bars in black).
Different fractions of the link data rate assigned to task 1 (the rest is
assigned to task 2) from a total of 100 Mbit/s. Data Resource 1 Resource L VM
1VM 2 Figure 8. Combined progress of task 1 and 2 process of Figure 5 with
bottlenecks (top) and usage of the link data rate (bottom) for the evaluation
case with 50 % (left) and 95 % (right) of the total data rate assigned to task
1’s download process. If task 1’s download process gets assigned 95 % of the
data rate from the beginning, task 2’s download is slower than the download
and processing of task 1, forming an additional bottleneck (green section in
the top right graph).

We analyzed the execution with different initial data rate fractions for task
1’s download process. For different link fractions, the total execution time
predicted by BottleMod is compared to the actual execution time (Figure 7).
For this model the predicted execution times seem to be well within the range
of the actual execution times. Figure 8 shows two scenarios in more detail.
Here, BottleMod also provides the bottlenecks as well as the data rate
assignments during execution. The overall execution time of the workflow, as
predicted by BottleMod, is 32 % shorter when task 1’s download process gets
assigned 93 % or more of the available data rate instead of just 50 %. The
latter assignment, dividing the shared resource fairly to the applications
that request it, is the default strategy for resource management as there is
no specific information about future application behavior. Even if information
about the applications would not be as accurate as it is in this scenario, as
long as it is somewhat correct, some increase in performance can be expected.

##  6\. Performance

Performance is a crucial property for bottleneck analysis. The more
lightweight but still accurate a framework is, the more often it is affordable
to be executed. Almost instant analysis could be done periodically during
runtime with updated measurements to steer resource allocation dynamically. In
this section, we compare the execution time of BottleMod with the state-of-
the-art workflow simulation framework WRENCH (Casanova et al., 2020).

WRENCH is a framework built on SimGrid (Casanova et al., 2014) that models and
simulates distributed computing applications. It thus can model and analyze
workflow management systems and the coordination of workflows. Tasks and their
behavior are not simulated in greater detail (Casanova et al., 2020). They
have inputs and outputs and need a certain amount of computational resources
in WRENCH. In contrast to BottleMod, the exact behavior, i.e., when a task
needs resources and how much, is not simulated. Therefore, WRENCH’s task model
is more basic and less accurate than BottleMod’s, especially for long-running
tasks that may change behavior over runtime.

A fair performance comparison between BottleMod and WRENCH needs us to
simulate the same workflow. Here our exemplary workflow from Figure 5 was used
again. Unfortunately, not all workflows can be modeled using WRENCH as it
handles tasks as independent execution units and does not directly support
data streaming and thus pipelined task execution, which is the default case
for BottleMod. In addition, WRENCH can only simulate fairly shared links, and
thus data rate limitations on file transfers, as used in our scenario, cannot
easily be modeled. Mimicking the data rate limitation in WRENCH by adding a
slow disk for certain files does not overcome the limitation, as it is hard to
release the limitation when one of the concurrent transfers finished.

For our direct comparison, we dropped the asymmetric link sharing by just
using the 50:50 bandwidth sharing case to overcome WRENCH’s limitations. Thus,
both downloads finish at the same time. Version 2.0 of WRENCH was used, which
depends on SimGrid version 3.31. The simulation was executed 1000 times on the
host machine that also ran the evaluation (see above). BottleMod needed 20.0
ms in that scenario and WRENCH 32.8 ms per analysis. The difference between
BottleMod and WRENCH grows a lot when simulating a larger input file. For
BottleMod, that only affects the location where the mathematical functions
change and does not impact the simulation performance. In contrast, WRENCH
simulates more disk reads and network packet traffic for a larger file, which
increases simulation time. Thus, for an input file size of 100 GB in the same
scenario, BottleMod only takes 22.8 ms per simulation while WRENCH needs 1.137
seconds. There are some differences in the performance of BottleMod as the
used methods of SciPy for finding intersections and roots of functions may
converge slightly different. However, that is merely noise, the runtime does
not scale with the simulated input data size at all. This is fundamentally
different to WRENCH.

##  7\. Related Work

A widely used and well-maintained framework for simulating tasks and workflows
is SimGrid (Casanova et al., 2014). It is also the base used by WRENCH
(Casanova et al., 2020), which focuses on the simulation of workflows and was
compared to BottleMod performancewise in Sect. 6. The approach is
significantly different than the approach described in this paper. SimGrid is
a discrete event simulation, comparable to ns3 (Henderson and ns 3
contributors, 2022) for networks, which also can be integrated into SimGrid.
Instead of using mathematical functions to describe a task or process, events
are used to express behavior. That may be more detailed and yield more
accurate results. But the information about events is more specific and
therefore often harder to acquire, especially for tasks that merely are
observable from the outside as a black box. On the other hand, given a task’s
source code, SimGrid can extract its needed events directly from the code with
some restrictions. Since these approaches often simulate many fine-grained
events, the performance may get worse fast for larger simulated tasks. SimGrid
focuses more on the interaction between tasks and processes. Most examples
provided by SimGrid address applications that do very detailed bidirectional
communication. Our model focuses more on the tasks execution and their main
data flow, rather than on discrete messages exchanged between two tasks. From
a data exchange perspective, this approach is broader and less detailed. It
closely resembles the acyclic dependency graph of tasks, representing a
typical data analysis workflow which is also the context BottleMod was
developed in. Each task of a scientific workflow receives input from
preceeding tasks and produces an output, which is used in subsequent tasks.
Communication and data flow is usually unidirectional for any two concrete
workflow tasks and can be easily represented in this model. Thus, the proposed
model does focus more on the result generation pattern of each task. That
could also be simulated using SimGrid but would be less efficient.

Predicting resource usage is not a new problem. Quite early processes were
clustered by their resource usage from previous executions. These clusters
were used to predict resource usage, helping load balancing purposes
(Devarakonda and Iyer, 1989). Neural networks were also be used for clustering
of processes and prediction (Senger et al., 2004). This approach uses data
from many previous executions of many different processes to derive the
clusters which are used for the prediction. In contrast BottleMod is able to
describe the individual process behavior, not summarizing behavior of many
processes into clusters which in turn can provide more accurate predictions.

Declarative data analysis frameworks such as Spark (Zaharia et al., 2010) and
Flink (Carbone et al., 2015) try to assign resources where they are most
needed by the concept of lazy evaluation. The required data flow to compute
particular outputs is defined, and when the output is needed, the input
dependencies are followed backward, and the corresponding computational task
is triggered to produce it. Thus, the execution environment only sees the
immediately important tasks and assigns resources to them instead of executing
the whole data flow from the beginning. That is closer to the reactive model
of regular operating system resource managers. Only tasks solely defined in
the data flow language might be optimized better. However, that is often not
the case for scientific workflows where standalone tools are used that might
even be closed source. Dedicated schedulers like Klink (Farhat et al., 2021)
optimize output latency of streaming applications with window queries written
in such frameworks by tracking the progress of queries using watermarks and
prioritizing queries close to their finish. That is closer to a more proactive
approach by taking into the account the query’s progress, here defined through
watermarks. However, while yielding significant improvements with such an
approach, it is only applicable for certain stream processing applications and
queries and not for general black box applications often used in scientific
workflows. Our approach might help such frameworks, given information about
the tasks that need to be executed, by providing the ability to simulate the
execution in advance. That way, the framework may assign resources such as CPU
time to the processes that benefit most.

Dynamic resource allocation is a challenge in several practical systems. For
example, in the context of web applications sharing the same hardware with
different expectations regarding response time, the load depends on the user
behavior and interest, which makes load predictions harder and requires direct
monitoring to meet the quality-of-service constraints (Chandra et al., 2003).
In contrast, BottleMod was developed in the context of scientific workflows.
Resource requirements of a workflow may depend on the input data but are often
well predictable. Another example is the dynamic resource allocation for GPGPU
tasks under quality-of-service constraints (Aguilera et al., 2014). GPU
resources not needed for the quality-of-service constraints of one application
can be used for other applications or be shut down to save energy. BottleMod
does not provide a concrete allocation algorithm but a static framework to
analyze and predict resource requirements. It allows other components, such as
a scheduler, to base their decisions on those predictions to find efficient
allocations. As BottleMod is fast, it can be repeatedly executed online with
an updated state from monitoring to serve a dynamic resource allocation
algorithm just in time.

##  8\. Conclusion

We presented BottleMod, a comprehensive technique to model and analyze the
behavior of (chains of) tasks mathematically. It can predict the runtime and
resource usage of a process. Additionally, it can be used to find potential
execution bottlenecks analytically and provide detailed information about
them. This includes identifying the root cause and predicting the performance
gain when the bottleneck is remedied.

The precision of BottleMod relies on the granularity of the provided
mathematical functions. By differentiation of _input_ and _output_ functions,
there is a seperation of concerns between the execution and the process-
specific details of the model. This can enable easier application of the model
for task authors as well as execution environment administrators.

The evaluation (Sect. 5) showed that, given accurate information about the
processes and the resource allocation, BottleMod already works very precise.
In reality this can be a challenge since extracting accurate data for
BottleMod can be difficult. This especially applies for tasks that are
considered as black boxes. Their behavior can still be figured out and modeled
through extensive logging during exemplary executions using, e.g., extended
Berkeley packet filter (eBPF Developers and Committee, 2022) (based on the
original Berkeley packet filter (McCanne and Jacobson, 1993)). The behavior
can also be figured out by running experiments where the task is executed in
an environment controlling the needed resources and input data, making them
available in a controlled manner.

The results of BottleMod contain the progress, bottlenecks and predicted
resource usage of a process. All this information can be used by a resource
manager to schedule resources proactively. The results could also enable more
efficient placement of tasks, running as part of workflows in distributed
environments, on nodes. In order to optimize resource allocation and mitigate
the most disadvantageous bottlenecks, it is up to the resource manager to
apply the insights found by the BottleMod analysis to the actual execution.
The resource manager could change priorities or limit resources with methods
such as Linux control groups (Heo, 2015) or SDN bandwidth reservations.

The practical implementation is able to represent functions by piecewise
polynomials. Calculation of the results only needs to iterate over few
locations of the progress function, namely the points where the current
bottleneck or a relevant functions piece changes. This behavior is
fundamentally different to existing approaches based on simulation of discrete
events. Depending on the number of events using BottleMod can be much faster.
This advantage can even be further increased by using, e.g., piecewise linear
functions instead of polynomials. Due to this efficient analysis, BottleMod
may even be used while the tasks or the workflow is still executing to conduct
certain optimizations just in time, incorporating the most recent information
to deliver even more precise results.

Our BottleMod implementation the scripts used to execute our evaluation will
be made publically available until (no later than) submission of the camera-
ready paper under: https://github.com/bottlemod/bottlemod.

## References

  * (1)
  * Aguilera et al. (2014) Paula Aguilera, Katherine Morrow, and Nam Sung Kim. 2014\.  QoS-aware dynamic resource allocation for spatial-multitasking GPUs.  _19th Asia and South Pacific Design Automation Conference (ASP-DAC)_ (Jan. 2014), 726–731.  https://doi.org/10.1109/ASPDAC.2014.6742976
  * Bellard and the FFmpeg contributors (2022) Fabrice Bellard and the FFmpeg contributors. 2022.  FFmpeg.  Retrieved July 26, 2022 from https://ffmpeg.org/
  * Carbone et al. (2015) Paris Carbone, Stephan Ewen, Seif Haridi, Asterios Katsifodimos, Volker Markl, and Kostas Tzoumas. 2015.  Apache Flink™: Stream and Batch Processing in a Single Engine.  _IEEE Data Engineering Bulletin_ 38, 4 (Jan. 2015), 28–38.
  * Casanova et al. (2020) Henri Casanova, Rafael Ferreira da Silva, Ryan Tanaka, Suraj Pandey, Gautam Jethwani, William Koch, Spencer Albrecht, James Oeth, and Frédéric Suter. 2020.  Developing Accurate and Scalable Simulators of Production Workflow Management Systems with WRENCH.  _Future Generation Computer Systems_ 112 (2020), 162–175.  https://doi.org/10.1016/j.future.2020.05.030
  * Casanova et al. (2014) Henri Casanova, Arnaud Giersch, Arnaud Legrand, Martin Quinson, and Frédéric Suter. 2014\.  Versatile, scalable, and accurate simulation of distributed applications and platforms.  _J. Parallel and Distrib. Comput._ 74, 10 (2014), 2899–2917.  https://doi.org/10.1016/j.jpdc.2014.06.008
  * Chandra et al. (2003) Abhishek Chandra, Weibo Gong, and Prashant Shenoy. 2003\.  Dynamic Resource Allocation for Shared Data Centers Using Online Measurements.  _SIGMETRICS Perform. Eval. Rev._ 31, 1 (June 2003), 300–301.  https://doi.org/10.1145/885651.781067
  * Devarakonda and Iyer (1989) Murthy V. Devarakonda and Ravishankar K. Iyer. 1989.  Predictability of process resource usage: a measurement-based study on UNIX.  _IEEE Transactions on Software Engineering_ 15, 12 (1989), 1579–1586.  https://doi.org/10.1109/32.58769
  * developers (2022) SciPy developers. 2022\.  SciPy.  Retrieved July 26, 2022 from https://scipy.org/
  * eBPF Developers and Committee (2022) eBPF Developers and Steering Committee. 2022.  Extended Berkeley Packet Filter (eBPF).  Retrieved July 26, 2022 from https://ebpf.io/
  * Farhat et al. (2021) Omar Farhat, Khuzaima Daudjee, and Leonardo Querzoni. 2021\.  Klink: Progress-Aware Scheduling for Streaming Data Systems. In _Proceedings of the 2021 International Conference on Management of Data_ (Virtual Event, China) _(SIGMOD ’21)_. Association for Computing Machinery, New York, NY, USA, 485–498.  https://doi.org/10.1145/3448016.3452794
  * Foundation (2022) Cloud Native Computing Foundation. 2022\.  Kubernetes.  Retrieved July 26, 2022 from https://kubernetes.io/
  * Henderson and ns 3 contributors (2022) Thomas R. Henderson and ns 3 contributors. 2022.  ns-3 Network Simulator.  Retrieved July 26, 2022 from https://www.nsnam.org/
  * Heo (2015) Tejun Heo. 2015\.  Control Group v2.  Retrieved July 26, 2022 from https://ebpf.io/
  * Leser et al. (2021) Ulf Leser, Marcus Hilbrich, Claudia Draxl, Peter Eisert, Lars Grunske, Patrick Hostert, Dagmar Kainmüller, Odej Kao, Birte Kehr, Timo Kehrer, Christoph Koch, Volker Markl, Henning Meyerhenke, Tilmann Rabl, Alexander Reinefeld, Knut Reinert, Kerstin Ritter, Björn Scheuermann, Florian Schintke, Nicole Schweikardt, and Matthias Weidlich. 2021.  The Collaborative Research Center FONDA.  _Datenbank-Spektrum_ 21, 3 (01 Nov. 2021), 255–260.  https://doi.org/10.1007/s13222-021-00397-5
  * McCanne and Jacobson (1993) Steven McCanne and Van Jacobson. 1993.  The BSD Packet Filter: A New Architecture for User-Level Packet Capture. In _Proceedings of the USENIX Winter 1993 Conference_ (San Diego, California) _(USENIX’93, Vol. 46)_. USENIX Association, USA, Article 2\.
  * Russell and netfilter contributors (2022) Paul ’Rusty’ Russell and netfilter contributors. 2022.  The netfilter.org project.  Retrieved July 26, 2022 from https://netfilter.org/
  * Senger et al. (2004) Luciano J. Senger, Marcos J. Santana, and Regina H. C. Santana. 2004.  Using Runtime Measurements and Historical Traces for Acquiring Knowledge in Parallel Applications. In _Computational Science - ICCS 2004_ , Marian Bubak, Geert Dick van Albada, Peter M. A. Sloot, and Jack Dongarra (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 661–665.
  * Tommaso et al. (2017) Paolo Di Tommaso, Maria Chatzou, Evan W. Floden, Pablo P. Barja, Emilio Palumbo, and Cedric Notredame. 2017\.  Nextflow enables reproducible computational workflows.  _Nature Biotechnology_ 35, 4 (01 April 2017), 316–319.  https://doi.org/10.1038/nbt.3820
  * Zaharia et al. (2010) Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2010\.  Spark: Cluster Computing with Working Sets. In _Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing_ (Boston, MA) _(HotCloud’10)_. USENIX Association, USA, Article 10.

##  Appendix A Evaluation Workflow

Task 1 commands:

# create pipe
mkfifo pipe1
# set the buffersize of the pipe to 256 MiB (own small C program using fcntl()
to set F_SETPIPE_SZ)
./setpipesize pipe1 $((256 * 1024 * 1024)) &
# set maximum channel bandwidth for task 1 (using port 8080)
nft add rule inet filter input ip protocol tcp ip saddr 192.168.75.142 tcp
sport 8080 $\backslash$
limit rate over $RATE_TASK1 kbytes/second drop
# reverse the video (in background), reading from the pipe blocks until data
arrives
ffmpeg -y -to 05:00 -f mp4 -i pipe1 -an -vf reverse -c:v libx264 -preset
veryfast -threads 2 -movflags $\backslash$
frag_keyframe+empty_moov tmp/t1.mp4 &
# download the video file, writing it to the pipe
wget -O pipe1 http://192.168.75.142:8080/video.mp4
# after download finished, release the full bandwidth to the other task
nft replace rule inet filter input handle 2 ip protocol tcp ip saddr
192.168.75.142 tcp sport 80 $\backslash$
limit rate over $RATE_TOTAL kbytes/second drop

Task 2 commands:

# set maximum channel bandwidth for task 2 (using port 80)
nft add rule inet filter input ip protocol tcp ip saddr 192.168.75.142 tcp
sport 80 $\backslash$
limit rate over $RATE_TASK2 kbytes/second drop
# rotate the video
ffmpeg -y -i http://192.168.75.142:80/video.mp4 -an -c:v copy -metadata:s:v:0
rotate=180 -movflags $\backslash$
frag_keyframe+empty_moov tmp/t2.mp4
# when finished, release the full bandwidth to the other task
nft replace rule inet filter input handle 3 ip protocol tcp ip saddr
192.168.75.142 tcp sport 8080 $\backslash$
limit rate over $RATE_TOTAL kbytes/second drop

Task 3 command:

# combine video outputs of task 1 and task 2
ffmpeg -y -to 05:00 -i tmp/t1.mp4 -to 05:00 -i tmp/t2.mp4 -map 0 -map 1 -c
copy result.mp4