単純選択ソートとバイトニックソートを、C言語で記述し、高位合成した。
単純選択ソートのデータアクセスパタン
単純選択ソートは一つずつ最小値を選んでいくソーティング方法であるから、
インデックスiの最小値を探索してソーティングする場合
array[i]をリードし、そこからtex:{N-i}個の値をフェッチしながら最小値を選んでいく。
つまり、ターゲットのリードの数はN回、比較用に個のデータをフェッチし、最後に2回データの書き込み(値の交換)をする。
従って、1つの場所の値を決定するのに
の時間がかかる。
抜き出し(拡大図)
最小値を決定し、値を交換したときの波形。2サイクル連続で、交換する場所に対して書き込みをしている。
全体図
書き込みを起こすタイミングが、飛び飛びになっているのが分かる。その感覚は、データの量(=N)に比例していることが分かる。
バイトニックソートのアクセスパタン
ちなみにバイトニックソートは、配列から何度も値を呼び出して、何度も交換が発生する。C言語の記述を見れば、配列に対する読み込みと書き込みが何度も発生することは簡単に予想できる。
データ比較の拡大図
かなり近い感覚で、読み込みと書き込みが発生している。これはつまりデータの交換がかなりの頻度で発生していることに他ならない。
若干引いて見たときのデータアクセスパタン
単純選択ソートと比較すると、データアクセスの頻度は高く、メモリアクセスの頻度も高い。 しかし、バイトニックソートはアルゴリズムの特性上、並列にアクセスできることからデュアルポートメモリの特性を利用して2並列で交換処理をやっているように見える。 その分、単純選択ソートよりも高速に処理が行なえているように見える。
逆に言うと、バイトニックソートを単純に実装しただけでは、メモリアクセスを並列化することによる速度向上分(約2倍)しか効果が出ないということだ。 やはりハードウェアとして実行することを考えると、「並列演算」だけでなく「どのようにしてメモリアクセスを減らすか」ということを特に強く意識しないといけないということが分かる。
これは別にソフトウェアの実装についても同じことが言えるのだが、ハードウェアとして実装した場合それが目に見えて表れるので、普段忘れがちなことを思い出させてくれるというわけだ。
