2005/09/30

最上の日々 9/28より:

１、関数型プログラミングは、たまたま並列性を最大に記述する方法でもある。それを利用すれば並列性の抽出は容易だ。

２、関数型のプログラムの構文木を直接実行するプロセッサがあるといい。でもそこまで行かなくとも二股同時実行コール命令を追加するだけでも効果がある。

2.について。面倒なのは呼び出しより帰って来た後の同期だから、 「二股同時コール」はそこまで含めてのことだろう。 ただ、プロセッサレベルでは非同期呼び出し命令と同期命令に分かれてた 方が使いでがあるし、そうなるんじゃないかと思う。(言語レベルでの並列 呼び出しをコンパイラが非同期呼び出し+同期命令に展開すればいい)

例えばPS2ではコードとデータを用意してDMAをキックすることでVUが (CPUと並行して)計算を進めてくれる。結果を受け取るには 確かVUから割り込みもかけられたと思うが、コンソールゲームでは 計算時間の予測がたてやすい場合も多くて、CPU側である程度他の計算を 進めてからポーリングして同期していた。

ハードウェアでマルチコアに複数のスレッドを振ってくれるような機構が 出来たなら、非同期呼び出し命令も同期命令もスレッド操作のプリミティブ として処理されることになるかな。

1.について。副作用無しの関数型プログラミングは、 それだけでは並列性の記述には不十分だ。

「AかつB」「AまたはB」というパターンには、AとBを独立して評価できる場合と Bの評価可能性がAの評価結果に依存する場合がある。 後者の例は(and (char? x) (char=? x #?a))。 逐次プログラミングでは両者の区別は不要だが、並列プログラミングでは 区別してもらわないと、前者でAとBを並列に評価する機会を失う。

これはかなり本質的な違いで、「『AまたはB』でAかBの いずれかが停止しなくても、もう一方が停止すれば答えが出る」 というセマンティクスは並行演算を前提としないと実現できない。

これらの演算は実用的には非常に重要だ。並列演算を適用したい大きな データセットを扱う問題であっても、得たい答えは入力の データセットより遥かに小さい場合が多い。 ということは多くの問題で、どこかでたくさん並列に流れてた データの流れがぐっとしぼられる点が必ず一つ以上あるということだ。 例えば「たくさんのものの中から(どれでも良いから)ひとつ条件を満たすものを選ぶ」 という操作は頻出するけれど、関数的な素直な記述：

(define (find pred set)
  (cond ((pred (car set)) (car set))
        (else  (find pred (cdr set)))))

からは並列性は抽出できない。

並列に条件判断を走らせて、どれかひとつが帰って来た時点でそれを採用し 他は捨てる、ということになれば、走っている並列演算をキャンセルする機構も 組み込みで必要になる。

Tag: Programming