並列分散システムレポート1

並列分散システムレポート１
055717A:金城佑典
１マージソートのアルゴリズム
1.p台のプロセッサを準備
2.データをp個の領域に分割し、p台のプロセッサに割り当てる
3.プロセッサごとに割り当てられたデータ（１プロセッサあたり(n/p)個）をマージソート
4.プロセッサのデータを統合する（自分の番号+1のプロセッサから受け取ったデータと自分のデータをマージす
る）
5.手順3と4をlog(p)回繰り返す
２解析
1: n個の数をp個の領域に分けるのにnステップかかるとすると：
t_comp1=n
2: n/p個データを含むp個のパケットを各プロセッサに送る通信時間（ブロードキャストのとき）：
t_comm1=t_startup+t_data*n
（ここでt_startupは準備にかかる時間、t_dataはデータの転送にかかる時間）
3: n/p個のデータをマージソートする時間：
t_comm2=(n/p)log(n/p)
4: プロセッサのデータをまとめるのにかかる通信時間：
１番深い階層（log(p)）：t_startup+(n/p)*t_data
２番目に深い階層（log(p)-1）：t_startup+(2n/p)*t_data
……
最後までつづけると：log(p)*t_startup+(n/p+2n/p+…+n/2)*log(p)*t_data
5: 2と３はlog(p)回行われるので全体の計算時間は
：全体の計三時間＝データを各プロセッサに送る時間＋n/p個のデータをソートする時間＋プロセッサの
データをマージしていく時間通信時間
：tp=t_startup+t_data*n+(n/p)log(n/p)+log(p)*t_startup+(n/p+2n/p+…+n/2)*log(p)*t_data

Download Report