Skip to main content
construction release_alert
Scholars@Duke will be undergoing maintenance April 11-15. Some features may be unavailable during this time.
cancel
Journal cover image

Compiler management of communication and parallelism for quantum computation

Publication ,  Conference
Heckey, J; Patil, S; JavadiAbhari, A; Holmes, A; Kudrow, D; Brown, KR; Franklin, D; Chong, FT; Martonosi, M
Published in: International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS
March 14, 2015

Quantum computing (QC) offers huge promise to accelerate a range of computationally intensive benchmarks. Quantum computing is limited, however, by the challenges of decoherence: i.e., a quantum state can only be maintained for short windows of time before it decoheres. While quantum error correction codes can protect against decoherence, fast execution time is the best defense against decoherence, so efficient architectures and effective scheduling algorithms are necessary. This paper proposes the Multi-SIMD QC architecture and then proposes and evaluates effective schedulers to map benchmark descriptions onto Multi-SIMD architectures. The Multi-SIMD model consists of a small number of SIMD regions, each of which may support operations on up to thousands of qubits per cycle. Efficient Multi-SIMD operation requires efficient scheduling. This work develops schedulers to reduce communication requirements of qubits between operating regions, while also improving parallelism. We find that communication to global memory is a dominant cost in QC. We also note that many quantum benchmarks have long serial operation paths (although each operation may be data parallel). To exploit this characteristic, we introduce Longest-Path-First Scheduling (LPFS) which pins operations to SIMD regions to keep data in-place and reduce communication to memory. The use of small, local scratchpad memories also further reduces communication. Our results show a 3% to 308% improvement for LPFS over conventional scheduling algorithms, and an additional 3% to 64% improvement using scratchpad memories. Our work is the most comprehensive software-to-quantum toolflow published to date, with efficient and practical scheduling techniques that reduce communication and increase parallelism for full-scale quantum code executing up to a trillion quantum gate operations.

Duke Scholars

Published In

International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS

DOI

ISBN

9781450328357

Publication Date

March 14, 2015

Volume

2015-January

Start / End Page

445 / 456

Related Subject Headings

  • Software Engineering
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Heckey, J., Patil, S., JavadiAbhari, A., Holmes, A., Kudrow, D., Brown, K. R., … Martonosi, M. (2015). Compiler management of communication and parallelism for quantum computation. In International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS (Vol. 2015-January, pp. 445–456). https://doi.org/10.1145/2694344.2694357
Heckey, J., S. Patil, A. JavadiAbhari, A. Holmes, D. Kudrow, K. R. Brown, D. Franklin, F. T. Chong, and M. Martonosi. “Compiler management of communication and parallelism for quantum computation.” In International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS, 2015-January:445–56, 2015. https://doi.org/10.1145/2694344.2694357.
Heckey J, Patil S, JavadiAbhari A, Holmes A, Kudrow D, Brown KR, et al. Compiler management of communication and parallelism for quantum computation. In: International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS. 2015. p. 445–56.
Heckey, J., et al. “Compiler management of communication and parallelism for quantum computation.” International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS, vol. 2015-January, 2015, pp. 445–56. Scopus, doi:10.1145/2694344.2694357.
Heckey J, Patil S, JavadiAbhari A, Holmes A, Kudrow D, Brown KR, Franklin D, Chong FT, Martonosi M. Compiler management of communication and parallelism for quantum computation. International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS. 2015. p. 445–456.
Journal cover image

Published In

International Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS

DOI

ISBN

9781450328357

Publication Date

March 14, 2015

Volume

2015-January

Start / End Page

445 / 456

Related Subject Headings

  • Software Engineering