MPI紹介 ①

MPI ( Message Passing Interface )

プログラムを並列化するためのライブラリ

スーパーコンピュータから、PCクラスタ、一般のPCで使用可能！！

並列コンピュータ　イメージ

MPIは、プロセス並列である。
プロセスは、独自のメモリ空間を保持する。
MPIでは、MPIプロセスを生成し並列処理を行う。
MPIプロセス間のデータのやり取り(他のプロセスにデータをあげたり・もらったり)は
MPI通信関数を使用してOSを介した通信によって行われる。

プロセス並列の他に、スレッド並列というものがある。
例えば、OpenMPやpthreadなどがある。
スレッドは、親プロセスからフォーク処理によって生成される。
複数のスレッドを生成した場合、スレッド間は親プロセスが持つメモリ空間
を共有することができる。

空間充填曲線 応用

空間充填曲線を使った応用例 

モートンオーダー、ヒルベルト曲線を使用して
メモリ上のデータを並び替える方法

 ランダムな1000個の点を
　　x座標 :　0.0 ~ 10.0
　　y座標 :　0.0 ~ 10.0
    の範囲に発生させ、メモリ上の順番に沿って点を線で繋いだ場合の例

モートンソート

空間分割レベル0から10まで変化させて、

点をメモリ上の順番に沿って線で繋いだ図

ヒルベルトソート

空間分割レベル0から10まで変化させて、

点をメモリ上の順番に沿って線で繋いだ図

空間充填曲線②

モートン オーダー　(Morton-Order, Z-order)

モートンキーの算出方法

モートンキーは、XYの位置情報を１ビットずつを交互に並べたものである

空間分割レベル２であり、空間数が16個ある場合の例が下記である

2進数表記

10進数表記

XY方向の位置情報を1ビットずつ交互に並べることによって、16個の空間を

Zを描くように辿ることができる

三次元空間の場合は、Z方向が加わるため、

ZYX ZYX ZYXとビットを並べることでモートンキーを算出することができる

モートンキーの計算をコードに起こしてみる

空間充填曲線①

空間充填曲線である、モートンオーダー・ヒルベルト曲線の紹介

モートン オーダー　(Morton-Order, Z-order)

  「Zを描くように空間を辿る曲線」

例：二次元の空間（0.0~10.0）を空間分割レベルを0から10まで

変化させ、モートン曲線で辿った場合

ヒルベルト曲線　(Hilbert Curve)

  「コを描くように空間を辿る曲線」

例：二次元の空間（0.0~10.0）を空間分割レベルを0から10まで

変化させ、ヒルベルト曲線で辿った場合