Change search
Link to record
Permanent link

Direct link
BETA
Schulte, Christian, ProfessorORCID iD iconorcid.org/0000-0002-6283-7004
Alternative names
Publications (10 of 54) Show all publications
Ingmar, L. & Schulte, C. (2018). Making Compact-Table Compact. In: 24th International Conference on the Principles and Practice of Constraint Programming, CP 2018: . Paper presented at 24th International Conference on the Principles and Practice of Constraint Programming, CP 2018, Lille, France, 27 August 2018 through 31 August 2018 (pp. 210-218). Springer, 11008
Open this publication in new window or tab >>Making Compact-Table Compact
2018 (English)In: 24th International Conference on the Principles and Practice of Constraint Programming, CP 2018, Springer, 2018, Vol. 11008, p. 210-218Conference paper, Published paper (Refereed)
Abstract [en]

The compact-table propagator for table constraints appears to be a strong candidate for inclusion into any constraint solver due to its efficiency and simplicity. However, successful integration into a constraint solver based on copying rather than trailing is not obvious: while the underlying bit-set data structure is sparse for efficiency it is not compact for memory, which is essential for a copying solver. The paper introduces techniques to make compact-table an excellent fit for a copying solver. The key is to make sparse bit-sets dynamically compact (only their essential parts occupy memory and their implementation is dynamically adapted during search) and tables shared (their read-only parts are shared among copies). Dynamically compact bit-sets reduce peak memory by 7.2% and runtime by 13.6% on average and by up to 66.3% and 33.2%. Shared tables even further reduce runtime and memory usage. The reduction in runtime exceeds the reduction in memory and a cache analysis indicates that our techniques might also be beneficial for trailing solvers. The proposed implementation has replaced Gecode’s original implementations as it runs on average almost an order of magnitude faster while using half the memory.

Place, publisher, year, edition, pages
Springer, 2018
Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 11008
National Category
Computer Engineering
Identifiers
urn:nbn:se:kth:diva-238350 (URN)10.1007/978-3-319-98334-9_14 (DOI)2-s2.0-85053157546 (Scopus ID)9783319983332 (ISBN)
Conference
24th International Conference on the Principles and Practice of Constraint Programming, CP 2018, Lille, France, 27 August 2018 through 31 August 2018
Note

QC 20181113

Available from: 2018-11-13 Created: 2018-11-13 Last updated: 2018-12-17Bibliographically approved
Castañeda Lozano, R. & Schulte, C. (2018). Survey on Combinatorial Register Allocation and Instruction Scheduling. ACM Computing Surveys
Open this publication in new window or tab >>Survey on Combinatorial Register Allocation and Instruction Scheduling
2018 (English)In: ACM Computing Surveys, ISSN 0360-0300, E-ISSN 1557-7341Article in journal (Refereed) In press
Abstract [en]

Register allocation (mapping variables to processor registers or memory) and instruction scheduling (reordering instructions to increase instruction-level parallelism) are essential tasks for generating efficient assembly code in a compiler. In the last three decades, combinatorial optimization has emerged as an alternative to traditional, heuristic algorithms for these two tasks. Combinatorial optimization approaches can deliver optimal solutions according to a model, can precisely capture trade-offs between conflicting decisions, and are more flexible at the expense of increased compilation time.

This paper provides an exhaustive literature review and a classification of combinatorial optimization approaches to register allocation and instruction scheduling, with a focus on the techniques that are most applied in this context: integer programming, constraint programming, partitioned Boolean quadratic programming, and enumeration. Researchers in compilers and combinatorial optimization can benefit from identifying developments, trends, and challenges in the area; compiler practitioners may discern opportunities and grasp the potential benefit of applying combinatorial optimization.

Place, publisher, year, edition, pages
ACM Press, 2018
National Category
Computer Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-232189 (URN)
Funder
Swedish Research Council, 621-2011-6229
Note

QC 20180823

Available from: 2018-07-13 Created: 2018-07-13 Last updated: 2018-12-11Bibliographically approved
Hjort Blindell, G., Carlsson, M., Castañeda Lozano, R. & Schulte, C. (2017). Complete and Practical Universal Instruction Selection. Paper presented at International Conferences on Compilers, Architectures and Synthesis for Embedded Systems. ACM Transactions on Embedded Computing Systems
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-3465Article 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.

Place, publisher, year, edition, pages
ACM Press, 2017
Keywords
instruction selection, code generation, constraint programming, combinatorial optimization
National Category
Computer Systems Embedded Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-213968 (URN)10.1145/3126528 (DOI)000414353800002 ()2-s2.0-85030692980 (Scopus ID)
Conference
International Conferences on Compilers, Architectures and Synthesis for Embedded Systems
Funder
Swedish Research Council, 621-2011-6229
Note

QC 20170908

Available from: 2017-09-07 Created: 2017-09-07 Last updated: 2018-01-03Bibliographically approved
Corcoran, D., Andimeh, L., Ermedahl, A., Kreuger, P. & Schulte, C. (2017). Data Driven Selection of DRX for Energy Efficient 5G RAN. In: 2017 13TH INTERNATIONAL CONFERENCE ON NETWORK AND SERVICE MANAGEMENT (CNSM): . Paper presented at 13th International Conference on Network and Service Management (CNSM), NOV 26-30, 2017, Tokyo, JAPAN. IEEE
Open this publication in new window or tab >>Data Driven Selection of DRX for Energy Efficient 5G RAN
Show others...
2017 (English)In: 2017 13TH INTERNATIONAL CONFERENCE ON NETWORK AND SERVICE MANAGEMENT (CNSM), IEEE , 2017Conference paper, Published 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.

Place, publisher, year, edition, pages
IEEE, 2017
Series
International Conference on Network and Service Management, ISSN 2165-9605
Keywords
Software architecture, 5G mobile communication, Adaptive systems, Energy efficiency, Green computing
National Category
Communication Systems
Identifiers
urn:nbn:se:kth:diva-228174 (URN)000427961400004 ()978-3-9018-8298-2 (ISBN)
Conference
13th International Conference on Network and Service Management (CNSM), NOV 26-30, 2017, Tokyo, JAPAN
Note

QC 20180521

Available from: 2018-05-21 Created: 2018-05-21 Last updated: 2018-12-11Bibliographically approved
Corcoran, D., Andimeh, L., Ermedahl, A., Kreuger, P. & Schulte, C. (2017). Data Driven Selection of DRX for Energy Efficient 5G RAN. In: 13th International Conference on Network and Service Management (CNSM), 2017: . Paper presented at 13th International Conference on Network and Service Management, CNSM 2017, Tokyo, Japan, 26 November 2017 through 30 November 2017 (pp. 1-9). IEEE conference proceedings
Open this publication in new window or tab >>Data Driven Selection of DRX for Energy Efficient 5G RAN
Show others...
2017 (English)In: 13th International Conference on Network and Service Management (CNSM), 2017, IEEE conference proceedings, 2017, p. 1-9Conference paper, Published 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.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2017
National Category
Computer Sciences
Identifiers
urn:nbn:se:kth:diva-225402 (URN)10.23919/CNSM.2017.8255972 (DOI)2-s2.0-85046680815 (Scopus ID)
Conference
13th International Conference on Network and Service Management, CNSM 2017, Tokyo, Japan, 26 November 2017 through 30 November 2017
Note

QC 20180507

Available from: 2018-04-19 Created: 2018-04-19 Last updated: 2018-12-11Bibliographically approved
Scott, J. D., Flener, P., Pearson, J. & Schulte, C. (2017). Design and implementation of bounded-length sequence variables. In: 14th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, CPAIOR 2017: . Paper presented at 14th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, CPAIOR 2017, Padova, Italy, 5 June 2017 through 8 June 2017 (pp. 51-67). Springer, 10335
Open this publication in new window or tab >>Design and implementation of bounded-length sequence variables
2017 (English)In: 14th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, CPAIOR 2017, Springer, 2017, Vol. 10335, p. 51-67Conference paper, Published paper (Refereed)
Abstract [en]

We present the design and implementation of bounded -length sequence (BLS) variables for a CP solver. The domain of a BLS variable is represented as the combination of a set of candidate lengths and a sequence of sets of candidate characters. We show how this representation, together with requirements imposed by propagators, affects the implementation of BLS variables for a copying CP solver, most importantly the closely related decisions of data structure, domain restriction operations, and propagation events. The resulting implementation outperforms traditional bounded-length string representations for CP solvers, which use a fixed-length array of candidate characters and a padding symbol.

Place, publisher, year, edition, pages
Springer, 2017
Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 10335
National Category
Other Engineering and Technologies
Identifiers
urn:nbn:se:kth:diva-210288 (URN)10.1007/978-3-319-59776-8_5 (DOI)000434086200005 ()2-s2.0-85020813669 (Scopus ID)9783319597751 (ISBN)
Conference
14th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, CPAIOR 2017, Padova, Italy, 5 June 2017 through 8 June 2017
Funder
Swedish Research Council, 2015-4910
Note

QC 20170630

Available from: 2017-06-30 Created: 2017-06-30 Last updated: 2018-12-11Bibliographically approved
Hjort Blindell, G., Castañeda Lozano, R., Carlsson, M. & Schulte, C. (2015). Modeling Universal Instruction Selection. In: Gilles Pesant (Ed.), Principles and Practice of Constraint Programming: 21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings. Paper presented at 21st International Conference on Principles and Practice of Constraint Programming,August 31-September 4, 2015, Ireland (pp. 609-626). Springer, 9255
Open this publication in new window or tab >>Modeling Universal Instruction Selection
2015 (English)In: 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, Published 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.

Place, publisher, year, edition, pages
Springer, 2015
Series
Lecture Notes in Computer Science ; 9255
Keywords
instruction selection, global code motion, code generation, optimizing compilers, program representations, modern processor architectures
National Category
Computer Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-169684 (URN)10.1007/978-3-319-23219-5_42 (DOI)2-s2.0-84944558675 (Scopus ID)978-3-319-23219-5 (ISBN)
Conference
21st International Conference on Principles and Practice of Constraint Programming,August 31-September 4, 2015, Ireland
Funder
Swedish Research Council, VR 621-2011-6229
Note

QC 20150828

Available from: 2015-06-22 Created: 2015-06-22 Last updated: 2015-08-28Bibliographically approved
Lozano, R. C., Carlsson, M., Hjort Blindell, G. & Schulte, C. (2014). Combinatorial Spill Code Optimization and Ultimate Coalescing. SIGPLAN notices, 49(5), 23-32
Open this publication in new window or tab >>Combinatorial Spill Code Optimization and Ultimate Coalescing
2014 (English)In: SIGPLAN notices, ISSN 0362-1340, E-ISSN 1558-1160, Vol. 49, no 5, p. 23-32Article in journal (Refereed) Published
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.

Keywords
spill code optimization, ultimate coalescing, combinatorial optimization, register allocation, instruction scheduling
National Category
Computer Systems
Identifiers
urn:nbn:se:kth:diva-154398 (URN)10.1145/2597809.2597815 (DOI)000341937800004 ()2-s2.0-84905660668 (Scopus ID)
Funder
Swedish Research Council, VR 621-2011-6229
Note

QC 20141021

Available from: 2014-10-21 Created: 2014-10-20 Last updated: 2018-07-13Bibliographically approved
Castañeda Lozano, R. & Schulte, C. (2014). Survey on Combinatorial Register Allocation and Instruction Scheduling.
Open this publication in new window or tab >>Survey on Combinatorial Register Allocation and Instruction Scheduling
2014 (English)Report (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.

National Category
Computer Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-154598 (URN)
Funder
Vinnova, VR 621-2011-6229
Note

QC 20141117.

Archived at: arXiv:1409.7628 [cs.PL]

Available from: 2014-10-24 Created: 2014-10-24 Last updated: 2014-11-17Bibliographically approved
Schulte, C. & Tack, G. (2014). View-Based Propagator Derivation. In: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING, CP 2014: . Paper presented at 20th International Conference on the Principles and Practice of Constraint Programming (CP), SEP 08-12, 2014, Lyon, FRANCE (pp. 938-942).
Open this publication in new window or tab >>View-Based Propagator Derivation
2014 (English)In: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING, CP 2014, 2014, p. 938-942Conference paper, Published 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.

Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 8656
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:kth:diva-158858 (URN)10.1007/978-3-319-10428-7_71 (DOI)000345088200071 ()2-s2.0-84906247456 (Scopus ID)978-3-319-10428-7; 978-3-319-10427-0 (ISBN)
Conference
20th International Conference on the Principles and Practice of Constraint Programming (CP), SEP 08-12, 2014, Lyon, FRANCE
Note

QC 20150116

Available from: 2015-01-16 Created: 2015-01-12 Last updated: 2018-01-11Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-6283-7004

Search in DiVA

Show all publications