### Abstract

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | Centre for Telematics and Information Technology (CTIT) |

Number of pages | 45 |

Publication status | Published - 29 Feb 2016 |

### Publication series

Name | |
---|---|

Publisher | University of Twente, Centre for Telematics and Information Technology (CTIT) |

ISSN (Print) | 1381-3625 |

### Keywords

- EC Grant Agreement nr.: FP7/318490
- assignment
- guided local search
- run-time mapping
- Optimization
- multi-resource quadratic assignment and routing problem
- dynamic resource allocation
- Energy
- Scheduling
- Embedded Systems
- IR-99718
- METIS-316850
- EWI-26878
- EC Grant Agreement nr.: FP7/2007-2013

### Cite this

*Dynamic Resource Allocation*. Enschede: Centre for Telematics and Information Technology (CTIT).

}

*Dynamic Resource Allocation*. Centre for Telematics and Information Technology (CTIT), Enschede.

**Dynamic Resource Allocation.** / ter Braak, T.D.; Smit, Gerardus Johannes Maria; Holzenspies, P.K.F.

Research output: Book/Report › Report › Professional

TY - BOOK

T1 - Dynamic Resource Allocation

AU - ter Braak, T.D.

AU - Smit, Gerardus Johannes Maria

AU - Holzenspies, P.K.F.

N1 - eemcs-eprint-26878

PY - 2016/2/29

Y1 - 2016/2/29

N2 - Computer systems are subject to continuously increasing performance demands. However, energy consumption has become a critical issue, both for high-end large-scale parallel systems [12], as well as for portable devices [34]. In other words, more work needs to be done in less time, preferably with the same or smaller energy budget. Future performance and efficiency goals of computer systems can only be reached with large-scale, heterogeneous architectures [6]. Due to their distributed nature, control software is required to coordinate the parallel execution of applications on such platforms. Abstraction, arbitration and multi-objective optimization are only a subset of the tasks this software has to fulfill [6, 31]. The essential problem in all this is the allocation of platform resources to satisfy the needs of an application. This work considers the dynamic resource allocation problem, also known as the run-time mapping problem. This problem consists of task assignment to (processing) elements and communication routing through the interconnect between the elements. In mathematical terms, the combined problem is defined as the multi-resource quadratic assignment and routing problem (MRQARP). An integer linear programming formulation is provided, as well as complexity proofs on the N P-hardness of the problem. This work builds upon state-of-the-art work of Yagiura et al. [39, 40, 42] on metaheuristics for various generalizations of the generalized assignment problem. Specifically, we focus on the guided local search (GLS) approach for the multi-resource quadratic assignment problem (MRQAP). The quadratic assignment problem defines a cost relation between tasks and between elements. We generalize the multi-resource quadratic assignment problem with the addition of a capacitated interconnect and a communication topology between tasks. Numerical experiments show that the performance of the approach is comparable with commercial solvers. The footprint, the time versus quality trade-off and available metadata make guided local search a suitable candidate for run-time mapping.

AB - Computer systems are subject to continuously increasing performance demands. However, energy consumption has become a critical issue, both for high-end large-scale parallel systems [12], as well as for portable devices [34]. In other words, more work needs to be done in less time, preferably with the same or smaller energy budget. Future performance and efficiency goals of computer systems can only be reached with large-scale, heterogeneous architectures [6]. Due to their distributed nature, control software is required to coordinate the parallel execution of applications on such platforms. Abstraction, arbitration and multi-objective optimization are only a subset of the tasks this software has to fulfill [6, 31]. The essential problem in all this is the allocation of platform resources to satisfy the needs of an application. This work considers the dynamic resource allocation problem, also known as the run-time mapping problem. This problem consists of task assignment to (processing) elements and communication routing through the interconnect between the elements. In mathematical terms, the combined problem is defined as the multi-resource quadratic assignment and routing problem (MRQARP). An integer linear programming formulation is provided, as well as complexity proofs on the N P-hardness of the problem. This work builds upon state-of-the-art work of Yagiura et al. [39, 40, 42] on metaheuristics for various generalizations of the generalized assignment problem. Specifically, we focus on the guided local search (GLS) approach for the multi-resource quadratic assignment problem (MRQAP). The quadratic assignment problem defines a cost relation between tasks and between elements. We generalize the multi-resource quadratic assignment problem with the addition of a capacitated interconnect and a communication topology between tasks. Numerical experiments show that the performance of the approach is comparable with commercial solvers. The footprint, the time versus quality trade-off and available metadata make guided local search a suitable candidate for run-time mapping.

KW - EC Grant Agreement nr.: FP7/318490

KW - assignment

KW - guided local search

KW - run-time mapping

KW - Optimization

KW - multi-resource quadratic assignment and routing problem

KW - dynamic resource allocation

KW - Energy

KW - Scheduling

KW - Embedded Systems

KW - IR-99718

KW - METIS-316850

KW - EWI-26878

KW - EC Grant Agreement nr.: FP7/2007-2013

M3 - Report

BT - Dynamic Resource Allocation

PB - Centre for Telematics and Information Technology (CTIT)

CY - Enschede

ER -