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

Howard Jay Siegel - One of the best experts on this subject based on the ideXlab platform.

  • multi objective robust Static Mapping of independent tasks on grids
    Congress on Evolutionary Computation, 2010
    Co-Authors: Bernabe Dorronsoro, Anthony A Maciejewski, Pascal Bouvry, Alberto J Canero, Howard Jay Siegel
    Abstract:

    We study the problem of efficiently allocating incoming independent tasks onto the resources of a Grid system. Typically, it is assumed that the estimated time to compute each task on every machine is known. We are making the same assumption in this work, but we allow the existence of inaccuracies in these values. Our schedule will be robust versus such inaccuracies, ensuring that even when the estimated time to compute all the tasks is increased by a given percentage, the makespan of the schedule (i.e., the time when the last machine finishes its tasks) will not grow behind that percentage. We propose a new multi-objective definition of the problem, optimizing at the same time the makespan of the schedule and its robustness. Four well-known multi-objective evolutionary algorithms are used to find competitive results to the new problem. Finally, a new population initialization method for scheduling problems is proposed, leading to more efficient and accurate algorithms.

  • dynamically Mapping tasks with priorities and multiple deadlines in a heterogeneous environment
    Journal of Parallel and Distributed Computing, 2007
    Co-Authors: S Shivle, Howard Jay Siegel, Anthony A Maciejewski, Tracy D Braun, M Schneider, S Tideman, R Chitta, Raheleh B Dilmaghani, R Joshi, Aditya Kaul
    Abstract:

    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.

  • Static Mapping of subtasks in a heterogeneous ad hoc grid environment
    International Parallel and Distributed Processing Symposium, 2004
    Co-Authors: S Shivle, Howard Jay Siegel, Anthony A Maciejewski, R Castain, Tarun Banka, K Chindam, S Dussinger, Prakash Pichumani, Praveen Satyasekaran, William Saylor
    Abstract:

    Summary form only given. An ad hoc grid is a heterogeneous computing and communication system without a fixed infrastructure; all of its components are mobile. Energy management is a major concern in an ad hoc grid. One important aspect of energy management is to minimize the energy consumption during a mission. In an ad hoc grid, communication and computations are deeply intertwined, and any energy optimization must consider both types of activities together rather than separately. The Mapping (defined as matching and scheduling) of tasks onto machines with varied computational capabilities has been shown, in general, to be an NP-complete problem. Therefore, heuristic techniques are required to efficiently map tasks to machines in an ad hoc grid so as to minimize the energy consumed due to communication and computation. This research evaluates and compares energy management issues for resource allocation in ad hoc grids using six Static heuristics.

  • Static Mapping of subtasks in a heterogeneous ad hoc grid environment
    International Parallel and Distributed Processing Symposium, 2004
    Co-Authors: S Shivle, Howard Jay Siegel, Anthony A Maciejewski, R Castain, Tarun Banka, K Chindam, S Dussinger, Prakash Pichumani, Praveen Satyasekaran, William Saylor
    Abstract:

    Summary form only given. An ad hoc grid is a heterogeneous computing and communication system without a fixed infrastructure; all of its components are mobile. Energy management is a major concern in an ad hoc grid. One important aspect of energy management is to minimize the energy consumption during a mission. In an ad hoc grid, communication and computations are deeply intertwined, and any energy optimization must consider both types of activities together rather than separately. The Mapping (defined as matching and scheduling) of tasks onto machines with varied computational capabilities has been shown, in general, to be an NP-complete problem. Therefore, heuristic techniques are required to efficiently map tasks to machines in an ad hoc grid so as to minimize the energy consumed due to communication and computation. This research evaluates and compares energy management issues for resource allocation in ad hoc grids using six Static heuristics.

  • Static Mapping heuristics for tasks with dependencies priorities deadlines and multiple versions in heterogeneous environments
    International Parallel and Distributed Processing Symposium, 2002
    Co-Authors: Tracy D Braun, Howard Jay Siegel, Anthony A Maciejewski
    Abstract:

    Heterogeneous computing (HC) environments composed of interconnected machines with varied computational capabilities are well suited to meet the computational demands of large, diverse groups of tasks. The problem, of Mapping (defined as matching and scheduling) these tasks onto the machines of a distributed HC environment. has been shown, in general, to be NP-complete. Therefore; the development of heuristic techniques to find near-optimal solutions is required. In the HC environment investigated, tasks had deadlines, priorities, multiple versions, and may be composed of communicating subtasks. The best Static (off-line) techniques from some previous studies were adapted and applied to this Mapping problem: a genetic algorithm (GA), a GENITOR-style algorithm., and a greedy Min-min technique. Simulation studies compared the performance of these heuristics in several overloaded scenarios, i.e., not all tasks executed. The performance measure used was a sum of weighted priorities of tasks that completed before their deadline, adjusted based on the version of the task used. It is shown that for the cases studied here, the GENITOR technique found the best results, but the faster Min-min approach also performed very well.

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

  • multi objective robust Static Mapping of independent tasks on grids
    Congress on Evolutionary Computation, 2010
    Co-Authors: Bernabe Dorronsoro, Anthony A Maciejewski, Pascal Bouvry, Alberto J Canero, Howard Jay Siegel
    Abstract:

    We study the problem of efficiently allocating incoming independent tasks onto the resources of a Grid system. Typically, it is assumed that the estimated time to compute each task on every machine is known. We are making the same assumption in this work, but we allow the existence of inaccuracies in these values. Our schedule will be robust versus such inaccuracies, ensuring that even when the estimated time to compute all the tasks is increased by a given percentage, the makespan of the schedule (i.e., the time when the last machine finishes its tasks) will not grow behind that percentage. We propose a new multi-objective definition of the problem, optimizing at the same time the makespan of the schedule and its robustness. Four well-known multi-objective evolutionary algorithms are used to find competitive results to the new problem. Finally, a new population initialization method for scheduling problems is proposed, leading to more efficient and accurate algorithms.

  • dynamically Mapping tasks with priorities and multiple deadlines in a heterogeneous environment
    Journal of Parallel and Distributed Computing, 2007
    Co-Authors: S Shivle, Howard Jay Siegel, Anthony A Maciejewski, Tracy D Braun, M Schneider, S Tideman, R Chitta, Raheleh B Dilmaghani, R Joshi, Aditya Kaul
    Abstract:

    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.

  • Static Mapping of subtasks in a heterogeneous ad hoc grid environment
    International Parallel and Distributed Processing Symposium, 2004
    Co-Authors: S Shivle, Howard Jay Siegel, Anthony A Maciejewski, R Castain, Tarun Banka, K Chindam, S Dussinger, Prakash Pichumani, Praveen Satyasekaran, William Saylor
    Abstract:

    Summary form only given. An ad hoc grid is a heterogeneous computing and communication system without a fixed infrastructure; all of its components are mobile. Energy management is a major concern in an ad hoc grid. One important aspect of energy management is to minimize the energy consumption during a mission. In an ad hoc grid, communication and computations are deeply intertwined, and any energy optimization must consider both types of activities together rather than separately. The Mapping (defined as matching and scheduling) of tasks onto machines with varied computational capabilities has been shown, in general, to be an NP-complete problem. Therefore, heuristic techniques are required to efficiently map tasks to machines in an ad hoc grid so as to minimize the energy consumed due to communication and computation. This research evaluates and compares energy management issues for resource allocation in ad hoc grids using six Static heuristics.

  • Static Mapping of subtasks in a heterogeneous ad hoc grid environment
    International Parallel and Distributed Processing Symposium, 2004
    Co-Authors: S Shivle, Howard Jay Siegel, Anthony A Maciejewski, R Castain, Tarun Banka, K Chindam, S Dussinger, Prakash Pichumani, Praveen Satyasekaran, William Saylor
    Abstract:

    Summary form only given. An ad hoc grid is a heterogeneous computing and communication system without a fixed infrastructure; all of its components are mobile. Energy management is a major concern in an ad hoc grid. One important aspect of energy management is to minimize the energy consumption during a mission. In an ad hoc grid, communication and computations are deeply intertwined, and any energy optimization must consider both types of activities together rather than separately. The Mapping (defined as matching and scheduling) of tasks onto machines with varied computational capabilities has been shown, in general, to be an NP-complete problem. Therefore, heuristic techniques are required to efficiently map tasks to machines in an ad hoc grid so as to minimize the energy consumed due to communication and computation. This research evaluates and compares energy management issues for resource allocation in ad hoc grids using six Static heuristics.

  • Static Mapping heuristics for tasks with dependencies priorities deadlines and multiple versions in heterogeneous environments
    International Parallel and Distributed Processing Symposium, 2002
    Co-Authors: Tracy D Braun, Howard Jay Siegel, Anthony A Maciejewski
    Abstract:

    Heterogeneous computing (HC) environments composed of interconnected machines with varied computational capabilities are well suited to meet the computational demands of large, diverse groups of tasks. The problem, of Mapping (defined as matching and scheduling) these tasks onto the machines of a distributed HC environment. has been shown, in general, to be NP-complete. Therefore; the development of heuristic techniques to find near-optimal solutions is required. In the HC environment investigated, tasks had deadlines, priorities, multiple versions, and may be composed of communicating subtasks. The best Static (off-line) techniques from some previous studies were adapted and applied to this Mapping problem: a genetic algorithm (GA), a GENITOR-style algorithm., and a greedy Min-min technique. Simulation studies compared the performance of these heuristics in several overloaded scenarios, i.e., not all tasks executed. The performance measure used was a sum of weighted priorities of tasks that completed before their deadline, adjusted based on the version of the task used. It is shown that for the cases studied here, the GENITOR technique found the best results, but the faster Min-min approach also performed very well.

William Saylor - One of the best experts on this subject based on the ideXlab platform.

  • Static Mapping of subtasks in a heterogeneous ad hoc grid environment
    International Parallel and Distributed Processing Symposium, 2004
    Co-Authors: S Shivle, Howard Jay Siegel, Anthony A Maciejewski, R Castain, Tarun Banka, K Chindam, S Dussinger, Prakash Pichumani, Praveen Satyasekaran, William Saylor
    Abstract:

    Summary form only given. An ad hoc grid is a heterogeneous computing and communication system without a fixed infrastructure; all of its components are mobile. Energy management is a major concern in an ad hoc grid. One important aspect of energy management is to minimize the energy consumption during a mission. In an ad hoc grid, communication and computations are deeply intertwined, and any energy optimization must consider both types of activities together rather than separately. The Mapping (defined as matching and scheduling) of tasks onto machines with varied computational capabilities has been shown, in general, to be an NP-complete problem. Therefore, heuristic techniques are required to efficiently map tasks to machines in an ad hoc grid so as to minimize the energy consumed due to communication and computation. This research evaluates and compares energy management issues for resource allocation in ad hoc grids using six Static heuristics.

  • Static Mapping of subtasks in a heterogeneous ad hoc grid environment
    International Parallel and Distributed Processing Symposium, 2004
    Co-Authors: S Shivle, Howard Jay Siegel, Anthony A Maciejewski, R Castain, Tarun Banka, K Chindam, S Dussinger, Prakash Pichumani, Praveen Satyasekaran, William Saylor
    Abstract:

    Summary form only given. An ad hoc grid is a heterogeneous computing and communication system without a fixed infrastructure; all of its components are mobile. Energy management is a major concern in an ad hoc grid. One important aspect of energy management is to minimize the energy consumption during a mission. In an ad hoc grid, communication and computations are deeply intertwined, and any energy optimization must consider both types of activities together rather than separately. The Mapping (defined as matching and scheduling) of tasks onto machines with varied computational capabilities has been shown, in general, to be an NP-complete problem. Therefore, heuristic techniques are required to efficiently map tasks to machines in an ad hoc grid so as to minimize the energy consumed due to communication and computation. This research evaluates and compares energy management issues for resource allocation in ad hoc grids using six Static heuristics.

S Shivle - One of the best experts on this subject based on the ideXlab platform.

  • dynamically Mapping tasks with priorities and multiple deadlines in a heterogeneous environment
    Journal of Parallel and Distributed Computing, 2007
    Co-Authors: S Shivle, Howard Jay Siegel, Anthony A Maciejewski, Tracy D Braun, M Schneider, S Tideman, R Chitta, Raheleh B Dilmaghani, R Joshi, Aditya Kaul
    Abstract:

    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.

  • Static Mapping of subtasks in a heterogeneous ad hoc grid environment
    International Parallel and Distributed Processing Symposium, 2004
    Co-Authors: S Shivle, Howard Jay Siegel, Anthony A Maciejewski, R Castain, Tarun Banka, K Chindam, S Dussinger, Prakash Pichumani, Praveen Satyasekaran, William Saylor
    Abstract:

    Summary form only given. An ad hoc grid is a heterogeneous computing and communication system without a fixed infrastructure; all of its components are mobile. Energy management is a major concern in an ad hoc grid. One important aspect of energy management is to minimize the energy consumption during a mission. In an ad hoc grid, communication and computations are deeply intertwined, and any energy optimization must consider both types of activities together rather than separately. The Mapping (defined as matching and scheduling) of tasks onto machines with varied computational capabilities has been shown, in general, to be an NP-complete problem. Therefore, heuristic techniques are required to efficiently map tasks to machines in an ad hoc grid so as to minimize the energy consumed due to communication and computation. This research evaluates and compares energy management issues for resource allocation in ad hoc grids using six Static heuristics.

  • Static Mapping of subtasks in a heterogeneous ad hoc grid environment
    International Parallel and Distributed Processing Symposium, 2004
    Co-Authors: S Shivle, Howard Jay Siegel, Anthony A Maciejewski, R Castain, Tarun Banka, K Chindam, S Dussinger, Prakash Pichumani, Praveen Satyasekaran, William Saylor
    Abstract:

    Summary form only given. An ad hoc grid is a heterogeneous computing and communication system without a fixed infrastructure; all of its components are mobile. Energy management is a major concern in an ad hoc grid. One important aspect of energy management is to minimize the energy consumption during a mission. In an ad hoc grid, communication and computations are deeply intertwined, and any energy optimization must consider both types of activities together rather than separately. The Mapping (defined as matching and scheduling) of tasks onto machines with varied computational capabilities has been shown, in general, to be an NP-complete problem. Therefore, heuristic techniques are required to efficiently map tasks to machines in an ad hoc grid so as to minimize the energy consumed due to communication and computation. This research evaluates and compares energy management issues for resource allocation in ad hoc grids using six Static heuristics.

Fernando Moraes - One of the best experts on this subject based on the ideXlab platform.

  • evaluation of Static and dynamic task Mapping algorithms in noc based mpsocs
    International Symposium on System-on-Chip, 2009
    Co-Authors: Ewerson Carvalho, Cesar Marcon, Ney Calazans, Fernando Moraes
    Abstract:

    Task Mapping is an important issue in MPSoC design. Most recent Mapping algorithms perform them at design time, an approach known as Static Mapping. Nonetheless, applications running in MPSoCs may execute a varying number of simultaneous tasks. In some cases, applications may be defined only after system design, enforcing a scenario that requires the use of dynamic task Mapping. Static Mappings have as main advantage the global view of the system, while dynamic Mappings normally provide a local view, which considers only the neighborhood of the Mapping task. This work aims to evaluate the pros and cons of Static and dynamic Mapping solutions. Due to the global system view, it is expected that Static Mapping algorithms achieve superior performance (w.r.t. latency, congestion, energy consumption). As dynamic scenarios are a trend in present MPSoC designs, the cost of dynamic Mapping algorithms must be known, and directions to improve the quality of such algorithms should be provided without increasing execution time. This quantitative comparison between Static and dynamic Mapping algorithms is the main contribution of this work.

  • heuristics for dynamic task Mapping in noc based heterogeneous mpsocs
    Rapid System Prototyping, 2007
    Co-Authors: Ewerson Carvalho, Ney Calazans, Fernando Moraes
    Abstract:

    Multiprocessor Systems-on-Chip (MPSoCs) is a trend in VLSI design, since they minimize the "design crisis " (gap between silicon technology and actual SoC design capacity) and reduce the time to market. Important issues in MPSoC design are the communication infrastructure and task Mapping. MPSoCs may employ NoCs to integrate multiple programmable processor cores, specialized memories, and other IPs in a scalable way. Applications running in MPSoCs execute a varying number of tasks simultaneously, and their number may exceed the available resources, requiring task Mapping to be executed at runtime to meet real-time constraints. Most works in the literature present Static MPSoC Mapping solutions. Static Mapping defines a fixed placement and scheduling, not appropriate for dynamic workloads. Task migration has also been proposed for use in MPSoCs, with the goal to relocate tasks when performance bottlenecks are identified. This work investigates the performance of Mapping heuristics in NoC-based MPSoCs with dynamic workloads, targeting NoC congestion minimization, a key cost function to optimize the NoC performance. Here, tasks are mapped on the fly, according to communication requests and the load in the NoC links. Results show execution time and congestion reduction when congestion-aware Mapping heuristics are employed.