FPGAを用いたコラッツ予想の網羅的検証の高速化

• Item type: SIG Technical Reports(1)
• 公開日: 2018-08-27
• タイトル: FPGAを用いたコラッツ予想の網羅的検証の高速化
• タイトル / 言語: en
• タイトル: Acceleration for Exhaustive Verification of the Collatz Conjecture using the FPGA
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島大学
• 著者所属: 広島大学
• 著者所属: 広島大学
• 著者所属(英): en
• 著者所属(英): Hiroshima University
• 著者所属(英): en
• 著者所属(英): Hiroshima University
• 著者所属(英): en
• 著者所属(英): Hiroshima University
• 著者名: 佐伯, 和人; 伊藤, 靖朗; 中野, 浩嗣
• 著者名(英): Kazuto, Saiki; Yasuaki, Ito; Koji, Nakano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: コラッツ予想とは数論の未解決問題の 1 つである．任意の自然数 n が与えられたとき，n が偶数なら 2 で割り，n が奇数なら 3 を掛けて 1 を足す，得られた値に対しても同様の操作を繰り返すと有限回で 1 に到達するという予想である．本論文ではコラッツ予想の網羅的検証を高速に行う FPGA 実装を提案する．提案実装では回路のリソースを削減することでマルチコプロセッサシステムとしたときにより多くのコプロセッサを並べることを可能にした．本研究は Xilinx Virtex UltraScale + FPGA を対象デバイスとして設計を行い，4096 個のコプロセッサを並べたマルチコプロセッサシステムを実装した．結果として提案実装は 1 秒間に 6.16 × 10¹² 個の 64 bit 自然数の検証が可能であり，既存 GPU 実装と比較して約 2.56 倍の性能向上を達成した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The Collatz conjecture is a well-known unsolved problem in mathematics. Consider the following operation on an arbitrary positive number: if the number is even, divide it by two, and if the number is odd, triple it and add one. The conjecture asserts that, starting from any positive number, repeated iteration of the operations eventually produces the value 1. In this paper, we propose an FPGA implementation of the exhaustive verification for the Collatz conjecture. In the proposed implementation, a large number of coprocessors can be arranged on an FPGA by reducing the resource of circuits. We have implemented a multi-coprocessor system that has 4096 coprocessors on a Xilinx Virtex UltraScale+ FPGA. The experimental results show that our multi-coprocessor system can verify 6:16 × 10¹² 64bit natural numbers per second. Also, our implementation on the FPGA attains a speed-up factor of 2.56 over the existing GPU implementation.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2018-AL-169, 号 5, p. 1-8, 発行日 2018-08-27
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会