As we approach exascale systems, power is turning from an optimization goal to a critical operating constraint. With power bounds imposed by both stakeholders and the limitations of existing infrastructure, achieving practical exascale computing will therefore rely on optimizing performance subject to a power constraint. However, this requirement should not add to the burden of application developers; optimizing the runtime environment given restricted power will primarily be the job of high-performance system software. In this dissertation, we explore this area and develop new techniques that extract maximum performance subject to a particular power constraint. These techniques include a method to find theoretical optimal performance, a runtime system that shifts power in real time to improve performance, and a node-level prediction model for selecting power-efficient operating points. We use a linear programming (LP) formulation to optimize application schedules under various power constraints, where a schedule consists of a DVFS state and number of OpenMP threads for each section of computation between consecutive message passing events. We also provide a more flexible mixed integer-linear (ILP) formulation and show that the resulting schedules closely match schedules from the LP formulation. Across four applications, we use our LP-derived upper bounds to show that current approaches trail optimal, power-constrained performance by up to 41%. This demonstrates limitations of current systems, and our LP formulation provides future optimization approaches with a quantitative optimization target. We also introduce Conductor, a run-time system that intelligently distributes available power to nodes and cores to improve performance. The key techniques used are configuration space exploration and adaptive power balancing. Configuration exploration dynamically selects the optimal thread concurrency level and DVFS state subject to a hardware-enforced power bound. Adaptive power balancing efficiently predicts where critical paths are likely to occur and distributes power to those paths. Greater power, in turn, allows increased thread concurrency levels, CPU frequency/voltage, or both. We describe these techniques in detail and show that, compared to the state-of-the-art technique of using statically predetermined, per-node power caps, Conductor leads to a best-case performance improvement of up to 30%, and an average improvement of 19.1%. At the node level, an accurate power/performance model will aid in selecting the right configuration from a large set of available configurations. We present a novel approach to generate such a model offline using kernel clustering and multivariate linear regression. Our model requires only two iterations to select a configuration, which provides a significant advantage over exhaustive search-based strategies. We apply our model to predict power and performance for different applications using arbitrary configurations, and show that our model, when used with hardware frequency-limiting in a runtime system, selects configurations with significantly higher performance at a given power limit than those chosen by frequency-limiting alone. When applied to a set of 36 computational kernels from a range of applications, our model accurately predicts power and performance; our runtime system based on the model maintains 91% of optimal performance while meeting power constraints 88% of the time. When the runtime system violates a power constraint, it exceeds the constraint by only 6% in the average case, while simultaneously achieving 54% more performance than an oracle. Through the combination of the above contributions, we hope to provide guidance and inspiration to research practitioners working on runtime systems for power-constrained environments. We also hope this dissertation will draw attention to the need for software and runtime-controlled power management under power constraints at various levels, from the processor level to the cluster level.

The research described in this thesis stems from ROBOCARE1, a three year research project aimed at developing software and robotic technology for providing intelligent support for elderly people. This thesis deals with two problems which have emerged in the course of the project’s development: Multi-agent coordination with scarce resources. Multi-agent planning is concerned with automatically devising plans or strategies for the coordinated enactment of concurrently executing agents. A common realistic constraint in applications which require the coordination of multiple agents is the scarcity of resources for execution. In these cases, concurrency is affected by limited capacity resources, the presence of which modifies the structure of the planning/coordination problem. Specifically, the first part of this thesis tackles this problem in two contexts, namely when planning is carried out centrally (planning from first principles), and in the context of distributed multi-agent coordination. Domain modeling for scheduling applications. It is often the case that the products of research in AI problem solving are employed to develop applications for supporting human decision processes. Our experience in ROBOCARE as well as other domains has often called for the customization of prototypical software for real applications. Yet the gap between what is often a research prototype and a complete decision support system is seldom easy to bridge.The second part of the thesis focuses on this issue from the point of view of scheduling software deployment.Overall, this thesis presents three contributions within the two problems mentioned above. First, we address the issue of planning in concurrent domains in which the complexity of coordination is dominated by resource constraints. To this end, an integrated planning and scheduling architecture is presented and employed to explore the structural trademarks of multi-agent coordination problems in function of their resource-related characteristics. Theoretical and experimental analyses are carried out revealing which planning strategies are most fit for achieving plans which prescribe efficient coordination subject to scarce resources.We then turn our attention to distributed multi-agent coordination techniques (specifically, a distributed constraint optimization (DCOP) reduction of the coordination problem). Again, we consider the issue of achieving coordinated action in the presence of limited resources. Specifically, resource constraints impose n-ary relations among tasks. In addition, as the number of n-ary relations due to resource contention are exponential in the size of the problem, they cannot be extensionally represented in the DCOP representation of the coordination problem. Thus, we propose an algorithm for DCOP which retains the capability to dynamically post n-ary constraints during problem resolution in order to guarantee resource-feasible solutions. Although the approach is motivated by the multi-agent coordination problem, the algorithm is employed to realize a general architecture for n-ary constraint reasoning and posting.Third, we focus on a somewhat separate issue stemming from ROBOCARE, namely a software engineering methodology for facilitating the process of customizing scheduling components in real-world applications. This work is motivated by the strong applicative requirements of ROBOCARE. We propose a software engineering methodology specific to scheduling technology development. Our experience in ROBOCARE as well as other application scenarios has fostered the development of a modeling framework which subsumes the process of component customization for scheduling applications. The framework aims to minimize the effort involved in deploying automated reasoning technology in practise, and is grounded on the use of a modeling language for defining how domain-level concepts are grounded into elements of a technology-specific scheduling ontology.

This thesis proposes an expressive yet efficient declarative framework for graph matching in constraint programming (CP), and focuses on efficient algorithms to solve the subgraph isomorphism problem. The framework is based on graph and map variables, and specific graph morphism constraints. This allows to model and solve various graph matching problems, avoiding the tedious development of dedicated and specific algorithms. A specialized filtering algorithm is proposed for the subgraph isomorphism problem, which uses the semantic of the problem as well as the global structure of the two input graphs. It is shown that it is the state-of-the-art filtering algorithm, compared to dedicated algorithms and other CP approaches. Various search techniques from CP are also extended to the subgraph isomorphism problem. An automatic detection and exploitation of symmetries for the subgraph isomorphism problem is proposed, together with a decomposition approach of the search. The significance of this thesis lies in the fact that, even though the framework is expressive, CP can be considered as the state-of-the-art for subgraph isomorphism, outperforming the dedicated known algorithms on current benchmarks.

In the context of internationally challenging economic, design has been regarded as a key factor in assisting design and manufacturing companies to survive. By using up-to-date computer-supported technology, the global design collaboration based on multidisciplinary and distributed environment is becoming a mainstream to new product development (NPD). However, during the process of collaborative design, risk is rarely mentioned. In particular, due to the complexity of design process and lack of efficient design decision-making, there have been some design collaboration failures across multiple companies. Some design projects cannot deliver the benefits as companies have expected through the collaboration. Moreover, a number of stakeholders, managers and designers expressed their disappointment at not seeing the projected savings in cost and time, which critically discredited the value of design collaboration. Many studies in academia and commercial cases have suggested that risk assessment can be applied as an effective means in the realm of design. Nevertheless, few of them conducted risk management research associated with design constraints under a collaborative environment from both theoretical and practical perspectives. In current risk practice, many risk practitioners simply report key risks to their management teams and no further analysis, which might subsequently result in confusion with excessive discussions. Consequently, to prevent the failure of design collaboration and perform a satisfactory risk assessment, it is important to perform risk management with an upstream perspective and at an operational level. An approach, called constraint-based design risk management (DRM) where a conceptual framework has been proposed on the basis of collaborative design features, risk management process and Theory of Constraints (TOC). Moreover, a DRM matrix has been developed to map, measure and mitigate collaborative design risk through evaluating the critical design constraints, and then specified design risk variables in the light of risk criteria. Design constraints are quantitative parameters that frequently affect main design processes and decisions. The combination of design constraints and risk criteria can be accessible and applicable by designers and design mangers. In addition, a Bayesian weighting method based on Bayesian theorem has been developed to measure collaborative design risk in a more efficient manner. Ultimately, a DRM tool has been created as a simulated scenario prototype, which incorporated with three case-study evaluations, to demonstrate the importance and effectiveness of using TOC and risk theory in the realm of design collaboration.

The thesis addresses a complicated real-world scheduling problem from the space operations environment. The Mars Express Orbiter scheduling problem was first presented as a challenge by the European Space Agency. The thesis compares two different solutions. The first solution is an ad-hoc scheduler that is based on scheduling actions into a set of time windows and heavily utilizes local search techniques. The second solution models the problem as a constraint satisfaction problem (CSP) and uses the SICStus Prolog constraint programming solver to find a solution. Both schedulers are experimentally evaluated and the results are compared. Both approaches were able to provide a working solution. The conclusion however states that the more generic CSP based approach was capable of producing higher quality schedules even without a complicated heuristic. It however to compute the schedule for a small subset of inputs. On the other hand, the ad-hoc scheduler was capable of solving larger inputs but the produced solutions are not as good.

The subject of this thesis are mathematical programs with complementarity conditions (MPCC). At first, an economic example of this problem class is analyzed, the problem of effort maximization in asymmetric n-person contest games. While an analytical solution for this special problem could be derived, this is not possible in general for MPCCs. Therefore, optimality conditions which might be used for numerical approaches where considered next. More precisely, a Fritz-John result for MPCCs with stronger properties than those known so far was derived together with some new constraint qualifications and subsequently used to prove an exact penalty result. Finally, to solve MPCCs numerically, the so called relaxation approach was used. Besides improving the results for existing relaxation methods, a new relaxation with strong convergence properties was suggested and a numerical comparison of all methods based on the MacMPEC collection conducted. / Das Thema dieser Dissertation sind mathematische Programme mit Komplementaritätsrestriktionen (MPCC). Zunächst wurde eine ökonomische Anwendung dieses Problemklasse betrachtet, das sogenannte Wettbewerbsdesignproblem. Während es für dieses spezielle Problem möglich war eine analytische Lösung herzuleiten, ist dies im Allgemeinen nicht möglich. Daher wurden anschließend Optimalitätsbedingungen, die für eine numerische Lösung verwendet werden können, betrachtet. Genauer wurde ein stärkeres Fritz-John Resultat als die bisher bekannten zusammen mit neuen Constraint Qualifications hergeleitet und anschließend zum Beweis eines exakten Penaltyresultates benutzt. Schließlich wurden zur numerischen Lösung von MPCCs sogenannte Relaxationsverfahren betrachtet. Zusätzlich zur Verbesserung der Resultate für bekannte Verfahren wurde eine neue Relaxierung mit starken Konvergenzeigenschaften vorgeschlagen und ein numerischer Vergleich aller Verfahren auf Basis der MacMPEC Testsammlung durchgeführt.

Thesis advisor: Fabio Ghironi / This dissertation consists of three essays on macroeconomics with frictions and uncertainty shocks. The first essay is "Collateral Constrained Workers' Unemployment". Financial market and labor market are closely interconnected each other in the sense that unemployed workers have difficulty not only in borrowing new loan but also in repaying outstanding loan. In addition, if unemployment entails loss from default and no new loan, credit constrained workers will accept lower wage to avoid the loss from losing job. In this paper, we try to investigate the role of the interaction between financial market and labor market over the business cycle. To do that, we assume credit constrained workers can borrow against their houses and repay outstanding loans only when they are employed. We also introduce labor search and matching framework into our model to consider unemployment and wage bargaining process explicitly. With this setup, we find that adverse housing preference shock leads to substantial negative impact on labor market by reducing the benefit from maintaining job. As a result, high unemployment significantly amplifies the business cycle by reducing supply of loan and increasing default. This result would be helpful to understand recent "Great Recession" which was originated from the collapse of housing market and accompanied by high unemployment and default rate. The second essay is "International Financial Business Cycles". Recent international macroeconomics literature on global imbalances explains the U.S. persistent current account deficit and emerging countries' surplus, i.e., the U.S. is the borrower. Little research has been done on the banking-sector level, where U.S. banks are lenders to banks in emerging countries. We build a two country framework where banks are explicitly modeled to investigate how lending in the banking sector can affect the international macroeconomy during the recent crisis. In steady state, banks in the developing country borrows from the U.S. banks. When the borrowers in the U.S. pay back less than contractually agreed and damage the balance sheet of the U.S. banks, with the presence of bank capital requirement constraint, U.S. banks raise lending rates and decrease the loans made to U.S. borrowers as well as banks in the developing country. The results are a sharp increase in the lending spread, a reduction in output and a depreciation in the real exchange rate of the developing country. They are the experience of many emerging Asian markets following the U.S. financial crisis starting in late 2007. Another feature of our model captures an empirical fact, documented by Devereux and Yetman (2010), that across different economies, countries with lower financial rating can suffer more when the lending country deleverages. The third essay is "Uncertainty, Collateral Constrained Borrowers, and Business Cycle". Standard RBC model fails to generate the co-movement of key macro variables under uncertainty shock because precautionary saving motive decreases consumption but increases investment and labor. To fill this gap, we build a DSGE model with collateral constrained borrowers who can borrow against housing and capital. In the model with modest risk aversion, we can generate the desired co-movement of key macro variables under uncertainty shock and the co-movement comes from the collateral constraint channel through drop in housing price. Under uncertainty shock, highly indebted borrowers sell collaterals to avoid uncertainty in future consumption. As a result, housing price goes down and it makes credit crunch to borrowers through collateral constraint channel. The negative effect of uncertainty shock is strengthened in the economy with higher indebted borrowers. / Thesis (PhD) — Boston College, 2012. / Submitted to: Boston College. Graduate School of Arts and Sciences. / Discipline: Economics.

by Bo-ming Tong. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1994. / Includes bibliographical references (leaves 104-[110]). / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Concurrent Constraint Programming --- p.2 / Chapter 1.2 --- Finite Domain Constraints --- p.3 / Chapter 2 --- The Firebird Language --- p.5 / Chapter 2.1 --- Finite Domain Constraints --- p.6 / Chapter 2.2 --- The Firebird Computation Model --- p.6 / Chapter 2.3 --- Miscellaneous Features --- p.7 / Chapter 2.4 --- Clause-Based N on determinism --- p.9 / Chapter 2.5 --- Programming Examples --- p.10 / Chapter 2.5.1 --- Magic Series --- p.10 / Chapter 2.5.2 --- Weak Queens --- p.14 / Chapter 3 --- Operational Semantics --- p.15 / Chapter 3.1 --- The Firebird Computation Model --- p.16 / Chapter 3.2 --- The Firebird Commit Law --- p.17 / Chapter 3.3 --- Derivation --- p.17 / Chapter 3.4 --- Correctness of Firebird Computation Model --- p.18 / Chapter 4 --- Exploitation of Data-Parallelism in Firebird --- p.24 / Chapter 4.1 --- An Illustrative Example --- p.25 / Chapter 4.2 --- Mapping Partitions to Processor Elements --- p.26 / Chapter 4.3 --- Masks --- p.27 / Chapter 4.4 --- Control Strategy --- p.27 / Chapter 4.4.1 --- A Control Strategy Suitable for Linear Equations --- p.28 / Chapter 5 --- Data-Parallel Abstract Machine --- p.30 / Chapter 5.1 --- Basic DPAM --- p.31 / Chapter 5.1.1 --- Hardware Requirements --- p.31 / Chapter 5.1.2 --- Procedure Calling Convention And Process Creation --- p.32 / Chapter 5.1.3 --- Memory Model --- p.34 / Chapter 5.1.4 --- Registers --- p.41 / Chapter 5.1.5 --- Process Management --- p.41 / Chapter 5.1.6 --- Unification --- p.49 / Chapter 5.1.7 --- Variable Table --- p.49 / Chapter 5.2 --- DPAM with Backtracking --- p.50 / Chapter 5.2.1 --- Choice Point --- p.52 / Chapter 5.2.2 --- Trailing --- p.52 / Chapter 5.2.3 --- Recovering the Process Queues --- p.57 / Chapter 6 --- Implementation --- p.58 / Chapter 6.1 --- The DECmpp Massively Parallel Computer --- p.58 / Chapter 6.2 --- Implementation Overview --- p.59 / Chapter 6.3 --- Constraints --- p.60 / Chapter 6.3.1 --- Breaking Down Equality Constraints --- p.61 / Chapter 6.3.2 --- Processing the Constraint 'As Is' --- p.62 / Chapter 6.4 --- The Wide-Tag Architecture --- p.63 / Chapter 6.5 --- Register Window --- p.64 / Chapter 6.6 --- Dereferencing --- p.65 / Chapter 6.7 --- Output --- p.66 / Chapter 6.7.1 --- Collecting the Solutions --- p.66 / Chapter 6.7.2 --- Decoding the solution --- p.68 / Chapter 7 --- Performance --- p.69 / Chapter 7.1 --- Uniprocessor Performance --- p.71 / Chapter 7.2 --- Solitary Mode --- p.73 / Chapter 7.3 --- Bit Vectors of Domain Variables --- p.75 / Chapter 7.4 --- Heap Consumption of the Heap Frame Scheme --- p.77 / Chapter 7.5 --- Eager Nondeterministic Derivation vs Lazy Nondeterministic Deriva- tion --- p.78 / Chapter 7.6 --- Priority Scheduling --- p.79 / Chapter 7.7 --- Execution Profile --- p.80 / Chapter 7.8 --- Effect of the Number of Processor Elements on Performance --- p.82 / Chapter 7.9 --- Change of the Degree of Parallelism During Execution --- p.84 / Chapter 8 --- Related Work --- p.88 / Chapter 8.1 --- Vectorization of Prolog --- p.89 / Chapter 8.2 --- Parallel Clause Matching --- p.90 / Chapter 8.3 --- Parallel Interpreter --- p.90 / Chapter 8.4 --- Bounded Quantifications --- p.91 / Chapter 8.5 --- SIMD MultiLog --- p.91 / Chapter 9 --- Conclusion --- p.93 / Chapter 9.1 --- Limitations --- p.94 / Chapter 9.1.1 --- Data-Parallel Firebird is Specialized --- p.94 / Chapter 9.1.2 --- Limitations of the Implementation Scheme --- p.95 / Chapter 9.2 --- Future Work --- p.95 / Chapter 9.2.1 --- Extending Firebird --- p.95 / Chapter 9.2.2 --- Improvements Specific to DECmpp --- p.99 / Chapter 9.2.3 --- Labeling --- p.100 / Chapter 9.2.4 --- Parallel Domain Consistency --- p.101 / Chapter 9.2.5 --- Branch and Bound Algorithm --- p.102 / Chapter 9.2.6 --- Other Possible Future Work --- p.102 / Bibliography --- p.104

by Chong-kan Chiu. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1994. / Includes bibliographical references (leaves 97-103). / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Related Work --- p.2 / Chapter 1.2 --- Organizations of the Dissertation --- p.4 / Chapter 1.3 --- Notations --- p.4 / Chapter 2 --- Overview of ICLP(R) --- p.6 / Chapter 2.1 --- Basics of Interval Arithmetic --- p.6 / Chapter 2.2 --- Relational Interval Arithmetic --- p.8 / Chapter 2.2.1 --- Interval Reduction --- p.8 / Chapter 2.2.2 --- Arithmetic Primitives --- p.10 / Chapter 2.2.3 --- Interval Narrowing and Interval Splitting --- p.13 / Chapter 2.3 --- Syntax and Semantics --- p.16 / Chapter 3 --- Limitations of Interval Narrowing --- p.18 / Chapter 3.1 --- Computation Inefficiency --- p.18 / Chapter 3.2 --- Inability to Detect Inconsistency --- p.23 / Chapter 3.3 --- The Newton Language --- p.27 / Chapter 4 --- Design of CIAL --- p.30 / Chapter 4.1 --- The CIAL Architecture --- p.30 / Chapter 4.2 --- The Inference Engine --- p.31 / Chapter 4.2.1 --- Interval Variables --- p.31 / Chapter 4.2.2 --- Extended Unification Algorithm --- p.33 / Chapter 4.3 --- The Solver Interface and Constraint Decomposition --- p.34 / Chapter 4.4 --- The Linear and the Non-linear Solvers --- p.37 / Chapter 5 --- The Linear Solver --- p.40 / Chapter 5.1 --- An Interval Gaussian Elimination Solver --- p.41 / Chapter 5.1.1 --- Naive Interval Gaussian Elimination --- p.41 / Chapter 5.1.2 --- Generalized Interval Gaussian Elimination --- p.43 / Chapter 5.1.3 --- Incrementality of Generalized Gaussian Elimination --- p.47 / Chapter 5.1.4 --- Solvers Interaction --- p.50 / Chapter 5.2 --- An Interval Gauss-Seidel Solver --- p.52 / Chapter 5.2.1 --- Interval Gauss-Seidel Method --- p.52 / Chapter 5.2.2 --- Preconditioning --- p.55 / Chapter 5.2.3 --- Increment ality of Preconditioned Gauss-Seidel Method --- p.58 / Chapter 5.2.4 --- Solver Interaction --- p.71 / Chapter 5.3 --- Comparisons --- p.72 / Chapter 5.3.1 --- Time Complexity --- p.72 / Chapter 5.3.2 --- Storage Complexity --- p.73 / Chapter 5.3.3 --- Others --- p.74 / Chapter 6 --- Benchmarkings --- p.76 / Chapter 6.1 --- Mortgage --- p.78 / Chapter 6.2 --- Simple Linear Simultaneous Equations --- p.79 / Chapter 6.3 --- Analysis of DC Circuit --- p.80 / Chapter 6.4 --- Inconsistent Simultaneous Equations --- p.82 / Chapter 6.5 --- Collision Problem --- p.82 / Chapter 6.6 --- Wilkinson Polynomial --- p.85 / Chapter 6.7 --- Summary and Discussion --- p.86 / Chapter 6.8 --- Large System of Simultaneous Equations --- p.87 / Chapter 6.9 --- Comparisons Between the Incremental and the Non-Incremental Preconditioning --- p.89 / Chapter 7 --- Concluding Remarks --- p.93 / Chapter 7.1 --- Summary and Contributions --- p.93 / Chapter 7.2 --- Future Work --- p.95 / Bibliography --- p.97

Event stream processing (ESP) has become increasingly important in modern applications. In this dissertation, I focus on providing a robust ESP solution by meeting three major research challenges regarding the robustness of ESP systems: (1) while event constraint of the input stream is available, applying such semantic information in the event processing; (2) handling event streams with out-of-order data arrival and (3) handling event streams with interval-based temporal semantics. The following are the three corresponding research tasks completed by the dissertation: Task I - Constraint-Aware Complex Event Pattern Detection over Streams. In this task, a framework for constraint-aware pattern detection over event streams is designed, which on the fly checks the query satisfiability / unsatisfiability using a lightweight reasoning mechanism and adjusts the processing strategy dynamically by producing early feedback, releasing unnecessary system resources and terminating corresponding pattern monitor. Task II - Complex Event Pattern Detection over Streams with Out-of-Order Data Arrival. In this task, a mechanism to address the problem of processing event queries specified over streams that may contain out-of-order data is studied, which provides new physical implementation strategies for the core stream algebra operators such as sequence scan, pattern construction and negation filtering. Task III - Complex Event Pattern Detection over Streams with Interval-Based Temporal Semantics. In this task, an expressive language to represent the required temporal patterns among streaming interval events is introduced and the corresponding temporal operator ISEQ is designed.