卒業生とその進路

FPGAのオンチップメモリを活用する高密度イジング計算機


黄 偉強

2016 年度 卒 /学士(工学)

卒業研究の概要

本研究は、大規模な組み合わせ最適化問題を解くために、FPGAのオンチップメモリを活用する高密度イジング計算機を提案する。先行研究である完全並列型イジング計算機では、解ける組み合わせ最適化問題の規模はその回路規模によって制限されるが、本提案では、高いメモリバンド幅の持つFPGAのオンチップメモリを用い、部分的な並列処理を行うことで、より大規模な組合せ最適化問題に対応できる。

物流や交通など社会システムの効率化・最適化には、組み合わせ最適化問題と呼ばれる問題を高速かつ高電力効率に解く必要がある。しかし、組み合わせ最適化問題では、パラメータの増加に伴い、解となる候補も爆発的に増大するため、従来の逐次処理型汎用CPUでは、処理が困難である。さらに、これまで半導体の微細化に頼ったコンピュータの性能向上も限界を迎えつつある今、新しいコンピューティング技術が必要である。そこで、ナチュラルコンピューティングの発想の下に、磁性体のスピンの振る舞いを表すイジングモデルを模擬し、並列処理を行うことで、組み合わせ最適化問題を高速かつ高電力効率に解くFPGA実装のイジング計算機が提案された。しかし、従来のイジング計算機では、問題サイズに対応する回路規模が要求されるため、小規模なFPGAでは大規模組み合わせ最適化問題を解けない。そこで、本研究では、FPGAのオンチップメモリを活用し、部分的な並列処理によって大規模な組み合わせ最適化問題に対応できるアーキテクチャを提案する。

国際会議

  1. Yamamoto K., Huang W., Takamaeda-Yamazaki S., Ikebe M., Asai T., and Motomura M., "A Time-Division Multiplexing Ising Machine on FPGAs," International Symposium on Highly-Efficient Accelerators and Reconfigurable Technologies (HEART 2017), Ruhr University, Bochum, Germany (Jun. 7-9, 2017).