ツールキット解説書
ver.1.0
この文書はSACSIS2009併設企画
Multicore Programming Contest Cell Challenge 2009の
ツールキット解説ドキュメントに基づいています
Special Course on Computer Architecture 2009
これはなに?
• 課題に取り組む際のベースとなる
ツールキットの解説書です
• 「文字列の編集距離計算」のアルゴリズム
を説明します
Special Course on Computer Architecture 2009
課題
「文字列の編集距離計算」
• 2つの文字列の近さを計る方法
• かな漢字変換エンジンや,DNAの相同性検索などに利用される
• 2つの文字列の 編集距離
– 片方の文字列から,もう一方の文字列を得るための操作回
数の最小値
– 使用可能な操作は以下の3種類
• 削除:1つの文字を取り除く
• 挿入:1つの文字を新たに付け加える
• 置換:1つの文字を別の文字で置き換える
– 参考になるURI「wikipedia:レーベンシュタイン距離」
http://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A
5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2
Special Course on Computer Architecture 2009
編集距離計算の
アルゴリズムについて
Special Course on Computer Architecture 2009
編集距離の操作例
• 「weight」と「write」の編集距離
• 以下の操作で「weight」から「write」になる

1.
2.
3.
4.
weight
weighte (挿入:e)
wrighte (置換:e → r)
wrihte (削除:g)
write (削除:h)
• 3回以下の操作では「weight」を「write」にできない
• よって編集距離は 「4」
• 削除,挿入,置換は文字列の中のどの位置で
行ってもよい
Special Course on Computer Architecture 2009
編集距離計算のアルゴリズム(概要)
• 「動的計画法(Dynamic Programming)」が有名
weight
文字列1
write
文字列2
• 操作回数を表を作って求める
w
weight
write
w
r
i
t
e
e
i
g
h
t
操作回数を
格納する
テーブル
編集距離計算のアルゴリズム(手順)
このスライドには
アニメーションが設定されています
1.
最左列,最上行のセルは1~N,
1~Mの値と仮定
2.
上,左上,左のセル値と,当該の行
と列の文字列を使い,以下の方法で
各セルの値を計算する
N
1
2
3
4
5
6
0
w
e
i
g
h
t
1
w
0
1
2
3
4
5
2
r
1
1
2
3
4
5
3
i
2
2
1
2
3
4
4
t
3
3
2
2
3
3
5
M
e
4
4
3
3
3
4
アニメーションでは列ごとに計算しているが,
「上,左上,左のセル値」が決定しているセル
ならば計算手順は任意
A)
B)
C)
D)
E)
3.
4.
文字列が同一ならば左上セルの値
異なるならば左上セルの値+1(置換)
左セルの値+1(挿入)
上セルの値+1(削除)
(A)-(E)の最小値をセルの値に設定
テーブルの左上から値を求める
右下端のセル値が最終的な
編集距離となる
Special Course on Computer Architecture 2009
アルゴリズムのブロック化
このスライドには
アニメーションが設定されています
0
w
e
i
g
h
t
w
0
1
2
3
4
5
r
1
1
2
3
4
5
i
2
2
1
2
3
4
t
3
3
2
2
3
3
4
4
3
3
3
4
e
Block1
Block3
Block2
Block4
• 編集距離計算はブロック化して部分ブロ
ックごとに計算を行う
• 以下のデータがあれば,各ブロックの
計算が可能
– 文字列
– 最左列,最上列の値
• ブロック計算の入力は以下
– 部分文字列(各問題文字列中の該当部分)
– 最左列,最上列のセル値
• 出力は以下
– 最右列,最下行のセル値
• ツールキットでは,各ブロックの最右列,
最下行の値をメモリのユーザ領域に
格納,適宜読み出して使用する
課題の条件と
ツールキットの使い方
Special Course on Computer Architecture 2009
課題の条件
• ある文字列に対する編集距離を計算せよ.
• 編集距離計算は,複数の文字列を対象とし
ある制限時間内に計算できる文字列の数を
最大にせよ.
Special Course on Computer Architecture 2009
課題への取り組み方
• PPEプログラム(ppe.c)および
SPEのプログラム(spe1.c) を実装する
– 以下のプログラムを実装してください
• 編集距離を計算するPPE,SPEプログラム(ppe.c, spe1.cなど)
• 必要に応じてppe_user()関数
• speプログラムはppe_user()関数内から呼び出し(ツールキット参照)
• Makefile
(SPEごとに別のバイナリを実行したい場合は修正が必要です)
– 以下のファイルは変更が許可されません
• PPEプログラム(main_ppe.c,define.h)
Special Course on Computer Architecture 2009
ツールキット ver1.0
• 2つのテキストファイルを入力すると,それらの中の
文字列を読み込んで編集距離を求める
• 複数のSPEを使用する
• 制約:各文字列の文字数は128の倍数
– いろいろなサイズの例題ファイル付き
(file1, file2, … , file20)
• getrndstr.c を使用すると,任意長のランダム文字列
を生成できる
$ gcc -O3 -o getrndstr getrndstr.c
$ ./getrndstr 128 13 > file9999
乱数種13で生成される128文字の文字列を格納したファイルfile9999を生成する
Special Course on Computer Architecture 2009
makeでコンパイル
• Makefile を開き,“USERNAME”を自分の
ログイン名に変更
• コンパイルする
Special Course on Computer Architecture 2009
make run で実行
実行バイナリ, 文字列ファイル
複数文字列ファイルのあるディレクトリ
文字列ファイル(src_str) の文字列長
SPEの計算結果と,PPE に
格納されている答え ( 一致してればOK )
計算時間
Special Course on Computer Architecture 2009
制約 : メモリ領域の割当
• PPEからSPEに渡される変数 (先頭アドレス)
• 各文字列が配置されるメインメモリ上の領域
– str1, str2 それぞれ1MB
• 距離計算結果格納領域 (ans[0]に回答を格納すること)
– ans
128B
• 各文字列の長さnum1, num2
上記を含めたPPE,SPEの各メモリを
自由に使用できます
Special Course on Computer Architecture 2009
ツールキットver1.0の計算手順
• SPEを複数使用し編集距離を計算するコードの例
– main_ppe.c, define.h以外のファイルは編集可能
– 各SPEでの計算は,128文字を1単位とするブロックで行う
Special Course on Computer Architecture 2009
制約の確認
• 文字数は128の倍数(かつchar型)
• 問題で与えられる2つの文字列をそれぞれ文字列A,
文字列Bと呼ぶことにする
•
•
•
•
コードはlibspe2準拠
PPEでも処理のプログラムを書いてよい
SPEは7つまで使用可能
PPEのメモリは自由に確保してよい
Special Course on Computer Architecture 2009
問題へのアプローチ
• 文字列をブロックに分割すると,処理単位をある程度の
大きさに分けることができる
• ブロックの計算を各SPEで並列に実行できると速そう!
• どこが並列計算できるんだろう?
Special Course on Computer Architecture 2009
並列計算できる部分の確認(1/3)
要素
• データの依存関係
– スコアテーブルの各
要素は,左上,上,
左の要素の値が定
まっていると計算で
きる
Special Course on Computer Architecture 2009
並列計算できる部分の確認(2/3)
要素
• 水色が計算済みで
あれば赤色は並列
に計算可能
• これはブロックごと
でも適用できる!
Special Course on Computer Architecture 2009
並列計算できる部分の確認(3/3)
• ブロックの場合は
block
block
block
– 左上のブロックの
(一番右下の)要素
– 上のブロックの要素
行 (最下行)
– 左のブロックの要素
列(最右列)
の情報があれば
計算できる
Special Course on Computer Architecture 2009
ブロック計算の入出力
• 入力
– 左上のブロックの
(一番右下の)要素
– 上のブロックの要素行 (最下行)
– 左のブロックの要素列(最右列)
• 出力
–
–
–
–
計算後のスコアテーブルの..
(一番右下の)要素
最下行
最右列
Special Course on Computer Architecture 2009
メインメモリの使用法(1/2)
• ブロック計算の中間データを別々に保持して
おくとデータ量が非常に大きくなってしまうの
で,使いまわすことにする
1
2
3
4
保持しなければならない最下行
保持しなければならない最右列
• 右下要素はbnum1 x 2個の領
域を使いまわす
• 最下行は1つ上のブロックの計
算,最右列は1つ左のブロック
の計算以降は使わないので,
それぞれ文字列A,Bのブロック
数だけ保持しておけば良い
メインメモリの使用法(2/2)
• buf3中に各ブロックの出力を保持する領域を
決め,データを保持することにする
buf3
128*bnum1個の32bitデー
タによる領域
• 文字列Aがbnum1ブロック,Bがbnum2
ブロックに分けられるとすると,左図の通
り
128*bnum2個の32ビット
データによる領域
bnum1*2個の
32ビットデータによる領
域
保持しなければならない最下行
保持しなければならない最右列
各ブロックの右下の要素
(処理の開始終了フラグと一緒に転送する)
並列処理の方法
• 各SPEにどうやって処理を投げる?
SPE
SPE
PPE
計算開始通知
Job Queue
Tail
• PPE上でジョブキューを作り,各SPE
はフラグを見て処理の開始を知り,そ
こで指定されたブロック番号に従い,
SPE
SPE
計算対象のブロックの計算を行う
PPEでの処理
• 計算終了したブロック番号を元
に,計算が可能になるブロック番
号をキューに追加
計算終了通知
• 基本的に右と下のブロックが計
算可能ブロックの候補になる
次に計算するブロックの格納
• 処理が空のSPEに対し,キュー
から読み出したブロック番号を通
知し,計算させる
Head
• 右下のブロックの計算終了まで
続ける
補足)DMA転送用サブルーチン
• 転送用の命令
• dmaget, dmaput : ツールキットで使用されるDMA読み書き
関数
• dmaget((void*))spe_addr, ppe_addr, X);
メインメモリ領域のアドレスppe_addrを先頭としてXByteを読み出し,LocalStoreのアドレス
spe_addrから始まる領域に格納する.dmaputは逆方向.
SPE(LocalStore)
PPE(メインメモリ)
ppe_addr
spe_addr
128Byteアライメント
されたアドレス
Special Course on Computer Architecture 2009
おわり
Special Course on Computer Architecture 2009
ダウンロード

文字列の編集距離計算