| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2009-09-18 15:25 An FPGA-based Architecture for Verifying Collatz Conjecture ○Yasuaki Ito・Koji Nakano（Hiroshima Univ.）  RECONF2009-40 |
|
| 抄録 | （和） | 任意の正の数に対して，偶数のときその数を$2$で割り，奇数のとき$3$倍して$1$を加えるという操作を考える．コラッツ予想は，すべての正の数$n$に対して上記の操作を繰り返すと最終的に$1$になるという予想である．本論文では，コラッツ予想を検証するためのハードウェア・ソフトウェアの協調的手法を紹介する．本手法では，FPGAに実装した回路を用いて$1$になる数を回路を用いて高速に計算し，オーバーフローのため回路で計算できなかった数はホストPC上のソフトウェアによって多倍長演算を用いて検証をおこなう．我々はVertex{II}シリーズのFPGA X2CV3000-4を用いて24個のコプロセッサを実装し，評価をおこなった．その結果，本手法は，1秒間に$2.89 \times 10^9$個の64ビットの数が検証可能であることを確認した． |
| （英） | 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 Collatz conjecture assert that, starting from any positive number $n$, repeated iteration of the operations eventually produces the value $1$. The main contribution of this paper is to present hardware-software cooperative approach to verify the Collatz conjecture. The key idea of our approach is to sieve numbers $n$ that produces 1 using a circuit implemented on an FPGA. The numbers that fail to be verified by overflow are reported to the host PC. The host PC verifies those numbers using unlimited bits operations by software. We have implemented 24 coprocessors on the Vertex II family FPGA XC2V3000-4. The experimental results show that our hardware-software cooperative approach can verify $2.89 \times 10^9$ 64-bit numbers per second. | |
| キーワード | （和） | ハードウェアアルゴリズム / FPGA実装 / ブロックRAM / / / / / |
| （英） | Hardware Algorithm / FPGA Implementation / Block RAMs / / / / / | |
| 文献情報 | 信学技報, vol. 109, no. 198, RECONF2009-40, pp. 125-130, 2009年9月. | |
| 資料番号 | RECONF2009-40 | |
| 発行日 | 2009-09-10 (RECONF) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | RECONF2009-40 |
|
| 研究会情報 | |
| 研究会 | RECONF |
| 開催期間 | 2009-09-17 - 2009-09-18 |
| 開催地（和） | 宇都宮大学 |
| 開催地（英） | Utsunomiya Univ. |
| テーマ（和） | リコンフィギャラブルシステム，一般 |
| テーマ（英） | Reconfigurable Sysytems, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | RECONF |
| 会議コード | 2009-09-RECONF |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | An FPGA-based Architecture for Verifying Collatz Conjecture |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ハードウェアアルゴリズム / Hardware Algorithm |
| キーワード(2)（和/英） | FPGA実装 / FPGA Implementation |
| キーワード(3)（和/英） | ブロックRAM / Block RAMs |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 伊藤 靖朗 / Yasuaki Ito / イトウ ヤスアキ |
| 第1著者 所属（和/英） | 広島大学 (略称： 広島大) Hiroshima University (略称： Hiroshima Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 中野 浩嗣 / Koji Nakano / ナカノ コウジ |
| 第2著者 所属（和/英） | 広島大学 (略称： 広島大) Hiroshima University (略称： Hiroshima Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2009-09-18 15:25:00 |
| 発表時間 | 25分 |
| 申込先研究会 | RECONF |
| 資料番号 | RECONF2009-40 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | no.198 |
| ページ範囲 | pp.125-130 |
| ページ数 | 6 |
| 発行日 | 2009-09-10 (RECONF) |
[研究会発表申込システムのトップページに戻る]