M系列乱数の並列生成

M序列随机数的并行生成

基本信息

批准号：
02640161
负责人：
小柳義夫
金额：
--
依托单位：
University of Tsukuba
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1990
资助国家：
日本
起止时间：
1990 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-02640161/
关键词：
乱数 M系列並列処理ベクトル化 QCDPAX 初期値排他的論理和

项目摘要

ス-パ-・コンピュ-タで使用される乱数は膨大な数である。1秒に1G個=2^<30>生成すると31〜32桁の合同法の乱数は1秒で周期を回ってしまう。多倍長の合同法は計算が面倒なので、M系列乱数を用いる。この例では、周期は2^<521>ー1〓6.87×10^<156>で、1G個/秒でも10^<147>秒〓10^<140>年かかる。良好な性質をもつM系列乱数を並列計算機で生成するためには、初期値の設定の仕方が重要である。調査の結果、次の方法が有効であることが分かった。すなわち、各プロセッサに521語(1語=1ビット)からなる1次元配列{r_k,O≦k≦520}を用意し、配列rにビット毎のM系列から得られる1n個のビット列{a_t,0≦t≦1nー1}を横方向に並べる。プロセッサ数nが2の羃乗でない場合は、nを起える最小の2の羃乗について上の操作をおこない、0〜(nー1)の部分だけ取ればよい。乱数を生成するには、各プロセッサで独立に漸化式r_t=r_<tー521>.XOR.r_<tー32>を実行し、r_tを[0,1]の浮動小数に変換する。ただし、.XOR.はビット毎の排他的論理和である。各プロセッサでの乱数生成のアルゴリズムは逐次型の場合と同様で、ベクトル化可能である。このプログラムにより、521個の乱数が生成される。個数が個定されてしまうのが難であるが、ソフト的に調節すればよい。このベクトルアルゴリズムを高並列計算機QCDPAXにマイクロプログラムにより実装したところ、1個当り、373μsecで生成することができた。432台全体では1.16G個/秒である。なお、初期設定はホストのワ-クステ-ションで行う。

超级计算机中使用的随机数数量巨大。如果每秒生成1G = 2^<30>，则31-32位同余随机数将在1秒内循环一次。多精度同余法计算复杂，因此采用M序列随机数。在这个例子中，周期为2^<521>-1〓6.87×10^<156>，即使1G件/秒也需要10^<147>秒〓10^<140>年。为了在并行计算机上生成具有良好性质的M序列随机数，如何设置初始值很重要。根据调查的结果，发现以下方法是有效的。即为每个处理器准备一个由521个字(1字＝1位)组成的一维数组{r_k，O≤k≤520}，数组r包含1n个位串{a_t，0≤t≤1n -1} 水平排列。如果处理器数量n不是2的幂，则对导致n的最小的2的幂执行上述操作，只取0到(n-1)的部分。为了生成随机数，每个处理器独立执行递推公式 r_t=r_<t−521>.XOR.r_<t−32> 并将 r_t 转换为 [0,1] 中的浮点数。然而，.XOR 是按位异或。每个处理器中的随机数生成算法与顺序类型中的相同，并且可以矢量化。该程序生成 521 个随机数。虽然很难单独确定该数字，但可以使用软件进行调整。当该矢量算法在高度并行计算机QCDPAX上作为微程序实现时，可以在373微秒内生成每个矢量。所有 432 个单元的总速度为 1.16G/秒。初始设置在主机工作站上执行。