The Experts below are selected from a list of 279 Experts worldwide ranked by ideXlab platform

H.j. Siegel - One of the best experts on this subject based on the ideXlab platform.

  • preemptive resource management for dynamically arriving tasks in an oversubscribed Heterogeneous Computing System
    International Parallel and Distributed Processing Symposium, 2017
    Co-Authors: Dylan Machovec, H.j. Siegel, Anthony A. Maciejewski, Gregory A. Koenig, Sudeep Pasricha, Marcia Hilton, Rajendra Rambharos, Michael Wright, Thomas J Naughton, Neena Imam
    Abstract:

    We design resource management heuristics that assign serial tasks to the nodes of a Heterogeneous high performance Computing (HPC) System. The value of completing these tasks is modeled using monotonically decreasing utility functions that represent the time-varying importance of the task. The value of completing a task is equal to its utility function at the time of its completion. The overall performance of this System is measured using the total utility earned by all tasks during some interval of time. To maximize the performance of such a System where the preemption of tasks is possible, we have designed, analyzed, and compared a set of resource allocation heuristic techniques. We combine two utility-aware heuristics with three different preemption techniques to create six preemption-capable heuristics. We also consider the two utility-aware heuristics without preemption. We use simulation studies to evaluate this set of eight heuristics and compare them with an FCFS heuristic, which is often used in real Systems, and random assignments. In general, our set of eight heuristics is able to significantly outperform the comparison heuristics, and the preemption-capable heuristics are able to significantly increase the utility earned compared to the heuristics that do not use preemption. We analyze the performance tradeoffs among the different preemption-capable heuristics under a variety of oversubscribed workload environments.

  • stochastic based robust dynamic resource allocation for independent tasks in a Heterogeneous Computing System
    Journal of Parallel and Distributed Computing, 2016
    Co-Authors: Mohsen Amini Salehi, Luis D. Briceño, H.j. Siegel, Anthony A. Maciejewski, Jonathan Apodaca, Jay Smith, Edwin K P Chong, Timothy Renner, Vladimir Shestak, Joshua Ladd
    Abstract:

    Heterogeneous parallel and distributed Computing Systems frequently must operate in environments where there is uncertainty in System parameters. Robustness can be defined as the degree to which a System can function correctly in the presence of parameter values different from those assumed. In such an environment, the execution time of any given task may fluctuate substantially due to factors such as the content of data to be processed. Determining a resource allocation that is robust against this uncertainty is an important area of research. In this study, we define a stochastic robustness measure to facilitate resource allocation decisions in a dynamic environment where tasks are subject to individual hard deadlines and each task requires some input data to start execution. In this environment, the tasks that cannot meet their deadlines are dropped (i.e., discarded). We define methods to determine the stochastic completion times of tasks in the presence of the task dropping. The stochastic task completion time is used in the definition of the stochastic robustness measure. Based on this stochastic robustness measure, we design novel resource allocation techniques that work in immediate and batch modes, with the goal of maximizing the number of tasks that meet their individual deadlines. We compare the performance of our technique against several well-known approaches taken from the literature and adapted to our environment. Simulation results of this study demonstrate the suitability of our new technique in a dynamic Heterogeneous Computing System. Calculating stochastic task completion time in Heterogeneous System with task dropping.A model to quantify resource allocation robustness and propose mapping heuristics.Evaluating immediate and batch mappings and optimizing queue-size limit of batch mode.Analyzing impact of over-subscription level on immediate and batch allocation modes.Providing a model in the batch mode to run mapping events before machines become idle.

  • makespan and energy robust stochastic static resource allocation of a bag of tasks to a Heterogeneous Computing System
    IEEE Transactions on Parallel and Distributed Systems, 2015
    Co-Authors: Mark A Oxley, Luis D. Briceño, H.j. Siegel, Anthony A. Maciejewski, Jonathan Apodaca, Jay Smith, Sudeep Pasricha, Dalton Young, Shirish Bahirat, Bhavesh Khemka
    Abstract:

    Today’s data centers face the issue of balancing electricity use and completion times of their workloads. Rising electricity costs are forcing data center operators to either operate within an electricity budget or to reduce electricity use as much as possible while still maintaining service agreements. Energy-aware resource allocation is one technique a System administrator can employ to address both problems: optimizing the workload completion time (makespan) when given an energy budget, or to minimize energy consumption subject to service guarantees (such as adhering to deadlines). In this paper, we study the problem of energy-aware static resource allocation in an environment where a collection of independent (non-communicating) tasks (“bag-of-tasks”) is assigned to a Heterogeneous Computing System. Computing Systems often operate in environments where task execution times vary (e.g., due to cache misses or data dependent execution times). We model these execution times stochastically, using probability density functions. We want our resource allocations to be robust against these variations, where we define energy-robustness as the probability that the energy budget is not violated, and makespan-robustness as the probability a makespan deadline is not violated. We develop and analyze several heuristics for energy-aware resource allocation for both energy-constrained and deadline-constrained problems.

  • utility maximizing dynamic resource management in an oversubscribed energy constrained Heterogeneous Computing System
    Sustainable Computing: Informatics and Systems, 2015
    Co-Authors: Bhavesh Khemka, H.j. Siegel, Anthony A. Maciejewski, Gregory A. Koenig, Sudeep Pasricha, Ryan Friese, Sarah Powers, Marcia Hilton, Rajendra Rambharos, Steve Poole
    Abstract:

    Abstract The need for greater performance in high performance Computing Systems combined with rising costs of electricity to power these Systems motivates the need for energy-efficient resource management. Driven by the requirements of the Extreme Scale Systems Center at Oak Ridge National Laboratory, we address the problem of scheduling dynamically-arriving tasks to machines in an oversubscribed and energy-constrained Heterogeneous distributed Computing environment. Our goal is to maximize total “utility” earned by the System, where the utility of a task is defined by a monotonically-decreasing function that represents the value of completing that task at different times. To address this problem, we design four energy-aware resource allocation heuristics and compare their performance to heuristics from the literature. For our given energy-constrained environment, we also design an energy filtering technique that helps some heuristics regulate their energy consumption by allowing tasks to only consume up to an estimated fair-share of energy. Extensive sensitivity analyses of the heuristics in environments with different levels of heterogeneity show that heuristics with the ability to balance both energy consumption and utility exhibit the best performance because they save energy for use by future tasks.

  • Time utility functions for modeling and evaluating resource allocations in a Heterogeneous Computing System
    IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum, 2011
    Co-Authors: Luis D. Briceño, Bhavesh Khemka, Christopher Groër, Gregory Koenig, Gene Okonski, H.j. Siegel, Anthony A. Maciejewski, Steve Poole
    Abstract:

    This study considers a Heterogeneous Computing System and corresponding workload being investigated by the Extreme Scale Systems Center (ESSC) at Oak Ridge National Laboratory (ORNL). The ESSC is part of a collaborative effort between the Department of Energy (DOE) and the Department of Defense (DoD) to deliver research, tools, software, and technologies that can be integrated, deployed, and used in both DOE and DoD environments. The Heterogeneous System and workload described here are representative of a prototypical Computing environment being studied as part of this collaboration. Each task can exhibit a time-varying emph{importance} or emph{utility} to the overall enterprise. In this System, an arriving task has an associated priority and precedence. The priority is used to describe the importance of a task, and precedence is used to describe how soon the task must be executed. These two metrics are combined to create a utility function curve that indicates how valuable it is for the System to complete a task at any given moment. This research focuses on using time-utility functions to generate a metric that can be used to compare the performance of different resource schedulers in a Heterogeneous Computing System. The contributions of this paper are: (a) a mathematical model of a Heterogeneous Computing System where tasks arrive dynamically and need to be assigned based on their priority, precedence, utility characteristic class, and task execution type, (b) the use of priority and precedence to generate time-utility functions that describe the value a task has at any given time, (c) the derivation of a metric based on the total utility gained from completing tasks to measure the performance of the Computing environment, and (d) a comparison of the performance of resource allocation heuristics in this environment

Anthony A. Maciejewski - One of the best experts on this subject based on the ideXlab platform.

  • preemptive resource management for dynamically arriving tasks in an oversubscribed Heterogeneous Computing System
    International Parallel and Distributed Processing Symposium, 2017
    Co-Authors: Dylan Machovec, H.j. Siegel, Anthony A. Maciejewski, Gregory A. Koenig, Sudeep Pasricha, Marcia Hilton, Rajendra Rambharos, Michael Wright, Thomas J Naughton, Neena Imam
    Abstract:

    We design resource management heuristics that assign serial tasks to the nodes of a Heterogeneous high performance Computing (HPC) System. The value of completing these tasks is modeled using monotonically decreasing utility functions that represent the time-varying importance of the task. The value of completing a task is equal to its utility function at the time of its completion. The overall performance of this System is measured using the total utility earned by all tasks during some interval of time. To maximize the performance of such a System where the preemption of tasks is possible, we have designed, analyzed, and compared a set of resource allocation heuristic techniques. We combine two utility-aware heuristics with three different preemption techniques to create six preemption-capable heuristics. We also consider the two utility-aware heuristics without preemption. We use simulation studies to evaluate this set of eight heuristics and compare them with an FCFS heuristic, which is often used in real Systems, and random assignments. In general, our set of eight heuristics is able to significantly outperform the comparison heuristics, and the preemption-capable heuristics are able to significantly increase the utility earned compared to the heuristics that do not use preemption. We analyze the performance tradeoffs among the different preemption-capable heuristics under a variety of oversubscribed workload environments.

  • stochastic based robust dynamic resource allocation for independent tasks in a Heterogeneous Computing System
    Journal of Parallel and Distributed Computing, 2016
    Co-Authors: Mohsen Amini Salehi, Luis D. Briceño, H.j. Siegel, Anthony A. Maciejewski, Jonathan Apodaca, Jay Smith, Edwin K P Chong, Timothy Renner, Vladimir Shestak, Joshua Ladd
    Abstract:

    Heterogeneous parallel and distributed Computing Systems frequently must operate in environments where there is uncertainty in System parameters. Robustness can be defined as the degree to which a System can function correctly in the presence of parameter values different from those assumed. In such an environment, the execution time of any given task may fluctuate substantially due to factors such as the content of data to be processed. Determining a resource allocation that is robust against this uncertainty is an important area of research. In this study, we define a stochastic robustness measure to facilitate resource allocation decisions in a dynamic environment where tasks are subject to individual hard deadlines and each task requires some input data to start execution. In this environment, the tasks that cannot meet their deadlines are dropped (i.e., discarded). We define methods to determine the stochastic completion times of tasks in the presence of the task dropping. The stochastic task completion time is used in the definition of the stochastic robustness measure. Based on this stochastic robustness measure, we design novel resource allocation techniques that work in immediate and batch modes, with the goal of maximizing the number of tasks that meet their individual deadlines. We compare the performance of our technique against several well-known approaches taken from the literature and adapted to our environment. Simulation results of this study demonstrate the suitability of our new technique in a dynamic Heterogeneous Computing System. Calculating stochastic task completion time in Heterogeneous System with task dropping.A model to quantify resource allocation robustness and propose mapping heuristics.Evaluating immediate and batch mappings and optimizing queue-size limit of batch mode.Analyzing impact of over-subscription level on immediate and batch allocation modes.Providing a model in the batch mode to run mapping events before machines become idle.

  • makespan and energy robust stochastic static resource allocation of a bag of tasks to a Heterogeneous Computing System
    IEEE Transactions on Parallel and Distributed Systems, 2015
    Co-Authors: Mark A Oxley, Luis D. Briceño, H.j. Siegel, Anthony A. Maciejewski, Jonathan Apodaca, Jay Smith, Sudeep Pasricha, Dalton Young, Shirish Bahirat, Bhavesh Khemka
    Abstract:

    Today’s data centers face the issue of balancing electricity use and completion times of their workloads. Rising electricity costs are forcing data center operators to either operate within an electricity budget or to reduce electricity use as much as possible while still maintaining service agreements. Energy-aware resource allocation is one technique a System administrator can employ to address both problems: optimizing the workload completion time (makespan) when given an energy budget, or to minimize energy consumption subject to service guarantees (such as adhering to deadlines). In this paper, we study the problem of energy-aware static resource allocation in an environment where a collection of independent (non-communicating) tasks (“bag-of-tasks”) is assigned to a Heterogeneous Computing System. Computing Systems often operate in environments where task execution times vary (e.g., due to cache misses or data dependent execution times). We model these execution times stochastically, using probability density functions. We want our resource allocations to be robust against these variations, where we define energy-robustness as the probability that the energy budget is not violated, and makespan-robustness as the probability a makespan deadline is not violated. We develop and analyze several heuristics for energy-aware resource allocation for both energy-constrained and deadline-constrained problems.

  • utility maximizing dynamic resource management in an oversubscribed energy constrained Heterogeneous Computing System
    Sustainable Computing: Informatics and Systems, 2015
    Co-Authors: Bhavesh Khemka, H.j. Siegel, Anthony A. Maciejewski, Gregory A. Koenig, Sudeep Pasricha, Ryan Friese, Sarah Powers, Marcia Hilton, Rajendra Rambharos, Steve Poole
    Abstract:

    Abstract The need for greater performance in high performance Computing Systems combined with rising costs of electricity to power these Systems motivates the need for energy-efficient resource management. Driven by the requirements of the Extreme Scale Systems Center at Oak Ridge National Laboratory, we address the problem of scheduling dynamically-arriving tasks to machines in an oversubscribed and energy-constrained Heterogeneous distributed Computing environment. Our goal is to maximize total “utility” earned by the System, where the utility of a task is defined by a monotonically-decreasing function that represents the value of completing that task at different times. To address this problem, we design four energy-aware resource allocation heuristics and compare their performance to heuristics from the literature. For our given energy-constrained environment, we also design an energy filtering technique that helps some heuristics regulate their energy consumption by allowing tasks to only consume up to an estimated fair-share of energy. Extensive sensitivity analyses of the heuristics in environments with different levels of heterogeneity show that heuristics with the ability to balance both energy consumption and utility exhibit the best performance because they save energy for use by future tasks.

  • Time utility functions for modeling and evaluating resource allocations in a Heterogeneous Computing System
    IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum, 2011
    Co-Authors: Luis D. Briceño, Bhavesh Khemka, Christopher Groër, Gregory Koenig, Gene Okonski, H.j. Siegel, Anthony A. Maciejewski, Steve Poole
    Abstract:

    This study considers a Heterogeneous Computing System and corresponding workload being investigated by the Extreme Scale Systems Center (ESSC) at Oak Ridge National Laboratory (ORNL). The ESSC is part of a collaborative effort between the Department of Energy (DOE) and the Department of Defense (DoD) to deliver research, tools, software, and technologies that can be integrated, deployed, and used in both DOE and DoD environments. The Heterogeneous System and workload described here are representative of a prototypical Computing environment being studied as part of this collaboration. Each task can exhibit a time-varying emph{importance} or emph{utility} to the overall enterprise. In this System, an arriving task has an associated priority and precedence. The priority is used to describe the importance of a task, and precedence is used to describe how soon the task must be executed. These two metrics are combined to create a utility function curve that indicates how valuable it is for the System to complete a task at any given moment. This research focuses on using time-utility functions to generate a metric that can be used to compare the performance of different resource schedulers in a Heterogeneous Computing System. The contributions of this paper are: (a) a mathematical model of a Heterogeneous Computing System where tasks arrive dynamically and need to be assigned based on their priority, precedence, utility characteristic class, and task execution type, (b) the use of priority and precedence to generate time-utility functions that describe the value a task has at any given time, (c) the derivation of a metric based on the total utility gained from completing tasks to measure the performance of the Computing environment, and (d) a comparison of the performance of resource allocation heuristics in this environment

Bhavesh Khemka - One of the best experts on this subject based on the ideXlab platform.

  • makespan and energy robust stochastic static resource allocation of a bag of tasks to a Heterogeneous Computing System
    IEEE Transactions on Parallel and Distributed Systems, 2015
    Co-Authors: Mark A Oxley, Luis D. Briceño, H.j. Siegel, Anthony A. Maciejewski, Jonathan Apodaca, Jay Smith, Sudeep Pasricha, Dalton Young, Shirish Bahirat, Bhavesh Khemka
    Abstract:

    Today’s data centers face the issue of balancing electricity use and completion times of their workloads. Rising electricity costs are forcing data center operators to either operate within an electricity budget or to reduce electricity use as much as possible while still maintaining service agreements. Energy-aware resource allocation is one technique a System administrator can employ to address both problems: optimizing the workload completion time (makespan) when given an energy budget, or to minimize energy consumption subject to service guarantees (such as adhering to deadlines). In this paper, we study the problem of energy-aware static resource allocation in an environment where a collection of independent (non-communicating) tasks (“bag-of-tasks”) is assigned to a Heterogeneous Computing System. Computing Systems often operate in environments where task execution times vary (e.g., due to cache misses or data dependent execution times). We model these execution times stochastically, using probability density functions. We want our resource allocations to be robust against these variations, where we define energy-robustness as the probability that the energy budget is not violated, and makespan-robustness as the probability a makespan deadline is not violated. We develop and analyze several heuristics for energy-aware resource allocation for both energy-constrained and deadline-constrained problems.

  • utility maximizing dynamic resource management in an oversubscribed energy constrained Heterogeneous Computing System
    Sustainable Computing: Informatics and Systems, 2015
    Co-Authors: Bhavesh Khemka, H.j. Siegel, Anthony A. Maciejewski, Gregory A. Koenig, Sudeep Pasricha, Ryan Friese, Sarah Powers, Marcia Hilton, Rajendra Rambharos, Steve Poole
    Abstract:

    Abstract The need for greater performance in high performance Computing Systems combined with rising costs of electricity to power these Systems motivates the need for energy-efficient resource management. Driven by the requirements of the Extreme Scale Systems Center at Oak Ridge National Laboratory, we address the problem of scheduling dynamically-arriving tasks to machines in an oversubscribed and energy-constrained Heterogeneous distributed Computing environment. Our goal is to maximize total “utility” earned by the System, where the utility of a task is defined by a monotonically-decreasing function that represents the value of completing that task at different times. To address this problem, we design four energy-aware resource allocation heuristics and compare their performance to heuristics from the literature. For our given energy-constrained environment, we also design an energy filtering technique that helps some heuristics regulate their energy consumption by allowing tasks to only consume up to an estimated fair-share of energy. Extensive sensitivity analyses of the heuristics in environments with different levels of heterogeneity show that heuristics with the ability to balance both energy consumption and utility exhibit the best performance because they save energy for use by future tasks.

  • Time utility functions for modeling and evaluating resource allocations in a Heterogeneous Computing System
    IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum, 2011
    Co-Authors: Luis D. Briceño, Bhavesh Khemka, Christopher Groër, Gregory Koenig, Gene Okonski, H.j. Siegel, Anthony A. Maciejewski, Steve Poole
    Abstract:

    This study considers a Heterogeneous Computing System and corresponding workload being investigated by the Extreme Scale Systems Center (ESSC) at Oak Ridge National Laboratory (ORNL). The ESSC is part of a collaborative effort between the Department of Energy (DOE) and the Department of Defense (DoD) to deliver research, tools, software, and technologies that can be integrated, deployed, and used in both DOE and DoD environments. The Heterogeneous System and workload described here are representative of a prototypical Computing environment being studied as part of this collaboration. Each task can exhibit a time-varying emph{importance} or emph{utility} to the overall enterprise. In this System, an arriving task has an associated priority and precedence. The priority is used to describe the importance of a task, and precedence is used to describe how soon the task must be executed. These two metrics are combined to create a utility function curve that indicates how valuable it is for the System to complete a task at any given moment. This research focuses on using time-utility functions to generate a metric that can be used to compare the performance of different resource schedulers in a Heterogeneous Computing System. The contributions of this paper are: (a) a mathematical model of a Heterogeneous Computing System where tasks arrive dynamically and need to be assigned based on their priority, precedence, utility characteristic class, and task execution type, (b) the use of priority and precedence to generate time-utility functions that describe the value a task has at any given time, (c) the derivation of a metric based on the total utility gained from completing tasks to measure the performance of the Computing environment, and (d) a comparison of the performance of resource allocation heuristics in this environment

  • IPDPS Workshops - Time Utility Functions for Modeling and Evaluating Resource Allocations in a Heterogeneous Computing System
    2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum, 2011
    Co-Authors: Luis D. Briceño, Bhavesh Khemka, Christopher Groër, Gene Okonski, H.j. Siegel, Anthony A. Maciejewski, Gregory A. Koenig, Steve Poole
    Abstract:

    This study considers a Heterogeneous Computing System and corresponding workload being investigated by the Extreme Scale Systems Center (ESSC) at Oak Ridge National Laboratory (ORNL). The ESSC is part of a collaborative effort between the Department of Energy (DOE) and the Department of Defense (DoD) to deliver research, tools, software, and technologies that can be integrated, deployed, and used in both DOE and DoD environments. The Heterogeneous System and workload described here are representative of a prototypical Computing environment being studied as part of this collaboration. Each task can exhibit a time-varying emph{importance} or emph{utility} to the overall enterprise. In this System, an arriving task has an associated priority and precedence. The priority is used to describe the importance of a task, and precedence is used to describe how soon the task must be executed. These two metrics are combined to create a utility function curve that indicates how valuable it is for the System to complete a task at any given moment. This research focuses on using time-utility functions to generate a metric that can be used to compare the performance of different resource schedulers in a Heterogeneous Computing System. The contributions of this paper are: (a) a mathematical model of a Heterogeneous Computing System where tasks arrive dynamically and need to be assigned based on their priority, precedence, utility characteristic class, and task execution type, (b) the use of priority and precedence to generate time-utility functions that describe the value a task has at any given time, (c) the derivation of a metric based on the total utility gained from completing tasks to measure the performance of the Computing environment, and (d) a comparison of the performance of resource allocation heuristics in this environment

E. Ilavarasan - One of the best experts on this subject based on the ideXlab platform.

  • Genetic Algorithm for Task Scheduling on Distributed Heterogeneous Computing System
    International Journal of Engineering, 2015
    Co-Authors: E. Ilavarasan, P. Thambidurai
    Abstract:

    Distributed Heterogeneous Computing System are increasingly being employed for critical applications, such as aircraft control, industrial process control, and banking Systems. Efficient application scheduling is a key issue for achieving high performance in this System. The problem is generally addressed in terms of task scheduling, where the tasks are the schedulable units of a program. The task scheduling problem has been extensively studied and a large number of scheduling heuristics have been presented in the literature. In this paper we propose a new task-scheduling algorithm namely, Genetic Algorithm for Task Scheduling (GATS) on Heterogeneous Computing System, which provides optimal results for applications represented by directed acyclic graph. The performance of the algorithm is illustrated by comparing the schedule length, speedup, and efficiency with existing algorithms such as CPOP, HEFT and PSGA. The comparison study based on randomly generated graphs and graphs of three real world applications such as Gaussian Elimination Algorithm, Fast Fourier Transformation, and Gauss Jordan algorithm shows that GATS algorithm substantially outperforms existing algorithms.

  • high performance task scheduling algorithm for Heterogeneous Computing System
    International Conference on Algorithms and Architectures for Parallel Processing, 2005
    Co-Authors: E. Ilavarasan, P. Thambidurai, R. Mahilmannan
    Abstract:

    A key issue in obtaining high performance from a parallel program represented by a Directed A-cyclic Graph (DAG) is to efficiently mapping it into the target System. The problem is generally addressed in terms of task scheduling, where the tasks are the schedulable units of a program. The task scheduling problems have been shown to be NP-complete in general as well as several restricted cases. In order to be of practical use for large applications, scheduling algorithms must guarantee high performance by minimizing the schedule length and scheduling time. In this paper we propose a new task-scheduling algorithm namely, High Performance task Scheduling (HPS) algorithm for Heterogeneous Computing System with complexity O (v + e) (p+ log v), which provides optimal results for applications represented by DAGs. The performance of the algorithm is illustrated by comparing the schedule length, speedup, efficiency and the scheduling time with existing algorithms reported in this paper. The comparison study based on both randomly generated graphs and graphs of some real applications shows that HPS algorithm substantially outperforms existing algorithms.

  • ICA3PP - High performance task scheduling algorithm for Heterogeneous Computing System
    Distributed and Parallel Computing, 2005
    Co-Authors: E. Ilavarasan, P. Thambidurai, R. Mahilmannan
    Abstract:

    A key issue in obtaining high performance from a parallel program represented by a Directed A-cyclic Graph (DAG) is to efficiently mapping it into the target System. The problem is generally addressed in terms of task scheduling, where the tasks are the schedulable units of a program. The task scheduling problems have been shown to be NP-complete in general as well as several restricted cases. In order to be of practical use for large applications, scheduling algorithms must guarantee high performance by minimizing the schedule length and scheduling time. In this paper we propose a new task-scheduling algorithm namely, High Performance task Scheduling (HPS) algorithm for Heterogeneous Computing System with complexity O (v + e) (p+ log v), which provides optimal results for applications represented by DAGs. The performance of the algorithm is illustrated by comparing the schedule length, speedup, efficiency and the scheduling time with existing algorithms reported in this paper. The comparison study based on both randomly generated graphs and graphs of some real applications shows that HPS algorithm substantially outperforms existing algorithms.

  • DFMA - Levelized scheduling of directed a-cyclic precedence constrained task graphs onto Heterogeneous Computing System
    First International Conference on Distributed Frameworks for Multimedia Applications, 1
    Co-Authors: E. Ilavarasan, P. Thambidurai
    Abstract:

    Efficient scheduling of processes onto processors of a Heterogeneous Computing System has always been an important and challenging area of research. The scheduling problem has been shown to be NP-complete in general cases as well as in several restricted cases. Because of its key importance, this problem has been extensively studied in the recent years and many algorithms for homogenous System and a few algorithms for Heterogeneous System have been proposed in the literature. In this paper, we propose a new duplication based task scheduling algorithm, namely, levelized heavily communicating node first (LHCNF) that statically schedules directed a-cyclic precedence constrained task graphs (DAGs) onto Heterogeneous Computing System to minimize the schedule length or overall completion time of the application. The performance of the algorithm has been observed by its application to some practical DAGs, and by comparing it with other existing scheduling algorithms such as HEFT, LDBS1 and LDBS2 in terms of the schedule length and speedup. The comparison studies shows that LHCNF significantly outperforms HEFT, LDBS1 and LDBS2 in schedule length, speedup.

  • ISPDC - Performance Effective Task Scheduling Algorithm for Heterogeneous Computing System
    The 4th International Symposium on Parallel and Distributed Computing (ISPDC'05), 1
    Co-Authors: E. Ilavarasan, P. Thambidurai, R. Mahilmannan
    Abstract:

    Finding an optimal solution to the problem of scheduling an application modeled by a directed acyclic graph (DAG) onto a distributed System is known to be NP-complete. The complexity of the problem increases when task scheduling is to be done in a Heterogeneous Computing System, where the processors in the network may not be identical and take different amounts of time to execute the same task. This paper introduces a performance effective task scheduling (PETS) algorithm for network of Heterogeneous System, with complexity O(v+e) (p+log v), which provides optimal results for applications represented by DAGs. The performance of the algorithm is illustrated by comparing the schedule length, speedup, efficiency and the scheduling time with existing algorithms such as, Heterogeneous earliest finish time (HEFT) and critical-path on a processor (CPOP) and levelized min time (LMT) reported in this paper. The comparison study based on both randomly generated graphs and graphs of some real applications shows that PETS algorithm substantially outperforms existing algorithms

Luis D. Briceño - One of the best experts on this subject based on the ideXlab platform.

  • stochastic based robust dynamic resource allocation for independent tasks in a Heterogeneous Computing System
    Journal of Parallel and Distributed Computing, 2016
    Co-Authors: Mohsen Amini Salehi, Luis D. Briceño, H.j. Siegel, Anthony A. Maciejewski, Jonathan Apodaca, Jay Smith, Edwin K P Chong, Timothy Renner, Vladimir Shestak, Joshua Ladd
    Abstract:

    Heterogeneous parallel and distributed Computing Systems frequently must operate in environments where there is uncertainty in System parameters. Robustness can be defined as the degree to which a System can function correctly in the presence of parameter values different from those assumed. In such an environment, the execution time of any given task may fluctuate substantially due to factors such as the content of data to be processed. Determining a resource allocation that is robust against this uncertainty is an important area of research. In this study, we define a stochastic robustness measure to facilitate resource allocation decisions in a dynamic environment where tasks are subject to individual hard deadlines and each task requires some input data to start execution. In this environment, the tasks that cannot meet their deadlines are dropped (i.e., discarded). We define methods to determine the stochastic completion times of tasks in the presence of the task dropping. The stochastic task completion time is used in the definition of the stochastic robustness measure. Based on this stochastic robustness measure, we design novel resource allocation techniques that work in immediate and batch modes, with the goal of maximizing the number of tasks that meet their individual deadlines. We compare the performance of our technique against several well-known approaches taken from the literature and adapted to our environment. Simulation results of this study demonstrate the suitability of our new technique in a dynamic Heterogeneous Computing System. Calculating stochastic task completion time in Heterogeneous System with task dropping.A model to quantify resource allocation robustness and propose mapping heuristics.Evaluating immediate and batch mappings and optimizing queue-size limit of batch mode.Analyzing impact of over-subscription level on immediate and batch allocation modes.Providing a model in the batch mode to run mapping events before machines become idle.

  • makespan and energy robust stochastic static resource allocation of a bag of tasks to a Heterogeneous Computing System
    IEEE Transactions on Parallel and Distributed Systems, 2015
    Co-Authors: Mark A Oxley, Luis D. Briceño, H.j. Siegel, Anthony A. Maciejewski, Jonathan Apodaca, Jay Smith, Sudeep Pasricha, Dalton Young, Shirish Bahirat, Bhavesh Khemka
    Abstract:

    Today’s data centers face the issue of balancing electricity use and completion times of their workloads. Rising electricity costs are forcing data center operators to either operate within an electricity budget or to reduce electricity use as much as possible while still maintaining service agreements. Energy-aware resource allocation is one technique a System administrator can employ to address both problems: optimizing the workload completion time (makespan) when given an energy budget, or to minimize energy consumption subject to service guarantees (such as adhering to deadlines). In this paper, we study the problem of energy-aware static resource allocation in an environment where a collection of independent (non-communicating) tasks (“bag-of-tasks”) is assigned to a Heterogeneous Computing System. Computing Systems often operate in environments where task execution times vary (e.g., due to cache misses or data dependent execution times). We model these execution times stochastically, using probability density functions. We want our resource allocations to be robust against these variations, where we define energy-robustness as the probability that the energy budget is not violated, and makespan-robustness as the probability a makespan deadline is not violated. We develop and analyze several heuristics for energy-aware resource allocation for both energy-constrained and deadline-constrained problems.

  • Time utility functions for modeling and evaluating resource allocations in a Heterogeneous Computing System
    IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum, 2011
    Co-Authors: Luis D. Briceño, Bhavesh Khemka, Christopher Groër, Gregory Koenig, Gene Okonski, H.j. Siegel, Anthony A. Maciejewski, Steve Poole
    Abstract:

    This study considers a Heterogeneous Computing System and corresponding workload being investigated by the Extreme Scale Systems Center (ESSC) at Oak Ridge National Laboratory (ORNL). The ESSC is part of a collaborative effort between the Department of Energy (DOE) and the Department of Defense (DoD) to deliver research, tools, software, and technologies that can be integrated, deployed, and used in both DOE and DoD environments. The Heterogeneous System and workload described here are representative of a prototypical Computing environment being studied as part of this collaboration. Each task can exhibit a time-varying emph{importance} or emph{utility} to the overall enterprise. In this System, an arriving task has an associated priority and precedence. The priority is used to describe the importance of a task, and precedence is used to describe how soon the task must be executed. These two metrics are combined to create a utility function curve that indicates how valuable it is for the System to complete a task at any given moment. This research focuses on using time-utility functions to generate a metric that can be used to compare the performance of different resource schedulers in a Heterogeneous Computing System. The contributions of this paper are: (a) a mathematical model of a Heterogeneous Computing System where tasks arrive dynamically and need to be assigned based on their priority, precedence, utility characteristic class, and task execution type, (b) the use of priority and precedence to generate time-utility functions that describe the value a task has at any given time, (c) the derivation of a metric based on the total utility gained from completing tasks to measure the performance of the Computing environment, and (d) a comparison of the performance of resource allocation heuristics in this environment

  • IPDPS Workshops - Time Utility Functions for Modeling and Evaluating Resource Allocations in a Heterogeneous Computing System
    2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum, 2011
    Co-Authors: Luis D. Briceño, Bhavesh Khemka, Christopher Groër, Gene Okonski, H.j. Siegel, Anthony A. Maciejewski, Gregory A. Koenig, Steve Poole
    Abstract:

    This study considers a Heterogeneous Computing System and corresponding workload being investigated by the Extreme Scale Systems Center (ESSC) at Oak Ridge National Laboratory (ORNL). The ESSC is part of a collaborative effort between the Department of Energy (DOE) and the Department of Defense (DoD) to deliver research, tools, software, and technologies that can be integrated, deployed, and used in both DOE and DoD environments. The Heterogeneous System and workload described here are representative of a prototypical Computing environment being studied as part of this collaboration. Each task can exhibit a time-varying emph{importance} or emph{utility} to the overall enterprise. In this System, an arriving task has an associated priority and precedence. The priority is used to describe the importance of a task, and precedence is used to describe how soon the task must be executed. These two metrics are combined to create a utility function curve that indicates how valuable it is for the System to complete a task at any given moment. This research focuses on using time-utility functions to generate a metric that can be used to compare the performance of different resource schedulers in a Heterogeneous Computing System. The contributions of this paper are: (a) a mathematical model of a Heterogeneous Computing System where tasks arrive dynamically and need to be assigned based on their priority, precedence, utility characteristic class, and task execution type, (b) the use of priority and precedence to generate time-utility functions that describe the value a task has at any given time, (c) the derivation of a metric based on the total utility gained from completing tasks to measure the performance of the Computing environment, and (d) a comparison of the performance of resource allocation heuristics in this environment