Σχολή Επιστημών και Τεχνολογίας της Πληροφορίας

Μόνιμο URI για αυτήν την κοινότηταhttps://pyxida.aueb.gr/handle/123456789/2

Η Σχολή Επιστημών και Τεχνολογίας της Πληροφορίας περιλαμβάνει τα Τμήματα: - Τμήμα Πληροφορικής - Τμήμα Στατιστικής

Περιήγηση

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω

Τώρα δείχνει 1 - 1 από 1

Algorithmic problems in power management of computing systems
Zois, Georgios; Athens University of Economics and Business, Department of Informatics; Universite Pierre et Marie Curie; Ecole doctorale Informatique, Telecommunications et Electronique, Laboratoire d' Informatique de Paris 6, Decision, Systemes Intelligents et Recherche Operationnelle; Bampis, Evripidis; Milis, Ioannis
This thesis is focused on energy-efficient algorithms for job scheduling problems on speed-scalableprocessors, as well as on processors operating under a thermal and cooling mechanism, where, for a given budget of energy or a thermal threshold, the goal is to optimize a Quality of Service criterion. A part of our research concerns scheduling problems arising in large-data processing environments. In this context, we focus on the MapReduce paradigm and we consider problems of energy-efficient scheduling on multiple speed-scalable processors as well as classical scheduling on a set of unrelated processors.First, we study the minimization of the maximum lateness of a set of jobs on a single speed-scalable processor. We consider two variants of the problem: a budget variant, where we aim in minimizing maximum lateness for a given budget of energy and an aggregated variant, where we want to minimize a linear combination of maximum lateness and energy. We propose optimal algorithms for both variants in the non-preemptive case where jobs have common release dates. Our algorithms are based on a number of structural properties that can be obtained after applying the KKT (Karush-Kuhn-Tucker) conditions on a convex programming formulation of the problem. In the presence of arbitrary release dates, we prove that both variants become strongly NP-hard. Moreover, for the budget variant we show that it does not admit any O(1)-competitive deterministic algorithm, while for the aggregated variant we propose a 2-competitive online algorithm. Then, we study energy-aware MapReduce scheduling where the goal is to minimize the total weighted completion time of a set of MapReduce jobs under a given budget of energy. We first propose a convex programming relaxation of the problem, when the execution orderof jobs is known. We combine the solution of this relaxation with two natural list scheduling policies (First Come First Served and Highest Density First) and compare experimentally their effectiveness. Although their performance for random instances is fairly good, we prove that there are instances for which it is very far from the optimal. Next, we propose a linear programming approach which is based on an interval indexed LP-relaxation of the problem that incorporates a discretization of the possible speed values. Our algorithm transforms an optimal solution to this LP into a feasible solution for the problem by list scheduling in the order of tasks' _-points, where _ 2 (0; 1). We obtain a constant factorapproximation algorithm for the total weighted completion time of a set of MapReduce jobs using energy augmentation. In the context of classical MapReduce scheduling (where energy is not our concern) we also study the scheduling of a set of MapReduce jobs on unrelated processors with the goal of minimizing their total weighted completion time. We propose a 54-approximation algorithm which computes a feasible schedule by merging two individual schedules (of either Map or Reduce tasks) into a single schedule. Moreover, we consider the significant part of data shuffle in MapReduce applications and extend our model to capture the shuffle phase. We manage to keep the same ratio of 54 when the Shuffle tasks are scheduled on the same processors with the corresponding Reduce tasks, which becomes81 when the Shuffle and the Reduce tasks are scheduled on different processors. Finally, we focus on temperature-aware scheduling on a single processor that operates under a strict thermal threshold, where each job has its own heat contribution and the goal is to maximize the schedule's throughput. We consider the case of unit-length jobs with a common deadline and we revisit the offline CoolestFirst scheduling, i.e., the job with the smaller heat contribution is scheduled first. We study the approximability of Algorithm CoolestFirst and propose two different rounding schemes that yield lower bounds on its approximation factor. The first is based on a partition of the schedule according to theheat contributions of the jobs, while the second is based on a linear programming approach. The latter, which is actually more refined, yields a lower bound of at least 0.72.i

Περιήγηση

Πλοήγηση Σχολή Επιστημών και Τεχνολογίας της Πληροφορίας ανά Επιβλέπων "Bampis, Evripidis"