各種アルゴリズムの計算量はしばし重要な問題である。
またリアルタイムシステムや並列系の計算機(FPGAも含む)を考える場合、ワーストケースの検討も重要である。
例えばIn-placeアルゴリズムの中で最速に属するクイックソートのアルゴリズムは平均して O(n log n) の計算オーダーが期待できるが、単純な適用だとワーストケースでは O(n^2) である。
仮にソーティング専用の並列計算機構造を作る場合、ワーストケースにも耐えられるように構成する必要がある。
計算オーダーはしばしチューリングマシンのモデルを前提に語られて来た。
チューリングマシンはもともと有限の計算ユニットと、無限の長さのテープでの計算機モデルであるので、そのまま有限個数に固定された演算器と、解きたい問題に対して十分な量のメモリが存在する一般的な計算機の構成にそのまま対応づく。
この場合、演算に要する計算時間は、そのまま演算量のオーダーに対応づく。
しかしながら、並列計算機の構成そのものをアルゴリズムに対して設計できるケースでは話が少し変わってくる。
ここで、計算ユニットの方も、解きたい問題に対して十分な量を自由に割り当て可能として、答えを求めるのに必要な時間を考えてみる。
例えば n 個のデータの中から最大値を求めるアルゴリズムを考える。
言うまでもなく演算量は O(n) である。
ここで、計算ユニットが n より十分小さい有限個に固定されているいわゆる普通の計算機であれば、計算時間は n に対応づく。
しかしながら、比較器を n に対応づく個数割り当てることが出来れば、いわゆるトーナメント式に比較を行うことで 計算時間は log n に対応づく。
これは演算器が nに対応づく個数の並列計算機で単発の計算を行う場合は並列度の問題でもあり、アルゴリズムの前半では多くの演算器が稼動し、並列度は高く、後半では並列度が下がっていく。
また、n個のデータセットが m回入力され、最大値をm回求めるような計算を、スループット１で行うパイプライン計算機を設計する場合は、計算ユニットの個数にも関連する。
n log n に対応づく演算器の個数が必要であるが、この場合は演算ユニットはすべて100%稼動し、log n の時間の後に、毎サイクル結果が出力される(ただ残念ながらまだGPGPUなどはこのパイプライン演算での並列化は苦手なので、このあたりはまだまだFPGAなどの担当範囲と思われる)。
各種アルゴリズムに置いて計算量のオーダーが示されることは多い。しかしながら、計算ユニットを任意個アサインできる前提の場合の、最悪計算時間のオーダー、その際の計算ユニットのオーダー、その計算ユニット数に対する並列度(稼働率)のオーダー、などはあまり示されることが無い。
これらは専用計算機を設計する場合には従来までの非常に重要であったし、GPGPUなどの出現で「計算ユニットが n より十分小さい有限個に固定されている」という前提が崩れ始めている現状において非常に重要な課題と考える。
余談だが、少し先のソートの話をもう少し考察して見る。
最大値と最小値はトーナメント型の計算機構成で log n の計算時間で解ける。一方で、２番目とか３番目とかでは敗者復活戦が必要になり、演算時間が増えていき、中央値の探索で最悪値となる。
最大値と最小値以外の計算については、有名な「選択アルゴリズム」というのが存在する。
wikipedia によると、かのクヌース先生が下限としてにたようなことを記載されているようであるが、「この下限は k=2 のとき成り立つが、さらに大きな k ではもっと複雑な下限が存在する」とさらっと凄い事が書かれている。
選択的アルゴリズムもベースがクイックソートなので、一見すると計算量のワーストケースが O(n) ではなく O(n log n) になってしまうような気もしなくも無い。
が、「中央値の中央値」によって、O(n) の計算量で確実に中央一定比率の区画のピボットを選択が保証できるアルゴリズムが存在する。クイックソートもこのアルゴリズムとの併用で最悪時演算量を O(n log n) で保証できたりする。多くの従来型計算機のソフトウェア実装だとここまでやると逆に計算が遅くなるケースも多く、質の良い乱数でのピボット選択が重要になるようだが、系列系ではこの手の最悪値保証は重要である。
並列系では中央値の中央値は log n の計算時間であるにもかかわらず、nに対する固定比率で絞り込めるところが肝で、これを再帰的に行うことでオーダーを１ランク落とすことが出来る。
上記を加味すれば、並列系での中央値選択 は log n のオーダーの時間で達成できそうな気がする。
当然ながら、 log n のオーダーの時間でソーティングができる計算機構成が組めることになる。
データの数よりも演算器の数が多いということは最近では十分ありえる。
特に画像処理の場合、例えば 一定のフィルタサイズでメディアンフィルタとか、特徴量の上位数個の抜出とか、統計系の演算が発生するケースは十分あるが、GPUのコア数やFPGA化する場合の比較器の数とか、データ数より演算器が多く、このオーダーを達成できるケースは多々ある。
かつて、単調に増加していたCPUのクロック周波数は、ここ十数年4GHz前後でとどまり、代わりに計算並列度が飛躍的に向上している。
SIMDやマルチから始まり、メニーコアとなり、この先どこまで行くか分からない。
FPGAなども同様に多くの高度な演算を搭載できるようになってきたために、行き着くところは同じところに向かっている。
優れたアルゴリズムを考える場合、単に計算量や、消費メモリ量だけでなく、並列度という概念は改めて重要であるし、これらを扱える共通的な指標は今後まずます重要であると考える。
＜追記＞
クイックソート的な回路を考える元気は無いので、ひとまず log n の時間でn個のデータのソートが可能かどうかだけ考察して見た。
1. n(n-1)個の演算器を用意してすべてのデータ同士の比較を行う[1サイクル]
(同値のものは初期位置で優劣をつける)
2. 各nの大小較結果をトーナメント型で数え上げる [log n サイクル]
3. 数え上げた数を位置として結果メモリにストアする[1サイクル]
1が既に馬鹿ソート感をかもし出していたり、メモリアクセスの問題はまあおいておいて、理屈としては出来そうだ。
FPGAだと3の部分で巨大なセレクタが出来てしまい、1サイクルでは難しいが、セレクタを log n サイクルで組んでもオーダーは変わらない。中央値などのk番目要素が欲しいだけならただのマルチプレクサである。
後は 1を工夫して、log n 掛かって良いので、演算器数を圧縮できれば良いわけであるが、2と組み合わせて最適化が必要だろうなぁ。
実用的なところで効率の良いメディアンフィルタとか作れたら面白いかなと思う今日この頃。
画像処理の場合スループット１というケースが多いので、単純選択ソートだと n^2 のオーダーの比較器を並べることになるので、ある程度フィルタサイズが大きくなってくると工夫の余地が多数出てきそうな気がする。
コメント