Dynamic Resource Allocation

T.D. ter Braak, Gerardus Johannes Maria Smit, P.K.F. Holzenspies

Research output: Book/ReportReportProfessional

94 Downloads (Pure)

Abstract

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.
Original languageUndefined
Place of PublicationEnschede
PublisherCentre for Telematics and Information Technology (CTIT)
Number of pages45
Publication statusPublished - 29 Feb 2016

Publication series

Name
PublisherUniversity 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

ter Braak, T. D., Smit, G. J. M., & Holzenspies, P. K. F. (2016). Dynamic Resource Allocation. Enschede: Centre for Telematics and Information Technology (CTIT).
ter Braak, T.D. ; Smit, Gerardus Johannes Maria ; Holzenspies, P.K.F. / Dynamic Resource Allocation. Enschede : Centre for Telematics and Information Technology (CTIT), 2016. 45 p.
@book{7ba26a69e0b4409baf72218dcb6e14bb,
title = "Dynamic Resource Allocation",
abstract = "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.",
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",
author = "{ter Braak}, T.D. and Smit, {Gerardus Johannes Maria} and P.K.F. Holzenspies",
note = "eemcs-eprint-26878",
year = "2016",
month = "2",
day = "29",
language = "Undefined",
publisher = "Centre for Telematics and Information Technology (CTIT)",
address = "Netherlands",

}

ter Braak, TD, Smit, GJM & Holzenspies, PKF 2016, 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.

Enschede : Centre for Telematics and Information Technology (CTIT), 2016. 45 p.

Research output: Book/ReportReportProfessional

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 -

ter Braak TD, Smit GJM, Holzenspies PKF. Dynamic Resource Allocation. Enschede: Centre for Telematics and Information Technology (CTIT), 2016. 45 p.