優先度付きオンチップルータVIX

全文

(1)情報処理学会論文誌. コンピューティングシステム. Vol.6 No.1 87–98 (Jan. 2013). 優先度付きオンチップルータ VIX 水頭一壽1,a). 向後卓磨1. 山崎大輝1. 松谷宏紀1. 山. 信行1. 受付日 2012年7月4日, 採録日 2012年10月6日. 概要：近年，メニーコア CMP の通信基盤である NoC において，CMP のシステムレベルの最適化や QoS 制御のためにパケットの転送遅延を優先度に基づいて制御する要求が高まりつつある．従来の優先度付き. NoC では優先度導入によるルータ面積の大幅な増加と，高優先度パケットが低優先度パケットにブロックされる優先度逆転によるネットワーク性能の低下が問題とされている．本論文では，VC 割当てとクロスバ割当てのパイプラインステージを統合する優先度付きオンチップルータ VIX を提案し，これらの問題を解決する．提案手法を Verilog HDL によって実装し，評価を行う．ネットワーク性能の評価では，5 種類の case study ごとに転送遅延に関する評価を行い，VIX が優先度逆転問題の発生率を抑えることでネットワーク性能を向上させていることを示す．また，提案手法を TSMC 65 nm のプロセスでレイアウトし，面積，クリティカルパス，消費電力の評価を行い，VIX が VC の数と優先度のビット数に対してスケーラビリティがあることを示す．キーワード：ネットワークオンチップ，リアルタイム. Prioritized On-Chip Router VIX Kazutoshi Suito1,a) Takuma Kogo1 Daiki Yamazaki1 Hiroki Matsutani1 Nobuyuki Yamasaki1 Received: July 4, 2012, Accepted: October 6, 2012. Abstract: Toward QoS control and system-level optimization on NoC-based many-core CMPs, prioritized packet transfer that controls the communication latency based on the priority becomes more important. Such priority control increases hardware amount of routers. In addition, priority inversion problem in which higher-priority packets are blocked by lower-priority packets degrades the network performance. To overcome these problems, in this paper, we propose the VIX router architecture, in which VC allocation and crossbar allocation stages are integrated to a single stage. The VIX router architecture is designed with Verilog HDL and implemented with TSMC 65 nm process technology. Five case studies evaluate the VIX router in terms of communication latency and demonstrate that the VIX router can mitigate the priority inversion problems and improve the network performance. The implementation results show that the VIX router is scalable even when the number of VCs and priority bits are increased. Keywords: Network-on-Chip, real-time. 1. はじめに. コアを搭載するメニーコア CMP [11], [12], [21] が実現されており，今後も CMP のコア数は増加し続けると多くの. 半導体技術により数十億ものトランジスタが集積可能. 研究者および開発者が予想している．メニーコア CMP で. となることから，1 つのチップに複数のコアを搭載する. はコアどうしの通信のためにスケーラビリティ，転送遅. Chip-Multiprocessors（CMPs）がプロセッサ性能を向上. 延，バンド幅，ハードウェア量，消費電力などを考慮して，. させるアーキテクチャとして有望である．すでに多数の. Networks-on-Chip（NoC）[4] が用いられる．メニーコア CMP における NoC の性能はシステム全体に大きな影響. 1 a). 慶應義塾大学 Keio University, Yokohama, Kanagawa 240–0063, Japan [email protected]. c 2013 Information Processing Society of Japan . を与える．特に NoC のパケットの転送遅延はアプリケーションの実行時間に大きく影響する．パケットの転送遅延. 87.

(2) 情報処理学会論文誌. コンピューティングシステム. Vol.6 No.1 87–98 (Jan. 2013). 通信遅延を保証する QoS 制御. は式 (1) で与えられる．. Delay = H × Dr + Dc + Ds. (1). H は平均ホップ数，Dr はルータ遅延，Dc は衝突遅延，. 一定の通信遅延を保証するために QoS を制御する．リアルタイム性が必要なシステムやアプリケーションはもちろん，それ以外の用途においても通信遅延の保証は重要で. Ds はパケットを構成するフリット数分の注入遅延であ. ある．たとえば，ある通信パターンに対してパケットの転. る．コア数の増加にともない第 1 項の転送遅延の影響が. 送遅延が何十倍以上のオーダで増大するようではシステム. 大きくなるため，Dr （ルータのパイプラインステージ. を構成するうえで支障となりかねない．コア数の増加にと. 数）を削減するルータアーキテクチャが数々提案されてき. もない通信時間の予測が難しくなるため，今後は QoS 制. た [15], [17], [18], [20]．また H を削減する効率の良いトポ. 御の重要性が増していくと考えられる [10], [16], [19]．. ロジ [1], [6], [14] も提案されており．これらの先行研究により第 1 項の遅延の影響は最小限に抑えられつつある．第. 2.2 優先度付き Network-on-Chip における問題点. 3 項の Ds はパケット長（フリット数）で決まり固定であ. 2.1 節で述べた優先度付き NoC の先行研究では，先読み. る．さらなる性能向上のためには第 2 項の Dc を小さくす. ルーティング [9] と投機的クロスバ割当て [20] を組み合わ. る必要がある．. せた従来の 2 ステージパイプラインルータ [5] の VC アロ. システムレベルで考えた場合，すべてのパケットの Dc を削減する必要はなく転送遅延がクリティカルなパケッ. ケータおよびクロスバアロケータに単純に優先度比較論理を追加している．. トを優先することが有効であることが明らかにされてい. 2 ステージパイプラインルータはインテルのメニーコア. る [2], [7], [8], [10], [16]．クリティカルなパケットの転送遅. CMP [12] でベースとして採用されているだけでなく，多. 延を制御するには，パケットに優先度を付加して，ネット. くの NoC の研究 [15], [17], [18] においてもベースにされて. ワークを構成する各ルータでクロスバや Virtual Channels. いる事実上の標準ルータであるため，本論文では 2 ステー. （VCs）[5] などの資源を優先度に基づいて割り当てればよ. ジパイプラインルータを従来ルータと呼ぶことにする．. い．しかし従来のオンチップルータに単純に優先度比較論. 本節では，従来手法においてハードウェア量が大幅に増. 理を追加した場合，ルータのハードウェア量が大幅に増大. 加することと，優先度逆転問題が生じることを指摘する．. すると同時に，高優先度パケットが低優先度パケットにブ. 2.2.1 ハードウェア量. ロックされて高優先度パケットの転送遅延が増大してし. 優先度付き NoC では VC アロケータとクロスバアロケー. まう優先度逆転問題の発生頻度が高いという問題がある．. タを構成する各 Matrix Arbiter [20] に優先度比較論理が追. そこで本論文は，優先度制御を考慮したオンチップルータ. 加される．Matrix Arbiter と VC アロケータへの優先度の. VIX を提案し，これらの問題を解決する．. 追加がハードウェア量におよぼす影響を明らかにするた. 本論文の構成は次のとおりである．2 章で優先度付き. め，予備評価を行った．優先度を追加した Matrix Arbiter. NoC のサーベイとその考察を述べ，3 章で提案する VIX. と VC アロケータを Verilog HDL で実装し，Synopsys 社. ルータの設計および実装について述べる．4 章では VIX. の Design Compiler を用いて TSMC 社 65 nm のプロセス. ルータの評価を行う．5 章で本論文をまとめる．. テクノロジをターゲットに合成した．Matrix Arbiter に. 2. 背景 2.1 優先度付き Network-on-Chip NoC に優先度を導入する目的は以下の 3 つに分類できる．ネットワークの特性に基づいた資源割当て制御. は 3 GHz，VC アロケータには 1 GHz のタイミング制約を与え，合成後の面積を見積もった．図 1 (a) に Matrix. Arbiter，図 1 (b) に VC アロケータの合成結果を示す．優先度付き Matrix Arbiter の面積は入力数およびサポートする優先度のビット数に対してそれぞれおよそ線形で. ネットワークレベルでの転送遅延削減を目的とし，Dc. ある（図 1 (a)）．また，従来の VC アロケータは，物理. の影響が大きいパケット長の短いパケットに高い優先度を. チャネル数を p，VC 数を v とすると，それぞれ pv 個の. 与え，パケット長の長いパケットには低い優先度を与える. v 入力ローカルアービタと pv 入力グローバルアービタ. 方式が提案されている [2]．. で構成される（図 1 (c) 参照）．優先度アービタの面積を. アプリケーションの特性に基づいた資源割当て制御. O(Input × P riority) と仮定すると，VC アロケータの面積. アプリケーションの実行時間削減を目的とし，通信遅延. は O(p2 v 2 × P riority) と考えることができる．そのため，. がクリティカルなアプリケーションのパケットに高い優先. VC 数が多いときは優先度のビット数がルータ面積に与え. 度を与える方式 [7] や，アプリケーションの実行時間に大. る影響が大きくなる．. きな影響を与えるパケットに高い優先度を与える方式 [8] が提案されている．. 文献 [8] では優先度 8 ビットと VC 数 6 を仮定しているが，このとき VC アロケータの面積は約 2.0 mm2 である（図 1 (b)）．これは VC で使用するバッファ（約 2 KB）の. c 2013 Information Processing Society of Japan . 88.

(3) 情報処理学会論文誌. コンピューティングシステム. Vol.6 No.1 87–98 (Jan. 2013). (a) 優先度アービタのセルエリア. (b) VC アロケータのセルエリア. (c) VC アロケータの構成. 図 1 予備評価. Fig. 1 Exploratory evaluation.. 面積 0.5 mm2 を超える非常に大きなサイズである．バッ. 優先度の最大値より大きいときに優先度逆転問題が発生し. ファ，クロスバアロケータおよびクロスバの面積はそれぞ. ていると定義する．. 2. れ O(pv)，O(max{v, p} × p × P riority) および O(p ) であるので，VC 数の増加による VC アロケータの面積の増加率はルータ内の他のユニットよりも大きい．そのため，優先度数ビットかつ VC 数 4 以上のとき，VC アロケータがルータ面積の多くを占めることになる．. 3. VIX ルータアーキテクチャ 3.1 VIX オンチップルータの設計 VC アロケータの多大なハードウェア量と VC の浪費による高優先度パケットの転送遅延増大を同時に解決するた. これらの結果より，VC アロケータおよびクロスバアロ. めに，VC アロケータの構成を変更することが望ましい．. ケータに単純に優先度比較論理を追加する従来手法では，. 優先度付き NoC では優先度を考慮しない NoC と比較す. VC の数や優先度のビット数が増えるとハードウェア量が. ると，低優先度パケットのクロスバが割当てが成功する可. 大幅に増加することが分かる．また，優先度ごとに専用の. 能性は低いため，低優先度パケットに VC を割り当てた. VC を持つアーキテクチャ [3] も提案されているが，優先度. としてもスループットは向上せず，反対に割り当てるこ. の数だけ VC が必要になるため，スケーラビリティに問題. とによって VC を浪費する可能性がある．この洞察に基. がある．. づき，本論文では VC 割当てとクロスバ割当てのパイプラ. 2.2.2 優先度逆転問題. インステージを統合する VIX（Virtual channel allocation. 優先度を考慮しない従来ルータは，多数の VC を用いて. integrated with crossbar allocation）ルータを提案する．. フリットレベルのインタリーブを行うことでクロスバの. VIX ルータでは，投機的にクロスバ割当てを行うことで. マッチング効率を上げ，高スループットと低転送遅延を実. VC 割当てを同時実行するのではなく，同じパイプライン. 現している．従来ルータに単純に優先度比較論理を追加し. ステージでクロスバ割当て，VC 割当ての順で逐次的に行. た場合，インタリーブよりも多く発生するフリットレベル. う．これにより，VC がすべて占有されたことに起因する. のプリエンプションによって VC を効率良く用いることが. クロスバのブロック発生を抑制して，クロスバのマッチン. できず，スループットが低下する．. グ効率の低下を防ぐとともに，高優先度パケットの追い越. 従来ルータでは VC 割当てとクロスバ割当てが独立で行. しを支援し，優先度逆転問題の発生を抑制する．. われており，高優先度パケットによってブロックされ長い. VIX ルータは各出力チャネルに対して 1 サイクルで最大. 時間クロスバが割り当てられることのない低優先度パケッ. 1 つの VC しか割り当てないため，VC 割当ての論理はク. トに対しても VC は割り当てられる．その結果，低優先度. ロスバ割当てのグラントを利用することができる．従来の. パケットによって VC が占有され，ネットワークの性能が. 面積の大きな VC アロケータが不要となるため，VC 割当. 低下する．. ての論理を大幅に削減することができる．また VIX ルー. また，低優先度パケットによって多くの VC が占有され. タではクロスバが割り当てられる高優先度のパケットのみ. た状態で VC が枯渇した場合，後続の高優先度パケットに. が VC を獲得できるので VC の浪費問題も同時に解決でき. VC を割り当てることができず，低優先度パケットによっ. る．先読みルーティング [9] を併用することが可能なため，. て高優先度パケットの転送が阻害される優先度逆転問題が. VIX ルータのパイプラインは従来ルータと同じ 2 ステージ. 発生する．. にすることができる．. 本論文では，ルータ内の各出力チャネルに対して優先度逆転問題を定義する．クロスバが割り当てられるパケットの優先度が当該出力チャネルの VC を占有するパケットの. c 2013 Information Processing Society of Japan . 3.2 VIX オンチップルータの実装図 2 に VIX ルータのアーキテクチャを示す．VIX ルー. 89.

(4) 情報処理学会論文誌. コンピューティングシステム. Vol.6 No.1 87–98 (Jan. 2013). W inReq: a request that wins arbitration OC(W inReq): an output channel of the request M C(W inReq): a message class of the OC(W inReq) Operation at each Free VC Pool 01: if VC is not allocated to W inReq then 02:. if W inReq has not get VC yet then forward VC id from Free VC Pool of M C(W inReq). 03:. update Free VC Pool of M C(W inReq). 04: 05:. else. 06: 07: 図 2. VIX ルータのアーキテクチャ. Fig. 2 Architecture of VIX router.. no operation end if. 08: else 09:. no operation. 10: end if. タでは VC アロケータが除外され，代わりにフリーな VC. Operation at each Request Controller. を管理する VC プールを各出力チャネルに 1 つずつ追加. 01: if VC is already allocated to W inReq then. している．VC プールは利用可能な VC を管理し，そのう. 02:. ち 1 つの VC 識別子を出力する．VC の管理は従来ルータ. 03: else. でもすでに実装されているため，実質的な追加論理は各出力チャネルごとに利用可能な VC を 1 つ選択する論理，つ. 04: 05: 06:. Request is sent to ... if Free VC Pool of M C(W inReq) is not empty then Request is sent to ... else. まり p 個の v : 1 固定アービタのみである．VC プールは. 07:. 従来どおりクレジットと VC 割当ての結果によって更新さ. 08:. れる．VIX では各 VC プールが VC 割当ての結果を得るた. 09: end if. めに，各リクエストの VC 割当て済みを意味する情報 vc. reserved をローカルアービタおよびグローバルアービタ. Request is masked end if 図 3. VC プールとリクエストコントローラの動作. Fig. 3 Behavior of the request controller and the VC pool.. のグラントによって選択することで伝搬させている．VC プールからは利用可能な VC が存在しないことを意味する情報 empty および利用可能な VC の識別子を意味する情. 4. 評価. 報 allocatable vc id を出力させている．これら 2 つの情. Verilog HDL を用いてオンチップルータを実装し，評価. 報は各入力チャネルに追加したリクエストコントローラが. を行う．実装したルータは提案ルータの VIX および 2.2 節. VC 割当ての際に利用する．リクエストコントローラは各. で説明を行った従来の 2 ステージパイプラインルータの. リクエストのうち不要なリクエストをフィルタリングす. SPC である．評価では 5 種類の case study におけるネッ. る．リクエストコントローラは VC 獲得済みのリクエスト. トワーク性能を示す．また，各ルータの配置配線後の面積，. はそのまま通過させ，VC 未獲得のリクエストは利用可能. クリティカルパス，消費エネルギーを明らかにし，提案手. な VC が存在すれば通過させ，存在しなければ無効にする．. 法の優位性を明らかにする．. VIX ルータは各出力チャネルにある VC プールから割当て可能な VC 識別子を 1 つだけ出力しているが，メッセー. 4.1 ネットワーク性能の評価. ジクラス 1 つごとに割当て可能な VC を管理し，それぞれ. 4.1.1 評価環境. から識別子を 1 つ出力するように変更する．またリクエス. ネットワークシミュレーションには Cadence 社の NC-. トのタプル（information）にメッセージクラス識別子の情. Verilog を用いた．評価のためのパラメータを表 1 に示. 報 mc id を追加し，リクエストコントローラのリクエス. す．ネットワークシミュレーションにおける 5 種類の case. ト無効化の論理は当該出力チャネルかつ当該メッセージク. study ではデフォルトパラメータを基に表 1 右側のパラ. ラスの割当て可能な VC の存在をチェックするように変更. メータに変更して評価を行った．各評価パラメータは実. する．VC の獲得は当該出力チャネルかつ当該メッセージ. CMP における NoC のパラメータ（表 2）と優先度付き. クラスの VC 識別子を受け取るように変更する．VC プー. NoC の先行研究 [2], [7], [8], [10], [16] で用いたパラメー. ルの更新はどのメッセージクラスに対してポップするか決. タを基に定めた．トポロジはレイアウトが容易な 2 次元. められるように vc resereved と同様にリクエストのタプル. メッシュとした．ネットワークサイズは 64 ノードを標準. の 1 つとして mc id を伝搬させ，VC プールが受け取るこ. とし，文献 [12] のようにクラスタを NoC で接続する構成. とができるように変更する．これらを図 3 にまとめた．. については 16 クラスタを想定した．評価に用いるルータの構成は，VC 数を 2∼4 ch，フリット幅を 64∼128 bits と. c 2013 Information Processing Society of Japan . 90.

(5) 情報処理学会論文誌. コンピューティングシステム. Vol.6 No.1 87–98 (Jan. 2013). 表 1. 評価のためのパラメータ. Table 1 Evaluation parameters. Characteristic. Baseline Parameters. Five Case Studies. Topology. 8-ary 2-mesh. Case study 5:. 4-ary 2-mesh. Traffic. Uniform. Case study 1:. Uniform, Transpose [5], Local *1. Link delay. 1 cycle. Packet size. 1 or 5 flits (50-50 chance). Case study 4:. 1 or 9 flits (50-50 chance). Priority *2. 4 bits = {batch *3 , packet size [2]}. Case study 2:. 6 bits = {batch, packet size, hop count *4 }. Switching. Wormhole + VC (credit base). Routing. Dimension-order. Allocation. Priority + least recently served *5. # of Ports. 5/router. # of VCs. 4/port. Case study 3:. 2/port. VC depth. 4 flits/VC Case study 4:. 64 bits. Flit width. 128 bits. Others. Req/Ack constraint *6 , 2 MCs *7. した．パケットのペイロードが 64 Bytes であることを想. ついてトラフィックパターンごとの評価を示す．図 4 (a)，. 定しパケット長を定めた．また，制御用のショートパケッ. 図 5 (a)，図 6 (a) より，各トラフィックに共通してネット. トとデータ用のロングパケットを想定した．多くの場合は. ワークの飽和直前の負荷において，高優先度が与えられて. ショートパケットとロングパケットが対になって使用され. いるショートパケットの平均転送遅延が削減されているこ. ると考えられるため，両パケットの発生確率を同率とした．. とが分かる．また低優先度が与えられているロングパケッ. 優先度は優先度付き NoC の先行研究 [2], [7], [8], [10], [16]. トの平均転送遅延は増加していない．これは，VIX によっ. で用いられた 1∼8 bits を想定した．. て優先度逆転問題が解消され，ショートパケットの転送遅. 4.1.2 Case study 1：トラフィックパターン. 延が改善されるため，結果的にこれらのショートパケット. ショートパケットおよびロングパケットの転送遅延に. によってブロックされていたロングパケットの転送遅延も改善されたためと考えられる．結果，全パケットの平均転. *1. *2. *3. *4. *5. *6. *7. 空間的局所性を考慮した Local トラフィックを定義する．Local トラフィックはディスティネーションが 75%の確率で隣接ノードの中からランダムに，25%の確率で全ノードからランダムに決まる．エイジングを行わない固定優先度付加方式は低優先度パケットがスタベーションを起こしネットワークの挙動が不安定になる．バッチ方式は先行研究 [7], [8], [10], [16] で採用されているため，バッチ方式をデフォルトの優先度付加方式に組み込むこととした．評価では 2 種類の優先度付加方式を適用するが，VIX ルータは優先度付加方式には非依存であり，様々な優先度付加方式と組み合わせることができる．バッチ方式は優先度をエイジングする方法でありバッチインターバルと呼ぶ一定サイクルごとにパケットの優先度を 1 上げる方法である．バッチ方式は低優先度パケットのスタベーションの発生を防ぐだけでなく，パケットの公平性も向上させる．詳細は先行研究 [7], [8], [10], [16] を参照されたい．評価では，バッチインターバルを 64 サイクル，バッチ数を 8 としている． Dc の影響が大きいホップ数の多いパケットに高い優先度を付加する方式 [13] である．本論文の評価では優先度を hop counts/4 として算出した．各アロケータを構成するアービタは優先度比較論理を導入した Matrix Arbiter [20] である．そのため，最高優先度リクエストがグラントを得ることになる．同一優先度リクエストが存在するときは least recently served のポリシでグラントが与えられる．リクエストパケット（パケット長はランダムに決定される）は送信ノードで生成され，リクエストパケットが宛先ノードに到着すると送信ノード宛てにアクノレッジパケットが生成される．またアクノレッジパケットのパケット長はリクエストパケットがショートならばロング，ロングならばショートと対応付けられている．リクエスト・アクノレッジパケットは共用 VC の VC0 と VC1 を優先的に使い，共用 VC がない場合はリクエストパケットなら VC2 を，アクノレッジパケットなら VC3 を使用するものとした．. c 2013 Information Processing Society of Japan . 送遅延が削減されている．高優先度パケットの転送遅延の削減は VIX のクロスバ割当てに連動した VC 割当てにより，VC 利用効率が向上したことで，優先度逆転問題の発生の頻度が低下したためである．VC 利用効率が向上したことでスループットも向上している．図 4 (b)，図 5 (b)，図 6 (b) より，SPC は優先度逆転問題の頻発により，低い負荷であっても最大転送遅延が大幅に増大し，場合によっては高優先度パケットの最大転送遅延が低優先度パケットの最大転送遅延を上回ることが観測されているのが分かる．VIX は優先度逆転問題の頻発を軽減しているため，負荷の増大に従って最大転送遅延が増加するという傾向となった．また VIX では高優先度パケットの最大転送遅延が低優先度パケットの最大転送遅延を上回ることがなかった．さらに，VIX で低優先度パケットの転送は高優先度パケットの転送完了に依存しているため，. VIX の高優先度パケットの転送遅延削減により低優先度パケットの転送遅延も連鎖的に削減されている．図 4 (c)，図 5 (c)，図 6 (c) より，VIX は低い負荷からジッタ（転送遅延の標準偏差）の増大を抑制していることが分かる．これは，SPC では負荷が低いときにおいても. VC の浪費および枯渇が発生し，高優先度パケットの転送遅延の急激な増加が発生しているといえる．最悪転送遅延についての考察と同様に高優先度パケットの転送遅延の急. 91.

(6) 情報処理学会論文誌. コンピューティングシステム. 表 2. Vol.6 No.1 87–98 (Jan. 2013). 実 CMP における NoC のパラメータ. Table 2 NoC parameters of real CMP. Network Topology. # of VCs. 8 × 10 Mesh. 2. TILE64 [21]. 8 × 8 Mesh. 1. 32 bits. Dimension-order. SCC [12]. 4 × 6 Mesh. 8. 128 bits. Dimension-order. CMP TeraFlops [11]. (a) 平均転送遅延. Flit width 32 bits. (b) 最大転送遅延. Routing Source routing. (c) ジッタ. 図 4 Case study 1：Uniform トラフィック. Fig. 4 Case study 1: Uniform traffic.. (a) 平均転送遅延. (b) 最大転送遅延. (c) ジッタ. 図 5 Case study 1：Transpose トラフィック. Fig. 5 Case study 1: Transpose traffic.. (a) 平均転送遅延. (b) 最大転送遅延. (c) ジッタ. 図 6 Case study 1：Local トラフィック. Fig. 6 Case study 1: Local traffic.. 激な増加を抑制したことにより連鎖的に低優先度パケット. 平均転送遅延が削減されていることが分かる．低優先度パ. の急激な増加も抑制したといえる．. ケットの平均転送遅延も，ほとんどの場合において削減さ. 4.1.3 Case study 2：優先度付加方式. れている．しかし，図 8 (b) において，優先度 0 のホップ. Case study 2 では，case study 1 より優先度が 2 ビット. 数 1∼3（1–3 H）の負荷が低い場合，SPC と比べて VIX の. 多いため，優先度付きトラフィック特有のフリットレベル. 平均転送遅延が増加している．これは，低優先度パケット. のプリエンプションが発生する頻度が高くなる．つまり. が優先度逆転によって高優先度パケットよりも早く転送さ. ルータの優先度に基づいたフロー制御がトラフィックに与. れていたため，VIX によって優先度逆転問題が解消された. える影響が大きくなる．. ことにより，結果的に低優先度パケットの平均転送遅延が. 図 7 より，case study 1 と同様に高優先度パケットの. c 2013 Information Processing Society of Japan . 増加したと考えられる．また，スループットの向上につい. 92.

(7) 情報処理学会論文誌. コンピューティングシステム. (a) 全パケット. Vol.6 No.1 87–98 (Jan. 2013). (b) ロングパケット. (c) ショートパケット. 図 7 Case study 2：平均転送遅延. Fig. 7 Case study 2: Average transfer delay.. (a) 全パケット. (b) ロングパケット. (c) ショートパケット. 図 8 Case study 2：最大転送遅延. Fig. 8 Case study 2: Maximum transfer delay.. (a) 全パケット. (b) ロングパケット. (c) ショートパケット. 図 9 Case study 2：ジッタ. Fig. 9 Case study 2: Jitter.. ても case study 1 と同様である．VIX では，負荷が無負荷. い，つまり Dc が大きくなっていることからいえる．これ. 状態から飽和状態になる手前の間，負荷に対する平均転送. に加えて VIX は優先度逆転問題の頻発を回避する代わりに. 遅延の増分がわずかであり，ホップ数を基に与えた優先度. 低優先度パケットの転送機会を奪っているため，VIX では. が転送遅延を正確に制御している．. 最低優先度パケットの転送遅延が増大する懸念がある．し. Case study 1 と同様に，図 8 より最大転送遅延を削減. かし，高優先度パケットの転送遅延削減に付随して低優先. し，図 9 より，高優先度パケットのジッタを削減してい. 度パケットの転送遅延も削減される．これらを差し引いた. ることが分かる．一方で，VIX および SPC の両者ともに. 結果，図 7 のとおり下位 2 レベルの優先度のパケットの平. 優先度 0 のホップ数 1∼3（1–3 H）のロングパケットの平. 均転送遅延は VIX は SPC より大きくなっている（VIX の. 均転送遅延が優先度 1 のホップ数 4∼7（4–7 H）のロング. 方が最大転送遅延が小さいことに注意されたい）．サポー. パケットの平均転送遅延を超えている．このようなホップ. トする優先度のビット数が増加するに従って，提案方式に. 数と平均転送遅延の逆転は高優先度であるショートパケッ. おける低優先度パケットの転送遅延が増加するトレードオ. トでは発生していない．このホップ数と平均転送遅延の逆. フが顕著に現れると考えられる．. 転は低優先度パケットが高優先度パケットにブロックされ. 4.1.4 Case study 3，4，5：. 続けるために生じると考えらる．これは各手法とも最低優先度パケットのジッタが他の優先度のパケットよりも大き. c 2013 Information Processing Society of Japan . VC 数，パケット長，ネットワークサイズ VC 数，パケット長およびネットワークサイズのパラメー. 93.

(8) 情報処理学会論文誌. コンピューティングシステム. (a) Case study 3. Vol.6 No.1 87–98 (Jan. 2013). (b) Case study 4. (c) Case study 5. 図 10 Case study 3，4，5：平均転送遅延. Fig. 10 Case study 3, 4, 5: Average transfer delay.. (a) Case study 3. (b) Case study 4. (c) Case study 5. 図 11 Case study 3，4，5：最大転送遅延. Fig. 11 Case study 3, 4, 5: Maximum transfer delay.. (a) Case study 3. (b) Case study 4. (c) Case study 5. 図 12 Case study 3，4，5：ジッタ. Fig. 12 Case study 3, 4, 5: Jitter.. タを変更しても，VIX は図 10 より平均転送遅延，図 11. Case study 5 ではネットワークサイズが小さくなって. より最大転送遅延，図 12 よりジッタを削減することが分. いるため，パケットどうしの衝突が少なく，VC 枯渇が発. かる．. 生しにくい構成である．図 10 (c) と図 4 (a) を比較すると. Case study 3 では VC 数を case study 1 の 0.5 倍とし. VIX ではスループットが 1.72 倍になったのに対し，SPC. ている．図 10 (a) と図 4 (a) を比較すると VC が 2 倍にな. では 1.83 倍となった．VC 枯渇が発生しにくいとき，VIX. ると VIX ではスループットが 1.93 倍になったのに対し，. は SPC とスループットの差が小さくなるといえる．. SPC では 1.85 倍となっている．VIX は VC 数が多くなる. 4.1.5 優先度逆転問題発生率. ほどスループットの点で有利であるといえる．. 図 13 は，Uniform トラフィックにおける各ルータの各. Case study 4 ではパケット長を長くしているため，ネッ. 出力チャネルにおける優先度逆転問題の発生率を示してい. トワークをまたがってロングパケットが VC を占有するこ. る．Case study 1（case1）において VIX は優先度逆転問. とになり，case study 3 と同様に VC 枯渇が発生しやすい. 題発生率を負荷が 0.10 のとき 21%削減し，負荷が 0.22 の. 構成である．図 10 (b) と図 4 (a) を比較すると VIX では. とき 54%削減した．優先度逆転問題発生率に差が出る負荷. スループットは低下しないのに対し，SPC では約 0.9 倍と. 0.10 以上のとき，図 4 (a)，図 4 (b)，図 4 (c) から分かるよ. なった．VIX は VC 枯渇が発生しやすいとき，スループッ. うに平均転送遅延，ジッタおよび最大転送遅延においても. トの点で有利であるといえる．. 差が出ている．. c 2013 Information Processing Society of Japan . 94.

(9) 情報処理学会論文誌. コンピューティングシステム. Vol.6 No.1 87–98 (Jan. 2013). 図 14 ルータの面積. Fig. 14 Area of router.. 図 13 優先度逆転問題発生率. Fig. 13 Incidence ratio of priority inversion problem.. 同様に，case study 2（case2）においては，負荷が 0.18. エネルギーとする．フリットのビット幅は 64 bits，ホップ数は評価に使用した 8 × 8 のメッシュを想定し，5.33 とし. のとき 22%，負荷が 0.26 のとき 56%削減している．また，. た．Esw は Synopsys 社の Power Compiler を用いて配置. 優先度逆転問題発生率に差が出る負荷 0.12 以上のとき，全. 配線後のネットリストから求めた．Elink は次式で計算で. パケットの平均転送遅延およびジッタにおいても差が出て. きる．. いる（図 7 (a)，図 9 (a)）．以上より，VIX は優先度逆転問題の発生率を抑えることでネットワーク性能を向上させているといえる．. Elink = d × V 2 × Cwire ÷ 2. (3). d は 1 ホップあたりの平均距離，V は動作電圧，Cwire は単位長あたりの配線容量とする．1 ホップあたりの平均距. 4.2 配置配線による評価. 離は 8 × 8 のメッシュで 8 mm 角のチップと仮定し，1 mm. 4.2.1 評価環境. とした．動作電圧は使用したプロセスの動作電圧である. 実装した VIX および SPC のルータを Synopsys 社の De-. 1.0 V とし，配線容量は配置配線後の寄生容量抽出を用い. sign Compiler を用いて TSMC 社 65 nm のプロセステクノ. て求め，92.18 fF/mm とした．. ロジをターゲットに合成した．論理合成時には VIX およ. 4.2.2 面積. び SPC ともに 1 GHz のタイミング制約を与えた．その後，. 配置配線後のルータの面積を図 14 に示す．VC が 2 本. Cadence 社の SoC Encounter を用いて配置配線し，配置配. の場合，VIX の面積は SPC と比較して，優先度 2 ビット. 線後のネットリストの面積，およびクリティカルパスを求. 時に 54.1%，優先度 8 ビット時に 38.7%削減している．ま. める．配置配線時には，論理合成結果のクリティカルパス. た，VC が 4 本の場合，VIX の面積は SPC と比較して，優. に 25%のマージンを見込んだ値をタイミング制約とし，配. 先度 2 ビット時に 35.7%，優先度 8 ビット時に 73.8%と大. 置配線に使用するバウンダリのサイズはネットリストに対. 幅に面積を削減している．VC の本数が 2 本から 4 本と 2. する使用率が 75%となるように決定した．また，ターゲッ. 倍になると，SPC のルータ面積は優先度 2 ビット時に 3.00. トとなる TSMC 社 65 nm のプロセステクノロジは 9 層の. 倍，優先度 8 ビット時に 4.29 倍となる一方で，VIX のルー. 配線層を持つが，通常オンチップルータは CPU などとと. タ面積は優先度 2 ビット時に 1.88 倍，優先度 8 ビット時. もに配置配線されることを考慮し，配線には 5 層までを使. は 1.83 倍となった．これらの評価結果は，SPC の面積の. 用するものとした．. 多くを占める VC アロケータの面積が O(p2 v 2 × P riority). 消費エネルギーの評価では，1 フリットのデータを転送. であるのに対し，VIX の VC 割当て機能を持つクロスバア. する際に消費するエネルギーを評価指標とした．1 フリッ. ロケータの面積は O(p2 v × P riority) である点から，妥当. ト転送する際の平均消費エネルギー Ef lit は次式で計算で. であると考えられる．ルータの物理チャネル数が大きいと. きる．. き，SPC の面積はさらに増大すると考えられる．以上の. Ef lit = wHave × (Esw + Elink ). (2). 評価結果より，VIX は VC の数と優先度のビット数が増加しても面積の増加率が小さく，VIX は VC の数と優先度の. w をフリットのビット幅，Have を平均ホップ数，Esw を. ビット数に対してスケーラビリティがあるといえる．. ルータが 1 ビットのデータを転送する際に要するエネル. 4.2.3 クリティカルパス. ギー，Elink をリンクが 1 ビットのデータ転送に消費する c 2013 Information Processing Society of Japan . 配置配線後のルータのクリティカルパスを図 15 に示す．. 95.

(10) 情報処理学会論文誌. コンピューティングシステム. Vol.6 No.1 87–98 (Jan. 2013). 表 3 SPC の各モジュールの遅延. Table 3 Delay for each module in the SPC. # of. # of. VCs. Priority. Critical Path [ns] Req Ctrl. VC Alloc. Total. 1. 0.23. 1.09. 1.32. 2. 0.24. 1.10. 1.34. 3. 0.24. 1.16. 1.40. 4. 0.24. 1.21. 1.45. 5. 0.24. 1.25. 1.49. 6. 0.24. 1.26. 1.50. 7. 0.24. 1.30. 1.54. 8. 0.24. 1.38. 1.62. 1. 0.23. 1.39. 1.62. 2. 0.24. 1.47. 1.71. 3. 0.24. 1.51. 1.75. 4. 0.24. 1.60. 1.84. VC が 2 本の場合，VIX のクリティカルパスは SPC と. 5. 0.24. 1.64. 1.88. 比較して，優先度 2 ビット時に 10.4%，優先度 8 ビット時. 6. 0.24. 1.70. 1.94. に 16.2%短いという結果になった．また，VC が 4 本の場. 7. 0.24. 1.72. 1.96. 8. 0.24. 1.82. 2.06. 2. 図 15 ルータのクリティカルパス. Fig. 15 Critical path of router. 4. 合，VIX のクリティカルパスは SPC と比較して，優先度. 2 ビット時に 10.8%，優先度 8 ビット時に 21.2%短いとい. 表 4. う結果になった．. SPC のクリティカルパスは「VC アロケータ → 投機論理」というパスとなった．VIX のクリティカルパスは「リクエストコントローラ → クロスバアロケータ」というパ. VIX の各モジュールの遅延. Table 4 Delay for each module in the VIX. # of. # of. Critical Path [ns]. VCs Priority Req Ctrl VC Pool Xbar Alloc Total 1. 0.24. 0.14. 0.53. 0.91. スとなった．VIX はハードウェア量の多い VC アロケータ. 2. 0.25. 0.14. 0.59. 0.98. が削減されている分，クリティカルパスも削減されている. 3. 0.25. 0.14. 0.61. 1.00. 4. 0.25. 0.14. 0.62. 1.01. 5. 0.25. 0.14. 0.63. 1.02. 6. 0.25. 0.14. 0.65. 1.04. と考えられる．また，同様の理由で，VC の本数や優先度. 2. のビット数が増えた際にも，クリティカルパスの増加がゆるやかになっている．. 7. 0.25. 0.14. 0.66. 1.05. 提案手法によってルータのクリティカルパスの遅延が減. 8. 0.25. 0.14. 0.67. 1.06. ることを明確にするために，SPC のリクエストコントロー. 1. 0.29. 0.17. 0.58. 1.04. ラと VC アロケータ，VIX のリクエストコントローラ，ク. 2. 0.29. 0.17. 0.64. 1.10. 3. 0.29. 0.17. 0.68. 1.14. 4. 0.29. 0.17. 0.69. 1.15. 5. 0.29. 0.17. 0.70. 1.16. 6. 0.29. 0.17. 0.71. 1.17. の遅延の合計と比較して，VIX のリクエストコントローラ. 7. 0.29. 0.17. 0.72. 1.18. の遅延，クロスバアロケータの遅延，フリー VC プールの. 8. 0.29. 0.17. 0.73. 1.19. ロスバアロケータ，フリー VC プール各モジュールの遅延を表 3 と表 4 に示す．. SPC のリクエストコントローラの遅延と VC アロケータ. 4. 遅延の合計は，すべての場合において VIX の方が短い遅延となった．また，SPC リクエストコントローラ，および VIX のリクエストコントローラとフリー VC プールは，優先度の. 数に対してスケーラビリティがあるといえる．. 4.2.4 消費エネルギー配置配線後のルータの消費エネルギーを図 16 に示す．. ビット数に影響されず，ほぼ一定の遅延となった．優先度. VC が 2 本の場合，VIX の消費エネルギーは SPC と比較. のビット数によって遅延が増大する要因は，SPC では VC. して，優先度 2 ビット時に 12.9%，優先度 8 ビット時に. アロケータ，VIX ではクロスバアロケータとなっている．. 14.8%少ないという結果になった．また，VC が 4 本の場. SPC の VC アロケータと VIX のクロスバアロケータを比. 合，VIX の消費エネルギーは SPC と比較して，優先度 2. 較した場合，すべての場合において VIX のクロスバアロ. ビット時に 34.4%，優先度 8 ビット時に 39.0%少ないとい. ケータの遅延が短く，優先度のビット数が増えた際の遅延. う結果になった．これらの結果より，消費エネルギーの面. の増大もゆるやかになっている．. でも優位であることが分かった．VIX は SPC と比較して. 以上の評価結果より，VIX は VC の数と優先度のビット. c 2013 Information Processing Society of Japan . ハードウェアコストが低いため，このような結果になった. 96.

(11) 情報処理学会論文誌. コンピューティングシステム. Vol.6 No.1 87–98 (Jan. 2013). [3]. [4]. [5] [6]. 図 16 消費エネルギー Ef lit. Fig. 16 Power consumption Ef lit .. と考えられる．また，同様の理由で，VC の本数や優先度. [7]. [8]. のビット数が増えた際にも，消費エネルギーの増加がゆるやかになっている．以上の評価結果より，VIX は VC の数と優先度のビット数に対してスケーラビリティがあるとい. [9]. える．. 5. 結論. [10]. 本論文では，VC 割当てとクロスバ割当てのパイプラインステージを統合する優先度付きオンチップルータ VIX を提案した．提案手法はルータ面積を大幅に削減すると同時に VC 利用効率を向上させ，高優先度パケットの転送遅. [11]. 延削減，転送遅延のバラつき抑制およびスループット向上をクリティカルパスを増大させることなく達成した．5 種. [12]. 類の case study によってトラフィックパターン，優先度付加方式，VC 数，パケット長およびネットワークサイズによらず，VIX はネットワーク性能を向上させることができることを示した．また，提案手法を TSMC 65 nm のプロセスでレイアウトし，面積，クリティカルパス，消費エネルギーの評価を行い，VIX が VC の数と優先度のビット数に対してスケーラビリティがあることを示した．以上の結果より，優先度付き NoC において提案手法は有用である. [13]. といえる．謝辞本研究は科学技術振興機構 CREST の支援によるものであることを記し，謝意を表す．また，本研究の一部. [14]. は文部科学省グローバル COE プログラム「環境共生・安全システムデザインの先導拠点」によるものであることを記し，謝意を表す．. [15]. 参考文献 [1]. [2]. Balfour, J. and Dally, W.: Design and Tradeoffs for Tiled CMP On-Chip Networks, Proc. International Conference on Supercomputing (ICS’06 ), pp.187–198 (2006). Bolotin, E., Guz, Z., Cidon, I., Ginosar, R. and Kolodny, A.: The Power of Priority: NoC Based Distributed Cache Coherency, Proc. 1st ACM/IEEE International. c 2013 Information Processing Society of Japan . [16]. Symposium on Networks-on-Chip (NOCS’07 ), pp.117– 126 (2007). Bolotin, E., Cidon, I., Ginosar, R. and Kolodny, A.: QNoC: QoS architecture and design process for Network on Chip, Journal of Systems Architecture: The EUROMICRO Journal, pp.105–128 (2004). Dally, W.J. and Towles, B.: Route Packets, Not Wires: On-Chip Interconnection Networks, Proc. Design Automation Conference (DAC’01 ), pp.684–689 (2001). Dally, W.J. and Towles, B.: Principles and Practices of Interconnection Networks, Morgan Kaufmann (2004). Das, R., Eachempati, S., Mishra, A.K., Narayanan, V. and Das, C.R.: Design and Evaluation of a Hierarchical On-Chip Interconnect for Next-Generation CMPs, Proc. Symposium on High-Performance Computer Architecture (HPCA’09 ), pp.175–186 (2009). Das, R., Mutlu, O., Moscibroda, T. and Das, C.R.: Application-Aware Prioritization Mechanisms for OnChip Networks, Proc. International Symposium on Microarchitecture (MICRO’09 ), pp.280–290 (2009). Das, R., Mutlu, O., Moscibroda, T. and Das, C.R.: Aergia: Exploiting Packet Latency Slack in On-Chip Networks, Proc. International Symposium on Computer Architecture (ISCA’10 ), pp.106–116 (2010). Galles, M.: Scalable pipelined interconnect for distributed endpoint routing: The SGI SPIDER chip, Proc. International Symposium on High-Performance Interconnects (HOTI’96 ), pp.141–146 (1996). Grot, B., Keckler, S.W. and Mutlu, O.: Preemptive Virtual Clock: A Flexible, Efficient, and Cost-effective QoS Scheme for Networks-on-Chip, Proc. International Symposium on Microarchitecture (MICRO’09 ), pp.89–100 (2009). Hoskote, Y., Vangal, S., Singh, A., Borkar, N. and Borkar, S.: A 5-GHz Mesh Interconnect for a Teraflops Processor, IEEE Micro, Vol.27, pp.51–61 (2007). Howard, J., Dighe, S., Hoskote, Y., Vangal, S., Finan, D., Ruhl, G., Jenkins, D., Wilson, H., Borkar, N., Schrom, G., Pailet, F., Jain, S., Jacob, T., Yada, S., Marella, S., Salihundam, P., Erranguntla, V., Konow, M., Riepen, M., Droege, G., Lindemann, J., Gries, M., Apel, T., Henriss, K., Lund-Larsen, T., Steibl, S., Borkar, S., De, V., Van Der Wijngaart, R. and Mattson, T.: A 48Core IA-32 Message-Passing Processor with DVFS in 45 nm CMOS, IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC’10 ), pp.108–109 (2010). Kato, S., Fujita, Y. and Yamasaki, N.: Periodic and Aperiodic Communication Techniques for Responsive Link, Proc. IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’09 ), pp.135–142 (2009). Kim, J., Balfour, J. and Dally, W.J.: Flattend Butterfly Topology for On-Chip Networks, Proc. International Symposium on Microarchitecture (MICRO’07 ), pp.172–182 (2007). Kumar, A., Peh, L.-S., Kundu, P. and Jha, N.K.: Express Virtual Channels: Towards the Ideal Interconnection Fabric, Proc. International Symposium on Computer Architecture (ISCA’07 ), pp.150–261 (2007). Lee, J.W., Ng, M.C. and Asanovic, K.: GloballySynchronized Frames for Guaranteed Quality-of-Service in On-Chip Networks, Proc. International Symposium on Computer Architecture (ISCA’08 ), pp.89–100 (2008).. 97.

(12) 情報処理学会論文誌. [17]. [18]. [19]. [20]. [21]. コンピューティングシステム. Vol.6 No.1 87–98 (Jan. 2013). Matsutani, H., Koibuchi, M., Amano, H. and Yoshinaga, T.: Prediction Router: Yet Another Low Latency On-Chip Router Architecture, Proc. Symposium on High-Performance Computer Architecture (HPCA’09 ), pp.367–378 (2009). Mullins, R., West, A. and Moore, S.: Low-latency virtual-channel routers for on-chip networks, Proc. International Symposium on Computer Architecture (ISCA’04 ), pp.188–197 (2004). Owens, J.D., Dally, W.J., Ho, R., Jayasimha, D.J., Keckler, S.W. and Peh, L.-S.: Rereach challenges for on-chip interconnection networks, IEEE Micro, Vol.27, pp.96–108 (2007). Peh, L.-S. and Dally, W.J.: A deley model and speculative architecture for pipelined routers, Proc. Symposium on High-Performance Computer Architecture (HPCA’01 ), pp.255–266 (2001). Wentzlaff, D., Griffin, P., Hoffmann, H., Bao, L., Edwards, B., Ramey, C., Mattina, M., Miao, C.-C., III, J.F.B. and Agarwal, A.: On-Chip Interconnection Architecture of the Tile Processor, IEEE Micro, Vol.27, pp.15–31 (2007).. 松谷宏紀（正会員） 2004 年慶應義塾大学環境情報学部卒業．2008 年同大学大学院理工学研究科開放環境科学専攻博士課程修了．博士（工学）．現在，慶應義塾大学理工学部情報工学科専任講師．2009 年度より 2010 年度まで日本学術振興会特別研究員 SPD．計算機アーキテクチャ，オンチップネットワークの研究に従事．. 山. 信行（正会員）. 1991 年慶應義塾大学理工学部物理学科卒業．1996 年同大学大学院理工学研究科計算機科学専攻博士課程修了．博士（工学）．同年電子技術総合研究所入所．1998 年 10 月慶應義塾大学理. 水頭一壽（学生会員）. 工学部情報工学科助手．同専任講師を経て，2004 年 4 月より同助教授（現，准教授）．リアルタ. 2008 年慶應義塾大学理工学部情報工. イムシステム，プロセッサアーキテクチャ，並列分散処理，. 学科卒業．2010 年同大学大学院理工. システム LSI，ロボティクス等の研究に従事．日本ロボッ. 学研究科開放環境科学専攻修士課程修. ト学会，電子情報通信学会，IEEE 各会員．. 了．現在，同大学院後期博士課程に在籍．リアルタイム通信の研究に従事．. 向後卓磨 2009 年慶應義塾大学理工学部情報工学科卒業．2011 年同大学大学院理工学研究科開放環境科学専攻修士課程修了．現在，日本電気株式会社スマートエネルギー研究所勤務．マイクログリッド等の研究に従事．. 山崎大輝 2011 年慶應義塾大学理工学部情報工学科卒業．現在，同大学大学院前期博士課程に在籍．オンチップネットワークの研究に従事．. c 2013 Information Processing Society of Japan . 98.

(13)