View in EDS

ERPOT: A Quad-Criteria Scheduling Heuristic to Optimize Execution Time, Reliability, Power Consumption and Temperature in Multicores.

Saved in:
Bibliographic Details
Title: ERPOT: A Quad-Criteria Scheduling Heuristic to Optimize Execution Time, Reliability, Power Consumption and Temperature in Multicores.
Authors: Abdi, Athena1 (AUTHOR) atena_abdi@aut.ac.ir, Girault, Alain2 (AUTHOR) alain.girault@inria.fr, Zarandi, Hamid R.1 (AUTHOR) h_zarandi@aut.ac.ir
Source: IEEE Transactions on Parallel & Distributed Systems. Oct2019, Vol. 30 Issue 10, p2193-2210. 18p.
Subjects: Redundancy in engineering, Directed acyclic graphs, Temperature control, NP-complete problems, Acyclic model, Reliability in engineering
Abstract: We investigate multi-criteria optimization and Pareto front generation. Given an application modeled as a Directed Acyclic Graph (DAG) of tasks and a multicore architecture, we produce a set of non-dominated (in the Pareto sense) static schedules of this DAG onto this multicore. The criteria we address are the execution time, reliability, power consumption, and peak temperature. These criteria exhibit complex antagonistic relations, which make the problem challenging. For instance, improving the reliability requires adding some redundancy in the schedule, which penalizes the execution time. To produce Pareto fronts in this 4-dimension space, we transform three of the four criteria into constraints (the reliability, the power consumption, and the peak temperature), and we minimize the fourth one (the execution time of the schedule) under these three constraints. By varying the thresholds used for the three constraints, we are able to produce a Pareto front of non-dominated solutions. We propose two algorithms to compute static schedules. The first is a ready list scheduling heuristic called Execution time, Reliability, POwer consumption and Temperature (ERPOT). ERPOT actively replicates the tasks to increase the reliability, uses Dynamic Voltage and Frequency Scaling to decrease the power consumption, and inserts cooling times to control the peak temperature. The second algorithm uses an Integer Linear Programming (ILP) program to compute an optimal schedule. However, because our multi-criteria scheduling problem is NP-complete, the ILP algorithm is limited to very small problem instances. Comparisons showed that the schedules produced by ERPOT are on average only 10 percent worse than the optimal schedules computed by the ILP program, and that ERPOT outperforms the PowerPerf-PET heuristic from the literature on average by 33 percent. [ABSTRACT FROM AUTHOR]
Copyright of IEEE Transactions on Parallel & Distributed Systems is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 138593209
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: ERPOT: A Quad-Criteria Scheduling Heuristic to Optimize Execution Time, Reliability, Power Consumption and Temperature in Multicores.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Abdi%2C+Athena%22">Abdi, Athena</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> atena_abdi@aut.ac.ir</i><br /><searchLink fieldCode="AR" term="%22Girault%2C+Alain%22">Girault, Alain</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> alain.girault@inria.fr</i><br /><searchLink fieldCode="AR" term="%22Zarandi%2C+Hamid+R%2E%22">Zarandi, Hamid R.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> h_zarandi@aut.ac.ir</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22IEEE+Transactions+on+Parallel+%26+Distributed+Systems%22">IEEE Transactions on Parallel & Distributed Systems</searchLink>. Oct2019, Vol. 30 Issue 10, p2193-2210. 18p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Redundancy+in+engineering%22">Redundancy in engineering</searchLink><br /><searchLink fieldCode="DE" term="%22Directed+acyclic+graphs%22">Directed acyclic graphs</searchLink><br /><searchLink fieldCode="DE" term="%22Temperature+control%22">Temperature control</searchLink><br /><searchLink fieldCode="DE" term="%22NP-complete+problems%22">NP-complete problems</searchLink><br /><searchLink fieldCode="DE" term="%22Acyclic+model%22">Acyclic model</searchLink><br /><searchLink fieldCode="DE" term="%22Reliability+in+engineering%22">Reliability in engineering</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We investigate multi-criteria optimization and Pareto front generation. Given an application modeled as a Directed Acyclic Graph (DAG) of tasks and a multicore architecture, we produce a set of non-dominated (in the Pareto sense) static schedules of this DAG onto this multicore. The criteria we address are the execution time, reliability, power consumption, and peak temperature. These criteria exhibit complex antagonistic relations, which make the problem challenging. For instance, improving the reliability requires adding some redundancy in the schedule, which penalizes the execution time. To produce Pareto fronts in this 4-dimension space, we transform three of the four criteria into constraints (the reliability, the power consumption, and the peak temperature), and we minimize the fourth one (the execution time of the schedule) under these three constraints. By varying the thresholds used for the three constraints, we are able to produce a Pareto front of non-dominated solutions. We propose two algorithms to compute static schedules. The first is a ready list scheduling heuristic called Execution time, Reliability, POwer consumption and Temperature (ERPOT). ERPOT actively replicates the tasks to increase the reliability, uses Dynamic Voltage and Frequency Scaling to decrease the power consumption, and inserts cooling times to control the peak temperature. The second algorithm uses an Integer Linear Programming (ILP) program to compute an optimal schedule. However, because our multi-criteria scheduling problem is NP-complete, the ILP algorithm is limited to very small problem instances. Comparisons showed that the schedules produced by ERPOT are on average only 10 percent worse than the optimal schedules computed by the ILP program, and that ERPOT outperforms the PowerPerf-PET heuristic from the literature on average by 33 percent. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of IEEE Transactions on Parallel & Distributed Systems is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=138593209
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1109/TPDS.2019.2906172
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 18
        StartPage: 2193
    Subjects:
      – SubjectFull: Redundancy in engineering
        Type: general
      – SubjectFull: Directed acyclic graphs
        Type: general
      – SubjectFull: Temperature control
        Type: general
      – SubjectFull: NP-complete problems
        Type: general
      – SubjectFull: Acyclic model
        Type: general
      – SubjectFull: Reliability in engineering
        Type: general
    Titles:
      – TitleFull: ERPOT: A Quad-Criteria Scheduling Heuristic to Optimize Execution Time, Reliability, Power Consumption and Temperature in Multicores.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Abdi, Athena
      – PersonEntity:
          Name:
            NameFull: Girault, Alain
      – PersonEntity:
          Name:
            NameFull: Zarandi, Hamid R.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 10
              Text: Oct2019
              Type: published
              Y: 2019
          Identifiers:
            – Type: issn-print
              Value: 10459219
          Numbering:
            – Type: volume
              Value: 30
            – Type: issue
              Value: 10
          Titles:
            – TitleFull: IEEE Transactions on Parallel & Distributed Systems
              Type: main
ResultId 1