Dynamically mapping tasks with priorities and multiple deadlines in a heterogeneous environment

Jong Kook Kim, Sameer Shivle, Howard Jay Siegel, Anthony A. Maciejewski, Tracy D. Braun, Myron Schneider, Sonja Tideman, Ramakrishna Chitta, Raheleh B. Dilmaghani, Rohit Joshi, Aditya Kaul, Ashish Sharma, Siddhartha Sripada, Praveen Vangari, Siva Sankar Yellampalli

Research output: Contribution to journalArticlepeer-review

76 Citations (Scopus)


In a distributed heterogeneous computing system, the resources have different capabilities and tasks have different requirements. To maximize the performance of the system, it is essential to assign the resources to tasks (match) and order the execution of tasks on each resource (schedule) to exploit the heterogeneity of the resources and tasks. Dynamic mapping (defined as matching and scheduling) is performed when the arrival of tasks is not known a priori. In the heterogeneous environment considered in this study, tasks arrive randomly, tasks are independent (i.e., no inter-task communication), and tasks have priorities and multiple soft deadlines. The value of a task is calculated based on the priority of the task and the completion time of the task with respect to its deadlines. The goal of a dynamic mapping heuristic in this research is to maximize the value accrued of completed tasks in a given interval of time. This research proposes, evaluates, and compares eight dynamic mapping heuristics. Two static mapping schemes (all arrival information of tasks are known) are designed also for comparison. The performance of the best heuristics is 84% of a calculated upper bound for the scenarios considered.

Original languageEnglish
Pages (from-to)154-169
Number of pages16
JournalJournal of Parallel and Distributed Computing
Issue number2
Publication statusPublished - 2007 Feb
Externally publishedYes

Bibliographical note

Funding Information:
This research was supported by the Colorado State University George T. Abell Endowment. ∗Corresponding author. E-mail addresses: jongkook@ieee.org (J.-K. Kim), sameer.shivle@gmail.com (S. Shivle), hj@colostate.edu (H.J. Siegel), aam@colostate.edu (A.A. Maciejewski), tdbraun@yahoo.com (T.D. Braun), myron_schneider@agilent.com (M. Schneider), stidema@sandia.gov (S. Tideman), ramacmr@cs.colostate.edu(R. Chitta), rdilmaghani@ucsd.edu (R.B.Dilmaghani), aditya21@lycos.com(A.Kaul), ashish@engr.colostate.edu (A. Sharma), siddhu@engr.colostate.edu (S. Sripada), praveen@engr.colostate.edu (P. Vangari), syella1@lsu.edu (S.S. Yellampalli).


  • Deadlines
  • Distributed computing
  • Dynamic mapping
  • Heterogeneous computing
  • Priority
  • Resource allocation
  • Resource management
  • Scheduling
  • Static mapping

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'Dynamically mapping tasks with priorities and multiple deadlines in a heterogeneous environment'. Together they form a unique fingerprint.

Cite this