DEIM Forum 2017 C8-3

GPU を用いた大規模な文書に対する高精度検索のための高速な重み付け計算
柳本

晟熙†

欅

惇志††

宮崎

純††

† 東京工業大学工学部情報工学科 〒 152–8550 東京都目黒区大岡山二丁目１２‐１†† 東京工業大学情報理工学院 〒 152–8550 東京都目黒区大岡山二丁目１２‐１
E-mail: †yanagimoto@lsc.cs.titech, ††keyaki@lsc.cs.titech.ac.jp, †††miyazaki@cs.titech.ac.jp
あらまし 本研究では, ウェブ上に大量に存在する様々な文書から抽出された索引語に対し, 高精度な情報検索に必要となる重み付け計算を GPU を用いて行う. 並列処理のフレームワークである MapReduce と, MapReduce を GPU 上で実行するためのフレームワークである Mars を利用し, 重み付け計算を行う既存研究は存在するが, GPU のメモリ上に格納できない大規模なデータを想定していない. 本研究では, 大規模なデータに対してもデータを分割して効率的に計算を行うことできる手法を提案し, 評価を行う.
キーワード

GPGPU, 情報検索, MapReduce, 索引語重み付け

1. は じ め に
現在, 大量のウェブページが存在し, その中からユーザの要求に合致するページを正確に抽出する高精度な情報検索が必要とる. 一方, Mars は GPU プログラミングの複雑さをほとんど意識することなく使用することができるよう設計されているため,

GPU プログラミングに精通していない人でも容易に扱うことができる.

されている. 高精度な情報検索を実現するために, TF-IDF [1]

森谷ら [10] は Mars を拡張し, 文書から抽出された索引語にや BM25 [2] など，さまざまな索引語重み付け手法が提案され対して上記の高精度検索用の重み付けを高速に行うことを可能ている. これらの重み付け手法において用いられる統計量は, あにした. しかし, 一般にグラフィックカード上のメモリである

る文書内で出現する索引語の統計量から算出される局所的統計

VRAM は, コンピュータのメインメモリよりも容量が小さいた

量と, 文書集合全体の索引語の出現統計量から算出される大域

め, 一度の MapReduce で扱える文書集合のサイズが限られて的統計量の二種類に分類される.

おり, 森谷らの手法では扱うことができる文書集合のサイズに

上記の索引語重みを高速に計算するために, 文書集合を分割限界がある.

し, 並列に計算する研究が取り組まれている [3] [4] [5]. 並列処

この問題を解決するために, 本研究では大規模な文書集合を理を行うための代表的なフレームワークとして Google が開発

チャンクと呼ばれる小さな文書集合に分割して計算を行う. そした MapRedece [6] が存在する. MapRedece はデータセットの際, チャンクごとの独立した計算結果では大域的統計量を算をクラスタ内のノードに分散させ, 入力データから Key/Value

出することができない. そこで本研究では, 目的の異なる二種ペアを生成する Map ステップと, それらを集約し, 結果を算出

類の MapReduce を提案し, 1 回目の MapReduce でチャンク

する Reduce ステップの二つのステップに分けて並列計算を行ごとの大域的統計量を集約することで, 文書集合全体におけるう. MapReduce の並列処理をクラスタ上ではなく, マルチコア

大域的統計量を算出する. 続く 2 回目の MapReduce で索引語

CPU 上で実装した Phoenix [7] も存在する.
MapReduce で高速にデータを処理するためには, データを分の重み付けを完了する. これにより大規模な文書集合に対しても重み付け計算を可能にする.

散した各ノードで高速に処理することが求められる. その解決

また, GPUTeraSort [11] は GPU を用いたソートアルゴリズ方法の一つが, GPU を汎用計算に利用する GPGPU (General-

ムを提案し, 計算の各ステージをパイプライン処理で行っていpurpose Computing on Graphics Processing Units) である.

る. 本研究でも, 計算の各ステージに対してパイプライン処理

GPU は本来, 画像処理を目的として開発されたが, その並列計を施すことによって, 提案手法の高速化を実現する.

算能力の高さから汎用計算に使用する研究がなされてきた. な
お, 現在では一般用途のマシンにも GPU が搭載されていることが一般的であるため, 多数のマシンにおいて GPU を用いた並列処理を行うことが可能である. また, GPGPU の一環として, MapReduce を GPU 上で行うためのフレームワークであ本研究では, 大規模な文書集合における索引語の重み付けとして, 前述の BM25 の計算を行い, その評価実験を行う.

2. 関 連 研 究
本節では, はじめに索引語の重み付け計算である BM25 [2] のる Mars [8] が存在する. GPU での並列コンピューティング開計算式を述べる. また, 既存研究である GPU を用いた重み付け

発環境として CUDA [9] が存在するが, 計算能力を十分に引き計算手法 [10] と, GPU を用いてデータベースの莫大なレコー出すためには GPU のアーキテクチャに精通している必要があ

ドをソートすることを実現した GPUTeraSort [11] について説

ᩥ᭩ϭ
ĂƉƉůĞ
ŵĞůŽŶ
ĂƉƉůĞ

ĂƉƉůĞ
ŵĞůŽŶ
ф͕ĚŽĐϭх
ĂƉƉůĞ

ᩥ᭩Ϯ
ďĂŶĂŶĂ
ŵĞůŽŶĂƉƉůĞďĂŶĂŶĂ

ďĂŶĂŶĂ
ŵĞůŽŶф ĂƉƉůĞ
ďĂŶĂŶĂ

ᩥ᭩ϯ
ƉĞĂĐŚ
ŵĞůŽŶ
ďĂŶĂŶĂ

ф;ĂƉƉůĞ͕ĚŽĐϭͿ͕Eh>>х
ф;ŵĞůŽŶ͕ĚŽĐϭͿ͕Eh>>х
ф;ĂƉƉůĞ͕ĚŽĐϭͿ͕Eh>>х

ф;ďĂŶĂŶĂ͕ĚŽĐϮͿ͕Eh>>х
ф;ŵĞůŽŶ͕ĚŽĐϮͿ͕Eh>>х
ф;ĂƉƉůĞ͕ĚŽĐϮͿ͕Eh>>х
ф;ďĂŶĂŶĂ͕ĚŽĐϮͿ͕Eh>>х

͕ĚŽĐϮх

ф;ƉĞĂĐŚ͕ĚŽĐϯͿ͕Eh>>х
ф;ŵĞůŽŶ͕ĚŽĐϯͿ͕Eh>>х
ф;ďĂŶĂŶĂ͕ĚŽĐϯͿ͕Eh>>х

ƉĞĂĐŚ
ŵĞůŽŶ
ф͕ĚŽĐϯхďĂŶĂŶĂ

ϭ͘ධຊф;ĂƉƉůĞ͕ĚŽĐϭͿ͕Eh>>х
ф;ĂƉƉůĞ͕ĚŽĐϭͿ͕Eh>>х
ф;ĂƉƉůĞ͕ĚŽĐϮͿ͕Eh>>х

ĂƉƉůĞ
&сϮ

ф;ďĂŶĂŶĂ͕ĚŽĐϮͿ͕Eh>>х
ф;ďĂŶĂŶĂ͕ĚŽĐϮͿ͕Eh>>х
ф;ďĂŶĂŶĂ͕ĚŽĐϯͿ͕Eh>>х

ďĂŶĂŶĂ ;ďĂŶĂŶĂ͕ĚŽĐϮͿ͗d&сϮ&сϮ ;ďĂŶĂŶĂ͕ĚŽĐϯͿ͗d&сϭф;ŵĞůŽŶ͕ĚŽĐϭͿ͕Eh>>х
ф;ŵĞůŽŶ͕ĚŽĐϮͿ͕Eh>>х
ф;ŵĞůŽŶ͕ĚŽĐϯͿ͕Eh>>х

;ŵĞůŽŶ͕ĚŽĐϭͿ͗d&сϭŵĞůŽŶ;ŵĞůŽŶ͕ĚŽĐϮͿ͗d&сϭ
&сϯ
;ŵĞůŽŶ͕ĚŽĐϯͿ͗d&сϭф;ƉĞĂĐŚ͕ĚŽĐϯͿ͕Eh>>х

ƉĞĂĐŚ;ƉĞĂĐŚ͕ĚŽĐϯͿ͗d&сϭ
&сϭ

Ϯ͘DĂƉ

ϯ͘^ŚƵĨĨůĞ

;ĂƉƉůĞ͕ĚŽĐϭͿ͗d&сϮ
;ĂƉƉůĞ͕ĚŽĐϮͿ͗d&сϭϰ͘ZĞĚƵĐĞ

фĂƉƉůĞ͕;ĚŽĐϭ͕Ϭ͘ϭϯϳͿхфĂƉƉůĞ͕;ĚŽĐϮ͕Ϭ͘ϬϴϵͿхфďĂŶĂŶĂ͕;ĚŽĐϮ͕Ϭ͘ϭϮϲͿхфďĂŶĂŶĂ͕;ĚŽĐϯ͕Ϭ͘ϭϬϭͿхфŵĞůŽŶ͕;ĚŽĐϭ͕ͲϬ͘ϭϴϯͿхфŵĞůŽŶ͕;ĚŽĐϮ͕ͲϬ͘ϭϲϮͿхфŵĞůŽŶ͕;ĚŽĐϯ͕ͲϬ͘ϭϴϯͿхфƉĞĂĐŚ͕;ĚŽĐϯ͕Ϭ͘ϰϵϳͿхϱ͘ฟຊ

図 1 既存手法のワークフロー

明する.

<(term, documentID), NULL>となる.

2. 1 BM25（ 3 ） Shuﬄe

まず, BM25 の計算式を示す. 文書 d における索引語 t の重Shuﬄe ステップは Map ステップの出力をユーザーの定義に

み wd,t は下記の式 (1) で算出できる.

wd,t =(k1 +1)tfd,t
dld )+tfk1 ((1−b)+b avdl
d,t

lwd,t =

−dft +0.5· log N df
t +0.5(k1 +1)tfd,t
dld )+tfk1 ((1−b)+b avdl
d,t−dft +0.5
gwt = log N df
t +0.5

従って並べ替えるステップである (図 1 中の 3.Shuﬄe). ここでは, key/value ペアを key の第一要素である索引語 (term) で辞(1)

書順に並べ替え, 索引語が同一のものについては key の第二要(2)

素である文書 ID(documentID) で昇順に並べ替える. そして,

(3)

ステップで並列に処理する. なお, 文書 ID が異なる key/value

key に同一の索引語を持つ key/value ペアごとに次の Reduce

式 (1) 中の tfd,t を文書 d における索引語 t の出現頻度, dft

ペアであっても, 同一の索引語を持つ key の場合は, Reduce ス

を索引語 t を含む文書数, N を文書集合全体の文書数, dld を

テップでは同一のスレッドで処理することで効率的に処理を文書 d に含まれる索引語の数, avdl を文書集合全体の平均文行う.

書長である. また, k1 , b はパラメータであり, 以降それぞれ（ 4 ） Reduce

k1 = 1.2, b = 0.75 と設定する. また, avdl の値はウェブ文書に

Reduce ステップは Shuﬄe ステップの結果を集約し, 最終結果

おいては頻繁に変化することはないと考えられるため, 既知とである BM25 を算出するステップである (図 1 中の 4.Reduce).

する.

Shuﬄe ステップの出力データを 2 回走査することで文書 d に

ここで, 式 (1) の第一項目を以降局所的重みと呼び, 式 (2) における索引語 t の出現頻度 tfd,t と文書集合中における索引語 t

示し, 式 (1) の第二項目を以降大域的重みと呼び, 式 (3) に示す.

の文書頻度 dft を算出する. 以上で BM25 の算出に必要な値を2. 2 GPU を用いた重み付け計算手法

全て得ることができたため, Reduce ステップ内で索引語の重み

本節では森谷らによる, Mars を用いた BM25 を計算する手

wd,t を算出する. 最終的な Reduce ステップの出力は<(term,

法 [10] について述べる. この手法の概要を図 1 に示す.

documentID), BM25>となる.

（ 1 ） 文書データの入力（ 5 ） 結果の出力

BM25 の MapReduce を用いた計算手法を述べる. MapRe-

Reduce ス テップ で 得 ら れ た 結 果 を.

duce は key/value ペアを入力とする. したがって, ここでは

BM25>の形でファイルに出力する (図 1 中の 5. 出力). なお,

文書 (document) を key, 各文書に 1 対 1 で割り当てられる文

この出力作業は CPU により行われる.

書 ID(documentID) を value とする. すなわち, <document,<term, documentID,

2. 3 GPUTeraSort

documentID>の key/value ペアを入力データとする (図 1 中の本節では Govindaraju ら [11] による, GPU 上でデータベー

1. 入力). この時, 文書数 N と文書長 dld を求める. 入力されスの莫大なレコードをソートすることを実現した GPUTera-

たデータは, 続く Map ステップでそれぞれ並列に処理される.

Sort について述べる. GPUTeraSort はメモリ集約的, 計算集

なお, 入力作業は CPU 上で行われ, 続く Map ステップから約的な処理を GPU 上で行い, ディスク I/O やリソース管理

Reduce ステップは GPU 上で行われる.

を CPU 上で行うことで高速なソートを実現している. また,（ 2 ） Map

GPUTeraSort は下記の五つのステージから構成される. 入力

Map ステップは, 中間データを key/value ペアで出力する (図データは一度に VRAM に格納できないため, 分割して処理を

1 中の 2.Map). key は, 文書から抽出された索引語 (term) と行う. 分割された各データをチャンクと呼ぶ. 各チャンクに対文書 ID の組から構成される. この時, 抽出した索引語を数える

して, 下記 (1)Reader から (5)Writer 五つのステージを繰り返ことで dld が求まる. value は続く Shuﬄe ステップでは必要とし行う. その際, 高速化のために各ステージはパイプライン処しないため NULL とする. すなわち, Map ステップの出力は理で行われる.

ůŽĐĂůͲDZŐůŽďĂůͲDZ;䝏䝱䞁䜽䜢⏕ᡂ䛷䛝䛺䛟䛺䜛䜎䛷⧞䜚㏉䛩Ϳ

;඲䛶䛾䝏䝱䞁䜽䛻ᑐ䛧䛶ůŽĐĂůͲDZ䜢⤊䛘䛯ᚋ䛻ůŽĐĂůͲDZ䛸ྠ䛨ᅇᩘ⧞䜚㏉䛩Ϳ

ඹ᭷䝯䝰䝸

݂݀௧
;䝝䝑䝅䝳
䝔䞊䝤䝹Ϳ

ܰ
ᩥ᭩㞟ྜ

䐦

䐢

䐟
䝏䝱䞁䜽݅

DĂƉZĞĚƵĐĞ݂݀௧ ሺ݄ܿ‫݇݊ݑ‬௜ ሻdĞƌŵͲ>ŝƐƚ;݅Ϳ

䐣

䐠

䐧

䐡

>ŽĐĂůtĞŝŐŚƚ;݅ͿͲϭ>ŽĐĂůtĞŝŐŚƚ;݅ͿͲϮDĂƉZĞĚƵĐĞ

呍呍呍

䐤

䐥

䐨

DϮϱ
䐩

>ŽĐĂůtĞŝŐŚƚ;݅ͿͲ݉௜ධຊ;䐟͕䐠ͿDĂƉZĞĚƵĐĞ;䐡Ϳ୰㛫⤖ᯝฟຊ;䐢͕䐣͕䐤Ϳ

ධຊ
;䐥͕䐦͕
䐧Ϳ

DĂƉ
ZĞĚƵĐĞ;䐨Ϳ⤖ᯝฟຊ;䐩Ϳ

図 2 提案手法のワークフロー（ 1 ） Readerにバイトニックソートを採用している.

Reader ステージでは, ソートする対象のデータの各チャンクを

GPUTeraSort の性能は様々な要因に左右される. 使用する順にメインメモリに読み込む. この時, 入力データをストライ

GPU の性能はもちろん, メインメモリのバンド幅やディスクピングされたディスクに書き込んでおくことで, ディスク I/OI/O 性能にも影響を受ける. また, パイプラインの各ステージののバンド幅が向上する.

負荷分散を適切に行うことでスループットが向上する. ソート（ 2 ） Key-Generator

対象のデータベースのサイズが極端に小さい場合を除き, デー

Key-Generator ステージでは, ソートする各レコードのポイン

タを VRAM へ転送する時間は計算時間と比較して相対的に小タに対応する Key を用意し, (Key, Record-pointer) ペアを生さくなる. また, チャンクサイズを変化させることにより, 全体成する. このステージは計算集約的ではないが, メモリを多くの実行時間も変化する. 5 ステージから構成されるパイプライ

使用するためメモリ集約的な処理である.

ン処理を行っているため, チャンクサイズの理論上の最大値は（ 3 ） Sorter

メインメモリサイズの 1/5 となる.

Sorter ステージでは, 前のステージで生成したペアを VRAMへ転送し, ソートを行う. このステージは計算集約的であり, メ
モリ集約的でもある. ソート結果は VRAM からメインメモリ

3. 提 案 手 法
本研究は, 既存研究である Mars を用いて BM25 を算出するに転送される.

手法を拡張し, 既存研究では扱うことができない大規模な文書（ 4 ） Reorder集合に対しても効率よく BM25 を計算する手法を提案する.

Reorder ステージでは, 前のステージでソート済みの (Key,

既存研究では, 文書集合全体を一度に VRAM へ転送して計Record-pointer) ペアにならい, 実際にレコードを並べ替える.

算を行うが, 本研究では, 文書集合の全体を一度に VRAM に

この並べ替えられたデータを run と呼ぶ.

転送して計算することができないような, 大規模な文書集合を（ 5 ） Writer

対象とする. そこで, 文書集合を複数のチャンクに分割して計Writer ステージでは, 前のステージで生成された run をディス算を行う. チャンク一つあたりのサイズを大きくすることで,クに書き込む.

中間結果を出力するためのディスク I/O や, VRAM にデータ

（ 6 ） run の集約を転送するためのオーバーヘッドは小さくなる. しかし, 一度以上の五つのステージを全てのデータに対して実行した結果,に多くのデータをソートするため, 計算量は大きくなる. 一方,

複数の run がディスクに書き込まれる. これらの run をマージ

チャンクサイズを小さくすると, オーバーヘッドは大きくなるすることにより, 全データがソートされた最終結果が得られる.

が, ソートの計算量は小さくなる. 特に VRAM とメインメモ

なお, GPUTeraSort のソートアルゴリズムにはバイトニックリ間でデータを転送するためのオーバーヘッドが相対的に大きソートを用いている. バイトニックソートは, 昇順のデータ列

くなる. したがって, 中間結果を出力するためのディスク I/O,と降順のデータ列が交互に出現するバイトニック列を生成しな

VRAM へのデータ転送のオーバーヘッドとデータをソートす

がらソートを行うアルゴリズムである. データを分割してソーる計算量にはトレードオフの関係がある. また, 提案手法では役トを行うことが可能であるため, GPU の得意とする並列計算と割の異なる二つの MapReducce を提案し, それぞれ local-MR

親和性が高い. また, GPU の苦手する条件分岐を行わない点にと global-MR とする. ここで, 提案手法の概要を図 2 に示す.

おいても相性が良い. したがって, Mars もソートアルゴリズム

local-MR と global-MR はそれぞれ図 2 中青枠で囲まれている処理を指す.

dft,i は索引語 t を key とし, dft,i を value とした key/value
ペアと考えることができる. 本研究では, 計算対象をウェブ文

3. 1 local-MR書とするため, 文書集合に同一の索引語が複数回出現するもの

local-MR は, 全てのチャンクに対して逐次的に 1 回ずつ行と考えられる. そこで, 索引語 t と dft,i のペアの集合をメイン

1 から⃝
6 を 1 回の local-MR の入力から出力とわれる. 図 2 の⃝メモリにて保持するためには, 文書集合に出現する全ての索引

し, 全てのチャンクに対して繰り返す. 1 回の local-MR の目的

語を 1 個ずつ格納できるサイズに加え, 索引語の種類と同じ数は, チャンク i 内で索引語 t を含む文書数 dft,i とチャンク i にの整数値 dft を格納できるサイズが必要となる. 一方, この条含まれる文書数 Ni , 更に BM25 を構成する式 (2) の局所的重件を満たしておらず, メインメモリにて保持できない場合には,

み lwd,t を算出することである. 局所的重み lwd,t は局所的統計

中間ファイルとしてディスクに出力することで解決できる. 本

量で構成されるため, チャンクごとに独立に計算を行う.

研究では, 前述のペアの集合をメインメモリに格納できる状況

それに対して, 大域的重み gwt は大域的統計量であるため,を想定し, メインメモリ内に作成するハッシュテーブルにて管文書集合全体に対して計算しなければならない. そのため, 各4理する (図 2 中の⃝).
ハッシュテーブルに登録されていない索

チャンクの local-MR が完了する度に dft,i と Ni を集約する.

引語の dft,i については新たに格納する. 既にハッシュテーブル

その結果, 全てのチャンクに対する local-MR が完了した時点に登録されている索引語については value である dft,i を加算す

で, 文書集合全体における dft と N の算出が完了する.

る. これにより, 全てのチャンクに対して local-MR が完了した以降は, local-MR で上述の dft と N , lwd,t を求める手法を時点で, 文書集合全体における索引語 t を含む文書数 dft が算示す.

出される. また, ハッシュテーブルに dft を格納すると同時に,（ 1 ） 文書集合の分割と入力

チャンク i に含まれる索引語集合を辞書順にテキストファイル

文書集合を予め設定したチャンクのサイズに分割して計算を行に出力する. これは, 続く global-MR で用いられ, ファイルのうため, 読み込む文書のサイズの合計が, 設定したチャンクサイ

5
名前を Term-List(i) とする (図 2 中の⃝).

ズを上回らない最大の文書ファイル数をメインメモリに読み込

lwd,t については, 索引語と文書 ID のペア (term, documen-1
む (図 2 中の⃝).
この時, 読み込んだ文書数をメインメモリ内tID) を key とし, lwd,t を value とした key/value ペアと考えの共有領域に保持しておく. これを, チャンク i における文書数ることができる. この key/value ペアは文書集合全体における,

Ni とする. 新たにチャンクを生成するたびに Ni を足し合わせ

索引語とそれを含む文書の組み合わせの数だけ存在するため,ていくことで, 全ての local-MR が完了した時点で, 文書集合全

文書集合が大きくなるにつれ, メインメモリに保持するには大1体の文書数 N が求まる (図 2 中の⃝).

きすぎるサイズになることが想定される. そこで, lwd,t は中間

続く MapReduce は key/value ペアを入力とする. 既存手法

ファイルとしてテキストファイルに出力する. 出力の形式は１と同様, key を文書, value を文書に 1 対 1 で与えられる文書 ID

行に (term, documentID, lwd,t ) の組を一つ出力する. こことする. すなわち, <document, documentID>を MapReduce

で, global-MR の高速化のために, 中間ファイルは複数に分割

2の入力とする (図 2 中の⃝).

して出力する. このチャンク i における j 番目の中間ファイル（ 2 ） MapReduceの名前を LocalWeight(i)-j とし, ファイル数を mi とする (図 2

前のステップで生成したチャンクに対して, dft,i と Ni を算出

6中の⃝).
LocalWeight(i) は global-MR の入力データとなるが3する MapReduce を行う (図 2 中の⃝).

7(図 2 中の⃝),Mars は入力データの数だけ並列に Map ステッ

Map ステップは, 文書から索引語を抽出する. 抽出した索引プを行う. そのため, LocalWeight(i) を分割することで並列処語を数えることで dld が求まる. そして, 索引語 (term) と文書

理数を増やすことができ, 効率的に MapReduce を行うことがID(documentID) のペアを key とする. value は Shuﬄe ステッ

できる.

プで必要ないため, NULL とする. すなわち, Map ステップの出力は<(term, documentID), NULL>となる.

Shuﬄe ステップは key/value ペアを, key(term, documentID) の第一要素である索引語 (term) で辞書順に並べ替え, 索
引語が等しい key については文書 ID で並べ替える.

N については, 単一の整数であるため, サイズは極めて小さ
い. したがってメインメモリ内に保持する.
以上で, local-MR による N , dft , lwd,t の算出と Term-Listの作成が完了した.

3. 2 global-MR

Reduce ステップは同じ索引語を key に含むペアごとに並列

global-MR の目的は, local-MR で求めた中間結果から BM25に行われる. key を走査し, dcumentID に重複がないようにカを算出することである. global-MR は, local-MR で生成されたウントすることで, 現在扱っているチャンク i における索引語 tチャンクの数だけ繰り返し行われる.

を含む文書数 dft,i が求まる. また, 同一の documentID を持つ（ 1 ） 中間結果の入力

key をカウントすることで tfd,t が求まる. 以上で, lwd,t の算出

はじめに, local-MR が生成した中間ファイル LocalWeight(i)-jに必要な値が全て求まったため, Reduce ステップで算出する.

を読み込む. ここで, 一度の入力でチャンク i から生成されこうして, Reduce ステップの出力は<(term, documentID),

た LocalWeight(i)-1 から LocalWeight(i)-mi の mi 個のファ(dft,i , lwd,t )>の key/value ペアとなる.

7
イルを全て読み込む (図 2 中の⃝).
続く索引語の重みを計（ 3 ） 中間結果の出力算する MapReduce の入力は, key を LocalWeight(i)-j, value

本節では, local-MR の結果を保持する方法について述べる.

をファイルに 1 対 1 に割り当てられる ID とする. すなわち,

global-MR において, パイプライン処理を行うステージをまと䝏䝱䞁䜽1 /ŶƉƵƚDĂƉZĞĚƵĐĞ

KƵƚƉƵƚ

䝏䝱䞁䜽Ϯ

/ŶƉƵƚ

DĂƉ
ZĞĚƵĐĞ

KƵƚƉƵƚ

/ŶƉƵƚDĂƉZĞĚƵĐĞ䝏䝱䞁䜽ϯめる.
（ 1 ） Input（ 2 ） MapReduce（ 3 ） Output
KƵƚƉƵƚ

図 3 パイプライン処理の概要<LocalWeight(i)-j, FileID>である.
続いて, Term-List(i) を参照し, チャンク i に出現する索引語の dft をハッシュテーブルから取り出し<term, dft >ペアの集

Input ステージと Output ステージは local-MR, global-MR そ
れぞれにおけるデータの入出力を行うステージである. MapRe-duce ステージは MapReduce 処理と, それに必要な入力や出力データを VRAM とメインメモリ間で転送するステージである.
本研究では, 上記の 3 ステージをパイプライン処理で行うこと
で高速化を行う.

8
合を生成する. この集合を dft (chunki ) とする (図 2 中の⃝).

3. 4 コストモデル

dft (chunki ) は Reduce ステップの引数として VRAM へ転送

以上の議論から, 提案手法の実行時間を見積もるためのコ9する (図 2 中の⃝).
同時に, N も VRAM へ転送する.

ストモデルを立てる. 提案手法の実行時間はチャンクサイズ c（ 2 ） MapReduce

を変数とした関数 AllT ime(c) とみなすことができる. また,

MapReduce を行い, 最終的結果である BM25 を求める (図 2

local-MR, global-MR どちらにおいても, Input, Map, Reduce,

10
中の⃝).

Output ステップは計算量 O(c) の処理であり, Mars では Shuﬄe

Map ステップは, 入力データの key である LocalWeight(i)-j

ステップ内でバイトニックソートを使用しているため, Shuﬄe

ファイルから索引語, 文書 ID, lwd,t を抜き出し, 出力する. しステップは計算量 O(c(log c)2 ) の処理であると考えられる. したがって, 出力 key/value ペアは, key を索引語, 文書 ID, value

たがって, Input, Map, Reduce, Output ステップの各合計実行

を lwd,t とする. すなわち, <(term, documentID), lwd,t >で

時間は下記式 (4), Shuﬄe ステップの合計実行時間は下記式 (5)ある.

で表すことができると仮定する.

Shuﬄe ステップは key/value ペアを, key(term, documentID) の第一要素である索引語 (term) で辞書順に並べ替え, 索•Input, Map, Reduce, Output ステップの各合計実行時

間 Ti (c), Tm (c), Tr (c), To (c)引語が等しい key については文書 ID で並べ替える.

S ′(A c + B ′ )c
SB ′= SA′ +c
B=A+
c

Ti (c) =Reduce ステップは同じ索引語を key に含むペアごとに並列に行われる. global-MR の入力時に, VRAM へ転送された<term, dft >ペアのリストから, Reduce ステップの当該スレッドが担当する索引語の dft 値を探索する. また, N も既に入力
時に VRAM に転送されているので参照可能である. 以上で,gwt の算出に必要な全ての値が揃ったため gwt を算出し, lwd,tとの積を求めることで BM25 による索引語重みとなる. こうし(4)

Tm (c), Tr (c), To (c) はいずれも Ti (c) と同様である.
• Shuﬄe ステップの実行時間 Tsて, Reduce ステップの出力は<(term, documentID), wd,t >のTs (c) =key/value ペアとなる.

S ′(A c(log c)2 + B ′ c)c

= SA′ (log c)2 + SB ′（ 3 ） 最終結果の出力(5)以上の global-MR を繰り返すことで, 全ての文書内の全ての= A(log c)2 + B

索引語に対する BM25 の算出が完了する. この結果をテキA′ , B ′ は式変形中にのみ出現する定数である. A, B は実験から

11
ストファイルに出力する (図 2 中の⃝).
出力の形式は (term,

documentID, wd,t ) とする.
3. 3 パイプライン処理
本研究では, 上述の local-MR と global-MR をそれぞれ三つのステージに分割し, パイプライン処理を行っている. local-MR

求めることが可能な各ステップごとに異なる定数であり, S は文書集合のサイズである. したがって, Sc は文書集合の分割数,
すなわちチャンク数である. ここで, パイプライン処理における MapReduce ステージの合計実行時間 Tmr (c) は下記式 (6)となる.

は各チャンクごとに, global-MR は LocalWeight(i) ごとにパイ
プライン処理を行う. その概要を図 3 に示す. ただし, 全てのチャンクに対して local-MR の処理が完了するまで dft と N の算出が完了しないため, global-MR を開始することができない.
また, パイプラインの各ステージはそれぞれ独立したプロセスで行われる. ステージ間のデータの受け渡しは高速に行う必要があるため, メインメモリ内の共有領域にデータを置くこととする.
パイプライン処理の構成を述べる. はじめに, local-MR とTmr (c) = Tm (c) + Ts (c) + Tr (c)
)
(
)
(
(
)
Br
Bm
2
+ As (log c) + Bs + Ar += Am +cc
Bm + Br+ Am + Arc
B= A(log c)2 ++D
c= As (log c)2 +(6)Am , Bm , As , Bs , Ar , Br はいずれも式変形中にのみ出現する定ϲϬϬ数である. また, A, B, D は実験から求めることができる定数でϱϬϬある. 以上より, AllT ime(c) は下記式 (7) となる.

ϰϬϬ䝏䝱䞁䜽䝃䜲䝈

+ max⟨Ti:g (c), Tmr:g , To:g (c)⟩⛊AllT ime(c) =max⟨Ti:l (c), Tmr:l , To:l (c)⟩
(7)

ϱD
ϭϬD
ϱϬD

ϯϬϬ
ϮϬϬ
ϭϬϬ

ここで, 実行時間を表す T (c) の添字に含まれる l, g はそれぞ

Ϭ

ϱϬD

れ local-MR と global-MR を意味する. また, max⟨a, b, c⟩ は

ϮϱϬD

ϱϬϬD

ϭ'

Ϯ'

ᩥ᭩㞟ྜ

a, b, c の内, 最大のものを表す.
図4

4. 評 価 実 験

提案手法の実行時間

ϲϬϱϬ

本節では, 提案手法の有効性の検証のための評価実験についϰϬ

行時間を計測した. また, 森谷らの提案した手法 [10] との比較
も行った.

⛊

て述べる. 本研究の提案手法による索引語の重み付け計算の実ϮϬ

なお, 評価実験には下記の PC を用いた.

ϭϬ•

CPU: Intel Core i7-4790 (3. 6GHz, 4 コア)•Ϭ

メインメモリ: 16GB•

HDD: TOSHIBADT01ACA200(2TB)•

OS: CentOS 7•

GPU: NVIDIA GeForce GTX TITAN Z

なお, GPU の VRAM のサイズは 6GB である.

/ŶƉƵƚDĂƉZĞĚƵĐĞ
KƵƚƉƵƚ

ϯϬ

ϱD

ϭϬD

ϱϬD

䝏䝱䞁䜽䝃䜲䝈

図 5 各チャンクサイズにおける local-MR のパイプラインのステージ合計実行時間(文書集合サイズ 500MB)

4. 1 実 験 準 備
本実験にはウェブからクローリングした英文文書から, 索引
語のみを抽出したテキストファイルの集合を文書集合とした.
文書集合のサイズは, 50MB, 250MB, 500MB, 1GB, 2GB の 5種類である.

4. 2 提案手法の実行時間
まず, 提案手法においてチャンクサイズを変更させた時の実
行時間の変化を図 4 に示す. チャンクサイズは, 5MB, 10MB,

50MB の 3 種類で実験を行った. いずれの文書集合においても,
チャンクサイズが 10MB の場合に最も良い結果が得られた.
図 5, 図 6 に各チャンクサイズにおける, パイプラインのス
テージごとの合計実行時間を示す. いずれも 500MB の文書集
合を使用した. 図 5 が local-MR, 図 6 が global-MR における結果である. つまり. 最も実行時間の長いステージが local-MR,

global-MR それぞれの実行時間となり, それらを足した値が全体の実行時間となる. 例として, 図 3 において, チャンク１のOutput ステージ, チャンク 2 の MapReduce ステージ, チャン
ク 3 の Input ステージは同時に実行が開始されため, その中で最も実行時間が長いステージが全体の実行時間となる. local-MRではチャンクサイズが小さいほどディスク I/O のオーバーヘッ
ドが大きくなり, Input ステージと Output ステージの実行時間は長くなる. 一方, MapReduce ステージではチャンクサイズが小さいほど Shuﬄe ステップで行うソートのオーバーヘッド
は小さくなるが, VRAM とメインメモリ間でのデータ転送のオーバーヘッドは大きくなる. つまり, ソートにかかるコストとデータ転送にかかるコストはトレードオフの関係にあり, チャ
ンクサイズが 10MB の場合が最良の結果となった. global-MR
においても local-MR と同様の理由により, チャンクサイズが小さいほど Input ステージと Output ステージの実行時間は長くなる. 一方, global-MR の MapReduce ステージの実行時間
はチャンクサイズが大きいほど短くなる. これは, global-MRの Shuﬄe ステップでソートするデータ数が local-MR よりも少なく, チャンクサイズを大きくしても Shuﬄe ステップの実行
時間の変化が小さいためである. 理由を詳述すると, local-MRでソートするデータ数は, チャンクに含まれる文書の文書長 (=文書に含まれる索引語数) の合計に等しいのに対し, global-MRでソートするデータ数は, 索引語とそれを含む文書の重複のな
い組み合わせの数に等しいため, このような結果が得られる.
図 7, 図 8 に各チャンクサイズにおける, ステップごとの合計実行時間を示す. いずれも 500MB の文書集合を使用した. 図 7 がlocal-MR, 図 8 が global-MR における結果である. local-MRにおいては, チャンクサイズを大きくするにつれて Shuﬄe ス
テップの実行時間が増えている. これは, Mars が Shuﬄe ステッ
プで行うソートアルゴリズムに, 計算量 O(N (log N )2 ) のバイ
トニックソートを使用しているためである. また, Map ステッ
プではチャンクサイズが大きい場合に実行時間が短くなっている. Map ステップでは複数の文書が GPU のコアに分散されて並列に処理されるため, チャンクサイズが小さい場合は並列度が低くなるためである. global-MR においても, Map ステップ
は local-MR と同様の理由により, チャンクサイズが大きい場
合に実行時間は短くなる. global-MR における Shuﬄe ステッ
プの処理時間は local-MR に比べて短くなっている. これは, 前
述の通り global-MR でソートするデータ数が local-MR よりも少ないためである.
図 9 に, 提案手法においてパイプライン処理を行わず逐次処理で行った場合の実行時間を示す. 各文書集合において最も処理時間が短いチャンクサイズを太字で示す. 逐次処理で行う

ϯϱ

逐次処理を行う場合とパイプライン処理を行う場合の最も高速ϯϬ

な結果を比較すると, 文書集合 1GB, 2GB ではパイプライン処
Ϯϱ理を行うことで約 2.1 倍の高速化を実現できた.

⛊

ϮϬ

/ŶƉƵƚ
DĂƉZĞĚƵĐĞ
KƵƚƉƵƚ

ϭϱϭϬ

4. 3 コストモデルの評価
本節では, 4 章で設計したコストモデルの評価を行う. 本節で扱う文書集合のサイズは全て 500MB とする.

ϱ
Ϭ

ϱD

ϭϬD

T:
T:
T:

ϱϬD
ᐇ⾜᫬㛫;䝭䝸⛊Ϳ䝏䝱䞁䜽䝃䜲䝈

図 6 各チャンクサイズにおける global-MR のパイプラインのステージ実行時間(文書集合サイズ 500MB)
ϴϬ
ϳϬ
ϲϬ

⛊

ϱϬ

KƵƚƉƵƚ
ZĞĚƵĐĞ
^ŚƵĨĨůĞ
DĂƉ
/ŶƉƵƚ

ϰϬ
ϯϬ
ϮϬ
ϭϬ

䝏䝱䞁䜽䝃䜲䝈;DͿ

図 10 local-MR におけるコストモデルグラフ

チャンクサイズを 2MB から 50MB の間で 2MB ずつ変化させ, ステップごとの合計実行時間を計測する. その結果から, コ

Ϭ

ϱD

ϭϬD

ϱϬD

ストモデルの各式中の定数 A, B, D を求めることができる. そ䝏䝱䞁䜽䝃䜲䝈

の際, Shuﬄe ステップの合計実行時間 Ts において, チャンク
図 7 各チャンクサイズにおける local-MR の

サイズ c が十分小さい値で変化するため, (log c)2 ≒ log c と各ステップの合計実行時間

した. 図 10 にコストモデルによる各ステージの合計実行時間(文書集合 500MB)ϴϬ

Ti:l , Tmr:l , To:l を示す. チャンクサイズが約 9MB の場合を境に

ϳϬ

Tmr:l が Ti:l を上回っていることがわかる.

ϲϬ

⛊

ϰϬ
ϯϬ
ϮϬ
ϭϬ

T:
T:
T:

ᐇ⾜᫬㛫;䝭䝸⛊ͿKƵƚƉƵƚ
ZĞĚƵĐĞ
^ŚƵĨĨůĞ
DĂƉ
/ŶƉƵƚ

ϱϬ

Ϭ

ϱD

ϭϬD

ϱϬD

図 8 各チャンクサイズにおける global-MR の䝏䝱䞁䜽䝃䜲䝈;DͿ

各ステップの合計実行時間⛊(文書集合 500MB)

図 11 global-MR におけるコストモデルグラフ

ϮϬϬϬ
ϭϴϬϬ
ϭϲϬϬ
ϭϰϬϬ
ϭϮϬϬ
ϭϬϬϬ
ϴϬϬ
ϲϬϬ
ϰϬϬ
ϮϬϬ
Ϭ

同様に global-MR について, 図 11 にコストモデルによる各ステージの合計実行時間 Ti:g , Tmr:g , To:g を示す. チャンクサイ
䝏䝱䞁䜽䝃䜲䝈

ϱD
ϭϬD
ϱϬD

ϱϬD

図9

ϮϱϬD

ϱϬϬD
ᩥ᭩㞟ྜ

ϭ'

Ϯ'

パイプライン処理を行わない場合の実行時間

場合, パイプライン処理で行う場合と異なり文書集合 50MB,

250MB ではチャンクサイズが 10MB, 文書集合 500MB 以上ではチャンクサイズが 50MB の場合に最も良い結果が得られた.

ズが約 6MB の場合を境に To:g が Ti:g を上回っていることがわかる.
以上より, 全体の実行時間 AllT ime(c) を求めることができる.


(2 <

= 約 6)=c< To:l + Ti:g
AllT ime(c) =(8)To:l + To:g
(約 6 < c < 約 9)

 T
(約 9 <
mr:l + To:g= c)
図 12 は, AllT ime(c) をグラフで表した図である. グラフから, AllT ime(c) はチャンクサイズが約 9MB の場合に最小値を取ることがわかる. 評価実験ではチャンクサイズが 10MB の場合が最良であったので, コストモデルの結果と概ね一致する.
以上により, 提案したコストモデルの妥当性を示した.

更に, 高速化のために文書中の文字列の扱い方を変えることᐇ⾜᫬㛫;䝭䝸⛊Ϳ

が考えられる. 本研究の提案手法では, 文字列に対するソート
処理や,T:  T:T:  T:T:  T:ᐇ ್

文字列をハッシュテーブルのキーとしている. GPU

上で索引語を文字列のまま扱うことはコストが大きくかかるため, 若月ら [12] は文字列である索引語を整数値と紐付ける辞書をメインメモリ上に構築し, GPU で処理を行う前に文字列を整数値に変換することで高速化を実現した. この手法を本研究にも適用することで, 更に効率的に大規模な文書の処理を行うことができると考える.

䝏䝱䞁䜽䝃䜲䝈;DͿ

謝⛊

図 12 AllT ime(c) のグラフ
ϭϬϬ
ϵϬ
ϴϬ
ϳϬ
ϲϬ
ϱϬ
ϰϬ
ϯϬ
ϮϬ
ϭϬ
Ϭ

本研究の一部は, JSPS 科研費 JP26280115, JP15H02701,

JP16H02908, JP15K20990 の助成を受けたものである. ここに記して謝意を表す.
᳃㇂䜙䛾ᡭἲ
ᥦ᱌ᡭἲ

文

ϱϬD

ϮϱϬD
ᩥ᭩㞟ྜ

図 13 森谷らの手法と提案手法の実行時間

4. 4 既存手法との比較
続いて, 森谷ら [10] の提案した, チャンクに分割せず一度に全データに対して処理を行う手法の実行時間と, 提案手法の実行時間を図 13 に示す. 提案手法の実行時間は, チャンクサイズを10MB とした時のものである. なお, 森谷らの手法では 500MBの文書集合ではメモリ不足であったため, 50MB と 250MB における比較結果のみを掲載する. 50MB の文書集合に対しては 1.9 倍, 250MB の文書集合に対しては 2.5 倍の高速化を実現
した.

5. お わ り に本研究は, GPU を用いて正確な情報検索のための索引語の重み付けを行う際に, データの分割を行うことで, 大規模デー
タに対しても処理を行うことを可能とした. また, コストモデルを立て、検証を行うことで提案手法の実行時間の挙動を把握すると共に, 最適なチャンクサイズを計算により推定することが可能となった. その結果, 最適なチャンクサイズは, 一度にVRAM に転送して計算を行うことができる最大のサイズではなく, VRAM へデータを転送するコストやソートに要する時間の観点から, VRAM のサイズに対して小さな 10MB 程度を
チャンクサイズとすることが良いということが判明した. 更に,計算の各ステージに対してパイプライン処理を施すことで, 効率よく計算を行うことを実現した.
今後の課題として, 計算を行うマシンを増やすことでスケールアウトを行い, より大規模な文書集合を高速に処理することが考えられる. しかし, 文書集合を複数のマシンに分散することで, BM25 による重み算出に必要な文書集合全体における dftと N を単純には算出することができない. したがって, マシン
間で dft と N を効率的に集約 · 共有する手法を考案する必要が
ある.

辞

献

[1] Christopher D. Manning, Prabhakar Raghavan, Hinrich
Schütze, “Introduction to Information Retrieval”, Cambridge University Press. 2008.
[2] K. S. Jones, S. Walker, S.e. Robertson, “A probabilistic
model of information retrieval: Development and comparative experiments”, Information Processing and Management, 36 (6): 779-808, 809-840, 2000
[3] J. Lin, C. Dyer, “Data-Intensive Text Processing with
MapReduce”, Morgan & Claypool Publisher, 2010[4] S. Tatikonda, F. Junqueira, B.B. Cambazoglu, V. Plachouras, “On eﬃcient posting list intersection with multicore processors”, In Proc. of the 32nd ACM SIGIR, pp.738–
739, 2009[5] S. Tatikonda, B.B. Cambazoglu, F. Junqueira, “Posting list
intersection on multicore architectures”, In Proc. of the 34th
ACM SIGIR, pp.963–972, 2011[6] J. Dean and S. Ghemawat, “Mapreduce: simplified dataprocessing on large clusters”, Commun. ACM, 51(1):107113, 2008
[7] C. Ranger, R. Raghuraman, A. Penmetsa, G. Bradski, C.
Kozyrakis, “Evaluating mapreduce for multi-core and multiprocessor systems”, In Proceedings of the 2007 IEEE 13th
International Symposium on High Performance Computer
Architecture (HPCA ’07), pp. 13–24, Washington, DC,
USA, 2007[8] B. He, W. Fang, Q. Luo, N. K. Govindaraju, T. Wang,“Mars: A MapReduce Framework on Graphics Processors”,
In Proc. of PACT 2008, pp. 260–269, 2008[9] M. Garland et al. , “ Parallel Computing Experiences with
CUDA”, IEEE Micro, Vol. 28, Iss. 4, pp. 13–27 , 2008[10] 森谷 祐介, 欅 惇志, 宮崎 純「GPU を用いた MapReduce による高精度検索のための高速な重み計算」第 7 回データ工学と情報マネジメントに関するフォーラム, 2015[11] Naga K. Govindaraju, Jim Gray, Ritesh Kumar, Dinesh
Manocha “GPUTeraSort: High Performance Graphics Coprocessor Sorting for Large Database Management” ACM
SIGMOD 2006, 325-336[12] 若月駿尭, 欅 惇志, 宮崎 純「効率的なテキスト処理を目指した
簡潔データ構造を用いるトライ木の GPU 上での実装」第 8 回
データ工学と情報マネジメントに関するフォーラム, 2016