A programming model which allows users to program with high productivity and which produces high performance executions has been a goal for decades. This dissertation makes progress towards this elusive goal by describing the design and implementation of the Galois system, a parallel programming model for shared-memory, multicore machines. Central to the design is the idea that scheduling of a program can be decoupled from the core computational operator and data structures. However, efficient programs often require application-specific scheduling to achieve best performance. To bridge this gap, an extensible and abstract scheduling policy language is proposed, which allows programmers to focus on selecting high-level scheduling policies while delegating the tedious task of implementing the policy to a scheduler synthesizer and runtime system. Implementations of deterministic and prioritized scheduling also are described. An evaluation of a well-studied benchmark suite reveals that factoring programs into operators, schedulers and data structures can produce significant performance improvements over unfactored approaches. Comparison of the Galois system with existing programming models for graph analytics shows significant performance improvements, often orders of magnitude more, due to (1) better support for the restrictive programming models of existing systems and (2) better support for more sophisticated algorithms and scheduling, which cannot be expressed in other systems. / text

Not available / text

Answer set programming (ASP) is a form of declarative programming oriented towards difficult combinatorial search problems. It has been applied, for instance, to plan generation and product configuration problems in artificial intelligence and to graph-theoretic problems arising in VLSI design and in historical linguistics. Syntactically, ASP programs look like Prolog programs, but the computational mechanisms used in ASP are different: they are based on the ideas that have led to the development of fast satisfiability solvers for propositional logic. ASP is based on the answer set/stable model semantics for logic problems, originally intended as a specification for query answering in Prolog. From the original definition of 1988, the semantics was independently extended by different research groups to more expressive kinds of programs, with syntax and semantics that are incompatible with each other. In this thesis we study how the various extensions are related to each other. In order to do that, we propose another definition of an answer set. This definition has three main characteristics: (i) it is very simple, (ii) its syntax is more general than the usual concept of a logic program, and (iii) strong theoretical tools can be used to reason on it. About (ii), we show that our syntax allows constructs defined in many other extensions of the answer sets semantics. This fact, together with (iii), allows us to study the expressiveness of those constructs. We also compare the answer set semantics with another important formalism developed by Norm McCain and Hudson Turner, called logic. / text

Stochastic programming facilitates decision making under uncertainty. It is usually impractical or impossible to find the optimal solution to a stochastic problem, and approximations are required. Sampling-based approximations are simple and attractive, but the standard point estimate of optimization and the Monte Carlo approximation. We provide a method to reduce this bias, and hence provide a better, i.e., tighter, confidence interval on the optimal value and on a candidate solution's optimality gap. Our method requires less restrictive assumptions on the structure of the bias than previously-available estimators. Our estimators adapt to problem-specific properties, and we provide a family of estimators, which allows flexibility in choosing the level of aggressiveness for bias reduction. We establish desirable statistical properties of our estimators and empirically compare them with known techniques on test problems from the literature.

No description available.

No description available.

Vibrational spectra techniques such as IR, Raman and SFG all carry molecular orientation information. Extracting the orientation information from the vibrational spectra often involves creating model spectra with known orientation details to match the experimental spectra. The running time for the exhaustive approach is O(n!). With the help of linear programming, the running time is pseudo O(n). The linear programming approach is with out a doubt far more superior than exhaustive approach in terms of running time. We verify the accuracy of the answer of the linear programming approach by creating mock experimental data with known molecular orientation distribution information of alanine, isoleucine, methionine, lysine, valine and threonine. Linear programming returns the correct orientation distribution information when the mock experimental spectrum consisted of different amino acids. As soon as the mock experimental spectrum consisted of same amino acids, different conformer with different orientation distribution, linear programming fails to give the correct answer albeit the species population is roughly correct. / Graduate

In multiple criteria programming, a decision maker has to choose a point from the set of efficient solutions. This is usually done by some interactive procedure, where he or she moves from one efficient point to the next until an acceptable solution has been reached. It is therefore important to provide some information about the "size" of the efficient set, i.e. to know the minimum (and maximum) criterion values over the efficient set. This is a difficult problem in general. In this paper, we show that for the bicriteria problem, the problem is easy. This does not only hold for the linear bicriteria problem, but also for more general problems. (author's abstract) / Series: Forschungsberichte / Institut für Statistik

published_or_final_version / Computer Science / Master / Master of Philosophy

published_or_final_version / Industrial Engineering / Master / Master of Philosophy