講義ノート¶
MPI Programming Samples
http://www.gsic.titech.ac.jp/supercon/supercon2004/jp/mpi/index.html
第 1 回: シラバス (10.12.2010)¶
並列アルゴリズムを用いて並列プログラミングを行う.
新たな基本的な並列アルゴリズムを開発できること.
どのような程度でアルゴリズムがアップできる?
課題 (%50) 試験 (%50).
8 回目は中間試験を行う.
マルチコアプログラミング (12 コア).
ハードウェワがすごいが, ソフォとウェアは追いつかない状況もある.
GPGPU (Graphics Processing Unit) –> 高い並列処理できる.
Pthread を使って並列処理を行う.
参考書: マルチコア CPU のための並列プログラミング, 安田他, 秀和システム.
もともとは MainFrame
計算速度:
1. アーキテクチャの進化
2. 応用問題も飛躍的に複雑になる
3. 常に計算速度向上の要望
消費電力もあがる問題にも注目.
用語:
並列プログラミング (並列処理)(共有記憶型):
特殊な並列構文と共有変数などをもつ並列言語 (並列言語を開発)
コンパイラが並列処理用の実行可能コードを生成する (Intel)
指示子を用いて並列処理可能部分を指定し, 暗黙的にスレッドを割当てる (OpenMP)
スレッドを明示的に定義し各プロセッサに割り当てる
特徴:
メッセージ通信型に比べてプログラミングが簡単になる
ハードウェアの構成が困難である
階層構造による工夫がある
並列コンピュータ
メモリを共有記憶マルチプロセッサシステム
単一のメモリ空間
メッセージ通信マルチコンピュータ
分散共有メモリ
並列プログラミング (分散メモリプログラミング):
逐次プログラムにメッセージ通信用のライブラリルーチンを挿入する
...
並列コンピュータの種類:
SISD(Single Instruction stream-Single Data stream) (逐次処理)
MIMD(Multiple Instruction stream-Multiple Data stream)
SIMD(Single Insruction stream-Multiple Data stream) (応用範囲は広い)
MIMD (使わない)
GrayScale (グレースケール)
メッセージ通信マルチコンピュータのアーキテクチャ:
静的結合網
リンク
結合網の評価基準 (バンド幅, Latency, 直径など)
完全結合網
ライン/リング
二次元アレイ (メッシュ)
トーラス
ツリー網 (2 分木網)
ハイパーキューブ網 (d 次元の (2進) ハイパーキューブ網)
Two-dimensional array (mesh)
Three-dimensional hypercube
Four-dimensional hypercube
粒度が大きい (プロセス生成とプロセス間通信のコストが小さくなる.)
粒度が小さい (コストが大きくなる)
並列コンピュータのアーキテクチャに応じて, 最適な粒度を決定する必要がある!!
Amdahl’s law (最大速度向上率)
チーム作り (2 人)
第 2 回: メッセージ通信計算 (10.19.2010)¶
特別な並列処理むけのプログラミング
逐次言語を拡張する
プロセス: 処理の単位, 一つのプロセッサに複数のプロセスが割り当てられる.
静的プロセス.
動的プロセス:
1. ライブラリとシステムコールを用いる
2. 破壊も可能
3. オーバーヘッド
4. spawn(name_of_process);
基本送受信ルーチン (send, recv)
メッセージ通信ルーチン:
1. 同期式メッセージ通信
2. 同期式送信ルーチン
3. 同期式受信ルーチン
4. データ転送とプロセス間の同期の２つの役割
5. 三段階プロトコル
プログラムモデル:
1. SPMD (Single Program Multiple Data) (MPI: if 文を用いる)
2. MPMP (Multiple Program Multiple Data) (PVM)
非同期通信のためのメッセージバッファが必要となる
ブロッキングメッセージ通信
MPI_Send(buf, count, datatype, dest, tag, comm)
MPI_Recv(buf, count, datatype, src, tag, comm, status)
tag:
ノンブロッキングメッセージ通信
MPI_Isend(sendbuf, count, datatype, dest, tag, comm, request)
sendbuf (任意): 送信バッファの先頭アドレス
count (整数): メッセージのサイズ
datatype (整数): メッセージのデータタイプ
dest (整数): 宛先プロセスのアドレス (ランク)
tag (整数): メッセージタグ, 送信メッセージの種類を区別するときに使用, 通常は [0] でよい, 同じメッセージタグ番号同士で通信
comm (整数): コミュニケータを指定する
request (整数): 通信識別子. MPI_Waitall で使用.
MPI_Irecv(buf, count, datatype, src, tag, comm, request)
I*: Intermediate
reques (id)
MPI_Wait()
MPI_Test()
ブロードキャスト (broadcast)
マルチキャスト (multicast)
スキタ (scatter) (分配)
ギャザー (gather) (収集)
MPI_Isend(...) MPI_Wait() ２つとも必要となる.
MPI プログラミングは SPMD式 であるため.
SPMD/SIMD (Single Program/Instruction Multiple Data)
基本的には各プロセスは [同じことをやる] が [データが違う], 大規模なデータを分割し, 各部分について各プロセスが計算する.
全体データと局所データ, 全体番号と局所番号.
PE: Processing Element
第 3 回: 驚異的並列分散 (10.26.2010)¶
独立並列処理
驚異的並列処理 (embarassingly parallel)
OpenCL
16 コア
サーバが GPU ベース
800 コア以上のサーバ (100 万円)
マスタースレーブ (master slave) 構成が一般的 (静的プロセス)
画像の幾何学的変換 (近驚異的並列処理が可能)
- シフト
- スケーリング
- 回転
- クリッピング
PANY (任意のプロセッサ)
マスタは 各スレーブに先頭行を送っているが, クラス ID より計算できるので必要ない
欠点:
結果の転送は画像毎だと通信オーバーヘッドが大きくなる
改善方法:
グループ化することにより低減できる
並列処理における通信時間
t_comm = t_startup + m・t_data
t_startup: メッセージの作成 + 送信の開始 (一定)
t_comp = 2・(n^2/p)
マンデルブロー 集合 (漸化式を用いて簡単に求められる) の各要素がバラバラになる
マスターが仕事のプールを持っている
漸化式の計算は主な点としてマンデルブロー集合を作成
マンデルブロー (並列化):
静的タスク割当
動的タスク割当
data_tag であれば, 各プロセスは並列処理を行う
terminator_tag であれば, 各プロセスは終了となる
第 4 回: 分割と分割統治法 (11.02.2010)¶
マージソートと同じような考え方であり, 極基本的な考え方である.
マージソートを並列処理
分割法: 問題をいくつかの部分に単純に分割してそれぞの部分を別々に計算する.
分割戦略:
1. データ分割法
2. 機能分割
for(i = 0, x = 0; i < m; i++, x += s):
i = 0, x = 0;
i < m;
x += s;
Mastter は全ての個数を持っている
P_any どのような順番で値を受けても okay
Slave: recv(numbers, s, Pmaster);
Bcast: すべのデータを送る
Scatter: 一部のデータを送る
scatter <-> scatter reduce_add() <-> reduce_add()
逐次計算の時間計算量: n-1 回の加算 -> O(n)
- 並列計算::
- 段階 1-通信 段階 2-計算 段階 3-通信 段階 4-計算 全体
t(comm) = t(startup) + m・t(data)
t(startup) はほとんどかわらない
scatter を用いた場合, 起動時間の回数を減らせる可能性がある
逐次処理 O(n) と並列処理 O(n+m)
並列処理のスピードはすぐにわからない
2 分木の高さは log(p)
t(startup) = 0 にならないようにすること
t_comm1 = (n/2)t_data + (n/4)t_data
t_comm2 = t_data・log(p)
バケツソート (範囲を使ってソートする):
比較交換ではなくて分割に基づくソート
各バケツの中をソートする
連結する
O( n・log(n) ) O( (n/m) ・(log(n/m)) )
バケツソートを並列処理にする場合は, データ入力部分をいろいろ工夫しないと並列処理の速さを表せない.
中間試験: マージソートをどうやって並列処理できるのか? バケツソートより簡単に作れるはず
Aグループ: TSP 問題を並列処理で解く
報告書を書くこと
第 5 回¶
パイプライン技法
総和のルールを参照すること
周波数フィルタのパイプライン処理
ステージ1 ステージ2 ステージ3 ... ステージN
一つのプログラムを複数のパラメータで (複数回) を実行する
5.1 の図
p は process の数 m は instance の数
パイプラインソート (挿入法の並列)
python で easy_install
TYPE 2
素数発生: 2 以上の整数列を生成する 最初の数を素数として保存 保存した素数の倍数を整数列から削除 2 に戻る
エラトステネス (Eratosthenes) の振るい
逐次コード (for 文を使う)
並列コード (while 文を使う)
パイプラインプログラムによる素数発生:
- 1 ~ N までの素数をパイプラインで求めよ
- 最初の K 個
第 6 回¶
バリア
木 (Tree) 構造による実装 1. 到着段階 2. 開放段階 3. プロセスが n 個の時, O(logn) の時間複雑度
Master / Slave
FFT (バタフライ演算) 1st, 2nd, 3rd stage
P0, P1, P2,..., P7 は互いに平等であり
局所同期
デッドロックがおこりやすい ご注意すること デバッグが難しい データ並列計算 (異なるデータ処理, 画像処理, 各ピクセルを割り当てること) 画像処理 (独立処理できる, 同期を処理しながら, やる)
foreach (逐次処理) forall (並列処理, 同時に行わせる)
SPMD (Single Program Multiple Data)
プレフィックス総和計算
来週は休み 再来週は中間試験 (未来門がある, 第 7 章まで)
負荷平均化と終了検知
静的負荷平均化
NP Hard Problem
中央管理型 非中央管理型
中央管理型動的負荷平均化 (テトリス)
CPU にプロセスを割り当てる
優先付きキュー (ヒープ)
ランダムポーリングアルゴリズム 直線構造を利用した負荷平均化 分散終了検知アルゴリズム
活性, 不活性と親子関係
第 7 回¶
中間試験 + Final Presentation
締め切り: 期末試験の最終日
発表日: 決まっていない
報告書にいれる内容:
テーマ
調査の背景,目的, 目標
調査計画
調査結果
考察
議事録
最新の研究成果 (文献に参考すること)
HMM (Hidden Markov Model, 隠れマルコフモデル)
統計的な手法
TOP 500 http://www.top500.org/
GREEN 500 http://www.green500.org/
第 8 回¶
みんなに理解できるように説明する, スライドを作る.
グレースケール変換: 24 ビットの RGB を持つカラー画像を, 8 ビットのグレースケール画像に変換すれば, それだけ高速に処理できる. グレースケール変換は, RGB いずれか一つの要素値を抽出する方法や, RGB 各要素に一定の重みつけをして平均をとる NTSC 加重平均法などがある.
- Netpbm:
- PBM (Portable Bitmap formats)
- PPM (Portable Pixmap formats)
- PNM (Portable Greymap formats)
赤色の濃い部分や青色の濃い部分が, 同じような明るさになっていることがわかると思う.
第 9 回¶
第 10 回¶
第 11 回¶
第 12 回¶
第 13 回¶
第 14 回¶
第 15 回¶
第 16 回¶
金谷健一のここが変だよ日本人英語 (第 1 回)
国際会議, 国際論文誌
これよって “自己評価” の能力が高まり, 日本からの論文の選択率が向上し, 日本の研究が国際的により認められることを期待している.
レンジファインダ (Range Finder, カメラなどの距離測定器)
to obtain d -> for obtaining
[to + 動詞] は指定された目的を達成する意味である.
This is the method to do so. (これがそれをする方法だ)
I propose a new method for solving a nonlinear equation < 非線形方程式を解く (とすればその) ための新しい方法を提案する. >
I propose a new method to solve this problem. < この (解かなければならない) 問題を解くのに私は新しい方法を提案する. >
the 3D information -> 3D information
まだ説明していない事項には the をつけない.
in term of ... -> in view of its high accuracy and high speed of measurement
This project is infeasable in terms of profitability. < この計画は収支に関して実現性がない. >
profitability は [変数名] であり, その [値] はプラスでもマイナスでもよい (ここではマイナス). しかし This project is very feasible in view of its profitablity. < この計画はその高い収益性から非常に実現性が高い. > は常にプラスの実態を意味する.
improvements -> their improvements
improvements は 必ず何かの改良でなければならない. their は直前の methods を受ける.
have been proposed -> have been proposed in the past
長い主語の文が be ~ed で終わるのはスタイルがよくない. 時, 場所, 方法などを示す副詞句をいれるのがよい.
however -> However,
however は副詞で, and や but のように文をつなぐことができない. 前文をピリオドで終了し, However, ... とする.
equipment -> devices
like -> such as
like は口語. 文章では such as.
is required
However, they require special devices such as a laser light source.
On the other hand, 対比を示す
Another well known tool is the use of moire topology. (単に列挙する)
is useful for estimating
the shape of the object -> the object shape
there is no definitive solution ->
there has been no definitive solution yet.
no definitive solution has been found yet.
Meanwhile, under the ...
meanwhile は小説で話題を転換するのに用いられるが, 無意味な単語なので論文に用いないほうがよい.
The projector can -> such a projector can
onto the object
We use a liquid crystal projector as a tool for measuring the 3D object shape.
and the resolution is
文をつなぐ and の前にはカンマをいれる. しかし二つの文は liquid crystal projector
- command line audio player:
- . afplay . mpg123 . qtplay
qlmanage -p music.mp3
improving day by day
Today, the resolution has improved considerably / significantly がよい.
As a result, more and more people are using liquid crystal projectors, which do not require any special equipment.
to evaluate -> for computing / estimating
the current -> existing
a neighborhood of -> the neighborhood of
thus the intensity -> so the intensity
An extension -> Expansion
