HBJモデル

HBJ_model
。
コンピュータサイエンス では、 Helman-Bader-JaJaモデル は、次のパラメータで定義された並列計算の簡潔なメッセージパッシングモデルです。 p { p}
はプロセッサの数です。 n { n}
問題のサイズです。 m { m}
ネットワークを介して送信されるパケット内のマシンワードの数です。 τ { tau}
待ち時間、またはプロセッサがネットワーク上で通信を開始するのにかかる時間です。 σ { sigma}
は、プロセッサが注入または受信できる帯域幅、つまりマシンワードあたりの時間です。 m { m}
ネットワークからのマシンワード。T c o m p
{ T_ {comp}}
は、プロセッサで費やされる最大の計算時間です。T c o m m
{ T_ {comm}}
ネットワーク上での通信に費やされた時間です。
このモデルは、 q { q}
プロセッサ、間のブロック順列 q { q}
プロセッサはかかります（（ τ+ σ m ）。 {（ tau + sigma m）}
時間、どこ m { m}
最大のブロックのサイズです。

一般的な並列アルゴリズムの分析
MPIライブラリに含まれる一般的な並列アルゴリズムの複雑さ：
ポイントツーポイント通信： O （（ τ+ σ m ）。 { O（ tau + sigma m）}
  割引 ： O （（ lo g（（ p ）。 （（ τ+ σ m ）。 ）。
{ O（log（p）（ tau + sigma m））}
  ブロードキャスト： O （（ lo g（（ p ）。 （（ τ+ σ m ）。 ）。
{ O（log（p）（ tau + sigma m））}
  並列プレフィックス： O （（ lo g（（ p
）。n p（（ τ+ σ m ）。 ）。
{ O（log（p）{n over p}（ tau + sigma m））}
  すべてに： O （（ p（（ τ+ σ m ）。 ）。 ）。 { O（p（ tau + sigma m）））}

 

参考文献
^ デビッドR.、ヘルマン; デビッドA.、ベイダー; JaJa、Joseph（1998）。「実験的研究によるランダム化並列ソートアルゴリズム」 （PDF）。Journal of Parallel andDistributedComputing。52：1–23 。
^ Bader、David A .; Jaja、Joseph（1996）。「動的データの再配布、中央値の検出、および選択のための実用的な並列アルゴリズム」。第10回IEEE国際並列処理シンポジウムの議事録：292–301。”