文献

J-GLOBAL ID：201802249552613286   整理番号：18A1236783

イジング計算機によるスロット配置問題の解法

著者 (9件)： 金丸翔 (早稲田大 基幹理工) ,  於久太祐 (早稲田大 大学院基幹理工学研究科) ,  多和田雅師 (早稲田大 大学院基幹理工学研究科) ,  田中宗 (早稲田大 グリーン・コンピューティング・システム研究機構) ,  田中宗 (JST-さきがけ) ,  林真人 (日立) ,  山岡雅直 (日立) ,  柳澤政生 (早稲田大 大学院基幹理工学研究科) ,  戸川望 (早稲田大 大学院基幹理工学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 118  号： 85(MSS2018 1-36)  ページ： 161-166  発行年： 2018年06月07日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： イジング計算機は組合せ最適化問題を物理システムにマッピングすることで,組合せ最適化問題の準最適解を高速に得ることができるとして注目されている。スロット配置問題は,論理ブロックの最適配置や最適配送決定において重要な役割を果たす組合せ最適化問題である。本研究では,イジング計算機によって効率よく解法する手法を提案する。まず,イジングモデルのエネルギー関数として,スロット配置問題の制約を満たすときにエネルギーが最小となる制約項を導入する。さらに,配置された部品間の配線数とマンハッタン距離の加重和が部品間の重みとなる目的関数項を導入することで,スロット配置問題をイジングモデルとしてマッピングする。また,イジング計算機によって得られた解に対し,解釈処理なるアイデアを導入することで,制約を満たさない解が得られたとしても,制約を満たす解に解釈し直す手法を提案する。このとき提案手法が必要とするステップ数は,SAによるスロット配置に比較して,最小で約1/20程度となった。(著者抄録)

シソーラス用語： *Ising模型 ,  計算機械 ,  組合せ最適化問題 ,  *計算機利用 ,  半導体集積回路 ,  シミュレーテッドアニーリング
準シソーラス用語： *Isingモデル ,  計算機 ,  *ナチュラルコンピューティング ,  CMOS回路

分類 (1件)： その他の計算機  (JC06020B)

引用文献 (10件)：

• M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, E. M. Chapple, C. Enderud, J. P. Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, C. J. S. Truncik, S. Uchaikin, J. Wang, B. Wilson, and G. Rose, ′′Quantum annealing with manufactured spins,′′ Nature, vol. 473, no. 7346, pp. 194-198, May 2011.
• M. Yamaoka, C. Yoshimura, M. Hayashi, T. Okuyama, H. Aoki, and H. Mizuno, ′′A 20k-spin Ising chip to solve combinatorial optimization problems with CMOS annealing,′′ IEEE Journal of Solid-State Circuits, vol. 51, no. 1, pp. 303-309, Jan. 2016.
• S. Tsukamoto, M. Takatsu, S. Matsubara, and H. Tamura, ′′Acceleratorarchitecture for combinatorial optimization problems,′′ Fujitsu Scientific & Technical Journal, vol. 53, no. 5, pp. 8-13, Sep. 2017.
• S. Utsunomiya, K. Takata, and Y. Yamamoto, ′′Mapping of Ising models onto injection-locked laser systems,′′ Optical Society of America, vol. 19, no. 19, pp. 18091-18108, 2011.
• C. Yoshimura, M. Hayashi, T. Okuyama, and M. Yamaoka, ′′FPGA-based annealing processor for Ising model,′′ in Proc. 2016 Fourth International Symposium on Computing and Networking (CANDAR), pp. 436-442, Nov. 2016.

タイトルに関連する用語 (4件)： 計算機 ,  スロット ,  配置問題 ,  解法