並列環境部門 全体講評

並列部門には15件の応募があった。すべての応募者が逐次部門にも応募してい たので、まず逐次KLIC処理系を利用して逐次部門作品を開発し、その上で並列化 に挑戦したものと思う。環境に恵まれた人は複数ワークステーションなどの上 でPVMベースの分散KLIC処理系を動かし並列化の検討を行なったかもしれない。 だが、プロセッサ間通信性能に優れる共有メモリ版の並列KLIC処理系を利用 してデバッグやチューニングができた人はわずかであると思われる。このこと を考えると応募件数は我々の期待を上回るものであった。

さて、課題そのものは逐次部門と同一である。KL1言語には、並行プロセスのプ ロセッサへのマッピングを変更するだけで同一プログラムを逐次KL1処理系でも 並列KL1処理系でも動かすことができるという特徴がある。そこで並列計算機上 での評価に先だって逐次部門と同様の評価を逐次処理系を用いて行なうとともに レポートとプログラムの書類審査をすることとした。

多くのプログラムは、現在利用可能なプロセッサ台数を組込み述語 current_node で調べ それに基づいて負荷を分散していた。それらのほとんどは、与えられた プロセッサ台数が変わっても無修整で動作する汎用の並列プログラムであった。 他のものは、プロセッサ台数が２以上あるいは特定の台数（16など）であること を仮定してコーディングされていた。だが、プロセッサ台数に仮定をおいたプロ グラムも、プロセスのプロセッサへのマッピング（@node( ) 記法の引数）を変更 すれば逐次処理系で動作するはずであるので、そのような変更を施して検査プロ グラムにかけた。もちろん、プログラムの汎用性の点からは利用できる台数を 自動的にフルに利用するプログラムの方が高く評価できる。

検査プログラムと書類審査の結果 11件は少なくとも参加賞に値するものと判 定された。プログラムを並列化するときに些細な誤りを導入したと思われる作 品もあった。が、些細な誤りであると判定されたものについては参加賞を授与 することとした。

なお、15件中３作品はプロセスのマッピング記法を全く用いていなかった。 KLIC処理系は自動並列化は行なわないので、このままでは並列効果を出すことは できない。だが、並列処理に関する考察があり、かつ、マッピング指定を適切に 追加すれば並列化可能と思われる２作品については、動作確認のうえ参加賞を 授与することとした。

ただし、KL1言語の場合マッピングの変更はプログラムの論理的な正当性に影 響しないので、かりに並列計算機が手許になくても並列に動かしたときに作ら れるであろうプロセス構成での論理的な評価を逐次処理系で行なうことが可能 である。つまり、current_node(_, N) の呼出しに代えて「仮想的なプロセッ サ台数」を指定するゴール（N = 16 など）を実行するとともにゴールについ た @node( ) の指定は除去してしまえば、物理的には逐次実行であるが論理的 には16台のプロセッサがあった場合と同じプロセス構造、データ構造における正 当性が検査できる。このことを知っているとデバッグに非常に有用であろう。

さて、参加賞に値すると判定された11件については、逐次部門作品との性能比較 も兼ねて逐次部門の予選・本選データでの評価を行なうとともに AITEC にあ る SparcCenter 2000 上の共有メモリ版並列処理系での評価を行なった。

並列処理系での実行時間の測定は、逐次処理系のように CPU時間で行なうわけ にはいかない。つまり、全プロセッサの計算が終わり解が求まるまでの時間を 測定しなければならず、その値は CPU時間ほどは安定していない。また、各プロ グラムが要求する共有メモリ容量の違いなど手作業で対応しなければならない 部分も多かった。さらに、並列部門では特に大きなデータサイズでの性能評価が 重要であるし、プロセッサ台数をいろいろ変えて並列効果を見る必要もある。 これらのことから結論が出るまでには予想を大幅に上回る時間と労力を要した。

さて、並列処理の第一義的な目的は高い台数効果を得ることではない。高い絶 対性能を得ることである。逐次性能の低いプログラムが並列実行で性能向上を 果たしたとしても、それが逐次性能の高いプログラムの逐次性能をなお下回る ようでは無意味である。したがって、審査委員会でも性能評価においては まず逐次性能に注目した。また、データサイズを十分大きくしないと並列化オー バーヘッドの影響を小さくできないので、最終決戦ではかなり大きなデータを用 いて最大16プロセッサを用いて評価を行なった。

上位に残った作品は、データ値と重複数の対をデータ値から求めたハッシュ値 によって分類し、それぞれのグループに関する演算を各プロセッサで並列実行さ せる方式をとっていた。それ以外の方式、たとえばTRIEを用いた作品やプロセ スネットワークを構成して要素をフィルタリングするといった作品はモデリン グの上では興味深かったが並列実行しても上位作品の方式の性能には及ばな かった。

以上が審査経過であるが、最終的に「並列部門は最優秀賞は該当なし、優秀賞 １作品、佳作２作品」という結論となった。最優秀賞が見送られた主な理由は、 逐次性能が十分高くしかも並列実行による十分な性能向上が得られた作品が 残念ながらなかったことによる。しかし、これは必ずしも応募者の努力が不足してい たことを意味するものではないことをここで強調したい。なぜなら性能向上 には最終段階でのチューニングが不可欠であるが、それが存分にできる環境が普 及しているとは言えないからである。また、現在の処理系で十分な並列効果を得 るには最終決戦のデータよりもさらに大きなデータが必要であるように思えた。 したがって、むしろそのような状況で本部門に応募した方々の健闘精神を多と しなければならない。

並列記号処理系はまだまだ普及途上にあり利用できる人は限られている。また、 ＫＬ1による並列処理はＣ言語などの手続き型言語をベースとした並列処理と 比べ、より抽象的な計算モデルに立脚しているため、論理的に正しいプログラム を書くことは容易になった半面、性能チューニングのための方法論の普及確立は 今後の課題として残されている。KLIC開発チームや並列記号処理という研究分野 全体にとって貴重な経験と宿題を残すコンテストでもあった。


他部門の表彰 自由課題部門発表