既存手法

提案手法と同様に，オンチップルータの各チャネルのバッファ構成を最適化す る研究として文献[7]の手法がある．文献[7]で提案されているシステムは，m×n MESH トポロジとし，固定型ルーティングのルーティング法としてXY ルーティ

ングとodd-even ルーティングの2パターンを実装している．そして，パケット

転送法としてストアアンドフォワード，バーチャルカットスルーを対象とし，待 ち行列モデルを用いてオンチップルータの各チャネルのバッファ長を最適化する．

ストアアンドフォワードとバーチャルカットスルーは，いずれも各チャネルにパ ケット全体を格納できるサイズのバッファを持つパケット転送法である．文献[7]

では，これらのパケット転送法を用いた上で，全てのパケットは同じサイズであ ると仮定し，パケット転送の中断が発生しない環境を想定している．このように パケット転送を単純化することで，各パケットに対するルータの処理時間を一定 と考えることができ，事前にサイクル単位で計算することが可能となる．

表3.1にこの手法で用いられているパラメータを示す．これらのパラメータを 用いると目的関数は以下の式で表される．

Given:

利用可能なバッファ資源 B

アプリケーションの通信特性 ax,y，d^x_x,y^0,y0

オンチップルータにおけるパケット処理時間 S ルーティング・ファンクション R

Determine:

平均パケット遅延時間 Lが最小となる各チャネルのバッファサイズ l_x,y,dirを求 める．すなわち，

min(L)  s.t.X

∀x

X

∀y

X

∀dir

l_x,y,dir ≤B. (3.1)

この目的関数を満たすために，まず各チャネルに最小のバッファ長を与え（この 場合はパケット1つ分のバッファ長），バッファ資源制約の範囲内でボトルネック となるチャネルのバッファ長を増やしていく．このボトルネックとなるチャネルを 検出する指標として，チャネル Cx,y,dirにおいてバッファが一杯になっている確率

b_x,y,dirを用いる．そしてこのb_x,y,dirを解析するために用いられるのがM/M/1/K待 ち行列モデルである．初めの2つの“M”はcustomar の到着時間とserverのサー ビス時間が指数分布に従うことを意味し，“1”はserver の数が1つであること，

“K”は行列が有限であることを意味している．この場合，チャネルC_x,y,dirは長さ

l_x,y,dirの有限行列としてモデル化され，サービス率µ_x,y,dirで処理されるパケット

の到着率はλx,y,dirとしてモデル化されている．そして，パケットの到着率λx,y,dir

は，固定型ルーティングによって事前に各通信のパスが決定されており，また，パ ケット転送が途中で中断されないため，事前に計算することができる．λx,y,dirは，

パケットの発生確率ax,yと発生したパケットが(x⁰, y⁰)を通る確立d^x_x,y^0,y0 を用いて 以下の式で表される．なお，例としてdir=North の場合を示す．

λx,y,N =X

∀j,k

X

∀j⁰,k⁰

aj,k×d^j_j,k^0,k0×R(j, k, j⁰, k⁰, x, y, N) (3.2) このとき，R(j, k, j⁰, k⁰, x, y, N)はP E_j,kからP E_j⁰_,k⁰に向かうパケットがチャネル

C_x,y,Nを通る場合は1，そうでない場合は0とする．また，バッファが一杯になっ

ていることによりパケット転送がブロックされる確率b_x,y,N はM/M/1/Kモデル の公式により，以下の式で表される．

ρ_x,y,N = λ_x,y,N µx,y,N

(3.3) b_x,y,N = 1−ρ_x,y,N

1−ρ^l_x,y,N^x,y,N+1 ×ρ^l_x,y,N^x,y,N (3.4) よって，サービス率µ_x,y,dirを求めることで，b_x,y,dirを求めることができる．

ここからさらに平均待ち時間等を用いた近似によって以下の式が得られる．

µ_x,y,N =p^N_x,y,N ×µ^N_x,y,N +p^E_x,y,N ×µ^E_x,y,N +p^W_x,y,N ×

µ^W_x,y,N +p^S_x,y,N ×µ^S_x,y,N +p^LO_x,y,N ×µ^LO_x,y,N (3.5)

µ_x,y,N =λ_x,y,N + 1

1

1/S−λx,y,N + _µ ¹

x,y,N−λx,y,N

(3.6)

この非線形方程式をMatlab の関数 fsolve を用いて解くことにより，オンチップ ルータのチャネルごとにµ_x,y,dirを求めることができ，式(3.3)，(3.4)を用いてb_x,y,dir が分かる．b_x,y,dirが最も大きいチャネルがボトルネックである．そしてこれらの 解析モデルを用いて以下の手順でバッファ長の最適化が行われている．

1. 初期構成（各チャネルにパケット1個分のサイズのバッファ）の状態でチャ ネルごとにb_x,y,dirを求める．

2. ボトルネックとなるチャネルにパケット一個分のバッファ長を追加．

3. これまでに割当てたバッファの合計がバッファ資源制約Bの範囲内であるか どうかを確認し，範囲内であれば再びボトルネックとなるチャネルの検出，

Bに達しているなら終了する．

計算複雑度はCをチャネルの数とし，F(C)を非線形計画問題のソルバーの複雑 度とした場合，O(B×F(C))で得られる．

文献[7]では以上のようにしてバッファ長の最適化を図る．長所として

• 数学的な解析モデルを使用しているため非常に高速である という点が挙げられるが，短所として

• ワームホールルーティングに対応できない

• パケット長を一定にする必要がある

• 仮想チャネルの追加に対応できない

等が挙げられる．これらの欠点はパケット転送を単純化する必要性からきている が，いずれもNoC の性能を減少させる要因となる．ストアアンドフォワードと バーチャルカットスルーは，パケット全体を格納できるサイズのバッファが各チャ ネルに必要となる．また，パケット長を一定にしなければならない．よってパケッ ト長の設定が重要となる．まず，パケット長を短くするという方法が考えられる が，マルチメディア処理のように大量のデータをやり取りする必要がある場合，同 一の宛先のパケットを分けて送信することになり，性能低下の原因となる．一方 で，パケット長を長くした場合においてもバッファサイズが大きくなってしまう という問題がある．提案手法はシミュレーションベースとしているため，解の探 索時間は長くかかるが，これらの問題点を克服するものである．

表 3.1: Parameter Notation[7]

Parameter Description

SP The size of a packet

B The total buffering space budget L The average packet latancy

S Packet service time in a router without contention dir Direction,i.e. North,South,East,West,Local

R Routeing function

Rx,y The router located at tile (x, y)

Cx,y,dir Thedirdirection input channel in routerRx,y

P Ex,y The PE located at tile (x, y) lx,y,dir The buffer size of channelCx,y,dir

ax,y Packet injection rate ofP Ex,y

d^x_x,y^0,y0 The probability of a packet generated byP Ex,y to be delivered toP Ex⁰,y⁰

λx,y,dir The packet arrival rate at channelCx,y,dir

p^dir_x,y,dir⁰ The probability of a packet at channelC_x,y,dir to be delivered towarddir⁰ direction µx,y,dir The service rate for packet at channelCx,y,dir

ρx,y,dir The unilization factor of channelCx,y,dir

bx,y,dir The probability of the buffer atCx,y,dir being full