{"id":191036,"updated":"2025-01-20T00:58:08.890671+00:00","links":{},"created":"2025-01-19T00:56:57.382929+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00191036","sets":["1164:2592:9368:9546"]},"path":["9546"],"owner":"11","recid":"191036","title":["FPGAを用いたコラッツ予想の網羅的検証の高速化"],"pubdate":{"attribute_name":"公開日","attribute_value":"2018-08-27"},"_buckets":{"deposit":"c1a38bb9-a229-4a2d-96ab-b0b73351905c"},"_deposit":{"id":"191036","pid":{"type":"depid","value":"191036","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"FPGAを用いたコラッツ予想の網羅的検証の高速化","author_link":["439000","439001","438999","439002","439003","438998"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"FPGAを用いたコラッツ予想の網羅的検証の高速化"},{"subitem_title":"Acceleration for Exhaustive Verification of the Collatz Conjecture using the FPGA","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2018-08-27","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"広島大学"},{"subitem_text_value":"広島大学"},{"subitem_text_value":"広島大学"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Hiroshima University","subitem_text_language":"en"},{"subitem_text_value":"Hiroshima University","subitem_text_language":"en"},{"subitem_text_value":"Hiroshima University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/191036/files/IPSJ-AL18169005.pdf","label":"IPSJ-AL18169005.pdf"},"date":[{"dateType":"Available","dateValue":"2020-08-27"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL18169005.pdf","filesize":[{"value":"935.7 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"c4048fa6-a52a-43ce-8246-a1604aa2afcf","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2018 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"佐伯, 和人"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"伊藤, 靖朗"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"中野, 浩嗣"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Kazuto, Saiki","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Yasuaki, Ito","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Koji, Nakano","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN1009593X","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"2188-8566","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"コラッツ予想とは数論の未解決問題の 1 つである．任意の自然数 n が与えられたとき，n が偶数なら 2 で割り，n が奇数なら 3 を掛けて 1 を足す，得られた値に対しても同様の操作を繰り返すと有限回で 1 に到達するという予想である．本論文ではコラッツ予想の網羅的検証を高速に行う FPGA 実装を提案する．提案実装では回路のリソースを削減することでマルチコプロセッサシステムとしたときにより多くのコプロセッサを並べることを可能にした．本研究は Xilinx Virtex UltraScale +  FPGA を対象デバイスとして設計を行い，4096 個のコプロセッサを並べたマルチコプロセッサシステムを実装した．結果として提案実装は 1 秒間に 6.16 × 10¹² 個の 64 bit 自然数の検証が可能であり，既存 GPU 実装と比較して約 2.56 倍の性能向上を達成した．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"8","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2018-08-27","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"5","bibliographicVolumeNumber":"2018-AL-169"}]},"relation_version_is_last":true,"weko_creator_id":"11"}}