J73 j IEICE 1999 4 最近の更新履歴 Hideo Fujiwara J73 j IEICE 1999 4

選択問題を解く BSP モデ ル 及び BSP

^∗

モデ ル 上の並列アルゴ リズ ム

石水 隆

^†

藤原 暁宏

^††

井上美智子

^†

増澤 利光

^†

藤原 秀雄

^†

Parallel Algorithms for Selection on the BSP Model and the BSP

^∗

Model

Takashi ISHIMIZU

^†

, Akihiro FUJIWARA

^††

, Michiko INOUE

^†

,

Toshimitsu MASUZAWA

^†

, and Hideo FUJIWARA

^†

あら まし 本論文では ，BSP（ Bulk-Synchronous Parallel）モデル及び BSP^∗ モデ ル 上で 選択 問題を 解 く 並列アルゴ リズ ムを 提案する ．BSP モデル及び BSP^∗モデ ルは ，近年提案され た 並列計算モデ ル で あり，最 近 の 並 列 計 算に お い て 重 要と され て い る 通 信コ スト を ，同 期 周 期L，通信路帯域幅の 逆数 g，パケット サ イズ B といったパラ メータに より 表すことを 可能にし たモデ ル であ る．本論文では ，デ ータ数 n の選 択 問題に 対し ，p 個のプ ロセッサを 用いてBSP モデル上で任意の整数 d (1 <_{= d <}= log n) に対し 内部計算時間 O(ⁿ_p+d log p log log n+Llog p log log n

log d ^{)，通信時間 O(gn}p^+(gd+L)

log p log log n

log d ^{)，また，BSP∗モデル上で内部}

計算時間_O(ⁿ

p+ d log p log log n + Llog p log log n

log d )，通信時間 O(g(_pBⁿ + (ⁿ_p)¹⁷(log p)⁶⁷) + (gd + L)log p log log n log d ⁾

の並列アルゴ リズムを 提案する．

キーワード 並列アルゴ リズム，BSP モデル，選択問題，計算量

1. ま え が き

従来の並列アルゴ リズムに 関する研究は ，共有 メモ リ型並 列計算モデ ル では_PRAM（Parallel Random Access Machine^），分散 メモリ型並列計算モデ ルでは メッシュモデル，ハイパキューブ モデル等の特定のネッ ト ワーク構造をもつ並列計算モデ ルに 関する研究が 主 流であった ．初期の並列計算機の多くが ，低ビ ット の 並列処理専用に 開発され たプ ロセッサを 使って，短い 周期で同期をとりながら処理を行うものであったため， これ ら の 並列 計 算モデ ル で も₁命令ご と の 同 期が 仮 定され ることが 多か った ．また，初期の並列計算機で は ，プ ロセッサの演算能力が 低か ったこともあり，プ ロセッサ内部の演算に 比べて，プ ロセッサ間の通信は それほど 考慮が 必要とされず，上記の並列計算モデ ル においても，通信コ ストの表現には 重点が おかれてい

†奈良先端科学技術大学院大学情報科学研究科 ，生駒市

Graduate School of Information Science Nara Institute of Science and Technology, 8916–5 Takayama, Ikoma-shi, 630– 0101 Japan

††九州工業大学情報工学部電子情報工学科，飯塚市

Department of Computer Science and Electronics, Kyushu Institute of Technology, 680–4 Kawazu, Iizuka-shi, 820–8502 Japan

なか った ．

し かし ながら ，プ ロセッサ能力の向上に 伴い，プ ロ セッサ間の通信コ ストがプ ロセッサ内部の演算コ スト と と もに ，並 列 計 算の コ スト に おけ る 重 要な 要 素と なってきた ．また ，同時に 多くのプ ロセッサが 大部分 の処理を他のプ ロセッサと 同期せずに 処理を行う非同 期処理も主流となってきた ．これらの特徴をもつ最近 の並列計算機に 対し ては ，_PRAMを 代表と する従来 の並列計算モデ ルでは ，アルゴ リズムの評価を正確に 行うことが 困難であり，これらの特徴に 対応し た新し い並列計算モデ ルが 望まれ ていた ．

本論文では上記の要求に 対応し た並列計算モデ ルで あ る_BSP（Bulk-Synchronous Parallel^{）モデ ル}[9]^， 及び その 拡張モデ ルであ る_BSP^∗モデル_[2]を 使用し てアルゴ リズムの提案を行う．_BSPモデルは_Valiant により提案され た並列計算モデ ルであり，通信コ スト を同期周期，通信命令実行時間を表す_L，_gという二 つの パラ メータに より 表すこ とが 可能に なって いる ． また同期機構を仮定することに より，非常に 緩い同期 の処理に対応可能なモデルである．_BSP^∗モデルでは ， 通信パケット サ イズを 表すパラ メータ_B を 導入する ことにより，より実際に 即し たアルゴ リズムの計算量

D– Vol. J82–D– No. 4 pp. 533–542 1999 4 533

の検証を可能にし ている．

本論文では，これらのモデル上で選択問題を解く並列 アルゴ リズムの提案を行う．選択問題とは，全順序関係 をもつ_n個のデ ータの集合_Sと自然数_{k (1 <= k <= n)} が 与えられたときに ，_Sの中から_k番目に小さい要素 を求める問題であり，多くのアプ リケーシ ョンにおい て ，部分問題とし て 利用され て いる基 本問題で あ る ． この 選択問題に 対し ては ，_O(n)時間の 最適逐次アル ゴ リズム_[8]が 知られている．

選 択 問 題に 対す る 並 列アルゴ リズ ムとし ては ，以 下のものが 知られている．_{Cole [3]}は_{EREW PRAM} 上でO(log n log^∗n)^{時間（ 注1），}_{log n log}ⁿ _∗n^{プ ロセッサ，} CRCW PRAM^上でO(^{log n log}_{log log n}^∗n)^時間，n log log n

log n log^∗n

プ ロ セッサで 選 択 問 題 を 解 く 最 適 加 速

（ 注_2）

な 並 列 ア ルゴ リズ ムを 示し た ．_BSPモデ ル 上では_Gerbessio- tis^ら[5]が 内 部 計 算 時 間_O(ⁿ

p ^{+ L log p)，通 信 時 間}

O(gⁿ

2 3^+δ

p ^{+ L log p)で停止し ，確率1 − O(n} 1−ρ₎

で解 を出力する_{p (1 <= p <= n}^2/3_+ζ)プロセッサの確率的並 列アルゴ リズムを示した．_ρ，_δ，_ζは0 < ζ < δ <¹/3^，

ρ > 1となる任意の 定数である．_BSP^∗モデ ル 上では B¨aumker^ら[1]^{がプ ロセッサ数}p = O(_logⁿ4_n)^，c^が 任 意の 定 数の と き _{B <=}

n

p に 対し て 内部 計算 時間 O(ⁿ_p+ L log p)^{，通信時間}O(_B^g

ⁿ_p+ (L + g) log p) となる確率 _{1 −} ¹

n^c の確率的並列アルゴ リズムを示し た ．以上の よ うに ，_BSPモデ ル ，及び_BSP^∗ モデ ル では ，選択問題を解く確率的なアルゴ リズムは 提案さ れ て い るが ，決 定 性アルゴ リズ ムは 提 案され て いな か った ．

本論文では選択問題を解く以下の二つの 決定性並列 アルゴ リズムを示す．

（₁）_BSP モ デル上 で内 部 計 算 時 間 _O(ⁿ

p

+ d log p log log n + Llog p log log n

log d ^{)，通信 時 間O(g} n p

+ (gd + L)log p log log n

log d ^{)のアルゴ リズム．}

（₂）_BSP^∗ モ デ ル 上 で 内 部 計 算 時 間 _O(ⁿ

p

+ d log p log log n + Llog p log log n

log d ^{)，通信時間O(g(}

n pB

+ (ⁿ_p)¹⁷(log p)⁶⁷) + (gd + L)log p log log n

log d ^{)のアルゴ リ}

ズム．

ただし_dは_{1 <= d <= log n}を満たす任意の整数であり， かつプ ロセッサ数_pは_{1 <= p <=} ⁿ

log n ^{である．（1）の}

アルゴ リズムの計算量は ，g = d = O(1)^{のとき内部}

計算時間，通信時間がともに_O(ⁿ

p+ L log p log log n) となり，プ ロセッサ数が 小さい 場合は ，最適加速なア ルゴ リズムとなる．（₂）のアルゴ リズムも，_{d = O(1)}， g <_{= B = O((p log p}ⁿ )⁶⁷) の場 合，内部計算時間，通信 時間が と もに _O(ⁿ

p + L log p log log n) ^{とな り，プ ロ} セッサ数が 小さい場合は ，最適加速なアルゴ リズムと なる．

2. 準 備

2. 1 BSPモデル及びBSP^∗モデ ル

2. 1. 1 定 義

BSP^（Bulk-Synchronous Parallel^{）モ デ ル}[9]^は Valiantに よって 提 案 され た 非 同 期 式 並 列 計 算 モデ ルであり，以下の構成要素からなる．

• 局所 メモリをもつ複数のプ ロセッサ（ 本論文中 ではプ ロセッサ数を_pとし ，各プ ロセッサを_{Pi(1 <=} i <_{= p)}^{で 表す ）}

• ^{プ ロセッサ間の}1^対1メッセージ 通信を行う完 全結合網

• プ ロセッサ間の同期を実現するための同期機構 BSPモデル上での並列アルゴ リズムは ，各プ ロセッ サが 実行するプ ログ ラムに より表され る．各プ ロセッ サが 実行するプ ログ ラムは スーパステップ の列からな る．各スーパステップ は 内部計算命令の列からなる内 部計算フェーズと ，送信命令，受信命令の列からなる 通信フェーズで 構成され ており，各プ ロセッサは スー パ ス テップ の 命 令を 非 同 期に 実 行す る ．また ，ス ー パステップ の命令を終了後，プ ロセッサ間でバリヤ同 期

（ 注_3）

をとり，次のスーパステップの実行に移る．メッ セージ の受信については ，各スーパステップ 中の通信 フェーズで送信された メッセージは同一のスーパステッ プ の通信で 受信され るが ，その メッセージはその次の スーパステップ 以降でし か 利用できないと 仮定する． BSPモデルは以下の二つのパラ メータにより，具体 的なネット ワーク構造や メッセージ 配送の仕組みを 抽 象化し ている．

（ 注₁）：log∗ n = min{i| log(i) n <_{= 2}}^{．こ こ で ，}log(i) n = log(log(i−1) n), log(1) n = log n^{で ある．}

（ 注₂）：並列アルゴ リズ ムのプ ロセッサ数と 時間計算量の積が 最速の逐 次アルゴ リズ ムの時 間計算量と漸近的に 等し いとき ，その並列アルゴ リ ズムは 最適加速な並 列アルゴ リズムで あるという．

（ 注₃）：バ リヤ同期とは ，協調し て動 作する多数のプ ロセ ッサの歩 調を 合わせ ることを目的とし た同期プ リミテ ィブ である．バ リヤ同期を 実行 し て同 期をと る場合 ，すべてのプ ロセッサが バ リヤに 到達するまでど の プ ロサッサも実行を 継続できず，封鎖され る．

BSP モデル及び BSP

• L^{：バ リヤ同期周期}

• g (<_{= L)}^：1個の 送信命令又は 受信命令の 実 行 に 必要な時間

BSPモデル上の並列アルゴ リズムの基本的命令の実 行時間について ，以下のように仮定され ている．

• ^{各プ ロセッサは}1^{単位時間に}1^{内部計算命令を} 局所 メモリにのみ基づいて 実行する．

• ^{メッセージ}1個の送信命令又は 受信命令の実行 は_g単位時間で 行われ る．ただし ，₁メッセージは₁ 語からなるものとし ，サ イズ₁の メッセージ と呼ぶ．

• あ る ス ー パ ス テップ に お い て ，すべ て のプ ロ セッサで 命令の実 行を 終了し てから _L 時間以内にバ リヤ同期がとられ ，次のスーパステップ の実行に移る． よって ，あるスーパステップにおいて ，各プ ロセッサ がたかだか _w個の 内部計算命令，たかだか_h個の送 信命令又は 受信命令を割り当てられた場合，その スー パステップ の実行にはO(w + gh + L)^{時間かかる．} 以降では 簡単のために ，各スーパステップ は内部計 算命令のみ，あるいは 送信命令及び 受信命令のみから なるとし ，内部計算命令のみからなるスーパ ステップ の 実 行 時 間を 内 部 計 算 時 間 ，送 信 命 令 及び 受 信 命 令 のみからなるスーパステップ の実行時間を通信時間と 呼ぶ ．

BSP^∗モデル[2]^はB¨aumker^{らによって提案された} BSPモデ ルの拡張モデ ルであり，_BSPモデ ルのパラ メータに 加えて以下のような通信パケット のサイズを 表すパラ メータをもつ．

• B (>_{= 1)}：通信パケット の最小サ イズ

この拡張は ，多くの並列計算機において ，メッセー ジがある特定のサ イズの通信パケット とし て伝達され るという事実に 基づいている．

また ，この 拡張に よる_BSPモデ ルから の 変更点は 以下のとおりである．

• 同じプ ロセッサに 対する_s語の メッセージをサ イズ_sの メッセージとし て送信又は 受信できる．

• ^{サ イズ} s の メッセージ の 送 信命 令 又は 受信 命 令の 実 行は _g⌈^s

B^⌉ 単 位 時間で 行われ る ．よって 各プ ロセッサが たか だか_w 個の内 部計算命令，各サ イズ s1, s2, . . . , sh^{であ るたかだか} h個の メッセージ の 送 信命令又は 受信命令からなるスーパステップ の実行に は ，_{O(w + g}



h i=1^⌈

si

B^{⌉ + L)時間かか る．}

2. 1. 2 _BSPモデ ル 及び_BSP^∗モデ ル 上の 基本ア ルゴ リズム

本 論 文 中で 提 案す る 選 択 問 題を 解 く 並 列アルゴ リ

ズ ムで は ，ブ ロード キャ スト 操作 ，接頭部 演算操作 ， ソーテ ィング 操作を 行 う_BSPモデ ル 上の 並列アルゴ リズ ムを 利用する ．各操作は_BSPモデ ル 及び_BSP^∗ モデ ル 上では以下のように定義され る．以下の定義で は 要素_a，各_ai，各_bi等はいずれ もサ イズ₁であ る とする．

［ 定義₁］（ブ ロード キャ スト 操作 ）ブロード キャスト 操作とは ，ある₁プ ロセッサが 保持する要素をすべて のプ ロセッサに 送信する操作である．

入力：値_a（プ ロセッサ_P1が 保持する．） 出力：すべてのプ ロセッサが 値_aを保持する．

［ 定義₂］（ 接頭部演算操作 ） 入 力：_n 個 の 要 素 列 (a1, a2, . . . , an)^．各 Pi (1 ^<₌ i ^<₌ p) ^が (a_⌈(i−1)ⁿ

p^{⌉+1, a⌈(i−1)n}p^⌉+2, . . . , a_⌈iⁿ

p^{⌉)を保持する．}

出力：各_{j (1 <= j <= n)}について，_{bj= a1◦a2◦· · ·◦aj} を満たす要素列_{(b1, b2}, · · · , bn)^．各Pi(1 <_{= i <= p)}^が (b_⌈(i−1)ⁿ

p^{⌉+1, b⌈(i−1)n}p^⌉+2, . . . , b_⌈iⁿ

p^{⌉)を保持する．}

［ 定義₃］（ ソーテ ィング 操作 ）ソーティング操作とは 要素を昇順に並べ替え る操作である．

入力：全順 序関係 をもつ _n 個 の要 素集合 A = {a1, a2, . . . , an}^．各 Pi (1 <_{= i <= p)} ^が (a_⌈(i−1)ⁿ

p^{⌉+1, a⌈(i−1)n}p^⌉+2, . . . , a_⌈iⁿ

p^{⌉)を保持する．}

出力：_Aのソート 列_{(b1, b2}, . . . , bn)^．各Pi (1 <_{= i <=} p)^が(b⌈(i−1)ⁿ_p⌉+1, b⌈(i−1)ⁿ_p⌉+2, . . . , b⌈iⁿ_p⌉)^を保持す る．

表₁にブ ロード キャスト操作，接頭部演算操作，ソー テ ィング 操作に 関する既知の結果を示す．以下では 内 部計算時間，通信時間をそれぞれ_TI，_TC と表す．

BSP^{モデ ルで 計算量が} f (n, p, g, L)^{で あ るアルゴ} リズムは ，_BSP^∗モデ ル 上で 同じ 計算量f (n, p, g, L)

表1 BSP モデル上の基本操作に対する計算量 Table 1 The complexities for basic operations on the

BSP model.

操作 時間計算量 プ ロセ ッサ数 文献

ブ ロード キャ スト

TC : O((gd + L)^{log p}_{log d}^{) p [9]} TI : O((d + L)^{log p}_{log d}^{+ n}p ) ^p 接頭部演算

TC : O((gd + L)^{log p}_{log d}^{) 1 <}= p <= n [9]

TI : O(^{n log n}p ^{+ L}_{log n}^{log n} p

) p

ソーテ ィング

TC : O((gⁿp + L)_{log n}^{log n} p

) 1 <_{= p <= n} [6]

TI^{： 内部計算時間，}TC^{：通信時間} d^：1 <_{= d <= p}^{の任意の定数}

で 動作することが 可能である，すなわち，_BSP

∗

モデ ルにも表₁の結果が 適用できる．

また，表₁中の_Goodrichのソーティング アルゴ リ ズ ム_[6]は ，以下のよ うな 特性に より，_BSP^∗ モデ ル 上では 計算量が 改善され る．

Goodrichのソーテ ィングアルゴ リズム_[6]は ，各プ ロセッサは₁スーパ ステップ で_O(ⁿ

p^{) 個の 要素の 送}

信，及び 受信を行い，また ，_O(^{log n}

logⁿ_p^{)スーパステップ}

で終了するので ，_BSPモデル上では ，通信の計算量が O((gⁿ_p+ L)_log^{log n}n

p⁾

となっている．しかし ながら，この アルゴ リズムでは，各プロセッサが₁スーパステップで 送信する メッセージ の送信先，及び 受信する メッセー ジの送信元のプ ロセッサ数はたかだか₂₍ⁿ

p⁾ 1

7 である．

BSP^{∗モデ ルでは ，}1スーパ ステップ に おいて ，_d個 のプ ロセッサに _si 個（_{1 <= i <= d}）ずつ送信するため には ，_O(g



d i=1^⌈

si

B^{⌉ + L)}の通信時間しか必要とし な い．また，各プ ロセッサは ，₁スーパステップで_O(ⁿ

p⁾

個の要素の送受信を行うので ，



²⁽ⁿp⁾ 1 7

i=1 ^{si= O(n}p^)で

ある．し たが って ，このソーテ ィング アルゴ リズムの 1スーパステップ の通信時間は ，

O







^g







2(ⁿ_p)¹⁷



i=1



_si B









^{+ L}







= O



g



n pB ⁺

n p



¹₇

^

+ L



となる．

し たが って，以下の補題が 得られ る．

［ 補題₁］ソーテ ィング 操作は_BSP^∗モデ ル 上で TI: O

n log n

p ^{+ L}

log n logⁿ_p



TC: O



g



n pB ⁺

n p



¹₇

^

+ L



log n logⁿ_p



で 実行できる． 2. 2 選 択問 題

全順序関係をもつ要素集合_{A = {a1, a2}, . . . , an}^に 対し て ，関数_rank(ai, A) (1 <_{= i <= n)}^を

rank(ai, A) = |{a ∈ A|a <_{= a}i}|

と定義する．なお，簡単のために 任意のi, j (1 <_{= i <}

j <_{= n)}^{に ついて}ai= a| j とする．このと き，選択問 題は 以下のように 定義され る．

［ 定義₄］（ 選択問題 ） 選 択 問 題は 全 順 序 関 係を も つ n^{個の要素の集合}A^{と 整数}k (1 <_{= k <= n)}^{が 与えら} れ たと きに ，_Aの 中で_k 番目に 小さい 要素を 求め る 問題である．

入力：全順序関係をもつ_n個の 要素集合_{A = {a1,} a2, . . . , an}^{，及び ，整数}k (1 <_{= k <= n)}^．各Pi(1 <₌ i <_{= p)}^が {a_⌈(i−1)ⁿ

p^{⌉+1, a⌈(i−1)n}p^⌉+2, . . . , a_⌈iⁿ

p^{⌉}を ，}

Pp^がk^{を保持する．}

出力：ある一つのプ ロセッサがrank(a, A) = k^を 満たす要素_{a ∈ A}を出力する．

3. 選択問題を解くアルゴ リズ ム

3. 1 BSPモデル上のアルゴ リズ ム 3. 1. 1 アルゴ リズムの概要

本 ア ル ゴ リ ズ ム は _Vishkinに よって 提 案 さ れ た

EREW PRAM上の 並列アルゴ リズ ム_[10]をもとに

し ている．

選択問題はソーテ ィング 操作を用いて 解くことがで きるのは明らかである．しかし ，一般にソーティング 操 作の計算量は ，選択問題を解く計算量よりも大きくな る．_BSPモデ ル上の並列アルゴ リズムの場合も，表₁ のソ ーテ ィング アルゴ リズ ム_[6]に より，内部計算時 間_O(^{n log n}

p ^{+ L}

log n

logⁿ_p^{)，通信時間O((g} n p^{+ L)}

log n logⁿ_p⁾

でソート を行い，選択問題を解くことができるが ，こ の 計 算 量で は 選 択 問 題に 対し ては 最 適 加 速な アルゴ リ ズ ム と は な ら な い ．そ こ で 本 ア ルゴ リ ズ ム で は ， Viskin [10]のアルゴ リズムの方針を用いて ，_k番目で はあり得ない要素を以下に述べる操作により取り除き， 対象要素数を ⁿ

log n まで 減少させた後にソーテ ィング

操作を 行う．このことに より，ソーテ ィング のための 計算量を減らすことができ，最適加速なアルゴ リズム となる．

要素数を_nから ⁿ

log n に 減らすための操作は ，以下

のフェーズを 反復することによって行 う．まず，対象 要素の 中から 適当な 要素_mを 選び ，対象要素集合を mよりも小さいのものからなる集合，及び 大きいもの から な る集合に 分割する ．これ ら の₂集合に ついて ， ど ちらに _k 番目に 小さい 要 素が 含まれ て いるか を 計

算し ，_k番目の要素が 含まれていない方の集合を対象 要素から 除外する．また ，_mが_k 番目の 要素であれ ば それ を出力し て停止する．本アルゴ リズムでは ，各

BSP モデル及び BSP

プ ロセッサが 保持する各要素の各中央値を求め，その 各中央値の 中央値を 上記の 要素_mとし て 用いる ．こ こで ，要素集合_{A = {a1, a2}, . . . , an}^{の 中央値とは ，} rank(a, A) = ⌈ⁿ₂⌉^{を満たす要素}a ∈ A^{である．中央} 値の 中 央値を 分割の 基準とし て 利用することに より， 対象の要素数を₁回のフェーズで ¹

c^{（cはc > 1を満}

たす定数 ）以下にすることができるので ，後述のとお

りO(log log n)のフェーズの反復により，対象要素数

は ⁿ

log n ^{以下となる．}

3. 1. 2 分配 操作

BSPモデルは分散メモリ型の並列計算モデルである ので ，各プ ロセッサがど の要素を保持するかを考慮す る必要がある．本アルゴ リズムでは ，各プ ロセッサが 保持する要素数を均等にするために ，以下の分配操作 を使用する．

［ 定義₅］（ 分配操作 ）_n個の要素が各_{Pi(1 <= i <= p)} に _ni 個ず つ 保 持 され て い ると す る ．た だし ，_{n =}



p

j=1^njである．分配操作とは ，各プ ロセッサがたか だか_⌈ⁿ

p^{⌉個，少なくとも⌊} n

p^{⌋個の要素を保持するよ}

うに 要素を分配する操作である．

入 力：_n 要 素か ら な る 集 合 _A．各 _{Pi (1 <= i <= p)} は 互 い に 素 で あ る 集 合 _A の 部 分 集 合 _{Ai (|Ai| =} ni, A1∪ A2∪ . . . ∪ Ap= A)^{を保持する．}

出力：_n要素からなる集合_A．各_{Pi(1 <= i <= p)}は互 いに素である_Aの部分集合_A^′_i(A^′_1∪A^′_{2∪. . .∪A}^′_{p= A)} を保持する．ただし ，各_Aiは_⌊ⁿ

p^{⌋ <}= |A^′i^{| <}= ⌈ⁿp^⌉を

満たすものとする．

以下に 分配操作のアルゴ ルズムを示す．

［ 分配操作アルゴ リズム ］

（₁）接頭部演算操作を 用いて 各_{i (1 <= i <= p)}に 対し ，_si=



i

j=1^{njを計算する．}

（₂）各 _{Pi (1 <= i <= p)} が 保 持 す る _ni 個 の 要 素 か ら な る 要 素 集 合 を _{Ai = {asi−ni+1,} as_i−n_i+2, . . . , as_i}^{と する ．各} Pi^{は 保持する各要素}

aj(si−ni+1 <_{= j <= s}i)^を⌈(i^′−1)ⁿ_p⌉+1 <_{= j <= ⌈i}^{′ n}_p⌉ を満たす_Pi′ に 送信する．

（₃）各_{Pi(1 <= i <= p)}において（₂）で受信し た 要素の集合を_A^′_iとする．

［ 補題₂］_{nmax = max{n1, n2}, . . . , np}^{と する ．任} 意の 定 数_{d (1 <= d <= p)}に 対し て ，先の 分 配 操作は BSP^{モデ ル 上で ，}

TI: O

nmax+ (d + L)^{log p} log d



TC: O

gnmax+ (gd + L)^{log p} log d



で 実行できる．

（ 証明 ） _p要素の接頭部和演算操作は ，表₁のアルゴ リズム_[6]を用いて ，

TI: O

(d + L)^{log p} log d



, TC: O

(gd + L)^{log p} log d



で実行できる．また，（₂）において，各プロセッサはたか だか_nmax個の要素を送信し ，たかだか_⌈ⁿ

p^{⌉ (<}= n^max) 個の要素を受信する．よって通信時間は_O(gnmax+L) である．また要素の送信先の決定に 要する内部計算時 間は ，_{O(nmax+ L)}である． _✷

3. 1. 3 アルゴ リズムSelection

こ こで は_BSPモデ ル 上で 選 択 問 題を 解 く _{p (1 <=} p <_{= log n}ⁿ )プ ロ セッサの ア ルゴ リ ズ ムSelectionを 示す．

［ アルゴ リズムSelection］

（₁）各_{Pi(1 <= i <= p)}において，_{s := n}，_k^′_{:= k} とする（_sは ，アルゴ リズム中の対象要素数を，_k^′は 見つけ 出す要素のラン クを表す ）．

（₂）_{s >} ⁿ

log n ^{ならば ，s <}= log n^{n 以下のフェーズ}

（_2.1）∼（_2.6）を繰り返す．

（_2.1）各_{Pi(1 <= i <= p)}上において ，_Aiの中央値 mi^{を求める．}

（_2.2） プ ロセッサ全体により，中央値集合_{{m1, m2,} . . . , mp}をソ ートし ，中央値集合の中 央値（_mと す る ）を 計算する ．_mを 保持するプ ロセッサは ，_mを すべてのプ ロセッサにブ ロード キャ スト する．

（_2.3）各_{Pi(1 <= i <= p)}上において ，_Aiの要素を 以下のような二つの 部分集合_A¹_i，_A²_i に 分割する．

A¹i = {x ∈ Ai|x < m}, A²i = {x ∈ Ai|x > m}

（_2.4）各_{Pi(1 <= i <= p)}上において ，_A¹_i のサイズ

|A¹_i|を計算する．次に ，プ ロセッサ全体により，その 和_s¹₌



p j=1^|A

1

j^{|を計算し ，s1 をすべてのプ ロセッ}

サにブ ロード キャ スト する．

（_2.5）各_{Pi (1 <= i <= p)} 上に おいて ，以下を 実行 する．

•^（k^′ < s¹+ 1 ^{の 場 合 ）}Ai := A¹_i^，s := s^{1 と} する．

•^（k^′> s¹+ 1^{の場合 ）}k^′:= k^′− (s¹+ 1)^{とし ，} Ai:= A²_i^，s := s − (s¹+ 1)^とする．

•^（k^′= s¹+ 1^{の場合 ）}P1^はm^{を出力し ，アル}

ゴ リズムを停止する．

（_2.6）各プ ロセッサが保持する要素_{Ai(1 <= i <= p)} に 対し ，分配操作を行う．分配操作後の各プ ロセッサ が 保持する要素を _Aiとする．

（₃）す べ て の プ ロ セッサ を 用 い て ，要 素 集 合 A1 ∪ A2∪ . . . ∪ Ap ^{を ソ ート し ，}k^′ 番 目 の 要 素 を 保持するプ ロセッサが その要素を出力する．

3. 1. 4 正当性の証明

アルゴ リズムが 停止すれば ，その出力が 選択問題の 解で あ ることは アルゴ リズ ムより 明らかで あ るので ， ここではアルゴ リズムの停止性のみを示す．このため に ，（₂）の繰返し 回数がたかだかO(log log n)^である ことを示す．

以下では（_2.1）から（_2.6）まで の₁回の 実行を₁ 反復フェーズと呼ぶ ．

［ 補題₃］Selectionの 各反復フェーズ 中の（_2.4）終 了時，¹

6s − 1 < s¹< ⁵₆s^{が 成り立つ．}

（ 証明 ） _Aを（₂）の各反復フェーズの開始時点の要 素集合_{A = A1∪ A2}∪ . . . ∪ Ap と する ．このと き ， s = |A|^である．

各 反 復 フェー ズ の（_2.4）終 了 時 の _s¹ に 対し て ， s¹ = rank(m, A) − 1で あ るので ，補 題を 示すに は

1

6s < rank(m, A) <⁵₆s + 1^{を示せば よい．} sの値により場合分けを行う．

（_i）_{s < 3p}のとき

m^は{m1, m2, . . . , mp}の中央値であるので ，_Aの 要 素の う ち_m 以 下の 要素は 少な くと も _⌈

p

2^{⌉ 個 存在}

する ．_{s < 3p}より，rank(m, A) >_{= ⌈}^p₂⌉ > ^s₆ ^{が 成り} 立つ．

同様に ，_mより大きい要素は 少な くとも_⌊^p

2^⌋個存

在する．し たが ってs − rank(m, A) >_{= ⌊}^p₂⌋ > ^s₆− 1 が 成り立つ．

（_ii）_{s >= 3p}のとき

m ^は {m1, m2, . . . , mp} の 中 央 値 で あ る の で ， {m1, m2, . . . , mp}^{の要素のうち}m^{以下の要素は}⌈^p₂⌉ 個存在する．また，各_{mi(1 <= i <= p)}は_Aiの中央値 であるので_Aiの要素のうち_mi以下の要素は_⌈¹

2^⌊ s p^⌋⌉

個存在する．したがって_Aの要素のうち_m以下の要素 は少なくとも_⌈^p

2^⌉⌈ 1 2^⌊

s

p^{⌋⌉個存在する．ここでs <}= 3p より_⌈^p

2^⌉⌈ 1 2^⌊

s p^{⌋⌉ >}

p 2⁽

s 2p ⁻

1 2^{) >}=^p2⁽

s 2p⁻

s 6p^{) =}

s 6 ^が

成り立つので ，rank(m, A) >^s₆ ^{が 成り立つ．} 同様に，_{{m1, m2}, . . . , mp}^{の要素のうち}m^以上の 要素は_⌊

p

2^{⌋ + 1}個存在すること，及び ，_{Bi(1 <= i <= p)}

の要素の うち_mi以上の要素は _⌊¹

2^⌊ s

p^{⌋⌋ + 1個存在す}

ることからs − rank(m, A) > ^s₆ − 1^{が 成り立つ．} 以上より ^s

6 < rank(m, A) < ^5s₆ + 1^となる． _✷

［ 補題₄］アルゴ リズ ムSelectionの（₂）の 反 復フ ェーズ 数はO(log log n)^である．

（ 証明 ） 補題₃より，第_j 番目の 反復フェーズ 開始 時点の 要素集合_Aの 要素数_sは _{s < n(}⁵

6⁾ j−1

とな る．よってO(log log n)^{回の反復により}s <_{= log n}^{n と}

なる． _✷

3. 1. 5 計 算 量

［ 定理₁］任 意の 整 数 _{d (1 <= d <= log n)}に 対し て ， アルゴ リズムSelectionは_BSPモデ ル 上で ，

TI: O

n

p+ d log p log log n + L

log p log log n log d

 

TC: O

gⁿ

p ^{+ (gd + L)}

log p log log n log d



で 選択問題を解く．

（ 証 明 ） ア ルゴ リズ ムの 各 ステップ の 計 算 量を 評 価 する．

（₁）は各_Piにおいて定数個の内部計算であるので ， TI: O(L)^{で実行できる．また，（}3^{）はたかだか} _{log n}ⁿ 個の要素のソーテ ィング 操作であり，表₁のソーテ ィ ング アルゴ リズム_[6]を用いると ，

TI: O



_n

log n^log n log n

p ^{+ L}

log_{log n}ⁿ log

n log n

p



= O

n

p^{+ L}

log_{p log n}ⁿ + log p log_{p log n}ⁿ



= O

n

p^{+ L log p}



TC: O



g

n log n

p ^{+ L}



× ^log

n log n

log

n log n

p



= O

gⁿ

p^{+ L log p}



で 実行できる．

し たが って以下では（₂）の計算量のみに ついて 検 証する ．まず₁反復フェーズの 計算量を 評価する（_s は 各反復フェーズ開始時点の要素数である ）．

（_2.1）の各プ ロセッサ上の中央値の計算は ，既知の 逐次アルゴ リズム_[8]を用いて内部計算時間_O(^s

p^{+ L)}

で 求められ る ．また ，（_2.3）のソ ーテ ィング 操作を 除

BSP モデル及び BSP

いたその他のステップ は ，前述のブ ロード キャ スト 操 作，接頭部和演算，分配操作，及び ，_O(^s

p^{+ L)時間}

の内部計算により実現され ているので ， TI: O

s

p^{+ (d + L)} log p log d



,

TC: O

g^s

p^{+ (gd + L)} log p log d



で 実行できる．

（_2.2）のソーテ ィング 操作は ，以下のよ うに実現す る．各プ ロセッサ一つず つの要素をすべてのプ ロセッ サを 使って 表₁のアルゴ リズム_[6]に よりソート する

と ，_{O(L log p)}の通信時間がかかることになり，効率

が 悪い．そこで ，最初に ，要素を_⌈^p

d^⌉

（ 注_4）

個のプ ロセッ サに 集め ，少ないプ ロセッサ数によりソート を行うこ とにより，通信時間を減ら す．具体的には ，以下のよ うな操作を行う．

（_2.3.1） 各_{Pi (1 <= i <= p)}は_miを_P⌈i d^⌉

に 送信 する．

（_2.3.2） _{Pi(1 <= i <=} ^p

d^{)を 用いて ，{m1, m2, . . . ,}

mp}^{をソート する．}

（_2.3.3） _{{m1, m2}, . . . , mp}の中央値を 保持するプ ロセッサが ，その中央値をブ ロード キャ スト する．

以上の 操作に より，（_2.3）の計算量は ，表 ₁のソ ー ティングアルゴ リズム_[6]を，要素数_p，プ ロセッサ数

⌈^p_d⌉で 実行し た計算量となるので ，

TI: O



p log p

⌈^p_d⌉ ^{+ L ×} log p log_⌈^pp d^⌉



= O

d log p + L^{log p} log d



TC: O



g ^p

⌈^p_d⌉^{+ L}



× ^{log p} log_⌈^pp d^⌉



= O

(gd + L)^{log p} log d



となる．

以上より（₂）の₁反復フェーズは TI: O

s

p+ d log p + L^{log p} log d



,

TC: O

g^s

p^{+ (gd + L)} log p log d



である．

以下で ，（₂）全体の計算量を考える．（₂）の_j回目 の反復フェーズの開始時点の_Aの要素数_sを_s^(j)と する．補題₃より，_s^(j)_{< (}⁵

6⁾ j−1_n

であり，また ，補 題₄より，（₂）はO(log log n)フェーズ繰り返され る ので ，（₂）の計算量は ，

TI: O



_{log log n}



j=1

s^(j)

p + d log p + L^{log p} log d

 ^

= O



_{log log n}



j=1

_

5 6



j−1_n

p + d log p + L^{log p} log d

 ^

= O

n

p+ d log p log log n + Llog p log log n log d



TC: O



_{log log n}



j=1

g^s

(j)

p ^{+ (gd + L)} log p log d

 ^

= O



_{log log n}



j=1

g

^

⁵

6



j−1_n

p^{+ (gd + L)} log p log d

 ^

= O

gⁿ

p^{+ (gd + L)}

log p log log n log d



となる．

仮 定 す る _{d <= log n} の 範 囲

（ 注_5）

に お い て は ， log log n >_{= log d} ^{で あ り，（}3）の ソ ート の 計 算 量 よ り（₂）の計算量の 方が 漸近的に 大きいので ，アルゴ リズム全体の計算量も上記の計算量となる． _✷

定 理₁ よ り，_selection は p log p <₌ L log log n^{n log d ，}

g = O(1)のとき内部計算時間，通信時間ともに_O(ⁿ

p⁾

となり，最適加速となることが 示され る． 3. 2 BSP^∗ モデ ル上のアルゴ リズ ム 3. 2. 1 アルゴ リズムの概要

BSP^∗ モデ ル 上で 選 択 問 題を 解 く 並 列ア ルゴ リズ ムSelection^∗は 前述のSelectionにおけ る分配操作を BSP^∗用に 改良し たアルゴ リズムである．

BSP^∗モデ ルでは 異なるプ ロセッサに それぞれ サ イ ズ₁の メッセ ージ を _s 個 送信す るのに _gs単 位時 間 要す るが ，同 一のプ ロセッサに サ イズ _s の メッセ ー ジ₁個の送 信は _g⌈^s

B^⌉時間で 実行で き る．すなわ ち， BSP^∗モデ ルではサ イズの小さい メッセージを多数の プ ロセッサに対し 送信または受信することは 非効率的 で あ る ．Selectionで 用いられ る分配 操作では 各プ ロ

（ 注₄）：_dはブ ロード キャ スト 演算等の_dと 同じ 値を用いる．

（ 注₅）：プ ロセッサ数が 多い場合でも，内部計算時間を_nの 対数以下に するために 仮定．

セッサは たかだか サ イズ₁の メッセ ージ を_⌈ⁿ

p^⌉個の

プ ロセッサから 受信することがある．

Selection^∗では 分配操作の代わりに 各プ ロセッサの 保持する要素数をある程度均等にする擬似分配操作を 用いることにより通信時間を改善する．

3. 2. 2 擬似分配操作

［ 定義₆］（ 擬似分配操作 ） _n 個の 要 素が 各 _{Pi (1 <=} i <_{= p)}^に ni 個ず つ保 持され て いると する ．ただし ， n =

^

^p_j=1njである．擬似分配操作とは，各プ ロセッ サがたかだか ¹

2 n p^{+ ⌈}

n

p^{⌉個，少なくとも1個の要素を}

保持するよ うに 要素を分配する操作である．

入 力：_n 要 素か ら な る 集 合 _A．各 _{Pi (1 <= i <= p)} は 互 い に 素 で あ る 集 合 _A の 部 分 集 合 _{Ai (|Ai| =} ni, A1∪ A2∪ . . . ∪ Ap= A)^{を保持する．}

出力：_n要素からなる集合_A．各_{Pi(1 <= i <= p)}は互 いに素である_Aの部分集合_A

′

i^(A′1^∪A′2^{∪. . .∪A′}p^{= A)}

を保持する．ただし ，各_A^′_iは_{1 <= |A}^′_{i| <=}¹

2 n p^{+ ⌈}

n p^⌉

を満たすものとする．

以下に_BSP^∗モデル上での擬似分配操作のアルゴ ル ズムを示す．

［ 擬似分配操作アルゴ リズム ］

（₁）接頭部演算操作を 用いて 各_{i (1 <= i <= p)}に 対し ，_si=



i

j=1^{njを計算する．}

（₂）各_{Pi(1 <= i <= p)}が 保持する_ni個の要素を {as_i−n_i+1, as_i−n_i+2, . . . , as_i}^{と する ．各}Pi ^{に おい}

て以下の操作を行う．

•^（ni ^>₌ ¹₂ⁿ_p ^{の 場 合 ）各} Pi は 保 持 す る 各 要 素 aj(si−ni+1 <_{= j <= s}i)^を⌈(i^′−1)ⁿ_p⌉+1 <_{= j <= ⌈i}^{′ n}_p⌉ を満たす_ai′ に 送信する．

•^（ni<¹₂ⁿ_p ^{の場合 ）各}Pi(1 <_{= i <= p)}^は保持す る各要素_{aj (si− ni+ 1 <= j <= si)}の うち，あ る_i^′ に 対し _{j = ⌈(i}^′_{− 1)}ⁿ

p^{⌉ + 1とな るaj をPi′ に 送信}

する．

（₃）各_Piにおいて ，（₂）で 受信し た要素と 未送 信の要素からなる集合を_A^′_iとする．

［ 補題₅］擬 似 分 配 操 作 ア ル ゴ リ ズ ム 実 行 後 ，各 Pi (1 <_{= i <= p)} ^{に お い て} 1 <_{= |A}^′_i| <₌ ¹₂ⁿ_p + ⌈ⁿ_p⌉ が 成り立つ．

（ 証明） 擬似分配操作において，各_Piは_{a⌈(i−1)n p^⌉+1,

a⌈(i−1)ⁿ_p⌉+2, . . . , a⌈iⁿ_p⌉}の部分集合を受信し ，このう ち_a⌈(i−1)n

p^{⌉+1は必ず受信する．また，未送信の要素数}

は ¹

2 n

p^{より少ない．したがって，1 <}= |A^{′i| <}=¹2 n p^+⌈

n p^⌉

が 成り立つ． _✷

［ 補題₆］_{nmax = max{n1, n2}, . . . , np}^{と する ．任} 意の定数_{d (1 <= d <= p)}に 対し て ，_BSP^∗モデル 上で の擬似分配操作の計算量は

TI: O

nmax+ (d + L)^{log p} log d



TC: O

g^nmax

B ^{+ (gd + L)} log p log d



である．

（ 証明 ）（₁）（，₃）は_BSPモデル上の分配操作と同じ で，_{TI: O(nmax+(d+L)}^{log p}

log d^{)，TC: O((gd+L)} log p log d⁾

である．

（₂）に おいて ，各_{Pi (1 <= i <= p)}は 連続し たプ ロ セッサに 対し て要素を送信する．_Piが 要素を送信する 連続し た_j個のプ ロセッサを _{Pi′, Pi′+1}, . . . , Pi^′+j−1

と す る ．_Pi は た か だ か _nmax 個 の 要 素 を 保 持し ， P_i′₊₁, P_i′₊₂, . . . , P_i′_+j−2^{へは少なくとも}⌊ⁿ_p⌋^個の要 素を 送 信 す る ．よって ，各 _Pi は た か だ か _nmax 個 の 要 素を 一つのプ ロセッサに _⌈ⁿ

p^{⌉個ず つ ，たかだか} nmax

⌊ⁿ_p⌋ ^{+ 2}プ ロセッサに 対し て送信する．また ，各_Pi は たか だ か _⌈ⁿ

p^⌉ 個の 要 素を たか だ か

⌈ⁿ_p⌉ 1 2ⁿp

+ 2^{プ ロ} セッサから 受信する．

よって

TI: O(nmax+ L)

TC: O



g



nmax



_n

p



^{+ 2 +}



_n

p



1 2 n p

+ 2

 _

n pB



+ L



= O

^

g

^

^nmax B ^{+ 1}



+ L

^

である． _✷

3. 2. 3 アルゴ リズムSelection^∗

アルゴ リズムSelectionの（_2.6）を以下の（_2.6）^′に 変更する．また ，（₃）でソートが 行われ る前には要素 は 均等に 分配され てなければ ならないので ，ダ ミー要 素を加え要素を均等にするために ，（₃）の直前に以下 の（_3.0）を挿入する．

（_2.6）^′ すべてのプ ロセッサが 保持する要素に対し て擬 似分配操作を行う．

（_3.0） 各_Piにおいて，保持する要素に³

2 n p log n^−|Ai|

個のダ ミー要素を加え る． 3. 2. 4 正当性の証明

アルゴ リズムSelection^∗には ，アルゴ リズムSelec- tionの 正 当 性の 証 明と 同 様にし て 以 下の 補 題 ₇，補 題₈が 成り立つ．