Change search
Refine search result
12 1 - 50 of 53
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the 'Create feeds' function.
  • 1.
    Castañeda Lozano, Roberto
    et al.
    SICS (Swedish Institute of Computer Science), Sweden.
    Carlsson, Mats
    SICS (Swedish Institute of Computer Science), Sweden.
    Drejhammar, Frej
    SICS (Swedish Institute of Computer Science), Sweden.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. SICS (Swedish Institute of Computer Science), Sweden.
    Constraint-Based Register Allocation and Instruction Scheduling2012In: Principles and Practice of Constraint Programming: 18th International Conference, CP 2012, Québec City, QC, Canada, October 8-12, 2012. Proceedings / [ed] Michela Milano, Springer, 2012, p. 750-766Conference paper (Refereed)
    Abstract [en]

    This paper introduces a constraint model and solving techniques for code generation in a compiler back-end. It contributes a new model for global register allocation that combines several advanced aspects: multiple register banks (subsuming spilling to memory), coalescing, and packing. The model is extended to include instruction scheduling and bundling. The paper introduces a decomposition scheme exploiting the underlying program structure and exhibiting robust behavior for functions with thousands of instructions. Evaluation shows that code quality is on par with LLVM, a state-of-the-art compiler infrastructure.

    The paper makes important contributions to the applicability of constraint programming as well as compiler construction: essential concepts are unified in a high-level model that can be solved by readily available modern solvers. This is a significant step towards basing code generation entirely on a high-level model and by this facilitates the construction of correct, simple, flexible, robust, and high-quality code generators.

  • 2.
    Castañeda Lozano, Roberto
    et al.
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. SICS (Swedish Institute of Computer Science).
    Carlsson, Mats
    SICS (Swedish Institute of Computer Science).
    Hjort Blindell, Gabriel
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Register allocation and instruction scheduling in Unison2016In: Proceedings of CC 2016: The 25th International Conference on Compiler Construction, Association for Computing Machinery (ACM), 2016, p. 263-264Conference paper (Refereed)
    Abstract [en]

    This paper describes Unison, a simple, flexible, and potentially optimal software tool that performs register allocation and instruction scheduling in integration using combinatorial optimization. The tool can be used as an alternative or as a complement to traditional approaches, which are fast but complex and suboptimal. Unison is most suitable whenever high-quality code is required and longer compilation times can be tolerated (such as in embedded systems or library releases), or the targeted processors are so irregular that traditional compilers fail to generate satisfactory code.

  • 3.
    Castañeda Lozano, Roberto
    et al.
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. SICS (Swedish Institute of Computer Science) and KTH (Royal Institute of Technology).
    Hjort Blindell, Gabriel
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Carlsson, Mats
    SICS (Swedish Institute of Computer Science).
    Drejhammar, Frej
    SICS (Swedish Institute of Computer Science).
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Constraint-based Code Generation2013In: Proceedings of the 16th International Workshop on Software and Compilers for Embedded Systems, M-SCOPES 2013, Association for Computing Machinery (ACM), 2013, p. 93-95Conference paper (Refereed)
    Abstract [en]

    Compiler back-ends generate assembly code by solving three main tasks: instruction selection, register allocation and instruction scheduling. We introduce constraint models and solving techniques for these code generation tasks and describe how the models can be composed to generate code in unison. The use of constraint programming, a technique to model and solve combinatorial problems, makes code generation simple, flexible, robust and potentially optimal.

  • 4.
    Castañeda Lozano, Roberto
    et al.
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. SICS (Swedish Institute of Computer Science) and KTH (Royal Institute of Technology).
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Survey on Combinatorial Register Allocation and Instruction Scheduling2014Report (Other academic)
    Abstract [en]

    Register allocation and instruction scheduling are two central compiler back-end problems that are critical for quality. In the last two decades, combinatorial optimization has emerged as an alternative approach to traditional, heuristic algorithms for these problems. Combinatorial approaches are generally slower but more flexible than their heuristic counterparts and have the potential to generate optimal code. This paper surveys existing literature on combinatorial register allocation and instruction scheduling. The survey covers approaches that solve each problem in isolation as well as approaches that integrate both problems. The latter have the potential to generate code that is globally optimal by capturing the trade-off between conflicting register allocation and instruction scheduling decisions.

  • 5.
    Castañeda Lozano, Roberto
    et al.
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture (Closed 20120101), Software and Computer Systems, SCS (Closed 20120101).
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture (Closed 20120101), Software and Computer Systems, SCS (Closed 20120101).
    Wahlberg, Lars
    Testing Continuous Double Auctions with a Constraint-Based Oracle2010In: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING-CP 2010 / [ed] Cohen D, 2010, Vol. 6308, p. 613-627Conference paper (Refereed)
    Abstract [en]

    Computer trading systems are essential for today's financial markets where the trading systems' correctness is of paramount economical significance. Automated random testing is a useful technique to find bugs in these systems, but it requires an independent system to decide the correctness of the system under test (known as oracle problem). This paper introduces a constraint-based oracle for random testing of a real-world trading system. The oracle provides the expected results by generating and solving constraint models of the trading system's continuous double auction. Constraint programming is essential for the correctness of the test oracle as the logic for calculating trades can be mapped directly to constraint models. The paper shows that the generated constraint models can be solved efficiently. Most importantly, the approach is shown to be successful by finding errors in a deployed financial trading system and in its specification.

  • 6. Chu, Geoffrey
    et al.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Software and Computer Systems, SCS.
    Stuckey, Peter J.
    Confidence-based Work Stealing in Parallel Constraint Programming2009In: Fifteenth International Conference on Principles and Practice of Constraint Programming, Springer Science+Business Media B.V., 2009, Vol. 5732, p. 226-241Conference paper (Refereed)
    Abstract [en]

    The most popular architecture for parallel search is work  stealing: threads that have run out of work (nodes to be  searched) steal from threads that still have work.  Work  stealing not only allows for dynamic load balancing, but also  determines which parts of the search tree are searched next.  Thus the place from where work is stolen has a dramatic effect  on the efficiency of a parallel search algorithm.

      This paper examines quantitatively how optimal work stealing  can be performed given an estimate of the relative solution  densities of the subtrees at each search tree node and relates  it to the branching heuristic strength.  An adaptive work stealing algorithm is presented that  automatically performs different work stealing strategies based  on the confidence of the branching heuristic at each node. Many  parallel depth-first search patterns arise naturally from this  algorithm. The algorithm produces near perfect or  super linear algorithmic efficiencies on all problems tested.  Real speedups using 8 threads range from 7 times to  super linear.

  • 7.
    Corcoran, Diarmuid
    et al.
    KTH. Ericsson AB.
    Andimeh, Loghman
    Ericsson AB.
    Ermedahl, Andreas
    Ericsson AB.
    Kreuger, Per
    RISE SICS AB.
    Schulte, Christian
    KTH, Superseded Departments (pre-2005), Microelectronics and Information Technology, IMIT.
    Data Driven Selection of DRX for Energy Efficient 5G RAN2017In: 2017 13TH INTERNATIONAL CONFERENCE ON NETWORK AND SERVICE MANAGEMENT (CNSM), IEEE , 2017Conference paper (Refereed)
    Abstract [en]

    The number of connected mobile devices is increasing rapidly with more than 10 billion expected by 2022. Their total aggregate energy consumption poses a significant concern to society. The current 3gpp (3rd Generation Partnership Project) LTE/LTE-Advanced standard incorporates an energy saving technique called discontinuous reception (DRX). It is expected that 5G will use an evolved variant of this scheme. In general, the single selection of DRX parameters per device is non trivial. This paper describes how to improve energy efficiency of mobile devices by selecting DRX based on the traffic profile per device. Our particular approach uses a two phase data-driven strategy which tunes the selection of DRX parameters based on a smart fast energy model. The first phase involves the off-line selection of viable DRX combinations for a particular traffic mix. The second phase involves an on-line selection of DRX from this viable list. The method attempts to guarantee that latency is not worse than a chosen threshold. Alternatively, longer battery life for a device can be traded against increased latency. We built a lab prototype of the system to verify that the technique works and scales on a real LTE system. We also designed a sophisticated traffic generator based on actual user data traces. Complementary method verification has been made by exhaustive off-line simulations on recorded LTE network data. Our approach shows significant device energy savings, which has the aggregated potential over billions of devices to make a real contribution to green, energy efficient networks.

  • 8. Corcoran, Diarmuid
    et al.
    Andimeh, Logman
    Ermedahl, Andreas
    Kreuger, Per
    Schulte, Christian
    KTH.
    Data Driven Selection of DRX for Energy Efficient 5G RAN2017In: 13th International Conference on Network and Service Management (CNSM), 2017, IEEE conference proceedings, 2017, p. 1-9Conference paper (Refereed)
    Abstract [en]

    The number of connected mobile devices is increasing rapidly with more than 10 billion expected by 2022. Their total aggregate energy consumption poses a significant concern to society. The current 3gpp (3rd Generation Partnership Project) LTE/LTE-Advanced standard incorporates an energy saving technique called discontinuous reception (DRX). It is expected that 5G will use an evolved variant of this scheme. In general, the single selection of DRX parameters per device is non trivial. This paper describes how to improve energy efficiency of mobile devices by selecting DRX based on the traffic profile per device. Our particular approach uses a two phase data-driven strategy which tunes the selection of DRX parameters based on a smart fast energy model. The first phase involves the off-line selection of viable DRX combinations for a particular traffic mix. The second phase involves an on-line selection of DRX from this viable list. The method attempts to guarantee that latency is not worse than a chosen threshold. Alternatively, longer battery life for a device can be traded against increased latency. We built a lab prototype of the system to verify that the technique works and scales on a real LTE system. We also designed a sophisticated traffic generator based on actual user data traces. Complementary method verification has been made by exhaustive off-line simulations on recorded LTE network data. Our approach shows significant device energy savings, which has the aggregated potential over billions of devices to make a real contribution to green, energy efficient networks.

  • 9. Delgado, Alberto
    et al.
    Møller Jensen, Rune
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Software and Computer Systems, SCS.
    Generating Optimal Stowage Plans for Container Vessel Bays2009In: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING, 2009, Vol. 5732, p. 6-20Conference paper (Refereed)
    Abstract [en]

    Millions of containers are stowed ever.), week with goods worth billions of dollars, but container vessel stowage is an all but neglected combinatorial optimization problem. In this paper, we introduce a model for stowing containers in a vessel bay which is the result of probably the longest collaboration to date with a liner shipping company on automated stowage planning. We then show how to solve this model efficiently in - to our knowledge - the first; application of CP to stowage planning using state-of-the-art techniques such as extensive use of global constraints, viewpoints, static and dynamic symmetry breaking, decomposed branching strategies, and early failure detection. Our CP approach outperforms an integer programming and column generation approach in a preliminary study. Since a complete model of this problem includes even more logical constraints, we believe that stowage planning is a new application area, for CP with a high impact potential.

  • 10.
    Drejhammar, Frej
    et al.
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Haridi, Seif
    Brand, Per
    Flow Java: Declarative Concurrency for Java2003In: Proceedings of the Nineteenth International Conference on Logic Programming, 2003, Vol. 2916, p. 346-360Conference paper (Refereed)
  • 11. Flener, Pierre
    et al.
    Carlsson, Mats
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Software and Computer Systems, SCS.
    Constraint Programming in Sweden2009In: IEEE Intelligent Systems, ISSN 1541-1672, Vol. 24, no 2, p. 87-89Article in journal (Other academic)
  • 12. Frühwirth, Thom
    et al.
    Michel, Laurent
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Constraints in Procedural and Concurrent Languages2006In: Handbook of Constraint Programming, Elsevier, 2006, p. 453-494Chapter in book (Other academic)
  • 13.
    Haridi, Seif
    et al.
    Swedish Institute of Computer Science.
    Van Roy, Peter
    Département INGI, Univ. Catholique de Louvain.
    Brand, Per
    Swedish Institute of Computer Science.
    Schulte, Christian
    Ger. Res. Ctr. for Artif. Intell..
    Programming languages for distributed applications1998In: New generation computing, ISSN 0288-3635, E-ISSN 1882-7055, Vol. 16, no 3, p. 223-261Article in journal (Refereed)
    Abstract [en]

    Much progress has been made in distributed computing in the areas of distribution structure, open computing, fault tolerance, and security. Yet, writing distributed applications remains difficult because the programmer has to manage models of these areas explicitly. A major challenge is to integrate the four models into a coherent development platform. Such a platform should make it possible to cleanly separate an application's functionality from the other four concerns. Concurrent constraint programming, an evolution of concurrent logic programming, has both the expressiveness and the formal foundation needed to attempt this integration. As a first step, we have designed and built a platform that separates an application's functionality from its distribution structure. We have prototyped several collaborative tools with this platform, including a shared graphic editor whose design is presented in detail. The platform efficiently implements Distributed Oz, which extends the Oz language with constructs to express the distribution structure and with basic primitives for open computing, failure detection and handling, and resource control. Oz appears to the programmer as a concurrent object-oriented language with dataflow synchronization. Oz is based on a higher-order, state-aware, concurrent constraint computation model.

  • 14.
    Havelka, Dragan
    et al.
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Brand, P
    Haridi, Seif
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Thread-based mobility in Oz2005In: MULTIPARADIGM PROGRAMMING IN MOZART/OZ / [ed] Roy, PV, BERLIN: SPRINGER-VERLAG BERLIN , 2005, Vol. 3389, p. 137-148Conference paper (Refereed)
    Abstract [en]

    Strong mobility enables migration of entire computations combining code, data, and execution state (such as stack and program counter) between sites of computation. This is in contrast to weak mobility where migration is confined to just code and data. Strong mobility is essential for many applications where reconstruction of execution states is either difficult or even impossible: load balancing, reduction of network latency and traffic, and resource-related migration, just to name a few. This paper presents a model, programming abstractions, implementation, and evaluation of thread-based strong mobility. The model extends and takes advantage of a distributed programming model based on automatic synchronization through dataflow variables. It comes as a natural extension of dataflow computing which carefully separates issues concerning distribution and mobility. The programming abstractions capture various migration scenarios which differ in how the source and destination site relate to the site initiating migration. The implementation is based on replicating concurrent lightweight threads between sites controlled by migration managers.

  • 15.
    Hjort Blindell, Gabriel
    et al.
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. SICS RISE.
    Carlsson, Mats
    RISE SICS.
    Castañeda Lozano, Roberto
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. RISE SICS.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. RISE SICS.
    Complete and Practical Universal Instruction Selection2017In: ACM Transactions on Embedded Computing Systems, ISSN 1539-9087, E-ISSN 1558-3465Article in journal (Refereed)
    Abstract [en]

    In code generation, instruction selection chooses processor instructions to implement a program under compilation where code quality crucially depends on the choice of instructions. Using methods from combinatorial optimization, this paper proposes an expressive model that integrates global instruction selection with global code motion.The model introduces (1) handling of memory computations and function calls, (2) a method for inserting additional jump instructions where necessary, (3) a dependency-based technique to ensure correct combinations of instructions, (4) value reuse to improve code quality, and (5) an objective function that reduces compilation time and increases scalability by exploiting bounding techniques. The approach is demonstrated to be complete and practical, competitive with LLVM, and potentially optimal (w.r.t. the model) for medium-sized functions. The results show that combinatorial optimization for instruction selection is well-suited to exploit the potential of modern processors in embedded systems.

  • 16.
    Hjort Blindell, Gabriel
    et al.
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Castañeda Lozano, Roberto
    Swedish Institute of Computer Science.
    Carlsson, Mats
    Swedish Institute of Computer Science.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Modeling Universal Instruction Selection2015In: Principles and Practice of Constraint Programming: 21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings / [ed] Gilles Pesant, Springer, 2015, Vol. 9255, p. 609-626Conference paper (Refereed)
    Abstract [en]

    Instruction selection implements a program under compilation by selecting  processor instructions and has tremendous impact on the performance of the  code generated by a compiler. This paper introduces a graph-based  universal representation that unifies data and control flow for both  programs and processor instructions. The representation is the essential  prerequisite for a constraint model for instruction selection introduced in  this paper. The model is demonstrated to be expressive in that it supports many processor  features that are out of reach of state-of-the-art approaches, such as  advanced branching instructions, multiple register banks, and SIMD  instructions. The resulting model can be solved for small to medium size  input programs and sophisticated processor instructions and is competitive with LLVM in code quality. Model and representation are significant due to their  expressiveness and their potential to be combined with models for other code  generation tasks.

  • 17.
    Lagerkvist, Mikael Z.
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture.
    Advisors for incremental propagation2007In: Principles and Practice of Constraint Programming - CP 2007 / [ed] Bessiere, C, 2007, Vol. 4741, p. 409-422Conference paper (Refereed)
    Abstract [en]

    While incremental propagation for global constraints is recognized to be important, little research has been devoted to how propagator-centered constraint programming systems should support incremental propagation. This paper introduces advisors as a simple and efficient, yet widely applicable method for supporting incremental propagation in a propagator-centered setting. The paper presents how advisors can be used for achieving different forms of incrementality and evaluates cost and benefit for several global constraints.

  • 18.
    Lagerkvist, Mikael Zayenz
    et al.
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Software and Computer Systems, SCS.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Software and Computer Systems, SCS.
    Propagator Groups2009In: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING / [ed] Gent IP, 2009, Vol. 5732, p. 524-538Conference paper (Refereed)
    Abstract [en]

    This paper introduces propagator groups as an abstraction for controlling the execution of propagators as implementations of constraints. Propagator groups enable users of a constraint programming system to program how propagators within a group are executed. The paper exemplifies propagator groups for controlling both propagation order and propagator interaction. Controlling propagation order is applied to debugging constraint propagation and optimal constraint propagation for Berge-acyclic propagator graphs. Controlling propagator interaction by encapsulating failure and entailment is applied to general reification and constructive disjunction. The paper describes an implementation of propagator groups (based on Gecode) that is applicable to any propagator-centered constraint programming system. Experiments show that groups incur little to no overhead and that the applications of groups axe practically usable and efficient.

  • 19. Lee, Jimmy Ho Man
    et al.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Zhu, Zichen
    Increasing Nogoods in Restart-Based Search2016In: AAAI Conference on Artificial Intelligence, 2016, p. 3426-3433Conference paper (Refereed)
  • 20. Loth, M.
    et al.
    Hamadi, Y.
    Sebag, M.
    Schoenauer, M.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Bandit-based search for constraint programming2013In: AAAI Workshop - Technical Report: Volume WS-13-07, 2013, AI Access Foundation , 2013, p. 8-13Conference paper (Refereed)
    Abstract [en]

    Constraint Programming (CP) solvers classically explore the solution space using tree-search based heuristics. MonteCarlo Tree-Search (MCTS) is a tree-search method aimed at optimal sequential decision making under uncertainty. At the crossroads of CP and MCTS, this paper presents the Bandit Search for Constraint Programming (BASCOP) algorithm, adapting MCTS to the specifics of CP search trees. Formally, MCTS simultaneously estimates the average node reward, and uses it to bias the exploration towards the most promising regions of the tree, borrowing the multi-armed bandit (MAB) decision rule. The two contributions in BASCOP concern i) a specific reward function, estimating the relative failure depth conditionally to a (variable, value) assignment; ii) a new decision rule, hybridizing the MAB framework and the spirit of local neighborhood search. Specifically, BASCOP guides the CP search in the neighborhood of the previous best solution, by exploiting statistical estimates gathered across multiple restarts. BASCOP, using Gecode as the underlying constraint solver, shows significant improvements over the depthfirst search baseline on some CP benchmark suites. For hard job-shop scheduling problems, BASCOP matches the results of state-of-the-art scheduling-specific CP approaches. These results demonstrate the potential of BASCOP as a generic yet robust search method for CP.

  • 21. Loth, Manuel
    et al.
    Sebag, Michèlle
    Hamadi, Youssef
    Schoenauer, Marc
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Hybridizing constraint programming and Monte-Carlo tree search: Application to the job shop problem2013In: Lecture Notes in Computer Science / [ed] Giuseppe Nicosia and Panos Pardalos, 2013, p. 315-320Conference paper (Refereed)
    Abstract [en]

    Constraint Programming (CP) solvers classically explore the solution space using tree search-based heuristics. Monte-Carlo Tree-Search (MCTS), a tree-search based method aimed at sequential decision making under uncertainty, simultaneously estimates the reward associated to the sub-trees, and gradually biases the exploration toward the most promising regions. This paper examines the tight combination of MCTS and CP on the job shop problem (JSP). The contribution is twofold. Firstly, a reward function compliant with the CP setting is proposed. Secondly, a biased MCTS node-selection rule based on this reward is proposed, that is suitable in a multiple-restarts context. Its integration within the Gecode constraint solver is shown to compete with JSP-specific CP approaches on difficult JSP instances.

  • 22.
    Lozano, Roberto Castaneda
    et al.
    SCALE, Swedish Institute of Computer Science, Sweden .
    Carlsson, Mats
    Hjort Blindell, Gabriel
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Combinatorial Spill Code Optimization and Ultimate Coalescing2014In: SIGPLAN notices, ISSN 0362-1340, E-ISSN 1558-1160, Vol. 49, no 5, p. 23-32Article in journal (Refereed)
    Abstract [en]

    This paper presents a novel combinatorial model that integrates global register allocation based on ultimate coalescing, spill code optimization, register packing, and multiple register banks with instruction scheduling (including VLIW). The model exploits alternative temporaries that hold the same value as a new concept for ultimate coalescing and spill code optimization. The paper presents Unison as a code generator based on the model and advanced solving techniques using constraint programming. Thorough experiments using MediaBench and a processor (Hexagon) that are typical for embedded systems demonstrate that Unison: is robust and scalable; generates faster code than LLVM (up to 4 1 % with a mean improvement of 7 %); possibly generates optimal code (for 2 9 % of the experiments); effortlessly supports different optimization criteria (code size on par with LLVM). Unison is significant as it addresses the same aspects as traditional code generation algorithms, yet is based on a simple integrated model and robustly can generate optimal code.

  • 23. Mehl, Michael
    et al.
    Scheidhauer, Ralf
    Schulte, Christian
    KTH, Superseded Departments (pre-2005), Microelectronics and Information Technology, IMIT.
    An Abstract Machine for Oz1995Conference paper (Refereed)
  • 24. Michel, Laurent
    et al.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Hentenryck, Pascal Van
    Constraint Programming Tools2007In: Trends in Constraint Programming, IST Press, 2007, p. 41-57Chapter in book (Other academic)
  • 25. Reischuk, Raphael M.
    et al.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Software and Computer Systems, SCS.
    Stuckey, Peter J.
    Tack, Guido
    Maintaining State in Propagation Solvers2009In: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING / [ed] Gent, IP, Springer, 2009, Vol. 5732, p. 692-706Conference paper (Refereed)
    Abstract [en]

    Constraint propagation solvers interleave propagation, removing impossible values from variable domains, with search. The solver state is modified during propagation. But search requires the solver to return to a previous state. Hence a, propagation solver must determine how to maintain state during propagation and forward and backward search. This paper sets out the possible ways in which a propagation solver call choose to maintain state, and the restrictions that such choices place on the resulting system. Experiments illustrate the result of various choices for the three principle state components of a solver: variables, propagators, and dependencies between them. This paper also provides the first realistic comparison of trailing versus copying for state restoration.

  • 26.
    Schulte, Christian
    KTH, Superseded Departments (pre-2005), Microelectronics and Information Technology, IMIT.
    Comparing Trailing and Copying for Constraint Programming1999In: Proceedings of the Sixteenth International Conference on Logic Programming, MIT Press, 1999, p. 275-289Conference paper (Refereed)
  • 27.
    Schulte, Christian
    KTH, Superseded Departments (pre-2005), Microelectronics and Information Technology, IMIT.
    Oz Explorer: A Visual Constraint Programming Tool1997In: Proceedings of the Fourteenth International Conference on Logic Programming, MIT Press, 1997, p. 286-300Conference paper (Refereed)
  • 28.
    Schulte, Christian
    KTH, Superseded Departments (pre-2005), Microelectronics and Information Technology, IMIT.
    Parallel Search Made Simple2000In: Proceedings of TRICS: Techniques foR Implementing Constraint programming Systems, a post-conference workshop of CP 2000, 2000Conference paper (Refereed)
  • 29.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Principles and Practice of Constraint Programing-CP 2013: 19th International Conference, CP 2013, Uppsala, Sweden, September 16-20, 2013, Proceedings2013Collection (editor) (Refereed)
    Abstract [en]

    This book constitutes the refereed conference proceedings of the 19th International Conference on Principles and Practice of Constraint Programming (CP 2013), held in Uppsala, Sweden, in September 2013.  The 59 revised papers presented together with 5 invited talks were carefully selected from 170 submissions. The scope of the conference is on all aspects of computing with constraints, including: theory, algorithms, environments, languages, models and systems, applications such as decision making, resource allocation, and agreement technologies.

  • 30.
    Schulte, Christian
    Programming Systems Lab, DFKI, Stuhlsatzenhausweg 3, Saarbrücken, Germany.
    Programming Constraint Inference Engines1997In: Proceedings of the Third International Conference on Principles and Practice of Constraint Programming, Springer, 1997, Vol. 1330, p. 519-533Conference paper (Refereed)
    Abstract [en]

    Existing constraint programming systems offer a fixed set of inference engines implementing search strategies such as single, all, and best solution search. This is unfortunate, since new engines cannot be integrated by the user. The paper presents first-class computation spaces as abstractions with which the user can program inference engines at a high level, Using computation spaces, the paper covers several inference engines ranging from standard search strategies to techniques new to constraint programming, including limited discrepancy search, visual search, and saturation. Saturation is an inference method for tautologychecking used in industrial practice. Computation spaces have shown their practicability in the constraint programming system Oz.

  • 31.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Programming Constraint Services2002Book (Other academic)
  • 32.
    Schulte, Christian
    KTH, Superseded Departments (pre-2005), Microelectronics and Information Technology, IMIT.
    Programming Deep Concurrent Constraint Combinators2000In: Practical Aspects of Declarative Languages. PADL 2000, Springer, 2000, Vol. 1753, p. 215-229Conference paper (Refereed)
    Abstract [en]

    Constraint combination methods are essential for a flexible constraint programming system. This paper presents deep concurrent constraint combinators based on computation spaces as combination mechanism. It introduces primitives and techniques needed to program constraint combinators from computation spaces. The paper applies computation spaces to a broad range of combinators: negation, generalized reificatian, disjunction, and implication. Even though computation spaces have been conceived in the context of Oz, they are mainly programming language independent. This point is stressed by discussing them here in the context of Standard ML with concurrency features.

  • 33.
    Schulte, Christian
    KTH, Superseded Departments (pre-2005), Microelectronics and Information Technology, IMIT.
    Solver - An Oz Search Debugger1995Conference paper (Refereed)
  • 34.
    Schulte, Christian
    et al.
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture (Closed 20120101), Software and Computer Systems, SCS (Closed 20120101).
    Carlsson, M.
    Chapter 14 Finite domain constraint programming systems2006In: Foundations of Artificial Intelligence, 2006, no C, p. 495-526Chapter in book (Refereed)
  • 35.
    Schulte, Christian
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Carlsson, Mats
    Finite Domain Constraint Programming Systems2006In: Handbook of Constraint Programming / [ed] Francesca Rossi, Peter van Beek, Toby Walsh, Elsevier, 2006, p. 495-526Chapter in book (Other academic)
  • 36. Schulte, Christian
    et al.
    Smolka, Gert
    Encapsulated Search in Higher-order Concurrent Constraint Programming1994Conference paper (Refereed)
  • 37. Schulte, Christian
    et al.
    Smolka, Gert
    Würtz, Jörg
    Encapsulated Search and Constraint Programming in Oz1994In: Second International Workshop on Principles and Practice of Constraint Programming, Springer-Verlag , 1994, Vol. 874, p. 134-150Conference paper (Refereed)
  • 38.
    Schulte, Christian
    et al.
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Stuckey, P. J.
    When do bounds and domain propagation lead to the same search space?2005In: ACM Transactions on Programming Languages and Systems, ISSN 0164-0925, E-ISSN 1558-4593, Vol. 27, no 3, p. 388-425Article in journal (Refereed)
    Abstract [en]

    This article explores the question of when two propagation-based constraint systems have the same behavior, in terms of search space. We categorize the behavior of domain and bounds propagators for primitive constraints, and provide theorems that allow us to determine propagation behaviors for conjunctions of constraints. We then show how we can use this to analyze CLP(FD) programs to determine when we can safely replace domain propagators by more efficient bounds propagators without increasing search space. Empirical evaluation shows that programs optimized by the analysis' results are considerably more efficient.

  • 39.
    Schulte, Christian
    et al.
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Software and Computer Systems, SCS.
    Stuckey, Peter J.
    Dynamic Analysis of Bounds Versus Domain Propagation2008In: LOGIC PROGRAMMING, PROCEEDINGS / [ed] DelaBanda MG; Pontelli E, 2008, Vol. 5366, p. 332-346Conference paper (Refereed)
    Abstract [en]

    Constraint propagation solvers interleave propagation (removing impossible values from variable domains) with search. Previously, Schulte and Stuckey introduced the use of static analysis to determine where in a constraint program domain propagators can be replaced by more efficient bounds propagators and still ensure that the same search) is traversed. This paper introduces a dynamic,yet considerably simpler approach to uncover the same information. The information is obtained by a linear time traversal of an analysis graph that straightforwardly, v reflects the properties of propagators implementing constraints. Experiments confirm that the simple, dynamic method is efficient and that it can be used interleaved with search, taking advantage of the simplification of the constraint graph that arises from search.

  • 40.
    Schulte, Christian
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Stuckey, Peter J.
    Dynamic Variable Elimination During Propagation Solving2008In: PPDP 2008: Proceedings of the 10th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming, ACM Press, 2008, p. 247-257Conference paper (Refereed)
    Abstract [en]

    Constraint propagation solvers interleave propagation (removing impossible values from variables domains) with search. Propagation is performed by executing propagators (removing values) implementing constraints (defining impossible values). In order to specify constraint problems with a propagation solver often many new intermediate variables need to be introduced. Each variable plays a role in calculating the value of some expression. But as search proceeds not all of these expressions will be of interest any longer, but the propagators implementing them will remain active. In this paper we show how we can analyse the propagation graph of the solver in linear time to determine intermediate variables that can be removed without effecting the result. Experiments show that applying this analysis can reduce the space and time requirements for constraint propagation on example problems.

  • 41.
    Schulte, Christian
    et al.
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Software and Computer Systems, SCS.
    Stuckey, Peter J.
    Efficient Constraint Propagation Engines2008In: ACM Transactions on Programming Languages and Systems, ISSN 0164-0925, E-ISSN 1558-4593, Vol. 31, no 1, p. 2-Article in journal (Refereed)
    Abstract [en]

    This article presents a model and implementation techniques for speeding up constraint propagation. Three fundamental approaches to improving constraint propagation based on propagators as implementations of constraints are explored: keeping track of which propagators are at fixpoint, choosing which propagator to apply next, and how to combine several propagators for the same constraint. We show how idempotence reasoning and events help track fixpoints more accurately. We improve these methods by using them dynamically (taking into account current variable domains to improve accuracy). We define priority-based approaches to choosing a next propagator and show that dynamic priorities can improve propagation. We illustrate that the use of multiple propagators for the same constraint can be advantageous with priorities, and introduce staged propagators that combine the effects of multiple propagators with priorities for greater efficiency.

  • 42.
    Schulte, Christian
    et al.
    KTH, Superseded Departments (pre-2005), Microelectronics and Information Technology, IMIT.
    Stuckey, Peter J.
    When Do Bounds and Domain Propagation Lead to the Same Search Space2001In: Proceedings of the 3rd International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'00); Florence; Italy; 5 September 2001 through 7 September 2001, ACM Press, 2001, p. 115-126Conference paper (Refereed)
    Abstract [en]

    This paper explores the question of when two propagation-based constraint systems have the same behaviour, in terms of search space. We categorise the behaviour of domain and bounds propagators for primitive constraints, and provide theorems that allow us to determine propagation behaviours for conjunctions of constraints. We then show how we can use this to analyse CLP(FD) programs to determine when we can safely replace domain propagators by more efficient bounds propagators without increasing search space.

  • 43.
    Schulte, Christian
    et al.
    KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
    Stuckey, PJ
    Speeding up constraint propagation2004In: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING: CP 2004, PROCEEDINGS / [ed] Wallace, M, BERLIN: SPRINGER , 2004, Vol. 3258, p. 619-633Conference paper (Refereed)
    Abstract [en]

    This paper presents a model and implementation techniques for speeding up constraint propagation. Two fundamental approaches to improving constraint propagation are explored: keeping track of which propagators are at fixpoint, and choosing which propagator to apply next. We show how idempotence reasoning and events help track fixpoints more accurately. We improve these methods by using them dynamically (taking into account current domains to improve accuracy). We define priority-based approaches to choosing a next propagator and show that dynamic priorities can improve propagation. We illustrate that the use of multiple propagators for the same constraint can be advantageous with priorities, and introduce staged propagators which combine the effects of multiple propagators with priorities for greater efficiency.

  • 44.
    Schulte, Christian
    et al.
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Tack, G
    Views and iterators for generic constraint implementations2005In: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2005, PROCEEDINGS / [ed] VanBeek, P, BERLIN: SPRINGER-VERLAG BERLIN , 2005, Vol. 3709, p. 817-821Conference paper (Refereed)
    Abstract [en]

    This paper introduces an architecture for generic constraint implementations based on variable views and range iterators. Views allow, for example, to scale, translate, and negate variables. The paper shows how to make constraint implementations generic and how to reuse a single generic implementation with different views for different constraints. Applications of views exemplify their usefulness and their potential for simplifying constraint implementations. We introduce domain operations compatible with views based on range iterators to access and modify entire variable domains.

  • 45.
    Schulte, Christian
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Tack, Guido
    Perfect Derived Propagators2008In: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING / [ed] Stuckey, PJ, 2008, Vol. 5202, p. 571-575Conference paper (Refereed)
    Abstract [en]

    When implementing a propagator for a constraint, one must decide about variants: When implementing min , should one also implement max ? Should one implement linear equations both with and without coefficients? Constraint variants are ubiquitous: implementing them requires considerable effort, but yields better performance. This paper shows how to use variable views to derive perfect propagator variants: derived propagators inherit essential properties such as correctness and domain and bounds completeness.

  • 46.
    Schulte, Christian
    et al.
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Tack, Guido
    View-Based Propagator Derivation2014In: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING, CP 2014, 2014, p. 938-942Conference paper (Refereed)
    Abstract [en]

    When implementing a propagator for a constraint, one must decide about variants: When implementing min, should one also implement max? Should one implement linear equations both with and without coefficients? Constraint variants are ubiquitous: implementing them requires considerable effort, but yields better performance. This abstract shows how to use views to derive propagator variants where derived propagators are perfect in that they inherit essential properties such as correctness and domain and bounds consistency. Techniques for systematically deriving propagators are developed, and the abstract sketches an implementation architecture for views that is independent of the underlying constraint programming system. Evaluation of views implemented in Gecode shows that derived propagators are efficient and that views often incur no overhead. Views have proven essential for implementing Gecode, substantially reducing the amount of code that needs to be written and maintained.

  • 47.
    Schulte, Christian
    et al.
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Tack, Guido
    National ICT Australia (NICTA), Faculty of Information Technology, Monash Universit.
    View-based propagator derivation2013In: Constraints, ISSN 1383-7133, E-ISSN 1572-9354, Vol. 18, no 1, p. 75-107Article in journal (Refereed)
    Abstract [en]

    When implementing a propagator for a constraint, one must decide about variants: When implementing min, should one also implement max Should one implement linear constraints both with unit and non-unit coefficients Constraint variants are ubiquitous: implementing them requires considerable (if not prohibitive) effort and decreases maintainability, but will deliver better performance than resorting to constraint decomposition. This paper shows how to use views to derive propagator variants, combining the efficiency of dedicated propagator implementations with the simplicity and effortlessness of decomposition. A model for views and derived propagators is introduced. Derived propagators are proved to be perfect in that they inherit essential properties such as correctness and domain and bounds consistency. Techniques for systematically deriving propagators such as transformation, generalization, specialization, and type conversion are developed. The paper introduces an implementation architecture for views that is independent of the underlying constraint programming system. A detailed evaluation of views implemented in Gecode shows that derived propagators are efficient and that views often incur no overhead. Views have proven essential for implementing Gecode, substantially reducing the amount of code that needs to be written and maintained.

  • 48.
    Schulte, Christian
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Tack, Guido
    Views and Iterators for Generic Constraint Implementations2006In: Recent Advances in Constraints, Springer Berlin/Heidelberg, 2006, Vol. 3978, p. 118-132Chapter in book (Refereed)
  • 49.
    Schulte, Christian
    et al.
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture (Closed 20120101), Software and Computer Systems, SCS (Closed 20120101).
    Tack, Guido
    Weakly Monotonic Propagators2009In: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING / [ed] Gent IP, 2009, Vol. 5732, p. 723-730Conference paper (Refereed)
    Abstract [en]

    Today's models for propagation-based constraint solvers require propagators as implementations of constraints to be at least contracting and monotonic. These models do not comply with reality: today's constraint, programming systems actually use non-monotonic propagators. This paper introduces the first realistic model of constraint propagation by assuming it propagator to be weakly monotonic (complying with the constraint it implements). Weak monotonicity is shown to be the minimal property that guarantees constraint propagation to be sound and complete. The important insight is that weak monotonicity makes propagation in combination. with search well behaved. A case study suggests that non-monotonicity call be seen as all opportunity for more efficient propagation.

  • 50. Tack, Guido
    et al.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Smolka, Gert
    Generating propagators for finite set constraints2006In: Principles And Practice Of Constraint Programming - CP 2006 / [ed] Benhamou, F, 2006, Vol. 4204, p. 575-589Conference paper (Refereed)
    Abstract [en]

    Ideally, programming propagators as implementations of constraints should be an entirely declarative specification process for a large class of constraints: a high-level declarative specification is automatically translated into an efficient propagator. This paper introduces the use of existential monadic second-order logic as declarative specification language for finite set propagators. The approach taken in the paper is to automatically derive projection propagators (involving a single variable only) implementing constraints described by formulas. By this, the paper transfers the ideas of indexicals to finite set constraints while considerably increasing the level of abstraction available with indexicals. The paper proves soundness and completeness of the derived propagators and presents a run-time analysis, including techniques for efficiently executing projectors for n-ary constraints.

12 1 - 50 of 53
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf