プログラムの説明書

1.内部表現の形式

encodeは以下のように行なっています。

  (1) 与えられたマルチ集合のリストを、その各要素の値を
      プロッセサ数でmodを取った値により、
      プロセッサと同じ数のリストに分割する。
  (2) リストを取りまとめて、プロセッサの数と同じ長さの配列にする。
  (3) 各リストの中身をソートする。
  (4) 各リストについて、リストの同一要素を取りまとめて、
      c(要素,その要素の数)という構造のリストに変換する。

例えば、マルチ集合 [7,7,2,7,7,5,1,7,4] が与えられた場合、
(1)(2)により、{[7,7,7,7,5,1,7],[2,4]}とされ、
(3)により、{[1,5,7,7,7,7,7],[2,4]}とされ、
(4)により、最終的に、{[c(1,1),c(5,1),c(7,5)],[c(2,1),c(4,1)]}
という内部表現に変換されます。


2.並列化について

内部表現はもともとプロセッサの数に分割された形式を持っているため、
配列の各要素の演算を各プロセッサに割り当てることにより
並列化が行なえます。

各プロセッサにデータを割り当てる処理は、述語do1またはdo2により
一括して行なっています。


3.考察および問題点

自分の使っている WS の PVM があまりうまく動作しなかったため、
十分な動作チェックができませんでした。
この課題では、データ量に比べて演算のコストが小さいため、
並列化をしない方が実行速度は向上するかもしれません。

内部表現をこのプログラムのような形式にするならば、できれば、
分割したデータを各プロセッサが各々保持することが望ましく、
それによってパフォーマンスは大きく向上することでしょう。

あるいはまた、プロセッサ数が変化する環境にあったり、
内部表現のデータにかたよりがある(mod を取るとある値が多くなってしまうような)
場合は、modを取る数をプロセッサ数より十分大きな値にして、
暇なプロセッサに動的に割り当てることができれば良いかもしれません。