toolkit

ツールキット解説書
version 1.0
Special Cource on Computer Architectures 2010
1
内容
 課題に取り組む際に用いるツールキットの解説
 課題「最長共通部分列の計算」のアルゴリズム
 toolkit ver1.0の使いかた
 最速のプログラムを目指して
Special Cource on Computer Architectures 2010
2
課題の条件
 ある2つの文字列AとBについて，最長の共通部分列を
計算せよ
 複数の種類の文字列を対象とするようにし，制限時間
内にできるだけ多くの計算を行えるようにせよ。
Special Cource on Computer Architectures 2010
3
最長共通部分列の計算(1/4)
 最長共通部分列 (Longest Common Subsequence : LCS)
 Subsequenceとは，いくつかの要素をとりだし生成した系列
 X = < A, B, A, B, C> の場合
 <A, B>, <A, B, C>, <B, A>, <A, A>, <A, B, B, C> など
 連続してなくてもOK，順序だけは守る
 二つの系列について，共通する部分列を求めよう
 X = <A, B, C, A> , Y = <A, B, A> の場合
 最長の共通部分列は<A, B, A> で，長さは3
 (参考)
http://en.wikipedia.org/wiki/Longest_common_subsequence_pr
oblem
Special Cource on Computer Architectures 2010
4
最長共通部分列の計算(2/4)
 どのように計算する?
 二つの系列X, Yがあったとき，i番目とj番目のLCSは，よ
り小さな系列のLCSから計算ができる
 LCS(i, j) の値は，
 LCS(i-1, j)
 LCS(i , j-1)
 LCS(i-1, j-1)
がわかっていれば求めることができる
Special Cource on Computer Architectures 2010
5
最長共通部分列の計算(3/4)
 一番後ろの文字が等しい場合
 Xi = <..., A>
 Yj = <..., A>
LCS(i , j) は LCS（i-1, j-1) + 1
 一番後ろの文字が等しくない場合
 Xi = <..., A>
 Yj = <..., B>
LCS(i, j) はLCS(i-1, j)かLCS(i, j-1)の大きいほう
Special Cource on Computer Architectures 2010
6
最長共通部分列の計算(4/4)
 動的計画法 (Dynamic Programmming, DP) が有名
 X = <A, B, C, A> , Y = <A, B, A> の場合
A
B
A
0
0
0
A
0
1
1
1
B
0
1
2
2
C
0
1
2
2
A
0
1
2
3
LCS!!
Special Cource on Computer Architectures 2010
左のような表を考えた場合，前スライド
のアルゴリズムは，
上，
max 左，
左上 + (Xi == Yj ) ? 1 : 0
と書き表すことができる。
左上のセルから計算を始め，上記規則に
従って次々とに値を計算していく
7
課題への取り組み方
• PPEで動作するプログラム(ppe.c) および
SPEで動作するプログラム(spe.c) を実装する
– 以下のプログラムを実装してください
• 最長共通部分列を計算するPPE，SPEプログラム(ppe.c, spe.c
など)
– 以下のファイルは変更が許可されません
• PPEプログラム(main_ppe.c，define.h)
Special Cource on Computer Architectures 2010
8
toolkit ver1.0の計算手順
• SPEを複数使用し編集距離を計算するコードの
例
– main_ppe.c, define.h以外のファイルは編集可能
– 各SPEでの計算は，128文字を1単位とするブロック
で行う
Special Cource on Computer Architectures 2010
9
toolkit ver1.0の内容

ppe.c
PPE用ソースコード

spe.c
SPE用ソースコード

main_ppe.c
編集不可

spe.h

define.h

Makefile

getrndstr.c
ランダムな文字列を得たい場合に用いる

lcs.c
通常のLCSプログラム(結果のチェック用)

ans.txt
サンプル問題の答え

rep/
サンプル問題の文字列が書かれたファイルが入っている
編集不可
Special Cource on Computer Architectures 2010
10
toolkit ver1.0の使用法 (1/3)
• 2つのファイルを引数として与えると，それら
の中の文字列を読み込んで最長部分文字列を計
算する
• 初期状態で複数のSPEを使用する
• 制約：各文字列の文字数は128の倍数
– いろいろなサイズの例題ファイル付き
• getrndstr.c を使用すると，任意長のランダム文
字列を生成できる
$ gcc -O3 -o getrndstr getrndstr.c
$ ./getrndstr 128 13 > file9999
乱数種13で生成される128文字の文字列を格納したファイルfile9999を生成する
Special Cource on Computer Architectures 2010
11
toolkit ver1.0の使用法 (2/3)
 toolkit1.0.tgzを解凍後，makeでコンパイル
 サンプル問題の実行方法
 make run{数字} で実行できる (1から5まで)
問題番号
文字列A, Bの長さ
実行時間
最長共通部分列の長さ
Special Cource on Computer Architectures 2010
12
toolkit ver1.0の使用法 (3/3)
 答えは付属のlcs.cを用いることで確認できる
(make run* で実行する例題についてはans.txtに
解答が書かれています。他の文字列を用いる場合のみ
使用してください)
Special Cource on Computer Architectures 2010
13
制約の確認
• 文字数は128の倍数(かつchar型)
• 問題で与えられる2つの文字列をそれぞれ文字列A，
文字列Bと呼ぶことにする
•
•
•
•
コードはlibspe2準拠
PPEでも処理のプログラムを書いてよい
SPEは7つまで使用可能
PPEのメモリは自由に確保してよい
Special Cource on Computer Architectures 2010
14
課題に対するアプローチ
• 文字列をブロックに分割すると，処理単位をある程度
の大きさに分けることができる
• ブロックの計算を各SPEで並列に実行できると高速化が
期待できる!
• 並列計算が可能な部分はどこだろうか?
Special Cource on Computer Architectures 2010
15
並列処理の手法(1/3)
要素
Special Cource on Computer Architectures 2010
 データの依存関係
次の要素を計算するた
めには，左，上，左上
の3要素が定まっている
必要がある。
16
並列処理の手法(2/3)
要素
 水色の部分の計算が終了
していれば，並列に次の
要素を計算することが可
能
 これはブロックでも同様
に言える
Special Cource on Computer Architectures 2010
17
並列処理の手法(3/3)
 ブロックの場合は
block
block
block
1. 左上のブロックの
(一番右下の)要素
2. 上のブロックの要素行 (
最下行)
3. 左のブロックの要素列(最
右列)
の情報があれば計算できる
Special Cource on Computer Architectures 2010
18
ブロック計算の入出力
 入力
 左上のブロックの
(一番右下の)要素
 上のブロックの要素行 (最下
行)
 左のブロックの要素列(最右
列)
 出力
 計算後のスコアテーブルの (
一番右下の)要素
 最下行
 最右列
Special Cource on Computer Architectures 2010
19
各SPEの制御
SPE
SPE
SPE
SPE
 PPE上でキューを作り，
ジョブを管理
PPE
計算開始通知
Job Queue
Tail
PPEでの処理
• 計算終了したブロック番号を元に
，計算が可能になるブロック番号
計算終了通知
をキューに追加
• 基本的に右と下のブロックが計算
可能ブロックの候補になる
次に計算するブロックの格納
• 処理が空のSPEに対し，キューか
ら読み出したブロック番号を通知
し，計算させる
Head
• 右下のブロックの計算終了まで続
ける
Special Cource on Computer Architectures 2010
20
補足 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 Cource on Computer Architectures 2010
21
最速のプログラムを目指して
 実際に表を埋めているspe.cを改良する
 計算するブロックを制御しているppe.cを改良する
 並列に計算するためには?
 SPEのSIMD命令を用いる
 複数の要素に対して1命令で同一の演算が実行可能
 できるだけ1命令でたくさん計算する
 その他，ループアンローリングやbuiltin expect，ダブ
ルバッファリングなど
Special Cource on Computer Architectures 2010
22

Download Report