すくなくとも1種類のアルゴリズムをベースにして POSIX スレッドライブラリを利用して並列化することを必須とする。 余力がある場合、共有メモリ向けマクロの利用を試みること。 また、全部の種類を並列化を試みるのもよい。

• pthreads ライブラリの利用
  • ここを参考にして pthreads ライブラリの利用した、LU分解の並列化を行うこと。
  • LU分解関数の部分のみ並列化すればよい
  • できるだけ高速化を試みること
  • 逐次版のLU分解関数は残しておき、 「-a N」の指定で 並列版のLU分解関数の選択もできるようにすること
    並列版には N として 101〜を用いること。
  • 「-p P」の指定で スレッド数 P を選択できるようにすること
    「-a N」のN を 101〜として並列版としたときの P のデフォルト値は 2 とする．
  • 「-a N」が未指定の場合は 逐次版で一番高速と期待できるものにしておく。 ただし，「-p P」の指定でスレッド数 P を2以上とした場合には 並列版で一番高速と期待できるものにする．
  • すくなくとも以下のうち一つを試みること (高速化のためには複数を比較できるとよいので，余力があれば 複数試すこと)
    • right-looking法を分割型並列処理
      (実際には バリア同期を用いると良い)
    • Crout法を分割型並列処理
      (実際には バリア同期を用いると良い)
    • left-looking法をパイプライン型並列処理
    • ブロック化アルゴリズムを分割型並列処理
• 共有メモリ向けマクロの利用
  • 余力があれば，スレッド生成，join については pthread関数を用いつつ， 同期と，関連するアクセス順保証については， pthread_mutex_lock, pthread_mutex_unlock を伴う pthread_cond_wait, pthread_cond_broadcast の代わりに， ここの マクロ版共有メモリ向けプリミティブ を利用するようにしてみる．
  • 余力があれば，再帰的アルゴリズムをワークスティール （課題6参照）

LU分解の並列化

• right-looking法を分割型並列処理
  • 実際には，SPMD型でバリア同期を使うとよい．
  • 書き込みが多く(広い範囲)バンド幅を使い切りやすい。
• Crout法を分割型並列処理
  • right-looking法よりは書き込み範囲は狭い．
• left-looking法をパイプライン型並列処理
  • パイプライン型並列化は分割型並列化より難しい．
  • 同期の頻度は多くなる．
• より高度なアルゴリズムの並列化
  • ブロック化したアルゴリズムについては，ブロック内は並列化しなくてよい． ブロック化して局所性が高まっている場合，分割型並列処理も有望． (実績の多い方法)
  • 再帰的アルゴリズム(分割統治)の場合， 単純に並列化することは難しいが， 課題6に示すワークスティール方式は適している (ただしL全体的な終了判定ではなく分割統治に沿ったjoin型の同期が必要)．