はじめに

別記事「はじめに」を参照してください。

この記事では、前々回説明した「ソーティングネットワーク(コアパッケージ)」を使ってバッチャー奇偶マージソート回路を構成する方法を紹介します。

バッチャー奇偶マージソートとは

バッチャー奇偶マージソート(Batcher's odd-even megesort) は Ken Batche(en: Ken Batcher) によって考案された、要素数ｎに対して、大きさO(n(log n)**2) かつ深さO((log n)**2)のソーティングネットワークです(出典:Wikipedia/Batcher_odd-even_mergesort)。

次図に８入力のバッチャー奇偶マージソートのソーティングネットワークの例を示します。

Fig.1 バッチャー奇偶マージソートのソーティングネットワーク例

以下に再帰呼び出しを使って Python で記述したバッチャー奇偶マージソートの実装例を示します(出典:Wikipedia/Batcher_odd-even_mergesort)。

oddeven_sort.py

def compare_and_swap(x, a, b):
    if x[a] > x[b]:
        x[a], x[b] = x[b], x[a]
 
def oddeven_merge(x, lo, hi, r):
    step = r * 2
    if step < hi - lo:
        oddeven_merge(x, lo, hi, step)
        oddeven_merge(x, lo + r, hi, step)
        for i in range(lo + r, hi - r, step):
            compare_and_swap(x, i, i + r)
    else:
        compare_and_swap(x, lo, lo + r)
 
def oddeven_merge_sort_range(x, lo, hi):
    if (hi - lo) >= 1:
        mid = lo + ((hi - lo) / 2)
        oddeven_merge_sort_range(x, lo, mid)
        oddeven_merge_sort_range(x, mid + 1, hi)
        oddeven_merge(x, lo, hi, 1)
 
def oddeven_merge_sort(x):
    oddeven_merge_sort_range(x, 0, len(x)-1)

バッチャーズ奇偶マージソートの VHDL 記述

ソーティングネットワークの VHDL 記述

New_Network 関数

New_Network 関数は、バッチャーズ奇偶マージソートのソーティングネットワークに対応した Sorting_Network.Param_Type(「ソーティングネットワーク(コアパッケージ)」参照)を生成します。 New_Network 関数は OddEven_MergeSort_Network パッケージにて定義しています。