Bounding the Flow Time in Online Scheduling with Structured Processing Sets
In: IPDPS 2022 - 36th IEEE International Parallel & Distributed Processing Symposium ; https://hal.science/hal-03561018 ; IPDPS 2022 - 36th IEEE International Parallel & Distributed Processing Symposium, May 2022, Lyon, France. pp.1-11, 2022
Online
Konferenz
Zugriff:
International audience ; Replication in distributed key-value stores makes scheduling more challenging, as it introduces processing set restrictions, which limits the number of machines that can process a given task. We focus on the online minimization of the maximum response time in such systems, that is, we aim at bounding the latency of each task. When processing sets have no structure, Anand et al. (Algorithmica, 2017) derive a strong lower bound on the competitiveness of the problem: no online scheduling algorithm can have a competitive ratio smaller than Ω(m), where m is the number of machines. In practice, data replication schemes are regular, and structured processing sets may make the problem easier to solve. We derive new lower bounds for various common structures, including inclusive, nested or interval structures. In particular, we consider fixed sized intervals of machines, which mimic the standard replication strategy of key-value stores. We prove that EFT (Earliest Finish Time) scheduling is (3−2/k)-competitive when optimizing maxflow on disjoint intervals of size k. However, we show that the competitive ratio of EFT is at least m − k + 1 when these intervals overlap, even when unit tasks are considered. We compare these two replication strategies in simulations and assess their efficiency when popularity biases are introduced, i.e., when some machines are accessed more frequently than others because they hold popular data. Even though overlapping intervals suffer from a bad worst-case in theory, they enable clusters to reach a maximum load that is up to 50% higher than with disjoint sets.
Titel: |
Bounding the Flow Time in Online Scheduling with Structured Processing Sets
|
---|---|
Autor/in / Beteiligte Person: | Canon, Louis-Claude ; Dugois, Anthony ; Marchal, Loris ; Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) (FEMTO-ST) ; Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC) ; Université Bourgogne Franche-Comté COMUE (UBFC)-Université Bourgogne Franche-Comté COMUE (UBFC) ; Laboratoire de l'Informatique du Parallélisme (LIP) ; École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL) ; Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS) ; Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA) ; Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL) ; Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon ; Institut National de Recherche en Informatique et en Automatique (Inria) |
Link: | |
Zeitschrift: | IPDPS 2022 - 36th IEEE International Parallel & Distributed Processing Symposium ; https://hal.science/hal-03561018 ; IPDPS 2022 - 36th IEEE International Parallel & Distributed Processing Symposium, May 2022, Lyon, France. pp.1-11, 2022 |
Veröffentlichung: | HAL CCSD ; IEEE, 2022 |
Medientyp: | Konferenz |
Schlagwort: |
|
Sonstiges: |
|