We study two fundamental variants of the classic paging problem: green paging and parallel paging. In green paging one can choose the exact memory capacity in use at any given instant, between a maximum of k and a minimum of k/p pages; the goal is to minimize the integral of this number over the time required to complete a computation (note that running at lower capacity is not necessarily better, since might disproportionately increase the total completion time). In parallel paging, a memory of k pages is shared between p processors, each carrying out a separate computation; the goal is to minimize the respective completion times. We show how these two different problems are strictly related: any efficient solution to green paging can be converted into an efficient solution to parallel paging, and any lower bound for green paging can be converted into a lower bound for parallel paging - -in both cases in a black-box fashion. Exploiting this relation, we provide tight upper and lower bounds of (log p) on the competitive ratio with O(1) resource augmentation for both problems.

Green Paging and Parallel Paging

Peserico E.;Scquizzato M.
2020

Abstract

We study two fundamental variants of the classic paging problem: green paging and parallel paging. In green paging one can choose the exact memory capacity in use at any given instant, between a maximum of k and a minimum of k/p pages; the goal is to minimize the integral of this number over the time required to complete a computation (note that running at lower capacity is not necessarily better, since might disproportionately increase the total completion time). In parallel paging, a memory of k pages is shared between p processors, each carrying out a separate computation; the goal is to minimize the respective completion times. We show how these two different problems are strictly related: any efficient solution to green paging can be converted into an efficient solution to parallel paging, and any lower bound for green paging can be converted into a lower bound for parallel paging - -in both cases in a black-box fashion. Exploiting this relation, we provide tight upper and lower bounds of (log p) on the competitive ratio with O(1) resource augmentation for both problems.
2020
Annual ACM Symposium on Parallelism in Algorithms and Architectures
9781450369350
File in questo prodotto:
File Dimensione Formato  
AgrawalBDKPS20.pdf

non disponibili

Tipologia: Published (publisher's version)
Licenza: Accesso privato - non pubblico
Dimensione 905.9 kB
Formato Adobe PDF
905.9 kB Adobe PDF Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/3346929
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 2
social impact