algorithm - ソート時のバタフライネットワーク

Question

C ++のRobert Sedwick Algorithmsで偶数マージソートを研究しています。

テキストの一部として、奇偶マージソートを使用してソートネットワークで並列ソートを実装する方法について言及しました。この文脈で、著者はバタフライネットワークについて言及しました

私の質問は、基本的にバタフライ ネットワークとは何か、なぜバタフライと呼ばれているのかということです。簡単な例で説明していただければ幸いです。

私はそれをグーグルで検索しましたが、例による簡単な説明が見つかりません。

Answer 1

バタフライ ネットワークは、ある種のソーティング ネットワークです。ソーティング ネットワークは、抽象的なネットワーク (データ フロー ネットワークなど) と見なすことも、電気回路として非常に具体的なものと見なすこともできます。

これらのネットワークは、入力ワイヤと出力ワイヤ、および1 つのワイヤから別のワイヤに着信値をルーティングする2 つのコンパレータマルチプレクサで構成されます。並列ソートの例です。

出典:ライプツィヒ大学

上の図では、入力は左側のセットにあり、出力は右側にあり、四角いボックスはコンパレーターです。アイデアは、各入力に 0 から 15 までの任意の値を置くことができ、それらはコンパレータ (入力値を検査し、別のワイヤにルーティングするか、同じワイヤに保持するかを決定する) によって出力にルーティングされるということです。すべて 0値は一番上の出力 (000) にルーティングされ、すべて 1 の値は 2 番目の出力 (001) にルーティングされます。

名前は、バタフライ グラフに由来するIMHO です。これは、たとえば高速フーリエ変換に表示されます。この種の交差するデータ フローは、バタフライに似ています。

出典：ウィキペディア

バタフライ ネットワークの最初の図を見ると、何度も繰り返されていることがわかります。