学位論文 OpenCLによる疎行列圧縮形式の評価

工藤, 健史

pp.1 - 37 , 2016-03-25
内容記述
当研究室では,現在「大規模文書群の走査と語句抽出・収集の効率的手法の確立」の研究を行っている. 大規模文書群の解析では,一般的に文書群内全ての文書から出現した単語を抽出し,出現した単語とその出現頻度からなる特徴ベクトルを作成する.これをBag of words 形式と呼ぶ.取得するデータを文書群としたとき,文書毎に作成された特徴ベクトルを並べることで行列を生成することが出来る.この生成された行列はその要素の大半が0である疎行列となる.これは取得した全ての文書に出現するユニークな単語数に対し,あるひとつの文書に出現するユニークな単語数が極端に小さいからである.例として当研究室で使用しているデータでは,30,000文書で約100,000種類の単語が出現するが,1文書では約300種類の単語しか出現せず,非零要素の割合は全体で約0.3%である.このようにBag of words 形式を用いた文書群のクラスタリングには一般に大規模な行列を用いるが,先述の通り要素の大半が0となる疎行列である.Bag of words 形式を用いた文書群のクラスタリングには大きな疎行列(100,000×100,000等)の形式が必要となる.したがって疎行列の高速な取り扱いが研究のポイントとなる.著者が取り組んだ研究は、疎行列の圧縮方法の評価である.Bag of words 形式から得られる疎行列は膨大な量だが,圧縮処理を施すことでメモリ使用量の削減と計算速度の向上を見込める.疎行列圧縮実装の実行環境にOpenCL(Open Computer Language)を選択した.OpenCLとはCPU (Central Processing Unit)やGPU(Graphics Processing Unit)を用いたプログラミングを可能とする言語である.以前は画像処理のみにGPUは用いられてきたが,大量の並列処理が可能な点から画像処理以外の汎用化が進められている.このように画像処理以外の用途でGPUを用いることをGPGPU (General Purpose GPU)と呼ぶ.OpenCLはベンダーにとらわれないあらゆる環境での開発が可能となっている.圧縮形式にはCOO (Coordinate)形式,CRS非零要素が位置する座標を3種類の配列を用いて格納するものである.CRSはCOOにおける3種類の配列のうちひとつをさらに圧縮処理したもので,COOの発展版と位置づけられる.BSSはCRSからさらに格納情報を増やし,効率のよい並列処理演算を可能にしたものである.しかしBSSはこれまでGPU上での実装はされていない.これはBSSを利用した計算に一部並列化できない部分が存在した為と考えられる.著者はBSSでの格納情報を既存のものからさらにもうひとつ加えることでGPU 上でのBSSの実装を行った.COOとCRS,著者が拡張したBSSを,OpenCLを用いたGPU上で実行し,その評価に疎行列ベクトル積に必要な計算時間を用いる.疎行列ベクトル積は各形式で圧縮した形から同サイズのベクトルを掛け合わせた際の計算であり,その応答時間を評価対象とした(疎行列をAとし与えるベクトルをxとすると,y = Ax となる計算結果yを求める時間).疎行列ベクトル積に用いる行列はフロリダ大学が提供しているものを幾つか使用し,行列のサイズや疎率(非零要素のばらつき具合)の違いによって圧縮形式毎にどのような違いが発生するのかを定量的に考察した.
首都大学東京, 2016-03-25, 修士(理学)
本文を読む

https://tokyo-metro-u.repo.nii.ac.jp/?action=repository_action_common_download&item_id=2151&item_no=1&attribute_id=18&file_no=1

このアイテムのアクセス数:  回

その他の情報