Computer science is experiencing an AI renaissance, in which machine learning models are expediting important breakthroughs in academic research and commercial applications. Effective training of these models, however, is not trivial due in part to hyperparameters: user-configured values that parametrize learning models and control their ability to learn from data. Existing hyperparameter optimization methods are highly parallel but make no effort to balance the search across heterogeneous hardware or to prioritize searching high-impact spaces. In this paper, we introduce a framework for massively Scalable Hardware-Aware Distributed Hyperparameter Optimization (SHADHO). Our framework calculates the relative complexity of each search space and monitors performance on the learning task over all trials. These metrics are then used as heuristics to assign hyperparameters to distributed workers based on their hardware. We demonstrate that our framework scales to 1400 heterogeneous cores and that it achieves a factor of 1.6 speedup in the necessary time to find an optimal set of hyperparameters over a standard distributed hyperparameter optimization framework.
Existing heuristic scheduling solutions are not well-suited for solving the problem of scheduling a model search or hyperparameter optimization process because they assume that the task space is modeled as a dependency graph. Hyperparameter optimization is best modeled as a BoT application: mapping an effectively infinite set of independent tasks to a finite set of resources. Heuristic scheduling for BoT typically involves monitoring resource utilization @cite_12 @cite_36 to minimize the cost of running the tasks, or else scaling hardware to the set of tasks in the case of elastic cloud services @cite_37 . This work, by contrast, schedules based on properties of the tasks (i.e., model training sessions) themselves to match the available hardware, focusing on larger models with less certainty in their performance.
@cite_36 @cite_37 @cite_12
1542558562 2172250608 2660889552 1485083952
Scheduling Bag-of-Tasks (BoT) applications on the cloud can be more challenging than grid and cluster environments. This is because a user may have a budgetary constraint or a deadline for executing the BoT application in order to keep the overall execution costs low. The research in this paper is motivated to investigate task scheduling on the cloud, given two hard constraints based on a user-defined budget and a deadline. A heuristic algorithm is proposed and implemented to satisfy the hard constraints for executing the BoT application in a cost effective manner. The proposed algorithm is evaluated using four scenarios that are based on the trade-off between performance and the cost of using different cloud resource types. The experimental evaluation confirms the feasibility of the algorithm in satisfying the constraints. The key observation is that multiple resource types can be a better alternative to using a single type of resource. On parallel and distributed heterogeneous computing systems, a heuristic-based task scheduling algorithm typically consists of two phases: task prioritization and processor selection. In a heuristic based task scheduling algorithm, different prioritization will produce different makespan on a heterogeneous computing system. Therefore, a good scheduling algorithm should be able to efficiently assign a priority to each subtask depending on the resources needed to minimize makespan. In this paper, a task scheduling scheme on heterogeneous computing systems using a multiple priority queues genetic algorithm (MPQGA) is proposed. The basic idea of our approach is to exploit the advantages of both evolutionary-based and heuristic-based algorithms while avoiding their drawbacks. The proposedalgorithm incorporates a genetic algorithm (GA) approach to assign a priority to each subtask while using a heuristic-based earliest finish time (EFT) approach to search for a solution for the task-to-processor mapping. The MPQGA method also designs crossover, mutation, and fitness function suitable for the scenario of directed acyclic graph (DAG) scheduling. The experimental results for large-sized problems from a large set of randomly generated graphs as well as graphs of real-world problems with various characteristics show that the proposed MPQGA algorithm outperforms two non-evolutionary heuristics and a random search method in terms of schedule quality. Bag-of-Tasks (BoT) applications consisting of multiple tasks widely exist in numerous fields. As customers use cloud resources in a pay-as-you-go way, they are willing to execute BoT applications on clouds. Cloud providers and customers establish contracts in which applications' due dates are specified. If an application cannot be finished before the due date, the cloud provider should pay a tardiness penalty. When the private cloud has insufficient available resources to afford all customer-submitted BoT applications, the cloud provider has to outsource some tasks to public clouds with resource-used costs. The key challenge here is how to schedule tasks on hybrid clouds to minimize the total cost, including all applications' tardiness penalties and the cost of using public clouds' resources. We study and formulate this problem as an Integer Programming. Accordingly, we propose an effective greedy heuristic (GH) including two phases (task ordering and task scheduling). GH uses an Earlier Latest Start Time First method (ELSTF) for task ordering with the result that a task sequence is obtained. A Task Dispatching method (TD) is established for the task scheduling, in which each task in the obtained task sequence is scheduled one by one. Experimental results demonstrate that the proposed GH outperforms the baseline (RoundRobin) remarkably. ELSTF and TD are also verified to be effective. We consider scheduling on an unreliable machine that may experience unexpected changes in processing speed or even full breakdowns. We aim for a universal solution that performs well without adaptation for any possible machine behavior. For the objective of minimizing the total weighted completion time, we design a polynomial time deterministic algorithm that finds a universal scheduling sequence with a solution value within 4 times the value of an optimal clairvoyant algorithm that knows the disruptions in advance. A randomized version of this algorithm attains in expectation a ratio of e. We also show that both results are best possible among all universal solutions. As a direct consequence of our results, we answer affirmatively the question of whether a constant approximation algorithm exists for the offline version of the problem when machine unavailability periods are known in advance. When jobs have individual release dates, the situation changes drastically. Even if all weights are equal, there are instances for which any universal solution is a factor of Ω(logn loglogn) worse than an optimal sequence. Motivated by this hardness, we study the special case when the processing time of each job is proportional to its weight. We present a non-trivial algorithm with a small constant performance guarantee.