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 57) Show all publications
Kroll, L., Segeljakt, K., Schulte, C., Haridi, S. & Carbone, P. (2019). Arc: An IR for batch and stream programming. In: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI): . Paper presented at 17th ACM SIGPLAN International Symposium on Database Programming Languages, DBPL 2019, co-located with PLDI 2019, 23 June 2019 (pp. 53-58). Association for Computing Machinery (ACM)
Open this publication in new window or tab >>Arc: An IR for batch and stream programming
Show others...
2019 (English)In: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), Association for Computing Machinery (ACM), 2019, p. 53-58Conference paper, Published paper (Refereed)
Abstract [en]

In big data analytics, there is currently a large number of data programming models and their respective frontends such as relational tables, graphs, tensors, and streams. This has lead to a plethora of runtimes that typically focus on the efficient execution of just a single frontend. This fragmentation manifests itself today by highly complex pipelines that bundle multiple runtimes to support the necessary models. Hence, joint optimization and execution of such pipelines across these frontend-bound runtimes is infeasible. We propose Arc as the first unified Intermediate Representation (IR) for data analytics that incorporates stream semantics based on a modern specification of streams, windows and stream aggregation, to combine batch and stream computation models. Arc extends Weld, an IR for batch computation and adds support for partitioned, out-of-order stream and window operators which are the most fundamental building blocks in contemporary data streaming.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2019
Keywords
Data analytics, Intermediate representation, Stream processing
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:kth:diva-262617 (URN)10.1145/3315507.3330199 (DOI)2-s2.0-85071162040 (Scopus ID)9781450367189 (ISBN)
Conference
17th ACM SIGPLAN International Symposium on Database Programming Languages, DBPL 2019, co-located with PLDI 2019, 23 June 2019
Note

QC 20191017

Available from: 2019-10-17 Created: 2019-10-17 Last updated: 2019-10-17Bibliographically approved
Castañeda Lozano, R., Carlsson, M., Hjort 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 (ACM), 2019
Keywords
Combinatorial optimization, Instruction scheduling, Register allocation
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:kth:diva-262613 (URN)10.1145/3332373 (DOI)000501479500004 ()2-s2.0-85068443848 (Scopus ID)
Note

QC 20191024

Available from: 2019-10-24 Created: 2019-10-24 Last updated: 2020-01-08Bibliographically approved
Frimodig, S. & Schulte, C. (2019). Models for Radiation Therapy Patient Scheduling. In: 25th International Conference on Principles and Practice of Constraint Programming, CP 2019: . Paper presented at 25th International Conference on Principles and Practice of Constraint Programming, CP 2019; Stamford; United States; 30 September 2019 through 4 October 2019 (pp. 421-437). Springer, 11802
Open this publication in new window or tab >>Models for Radiation Therapy Patient Scheduling
2019 (English)In: 25th International Conference on Principles and Practice of Constraint Programming, CP 2019, Springer, 2019, Vol. 11802, p. 421-437Conference paper, Published paper (Refereed)
Abstract [en]

In Europe, around half of all patients diagnosed with cancer are treated with radiation therapy. To reduce waiting times, optimizing the use of linear accelerators for treatment is crucial. This paper introduces an Integer Programming (IP) and two Constraint Programming (CP) models for the non-block radiotherapy patient scheduling problem. Patients are scheduled considering priority, pattern, duration, and start day of their treatment. The models include expected future patient arrivals. Treatment time of the day is included in the models as time windows which enable more realistic objectives and constraints. The models are thoroughly evaluated for multiple different scenarios, altering: planning day, machine availability, arrival rates, patient backlog, and the number of time windows in a day. The results demonstrate that the CP models find feasible solutions earlier, while the IP model reaches optimality considerably faster.

Place, publisher, year, edition, pages
Springer, 2019
Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 11802
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:kth:diva-265123 (URN)10.1007/978-3-030-30048-7_25 (DOI)2-s2.0-85075737127 (Scopus ID)9783030300470 (ISBN)
Conference
25th International Conference on Principles and Practice of Constraint Programming, CP 2019; Stamford; United States; 30 September 2019 through 4 October 2019
Note

QC 20191211

Available from: 2019-12-11 Created: 2019-12-11 Last updated: 2019-12-11Bibliographically approved
Castañeda Lozano, R. & Schulte, C. (2019). Survey on Combinatorial Register Allocation and Instruction Scheduling. ACM Computing Surveys, 52(3), Article ID 62.
Open this publication in new window or tab >>Survey on Combinatorial Register Allocation and Instruction Scheduling
2019 (English)In: ACM Computing Surveys, ISSN 0360-0300, E-ISSN 1557-7341, Vol. 52, no 3, article id 62Article in journal (Refereed) Published
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 past 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 article 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
ASSOC COMPUTING MACHINERY, 2019
Keywords
Combinatorial optimization, register allocation, instruction scheduling
National Category
Computer Sciences
Identifiers
urn:nbn:se:kth:diva-257823 (URN)10.1145/3200920 (DOI)000481570600019 ()2-s2.0-85068049964 (Scopus ID)
Note

QC 20190906

Available from: 2019-09-06 Created: 2019-09-06 Last updated: 2019-09-06Bibliographically approved
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: 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)000427961400004 ()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: 2019-10-29Bibliographically 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)000364707100042 ()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: 2019-10-28Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-6283-7004

Search in DiVA

Show all publications