HOST
Pattern 0 Pattern 1
5.3 入力層分割による SOM 並列化
20000 40000 60000 80000 100000 120000 140000
0 20 40 60 80 100
Times of weight update
Competitive unit number
図 5.3: 競合層ユニットの重み更新回数
によるモデルと同様の問題が発生する．また，ウィナーの競合層上での位置がPE間の境 界に近く，近傍関数や学習率関数を距離の関数としている場合には，PE間通信が余分に 発生するという問題がある．Myklebustによる並列化手法についても，競合層分割による ノード 並列を基本にしているため，PE間の負荷が不均一という問題は解決されていない．
また，競合層のサイズが大きい大規模SOMでは，PE間の通信が大幅に増加するために十 分な高速化を行うことができないという問題もある．
以上の問題点を踏まえ，原理的に負荷の不均一が発生せず，大きな競合層を用いる大規 模SOMを高速に学習させる入力層分割法を次節で提案し，その評価を行う．
Input layer
Competitive layer
Input Neuron Input Neuron
Input Neuron Input Neuron
Weights from competi-tive neurons to a input neuron C
A B
C D
Weights from competi-tive neurons to a input neuron D
Weights from competi-tive neurons to a input neuron A
Weights from competi-tive neurons to a input neuron B
PE 2 PE 3
PE 0 PE 1
図 5.4: 入力層分割法の概要
による並列化を提案し，その性能を評価する．
図5.4に，入力層分割の概念を示す．各PEは入力層のユニットを担当し，競合層の各ユ ニットへの重みを持つ．したがって，競合層のどのユニットがウィナー，あるいは近傍と なって重み更新を行っても，すべてのPEが同等の処理をするため負荷の不均一は発生し ない．
対象とするSOMは入力層，競合層の2層とし，それぞれM 2M，N 2N個のユニッ トからなり，ある時刻 t における入力ユニット i と出力ユニット j間の重みを Wij
(i =
1;111;M 2
; j = 1;111;N 2
)とする．このSOMをM 2M個のPEに分割し，各PEはN2 次元の重みベクトルを持つ．学習パターンT =ft1;111;tM
2gが入力層ユニットに入力され た場合を考える．各PEは学習パターンで対応する要素を用い，入力ベクトル要素tiと重 みベクトルWijとの間のユークリッド 距離djiを（5.1）式に基づき計算する．
Algorithm 5.1 入力層分割法
1 Initialize W j
i (0).
2 Distributet
i
toeach PE i.
3 do on eachPE i,
4 for j=0 toN 2
,
5 d
j
i
=jjW j
i
(t)0T
i jj.
6 broadcastd j
i
and calclated j
= P
i d
j
i
,then sendittoPE i.
7 decidewinnerc=argmin
j d
j
and neighb ours N
c
(t)on each PE.
8 W
j
i
(t+1)=W j
i
(t)+h
cj (t)(W
j
i (t)0t
i
)j2N
c (t)
9 while d c
<LIMIT,orlearn formax iterations.
図 5.5: 入力層分割学習法のアルゴリズム
d j
i
= q
(t
i 0W
j
i )
2
; j =1;111;N 2
(5:1)
各PEiがdji
; j =1;111;N
2を計算した後で，iについてdjiを（5.2）式により集計し，結果 を全PEにブロード キャストする．
d j
= M
2
X
i=1 d
j
i
(5:2)
その結果，競合層ユニットjと学習パターン間の距離djをすべてのPEが持つことになる．
各PEは独立にdjが最も小さいものをウィナーcとして選び，（2.32）式，あるいは（2.33） 式で示される近傍関数hcjを用いてcとその近傍Nc(t)の重みを更新する．したがって，各
PEは同一個数の重み要素を更新することになり，負荷の不均一は原理的に発生しないこと になる．図5.5に，入力層分割法によるSOMの並列学習アルゴリズムを示す．
5.3.2
入力層分割法の学習時間
2.3.2節と同様に，入力層分割を用いた並列SOMの学習時間について考察する．入力層，
競合層はそれぞれM 2M，N 2Nの2次元格子を構成しており，NPE = M2個のPEを 持つ並列計算機に実装するとする．近傍関数は（2.32）式，近傍範囲Nc(t)は（2.34）式と した．
学習パターンは各要素に分解され，各要素がPEに分配される．各PEでは学習パター ン要素と競合層ユニットへの重みとの2乗誤差を計算する．これに必要な時間Td0は次式で
表される．
T 0
d
=N 2
(t
add +t
mul ti
) (5:3)
次に競合層中のユニットで最も学習パターンに近いユニットを決定するが，これには各
PEが持つ誤差要素を集計する必要がある．この集計には簡単化のため，各PEが一つのホ ストに誤差要素を送り，ホストで加算処理後各PEにブロード キャストするというモデル を用いる．すべてのPEがホストにデータを送るのに必要な時間がM2tcomm，ホストが送 られたデータを加算する時間が(M2 01)tadd，加算した結果の平方根を計算するための時 間がN2tsq，計算結果を全PEに送信するのに必要な時間がM2tcommであるので，誤差集 計に必要な時間Tc0 は次式のようになる．
T 0
c
=(M 2
01)t
add +N
2
t
sq +2M
2
t
comm
(5:4)
各PEはホストから受信した集計後の誤差をもとにウィナーと近傍を決定するが，これ は逐次処理を行ったときと同じTs;Tnである．近傍Nc(t)内の競合層ユニット数はNc2
(t)な ので，これの重み変更に必要な時間Tuw0 は(5.5)式で表される．
T 0
uw
=(2t
add +t
mul ti )N
2
c
(t) (5:5)
以上より，学習パターン一つを入力層分割SOMで学習するのに必要な時間Ttotal0somは（5.3） 式，（5.4）式，（5.5）式とTn;Tsとの総和であり，（5.6）式で表される．
T 0som
total
= T 0
d +T
0
c +T
n +T
s +T
0
uw
= n
M 2
+N 2
+2N 2
c
(t)+1 o
t
add +
n
N 2
+N 2
c
(t)+4 o
t
multi
+N 2
t
sq +T
s +2M
2
t
comm
(5.6)
入力層分割法を用いて，Np個の学習パターンをNepoch回学習するのに必要な時間は，（5.6） 式にNpを乗じ，それをNepochまで加算した（5.7）式で表されることになる．
T 0som
= N
epoch
X
t=1 N
p T
0som
total
(5:7)
5.3.3
競合層分割法の学習時間
本節では従来の競合層分割法による学習時間について議論する．入力層分割法と同じ条 件を用い，1PEに競合層の1ユニットを割り当てると仮定する． 学習パターンは1パター
ン毎にすべてのPEにブロードキャストされ，並列に競合層ユニットの誤差を計算する．こ れに必要な時間Td00は（5.8）式で表される．
T 00
d
=M 2
(t
add +t
mul ti )+t
sq
(5:8)
各PEは単一の競合層ユニットを割り当てられているので，競合層全体でのウィナーを 決定するためには一旦計算した誤差をホストに送る必要がある．ホストはウィナーを決定 後，各PEにウィナーをブロード キャストする．これに必要な時間Tc00は（5.9）式となる．
T 00
c
=2N 2
t
comm +t
s
(5:9)
ウィナー決定後，近傍半径および学習率の決定には，他のモデルと同様にTnの時間が必 要である．重みの更新は近傍範囲内のユニットを割り当てられたPEのみが行い，他のPE はアイド ル状態で処理の終了を待つとすると，重み更新に必要な時間Tuw00 は（5.10）式で 表される．
T 00
uw
=M 2
(2t
add +t
multi
) (5:10)
以上より，競合層を分割したときの並列モデルにより学習パターン1つを処理するのに 必要な時間Ttotal00somは（5.11）式となる．
T 00som
total
= T 00
d +T
00
c +T
n +t
s T
00
uw
= (3M 2
+2)t
add
+(2M 2
+4)t
mul ti
+t
sq +t
s +2N
2
t
comm
(5.11)
以上よりNp個の学習パターンをNepoch回学習するのに必要な時間T00somは（5.12）式で 表される．
T 00som
=N
epoch N
p T
00som
total
(5:12)
5.3.4
入力層分割法と競合層分割法の比較
（2.38）式による逐次処理SOMと，（5.6）式による入力層分割，および（5.11）式による競 合層分割による並列SOMの処理時間を比較する．M =N =n，Nepoch =1000,Np =100，
t
s
=n2t
addとし，理想並列計算機上での各学習法による学習時間を図5.6に示す．並列学 習における学習時間の計算では，ユニット数と同数のPEを使用すると仮定している．ま
1 1e+10 1e+20
10 100 1000 10000
Learning time (seconds)
Number of units on axis of each layer Input layer parallel model Competitive layer parallel model Serial
図 5.6: 逐次処理および理想並列計算機上での入力層分割と競合層分割学習法の学習時間
た，各学習時間の計算における各処理時間は，nCUBE/2での実測により以下のように設 定した．なお，通信時間tcommは1対1通信のときの値である．
t
add
= 1sec:
t
multi
= 1sec:
t
sq
= 10sec:
t
comm
= 100sec:
図5.6に示すように，逐次処理と比較して並列処理を用いた学習は大幅な高速化が達成で きる．これは，逐次処理では通信時間は各層の軸上のユニット数nに対してO (n4)で処理 時間が増加するのに対し，並列化時にはO(n2)であり，ネットワークのサイズが大きくな るにつれ並列化による効果が大きくなる．モデルによるシミュレーションでは，1002100 のSOMでは1万個のPEを用いた並列処理により約100倍の，100021000のSOMでは
約10000倍の高速化が達成できる．入力層分割法と競合層分割法を比較した場合，競合層
分割法の方がわずかに高速である．これは競合層分割法での2乗誤差の計算が並列でtsqで 行うことができるのに対し，入力層分割法はN2tsqとなることが一因と考えられる．
1 10 100 1000
1 10 100
Learning time (seconds)
Number of units on axis of input layer(M) Theoretical time
Learning time by ncube2
図 5.7: 並列SOM学習法のモデルと実装結果の比較
図5.7に，入力層分割法をnCUBE/2に実装したときの学習時間とモデルによる計算時間を 示す．このとき，入力層分割法での通信時間は配列加算通信を用いることにより，2M2tcomm から t0comm
(N
PE
;Mlen) となる．t0commにおいて，NPE = M2;Ml en = N2である．また，
SOMの規模は競合層を10210とし，入力層のサイズを222;424;828;16216とし，
N
p
=N
epoch
=100とした．図5.7より，モデルによる計算時間は実装による実験結果と誤 差10%以内で一致している．この結果から，SOMの学習時間検討の手段として（5.7）式，
（5.12）式を用いることは妥当と考えられる．
さて，図5.8にPE数とメッセージ長を考慮した通信時間を用いた場合の並列学習時間を 示す．このときの通信時間は，3.3.2節で示した（3.29）式を用いた．図5.8より，理想並列 計算機上での比較では差が見られなかったが，メッセージ長やPE数による通信遅延を考 慮すると競合層分割法に比べて入力層分割法の学習時間が長くなっている．競合層分割法 では通信で送られるメッセージ長は一定であるが，入力層分割法では競合層のユニット数 に比例してメッセージ長が増加し，ネットワークの規模が大きくなるにしたがって一回の 通信時間が増大する．このことから，各層で同一規模のユニットを持つSOMでは，競合 層分割法の方がやや高速となる．
次に，入力層と競合層のユニット数が異なる場合について検討する．図 5.9に入力層を
1 1e+10 1e+20
10 100 1000 10000
Learning time (seconds)
Number of units on axis of each layer Input layer parallel model Competitive layer parallel model Serial
図 5.8: 通信遅延を考慮した並列SOMの学習時間の比較
1002100として競合層のユニット数を変化させたときの学習時間を，図5.10に競合層を
1002100に固定して入力層のユニット数を変化させたときの学習時間を示す．このとき，
N
p
=100;N
epoch
=1000である．
入力層を1002100に固定した場合，図5.9より競合層ユニット数が少ない間は入力層分 割法の方が高速である．しかし，競合層のユニット数が増加するにしたがって入力層分割 法の学習時間は長くなり，競合層分割法の方が高速になる．入力層分割法では，（5.6）式よ り学習時間が競合層サイズN2により主として支配されているため，競合層のサイズが大き くなると学習時間が長くなる．これに対し，（5.11）式で示される競合層分割法の学習時間 ではNを含む項はなく，通信時間がt0comm
(N 2
;1:0)でNを影響を受けるのみである．
図5.10では競合層を1002100に固定し，入力層のサイズを変化させたときの学習時間を 示す．入力層分割法では（5.6）式から分かるようにtadd の係数と通信時間t0comm
(M 2
;N 2
)
にMが含まれているため，入力層サイズが大きくなると学習時間が長くなっていく．しか し，競合層分割法では（5.11）式より学習時間はMに支配されるため，入力層分割法より も学習時間の増加が大きくなり，入力層のサイズがおよそ競合層の4倍以上では入力層分 割法よりも学習時間が長くなる．
以上より，提案した入力層分割法は画像符号化などで多く用いられている大規模な入力