A metric and mixed-integer-programming-based approach for resource allocation in dynamic real-time systems
Date
2002
Authors
Siegel, Howard Jay, author
Maciejewski, Anthony A., author
Kim, Jong-Kook, author
Ali, Shoukat, author
Prasanna Kumar, V. K., author
Gundala, Shriram Bhargava, author
Yu, Yang, author
Gertphol, Sethavidh, author
IEEE, publisher
Journal Title
Journal ISSN
Volume Title
Abstract
Dynamic real-time systems such as embedded systems operate in environments in which several parameters vary at run time. These systems must satisfy several performance requirements. Resource allocation on these systems becomes challenging because variations of run-time parameters may cause violations of the performance requirements. Performance violations result in the need for dynamic re-allocation, which is a costly operation. In this paper, a method for allocating resources such that the allocation can sustain the system in the light of a continuously changing environment is developed. We introduce a novel performance metric called MAIL (maximum allowable increase in load) to capture the effectiveness of a resource allocation. Given a resource allocation, MAIL quantifies the amount of additional load that can be sustained by the system without any performance violations. A Mixed-Integer-Programming-based approach (MIP) is developed to determine a resource allocation that has the highest MAIL value. Using simulations, several sets of experiments are conducted to evaluate our heuristics in various scenarios of machine and task heterogeneities. The performance of MIP is compared with three other heuristics: Integer-Programming based, Greedy, and classic Min-Min. Our results show that MIP performs signifantly better when compared with the other heuristics.
Description
Rights Access
Subject
distributed processing
integer programming
real-time systems
resource allocation
software metrics
software performance evaluation