著者

渡部 信吾 阿部 公輝

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告コンピュータセキュリティ(CSEC) (ISSN:09196072)

巻号頁・発行日

vol.2005, no.41, pp.13-18, 2005-05-19

被引用文献数

1

---

モンテカルロ法などに代表されるコンピュータシミュレーションの分野やストリーム暗号といった暗号の分野においては,大量の疑似乱数が必要とされることが多い.疑似乱数生成アルゴリズムとしては Linear Feedback ShiftRegister(LFSR),線形合同生成器等多くの手法がある.なかでも MersenneTwister は周期が長く,乱数性がよいことが知られており,ハードウェア実装においては並列処理が可能である.本論文では Mersenne Twister のVLSI 設計を行い 並列度を上げたときのスループット,面積,速度効率について述べる. CMOS 0.18um テクノロジを用い,並列度を 208 としたとき スループットは 568.18GBytes/s (回路面積は 5.537mm2) となり ソフトウェアと比較し630倍以上高速であることがわかった.There are many applications including Monte Carlo simulation and stream ciphers, where a large number of psudo-random numbers are required to be generated at high speed. Among known algorithms for generating psudo-random numbers such as Linear Feedback Shift Register(LFSR) and Linear Congruential Generator(LCG), the Mersenne Twister has long-period cycle with excellent randomness. We focus on its intrinsic characteristics that many independent computations exist in the Mersenne Twister algorithm and thus a high degree of parallelism is expected to be utilized in hardware realization of the algorithm. In this paper, we describe a VLSI design of Mersenne Twister and evaluate the design with respect to the performance and area costs when increasing the degree of parallelism. Using CMOS 0.18um technology, a throughput of 568.18GBytes/s was obtained by fully exploiting the parallelism at the area cost of 5.537mm2. The speed was more than 630 times faster than software implementation of the algorithm.