計算クラスタ上で文字列の類似度を計算するための並列アルゴリズム

愛知工業大学研究報告 第

40

号

B

平成

1

7

年 ノート 263

計算クラスタ上で文字列の類似度を計算するための

並列アノレゴリズム

A

P

a

r

a

l

l

e

l

A

l

g

o

r

i

t

h

m

t

o

C

a

l

c

u

l

a

t

e

t

h

e

S

i

m

i

l

a

r

i

t

y

o

f

Two S

t

r

i

n

g

s

o

n

a

C

l

u

s

t

色

ro

f

C

o

m

p

u

t

e

r

s

鈴 木 晋 *

Susumu Suzuki*

水 野 勝 教 *

石 井 直 宏 牢

N

aohiro I

s

h

i

i

*

Katsunori Mizuno

ヰ

Abstract We

p

r

e

s

e

n

t

a

p

a

r

a

l

l

e

l

a

l

g

o

r

i

t

h

m

t

o

c

a

l

c

u

l

a

t

e

t

h

e

s

i

m

i

l

a

r

i

t

y

o

f

も

wos

七

r

I

n

g

son c

o

m

p

u

t

e

r

s

c

o

n

n

e

c

も

edby a

l

o

c

a

l

a

r

e

a

n

e

t

w

o

r

k

，

c

a

l

l

e

d

a

c

l

u

s

t

e

r

o

f

c

o

m

p

u

t

e

r

s

.

L

e

t

t

h

e

l

e

n

g

t

h

o

f

e

a

c

h

s

七

r

i

n

gbe

n

and t

h

e

number o

f

t

h

e

c

o

m

p

u

t

e

r

s

p.

We

show t

h

a

t

t

h

e

p

a

r

a

l

l

e

l

a

l

g

o

r

i

t

h

m

c

a

n

s

o

l

v

e

t

h

e

p

r

o

b

l

e

m

i

n

t

i

m

e

O(

手

)

w

h

e

n

p

:

:

:

;

ぽ

(2

S)

，

azMerefo

，

間

t

h

a

t

t

h

e

a

l

g

o

r

i

t

h

…

nd

由

oi

比

ti

担

n

吋七抗出

ime

児

eO(

岬ゾ

.

J

B

昂

h

耐同

'

n

均

.

!

尚

!

3

訂

)

(e:ご::

O(

仰

1

叩

Oη2

勾

)

リ

)

句

e

s

叩

pe

伺

c

i

叫

a

l

l

除

yw

袖

hen

word

七

h

llrO'立叩.刀

ough

七

hene

目七

wo

町

r

止

k

)

/

(

p

h

戸

y

戸

y

s

i

c

叫

a

1

討七

imef

o

r

七

hecompute

l'

t

o

e

x

e

c

u

t

e

one i

n

s

t

n

同

i

o

non CPU)

(e:::

1

0

0

)

.

S

i

n

c

e

t

h

e

t

i

m

e

c

o

m

p

l

e

x

i

t

y

o

f

t

h

e

s

e

q

u

e

n

t

i

a

l

a

l

g

o

r

i

t

h

m

i

s

O

(

η

2

)

，

t

h

e

p

a

r

a

l

l

e

l

a

l

g

o

r

i

t

h

m

i

s

f

a

s

t

e

r

七

h

i

l

nt

h

e

s

e

q

u

e

n

t

i

a

l

乱

1

9

o

r

i

t

h

m

.

1

はじめに

遺伝子工学の進展にともない大量の遺伝情報が蓄積 されるようになり，それらを計算機を使って高速に処理 することが急務となっている.

DNA

の塩基配列の類似 度の計算やタンパク質のアミノ酸配列の類似度の計算 はそのようなものの

1

つである.これらの計算は

2

つ の文字列の類似度の計算と見なすことができる

[

1

，

2

]

.

ところで，計算機工学の世界では，

1

9

9

0

年代から多数 のワークステーションやパソコンを

LAN

で接続したシ ステム上で並列処理を行う研究が盛んに行われるよう になり，現在では，

MPI (

M

e

s

s

a

g

e

P

a

s

s

i

n

g

I

n

t

e

r

f

a

c

e

)

や

SCore

等の並列処理のための基盤ソフトが無償で提 供されている.このように構成される並列計算システ ムは計算クラスタと呼ばれる

[

3

，

4

]

.

計算クラスタを 使って問題を高速に解くためには，問題を並列的に処 理する並列アノレゴリズムが必要である.特に計算クラ スタではB =(1語の転送時間

)

/

(

1

命令あたりの

CPU

時間)がかなり大きい(約

1

0

0

)

ため，通信時聞が爆発 しないように適切な粒度で問題を並列処理することが できる並列アノレゴリズムが重要である. 本稿では，文字列類似度問題を計算クラスタを使っ て高速に解くことを目的として並列アノレゴリズムを提 * 愛 知 工 業 大 学 経 営 情 報 科 学 部 情 報 科 学 科 コ ン ビュータシステム専攻(豊田市) 案し，その速さを評価する.文字列の長さを

n

，

計算 機の台数をp とする.提案する並列アノレゴリズムが，

(

1

)

p

三

v

?

i

i

(e:::妥)のとき，時間量

O

(

手)で問題 を解けること，故に特に，

(

2

)

p

=

v

志のとき，時間 量

O(JEn2)(20(10n3))

で問題を解けることを示 す.

1

台の計算機を使って問題を解く逐次アルゴリズ ムの時間量は

O

(

η

2

)

であるので，

(

1

)

より，計算機が そ子台以下のときは，並列アルゴリズムは逐次アルゴリ ズムより高速で、あり，その速さは使用できる計算機の 台数に比例して速くなる また，

(

2

)

よ り ， 妥 台 程 度 の計算機が使用できるときは，並列アルゴリズムは逐 次アルゴリズムより大幅に高速である.

2

文字列類似度問題

2つの文字列，例えば， "eα

s

t

"

と"ω

e

s

t

"

をギャッ プを挿入しながら並べたときに，同じ位置にある 2つ の文字からなる文字対で両文字が一致するような文 字対(一致文字対と呼ぶ)を最大何個作れるかを考え る.この例の文字列の場合，

-easE

_we-s のようにギャップ "'C (に?と記す)を挿入して並べると，全文字対('-'，ヲぜ) ， ('e'

，

'e')

，

('α' ，'-')~ ('s'

，

γ)

，

(

'

t

'

，

'

t

'

)

のうち，

3

つの文 字対 ('e'

，

'e')

，

(

ヲs'

，

's')

，

(

'

t

'

，

'

t

'

)

が一致文字対になる. また，どのようにギャップを挿入しでも，一致文字対 を

3

つより多く作ることはできない.故にJ

"

e

α

s

t

"

と ηω

e

s

t

"

に対しては，一致文字対の最大数は

3

である.

264 愛知工業大学研究報告，第40号B，平成17年，Vo1.40・B，Mar， 2005 w e S t (=S2)

。 。 。 。

Voo時 _{V01 → V02 →}

'

0

3→ V04 E ₁₀

、

。

↓

_{0もI ! 0}

、

₀₁₀

、

。

↓

₀ 100110V12ー0+V13O 14 G 10

、

o!o

、

。

畢

。

、

o!O

、

。

↓

o 0 " 0 .. 0.. 0 V20 → V21 → V_22→

h

_→ ν24 S

↓

o

、

。

↓

。

、

o !Oもl

↓

o

。

↓

、

0 V，~ _30→

Q

.

v" _'31→

.

Q

.

v"_'32→'3

.

Q

.

v" _3→

.

Q

₃₄ 10

、

o↓o

、

o!O泊↓o~歯1 10 0.. 0.. 0.. 0 V ー 今 V 40 ~ '41 ' '42-， _'43 ~ '44 (=S1) 図1. コスト付・きグラフG 文字列類似度問題は，上の例のように，

2

つ文字列が 与えられて，ギャッブを挿入してそれらの文字列を並 べたときの，ある目標関数

_f

(上の例では一致文字対の 数)の最大値(上の例では

3

)

，および，その値を与え る文字列の並べ方(上の例では高三:)を求める問題 である.最大値を文字列の類似度，文字列の並べ方を アライメント，特に，最大値を与える文字列の並べ方を 最適アライメントという.目標関数

f

は，上の例では

f

= 1

x

(一致文字対の個数)であったが，一般には

f

= C[ x (一致文字対の個数) + C H X (不一致文字対の個数) 十 CKX (ギャップ文字対の個数) と表される.ここで

，

c['CH

，

C Kは応用に適したある重 みであり，不一致文字対は ('αに'グ)のように異なる文 字からなる対，ギャップ文字対は

(

'

a

'

，

'-')のように文 字とギャップからなる対である. 本稿では，説明の簡単のため，文字列の類似度のみを 求める(最適アライメントを求めるように拡張するこ とは容易である).また，

2

つの文字列の長さは等しい とする (1節で述べたようにη と記す).

3

逐次アルゴリズムの紹介

文字列類似度問題はグラフ上の経路探索問題とし て解くことができる [1，2]. 2節の問題例(文字列が 81

=

"e

α

st"と82

="ω

est"，目標関数

f

の中の係 数がC[

=

1

，

cH

=

0ぅCK二 0)を使って説明する.問 題例に対して図

1

のコスト付きグラフ

G

を考える. Gでは， (jS1j + 1)(jS2j + 1) = (4 + 1)(4 + 1)個の 節 点 的j

，

i

，

j = 0

，

.

.

.

，

4

，

が格子状に並んでおり，横 方向，縦方向3 斜め方向に規則正しく枝が出ている. 文字列

S

の

i

番目の文字を S(i)と記す. Gの各枝 にはコストがついており，横方向および縦方向の枝 のコストは CK

=

0

，斜め方向の枝 (Vij

，

Vi+l

，

H

l

)

の コストは ，Sl(i

+

1

)

= S2

(

j

+

1

)

のとき C[= ，1 Sl(i

+

1

)

=

j

:

.

S2(j

+

1

)

のとき CH=

0

である

.G

上 の路のコストを路に現れる枝のコストの和と定義する. 例えば，図

1

の太い枝からなる路VOOVOIV12V22V33V44 のコストは0+1+0+1+1=3である.このよう にGおよび路のコストを定めると，

G

の左上の節点 VOOから右下の節点り44へ至るすべての路のコストの 中の最大値が文字列81= 九αst"とS2

="ω

est"の 類似度になる.最大値を与える路を最適路と呼ぶ.路 VOOVOl V12V22V33V44は最適路になっており，この路のコ スト 3が文字列の類似度になる (2節で述べた類似度 3 lこ一致する).

G

の最適路のコスト(文字列の類似度)の計算は図

2

の動的計画法により行うことができる.ここで，叫jは

斜め方向の枝(Vi-l

，

j-l

，

Vij)のコスト

，

D ijは節点VOO

から節点的jへの最適路のコストであり ，Dnnが求め る最適路のコスト(文字列の類似度)である.動的計画 法の時間量はO(η2)である. Doo =0 DOj = D O，j-l

+

CK

，

1

s

:

j

三

η DiO= D←1.0十 CK

，

l

:

S

i

:

S

n D ij

=

皿ax{D

←

1

，

j十 cK

，

Di-l

，

j-l

+

ω

ij

，

D i

，

j-l

+

CK}

，

1

:

S

i

，

j

:

S

n

.

図2.動的計画法

4

並列ア

j

レ

ニ

ゴ

1)

_.

_ズ

_ム

計算機クラスタは

1

台のマスタ計算機と

p

台のス レーブ計算機(スレーブ

#1

，.・.，スレーブ、

#p

と記す)を パス型LANで接続して構成されるa ただし，マスタの 仕事は少ないため，マスタとスレーブ

#1

は物理的に同 一の計算機とする.送信，受信とも，通信はすべて同期 型とする .Dnn (文字列の類似度)を計算する並列ア ノレゴリズムを次に示す. [マスタ計算機]

s

t

e

p

l

:

すべてのスレーブに文字列データを送信する.

s

t

e

p

2

:

スレーブ

#p

から Dnn(文字列の類似度)を受 信したら，それを表示して終了する.口 [スレーブ計算機

]

1

*

スレーブ

#k

とする.

*

/

s

t

e

p

l

:

マスタから文字列データを受信する.

s

t

e

p

2

:

k

=

1

ならば

s

t

e

p

3

へ，

2

壬

k:

Sp-l

ならば

s

t

e

p

4

へ

，

k=pならば

s

t

e

p

5

へ.

計算クラスタ上で文字列の類似度を計算するための並列アノレゴリズム

s

t

e

p

3

・

1

*

スレーブ

#1

における処理

*

j

f

o

r

(

i

=

1;

i

三

p

;p+

+

)

{

Bliを計算する.

C

1iをスレ}ブ

#2

に送信する.

}

終了する.

s

t

e

p

4

:

j

*

スレーブ

#k

(

2

壬k

孟

p-

1

)

における処 理

*

j

f

o

r

(

i

= 1;

i

三p

;p+

+

)

{

スレ}ブ子学

(

k-1

)

から Ck-1，iを受信する. Bkiを計算する. Ckiをスレ}ブ

#(k

+

1

)

に送信する.

}

終了する.

s

t

叩

5

:

j

*

スレーブ

'#p

における処理

*

j

f

o

r

(

i

=

1;

i

三p

;p+

+){

スレーブ

#(p

-1)から Cp-1，iを受信する. Bpiを計算する.

}

Dnnをマスターに送信する. 終了する，口 ここで，Bki

，

Ckiは次式で表されるDifjfの集合である. 、 、 ‘ Z E E ， J 1 i ， f t_、

， 、

! ? J

、

_lfJllLfil 円 円 、

nd

寸 t -9 噌 E ム

K

E

t

﹃ E E E E E E E E E B ﹁ ， ， B E E t -1 -1 1 i -t i 一 十 一

P+

一

p

n

一

η

一

r f l i l e e m i l l i -rtJ

、

_ttr13 ミ 11

、

n

n

m

m

<一く一 ・ 0b ， u g d <一<一 、_， ノ l 噌_i

、

_1/ 噌_i 叩 J

一

一

h

k

t

E

(

(

riJIL--JIll--J ー ー 1 1 一 1 占 同

=

+

一

P

十

一

p

l

M

n

一

n

一

TF ﹄ ﹁ 2 3 3 1 1 s t a z r t B ' B E l l t

C

ki =

{

D

印

I

i

'

=

r

ヂ

l

k

-1

，

同

o

{

，

r

千

l

(iード

l:::;k

三p

-1

，

1:::;i

三p

.

並列処理の流れを p

=

3

，

n

二

8

の例を使って説明 する.図3に示すように，

η

(

十 1)

x

η

(

十1)

=

9

x

9 の行列として表された全ての Difjfを

pxp=3x3

個のブロックに分け

，

B l1ド ー ・

，

B33と記す(式

(

1

)

の

Bki) .また ，BkiとBk+1，iの境界付近にある Di'j'を C11ド 園 川C23と記す(式(2)のCki).初め，スレーブ

#1

は， (1.

1

)

B l1 (に含まれる Difjl)を図

2

と類似の 動的計画法を使って計算し，計算結果

C

11(に含まれる Di'j')をスレープ

#2

に送信する.その後， (1.

2

)

B12 を計算し

，

C

12をスレーブ

#2

に送信し， (1.3)

B

13を 計算し

，C

13をスレーブ

#2

に送信する.スレーブ

#2

は，

(

2

.

1

)

C

11を受信すると ，

B

21を計算し ，

C

21をス レ}ブ

#3

に送信する.その後， (2.2)

C

12を受信する とB22を計算し ，C22をスレーブ

#3

に送信し，その 265 図3. 並列処理の流れ 表1.各時刻(段階)におけるスレーブの処理内容 スレーブ

#1

スレーブ

#2

スレーブ

#3

後，

(

2

.

3

)

0

13を受信すると B23を計算し ，C23をス レーブ

#3

に送信する.スレーブ

#3

は，

(

3

.

1

)

C

21を受 信すると

B

31を計算し，その後 ，

(

3

.

2

)

C

22を受信する とB32を計算し，その後 ，(3.3)C23を受信すると B33 を計算する.解DS8が得られたので，D88をマスタに 送信する.表1は各時刻(段階)におけるスレーブの 処理内容を示す.第

1

段階ではスレーブ

#1

のみが処 理

(

B

n の計算と

C

u の送信)を行うが，例えば，第

3

段階では全てのスレーブが処理を行う.最後に，第

5

段階でスレーブ

#3

がB33を計算してp 並列処理が終 了する.

5

計算時簡の評価

各

C

kiの転送時間は

A

'

+

B

'

(

f

平

1

+

1

)

と近似す ることができる.ここで，A'は通信起動時間，B'は1 語当たりの転送時間である

[

3

]

.

また

，

C

を

1

命令当た りの CPU時間とすると，各Bkiの計算時間はおよそ

Cf

ヂ p

である

t

列処理は(均一

1

)

個の段階よりな り，各段階において，各スレーブのBkiの計算は並行 して行われ，一方，全ての

C

kiの転送は逐次的に行わ

2

6

6

愛知工業大学研究報告，第

40

号

B

，平成

1

7

年，

Vo

l.羽田

B

，

Mar

，

2

0

0

5

れる.故に，並列処理にかかるすべての時間 Tt

(

P

)

は 次式で与えられる:

山)ど(均一

1

)

(

C

伴

r

+p

ベ←(

2 叫 刈

2

釘

C

(

Z

千+め叫

(伊例3

勾

)

ここで

，

A

:

:

:

:

:

A

'

γ

/C

，

B

:

:

:

:

:

B

'

γ

/

C

.

時間

T

t(

ρ

)

を

CPU

の ステップ数に換算したもの，すなわち，時間量を

T

(

p

)

と記す.

(

3

)

より，

時)

= 0

(~叫2+ 拘)ω

以下，時間量

T

(

p

)

を圭嗣面する. 式

(

4

)

の括弧内を

g

(

p

)

と記す:

T

(

P

)

=

O

(

g

(

p

)

)

ヲ

(

5

)

仰)=ご+勾

2+B

叩

(

6

)

このとき，

内 )

=十

2

勾

+

Bn.

(

7

)

l

(

p

)

=

0

の正の解をp。と記すと

-

5

+

地

+Bn

=

0

，

(

8

)

g

'

(

P

)

の符号より，

g

(

p

)

は

O<p:::;p

。のとき単調に減 少し

，

p=p

。のとき最小になる

.

p

:

:

:

;

p

。とする.

(

8

)

より

手

=

Po(2Apo

+

Bn)

>

Po(Apo

+

Bn).

(

9

)

Y O また，p

:

:

:

;

P

o

より 同 2 ~2

ニ 三 ニ

，

Ap

2 +Bnp 三 Ap~

+

Bnpo

・

(

1

0

)

p

P

o

(

6

)

，

(

9

)

う

(

1

0

)

より，

g(p) 豆半 +Ap~

+

Bnpo

<

竺

+

Z

<

2

2

1

(

日)

p

p P

o

P

(

5

)

，

(

1

1

)

より

，

p

壬P

o

のとき，

T

(

p

)

:

:

:

:

:

O

(

g

(

p

)

)

=

0

(~)仰)

P

o

より小さい

P

o

の近似値を求める

一

手

+2Bn

=

0

の解をpα と記す: 同 2 一二r十

2Bn

=

0

，

p

α

(

1

3

)

すなわち もし

，

nが すなわち

P

a

=

品

ヤバ品三室

2A2 n主 B3 を満たすならば，

(

7

)

，

(

1

3

)

，

(

1

4

)

より 目 2 ~2

(

1

4

)

(

1

5

)

91(pa)=-27+2APα

+Bn

壬

-

:

2

+

2Bn

=

0

~a rα であるので，

g

'

(

p

)

の単調増加性より

P

α 壬

P

o

・

A

，

B

は各々

1

0

4_，

₁

₀

2_{程度であるので，}

₍

₁

₅

₎

_はη主

₁

₀

₀

₀

(

>

>

2

0

0

)

であれば成立する.故に9 並列計算の対象と なるような大きさのnに対しては，

pa=J2524

を

p

。より小さい

p

。の近似値として使うことができる，

(12) より ， p~ 妥(= Pa)

のとき，並列アルゴリ ズムは逐次アノレゴリズム(時間量

O

(

η

2

)

)

より高速で あり，その速さは計算機の数pに比例して速くなる. また，

T(p

α

)=T(

長)

=O(hBn~)

:

:

:

:

:

0

(

v

'

B

n!)

竺

O

(

1

0

n

!

)

であるので，

P24

のとき，並列アルゴリズムは逐次 アノレゴリズムより大幅に高速である.

謝辞

この研究は愛知工業大学教育・研究特別助成の 援助を受けて行われました.

参考文献

[

1

]

中村春木，中井謙太:バイオテクノロジーのため のコンヒoュータ入門，コロナ社，東京，

1

9

9

5

.

[

2

]

Dan G

u

s

f

i

e

l

d

:

A

l

g

o

r

i

七

hmson S

t

r

i

n

g

s

，官

e

e

s

ヲ 組

d

S

e

q

u

e

n

c

e

s

-Computer S

c

i

e

n

c

e

and

Computa-t

i

o

n

a

l

B

i

o

l

o

g

y

，

-

Cambridge U

n

i

v

e

r

s

i

t

y

P

r

e

s

s

ヲ

New York

，

1

9

9

7

.

[

3

]

Barry W

i

l

k

i

n

s

o

n

and M

i

c

h

a

e

l

A

l

l

e

n

:

P

a

r

a

l

-1

e

l

Prongramming -T

e

c

h

n

i

q

u

e

s

and A

p

p

l

i

c

a

-t

i

o

n

s

U

s

i

n

g

N

e

七

workedWorks

七

a

t

i

o

n

s

叩

dP

a

r

-a

l

l

e

l

Computers

，

-

P

r

e

n

t

i

c

e

-

H

a

l

l

，

1

9

9

9

.

[

4

]

石)11裕，佐藤三久他:

Linux

で並列処理をしよう? 共立出版，東京，

2

0

0

2

.

( 受 理 平 成

1

7

年

3

月

1

7

日)