修 士 論 文 概 要 書

修 士 論 文 概 要 書

2008 年 2 月提出 学籍番号

3606U090–3

専門分野 情報・ネットワーク専攻 研究指導 設計解析システム研究

氏 名

傍士 雄介

指 導

教 員

柳澤 政生 ^印

研 究

題 目

オンチップルータにおけるバッファ構成最適化手法に関する研究

1 はじめに

近年，SoC設計におけるIPコア同士を結合するチップ内 接続網としてNetwork-on-a-Chip（NoC）が提案され，注 目を集めている．NoCアーキテクチャを用いることにより，

プロセス技術の微細化に伴い発生する，グローバル配線に よる配線遅延やクロストーク等の予測困難な物理事象の問 題の解決が期待される．しかし，一方でオンチップルータ

（以後ルータと呼ぶ）による面積，消費電力のオーバーヘッ ドが問題となる．そこで本論文では，ルータにおいて多く の面積，消費電力を占めるバッファ領域に着目し，チャネ ルごとにバッファ構成を最適化する手法を提案する．提案 手法は限られたバッファ資源の範囲内でネットワークのパ フォーマンスを最大化することを目的とし，最適化された バッファ構成を自動で得ることができる．

本論文は以下のように構成される．第2章ではオンチッ プルータについて述べる．第3章ではシミュレーションベー スのバッファ構成最適化手法を提案し，第4章では計算機 実験を行い提案手法の有効性を示す．

2 オンチップルータ

NoCは，並列計算機やSystem Area Network（SAN）で 用いられてきたパケット転送技術をチップ内のIPコア間の データ転送に応用し，チップ内でネットワークを構築する 技術であり，プロセッサコアやオーディオ/ビデオコーデッ クなどの専用IP，広範なインタフェースIP（USB，イー サネット，シリアルATA，DVB-H，HDMI等）やメモリ 等をルータを介して接続する．提案手法はこのルータに着 目する．

図1に仮想チャネルを持つワームホール・ルータを示す．

ルータはrouting logic，vc allocator，sw aloocator，そし てバッファごとのステート情報を保持するバッファから構 成される．ルータではヘッダ情報を持つフリット（ヘッダ フリット）が到着すると，以下の4サイクルをかけて処理 する．

1. routing computation：ヘッダフリットを解析して送信 方向を決定し，転送方向のバッファとの関連付け要求 をvc allocatorに送る．

2. virtual-channel allocation：パケットを受け取る側の ルータの入力チャネルから，関連付けがされていない バッファをラウンドロビンで選択し，パケットと関連 付ける．

3. crossbar allocation：関連付けが成立している全入力 チャネルのバッファから，1組にだけクロスバの使用 許可を与える．

4. crossbar transfer：関連付けられたバッファにフリット を転送する．

sw allocator(p) vc allocator(p,v) invc

state

invc state routing

lobic

・・

・・ ・・

outvc state

outvc state

・・・・・・

credit out

flit in

credit in

flit out Xbar(p,w)

input controller

・・

FIFO

FIFO

図 1: 仮想チャネル・ルータ.

ノード

オンチップルータ

図 2: MESHトポロジ.

NoCではこのようなルータをチップ上に複数個持ち，ネッ トワークを構成する．例えば図2のMESHトポロジでは，

チップ上にノードと同数のルータを持つ．このように多数 のルータを持つ構成は，並列処理性能に優れる反面，面積，

消費電力の増大が問題となる．対策としてルータ中で多く のコストを占めるバッファ領域の削減が行われるが，単純 に削減するだけではネットワークの性能が低下してしまう．

そこで，ルータの各チャネルごとにバッファ構成を最適化 する方法が有効となる．負荷が大きいチャネルには多くの バッファ資源を割当て，負荷が小さいチャネルには少量の バッファ資源を割当てることで，少量のバッファ資源で高 い性能のネットワークが構築できる．

3 バッファ構成最適化手法

提案手法はバッファ長と仮想チャネル数の最適化に対応 しており，限られたバッファ資源の範囲内で平均パケット 遅延時間が最小となるバッファ構成を得ることを目的とす る．既存研究では，提案手法が対象とするワームホールルー ティング，仮想チャネル数の最適化に対応した手法は確認 されていない．提案するバッファ構成最適化フローを図3 に示す．入力として以下の4種類のデータを与える．

• バッファ初期構成：全てのチャネルに1-flit分のバッ ファを与えた構成

• MESHサイズ：MESHトポロジの縦，横の長さ

トラフィック情報

シミュレーション バッファ初期構成

仮想チャネル追加 シミュレーション バッファ長追加

シミュレーション

L_L < L_V

Y N

使用バッファ総数+1

Y

N

最終バッファ構成 mesh サイズ

バッファ長追加 仮想チャネル追加

使用バッファ総数

< B

バッファ資源制約 B

図 3: バッファ構成最適化フロー.

• バッファ資源制約B：フリット単位で表した利用可能 なバッファ総量

• トラフィック情報：ネットワーク上のパケット通信の 宛先，発生頻度

手順を示す．まず，これらを入力としてシミュレーション を行い，ボトルネックとなるチャネルを検出する．ボトル ネック検出手段として以下の2種類のパケット転送のブロッ クの発生回数用いる．

1. バッファ長を増やすことで回避できるブロック 2. 仮想チャネルの追加で回避できるブロック

次にバッファ資源をバッファ長を増やすために割当てるか，

仮想チャネルを増やすために割当てるかを決定する．まず，

バッファ長を増やすことで回避できるブロックの発生回数 が最も多いバッファに対してバッファ長を1-flitだけ増や し，シミュレーションを行って平均パケット遅延時間LLを 求める．同様に，仮想チャネル追加で回避できるブロック の発生回数が最も多いチャネルに対してバッファ長1-flitの 仮想チャネルを挿入し，平均パケット遅延時間LV を求め る．そしてこれらを比較してLL < LV ならば，バッファ 長を追加し，LL > LV ならば仮想チャネルを追加する．な お，これらのシミュレーション時に得られるそれぞれのブ ロック回数は，次のループでバッファ長/仮想チャネル追加 シミュレーションを行う際に利用する．そして，使用バッ ファ総数を1-flit分だけ増やし，バッファ資源制約Bに達 しているかどうかを比較する．バッファ資源制約Bに達し ていれば最終バッファ構成として出力し，そうでなければ 再びバッファ長/仮想チャネル追加シミュレーションを行う．

このようにループを繰り返すことで，ボトルネックとな るチャネルには多くのバッファ資源が割当てられる．そし て得られた構成はチップ上のルータのチャネルごとに異な る構成を持つ．

4 計算機実験

本実験では，C++言語で記述したフリットレベルのイベ ントドリブン型NoCシミュレータを用いて，各バッファ構 成の平均パケット遅延時間の比較を行う．実験条件を以下 に示す．

• ネットワークトポロジ：6×6 MESH

• ルーティング法：XYルーティング

• パケット長：16-flits

• 入力パターン：Uniform Traffic，Hotspot Traffic

• シミュレーション期間：40,000サイクル（ただし，4,000 サイクルまでに生成されたパケットは測定対象外）

Uniform Trafficとは，ポアソン分布に従って均等な確率で 各ノードでパケットを生成し，そのパケットの宛先をラン ダムで指定した場合のトラフィックである．Hotspot Traffic とはUniform Traffic に加えて特定のノードを宛先とする パケットを増加させた場合のトラフィックである．

バッファ資源制約B = 1920（1920-flits分のバッファ）

として提案手法によって得られた構成と，各チャネルを均 一なバッファ構成とした場合の平均パケット遅延時間の比 較を表1に示す．表中の均一なバッファ構成の実験結果は，

同量のバッファ資源を用いたバッファ構成の中で最も小さ い平均パケット遅延時間を用いている．Uniform Trafficで は同量のバッファ資源を用いた均一な構成より劣るという 結果となった．これはUniform Traffic では均一な構成が バッファ構成の最適解となるためである．提案手法ではブ ロック回数の検出が生成する入力パターンに依存するため，

誤差が生じたと考えられる．Hotspot Trafficでは，10%の ホットスポットを設けた場合（Hotspot–1）も20%のホッ トスポットを設けた場合（Hotspot–2）も遅延時間の改善 が見られる．特にHotspot–2の場合は，提案手法で用いた バッファ資源の倍に相当するバッファを用いた均一な構成

（B=3840）よりも平均パケット遅延時間が小さくなる．こ れはネットワーク上のトラフィックの局所性が高まること により，提案手法によるバッファ構成最適化の効果がより 高まったためと考えられる．この場合，提案手法を用いる ことで半分のバッファ資源で均一な構成と同等のパフォー マンスが得られることになり，提案手法は有効であること を示せた．

表1: 平均パケット遅延時間の比較．

入力パターン 均一な構成 均一な構成 提案手法

（B=1920） （B=3840） （B=1920）

Uniform(0.008) 179.7 123.0 185.3

Hotspot–1(0.0063) 202.0 120.9 130.4

Hotspot–2(0.00475) 172.2 113.6 110.3

5 おわりに

本論文では，オンチップルータのバッファ構成最適化手 法を提案し，提案手法を用いることにより，少量のバッファ 資源で高い性能のネットワークが実現できることを示した．

今後の課題として，ブロックの重要度による重み付け手法 の確立が挙げられる．現在は対象とするブロックの発生回 数のみを検出しているが，ブロックの検出方法を改良する ことによって，より精度の高いボトルネックチャネルの検 出が可能となると考えられる．