Compiler management of communication and parallelism for quantum computation

Jeff Heckey, Shruti Patil, Ali JavadiAbhari, Adam Holmes, Daniel Kudrow, Kenneth R. Brown, Diana Franklin, Frederic T. Chong, Margaret Rose Martonosi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationASPLOS 2015 - 20th International Conference on Architectural Support for Programming Languages and Operating Systems
PublisherAssociation for Computing Machinery
Pages445-456
Number of pages12
ISBN (Electronic)9781450328357
DOIs
StatePublished - Mar 14 2015
Event20th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2015 - Istanbul, Turkey
Duration: Mar 14 2015Mar 18 2015

Publication series

NameInternational Conference on Architectural Support for Programming Languages and Operating Systems - ASPLOS
Volume2015-January

Other

Other20th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2015
CountryTurkey
CityIstanbul
Period3/14/153/18/15

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture

Keywords

  • Compilers
  • LLVM
  • Quantum
  • Scheduling

Fingerprint Dive into the research topics of 'Compiler management of communication and parallelism for quantum computation'. Together they form a unique fingerprint.

Cite this