• 検索結果がありません。

在必要性が高い多倍長整数のビット数は高々数千ビット程度である. そこで本論文では, 筆算に基づく O(n 2 ) 時間の乗算を並列計算に適した積表と名付けたデータ構造を用いて GPU 上で高速に並列実行する手法を提案する.FFT 乗算とちがって, 提案手法では乗数と被乗数のビット数が異なる場合に長い

N/A
N/A
Protected

Academic year: 2021

シェア "在必要性が高い多倍長整数のビット数は高々数千ビット程度である. そこで本論文では, 筆算に基づく O(n 2 ) 時間の乗算を並列計算に適した積表と名付けたデータ構造を用いて GPU 上で高速に並列実行する手法を提案する.FFT 乗算とちがって, 提案手法では乗数と被乗数のビット数が異なる場合に長い"

Copied!
8
0
0

読み込み中.... (全文を見る)

全文

Loading

図 3  積表構成アルゴリズム ・  赤と緑の部分は列数が等しく,その数は B の桁数に等しい.またこれらの行数は図 2 の ように増減し,その変化量は 1 列ごとに 2 行ずつである. ・  黄の部分の列数は A と B の桁数の差になり, 行数は B の桁数のちょうど 2 倍となる.  一般の場合の積表を求めるアルゴリズムを図 3 に示す.このアルゴリズムは BASE 進数 a 桁およ び b 桁の多倍長整数 A,B の各桁の値がそれぞれ配 列 A[0..a-1]および B[0..b-1]に格納されてい
図 6  負荷バランスを考慮して再構成した     積表の例(5 桁の多倍長整数 A と    3 桁の多倍長整数 B の場合) 3.3  アルゴリズム  図 7 の よ う に 長 方 形 RG を 1 つ が 横 (BLOCK_SIZE)要素×縦(BLOCK_SIZE×2)要素 と な る 水 色 の 領 域 に 区 分 け す る . こ こ で BLOCK_SIZE とは,CUDA での実装において 1 スレッドブロック(以降,ブロック)が持つスレッ ド数のことである.そして, 1 ブロックにこの水
図 8  長方形 RG に対するカーネル関数  次に長方形 Y に対するカーネル関数について述 べる.この関数は長方形 RG に対する関数と比べ, 参照する A や B の配列の添字や,総和を足し込む 配列 C の添字が異なるだけでほとんど同じである. ブロック数は ⌈(a-b)/BLOCK_SIZE⌉×⌈b/BLOCK_SIZE⌉  である.具体的なコードを図 9 に示す.  ここまでの関数により解を格納する配列 C へと 適切な総和を足し込んできたが,計算する桁数が十 分に多い時,配列 C はこの段階で
図 11  多倍長整数の和を求めるアルゴリズム  2つ目の処理,多倍長整数の和を求めるアルゴリ ズムについて説明する.多倍長整数の和を求める過 程で注意しなければならないのは,桁の繰り上がり の伝播である.最悪の場合,すなわち伝播が配列の 頭から最後まで続く場合には強い遂次性が生まれ, 1 スレッドが配列の頭から最後まで処理するのと 同等の計算時間がかかってしまう.今回実装するア ルゴリズムはハードウェアの全加算器の実装方法 の一つである carry skip adder[11]と本質的には同 じであり,こ

参照

関連したドキュメント

実際, クラス C の多様体については, ここでは 詳細には述べないが, 代数 reduction をはじめ類似のいくつかの方法を 組み合わせてその構造を組織的に研究することができる

事業セグメントごとの資本コスト(WACC)を算定するためには、BS を作成後、まず株

(問5-3)検体検査管理加算に係る機能評価係数Ⅰは検体検査を実施していない月も医療機関別係数に合算することができる か。

これはつまり十進法ではなく、一進法を用いて自然数を表記するということである。とは いえ数が大きくなると見にくくなるので、.. 0, 1,

解析の教科書にある Lagrange の未定乗数法の証明では,

、肩 かた 深 ふかさ を掛け合わせて、ある定数で 割り、積石数を算出する近似計算法が 使われるようになりました。この定数は船

荒天の際に係留する場合は、1つのビットに 2 本(可能であれば 3

いてもらう権利﹂に関するものである︒また︑多数意見は本件の争点を歪曲した︒というのは︑第一に︑多数意見は