The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Pemproses penyepuhlindapan berdasarkan model Ising adalah calon yang luar biasa untuk masalah pengoptimuman gabungan dan ia lebih unggul daripada komputer von Neumann umum. Pelaksanaan berasaskan CMOS pemproses penyepuhlindapan adalah cekap dan boleh dilaksanakan berdasarkan teknologi semikonduktor semasa. Walau bagaimanapun, masalah kritikal dengan pemproses penyepuhlindapan kekal. Terdapat sedikit putaran simulasi dan ketidakfleksibelan dari segi topologi graf yang boleh dilaksanakan disebabkan oleh kekangan perkakasan. Pendekatan terdahulu untuk mengatasi masalah ini adalah dengan meniru graf rumit pada tatasusunan putaran yang mudah dan berketumpatan tinggi dengan apa yang dipanggil pembenaman kecil, kaedah pendua putaran berdasarkan teori graf. Apabila graf rumit dibenamkan pada perkakasan sedemikian, banyak putaran digunakan untuk mewakili putaran darjah tinggi dengan menggabungkan berbilang putaran darjah rendah. Selain bilangan putaran, kualiti penyelesaian berkurangan akibat sambungan kukuh tiruan antara putaran pendua. Oleh itu, pendekatan tidak dapat menangani masalah praktikal berskala besar. Makalah ini mencadangkan seni bina perkakasan yang fleksibel dan berskala dengan pemultipleksan pembahagian masa untuk putaran besar-besaran dan topologi darjah tinggi. Graf sasaran dipisahkan dan dipetakan pada berbilang satah maya, dan setiap satah tertakluk kepada simulasi berjalin dengan pemprosesan pembahagian masa. Oleh itu, tingkah laku putaran darjah tinggi dicontohi dengan cekap dari semasa ke semasa, supaya tiada sambungan kukuh tiruan diperlukan, dan kualiti penyelesaian dipertingkatkan dengan sewajarnya. Kami melaksanakan reka bentuk perkakasan prototaip untuk FPGA, dan kami menilai kaedah yang dicadangkan dalam simulator pemproses penyepuhlindapan berasaskan perisian. Keputusan menunjukkan bahawa kaedah itu meningkatkan putaran yang boleh digunakan. Di samping itu, seni bina pemultipleksan pembahagian masa kami meningkatkan kualiti penyelesaian dan masa penumpuan dengan penggunaan sumber yang munasabah.
Kasho YAMAMOTO
Hokkaido University
Masayuki IKEBE
Hokkaido University
Tetsuya ASAI
Hokkaido University
Masato MOTOMURA
Tokyo Institute of Technology
Shinya TAKAMAEDA-YAMAZAKI
The University of Tokyo,JST PRESTO
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Kasho YAMAMOTO, Masayuki IKEBE, Tetsuya ASAI, Masato MOTOMURA, Shinya TAKAMAEDA-YAMAZAKI, "FPGA-Based Annealing Processor with Time-Division Multiplexing" in IEICE TRANSACTIONS on Information,
vol. E102-D, no. 12, pp. 2295-2305, December 2019, doi: 10.1587/transinf.2019PAP0002.
Abstract: An annealing processor based on the Ising model is a remarkable candidate for combinatorial optimization problems and it is superior to general von Neumann computers. CMOS-based implementations of the annealing processor are efficient and feasible based on current semiconductor technology. However, critical problems with annealing processors remain. There are few simulated spins and inflexibility in terms of implementable graph topology due to hardware constraints. A prior approach to overcoming these problems is to emulate a complicated graph on a simple and high-density spin array with so-called minor embedding, a spin duplication method based on graph theory. When a complicated graph is embedded on such hardware, numerous spins are consumed to represent high-degree spins by combining multiple low-degree spins. In addition to the number of spins, the quality of solutions decreases as a result of dummy strong connections between the duplicated spins. Thus, the approach cannot handle large-scale practical problems. This paper proposes a flexible and scalable hardware architecture with time-division multiplexing for massive spins and high-degree topologies. A target graph is separated and mapped onto multiple virtual planes, and each plane is subject to interleaved simulation with time-division processing. Therefore, the behavior of high-degree spins is efficiently emulated over time, so that no dummy strong connections are required, and the solution quality is accordingly improved. We implemented a prototype hardware design for FPGAs, and we evaluated the proposed method in a software-based annealing processor simulator. The results indicate that the method increased the spins that can be deployed. In addition, our time-division multiplexing architecture improved the solution quality and convergence time with reasonable resource consumption.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2019PAP0002/_p
Salinan
@ARTICLE{e102-d_12_2295,
author={Kasho YAMAMOTO, Masayuki IKEBE, Tetsuya ASAI, Masato MOTOMURA, Shinya TAKAMAEDA-YAMAZAKI, },
journal={IEICE TRANSACTIONS on Information},
title={FPGA-Based Annealing Processor with Time-Division Multiplexing},
year={2019},
volume={E102-D},
number={12},
pages={2295-2305},
abstract={An annealing processor based on the Ising model is a remarkable candidate for combinatorial optimization problems and it is superior to general von Neumann computers. CMOS-based implementations of the annealing processor are efficient and feasible based on current semiconductor technology. However, critical problems with annealing processors remain. There are few simulated spins and inflexibility in terms of implementable graph topology due to hardware constraints. A prior approach to overcoming these problems is to emulate a complicated graph on a simple and high-density spin array with so-called minor embedding, a spin duplication method based on graph theory. When a complicated graph is embedded on such hardware, numerous spins are consumed to represent high-degree spins by combining multiple low-degree spins. In addition to the number of spins, the quality of solutions decreases as a result of dummy strong connections between the duplicated spins. Thus, the approach cannot handle large-scale practical problems. This paper proposes a flexible and scalable hardware architecture with time-division multiplexing for massive spins and high-degree topologies. A target graph is separated and mapped onto multiple virtual planes, and each plane is subject to interleaved simulation with time-division processing. Therefore, the behavior of high-degree spins is efficiently emulated over time, so that no dummy strong connections are required, and the solution quality is accordingly improved. We implemented a prototype hardware design for FPGAs, and we evaluated the proposed method in a software-based annealing processor simulator. The results indicate that the method increased the spins that can be deployed. In addition, our time-division multiplexing architecture improved the solution quality and convergence time with reasonable resource consumption.},
keywords={},
doi={10.1587/transinf.2019PAP0002},
ISSN={1745-1361},
month={December},}
Salinan
TY - JOUR
TI - FPGA-Based Annealing Processor with Time-Division Multiplexing
T2 - IEICE TRANSACTIONS on Information
SP - 2295
EP - 2305
AU - Kasho YAMAMOTO
AU - Masayuki IKEBE
AU - Tetsuya ASAI
AU - Masato MOTOMURA
AU - Shinya TAKAMAEDA-YAMAZAKI
PY - 2019
DO - 10.1587/transinf.2019PAP0002
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E102-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2019
AB - An annealing processor based on the Ising model is a remarkable candidate for combinatorial optimization problems and it is superior to general von Neumann computers. CMOS-based implementations of the annealing processor are efficient and feasible based on current semiconductor technology. However, critical problems with annealing processors remain. There are few simulated spins and inflexibility in terms of implementable graph topology due to hardware constraints. A prior approach to overcoming these problems is to emulate a complicated graph on a simple and high-density spin array with so-called minor embedding, a spin duplication method based on graph theory. When a complicated graph is embedded on such hardware, numerous spins are consumed to represent high-degree spins by combining multiple low-degree spins. In addition to the number of spins, the quality of solutions decreases as a result of dummy strong connections between the duplicated spins. Thus, the approach cannot handle large-scale practical problems. This paper proposes a flexible and scalable hardware architecture with time-division multiplexing for massive spins and high-degree topologies. A target graph is separated and mapped onto multiple virtual planes, and each plane is subject to interleaved simulation with time-division processing. Therefore, the behavior of high-degree spins is efficiently emulated over time, so that no dummy strong connections are required, and the solution quality is accordingly improved. We implemented a prototype hardware design for FPGAs, and we evaluated the proposed method in a software-based annealing processor simulator. The results indicate that the method increased the spins that can be deployed. In addition, our time-division multiplexing architecture improved the solution quality and convergence time with reasonable resource consumption.
ER -