Change search
Link to record
Permanent link

Direct link
BETA
Publications (10 of 124) Show all publications
Castaneda Lozano, R., Carlsson, M., Blindell, G. & Schulte, C. (2019). Combinatorial register allocation and instruction scheduling. ACM Transactions on Programming Languages and Systems, 41(3), Article ID 17.
Open this publication in new window or tab >>Combinatorial register allocation and instruction scheduling
2019 (English)In: ACM Transactions on Programming Languages and Systems, ISSN 0164-0925, E-ISSN 1558-4593, Vol. 41, no 3, article id 17Article in journal (Refereed) Published
Abstract [en]

This article introduces a combinatorial optimization approach to register allocation and instruction scheduling, two central compiler problems. Combinatorial optimization has the potential to solve these problems optimally and to exploit processor-specific features readily. Our approach is the first to leverage this potential in practice: it captures the complete set of program transformations used in state-of-the-art compilers, scales to medium-sized functions of up to 1,000 instructions, and generates executable code. This level of practicality is reached by using constraint programming, a particularly suitable combinatorial optimization technique. Unison, the implementation of our approach, is open source, used in industry, and integrated with the LLVM toolchain. An extensive evaluation confirms that Unison generates better code than LLVM while scaling to medium-sized functions. The evaluation uses systematically selected benchmarks from MediaBench and SPEC CPU2006 and different processor architectures (Hexagon, ARM, MIPS). Mean estimated speedup ranges from 1.1% to 10% and mean code size reduction ranges from 1.3% to 3.8% for the different architectures. A significant part of this improvement is due to the integrated nature of the approach. Executing the generated code on Hexagon confirms that the estimated speedup results in actual speedup. Given a fixed time limit, Unison solves optimally functions of up to 946 instructions, nearly an order of magnitude larger than previous approaches. The results show that our combinatorial approach can be applied in practice to trade compilation time for code quality beyond the usual compiler optimization levels, identify improvement opportunities in heuristic algorithms, and fully exploit processor-specific features.

Place, publisher, year, edition, pages
Association for Computing Machinery, 2019
Keywords
Combinatorial optimization, Instruction scheduling, Register allocation
National Category
Natural Sciences
Identifiers
urn:nbn:se:ri:diva-39654 (URN)10.1145/3332373 (DOI)2-s2.0-85068443848 (Scopus ID)
Note

 Funding details: Vetenskapsrådet, VR, 621-2011-6229; Funding text 1: This article is partially based on preliminary work presented at the Principles and Practice of Constraint Programming (2012) [20]; Languages, Compilers, and Tools for Embedded Systems (2014) [21]; and Compiler Construction (2016) [22]conferences. Compared to the preliminary work, this article is completely restructured and rewritten, completes the combinatorial model with rematerialization, proposes extensions to capture additional program transformations and processor-specific features, and contributes a more exhaustive evaluation. Additions to the evaluation include more benchmarks and processors, evidence of the fundamental benefit of the integrated approach, an in-depth study of scalability, and actual execution measurements. This work has been partially funded by Ericsson AB and the Swedish Research Council (VR) under grant 621-2011-6229. Authors’ addresses: R. C. Lozano, RISE SICS, Electrum 229, Kista, 164 40, Sweden, KTH Royal Institute of Technology, School of Electrical Engineering and Computer Science, Electrum 229, Kista, 164 40, Sweden; email: roberto.castaneda@ri.se; M. Carlsson, RISE SICS, Electrum 229, Kista, 164 40, Sweden; email: mats.carlsson@ri.se; G. H. Blindell, KTH Royal Institute of Technology, School of Electrical Engineering and Computer Science, Electrum 229, Kista, 164 40, Sweden; email: ghb@kth.se; C. Schulte, KTH Royal Institute of Technology, School of Electrical Engineering and Computer Science, Electrum 229, Kista, 164 40, Sweden, RISE SICS, Electrum 229, Kista, 164 40, Sweden; email: cschulte@kth.se. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2019 Association for Computing Machinery. 0164-0925/2019/07-ART17 $15.00 https://doi.org/10.1145/3332373

Available from: 2019-08-07 Created: 2019-08-07 Last updated: 2019-08-07Bibliographically approved
Dubois, C., Grinchtein, O., Pearson, J. & Carlsson, M. (2018). Exploring Properties of a Telecommunication Protocol with Message Delay Using Interactive Theorem Prover. In: Einar Broch Johnsen and Ina Schaefer (Ed.), International Conference on Software Engineering and Formal Methods: . Paper presented at International Conference on Software Engineering and Formal Methods (SEFM 2018), part of STAF 2018 (pp. 239-253).
Open this publication in new window or tab >>Exploring Properties of a Telecommunication Protocol with Message Delay Using Interactive Theorem Prover
2018 (English)In: International Conference on Software Engineering and Formal Methods / [ed] Einar Broch Johnsen and Ina Schaefer, 2018, p. 239-253Conference paper, Published paper (Refereed)
Abstract [en]

An important task of testing a telecommunication protocol consists in analysing logs. The goal of log analysis is to check that the timing and the content of transmitted messages comply with specification. In order to perform such checks, protocols can be described using a constraint modelling language. In this paper we focus on a complex protocol where some messages can be delayed. Simply introducing variables for possible delays for all messages in the constraint model can drastically increase the complexity of the problem. However, some delays can be calculated, but this calculation is difficult to do by hand and to justify. We present an industrial application of the Coq proof assistant to prove a property of a 4G protocol and validate a constraint model. By using interactive theorem proving we derived constraints for message delays of the protocol and found missing constraints in the initial model.

Series
Lecture Notes in Computer Science ; 10886
Keywords
Testing of telecommunication protocol; Constraint programming; Formal proof; Coq
National Category
Computer Systems
Identifiers
urn:nbn:se:ri:diva-34224 (URN)10.1007/978-3-319-92970-5_15 (DOI)2-s2.0-85049015507 (Scopus ID)978-3-319-92969-9 (ISBN)978-3-319-92970-5 (ISBN)
Conference
International Conference on Software Engineering and Formal Methods (SEFM 2018), part of STAF 2018
Available from: 2018-07-17 Created: 2018-07-17 Last updated: 2019-01-08Bibliographically approved
Dekker, J. J., Björdal, G., Carlsson, M., Flener, P. & Monette, J.-N. (2017). Auto-tabling for subproblem presolving in MiniZinc. Constraints, 22(4), 512-529
Open this publication in new window or tab >>Auto-tabling for subproblem presolving in MiniZinc
Show others...
2017 (English)In: Constraints, ISSN 1383-7133, E-ISSN 1572-9354, Vol. 22, no 4, p. 512-529Article in journal (Refereed) Published
Abstract [en]

A well-known and powerful constraint model reformulation is to compute the solutions to a model part, say a custom constraint predicate, and tabulate them within an extensional constraint that replaces that model part. Despite the possibility of achieving higher solving performance, this tabling reformulation is often not tried, because it is tedious to perform; further, if successful, it obfuscates the original model. In order to encourage modellers to try tabling, we extend the MiniZinc toolchain to perform the automatic tabling of suitably annotated predicate definitions, without requiring any changes to solvers, thereby eliminating both the tedium and the obfuscation. Our experiments show that automated tabling yields the same tables as manual tabling, and that tabling is beneficial for solvers of several solving technologies.

Keywords
MiniZinc, Modelling methodology, Presolving, Tabling, Artificial intelligence, Constraint model, Original model, Solving performance, Constraint theory
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:ri:diva-32426 (URN)10.1007/s10601-017-9270-5 (DOI)2-s2.0-85020249248 (Scopus ID)
Funder
Swedish Research Council
Note

Funding details: Uppsala Universitet; Funding details: 2015-4910, VR, Vetenskapsrådet

Available from: 2017-10-31 Created: 2017-10-31 Last updated: 2018-08-24Bibliographically approved
Hjort Blindell, G., Carlsson, M., Lozano, R. C. & Schulte, C. (2017). Complete and practical universal instruction selection. ACM Transactions on Embedded Computing Systems, 16(5s), Article ID 119.
Open this publication in new window or tab >>Complete and practical universal instruction selection
2017 (English)In: ACM Transactions on Embedded Computing Systems, ISSN 1539-9087, E-ISSN 1558-3465, Vol. 16, no 5s, article id 119Article in journal (Refereed) Published
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.

Keywords
Code generation, Combinatorial optimization, Constraint programming, Instruction selection, Computer programming, Constraint theory, Embedded systems, Program processors, Bounding techniques, Function calls, Memory computations, Modern processors, Objective functions, Codes (symbols)
National Category
Natural Sciences
Identifiers
urn:nbn:se:ri:diva-33198 (URN)10.1145/3126528 (DOI)2-s2.0-85030692980 (Scopus ID)
Available from: 2018-01-31 Created: 2018-01-31 Last updated: 2018-08-23Bibliographically approved
Carlsson, M., Grinchtein, O. & Pearson, J. (2017). Modelling and Verification of User Interactions Using Constraint Programming. In: : . Paper presented at 2017 IEEE International Conference on Software Quality, Reliability and Security Companion (QRS-C), Prague, Czech Republic, 25-29 July 2017.
Open this publication in new window or tab >>Modelling and Verification of User Interactions Using Constraint Programming
2017 (English)Conference paper, Published paper (Refereed)
Abstract [en]

Graphical user interfaces are important components of today's software. User interfaces often require checking correctness of user interactions. In web applications such checks can be a part of the JavaScript code. User interfaces in web applications can evolve, some elements can be removed and new elements can be added. To check JavaScript code covers all possible incorrect scenarios in user interactions in web application, constraint programming is used. We use the MiniZinc constraint modelling language to model incorrect user behaviour and to convert JavaScript code into a constraint model. Then we perform an equivalence check to find deviations in JavaScript code. The approach was applied to design user interface of an industrial software product.

National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:ri:diva-32441 (URN)10.1109/QRS-C.2017.92 (DOI)2-s2.0-85034455918 (Scopus ID)
Conference
2017 IEEE International Conference on Software Quality, Reliability and Security Companion (QRS-C), Prague, Czech Republic, 25-29 July 2017
Available from: 2017-10-31 Created: 2017-10-31 Last updated: 2018-12-19Bibliographically approved
Beldiceanu, N., Carlsson, M., Derrien, A., Prud’Homme, C., Schutt, A. & Stuckey, P. (2017). Range-consistent forbidden regions of allen’s relations. In: : . Paper presented at 14th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, CPAIOR 2017. 5-8 June 2017 (pp. 21-29). Springer
Open this publication in new window or tab >>Range-consistent forbidden regions of allen’s relations
Show others...
2017 (English)Conference paper, Published paper (Refereed)
Abstract [en]

For all 8192 combinations of Allen’s 13 relations between one task with origin oi and fixed length ℓi and another task with origin oj and fixed length ℓj, this paper shows how to systematically derive a formula F (oj, oj, ℓi, ℓj), where oj and oj respectively denote the earliest and the latest origin of task j, evaluating to a set of integers which are infeasible for oi for the given combination. Such forbidden regions allow maintaining range-consistency for an Allen constraint.

Place, publisher, year, edition, pages
Springer, 2017
Series
LNCS ; 10335
Keywords
Computer programming, Operations research, Forbidden region, Constraint theory
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:ri:diva-31152 (URN)10.1007/978-3-319-59776-8_2 (DOI)2-s2.0-85020804195 (Scopus ID)9783319597751 (ISBN)
Conference
14th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, CPAIOR 2017. 5-8 June 2017
Note

Funding details: 640954, Horizon 2020; Funding text: The Nantes authors were partially supported both by the INRIA TASCMELB associated team and by the GRACeFUL project, which has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 640954.

Available from: 2017-08-23 Created: 2017-08-23 Last updated: 2018-08-24Bibliographically approved
Carlsson, M., Johansson, M. & Larson, J. (2017). Scheduling double round-robin tournaments with divisional play using constraint programming. European Journal of Operational Research, 259(3), 1180-1190
Open this publication in new window or tab >>Scheduling double round-robin tournaments with divisional play using constraint programming
2017 (English)In: European Journal of Operational Research, ISSN 0377-2217, E-ISSN 1872-6860, Vol. 259, no 3, p. 1180-1190Article in journal (Refereed) Published
Abstract [en]

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.

Keywords
Constraint programming, OR in sports, Scheduling, Computer programming, Constraint theory, Computational effort, Constraint programming model, Experimental evaluation, Integrated approach, Multi-step approaches, Round robin tournaments, Routers
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:ri:diva-29308 (URN)10.1016/j.ejor.2016.11.033 (DOI)2-s2.0-85008186432 (Scopus ID)
Available from: 2017-04-26 Created: 2017-04-26 Last updated: 2019-01-22Bibliographically approved
Carlsson, M., Gotlieb, A. & Marijan, D. (2017). Software product line test suite reduction with constraint optimization. In: : . Paper presented at 11th International Joint Conference on Software Technologies, ICSOFT 2016. 24 July 2016 through 26 July 2016 (pp. 68-87).
Open this publication in new window or tab >>Software product line test suite reduction with constraint optimization
2017 (English)Conference paper, Published paper (Refereed)
Abstract [en]

In many cases, Software Product Line Testing (SPLT) targets only the selection of test cases which cover product features or feature interactions. However, higher testing efficiency can be achieved through the selection of test cases with improved fault-revealing capabilities. By associating each test case a priority-value representing (or aggregating) different criteria, such as importance (in terms of fault discovered in previous test campaigns), duration or cost, it becomes possible to select a feature-covering test suite with improved capabilities. A crucial objective in SPLT then becomes to identify a test suite that optimizes reaching a specific goal (lower test duration or cost), while preserving full feature coverage. In this article, we revisit this problem with a new approach based on constraint optimization with the NValue and GlobalCardinality constraints and a sophisticated search heuristic. These constraints enforce the coverage of all features through the computation of max flows in a network flow representing the coverage relation. The computed max flows represent possible solutions which are further processed in order to determine the solution that optimizes the given objective function, e.g., the smallest test execution costs. Our approach is implemented in a tool called Flower/C and experimentally evaluated on both randomly generated instances and standard benchmarks. Comparing Flower/C with MiniSAT+ and Cplex, stateof-the-art tools for constraint optimization, we show that our approach is competitive with both tools on random instances and benchmarks. Our results show that MiniSAT+ is not competitive at all, whereas when the priority-value of each test case is uniformly set to 1, that Flower/C approaches Cplex in performance. We compare four different models of Flower/C, using different global constraints, and the one mixing different constraints shows the best performance with high reduction rates. These results open the door to an industrial adoption of the proposed technology.

Keywords
Feature coverage, Software product line testing, Test suite optimization, Test suite reduction, Computer software, Constrained optimization, Costs, Feature extraction, Heuristic algorithms, Optimization, Testing, Constraint optimizations, Feature interactions, Objective functions, Software Product Line, Test-execution cost, Software testing
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:ri:diva-31109 (URN)10.1007/978-3-319-62569-0_4 (DOI)2-s2.0-85026636393 (Scopus ID)9783319625683 (ISBN)
Conference
11th International Joint Conference on Software Technologies, ICSOFT 2016. 24 July 2016 through 26 July 2016
Note

Funding details: Cisco Systems; Funding details: Norges Forskningsråd; Funding text: We are grateful to Marius Liaeen from Cisco Systems, Norway and Alexandre Petillon for their participation to the discussion and initial work related to the approach described in the article. This work is partly supported by the Research Council of Norway (RCN) through the research-based innovation center Certus, under the SFI program.

Available from: 2017-08-28 Created: 2017-08-28 Last updated: 2018-08-24Bibliographically approved
Mossige, M., Gotlieb, A., Spieker, H., Meling, H. & Carlsson, M. (2017). Time-Aware Test Case Execution Scheduling for Cyber-Physical Systems. In: 23rd International Conference, CP 2017, Melbourne, VIC, Australia, August 28 – September 1, 2017, Proceedings: . Paper presented at CP 2017: Principles and Practice of Constraint Programming. (pp. 387-404).
Open this publication in new window or tab >>Time-Aware Test Case Execution Scheduling for Cyber-Physical Systems
Show others...
2017 (English)In: 23rd International Conference, CP 2017, Melbourne, VIC, Australia, August 28 – September 1, 2017, Proceedings, 2017, p. 387-404Conference paper, Published paper (Refereed)
Abstract [en]

Testing cyber-physical systems involves the execution of test cases on target-machines equipped with the latest release of a software control system. When testing industrial robots, it is common that the target machines need to share some common resources, e.g., costly hardware devices, and so there is a need to schedule test case execution on the target machines, accounting for these shared resources. With a large number of such tests executed on a regular basis, this scheduling becomes difficult to manage manually. In fact, with manual test execution planning and scheduling, some robots may remain unoccupied for long periods of time and some test cases may not be executed. This paper introduces TC-Sched, a time-aware method for automated test case execution scheduling. TC-Sched uses Constraint Programming to schedule tests to run on multiple machines constrained by the tests’ access to shared resources, such as measurement or networking devices. The CP model is written in SICStus Prolog and uses the Cumulatives global constraint. Given a set of test cases, a set of machines, and a set of shared resources, TC-Sched produces an execution schedule where each test is executed once with minimal time between when a source code change is committed and the test results are reported to the developer. Experiments reveal that TC-Sched can schedule 500 test cases over 100 machines in less than 4 min for 99.5% of the instances. In addition, TC-Sched largely outperforms simpler methods based on a greedy algorithm and is suitable for deployment on industrial robot testing.

Series
LNCS ; 10416
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:ri:diva-32442 (URN)10.1007/978-3-319-66158-2_25 (DOI)2-s2.0-85028694541 (Scopus ID)
Conference
CP 2017: Principles and Practice of Constraint Programming.
Note

Part of the Lecture Notes in Computer Science book series (LNCS, volume 10416)

Available from: 2017-10-31 Created: 2017-10-31 Last updated: 2019-01-10Bibliographically approved
Gotlieb, A., Carlsson, M., Liaaen, M., Marijan, D. & Petillon, A. (2016). Automated Regression Testing Using Constraint Programming. In: Proceedings of the Twenty-Eighth AAAI Conference on Innovative Applications (IAAI-16): . Paper presented at Twenty-Eighth Conference on Innovative Applications of Artificial Intelligence (IAAI-16), February 12-17, 2016, Phoenix, USA (pp. 4010-4015). AAAI Press
Open this publication in new window or tab >>Automated Regression Testing Using Constraint Programming
Show others...
2016 (English)In: Proceedings of the Twenty-Eighth AAAI Conference on Innovative Applications (IAAI-16), AAAI Press, 2016, p. 4010-4015Conference paper, Published paper (Refereed)
Abstract [en]

In software validation, regression testing aims to check the absence of regression faults in new releases of a software system. Typically, test cases used in regression testing are executed during a limited amount of time and are selected to check a given set of user requirements. When testing large systems, the number of regression tests grows quickly over the years, and yet the available time slot stays limited. In order to overcome this problem, an approach known as test suite reduction (TSR), has been developed in software engineering to select a smallest subset of test cases, so that each requirement remains covered at least once. However solving the TSR problem is difficult as the underlying optimization problem is NP-hard, but it is also crucial for vendors interested in reducing the time to market of new software releases. In this paper, we address regression testing and TSR with Constraint Programming (CP). More specifically, we propose new CP models to solve TSR that exploit global constraints, namely NValue and GCC. We reuse a set of preprocessing rules to reduce a priori each instance, and we introduce a structure-aware search heuristic. We evaluated our CP models and proposed improvements against existing approaches, including a simple greedy approach and MINTS, the state-of-the-art tool of the software engineering community. Our experiments show that CP outperforms both the greedy approach and MINTS when it is interfaced with MiniSAT, in terms of percentage of reduction and execution time. When MINTS is interfaced with CPLEX, we show that our CP model performs better only on percentage of reduction. Finally, by working closely with validation engineers from Cisco Systems, Norway, we integrated our CP model into an industrial regression testing process.

Place, publisher, year, edition, pages
AAAI Press, 2016
National Category
Computer Sciences
Identifiers
urn:nbn:se:ri:diva-30102 (URN)
Conference
Twenty-Eighth Conference on Innovative Applications of Artificial Intelligence (IAAI-16), February 12-17, 2016, Phoenix, USA
Available from: 2017-07-21 Created: 2017-07-21 Last updated: 2019-06-27Bibliographically approved
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0003-3079-8095

Search in DiVA

Show all publications
v. 2.35.7