第
7章
述べたのち、優先順位を持ったフロー制御法として占有法を提案した。第4章ではシミュ レーションに用いたシステムのハードウェア構成を説明し、シミュレータ上にどのように 実装したかについて述べた。
第5章では、格子結合における各仮想チャネルフロー制御手法の性能評価を行った。性 能比較は4章で述べたシミュレータを用いて行ない、ランダム通信およびFFTの性能を 評価した。まず、ランダム通信の平均転送時間および平均スループットの評価を行った。
その結果、平均転送時間は占有法の方が短く、平均スループットは占有法の方が大きくな り、双方とも占有法が良好な結果を示した。次に、FFTを実行した場合の性能評価を行っ た。その結果、平均通信時間は占有法の方が短くなるが、FFTの実行時間は双方ともほ ぼ同じになった。最後に、適応ルーティングとしてnorth last法を行った場合のランダム 通信の性能を評価した。その結果、パケット生成率を上げてゆくと両者の手法とも大きな 性能低下が起きたが、占有法では若干性能の低下が起こりにくくなることが分かった。
第6章では、階層型相互結合網であるTESHにおける仮想チャネルフロー制御法につい て説明し、さらにその性能を評価した。はじめに、TESHのネットワーク構成を説明し、
ルーティング法、デットロック回避の方法を述べ、階層型結合網用占有法のフロー制御を 説明した。実験は、まずランダム通信の平均通信時間および平均スループットを評価し た。その結果占有法は、メッシュの場合よりも大きな性能の向上が得られたが、階層型結 合網用占有法は性能に変化はなかった。階層型結合網用占有法の転送時間分布を測定した 所、占有法とほとんど変わらないという結果になった。FFTや四方向通信に関しても性 能評価を行った。その結果、占有法では実行時間が改善されたが、階層型結合網用占有法 では、かえって平均通信時間の悪化を招くため、FFTや四方向通信に関しても良い結果 が得られないことが明らかになった。階層型結合網用占有法に関しては、今後は平均通信 時間のばらつきを抑えられる方法を検討する必要があると思われる。
今後の課題として、第一に階層型相互結合網において平均通信時間のばらつきを抑えら れる方法を検討することと、TESHにおける効率的な適応ルーティングの方法を検討する ことが挙げられる。
謝辞
本研究を進めるにあたり、熱心に御指導頂いた北陸先端科学技術大学院大学 堀口 進 教 授、阿部 亨 助教授に深く感謝いたします。
副テーマで御指導頂きました金子峰雄助教授に感謝いたします。
研究の進め方等で、日頃より御指導して下さった山森一人助手、林亮子助手に深く感謝 いたします。
最後に、有意義なアドバイスを下さったマルチメディア統合システム講座の皆様に深く 感謝いたします。
参考文献
[1] 清水, 堀江, 石畑. 高速メッセージハンド リング機構. 情処学論, Vol. 34, No. 4, pp.
638{647, 1993.
[2] J.Kuskin et.al. The stanford ash multipro cessor. In ISCA94, pp. 302{313, 1994.
[3] 坂井,岡本,松岡,廣野,児玉,佐藤,横田. 超並列計算機rwc-1の基本構想. InJSPP93,
pp. 87{94, 1993.
[4] L.M.Ni and P.K.McKinley. A survey of wormhole routing techniques in direct
net-works. Proc of the IEEE, Vol. 81, No. 2,pp. 62{76, 1993.
[5] P.Kermani and L.Kleinrock. Virtual cut-through: A new computer communication
switching techniques. ComputerNetworks, Vol.3, No.4, pp. 267{286, 1979.
[6] W.J.Dally. Virtual-channel ow control. IEEE Trans on Parallel and Destributed
Systems, Vol.3,No. 2, 1992.
[7] M.P.Merlin and J.P.Schweitzer. Deadlo ck avoidance in store-and-forward networks
- 1: Store and forward deadlock. IEEE Trans. on Comm., Vol. COM-28, No.3, pp.
345{354, 1980.
[8] D.H.Linder andJ.C.Harden. Anadapticeand faulttolerantwormhole routing
strat-egyfor k-aryn-cubes. IEEE Trans. on Computers,Vol.C-40,No. 1,pp. 2{12,1991.
[9] J.Rexford, J.Hall, and K.G.Shin. A router architecture for real-time point-to-p oint
networks. In ISCA'23, pp. 237{246, 1996.
[10] H.Song, B.Kwon, and H.Yo on. Throttle and preempt: A new ow control for
real-time communicationin wormhole networks. In ICPP, pp. 198{202, 1997.
[11] 戸田, 西田,高橋,Michell, 山口. 優先度先送り方式による実時間相互結合網用ルータ チップの実現 と性能. 情処学論, Vol.36, No. 7,pp. 1619{1629,1995.
[12] 天野, 西,西村,工藤. 超並列計算機プロトタイプＪＵＭＰ−１のルータチップ. 信学 技報(cpsy-94-98), 電子情報通信学会, 1995.
[13] V.K.Jain, T.Ghirmai,and S.Horiguchi. Tesh:anew hierarchical interconnection
net-workfor massively parallel computing. IEICE Transactions, Vol. E80-D,No. 9, pp.
837{846, 1997.
[14] C.J.Glass and L.M.Ni. Maximally fully adaptive routing in2d meshes. In ISCA92,
pp. 278{287, 1992.
[15] Jong-Pyng Liand MattW.Mutka. Real-time virtualchannelowcontrol. In
Inter-national Phoenix Conference on Computers and Communications,pp. 97{103,1994.
[16] 富田眞治. 並列コンピュータ工学. 昭晃堂, 1996.
[17] 堀江,石畑, 池坂. 並列計算機ap1000における相互結合網のルーチング方式. 信学論
D-I, Vol. J75-D-I,No. 8, pp. 600{606, 1992.
[18] 天野英晴. 並列コンピュータ. 昭晃堂, 1995.
[19] W.J.Dally and C.L.Seitz. Deadlo ck-free messageroutinginmultipro cessor
intercon-nectionnetworks. IEEE Trans. on Computers, Vol.C-36, No.5, pp. 547{553, 1987.
[20] J.Duato. A new theory of deadlock-free adaptive routing in wormhole networks.
IEEE Trans. on Parallel and Distributed Systems, Vol. 4, No. 12, pp. 1320{1331,
1993.
[21] Y.R.Potlapalli. Trendininterconnectionnetworkstopologies: Hierarchicalnetworks.