Skip to content

Latest commit

 

History

History
58 lines (36 loc) · 2.36 KB

MP-DVFS.md

File metadata and controls

58 lines (36 loc) · 2.36 KB
Raw

Multi-Core Processor (MP)

SMP-AM-2012-Germany_Albers-DVFS

Ref: S. Albers, F. Müller, S. Schmelzer, Speed scaling on parallel processors, Algorithmica 68 (2) (2014) 404–425.

  • proved the NP-hardness of the multi-core DVS problem when tasks could not migrate and gave several approximation algorithms for various special cases.

Model

Consider n jobs,

  • Job i is specified by a release date $r(i),$ a deadline $d(i)$ .
  • Job i can be feasibly scheduled in the time interval $[r(i),d(i))$.
  • Processing volume $p(i)$, the amount of work that must be finished to complete the job.
  • Have to be assigned to m parallel processors, each of which can independently operate at variable speed.
  • Allow job preemption, disallow job migration.
  • Power Consumption depends on processor's speed $s$

$$ P(s) = s^{p} , p \geq 2 $$

Algorithm

First assign jobs to processors and then, on each processor, construct an optimal schedule for the job set assigned to it.

  • Unit Size Jobs with Agreeable Deadlines

    • polynomial time algorithm : RR
    • jobs are first sorted according to their release dates and are then assigned to processors using Round Robin

  • Unit Size Jobs with Arbitrary Release Dates and Deadlines (NP-hard)

    • Classified Round Robin

      • first divides the given jobs into classes such that each class job densities differ by a factor of at most 2

  • Jobs with Arbitrary Processing volume Requirements $p(i)$

    • Earliest Deadline and List scheduling (Greedy)
    • Assign each job to the processor that currently has the smallest load.

  • Online Algorithms

    • Apply a single processor online algorithm instead of constructing optimal schedules.

---- Appendix ----

See Multi-core Processor (MP) Folder

  • Linear Programming
  • Max flow

[24] E. Angel, E. Bampis, F. Kacem, D. Letsios, Speed scaling on parallel processors with migration, J. Comb. Optim. 37 (4) (2019) 1266–1282.

[25] E. Bampis, A. Kononov, D. Letsios, G. Lucarelli, M. Sviridenko, Energy efficient scheduling and routing via randomized rounding, J. Sched. 21 (1) (2018) 35–51.

[26] S. Albers, A. Antoniadis, G. Greiner, On multi-processor speed scaling with migration, J. Comput. Syst. Sci. 81 (7) (2015) 1194–1209.

[27] V. Chau, X. Chen, K.C.K. Fong, M. Li, K. Wang, Flow shop for dual CPUs in dynamic voltage scaling, Theor. Comput. Sci. 819 (2020) 24–34.