| 1. |
- Castañeda Lozano, Roberto, 1986-, et al.
(författare)
-
Constraint-based register allocation and instruction scheduling
- 2012
-
Ingår i: Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 9783642335570 - 9783642335587 ; , s. 750-766
-
Konferensbidrag (refereegranskat)abstract
- 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. |
- Wessén, Johan, et al.
(författare)
-
A constraint programming model for the scheduling and workspace layout design of a dual-arm multi-tool assembly robot
- 2023
-
Ingår i: Constraints. - : Springer. - 1383-7133 .- 1572-9354. ; 28, s. 71-
-
Tidskriftsartikel (refereegranskat)abstract
- The generation of a robot program can be seen as a collection of sub-problems, where many combinations of some of these sub-problems are well studied. The performance of a robot program is strongly conditioned by the location of the tasks. However, the scope of previous methods does not include workspace layout design, likely missing high-quality solutions. In industrial applications, designing robot workspace layout is part of the commissioning. We broaden the scope and show how to model a dual-arm multi-tool robot assembly problem. Our model includes more robot programming sub-problems than previous methods, as well as workspace layout design. We propose a constraint programming formulation in MiniZinc that includes elements from scheduling and routing, extended with variable task locations. We evaluate the model on realistic assembly problems and workspaces, utilizing the dual-arm YuMi robot from ABB Ltd. We also evaluate redundant constraints and various formulations for avoiding arm-to-arm collisions. The best model variant quickly finds high-quality solutions for all problem instances. This demonstrates the potential of our approach as a valuable tool for a robot programmer. © 2023, The Author(s).
|
|
| 3. |
- Grinchtein, Olga, et al.
(författare)
-
A Constraint Optimisation Model for Analysis of Telecommunication Protocol Logs
- 2015. - 6
-
Ingår i: Tests and Proofs. - Cham : Springer International Publishing. - 9783319212142 - 9783319212159 ; , s. 137-154
-
Konferensbidrag (refereegranskat)abstract
- Testing a telecommunication protocol often requires protocol log analysis. A protocol log is a sequence of messages with timestamps. Protocol log analysis involves checking that the content of messages and timestamps are correct with respect to the protocol specification. We model a protocol specification using constraint programming (MiniZinc), and we present an approach where a constraint solver is used to perform protocol log analysis. Our case study is the Public Warning System service, which is a part of the Long Term Evolution (LTE) 4G standard. We were able to analyse logs containing more than 3000 messages with more than 4000 errors.
|
|
| 4. |
- Beldiceanu, Nicolas, et al.
(författare)
-
On matrices, automata, and double counting
- 2010
-
Ingår i: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. - Berlin : Springer-Verlag. ; , s. 10-24
-
Konferensbidrag (refereegranskat)
|
|
| 5. |
- Carlsson, Mats, et al.
(författare)
-
Scheduling double round-robin tournaments with divisional play using constraint programming
- 2017
-
Ingår i: European Journal of Operational Research. - : Elsevier BV. - 0377-2217 .- 1872-6860. ; 259:3, s. 1180-1190
-
Tidskriftsartikel (refereegranskat)abstract
- We study a tournament format that extends a traditional double round-robin format with divisional single round-robin tournaments. Elitserien, the top Swedish handball league, uses such a format for its league schedule. We present a constraint programming model that characterizes the general double round-robin plus divisional single round-robin format. This integrated model allows scheduling to be performed in a single step, as opposed to common multistep approaches that decompose scheduling into smaller problems and possibly miss optimal solutions. In addition to general constraints, we introduce Elitserien-specific requirements for its tournament. These general and league-specific constraints allow us to identify implicit and symmetry-breaking properties that reduce the time to solution from hours to seconds. A scalability study of the number of teams shows that our approach is reasonably fast for even larger league sizes. The experimental evaluation of the integrated approach takes considerably less computational effort to schedule Elitserien than does the previous decomposed approach.
|
|
| 6. |
- Castañeda Lozano, Roberto, 1986-
(författare)
-
Integrated Register Allocation and Instruction Scheduling with Constraint Programming
- 2014
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This dissertation proposes a combinatorial model, program representations, and constraint solving techniques for integrated register allocation and instruction scheduling in compiler back-ends. In contrast to traditional compilers based on heuristics, the proposed approach generates potentially optimal code by considering all trade-offs between interdependent decisions as a single optimization problem.The combinatorial model is the first to handle a wide array of global register allocation subtasks, including spill code optimization, ultimate coalescing, register packing, and register bank assignment, as well as instruction scheduling for Very Long Instruction Word (VLIW) processors. The model is based on three novel, complementary program representations: Linear Static Single Assignment for global register allocation; copy extension for spilling, basic coalescing, and register bank assignment; and alternative temporaries for spill code optimization and ultimate coalescing. Solving techniques are proposed that exploit the program representation properties for scalability.The model, program representations, and solving techniques are implemented in Unison, a code generator that delivers potentially optimal code while scaling to medium-size functions. Thorough experiments show that Unison: generates faster code (up to 41% with a mean improvement of 7%) than LLVM (a state-of-the-art compiler) for Hexagon (a challenging VLIW processor), generates code that is competitive with LLVM for MIPS32 (a simpler RISC processor), is robust across different benchmarks such as MediaBench and SPECint 2006, scales up to medium-size functions of up to 1000 instructions, and adapts easily to different optimization criteria.The contributions of this dissertation are significant. They lead to a combinatorial approach for integrated register allocation and instruction scheduling that is, for the first time, practical (it robustly scales to medium-size functions) and effective (it yields better code than traditional heuristic approaches).
|
|
| 7. |
- Wessén, Johan Ludde, et al.
(författare)
-
Scheduling of Dual-Arm Multi-Tool Assembly Robots and Workspace Layout Optimization
- 2020
-
Ingår i: Proceedings of 17th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research. - Cham : Springer International Publishing. ; , s. 511-520
-
Konferensbidrag (refereegranskat)abstract
- The profitability of any assembly robot installation dependson the production throughput, and to an even greater extent on incurred costs. Most of the cost comes from manually designing the layoutand programming the robot as well as production downtime. With ever smaller production series, fewer products share this cost. In this work,we present the dual arm assembly program as an integrated routing andscheduling problem with complex arm-to-arm collision avoidance. Wealso present a set of high-level layout decisions, and we propose a unifiedCP model to solve the joint problem. The model is evaluated on realistic instances and real data. The model finds high-quality solutions in shorttime, and proves optimality for all evaluated problem instances, whichd emonstrates the potential of the approach.
|
|
| 8. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Linking Prefixes and Suffixes for Constraints Encoded Using Automata with Accumulators
- 2014. - 7
-
Ingår i: Principles and Practice of Constraint Programming. - Cham : Springer International Publishing. - 9783319104270 ; , s. 142-157
-
Konferensbidrag (refereegranskat)abstract
- Consider a constraint on a sequence of variables functionally determining a result variable that is unchanged under reversal of the sequence. Most such constraints have a compact encoding via an automaton augmented with accumulators, but it is unknown how to maintain domain consistency efficiently for most of them. Using such an automaton for such a constraint, we derive an implied constraint between the result variables for a sequence, a prefix thereof, and the corresponding suffix. We show the usefulness of this implied constraint in constraint solving, both by local search and by propagation-based systematic search.
|
|
| 9. |
|
|
| 10. |
- Beldiceanu, Nicolas, et al.
(författare)
-
On the reification of global constraints
- 2013
-
Ingår i: Constraints. - : Springer Science and Business Media LLC. - 1383-7133 .- 1572-9354. ; 18:1, s. 1-6
-
Tidskriftsartikel (refereegranskat)
|
|
