Mapping of Subtasks with Multiple Versions in a Heterogeneous Ad Hoc Grid Environment
- 5 April 2005
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 380-387
- https://doi.org/10.1109/ispdc.2004.34
Abstract
An ad hoc grid is a heterogeneous computing system composed of mobile devices. The problem studied here is to statically assign resources to the subtasks of an application, which has an execution time constraint, when the resources are oversubscribed. Each subtask has a preferred version, and a secondary version that uses fewer resources. The goal is to assign resources so that the application meets its execution time constraint while minimizing the number of secondary versions used. Five resource allocation heuristics to derive near-optimal solutions to this problem are presented and evaluated.Keywords
This publication has 13 references indexed in Scilit:
- Static mapping of subtasks in a heterogeneous ad hoc grid environmentPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Ad hoc grids: communication and computing in a power constrained environmentPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- The relative performance of various mapping algorithms is independent of sizable variances in run-time predictionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Segmented min-min: a static mapping algorithm for meta-tasks on heterogeneous computing systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- How to Solve It: Modern HeuristicsPublished by Springer Nature ,2000
- Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing SystemsJournal of Parallel and Distributed Computing, 1999
- Task Matching and Scheduling in Heterogeneous Computing Environments Using a Genetic-Algorithm-Based ApproachJournal of Parallel and Distributed Computing, 1997
- Genetic algorithms: a surveyComputer, 1994
- Allocating modules to processors in a distributed systemIEEE Transactions on Software Engineering, 1989
- Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical ProcessorsJournal of the ACM, 1977