第 6 回 ソーティングネットワーク

本日の内容

• 6-1. 前回の復習
• 6-2. 並列計算
• 6-3. ソーティングネットワーク
• 6-4. O(nlog n) Sorting Network

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

6-1. 前回の復習

6-2. 並列計算

並列計算とは複数のプロセッサを使って問題を解く計算モデルです。 モデルには大きく分けて二つがあります。

1. PRAM(Parallel Random Access Machine) RAM とは通常のコンピュータと同様、メモリにランダムアクセスできる計算機 モデルです。 複数の RAM が共有メモリによりメッセージ交換を行いながら計算を行うのが PRAM です。
2. 回路 入力、出力の幅が定数長で、定数時間で一定の計算を行うゲート と呼びます。 このゲートの出力を他のゲートの入力に接続し、多段接続を行って最終的に答 えを出力します。 特に、 AND, OR, NOT などの論理回路がよく研究されてます。

並列計算ではいくつかの前提があります。 現実的なモデルではプロセッサ数はあらかじめ決まってますが、理論的な並列 計算ではプロセッサはいくつも使って良いです。 また、プロセッサの構成や接続は入力の長さ毎に変えて構いません (入力ごとに構成することは、 1 を出す回路、 0 を出す回路を並べるだけで問題が解けてし まうので許されない)。 なお、長さ n に対して回路がプログラムにより決定可能であることが必要で、 これを Uniformityと言います。

計算量は実行時間やメモリ使用量の他、プロセッサの数、接続段数等も考慮し ます。

NC (Nick's Class)

入力の長さ n に対して、 O(n^k) 個のプロセッサで O(log^k n) 段数で計算でき る問題のクラスを NC と言います。 NC ⊆ P は知られていますが、異なるかどうかはわかっていません。 P=NP 問題同様 NC も P と異なると信じられています。 なお、 k を 1 や 2 に固定したクラスを NC¹, NC² などと呼ぶこともあります。

6-3. ソーティングネットワーク

二入力二出力のゲートとして、数 x, y を入力した時、出力 p, q が x≤y なら p=x, q=y、一方 x>y なら p=y, q=x となるもの を Comparator と呼びます。 この Comparator ゲートのみを使って入力された数列をソートすることを考え ます。 これを実現するためのネットワークをソーティングネットワーク と呼びます。

簡単のため左側に入力列が縦に与えられるとし、横線でデータの流れを表しま す。 そして、 Comparator を二つの横線を結ぶ縦の線分で表します。

ソーティングネットワークの例

例6-1

3 入力のソーティングネットワークを示します。

Bubble Sort

逐次実行型の Bubble Sort とは次のようなプログラムでした。

#include <stdio.h>
#define N 5
int main(void){
  int a[5]={4,5,3,2,1};
  int i,j,temp;
  for(i=0;i<N;i++){
    for(j=1;j<N-i;j++){
      if(a[j-1]>a[j]){
	temp=a[j-1];
	a[j-1]=a[j];
	a[j]=temp;
      }
    }
  }
  return 0;
}

この中の if 文の部分は二つのデータを比較して交換するので、 Comparator にあたります。 したがって、この for 文が示す Comparator 通りにソーティングネットワー クを構築すれば、任意の n 入力に対して回路を作ることができます。

i=0 の時

a[0]>a[1], a[1]>a[2], ..., a[N-3]>a[N-2], a[N-2]>a[N-1]

i=1 の時

a[0]>a[1], a[1]>a[2], ..., a[N-3]>a[N-2]

...

i=N-1の時

a[0]>a[1]

Comparator の数は N-1+N-2+...+1=N(N-1)/2=O(n²), 段数は N-1+N-2=2N-3=O(n) となります。

マージソート

二つのソート列が存在する時、その二つを合成して一つのソート列とするのが マージソートです。 さらに、最初全てのデータを一つだけからなるソート列と見なし、それぞれを 合成して全体をソート列にするのもマージソートと呼ばれます。

ソート列 a₀,a₁,a₂,...,a_n-1 と b₀, b₁,...,b_n-1 に対して、マージソー トは次のように帰納的に行います。 ソート列の部分列はソート列になりますので、偶数番列: a₀,a₂,...,a_n-2 と b₀,b₁,...,b_n-2 同士をマージします。こ れを c₀,c₂,...,c_2n-2 と呼び直すことに します。 一方、奇数番列: a₁, a₃, ..., a_n-1 と b₁, b₃, ..., b_n-1 も同様にマージし c₁,c₃,...,c_2n-1 と呼ぶことにします。 ここで a_i が b_j<a_i<b_j+1 という関係になってい たとします。 j または j+1 と i は偶奇を共にします。

j と i が共に偶数

c₀, c₂, ..., c_k=b_j, c_k+2=a_i, ... となりますが、c_k より小さい要素は a₀ から a_i-1 と b₀ から b_j-1 までの i+j 個で す。 従って、この j+k 個が c₀ から c_k-1 までがこの a₀,...,a_i-1 と b₀,...,b_j-1 になります。 従って、 b_j+1=c_k+1 となります。

同様の議論で、全体で j 番目の大きさの要素は j が偶数の時は c_j-1 か c_j に、j が奇数の時は c_j か c_j+1 のどちらかに置かれることになります。 従って、この偶数番目、奇数番目ごとのソートの後、 c₁と c₂、c₃とc₄、... の順番を調整すれば全 体をソートできることになります。 つまり、n 要素(0番目から n-1 番目)のマージソートは次の ようにするとできます。

1. 偶数番目、奇数番目毎に n/2 要素のマージソートを行なう
2. 1 番目と 2 番目、 3 番目と 4 番目、...、n-3 番目と n-2 番目を Comparator でつなぎ順番を調整する

但し、 2 要素は単純に Comparator をつなぐだけでできます。 このようにして作った 8 要素のマージソートのソーティングネットワークを 示します。

n/2 個のソート列ふたつを n 個につなげるために必要な段数 s(n) は偶数、 奇数番目のソートは並列にできますので、s(n)=s(n/2)+1,s(2)=1 より、 s(n)=O(log n)。 また Comparator の個数 g(n)=2g(n/2)+(n-2)/2 より g(n)=2(2(g(n/4)+n/4-1)+n/2-1)=2²g(n/4)+n/2-2+n/2-1 =...= 2^{log n}+n/2log n + 2^{log n} =O(nlogn) これを 1 個ずつ、2個ずつ、4 個ずつ、...、n 個と log n 段重ねますので、 全体の段数と Comparator の個数はそれぞれ O( log²n) と O(n log ²n)。

アルゴリズムの複雑さ

以下にアルゴリズムの複雑さを示します。 AKS はこれからお話するアルゴリズムです。

Knuth の Lower Bound により、ゲート数の最小値は Ω(n log n) でし た。 また段数も Ω(log n) なので、 AKS は最適な回路になっています。 但し、定数が巨大(2¹⁰⁰)なので実用的な回路ではありません。

6-4. O(nlog n) Sorting Network

M. Ajitai, J. Komlós, E. Szemerédi "An O(n log n) Sorting Network", 15th STOC(1983)

論文のアイディア

1. Expander Graph
2. Expander Graph から定数段ネットワークで ε-halver が作れる
3. ε-halver から定数段で ε-nearsort が作れる
4. O(log n) 段の ε-nearsort で誤り無しの Sort 回路を作ること ができる。

Expander Graph

準備

グラフを G=(V,E) で表す。 但し、 V は頂点の集合を表す有限集合、 E は辺の集合を表し、 E ⊆V×V　である。 この時、 V の部分集合 A に対して、A の隣接頂点の集合を Γ(A)={ v∈V | (v,a)∈E , a∈A} で表す。 二部グラフ(bipartite Graph) G=(V₁,V₂,E) とは、頂点集合 V₁, V₂ でそれぞれ、 V₁ 内部、V₂ 内部に辺 が存在しない、つまり E ⊆ V₁×V₂ となる。

定義

bipartite graph (V₁, V₂, E) |V₁|=|V₂|=n が (λ, α, c) expander graph　とは、V= V₁, V₂ について、 G の最大次数は c かつ、 V の任意の部分集合 A に対して、 |A|≤ αn の時、|Γ(A)|≥λ|A| が成り立つことを言 う。

定理

1 より大きい任意の λ と 正の数 α がλα<1 を満たすとき、 (λ, α, c) expander graph が存在するような c を λ と α から定めることができる。

(2,1/3,2^100) expander graph を構成的に作れることが示されている。 一方、(2,1/3,8) が存在することが言えている。 また、頂点数 n に対して、 O(log n) の次数のランダムグラフも高い確率で Expander になるらしい。

ε-halver

定義

ε=10^-15 などとする時、 ε-halver とは次のよ うな性質をもつ回路です。

1. 定数段
2. m 入力で、 m/2 出力 LU, HU の二つ
3. 入力はほとんどエラー無しに小さいものと大きいものに二分され、それぞ れ LU と HU に分けられる
4. エラーが発生する確率は mε

なお、 m が小さくなるとエラーが発生しなくなることに注意

構成

((1-ε)/ε, ε, c) expander graph を用意します。 これを入力 m 入力に対して、上半分、下半分で m/2 個ずつに分割します。 この expander graph は次数が c なので、c 個の 1-factor に分割します。 1-factor の定義は「次数が 1 の全域部分グラフ」というものです。 次数が 1 とは他とは接続していない辺を意味しますので、すべての頂点を含 む独立辺の集合になります。 この c 個の 1-factor に対応させて Comparator を配置し、 c 段の並列回路 とします。

ε-near sort

エラー確率を ε-halver とは別に設定します (ε=10^-6など)。 m 入力に対して、 1 段目は m/2 ずつ、 2 段目は m/4 ずつとどんどん ε-halver を使用して、ひとつの部分の大きさが m10^-9 になるまで半分ずつに分割していきます。 この段数は log 10⁹ になります。 途中の ε-halver で一回もエラーが出ない確率は (1-εm/2) (1-εm/4)...(1-εw) となり、エラーが出る確率はこれを 1 から引いたものになります。 これを展開すると ε の一次の項は (m/2+m/4+...+w) となり、m/2 が 支配的になります。これは w の大きさの 10⁹ 倍になるので、 結 局エラーの確率は 10⁹wε=10^-6w 程度になりま す。 前半部分のエラーに関しても同様の議論でできます。

アルゴリズム

基本的には与えられた列に対してさまざまな分割を組み合わせて ε near sort をかけまくります。 小さい列に関しては ε-nearsort は実際にエラー無しでソートします。 3log n 段かけると ε-nearsort は定数段、O(n) プロセッサですの で、全体で O(log n) 段、 O(n log n) 個の Comparator になります。

参考文献

Sorting Network http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/networks/sortieren.htm