1993年7月
しかし,最近の RISC や並列計算機のめざましい進歩と普及は,この期待とは逆 の方向をいくものであったと言える.これは,むしろ歓迎すべき方向であったと 思う.なぜなら,プログラミング言語と計算機アーキテクチャそれぞれに対する われわれの理解を深め,さらには両者をつなぐ方法論の進歩をもたらしたからである.
この動きの背景には,コンパイラ技術の近年のめざましい進歩がある.これは, 理論と実際がよくかみ合っている分野と言えよう.すでに逐次言語については, 人間が容易に想像できないような機械語を最適化コンパイラが出すようになった. レジスタ割付けのようなスケジューリング問題は,本来計算機が得意とする問 題であったわけである.さらに,RISC や並列計算機の出現は,文や命令のスケ ジューリング技術をも大きく進展させた[2].これらの スケジュー リングは,単に最適化問題を解けばよいというものではない.むしろ,最適化問 題を切り出すためのプログラム解析技術がきわめて重要である.より詳細で,よ り大域的な解析がとりいれられるようになった結果,高度な最適化が可能になっ たわけである.
このように,既存のプログラミング言語を所与のものとして,自動並列化を含む 最適化をしようとする試みの一方で,新たな並列プログラミング言語の設計も盛 んである.これは,より簡潔で汎用性の高い理論を軸として,並列処理へのエレ ガントな方法論を構築しようとするものである.しかし,既存の言語のもつ巨大 な文化と慣性に対抗するためには,強固な理論的基盤と実用性とを同時に示す 必要がある.
筆者は長年,並行・並列プログラミング言語 GHC および KL1 [9] の研究開発にたずさわってきた[10]が,そこで感じたこと は,言語設 計やその後の発展に際して,処理系作成,記述力,理論的扱いの三者を,バラン スよく考えることの重要性である.諸側面の相互交流が重要であると言うことも できる.
例をあげよう.プログラミング言語の理論研究の一つの柱は,その形式的意味論の研 究である.最適化コンパイラの正当性など,意味論なしでは議論できないはずで あるのに,残念ながら形式的意味論の研究がこれまでに実践に及ぼした影響はあ まり大きいとは言えない.その一因は,意味論研究からのフィードバックの不足 にあるのではないかと思う.与えられた言語を正確に記述することは当然重要で あるが,それだけでは一方通行に終わってしまう.言語設計者の立場からすれば, 理論研究から言語設計への積極的なフィードバックがほしいのである.
処理系作成や記述力といった実用的側面と,言語設計との相互交流も重要である. 理論的計算モデルから発生した言語がへたに実用性を目指すと,理論研究のため の版と実用版とができ,双方がほとんど遊離してしまいかねない.GHC/KL1 の一 つの設計目標は,この遊離を最小限にとどめるということであった [10].理論版である GHC と実用版である KL1 の間に差異 はあるが, その差異と関係を明確にするように努めた.
先述のプログラム解析であるが,新たな並列言語の場合も,既存の手続き型プロ グラムに伍する性能を得るために重要な技術となる.ここで,処理系を高速化す るだけならば高度なプログラム解析の枠組を作ればよい.しかし言語設計まで含 めて考えると,プログラム解析がアドホックにしかできないよりは,静的な(つ まりコンパイル時の)型検 査のように系統的にできるほうがはるかに望ましい.つまり,理論的定式化を,言 語機能,つまりは概念の形にして明示することができれば大きな前進である.
言語設計,理論,処理系作成の間のこのような相互交流が比較的うまくいった例 をひとつあげよう[4].GHC では,並行プロセスの間の 通信に, 論理型言語の特徴であるユニフィケーションという演算を使っている.この演算 は,双方向の情報の流れを許す強力なものであるが,並行言語の通信機能として 使うときは,複雑な情報の流れが静的に解析できると,処理系作成の上で好都 合であるし,記述力が大きく犠牲になることもない.そこで,GHC プログラムの 入出力モードの体系と,それに基づく静的解析の技法を提案した [8].これはプログラム解析手法の提案であると同時に, 言語機能 の提案にもなっている.またこれは,新たな最適化手法の実現を可能にした [8].このような相互交流は,理論と実践を分業でやっ ていたら容 易ではないであろう.
このギャップは,現実の並列プログラミングと大多数の並列アルゴリズム研究 の問題設定がまったく異なるからであるような気がしてならない.多くの並列プ ログラマにとっての当面の目標は,良い逐次アルゴリズムをもとに,できるかぎり の台数効果を引き出すこと,つまり n台の計算機で理想的には n 倍の性能 向上を図ることである.これに対して,並列アルゴリズム研究の主な関心は,十 分な台数のプロセッサが利用できるときの時間計算量にあった.
筆者は,アルゴリズムに内在する最大並列度以上の台数のプロセッサでの処理を 考える分野を超並列処理,それに比べて十分少ない台数のプ ロセッサでの 処理を考える分野を並列処理と呼び,明確に区別するのがよ いと考える. もちろん,現実のプロセッサ台数をこう単純に分類できるものではないが,この 両極端をよく考えることは意味があるし,具体的なプロセッサ台数でこの二つの 用語を分類しようとする試みに比べれば,はるかに合理的である.
すると,並列処理では,逐次処理の時間計算量を改善するどころではなく,いか にそれを悪化させずに台数効果をあげるかが重要課題であることがわかる.もと のアルゴリズムに 100p% の逐次部分があると,1/p倍以上の台数効果は 望めないというAmdahl の法則[5] がある.並列処理への理論的消極論としてよく引用される が,問題のサイズを大きくすればpは一般に小さくなるではないかという, 通常の反論だけに終わってしまうのも寂しい.重要なのは,もとの逐次アルゴリズ ムの中にある,強すぎる本質的逐次性を緩和して,pの値を下げる方法論であ る.まだ現在は,問 題ごとの個別的な対応が主であるが,たとえば見込み計算 (speculative computation) [7] という技法が有効であることは具体的に示されてきている.これ をより一般的な並列プログラミング・パラダイムとして定着させることは,近未 来の並列処理にとって非常に重要であろう.
並列処理における理論と実際の橋渡しを目指した計算モデルも提案されてきてい る.その一つがバルク同期並列(bulk-synchronous parallel, BSP)モデル [11]であり,逐次計算の文化におけるvon Neumannモデル のような役割を目指している.
一方,超並列処理のセッティングは,理論的可能性の追求の場としては非常に魅 力的であり,実際並列アルゴリズムや超並列人工知能[3] の研究から 得られる知見は大変興味深い.また,超並列計算機による問題解法として,問題 の構造をダイレクトにマッピングする方式が有望視されている.これらの研究や 考え方に共通するのは,論理的な見通しのよさの追求であり,これはアルゴリズ ム設計の出発点としては確かに重要であろう.超並列のパラダイムは,ソフトウェ アの質的変革を起こす可能性をもっている.
しかし,大多数の人にとって,超並列処理の第一目的は速度向上であるにちがい ない.実用化が近づき,性能への要求が強まるにつれて,現実の計算機の物理的 側面への配慮をはじめとする,非常に多くの工学的な工夫が,理論の枠組の中で も必要となろう.超並列計算量のモデルとして代表的なのは PRAM (Parallel Random Access Machine) [1] であるが,これに対す る批判的代 案の一つとして,3次元空間での実現における制約を設計原理とした Spatial Machine [6]というモデルが出てきている.
他分野から例をひくと,(計算機でない)機械設計においても,機械の動作が高速 化するにつれ,機構学だけでなく力学的な配慮が重要となってきた.この力学と 力学的配慮とに対応するものの発展が,超並列処理の分野でも望まれる.
逐次アルゴリズムの文化を考えてみるに,工学的意義の追求によって得られた蓄 積の比重はきわめて大きい.このような蓄積を図ることが,超並列処理が成熟す るために必要で,それによって,並列処理による改革的アプローチと超並列処理 による革新的アプローチの比較が,真に興味深いものとなろう.