Teaching

数理情報工学演習第二 B（ 4年生2004年冬学期）

「アルゴリズム運算による並列プログラムの導出」

日程

11月26日金曜日10時15分から，工学部6号64講義室にて．

レポートの提出は，12月10日までに筧宛にemailで．

概要

武市先生の資料「アルゴリズム運算による並列プログラムの導出」を使い，並列化定理（Parallelization Theorem）の解説を行ないます．欠席した人は研究室に資料を取りに来て下さい．

課題

同資料内の演習問題 9，演習問題10．

資料のポイント

• 累積を持たない計算の場合，二分木を葉から根へと計算することでO(log n)で求められる．【1.3節および1.4節（pp. 3--）】
• 累積を持つような計算の場合，まず値の組を返す関数tupを用いた計算を考える．その組の値を見ると，累積に依存するものと依存しないものとがある．そこで，
  1. 依存しないで決まる値を先に（並列に）計算する
  2. 次いで，その先に求めた値を使って残りの値を（並列に）計算する
  ことによってO(log n)のプログラムが求められる．【2.1節（pp.7--）】
• 並列化定理に示される式で演算子ふたつ（式の返り値のためのoplusと累積のためのotimes）を適切に指定することで，上記tupの演算が自動的に求められる【3.1節（pp.13--）】