負荷分散はプログラムで指定する

実際の並列計算機に計算を効率良く行なわせるためには, ふたつのことを考え なくてはならない.

負荷の分散

行なわなければならない計算が一台のプロセサに集中してしまうと, そのプロ セサの処理が終るまで計算が終らなくなってしまい, 並列に計算している意味 がない. したがって, 全体の問題をいくつかの部分問題に分割し, 多くのプ ロセサに均等に分散して, どのプロセサにも同程度の負荷がかかるようにしな ければならない.

通信の削減

全体の問題をいくつかの部分問題に分割して分散させるには, まず問題を配る ための通信が必要で, 最後には結果を集めるための通信が必要になる. また, 効率の良いアルゴリズムを使うには部分問題が完全に独立にできず, 計算途中 でも通信が必要になることも多い. 通信が多くなるとそのコストのために返っ て効率が落ちてしまうこともある. したがって, なるべく部分問題を解くプ ロセサ間の通信が少なくなるような問題の分割が重要である.

特に問題の部分問題への分割の仕方は, 解くべき問題が何なのか, どのような アルゴリズムを使うのかに大きく依存する. 現在のソフトウェア技術では, 部分問題への分割とその分散についての指針を明記していないようなプログラ ムが与えられても, それに対していつでも自動的に効率的な負荷分散を行える ようにすることは, まず不可能である. もちろん, たとえば行列のかけ算を 多数行なうなど, あらかじめ行なうべき計算の量を予測しやすい問題領域に限 定すれば, かなり効率的な自動並列化を行なうこともできる. しかし, いわ ゆる知識情報処理のような, 計算結果によって次に行なうべき計算が動的に大 きく変わることがあたりまえの分野では, 自動負荷分散は非常に難しい.

現在の技術がこういう水準にあるので, KL1 はこの困難な自動負荷分散の方式 の研究ツールとして役に立てるものと位置付けている. したがって, 負荷分 散は言語処理系で自動的には行おうとせず, プログラマが指定するものとした. ただし, プログラマがさまざまな負荷分散指定を行なうときに, できるだけ簡 単にできるように工夫している. それについては次節に述べる.