現在，並列計算機は科学技術計算をはじめ，多くの応用で利用されている．そのなかでも，メッセージ通信で並列処理を行なう分散メモリ型並列計算機は，その拡張性，柔軟性，信頼性に優れ，ノードとしてPC，ワークステーション，サーバなど多様な形態をとることが可能であり，多くのシステムに適用されている．並列処理の高速化には，各ノードの演算性能を向上させるだけでは応用性能は向上せず，通信性能の向上が必要である．そこで，本研究では，分散メモリ型並列計算機における相互結合網の性能向上について研究を行った．その結果，

1.構造化チャネルルーティングによる低レイテンシ，高スループット，デッドロックフリーな通信方式の実現

2.トーラスネットワークでの最適な全対全通信方式の実現

3.メッセージ長に比例するメッセージ処理オーバヘッドの削減

4.並列化コンパイラが必要とする通信機能の実現の4つの成果を得た．

並列計算機のノード間を接続する相互結合網は，その層構成をみると，物理層，リンク層，トランスポート層にわけることができる．物理層の機能として，信号伝送，コーディングがある．リンク層の機能として，フロー制御，仮想チャネル，ルーティングがある．また，トランスポート層の機能として，送達保証，パケット化，メッセージ処理がある．本研究では，リンク層とトランスポート層での性能向上ついて検討を行った．

構造化チャネルルーティングは，リンク層の仮想チャネルとルーティングに対応するものである．ワームホールルーティングは，ストアアンドフォワードに比べてレイテンシの小さい通信を実現できるが，スループットの低下とデッドロックの発生という2つの問題を持っており，これまで，この2つの問題を同時に解決する方式は提案されていなかった．本研究で提案した構造化チャネルルーティングは，ワームホールルーティングに構造化バッファプールのアルゴリズムを取り入れることにより，この2つの問題を同時に解決する．さらに，本方式を実現するスイッチLSIを開発し，実システムでの評価を行ない，性能を検証した．

トーラスネットワークでの最適な全対全通信方式は，リンク層のルーティングに対応するもので，ネットワークの性能を最大限に引き出す全対全通信を実現する．多くの応用で頻繁に使用される通信パターンの一つである全対全通信は，通信転送量が多く，マトリクスの転置，二次元FFT，ADIなどで使用されている．これまで，ストアアンドフォワードあるいはワームホールルーティングを使った方式も含め多くの研究がなされているが，メッシュの端と端が接続されているトーラスネットワークでの最適な全対全通信方式は提案されていなかった．本研究では，ワームホールルーティングを使ったトーラスネットワーク上での最適な全対全通信を提案した．トーラスネットワークでは，メッシュネットワークの2倍の性能を実現することができる．本方式は，1次元トーラスから多次元トーラスのネットワークに適用することができ，また，正方形だけでなく，長方形のネットワークにも適用することができる．さらには，接続チャネルが単方向あるいは両方向に対しても最適な方式を提案している．提案した方式では，ノードと相互結合網とのインタフェースのバンド幅は相互結合網の1チャネルのバンド幅と同じとしており，トーラスネットワークを持つ並列計算機に広く適用することができる．

トランスポート層のメッセージ処理の高速化では，まず，分散メモリ型並列計算機の性能を向上させるために必要な演算性能と通信性能のバランスについて定量的な評価を行った．その評価のために，メッセージパッシングアーキテクチャを対象に応用問題への通信や演算性能の影響を容易に調査可能とするメッセージレベルシミュレータを開発した．評価の結果，CPU性能を32倍に上げても，メッセージ処理性能を向上させなければ10倍程度の性能向上しか望めないこと，ネットワーク性能の影響に比べると，メッセージ処理性能が応用性能に大きな影響を与えることを示した．

その上で，トランスポート層のメッセージ処理について，大きく分けて二つの方式を検討した．まず，第一は，メッセージ長に比例したメッセージ処理オーバヘッドの削減である．メッセージ処理オーバヘッドは通信機能の設定など一定の時間を要するものとメッセージ長に比例する時間を要するものがあり，前者のオーバヘッドに対してはハードウェア化などいくつかの方法が提案されているが，後者のオーバヘッド削減の効果については研究されていなかった．本研究では，メッセージ長に比例したメッセージ処理オーバヘッドを削減するため3種類の方法，送信と演算のオーバラップ，メッセージをユーザ領域に直接受信する直接メッセージ受信，受信と演算とのオーバラップを適用した場合の効果について定量的に評価を行った．その結果，送信と演算のオーバラップは通信オーバヘッドを削減するが，その効果はあまり大きくなかった．直接メッセージ受信の効果は，応用問題の性質に依存するが22％性能が向上するものもあった．受信と演算とのオーバラップでは，大幅に性能向上し，約2倍もの性能向上となるものもあった．これらの検討結果は，今後の相互結合網インタフェースの設計に重要な指針を与えるものと考えている．

第二に，並列化コンパイラが必要とする通信機能，つまり，並列化コンパイラが生成したコードを効率良く実行する通信機能を検討し，それをハードウェア化した場合の効果についてシミュレータを用いて評価した．従来，並列化コンパイラに必要な機能という観点からの検討がなされておらず，並列化コンパイラが生成したコードを効率良く実行することができなかった．本研究では，通信機能を検討した結果，ダイレクトリモートアクセスとその通信完了を通知するフラグ更新（PUT/GETオペレーション），バリア同期，グローバル演算が必要であると結論した．そして， PUT/GETをハードウェア化した場合の性能を，実際の並列化コンパイラが生成したコードなどの応用に対してシミュレーションで定量的に評価し，その有効性を示した．本研究により，並列化コンパイラが生成したコードの効率的な実行を実現し，分散メモリ型並列計算機の課題の一つであったプログラミングについて，並列化コンパイラの適用を促進することができると考える．また，本研究で評価したPUT/GETをサポートするハードウェアは，PUT/GETによりメッセージバッファリングのオーバヘッドを削減し，通信と演算をオーバラップさせることでメッセージパッシングに比べて実行性能を向上させることができる．

本論文は、「並列計算機における相互結合網の高速化の研究」と題し、9章からなる。計算機処理に対する高速化の要求は留まる所を知らない。その要求を満たすための重要な手法が並列計算機であり、多数の計算機を結合することによって大規模な処理性能を実現するが、その性能向上のキーは計算機の単体性能の向上と、計算機を接続する相互結合網の性能向上である。本論文は、並列計算機の中でも大規模な性能を実現する上で中心的な役割を果たす、分散メモリ型並列計算機の相互結合網の高速化手法について論じたものである。

第1章「序論」は、研究の背景、目的を述べるとともに、本論文の構成についてまとめたものである。

第2章「並列計算機と相互結合網」は、対象とする分散メモリ型並列計算機の構成とそのための相互結合網について述べたもので、結合網の機能を物理層、リンク層、トランスポート層の3層に分けて検討し、それぞれの層における課題を論じて、本論文で取り上げる4つの課題を示している。

第3章「構造化チャネルルーティング方式」は、一つ目の課題であるワームホールルーティングでのデッドロック回避と高スループットの実現について論じたもので、ワームホールルーティングに構造化バッファプールのアルゴリズムを取り入れた構造化チャネルを提案することにより、それを実現したものである。更に、ネットワークとして二次元トーラスを用いた高並列計算機AP1000上にその方式を実装し、それがネットワークの持つ最大の転送スループットを出すことを実験により確かめている。

第4章「トーラスネットワークにおける最適全対全通信方式」は、多くの応用で用いられる通信パターンの中でよく用いられ、また、最も多くの通信転送量を必要とする全対全通信を取り上げ、その最適な方式を提案したものであって、これが第二の課題の解決を与えている。本アルゴリズムは一次元から多次元のトーラスネットワーク、長方形形状にも適用可能で、並列計算機AP1000にこれを実装し、チャネルの転送ピーク性能が達成可能なことを示している。

第5章「演算と通信の性能バランス」は、総合的な処理性能向上には、単なるネットワーク性能だけではなく、メッセージ処理性能とネットワーク性能を含む通信性能の向上が不可欠であることを指摘し、CPU性能と通信性能のバランスを定量的に理解して分散メモリ計算機の設計指針を与えるために、メッセージレベルシミュレータMLsimを開発して、これらの性能が応用性能にどの程度影響を与えるか検討した結果について述べている。その結果、CPU性能を上げてもメッセージ処理性能を向上させないと著しく応用性能が劣ること、通信性能が1/4となると応用性能が1/2となることなどいくつかの知見を与えている。

第6章「メッセージ通信方式I：通信と演算のオーバラップと直接メッセージ受信」は、第三の課題であるメッセージ処理時間を削減するための手法について論じたもので、メッセージ処理時間のうち、削減が困難であったメッセージ長に比例したオーバヘッドを削減する手法を与えている。すなわち、演算と送信とをオーバラップさせる方法、直接メッセージ受信手法、受信と演算とのオーバラップの3つの手法で、これらの効果を前章のシミュレータを用いて定量的に評価している。その結果、送信と演算のオーバラップは余り効果がないが、直接メッセージ受信の効果は応用問題に大きく依存し、また、受信と演算のオーバラップは応用性能に大きな影響を与えることを示している。

第7章は「メッセージ通信方式II：並列コンパイラが必要とする通信機能のサポート」で、分散メモリ型並列計算機が広く使われるために、ハードウエアの詳細を意識しないでプログラミングが行えるための支援を論じたものである。本章では、HPF、VPP FortranをAP1000に実装する場合を例題に取り上げ、並列コンパイラで生成されたコードを効率よく実行するために必要となる通信機能を検討し、それがダイレクトリモートデータアクセス、ストライドデータ転送、通信終了判定、バリア同期とグローバル演算であることを明らかにした。また、これらの内、リモートデータアクセスと通信終了判定は、PUT/GETオペレーションをハードウエアによってサポートすることによって高速化することが可能で、大変有効であることをシミュレーションによって示している。

第8章は「研究の位置づけ」であり、上記研究の成果を他の同種の研究と比較してそのオリジナリティを主張するとともにその意味合いを述べたものである。

第9章は「結論」である。

以上、これを要するに本論文は、分散メモリ型並列計算機の性能向上に本質的な相互結合網の高速化手法について論じ、それに必要な種々の要素方式を提案し高並列計算機AP1000に実装することによってその有効性を明らかにしたもので、情報工学上貢献するところ少なくない。

よって、本論文は、博士（工学）の学位請求論文として合格と認められる。