lrdcases $\displaystyle{##}$ $\displaystyle{##}$ { } lrdcases*
$\displaystyle{##}$ ## { }

# Agent-based Constraint Solving for Resource Allocation in Manycore Systems

Volker Wenzel†, Lars Bauer†, Wolfgang Schröder-Preikschat‡, Jörg Henkel†
†Chair for Embedded Systems (CES), Karlsruhe Institute of Technology (KIT),
Germany
‡ Friedrich-Alexander-Universität (FAU), Erlangen-Nürnberg, Germany
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

For efficiency reasons, manycore systems are increasingly heterogeneous, which
makes the mapping of complex workloads a key problem with a high optimization
potential. Constraints express the application requirements like which core
type to choose, how many cores to choose, exclusively or non-exclusively,
using a certain core, etc. In this work, we propose a decentralized solution
for solving application resource constraints by means of an agent-based
approach in order to obtain scalability. We translate the constraints into a
Distributed Constraint Optimization Problem (DCOP) and propose a local search
algorithm RESMGM to solve them. For the first time, we demonstrate the
viability and efficiency of the DCOP approach for heterogeneous manycore
systems. Our RESMGM algorithm supports a far wider range of constraints than
state-of-the-art, leading to superior results, but still has comparable
overheads w.r.t. computation and communication.

##  1 Introduction and Related Work

The amount of cores per CPU is growing and expected to be around hundreds or
even thousands in the next few years [1, 2]. This creates the challenge of how
to efficiently use the computational resources of such large manycore systems,
i.e., which computational resources should be assigned to which application.
The search space of the underlying problem grows excessively with the amount
of available resources. Highly dynamic workloads make it difficult to
pre/determine the resource allocation and call for _runtime_ resource
management approaches.

Among others, the authors of [3, 4, 5] argue that centralized control of a
huge amount of on/chip resources is to become a bottleneck and that
decentralized or _agent/based_ resource management schemes have to be devised.
By _agents_ , we understand per/application software entities that negotiate
the resource requirements thereof. Agent/based approaches to system management
like [3, 6] are favorable for a multitude of reasons with scalability to
bigger system sizes being the main advantage. Large manycore systems could
theoretically be programmed by giving the application programmer full
flexibility in choosing computational resources (e.g. cores) for the
individual threads, but that would burden the application programmer with a
great deal of additional intricacy. These applications would be tailored to a
specific manycore system, and it is unclear how several applications would
share the resources on the same manycore system with acceptable resource
allocation tradeoffs. Alternatively, application programmers could remain
agnostic of the concrete computational resource on which a thread is executed,
i.e., resource management would lie entirely in the responsibility of the
resource management system. This approach is also suboptimal in complex
scenarios, e.g., with heterogeneous computing resources, since the resource
management system has no means to differentiate more and less suitable
resource allocations.

We strongly believe that applications will have to be _resource/aware_ [7] and
provide _constraints_ , i.e., preferences for a desired resource assignment,
to the resource management system. By introducing support for constraints on
resource assignments, we give the application programmer freedom to influence
the resource assignment of an application. For instance, constraints encompass
a minimum and maximum amount of required compute cores, on/chip memory or
NoC/bandwidth necessary to execute the application. A concrete example for
such a constraint is given in Figure 1 (right), where Application 5 is mapped
to the small manycore architecture (left). The application provides two
implementation alternatives for its functionality and describes them as a
hierarchical composition using the Or and And constraints. One implementation
can be executed on an exclusively/reserved tile (Tile-Sharing forbidden) using
a single (PEQuantity) specialized (PEType) core. Alternatively, a larger
amount of regular cores scattered over several tiles of the manycore system
may be used. Existing examples of applications that benefit from using
constraints to express changing resource demands during different phases of
their execution comprise applications that use multigrid methods [8].

Figure 1:  Example architecture of a tiled manycore system (left) and the
constraint for Application 5 (right), showing that it needs either one
specialized core exclusively (i.e., no other application may use any resource
in the same tile), or several regular cores. Every application has a
constraint of this form and the resource management needs to resolve resource
requests at runtime.

Surveys of state/of/the/art manycore resource allocation systems are given in
[9, 10]. Our contribution in the presented taxonomy in [9] lies in the branch
of _distributed_ resource management systems that operate at _runtime_ and
support _heterogeneous resources_. A similar NoC/based system architecture is
targeted in [11], but it only employs a centralized stochastic hill climbing
approach for resource management in order to find a contiguous mapping of
resources. The approaches in [6, 12] are distributed, but they only support a
small subset of the constraints conceivable in our approach. The _Distributed
Resource Manager_ (DistRM) [6] foresees one agent per application and features
local decision/making. Moreover, DistRM also supports _malleable_
applications, i.e., applications that can dynamically adapt their resource
usage at runtime. The more recent decentralized resource management scheme
introduced in [13] elaborates on [6, 12]. This work has the most similar
objective to our work, and we therefore compare our proposed technique to it
in Section 4. It introduces a workload/aware distributed runtime framework for
malleable applications, i.e., applications that support changing their
resources at runtime. In contrast to RESMGM, [13] does not support the same
variety of constraints and there is no straight forward potential to extend
it.

Agent/based approaches for resource management can be constructed in multiple
ways. A great body of literature borrows from market inspired principles.
Examples are [3] and [14], which is a distributed resource management based on
market principles that proactively balances reliability degradation. Typically
these approaches have relatively low overheads, but an uncontrollable solution
quality. Another branch of agent/based resource managers employs methods from
mathematical optimization. An example is [15], which is a runtime resource
management approach that is based on nonlinear programming. It allows a
distributed application embedding for dealing with soft system/wide
constraints. Typically these approaches come with high overheads, but allow
trading off solution quality with computational and message passing overheads.
An orthogonal aspect of resource allocation schemes is, whether they work at
design time, runtime, or both (hybrid). An example of a hybrid scheme is
presented in [16], which is a performance-aware resource management scheme for
many-core architectures. Note that [16] performs application mapping in a
centralized way.

The novel contributions of this paper are as follows:

  * •

We are the first to tackle the problem of _manycore resource management_ with
an _agent/based constraint solving_ approach to the best of our knowledge.

  * •

For the first time, we formally translate the problem of agent/based solving
of resource constraints for resource/aware applications in manycore systems
into a versatile mathematical problem formulation: the _Distributed Constraint
Optimization Problem_ (DCOP). This yields a new approach of a fully
decentralized constraint solving for resource/aware applications.

  * •

We propose RESMGM, an optimized DCOP algorithm for decentralized resource
management. It uses the maximum gain message (MGM) communication [17] along
with a multitude of novel heuristics that improve execution time and solution
quality significantly. Among those heuristics are the _Smart initialization
heuristic_ to incorporate the respective system state, the _Early termination
heuristic_ , which adds improved termination detection, and the _Incorporating
system information heuristic_ , which exploits the architecture of the
manycore system in order to make the evaluation of constraints more efficient.

##  2 Problem Formulation and System Overview

###  2.1 System Overview

It is expected that future manycore CPUs will consist of a big amount of so
called _compute tiles_ with a tiled _Network/on/Chip_ (NoC)/based
communication infrastructure. By _compute tile_ we understand the basic unit
of future manycore systems, consisting of one or several compute cores,
caches, and a network adapter to interface the NoC. A typical software stack
for manycore systems is illustrated on the left side of Figure 2. The
_agent/based resource management system_ , the focus of this publication, is
situated on top of the operating system and below the application and its
runtime system (providing standard library calls). By an _agent_ we understand
a software entity that exclusively negotiates the resource demands of its
application, i.e., there is one agent per application. Agents can communicate
with other agents via message passing. An example of the agent’s interactions
is shown on the right side of Figure 2. An application that demands new or
different resources, passes a _constraint_ along with its request for
resources to the agent system via the agent-system API. The agents then start
a distributed constraint solving optimization that will be described in
Section 3.1. Resource requests that arrive before the constraint solving
finishes will be buffered and processed in the subsequent optimization. This
ensures termination of the started resource management process, instead of
aiming at ‘a moving target’. Afterwards, all buffered requests (potentially
from different applications) are processed together.

Figure 2:  Overview of targeted technology stack (left) and agent interactions
(right). The agent/based resource management is implemented as a part of a
manycore operating system.

###  2.2 Problem Formulation

In the following, a formal problem formulation is provided. We assume the
manycore system to consist of _allocatable resources_ $r_{e}$

$r_{e}\in R=\\{r_{1},\ldots,r_{r}\\}$ (1)

where $R$ is the set of all resources, and $r$ is the total number of
resources. The resources could be computational resources (i.e. cores), chunks
of scratchpad memory, NoC bandwidth or other countable resources present in
the manycore system. For the sake of simplicity, we will limit our discussion
to compute cores. Every resource is part of a _compute tile_ $t_{m}$.

$t_{m}\in T=\\{t_{1},\ldots,t_{t}\\}$ (2) $tile:R\mapsto T$ (3)

The function $tile$ maps resources to their corresponding compute tile, e.g.,
$tile(r_{e})=t_{m}$. $H$ is the set of heterogeneous resource types. In our
case there are three different computational resource types, namely
$H=\big{\\{}\mathrm{REGULAR},\ \mathrm{RECONFIG},\ \mathrm{STREAM}\big{\\}}$,
where $\mathrm{REGULAR}$ may represent a standard general purpose processor,
$\mathrm{RECONFIG}$ may represent a runtime reconfigurable processor, and
$\mathrm{STREAM}$ may represent a dedicated stream processing unit. Note that
our approach is not limited to specific resource types or a specific number of
different resource types. The function $type:R\mapsto H$ maps resources to
their corresponding heterogeneous resource type, e.g.,
$type(r_{e})=\mathrm{RECONFIG}$.

The set of applications is given by
$A=\\{a_{1},\ldots,a_{p}\\}\cup\\{a_{\textrm{new}}\\}$ We refer to
$\\{a_{1},\ldots,a_{p}\\}$ as _a priori_ applications with $p$ being the
number of a priori applications. $a_{\textrm{new}}$ ($\equiv a_{p+1}$)
represents a new application for which resources shall be found. Note that our
approach is not limited to resource allocations for a single new application.
It also supports multiple new applications and applications that change their
resource requirements at runtime, but for the sake of simplicity, we limit our
discussion to having just one new application. The function $assigned$
provides the current resource assignment of an application

$assigned:A\mapsto\mathcal{P}(R)$ (4)

where $\mathcal{P}(R)$ denotes the power set of the available resources, i.e.,
the resource assignment of an application is a subset of all resources.
Initially $assigned(a_{\textrm{new}})=\emptyset$.

All applications $a_{j}\in A$ provide a _soft, valued_ constraint, i.e., a
constraint that can be partially fulfilled.

$C_{j}:\mathcal{P}(R)\mapsto\mathbb{R}^{+}_{0}\cup\\{\infty\\}$ (5)

We assume one constraint $C_{j}$ per application $a_{j}$ that takes a set of
resources as input and evaluates them w.r.t. the constraint. Note that a
constraint may internally consist of sub/constraints. For instance the example
shown in Figure 1 (right) shows actually _the_ (one) constraint for
Application 5, describing its resource requirements. The constraints and their
internal composition are formalized further in Sections 3, 18, 19 and 20. The
problem to be solved is to find a resource assignment for $a_{\textrm{new}}$
that minimizes a _cost function_ , given by

$cost:\mathcal{P}(R)^{\,p+1}=\mathcal{P}(R)\times\ldots\times\mathcal{P}(R)\mapsto\mathbb{R}^{+}_{0}\cup\\{\infty\\}\vspace{+0.2em}$
(6)

It takes the $p+1$ resource assignments of the $p$ a priori applications and
the new application as input, evaluates their constraints and calculates the
corresponding cost for the resource assignments, where $cost\\!=\\!\infty$
means that at least one hard constraint is violated. The cost function returns
smaller values for resource allocations that are more useful (i.e., have a
higher _utility_) to the application. The goal is to minimize $cost$ by
finding a well/suited resource assignment. This is to be done by the agents,
whose local knowledge is only sufficient to evaluate some of the terms in
$cost$. The cost function is calculated as

$cost\\!=\\!\sum_{j=1}^{p+1}\Big{(}C_{j}\big{(}assigned^{\prime}(a_{j})\big{)}\Big{)}+\sum_{j=1}^{p+1}\Big{(}C_{\textrm{migr},j}\Big{)}+C_{\mathrm{Sys}}$
(7)

where the function $assigned^{\prime}$ provides the new (to be examined)
resource assignment of an application. Depending on the configuration of the
resource management system, it is permissible that the a priori applications
change their resource assignment from $assigned(a_{j})\in\mathcal{P}(R)$ to
$assigned^{\prime}(a_{j})\in\mathcal{P}(R)$ in order to allow the new
application to obtain a better resource assignment and/or to improve the
overall system performance. This incurs a migration cost represented by a set
of migration constraints

$C_{\textrm{migr},j}:\mathcal{P}(R)^{2}\mapsto\mathbb{R}^{+}_{0}\cup\infty$
(8)

where $C_{\textrm{migr},j}=\infty$ means that application $a_{j}$ does not
support migration. Lastly, it has to be made sure that resources are not
assigned to different applications at the same time. We formally capture this
with the system constraint $C_{\mathrm{Sys}}$, which we introduce more in
detail in Eq. 21.

##  3 Distributed constraint solving with the RESMGM algorithm

###  3.1 Formulating resource management as distributed constraint
optimization problem

We first outline how the formulated problem (see Section 2) can be expressed
as a _Distributed Constraint Optimization Problem_ (DCOP), and explain how it
can be applied to solve resource constraints for manycore architectures. Our
definitions regarding DCOP are based on [18]. Every _agent_ represents one
software _application_ in the system. The set of all agents in the system is
given by

$\tilde{A}=\\{\tilde{a}_{1},\ldots,\tilde{a}_{p}\\}\cup\\{\tilde{a}_{\textrm{new}}\\}$
(9)

in analogy to the set of applications $A$. Every agent in the system has
exactly one _resource assignment_ , except for $\tilde{a}_{\textrm{new}}$, for
which it is yet to be determined. The resource assignments of all agents make
up the the _resource allocation_.

Every agent $\tilde{a}_{j}$ maintains a _variable_ $v_{j}$ from the _domain_
$D$ in which it records the agent’s current local view of the system’s global
resource allocation. That is, $v_{j}$ contains the agent’s local view about
the resource owner for all $r$ resources, i.e., itself, another agent, no
agent (a free resource), or an unknown status.

$\begin{split}v_{j}=(\alpha_{1},\ldots,\alpha_{r})\in
D=d^{r}=d\times\ldots\times d\\\ \alpha_{i}\in
d=\tilde{A}\cup\\{\textrm{FREE}\\}\cup\\{\textrm{UNKNOWN}\\}\end{split}$ (10)

Note that this local view is typically incomplete, i.e., it does not contain
all information of the global view and might even contain _wrong_ information
temporarily. Each agent $\tilde{a}_{j}$ has its own local view $v_{j}$ and
each agent must at least have knowledge of all its own resources in $v_{j}$.
The set of all variables is given by
$V=\\{{v_{1},\ldots,v_{p}}\\}\cup\\{v_{\textrm{new}}\\}\\\ $ The
incomplete/wrong information will be incrementally updated by communicating
with other agents, as explained in the following.

Every agent strives to fulfill the constraint of its application as good as
possible, taking into account the other agents. In analogy to Eq. 5,
constraints are functions that rate the quality of resource assignments. The
original definition of $C_{j}$ in Eq. 5 expects the resources that are
actually assigned to an application $a_{j}$ as input. In the following, we use
an extended version of $C_{j}$ that also accepts the local resource allocation
view of an agent instead. For instance, the constraint $C_{j}$ rates the local
resource allocation view $v_{j}$ of agent $\tilde{a}_{j}$ to inform how good
the constraint is fulfilled by that assignment. The set of all constraints is
given by:

$C=\\{C_{1},\ldots,C_{p}\\}\cup\\{C_{\textrm{new}}\\}$ (11)

The agents examine different resource assignments (i.e. intermediate
assignments to variable $v_{j}$), communicate that to other agents to identify
and solve conflicting assignments, and try to optimize the global cost
function. The cost function (lower is better) for intermediate variable
assignments $v_{j}$ is given by

$\begin{split}\mathchoice{\hbox{$\displaystyle\widetilde{cost}$}}{\hbox{$\textstyle\widetilde{cost}$}}{\hbox{$\scriptstyle\widetilde{cost}$}}{\hbox{$\scriptscriptstyle\widetilde{cost}$}}:D^{\,p+1}=D\times\ldots\times
D\mapsto\mathbb{R}^{+}_{0}\cup\\{\infty\\}\\\
\mathchoice{\hbox{$\displaystyle\widetilde{cost}$}}{\hbox{$\textstyle\widetilde{cost}$}}{\hbox{$\scriptstyle\widetilde{cost}$}}{\hbox{$\scriptscriptstyle\widetilde{cost}$}}=\sum_{j=1}^{p+1}\Big{(}C_{j}(v_{j})\Big{)}+\sum_{j=1}^{p+1}\Big{(}C_{\textrm{migr},j}\Big{)}+C_{\mathrm{Sys}}\end{split}$
(12)

in analogy to the definition in Section 2. It is noteworthy to mention that
global knowledge is not necessary in order to minimize
$\textstyle\widetilde{cost}$. The agents minimize $\textstyle\widetilde{cost}$
by sending/receiving messages to/from other agents, evaluating their
constraints locally, and optimizing the assignment of their own variables.

Figure 3:  UML state machine of RESMGM. RESMGM alternates between
wait_ok?-mode and wait_improve-mode until termination. Transition between
states occurs, when all _ok?_ \- or _improve_ -messages have been received.

Many different kinds of constraints are conceivable. In the following,
$\tilde{a}$ is the agent to which the constraint applies,
$v=(\alpha_{1},\ldots,\alpha_{r})\in D$ (cf. Eq. 10) is a possible resource
assignment for agent $\tilde{a}$, and $v[r_{e}]=\alpha_{e},r_{e}\in R$ is the
local view of agent $\tilde{a}$ about the owner/status of resource $r_{e}$. We
envision the following constraints for our system: $C_{\mathrm{PEQuantity}}$
constrains the number of cores in a resource assignment:

$\begin{split}C_{\mathrm{PEQuantity}}(v,\tilde{a},\textrm{minPEs},\textrm{maxPEs})=\\\
\begin{cases}0&\textrm{minPEs}\leq\textrm{countPE}(v,\tilde{a})\leq\textrm{maxPEs}\\\
\infty&\textrm{else}\end{cases}\end{split}$ (13)
$\textrm{countPE}(v,\tilde{a})=\Big{|}\big{\\{}v[r_{e}],r_{e}\in
R:v[r_{e}]=\tilde{a}\big{\\}}\Big{|}$ (14)

where minPEs, maxPEs $\in\mathbb{N}_{0}$ are the minimum and maximum amount of
resources in the resource assignment ($\textrm{minPEs}\leq\textrm{maxPEs}$),
and countPE determines the amount of PEs assigned to $\tilde{a}$ in the
examined resource assignment $v$. $C_{\mathrm{PEQuantity}}$ evaluates to the
constraint cost, i.e., whether or not the constraint is fulfilled. Similarly,
$C_{\mathrm{PEType}}$ constrains the resource types in a resource assignment:

$C_{\mathrm{PEType}}(v,\tilde{a},\textrm{PEtype})\\!=\\!\begin{cases}0&\begin{aligned}
&\forall\,r_{e}\in R,v[r_{e}]=\tilde{a}:\\\
&type(r_{e})=\textrm{PEtype}\end{aligned}\\\ \infty&\textrm{else}\end{cases}$
(15)

where $type(r_{e})\in H$ is the resource type of $r_{e}$ (see Sections 2.2 and
2.2) and $\textrm{PEtype}\in H$ is the type of the requested resource. The
$C_{\mathrm{TileSharing}}$ constraint allows to request an exclusive access to
tiles, i.e., no resource in any of the tiles of the requesting agent may be
given to another agent. Additionally, the resource management system should
minimize the number of tiles in the resource assignment.

$C_{\mathrm{TileSharing}}(v,\tilde{a})=\begin{cases}0&\begin{aligned}
&\forall\,r_{e}\in R,v[r_{e}]=\tilde{a}\ \ \nexists\,r_{f}\in R:\\\
&tile(r_{e})=tile(r_{f})\ \wedge\\\
&v[r_{e}]\notin\big{\\{}\tilde{a},\mathrm{FREE}\big{\\}}\\\ \end{aligned}\\\
\infty&\textrm{else}\end{cases}$ (16)

$C_{\mathrm{Downey}}$ provides a hint on the scalability of an application.

$\begin{split}C_{\mathrm{Downey}}(v,\tilde{a},\textrm{Dow}_{\sigma},\textrm{Dow}_{A})=\\\
\begin{cases}1/f_{\textrm{Downey}}&f_{\textrm{Downey}}\big{(}\textrm{Dow}_{\sigma},\textrm{Dow}_{A},\textrm{countPE}(v,\tilde{a})\big{)}\neq
0\\\ \infty&else\end{cases}\end{split}$ (17)

$f_{\textrm{Downey}}\in\mathbb{R}^{+}_{0}$ is a formula to model the speedup
of parallel applications [19]. The model depends on the average parallelism
$\textrm{Dow}_{A}\in\mathbb{N}$, and the parameter
$\textrm{Dow}_{\sigma}\in\mathbb{R}^{+}$, which are both provided by the
application programmer. In order to build more complex constraints, we
introduce the conjunction and disjunction of constraints and to allow for
heterogeneous constraints, we define union.

$C_{\mathrm{And}}(v,C_{1},C_{2})=\textrm{max}\big{\\{}C_{1}(v),C_{2}(v)\big{\\}}$
(18)
$C_{\mathrm{Or}}(v,C_{1},C_{2})=\textrm{min}\big{\\{}C_{1}(v),C_{2}(v)\big{\\}}$
(19) $C_{\mathrm{Union}}(v,C_{1},C_{2})=C_{1}(v)+C_{2}(v)$ (20)

Here, $C_{1}$ and $C_{2}$ are independent constraints (e.g.
$C_{\mathrm{PEQuantity}}$, nested $C_{\mathrm{And}}$ etc., see Figure 1). For
the And/Or constraint, $C_{1}$ and $C_{2}$ are combined by max/min to ensure
that the worst/best resource assignment is considered. The union constraint
allows to request heterogeneous resources. For instance, requesting regular
and reconfigurable PEs is possible by creating two separate constraints (one
for regular and one for reconfigurable with the corresponding PE quantities
etc.) and then combining them using the union constraint. In order to
guarantee a consistent system state (e.g., there must not be two agents that
want to use the same resource), we introduce the notion of a system
constraint.

$C_{\mathrm{Sys}}=\begin{cases}0&\begin{aligned}
&\forall\,\tilde{a}_{j},\tilde{a}_{k}\in\tilde{A},\tilde{a}_{j}\neq\tilde{a}_{k}\
\ \nexists\,r_{e}\in R:\\\ &v_{j}[r_{e}]=\tilde{a}_{j}\wedge
v_{k}[r_{e}]=\tilde{a}_{k}\end{aligned}\\\ \infty&\textrm{else}\end{cases}$
(21)

The list of constraints presented here is by no means exhaustive and can be
extended to capture other types of constraints according to the specific
requirements of the applications. However, for the sake of simplicity, we
limit our considerations to the constraints presented above. The entire DCOP
is given as a tuple of
$\textrm{DCOP}=\left\langle\,V,D,C,\tilde{A},\mathchoice{\hbox{$\displaystyle\widetilde{cost}$}}{\hbox{$\textstyle\widetilde{cost}$}}{\hbox{$\scriptstyle\widetilde{cost}$}}{\hbox{$\scriptscriptstyle\widetilde{cost}$}},tile,R\,\right\rangle$.

###  3.2 The RESMGM algorithm

A variety of algorithms exist to solve the DCOP formulation established in
Section 3.1. Preliminary tests show the _Maximum Gain Message_ (MGM) [17]
algorithm to be a well/suited candidate for the purpose of manycore resource
management. MGM is an agent/based local search algorithm. It is _incomplete_ ,
i.e., it is not guaranteed to find an optimal solution, whereas complete DCOP
algorithms, like BnB/ADOPT [18], showed poor scalability in our preliminary
tests due to excessive overheads in computational effort and/or message
passing. Additionally, MGM comes with an _anytime property_ , i.e., it always
improves on a partial solution that can be extracted if the algorithm needs to
be interrupted before termination.

Starting from MGM as a baseline, we analyze its performance and behavior when
applied to the specific scenario of manycore resource management (cf. Section
3.1) and we conceive multiple novel heuristics that improve execution time and
solution quality significantly, altogether building the foundation of our
proposed _Resource Management MGM_ (RESMGM) algorithm. An overview of the
functioning of RESMGM is illustrated in Figure 3. A more in-depth
understanding follows from the pseudo codes in Algorithms 1 and 2111The
pseudo-code has been split in two parts to improve readability. and borrows
its terminology from [20].

The same algorithm is executed on every agent and communication takes place
via asynchronous messages between _neighboring_ agents, i.e., agents that have
a constraint between them (for instance the system constraint in Eq. 21). In
RESMGM, message delivery is assumed to be reliable, but delays are tolerated.

Neighboring agents exchange two types of messages between each other: Firstly
the _ok?_ /message contains an agent’s designation and the current assignment
of its variables (see Eq. 10). The receiving agent adds its neighbors’ current
variable assignment to its $\mathit{agent\\_view}$, which is a possibly
incomplete and outdated record of its neighbors’ resource assignment. After
having received the _ok?_ /messages from all neighbors, an agent uses its
$\mathit{agent\\_view}$ to calculate its current constraint cost and
determines for which assignment of its variables it can minimize its
constraint cost and by how much (=improvement). Subsequently, the agent
communicates its improvement via _improve_ /messages to all of its neighbors.
To avoid oscillations, the agent is only allowed to change its variable
assignment, if its improvement is maximum among its neighbors. Non/neighboring
agents can change their variable assignments concurrently.

RESMGM alternates between two modes, i.e., the wait_ok?/mode and the
wait_improve?/mode as illustrated in Figure 3. In the wait_ok?/mode, the agent
can either be waiting for all _ok?_ /messages to arrive from its neighbors or
it can be waiting for all _improve_ /messages to arrive in the
wait_improve?/mode. At the end of the processing in the wait_ok?/mode, the
agent sends out the _improve_ /messages and switches to the
wait_improve?/mode. Similarly, at the end of the processing in the
wait_improve?/mode, the agent sends out _ok?_ /messages and switches to the
wait_ok?/mode. RESMGM alternates between these two modes until termination.
The other agents execute the same steps. Synchronization happens when waiting
for all _ok?_ -/_improve_ -messages to arrive from the neighbors.

The algorithm improves the solution quality monotonously, i.e., if an agent’s
variable assignment does not change for any agent in a round, it will not
change for any agent in the remaining rounds. The _ok?_ /message has a Boolean
field that encodes, whether the sending agent has changed its variable
assignments in the last round or whether it has observed a change from any
other agent’s _ok?_ /message. Due to the high connectedness of the constraint
tree, it is safe to terminate RESMGM when one agent does not see any change
from other agents in a round.

Algorithm 1 RESMGM – wait_ok?-mode

1:initialize()

2:send_ok() //see Algorithm 2. Note that it is easier to comprehend the
algorithms by skipping the send_ok() function for now and continuing reading
the next lines, where the ok? messages are received from all neighboring
agents.

3:wait_ok?-mode:

4:when  received (ok?, $\tilde{a}_{n}$, $v_{n}$, $change_{n}$) do

5: $\mathit{counter}\leftarrow\mathit{counter}+1$

6: $\mathit{agent\\_views}\leftarrow\mathit{agent\\_views}\cup v_{n}$

7: if $\mathit{counter}=\mathit{number\\_of\\_neighbors}$ then

8: calc_and_send_improve()

9: $\mathit{counter}\leftarrow 0$

10: enter wait_improve?-mode //see Algorithm 2

11: end if

12:end do

13:

14:procedure calc_and_send_improve()

15:
$\mathit{current\\_cost}\leftarrow\mathchoice{\hbox{$\displaystyle\widetilde{cost}$}}{\hbox{$\textstyle\widetilde{cost}$}}{\hbox{$\scriptstyle\widetilde{cost}$}}{\hbox{$\scriptscriptstyle\widetilde{cost}$}}(v_{l}\cup\mathit{agent\\_views})$
//see Eq. 12 for the definition of $\textstyle\widetilde{cost}$;
$\mathit{agent\\_views}$ directly contains the local views of the neighboring
agents, i.e., $\mathit{agent\\_views}\in D\times...\times D$

16: $v^{\prime}_{l}\leftarrow$ determine new variable assignment that gives
the maximum improvement

17: $\mathit{my\\_improve}\leftarrow
current\\_cost-\mathchoice{\hbox{$\displaystyle\widetilde{cost}$}}{\hbox{$\textstyle\widetilde{cost}$}}{\hbox{$\scriptstyle\widetilde{cost}$}}{\hbox{$\scriptscriptstyle\widetilde{cost}$}}(v^{\prime}_{l}\cup\mathit{agent\\_views})$

18: if $\mathit{my\\_improve}>0$ then

19: $\mathit{can\\_move}\leftarrow\textbf{true}$

20: else

21: $\mathit{can\\_move}\leftarrow\textbf{false}$

22: end if

23: for each neighboring agent $\tilde{a}_{n}$ do

24: send (improve, $\tilde{a}_{l}$, $\mathit{my\\_improve}$,
$\mathit{current\\_cost}$, $\mathit{my\\_termination\\_counter}$) to
$\tilde{a}_{n}$

25: end for

26:end procedure

Algorithm 2 RESMGM – wait_improve?-mode

27:wait_improve?-mode:

28:when  received (improve, $\tilde{a}_{n}$, $v_{n}$, $\mathit{improve_{n}}$,
$\mathit{eval}$, $\mathit{termination\\_counter}$) do

29: $\mathit{counter}\leftarrow\mathit{counter}+1$

30: //Check whether the received variable assignment $v_{n}$ conflicts with
our $v^{\prime}_{l}$ (e.g. if $\tilde{a}_{n}$ wants to use the same resource
as we want). If that is the case and the improvement of $\tilde{a}_{n}$ is
better than ours, then we stick with our old variable assignment. In case of a
tie (identical improvements) a unique agent ID decides.

31: if
$\big{(}assignment\\_conflict(v_{n},v^{\prime}_{l})\big{)}\;\wedge\big{(}\,(\mathit{improve}>\mathit{my\\_improve}\;\vee$
$(\mathit{improve}=\mathit{my\\_improve}$ $\wedge$ $UID(\tilde{a}_{n})$ <
$UID(\tilde{a}_{l}$)) ) then

32: $\mathit{can\\_move}\leftarrow False$

33: end if

34: if $\mathit{counter}=\mathit{number\\_of\\_neighbors}$ then

35: send_ok()

36: $\mathit{counter}\leftarrow 0$

37: clear $\mathit{agent\\_views}$

38: enter wait_ok?-mode //see Algorithm 1

39: end if

40:end do

41:

42:procedure send_ok()

43:
$\mathit{my\\_termination\\_counter}\leftarrow\mathit{my\\_term^{\prime}\\_counter}+1$

44: if $can\\_move$ then

45: $v_{l}\leftarrow v^{\prime}_{l}$

46: $change_{l}\leftarrow my\\_termination\\_counter$

47: end if

48:
$\mathit{change\\_max=\max\limits_{\forall\,\textrm{neighbors}\,\tilde{a}_{n}}\big{\\{}change_{n}\big{\\}}}$

49: if
$\big{(}\mathit{my\\_term^{\prime}\\_counter}=\mathit{max\\_distance}\big{)}\;\vee$
$\big{(}change\\_max-\mathit{my\\_term^{\prime}\\_counter}>Thresh_{early\\_term}\big{)}$
then

50: terminate

51: end if

52: for each neighboring agent $\tilde{a}_{n}$ do

53: send (ok?, $\tilde{a}_{l}$, $\mathit{v_{l}}$, $r_{l}$, $change_{l}$) to
$\tilde{a}_{n}$

54: end for

55:end procedure

###  3.3 RESMGM: Heuristics and Optimization of MGM

In the following, we describe a set of heuristics that we apply in order to
improve the scalability of the MGM algorithm. These improvements are specific
to solving constraints for manycore resource management. We therefore refer to
this improved version of MGM as _Resource Management MGM_ (RESMGM). The
heuristics presented below improve execution time, solution quality, or both.

Smart initialization heuristic: The resource management system has to solve a
new DCOP every time any application changes its resource demands. We
initialize the a priori agents with their actual resource assignment from the
last DCOP optimization and the new agent’s variables with FREE after the first
optimization round. In the very first DCOP optimization, when no prior
resource allocation exists, every agent takes a value that minimizes its local
cost function without taking any other agent into account. By contrast, the
original MGM implementation initializes all variables with random values, as
starting with ‘less conflicting’ assignments reduces the effort of the initial
conflict resolution.

Early termination heuristic: In contrast to the original version of MGM, we
employ a different technique for quick termination detection. The original MGM
algorithm iterates for a fixed amount of $\mathit{max\\_distance}$ rounds,
even if an optimal solution has been found already. In general, determining,
whether a partial solution will not yield any improvement in subsequent
rounds, necessitates computation and communication. We make the following
observation: If the variable assignment does not change for any agent in round
$j,1\\!\leq\\!j\\!\leq\mathit{max\\_distance}$, it will not change for any
agent in the remaining rounds. This is due to the monotonous improvement of
the solution quality of the MGM algorithm. We extend the _ok?_ -message with a
Boolean field that encodes whether the agent has changed its variable in the
last round or whether it has observed change from any other agent’s _ok?_
-message. Every agent counts the rounds in which no change was observed and
terminates when this counter reaches a fixed built-in threshold value that is
determined for the constraint graph of the current DCOP. It is also possible
to lower the threshold value, such that MGM terminates, when ‘nearly all’
agents do not observe any more change in their variables.

Early termination in local search: We formulate the DCOP as a minimization
problem with a minimum constraint cost of zero. If a variable assignment with
zero constraint cost is found, we can abort the search without having to
iterate over the entire domain of a variable. Often variables have an optimal
assignment already before the start of the optimization. This idea can be
extended. Initially, the agents calculate the cost for giving up a resource
(_loss_) and the _ok?_ -message is extended with a field for this value. Upon
receiving an _ok?_ -message, agents store this value for every variable in a
hash map. The agents will then assign their variables to resources of other
agents first, such that the other agent has a minimal loss, while maximizing
its own decrease in solution cost (_gain_).

Incorporating system information: This heuristic exploits information about
the hardware platform in order to solve $C_{\mathrm{TileSharing}}$ more
efficiently. If $C_{\mathrm{TileSharing}}$ applies, the search strategy is
changed from iterating over individual cores to iterating over individual
tiles. Initially, the agent has to find out for every variable, if
$C_{\mathrm{TileSharing}}$ applies to it. The implementation of the heuristic
is similar to the previous one, with the notable difference that loss and gain
is accumulated for entire tiles. The heuristic allows to avoid checking
resources that are on non-free tiles.

Thinking globally: In the original implementation of MGM, agents optimize
their cost function locally without taking the cost of other agents into
account. This heuristic allows agents to consider loss and gain of both agents
in a mutual swap of resources. Due to the extended _ok?_ -message, the agent
can compare its gain with the potential loss of another agent. The agent
achieves this by temporarily changing its own local view to pretend a resource
is not allocated. This heuristic does not improve execution time, but it
improves the solution quality, especially in heavily loaded systems.

Multiple variable changes: The original implementation finds among all
neighbors the variable with the maximum local gain and only this variable is
allowed to change. Instead, this heuristic allows to change the assignment of
an arbitrary amount of variables as long as this does not cause any conflict.
An arbitrary number of variables of one agent can be changed as long as this
reduces the local cost monotonously. The heuristic decreases the amount of
rounds required by the algorithm.

Reduced field-of-view heuristic: If the a priori agents aim to improve their
resource assignment during the optimization too, the amount of constraints can
be reduced significantly by letting the a priori agents choose from PEs only,
that are geometrically close to PEs on the chip, that the priori agents have
claimed already. This means that the a priori agents have a limited _field of
view_. By limiting the field of view to a fixed number of tiles, the maximum
amount of constraints, and thereby conflicts, is limited to a constant and is
no longer affected by the size of the manycore system and the total amount of
agents.

Scalability optimizations: Initial tests show that the large number of
neighboring agents affect the scalability of RESMGM noticeably. We therefore
limit the amount of agents that can participate in the negotiation and propose
a heuristic that allows to select a reasonable subset of agents by augmenting
RESMGM with a _k-d tree_ data structure. The manycore system is logically
partitioned into partitions that group similar types and amounts of computing
resources. In the simplest case of a homogeneous system (see Figure 4) this
results in a binary space partition. The levels of the tree correspond to an
either vertical or horizontal cut of the manycore system as illustrated in
Figure 4. There is a fixed number of levels in the tree, which is
predetermined for the given manycore system. The nodes (except for root)
maintain a list of agents that have at least one resource assigned to them in
the given cut. This tree has to be updated during the execution of the
resource management. The nodes are stored in the scratchpad memory of
individual cores that are associated with the cut. When a new application
requests a resource allocation, its constraint is scanned, e.g., for the
requested resource types. For example, if a constraint does not request any
other core types than regular PEs, a list of agents for the negotiation is
assembled from the k-d tree omitting cuts that have only non-regular resources
(e.g. reconfigurable PEs, see Section 2.2). If a constraint involves a
TileSharing constraint, the tree is scanned for a partition that contains only
resources of a given agent and free resources.

Figure 4:  Example for resource allocation of several agents (top left). k-d
tree over resource allocation (bottom). A partition and the corresponding leaf
in the k-d tree are highlighted.

##  4 Evaluations

###  4.1 Experimental Setup

We evaluated the presented method using the _Sniper Multi-core Simulator_
[21], which is a fast, accurate and parallel simulation infrastructure for x86
architectures. We implemented our proposed RESMGM and the approach presented
by [13] as POSIX threads applications that can be run in Sniper.

Figure 5:  Overheads of different resource management schemes for increasing
number of tiles at constant system utilization. The overheads in the number of
instructions and maximum size of used agent memory of Anagnostopoulos’13 [13]
and RESMGM are comparable. The overheads in message passing overhead and
execution time of RESMGM are significantly smaller than [13].

Sniper is configured with a configuration file that is derived from the many-
core configuration which is shipped with releases of Sniper. This
configuration is loosely inspired by the Intel Xeon Phi and models a many-core
system that features many small cores with private L1 and L2 caches and
directory-based cache coherency. We use this configuration for our simulations
and modify it in order to model a tile-based architecture (see Figure 1) in
Sniper. For a tile-based architecture we need to model and measure messages
that are sent between tiles, i.e., communication between agents. Therefore, we
extend the model and introduce large private L3 caches per core. If used
properly, read and write access to the L3 caches can be regarded as a measure
of the message passing overhead.

At initialization of an agent object on a specific core, an isolated area of
memory (“agent memory”) is allocated for the agent such that it resides
entirely in the simulated L3 cache. Agent memory is only directly accessible
by a specific agent and is entirely self-contained, i.e., not only the actual
data is stored in it, but also the necessary bookkeeping. The agent memory
stores the agent’s message queue, its local view, and every other piece of
private data. Before starting the resource management algorithm, agents load
their agent memory into their private cache simulated in Sniper. Each agent
runs on its own simulated core in Sniper by creating a separate POSIX thread
and pinning it to a unique core.

Communication between agents occurs via simple message passing primitives.
Messages are constructed in the agent memory and appended to another agent’s
message queue. In order to read a message, the receiving agent retrieves a
pointer from the message in the message queue and reads the content that is
located in the sending agent’s agent memory. Subsequent cache-coherency
traffic between cores is therefore directly related to read accesses of remote
agents to another agent’s private cache. This can be exploited to measure
communication overhead of the algorithms. Note that the simulations only
execute the resource management algorithm to ensure that the message passing
evaluation is not disturbed by application activity.

In addition to our proposed RESMGM, we implemented the resource management
scheme introduced by [13] to compare against RESMGM. Ref. [13] introduces a
workload-aware distributed runtime framework for malleable applications, i.e.,
applications that support changing their resources at runtime. In our
experiments, we generate random constraints that are inspired by, but not
limited to the constraints required for the multigrid solver application
introduced in [22]. The multigrid solver has a master-slave structure and a
global queue of jobs. For the individual jobs, it defines
$C_{\mathrm{PEQuantity}}$ to request a single-digit amount of resources, a
scalability with $C_{\mathrm{Downey}}$ and $C_{\mathrm{TileSharing}}$ for some
jobs. Each a priori agent is assigned a random set of resources, in accordance
with a user-defined a priori system load and a specified maximum number of
resources per individual agent. By _a priori system load $\in[0,1]$_ we
understand the ratio of the number of initially allocated resources over the
total number of resources in the system. The metrics we obtain from Sniper are
execution time, number of executed instructions, number of requests to agent
memory and maximum size of used agent memory. The number of requests to agent
memory is equal to the number of loads from remote caches necessary for cache
coherency measured by the Sniper framework. The numbers, that we report, are
averaged over all cores of a system.

Figure 6: Overheads of different resource management schemes for increasing
number of agents at constant system size. The overheads in the number of
instructions and maximum size of used agent memory of Anagnostopoulos’13 [13]
and RESMGM are comparable. The overheads in message passing and execution time
of RESMGM are significantly smaller than [13]. An exception is the case of a
fully loaded system in which RESMGM needs to test a big number of possible
resource assignments before finding a valid solution. This creates high
overheads in the number of instructions and execution time.

A limitation of the comparison between RESMGM and [13] is, that they do not
support constraints, except for $C_{\mathrm{Downey}}$. In order to allow for a
more fair comparison, $C_{\textrm{TileSharing}}$ cannot be used. Ref. [13]
does not distinguish between different types of resources and disregards the
intricate resource requirements that applications formulate with a set of
constraints. This intrinsic deficiency of [13] puts RESMGM naturally at a
disadvantage in the following evaluations, since it is significantly more
complex to satisfy an entire set of constraints instead of balancing different
scaling properties of a number of applications. The following experiments were
conducted on a system with an Intel Core i7-6700T CPU with a clock rate of
$2.80\,\mathrm{GHz}$ and $32\,\mathrm{GiB}$ DDR3 RAM running Ubuntu 17.04
(GNU/Linux 4.10.0-33-generic x86_64).

###  4.2 Simulation Results

####  4.2.1 Increasing the number of tiles

In the first experiment, we vary the domain size, i.e., the amount of tiles in
the manycore system, ranging from 1 to 8. The a priori system load is at a
constant of 40% and the number of a priori agents is adjusted accordingly. A
priori agents are assigned up to 4 resources and the new agent requires 2 to 4
resources of any type. The overheads measured in the experiment are shown in
Figure 5. RESMGM has a significantly smaller execution time and message
passing overhead, although being at a disadvantage in the simulation setup.
The number of instructions and the maximum size of used agent memory are
comparable for both approaches. Reducing the amount of agents that participate
in the negotiation with the k-d tree helps to reduce the overheads further,
albeit visually it does not seem to alter the scalability of our approach
itself. For small numbers of tiles, the bars in Figure 5 for RESMGM w/ k-d
tree are too small to be visually seen in the plot. Note that [13] is a
randomized algorithm and the results may vary depending on random seed, system
state etc.

####  4.2.2 Increasing the number of agents

In the second experiment, the number of a priori agents is increased from 2 to
10 on a system with 3 tiles. A priori agents only claim up to 2 resources,
while the new agent continues to demand 2 to 4 resources of any type. The a
priori system load ranges from 11% (with two agents) to 100% (with ten
agents). The performed measurements are analogous to the previous experiment.
Our findings are shown in Figure 6. Similar to the first experiment, the
number of instructions and maximum size of used agent memory is comparable for
RESMGM and [13]. Message passing overhead and execution times are always
smaller for RESMGM, except for the case of a highly loaded system, in which
RESMGM has an execution time of more than 2$\times$ compared to [13]. This is
because the RESMGM agents need to test a big number of possible variable
assignments and evaluate the corresponding constraints before finding a valid
solution in a highly loaded system. Again, for a small numbers of agents, the
bars in Figure 6 for RESMGM w/ k-d tree are too small to be visually seen in
the plot.

##  5 Conclusions

The resources of state/of/the/art manycore systems are heterogeneous for
efficiency reasons. Their management, i.e., mapping application to cores, has
become a key problem since workloads are increasingly complex. We present a
DCOP formulation of the manycore resource allocation problem that allows
finding a resource allocation at runtime in a decentralized manner for
applications that provide constraints on their resource requirements. Our
proposed local search algorithm RESMGM finds resource allocations quickly and
efficiently with a high solution quality requiring a feasible computational
overhead. We demonstrate the effectiveness of our proposed approach with an
evaluation using the Sniper multi/core simulator. The computational overheads
of the state/of/the/art approach [13] and RESMGM are mostly comparable, but
RESMGM allows applications to express a wide range of constraints flexibly.

## Acknowledgment

Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research
Foundation) – Project Number 146371743 – TRR 89 Invasive Computing

## References

  * [1] S. Borkar, “Thousand core chips: A technology perspective,” in _Design Automation Conference (DAC)_ , 2007, pp. 746–749.
  * [2] A. Sodani, R. Gramunt, J. Corbal, H. S. Kim, K. Vinod, S. Chinthamani, S. Hutsell, R. Agarwal, and Y. C. Liu, “Knights Landing: Second-generation Intel Xeon Phi product,” _IEEE Micro_ , vol. 36, no. 2, pp. 34–46, 2016\.
  * [3] T. Ebi, M. A. Al Faruque, and J. Henkel, “TAPE: Thermal-aware agent-based power economy for multi/many-core architectures,” in _Intl. Conf. on Computer-Aided Design (ICCAD)_ , 2009, pp. 302–309.
  * [4] J. Cao, S. A. Jarvis, S. Saini, D. J. Kerbyson, and G. R. Nudd, “ARMS: An agent-based resource management sys. for grid comput.” _Scientific Programming_ , vol. 10, no. 2, pp. 135–148, 2002.
  * [5] Y. Ge, P. Malani, and Q. Qiu, “Distributed task migration for therm. manag. in many-core systems,” in _Design Automation Conference (DAC)_ , 2010, pp. 579–584.
  * [6] S. Kobbe, L. Bauer, D. Lohmann, W. Schröder-Preikschat, and J. Henkel, “DistRM: Distributed resource management for on-chip many-core systems,” in _Intl. Conf. on Hardware/Software Codesign and System Synthesis (CODES+ISSS)_ , 2011, pp. 119–128.
  * [7] F. Hannig, S. Roloff, G. Snelting, J. Teich, and A. Zwinkau, “Resource-aware programming and simulation of MPSoC architectures through extension of X10,” in _Intl. Workshop on Software and Compilers for Emb. Sys. (SCOPES)_ , 2011, pp. 48–55.
  * [8] H.-J. Bungartz, C. Riesinger, M. Schreiber, G. Snelting, and A. Zwinkau, “Invasive computing in HPC with X10,” in _SIGPLAN X10 Workshop (X10)_ , 2013, pp. 12–19.
  * [9] A. K. Singh, M. Shafique, A. Kumar, and J. Henkel, “Mapping on multi/many-core sys.: Surv. of curr. and emerg. trends,” in _Design Automat. Conf. (DAC)_ , 2013, pp. 1:1–1:10.
  * [10] A. K. Singh, P. Dziurzanski, H. R. Mendis, and L. S. Indrusiak, “A survey and comparative study of hard and soft real-time dynamic resource allocation strategies for multi-/many-core systems,” _ACM Computing Survey_ , vol. 50, no. 2, pp. 24:1–24:40, 2017.
  * [11] M. Fattah, M. Daneshtalab, P. Liljeberg, and J. Plosila, “Smart hill climb. for agile dyn. mapping in many-core systems,” in _Design Automation Conference (DAC)_ , 2013, pp. 39:1–39:6.
  * [12] G. Castilhos, M. Mandelli, G. Madalozzo, and F. Moraes, “Distributed res. manag. in NoC-based MPSoCs with dyn. cluster sizes,” in _Symposium on VLSI (ISVLSI)_ , 2013, pp. 153–158.
  * [13] I. Anagnostopoulos, V. Tsoutsouras, A. Bartzas, and D. Soudris, “Distributed run-time resource management for malleable applications on many-core platforms,” in _Design Automation Conference (DAC)_ , 2013, pp. 168:1–168:6.
  * [14] T. Melissaris, I. Anagnostopoulos, D. Soudris, and D. Reisis, “Agora: Agent and market-based resource management for many-core systems,” in _Intl. Conference on Electronics, Circuits and Systems (ICECS)_ , 2016.
  * [15] S. Wildermann, M. Glaß, and J. Teich, “Multi-objective distributed run-time resource management for many-cores,” in _Conference on Design, Automation & Test in Europe (DATE)_, 2014, pp. 221:1–221:6.
  * [16] D. Olsen and I. Anagnostopoulos, “Performance-aware resource management of multi-threaded applications on many-core systems,” in _Great Lakes Symposium on VLSI_ , 2017.
  * [17] R. T. Maheswaran, J. P. Pearce, and M. Tambe, “Distributed algorithms for DCOP: A graphical-game-based approach.” in _Intl. Conf. on Parallel and Distr. Computing and Comm. Systems (ISCA PDCS)_ , 2004, pp. 432–439.
  * [18] W. Yeoh, A. Felner, and S. Koenig, “BnB-ADOPT: An asynchronous branch-and-bound DCOP algorithm,” in _Intl. Joint Conf. on Autonomous Agents and Multiagent Systems - Volume 2 (AAMAS)_ , 2008, pp. 591–598.
  * [19] A. B. Downey, “A parallel workload model and its implications for processor allocation,” _Cluster Comput._ , vol. 1, no. 1, pp. 133–145, 1998.
  * [20] M. Yokoo and K. Hirayama, “Distributed breakout algorithm for solving distributed constraint,” in _Intl. Conf. on Multiagent Systems_ , 1996, pp. 401–408.
  * [21] T. E. Carlson, W. Heirmant, and L. Eeckhout, “Sniper: Exploring the level of abstraction for scalable and accurate parallel multi-core simulation,” in _Intl. Conf. for High Perf. Comput., Network., Storage and Analysis (SC)_ , 2011.
  * [22] S. Buchwald, M. Mohr, and A. Zwinkau, “Malleable invasive applications,” in _Software Engineering (Workshops)_ , 2015, pp. 123–126.

|  Volker Wenzel worked under the supervision of Prof. Jörg Henkel at the
Chair for Embedded Systems (CES), Karlsruhe Institute of Technology, Germany
from May 2013 until Oct. 2018.
---|---
|  Lars Bauer received the M.Sc. and Ph.D. degrees in computer science from
the University of Karlsruhe, Germany, in 2004 and 2009. He is currently a
research group leader and lecturer at the Chair for Embedded Systems (CES) at
the Karlsruhe Institute of Technology (KIT). Dr. Bauer received two
dissertation awards (EDAA and FZI), two best paper awards (AHS’11 and DATE’08)
and several nominations. His research interests include architectures and
management for adaptive multi-/manycore systems.
---|---
|  Wolfgang Schröder-Preikschat studied computer science at the Technical
University of Berlin, Germany, where he also took his doctor’s degree and
venia legendi. After a long-term period of extramural research at GMD/FhG,
Berlin, Germany, and ICSI, Berkeley, USA, he became full professor for
computer science at University of Potsdam, Magdeburg, and Erlangen, Germany,
likewise. Dr. Schröder-Preikschat is member of ACM, EuroSys, GI, IEEE, and
USENIX. His main research interest is on resource-aware (parallel) operating
systems, notably process coordination, especially as to time/energy-dependable
application and problem domains.
---|---
|  Jörg Henkel received the Diploma and Ph.D. (summa cum laude) degree from
the Technical University of Braunschweig. He is currently the Chair Professor
of embedded systems with the Karlsruhe Institute of Technology. Before that he
was a Research Staff Member with NEC Laboratories, Princeton, NJ, USA. His
research interest includes co-design for embedded hardware/software systems
with respect to power security and means of embedded machine learning. He has
led several conferences as a General Chair including ICCAD and ESWeek, and is
currently DAC Vice Chair. He serves as a steering committee chair/member for
leading conferences and journals for embedded and cyber-physical systems. He
has coordinated the DFG Program SPP 1500 “Dependable Embedded Systems” and is
a Site Coordinator of the DFG TR89 Collaborative Research Center on “Invasive
Computing”. He is the Chairman of the IEEE Computer Society, Germany Chapter.
He has received six best paper awards throughout his career from, among
others, ICCAD, ESWeek, and DATE. For two consecutive terms each, he served as
the Editor-in-Chief for both the ACM Transactions on Embedded Computing
Systems and the IEEE Design & Test magazine. He is the Vice President for
Publications at IEEE CEDA and a Fellow of the IEEE.
---|---