b. Formats

Input tree format

Input trees (DAG) are required to be given as directed out-tree that can be imported with the NetworkX package.

For the supported serialization formats, refer to the regarding documentation: Reading and writing graphs.

For our test files under the tests, we use the human-readable Graph Modelling Language (GML) format that has the advantage of modifying attributes on-the-fly.

In input trees, single-threaded serverless functions and their relationships are characterized with the following attributes.

Functions (Nodes):

• time - Avg. funtion execution time [ms] (used constant: RUNTIME)
• mem - Max. memory demands [MB] (used constant: MEMORY)

Invocations (Edges):

• rate - Avg. call rate [1/s] (used constant: RATE)
• data - Max. intermediary data overhead [ms] from data size * throughput (used constant: DATA)

One node representing the serverles platform (and its API gateway) is reserved with node ID P and must be pesent in the tree structure.

For chain algorithms, the restricted subchain is determined with the two bounding nodes start and end.

For tree algorithms, the critical path is defined as the subpath of the tree from the root node to one of its leaf node cp_end.

Minimal example tree

Example tree with 2 function nodes and an edges:

┌───────┐          ┌───────┐          ┌───────┐
│       │          │       │          │       │
│   P   ├─────────►│   1   ├─────────►│   2   │
│       │          │       │          │       │
└───────┘          └───────┘          └───────┘

graph [
  directed 1
  name "example"
  node [
    id 0
    label "P"
  ]
  node [
    id 1
    label "1"
    time 79
    mem 5
  ]
  node [
    id 2
    label "2"
    time 83
    mem 3
  ]
  edge [
    source 0
    target 1
    rate 1
    data 12
  ]
  edge [
    source 1
    target 2
    rate 3
    data 4
  ]
]

Algorithm parameters

For the same algorithm parameters the same syntax parameter are used for all algorithms impelmented in SLAMBUC.

These parameters and their descritpions are collected in the following:

Chain algorithms

Parameter	Description
runtime	running times in ms
memory	memory requirements in MB
rate	avg. rate of function invocations
data	input data fetching delay in ms
M	upper memory bound of the partition blocks (in MB)
N	upper CPU core bound of the partition blocks
L	latency limit defined on the critical path in the form of subchain[start -> end] (in ms)
start	head node of the latency-limited subchain
end	tail node of the latency-limited subchain
delay	invocation delay between blocks
unit	rounding unit for the cost calculation (default: 100 ms)

Tree algorithms

Parameter	Description
tree	service graph annotated with node runtime(ms), memory(MB) and edge rates and data overheads(ms)
root	root node of the graph
M	upper memory bound of the partition blocks (in MB)
N	upper CPU core bound of the partition blocks
L	latency limit defined on the critical path (in ms)
cp_end	tail node of the critical path in the form of subchain[root -> cp_end]
delay	invocation delay between blocks
flavors	list of flavors resources given by the tuple of available (memory, relative CPU cores)
timeout	time limit in sec
bidirectional	use bidirectional subcase elimination (may introduce quadratic increase in the worst case)
Epsilon	weight factor for state space trimming (0 <= Eps < 1, Eps = 0 falls back to exact calc.)
Lambda	latency factor for state space trimming (0 <= Lambda, Lambda = 0 falls back to exact calc.)

Additional parameters

Attribute	Description
unit	rounding unit for the cost calculation (default: 100 ms)
full	return full blocks or just their ending nodes
ichains	generator of chain partitions
only_cuts	return the number of cuts instead of the calculated latency
only_barr	return the subtree roots (barrier nodes) instead of full node partitioning
partition	function that partitions chain into blocks wrt. M and L
barriers	function that extracts barrier nodes from partition's returned data structure
exec_calc	function that calculates the effective runtimes from reference runtime and available CPU cores
solver	specific solver class (default: COIN-OR CBC)

Output format

Returned partitioning is typically accompanied with the optimal (minimal) cost of the partitioning and the calculated latency of the critical path, as well.

In pythonic term, partitioning is a list of partition blocks represented by the list of encompassed node IDs (int), i.e., list[list[int]].

Example partitioning of a 10-size tree:

[[1, 3, 4, 5], [2], [6, 8, 9, 10], [7]]

For the general algorithms considering multiple flavors, the partition blocks are grouped with their assigned flavors, i.e., list[tuple[list[int], Flavor]].

Example partitioning of a 10-size tree with a single flavor with M=6, N=1, gamma=1.0:

[([1, 2, 3], F[6,1,1.0]), ([4, 5, 6, 8, 9, 10], F[6,1,1.0]), ([7], F[6,1,1.0])]