北海道大学 大学院情報科学研究院

確率的セルオートマトンに基づく組合せ最適化問題求解ハードウェアアーキテクチャ

熊澤 輝顕

2018 年度 卒 ／修士（情報科学）

修士論文の概要

本論文ではZDD (ゼロサプレス型二分決定グラフ)を用いた三角形分割パターン列挙問題解法の超高速アルゴリズムの提案と、SCA (確率セルオートマトン)に基づく組合せ最適化問題処理ハードウェアの提案をしている。組合せ最適化問題とは、要素x∈ Eの集合族2^Eの中からもっとも要求を満たす集合C_max ⊆ 2^Eを求める問題である。C_max内の要素の組合せを最適解と呼ぶ。一般的に、要素数が増えると集合族の大きさ| 2^E |は指数的に大きくなる。最適解を求める方法は、集合を全て列挙するか、問題に応じた目的関数を元にヒューリティクスを用いて解く2通りの方法がある。本論文では、まずZDDを用いた列挙を行うことで、組合せ最適化問題の解を圧縮しながら超高速に列挙することが可能であることを示し、その後SCAに基づき設計した組合せ最適化問題を解くハードウェアが、並列性と柔軟性を兼ね備えていることを示すとともに、今後の発展性を示唆する。

国内学会 熊澤 輝顕, 鈴木 浩史, 石畠 正和, 浅井 哲也, 池辺 将之, 本村 真人, 高前田 伸也, "ZDDを用いた三角形分割パターンの列挙とその応用に向けて," 人工知能学会 第106回人工知能基本問題研究会, 指宿市民会館, (鹿児島), 2018年3月16-17日. 山本 佳生, 熊澤 輝顕, 池辺 将之, 浅井 哲也, 本村 真人, 高前田 伸也, "高次数イジングネットワークの時分割処理方式の検討," 電子情報通信学会コンピュータシステム研究会 (CPSY), 秋田アトリオンビル, (秋田), 2017年7月26-28日. 熊澤 輝顕, 池辺 将之, 浅井 哲也, 本村 真人, 高前田 伸也, "メモリアクセスパターンを考慮した遅延評価によるZDD構築の高速化," 基盤（S）離散構造処理系プロジェクト「2017年度初夏のワークショップ」, 北海道大学VBL棟, (札幌), 2017年6月23-24日. 熊澤 輝顕, 高前田 伸也, 池辺 将之, 浅井 哲也, 本村 真人, "メモリアクセスパターンを考慮した遅延評価によるZDD構築の高速化," 第30回 回路とシステムワークショップ, 北九州国際会議場, (北九州), 2017年5月11-12日.