Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
The Journal of Supercomputing
Erschienen in: The Journal of Supercomputing 6/2022

13.01.2022

Temporal and spatial parallel processing of simulated quantum annealing on a multicore CPU

verfasst von: Hasitha Muthumala Waidyasooriya, Masanori Hariyama

Erschienen in: The Journal of Supercomputing | Ausgabe 6/2022

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Simulated quantum annealing (SQA) is a probabilistic approximation method to find a solution for a combinatorial optimization problem using a digital computer. It is possible to simulate large-scale optimization problems on a CPU due to its high external memory capacity. However, the processing time increases exponentially with the number of variables, and parallel implementation is difficult due to the serial nature of the quantum Monte Carlo algorithm used in SQA. In this paper, we propose a method to accelerate SQA on a multicore CPU, based on temporal and spatial parallel processing with high data localization. According to the experimental results using 16-core CPU, we achieved from 8 to 16 times speedup compared to single-core CPU implementations. The proposed method can be used to solve combinatorial optimization problems that have more than 64,000 variables, which was not possible using previous GPU- and FPGA-based accelerators.
Vorheriger Artikel Provably secure blockchain privacy-preserving smart contract centric dynamic group key agreement for large WSN
Nächster Artikel An reinforcement learning-based speech censorship chatbot system

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
1.
Kadowaki T, Nishimori H (1998) Quantum annealing in the transverse Ising model. Phys Rev E 58(5):5355CrossRef
2.
Kadowaki T (1998) Study of optimization problems by quantum annealing, Ph. D. Dissertation, Department of Physics, Tokyo Institute of Technology
3.
Schrijver A (2003) Combinatorial optimization: polyhedra and efficiency. Springer, BerlinMATH
4.
Neukart F, Compostella G, Seidel C, von Dollen D, Yarkoni S, Parney B (2017) Traffic flow optimization using a quantum annealer. Front ICT 4:29CrossRef
5.
Orús R, Mugel S, Lizaso E (2019) Quantum computing for finance: overview and prospects, Reviews in Physics, p. 100028
6.
Elsokkary N, Khan FS, La Torre D, Humble TS, Gottlieb J (2017) Financial Portfolio Management using D-Wave Quantum Optimizer: The Case of Abu Dhabi Securities Exchange, Oak Ridge National Lab.(ORNL), Oak Ridge, TN (United States), Tech. Rep
7.
8.
Ushijima-Mwesigwa H, Negre CF, Mniszewski SM (2017) Graph partitioning using quantum annealing on the d-wave system, in Proceedings of the Second International Workshop on Post Moores Era Supercomputing. ACM, pp. 22–29
9.
10.
Lanting T, Przybysz AJ, Smirnov AY, Spedalieri FM, Amin MH, Berkley AJ, Harris R, Altomare F, Boixo S, Bunyk P et al (2014) Entanglement in a quantum annealing processor. Phys Rev X 4(2):021041
11.
Yamaoka M, Yoshimura C, Hayashi M, Okuyama T, Aoki H, Mizuno H (2016) A 20k-spin Ising chip to solve combinatorial optimization problems with CMOS annealing. IEEE J Solid-State Circuits 51(1):303–309CrossRef
12.
Okuyama T, Hayashi M, Yamaoka M (2017) An Ising Computer Based on Simulated Quantum Annealing by Path Integral Monte Carlo Method, in IEEE International Conference on Rebooting Computing (ICRC). IEEE, pp. 1–6
13.
Waidyasooriya HM, Araki Y, Hariyama M (2018) Accelerator Architecture for Simulated Quantum Annealing Based on Resource-Utilization-Aware Scheduling and its Implementation Using OpenCL, in International Symposium on Intelligent Signal Processing and Communication Systems (ISPAC), pp. 336–340
14.
Aidyasooriya H, Hariyama M (2019) Highly-parallel fpga accelerator for simulated quantum annealing, IEEE Transactions on Emerging Topics in Computing
15.
Liu C-Y, Waidyasooriya HM, Hariyama M (2019), Data-transfer-bottleneck-less architecture for FPGA-based quantum annealing simulation, in, (2019) Seventh International Symposium on Computing and Networking (CANDAR). IEEE 2019: 164–170
16.
Liu Y, Waidyasooriya HM, Hariyama M (2021) Design space exploration for an FPGA-based quantum annealing simulator with interaction-coefficient-generators, The Journal of Supercomputing, pp. 1–17
17.
Weigel M (2012) Performance potential for simulating spin models on GPU. J Comput Phys 231(8):3064–3082CrossRef
18.
Cook C, Zhao H, Sato T, Hiromoto M, Tan SXD (2018) GPU based parallel Ising computing for combinatorial optimization problems in VLSI physical design, arXiv preprint arXiv:​1807.​10750
19.
Waidyasooriya HM, Hariyama M (2020) A GPU-Based Quantum Annealing Simulator for Fully-Connected Ising Models Utilizing Spatial and Temporal Parallelism, IEEE Access, vol. 8, pp. 67 929–67 939
20.
Zaribafiyan A, Marchand DJ, Rezaei SSC (2017) Systematic and deterministic graph minor embedding for cartesian products of graphs. Quantum Inf Process 16(5):136MathSciNetCrossRef
21.
Booth M, Reinhardt SP (2017) A. Roy, Partitioning optimization problems for hybrid classical/quantum execution, D-wave technical report series, pp. 01–09
22.
Stinchcombe R (1973) Ising model in a transverse field I. Basic theory. J Phys C Solid State Phys 6(15):2459CrossRef
23.
Pfeuty P, Elliott R (1971) The Ising model with a transverse field, II. Ground state properties. J Phys C Solid State Phys 4(15):2370CrossRef
24.
25.
Suzuki M (1976) Relationship between d-dimensional quantal spin systems and (d+1)-dimensional Ising systems: equivalence, critical exponents and systematic approximants of the partition function and spin correlations. Progress Theor Phys 56(5):1454–1469CrossRef
26.
Suzuki M, Miyashita S, Kuroda A (1977) Monte Carlo simulation of quantum spin systems. I. Progress Theor Phys 58(5):1377–1387MathSciNetCrossRef
27.
28.
29.
Wu Q, Hao J.-K (2012) A Memetic Approach for the Max-cut Problem, In International Conference on Parallel Problem Solving from Nature. Springer, pp. 297–306
30.
Wang Y, Lü Z, Glover F, Hao J-K (2013) Probabilistic grasp-tabu search algorithms for the ubqp problem. Comput Oper Res 40(12):3100–3107MathSciNetCrossRef
31.
Kochenberger GA, Hao J-K, Lü Z, Wang H, Glover F (2013) Solving large scale max cut problems via tabu search. J Heuristics 19(4):565–571CrossRef
32.
Benlic U, Hao J-K (2013) Breakout local search for the max-cutproblem. Eng Appl Artif Intell 26(3):1162–1173CrossRef
33.
34.
Metadaten
Titel
Temporal and spatial parallel processing of simulated quantum annealing on a multicore CPU
verfasst von
Hasitha Muthumala Waidyasooriya
Masanori Hariyama
Publikationsdatum
13.01.2022
Verlag
Springer US
Erschienen in
The Journal of Supercomputing / Ausgabe 6/2022
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-021-04242-0

Weitere Artikel der Ausgabe 6/2022

The Journal of Supercomputing 6/2022 Zur Ausgabe

Correction

Correction to: AnonSURP: an anonymous and secure ultralightweight RFID protocol for deployment in internet of vehicles systems

OriginalPaper

MVDLSTM: MultiView deep LSTM framework for online ride-hailing order prediction

OriginalPaper

Human pose, hand and mesh estimation using deep learning: a survey

OriginalPaper

LBTM: A lightweight blockchain-based trust management system for social internet of things

OriginalPaper

A novel fog-computing-assisted architecture of E-healthcare system for pregnant women

OriginalPaper

Online energy-efficient fair scheduling for heterogeneous multi-cores considering shared resource contention

Premium Partner

    Bildnachweise