Search

Highlights • A HPC job dispatcher capable of bounding the power consumption is proposed. • The novel approach combines machine learning techniques and a constraint programming model. • Key idea: predict the power consumption of HPC application and use this knowledge to schedule them effectively. • A thorough comparison with other methods from the state-of-the-art is performed. Abstract Supercomputer installed capacity worldwide increased for many years and further growth is expected in the future. The next goal for high performance computing (HPC) systems is reaching Exascale. The increase in computational power threatens to lead to unacceptable power demands, if future machines will be built using current technology. Therefore reducing supercomputer power consumption has been the subject of intense research. A common approach to curtail the excessive power demands of supercomputers is to hard-bound their consumption, power capping. Power capping can be enforced by reactively throttling system performance when the power bound is hit, or by scheduling workload in a proactive fashion to avoid hitting the bound. In this paper we explore the second approach: our scheduler meets power capping constraints and minimizes quality-of-service (QoS) disruption through smart planning of the job execution order. The approach is based on constraint programming in conjunction with a machine learning module predicting the power consumptions of HPC applications. We evaluate our method on the Eurora supercomputer, using both synthetic workloads and historical traces. Our approach outperforms the state-of-the-art power capping techniques in terms of waiting time and QoS, while keeping schedule computation time under control. [ABSTRACT FROM AUTHOR]

One of the biggest challenges in the design of real-world decision support systems is coming up with a good combinatorial optimization model. Often enough, accurate predictive models (e.g. simulators) can be devised, but they are too complex or too slow to be employed in combinatorial optimization. In this paper, we propose a methodology called Empirical Model Learning (EML) that relies on Machine Learning for obtaining components of a prescriptive model, using data either extracted from a predictive model or harvested from a real system. In a way, EML can be considered as a technique to merge predictive and prescriptive analytics . All models introduce some form of approximation. Citing G.E.P. Box [1] “Essentially, all models are wrong, but some of them are useful”. In EML, models are useful if they provide adequate accuracy, and if they can be effectively exploited by solvers for finding high-quality solutions . We show how to ground EML on a case study of thermal-aware workload dispatching. We use two learning methods, namely Artificial Neural Networks and Decision Trees and we show how to encapsulate the learned model in a number of optimization techniques, namely Local Search, Constraint Programming, Mixed Integer Non-Linear Programming and SAT Modulo Theories. We demonstrate the effectiveness of the EML approach by comparing our results with those obtained using expert-designed models. [ABSTRACT FROM AUTHOR]

Scheduling and dispatching tools for high-performance computing (HPC) machines have the key role of mapping jobs to the available resources, trying to maximize performance and quality-of-service (QoS). Allocation and Scheduling in the general case are well-known NP-hard problems, forcing commercial schedulers to adopt greedy approaches to improve performance and QoS. Search-based approaches featuring the exploration of the solution space have seldom been employed in this setting, but mostly applied in off-line scenarios. In this paper, we present the first search-based approach to job allocation and scheduling for HPC machines, working in a production environment. The scheduler is based on Constraint Programming, an effective programming technique for optimization problems. The resulting scheduler is flexible, as it can be easily customized for dealing with heterogeneous resources, user-defined constraints and different metrics. We evaluate our solution both on virtual machines using synthetic workloads, and on the Eurora HPC with production workloads. Tests on a wide range of operating conditions show significant improvements in waitings and QoS in mid-tier HPC machines w.r.t state-of-the-art commercial rule-based dispatchers. Furthermore, we analyze the conditions under which our approach outperforms commercial approaches, to create a portfolio of scheduling algorithms that ensures robustness, flexibility and scalability. [ABSTRACT FROM AUTHOR]

Abstract: We propose a min-flow algorithm for detecting Minimal Critical Sets (MCS) in Resource Constrained Project Scheduling Problems (RCPSP). The MCS detection is a fundamental step in the Precedence Constraint Posting method (PCP), one of the most successful approaches for the RCPSP. The proposed approach is considerably simpler compared to existing flow based MCS detection procedures and has better scalability compared to enumeration- and envelope-based ones, while still providing good quality Critical Sets. The method is suitable for problem variants with generalized precedence relations or uncertain/variable durations. [Copyright &y& Elsevier]

Abstract: The integration of tree search and metaheuristic techniques for the solution of combinatorial optimization problems is a research area widely explored in the last decade. We propose a search strategy called Sliced Neighborhood Search, SNS, that iteratively explores slices of large neighborhoods of an incumbent solution by performing constraint programming tree search (along with constraint propagation). SNS encloses concepts from metaheuristic techniques. SNS can be used both as a stand alone search strategy, and embedded in other strategies as intensification and diversification mechanism. We provide an extensive experimental evaluation of SNS on hard instances of the Asymmetric Traveling Salesman Problem with Time Windows. We show the effectiveness of SNS as a stand alone strategy when compared to Limited Discrepancy Search and of SNS when included in a heuristic framework such as the constraint programming based local branching. [Copyright &y& Elsevier]

Strategic Environmental Assessment is a procedure aimed at introducing systematic assessment of the environmental effects of plans and programs. This procedure is based on the socalled coaxial matrices that define dependencies between plan activities (infrastructures, plants, resource extractions, buildings, etc.) and positive and negative environmental impacts, and dependencies between these impacts and environmental receptors. Up to now, this procedure is manually implemented by environmental experts for checking the environmental effects of a given plan or program, but it is never applied during the plan/program construction. A decision support system, based on a clear logic semantics, would be an invaluable tool not only in assessing a single, already defined plan, but also during the planning process in order to produce an optimized, environmentally assessed plan and to study possible alternative scenarios. We propose two logic-based approaches to the problem, one based on Constraint Logic Programming and one on Probabilistic Logic Programming that could be, in the future, conveniently merged to exploit the advantages of both. We test the proposed approaches on a real energy plan and we discuss their limitations and advantages. [ABSTRACT FROM AUTHOR]

Abstract: We propose an original, complete and efficient approach to the allocation and scheduling of Conditional Task Graphs (CTGs). In CTGs, nodes represent activities, some of them are branches and are labeled with a condition, arcs rooted in branch nodes are labeled with condition outcomes and a corresponding probability. A task is executed at run time if the condition outcomes that label the arcs in the path to the task hold at schedule execution time; this can be captured off-line by adopting a stochastic model. Tasks need for their execution either unary or cumulative resources and some tasks can be executed on alternative resources. The solution to the problem is a single assignment of a resource and of a start time to each task so that the allocation and schedule is feasible in each scenario and the expected value of a given objective function is optimized. For this problem we need to extend traditional constraint-based scheduling techniques in two directions: (i) compute the probability of sets of scenarios in polynomial time, in order to get the expected value of the objective function; (ii) define conditional constraints that ensure feasibility in all scenarios. We show the application of this framework on problems with objective functions depending either on the allocation of resources to tasks or on the scheduling part. Also, we present the conditional extension to the timetable global constraint. Experimental results show the effectiveness of the approach on a set of benchmarks taken from the field of embedded system design. Comparing our solver with a scenario based solver proposed in the literature, we show the advantages of our approach both in terms of execution time and solution quality. [Copyright &y& Elsevier]

We model portions of the search tree via so-called search constraints. We focus on a particular kind of search constraint, the k-discrepancy constraint appearing in discrepancy-based search. The property that a node has an associated discrepancy k can be modeled (and enforced) through a linear constraint. Our key result is the exploitation of the k-discrepancy constraint to improve the bound given by any relaxation of a combinatorial optimization problem through the additive bounding technique (Fischetti and Toth 1989). We show how this simple idea can be effectively exploited to tighten relaxations in CP solvers and speed up the proof of optimality by performing a large variety of computational experiments on test problems involving the AllDifferent constraint. In this view, the additive bounding technique represents a non-trivial link between search and bound. Moreover, such a technique is general because it does not depend on either the AllDifferent constraint or the discrepancy search technique. [ABSTRACT FROM AUTHOR]

Efforts aimed at combining operations research and constraint programming have become increasingly prominent and successful in the last few years. It is now widely recognized that integration, e.g., inference in the form of constraint propagation and relaxation in the form of linear programming, can yield substantial results. In this paper, we argue the benefits of constraint programming's global constraints as a basis for such an integration and discuss the advantages along with some examples. We illustrate the integration on the global cardinality structure, on piecewise linear functions, on variable subscripts, on the cycle structure and on resource constraints. Each example is completed with a case study. [ABSTRACT FROM AUTHOR]

The Traveling Salesman Problem with Time Windows (TSPTW) is the problem of finding a minimum-cost path visiting a set of cities exactly once, where each city must be visited within a specific time window. We propose a hybrid approach for solving the TSPTW that merges Constraint Programming propagation algorithms for the feasibility viewpoint (find a path), and Operations Research techniques for coping with the optimization perspective (find the best path). We show with extensive computational results that the synergy between Operations Research optimization techniques embedded in global constraints, and Constraint Programming constraint solving techniques, makes the resulting framework effective in the TSPTW context also if these results are compared with state-of-the-art algorithms from the literature. [ABSTRACT FROM AUTHOR]

Abstract: Data-Flow models are attracting renewed attention because they lend themselves to efficient mapping on multi-core architectures. The key problem of finding a maximum-throughput allocation and scheduling of Synchronous Data-Flow graphs (SDFGs) onto a multi-core architecture is NP-hard and has been traditionally solved by means of heuristic (incomplete) algorithms with no guarantee of global optimality. In this paper we propose an exact (complete) algorithm for the computation of a maximum-throughput mapping of applications specified as SDFG onto multi-core architectures. This is, to the best of our knowledge, the first complete algorithm for generic SDF graphs, including those with loops and a finite iteration bound. Our approach is based on Constraint Programming, it guarantees optimality and can handle realistic instances in terms of size and complexity. Extensive experiments on a large number of SDFGs demonstrate that our approach is effective and robust. [Copyright &y& Elsevier]