10

81 個の数字の部分的な並べ替えを行う高速な方法を探しています。理想的には、最小の 16 個の値を抽出しようとしています (16 個が完全に正しい順序である必要はありません)。

これのターゲットは、FPGA の専用ハードウェアです。そのため、結果として得られる実装の領域をできるだけ小さくしたいので、これは少し複雑な問題です。私は奇数-偶数マージソートアルゴリズムを見て実装しましたが、理想的には、私のニーズに対してより効率的なものを探しています (アルゴリズムの実装サイズが最小の 16 を与える部分ソートの場合、必ずしも順序ではなく、フルソート）

どんな提案でも大歓迎です

どうもありがとう

4

5 に答える 5

2

これは、ある種の信号処理カーネルのように聞こえます。デザインの正確なデータフローを知らずにこれに答えるのは難しいです。81要素のメモリを読み書きできる必要があるため、ソートを含むアルゴリズムにはアドレスデコードコストがかかります。このデータがメモリ内にある場合、このコストはすでに支払われていますが、別個のレジスタにある場合、それらへの書き込みにはエリアコストがかかります。

データがメモリ内にあると仮定すると、バブルソートを使用して、下位16の値を取得できます。以下のコードは2ポートメモリを想定していますが、一時レジスタを使用して書き込み値と書き込みインデックスを格納することにより、クロックサイクルごとに読み取りと書き込みを交互に行うことで、単一ポートで動作する可能性があります。これは、メモリ内に81個の要素しかないため、エリア効率が高くない場合があります。あるいは、ソースメモリは、一方が奇数のインデックスを持ち、もう一方が偶数のインデックスを持つ2つのシングルポートメモリとして実装できます。

// Not working code 
reg [15:0] inData [80:0]; // Must be two-port
reg [3:0]  iterCount = 0;
reg [6:0]  index = 0;
reg sorting;

always @(posedge clk)
  begin
  // Some condition to control execution
  if(sorting)
    begin

    if(index == 80)
      begin 

      // Stop after 16 iterations
      if(iterCount == 15)
        begin
        sorting <= 0;
        iterCount <= 0;
        end
      else
        begin
        iterCount <= iterCount+1;
        index <= 0;
        end
      end 
    else
      begin
      // If this is smaller than next item
      if(inData[index] < inData[index+1])
        begin
        // Swap with next item
        inData[index+1] <= inData[index];
        inData[index]   <= inData[index+1];
        end
      index <= index + 1;
      end
    end
  end

編集：レイテンシーに制約があり、1つのクロックドメインのみを許可し、パイプラインを作成する必要がある場合、問題はソーティングネットワークの選択とパイプラインへのマッピングに限定されます。リソース共有を使用できないため、ソーティングネットワークを指定すると領域が固定されます。

  • N = 81のソーティングネットワーク（Bitonic、Pairwiseなど）を選択します（簡単ではありません）
  • ソーティングネットワークを表す制御フローグラフを作成する
  • 出力66〜81に必要なノードを除くすべてのノードを削除します
  • 1つの比較ノードのレイテンシーLを決定します
  • ALAPスケジューリングを使用して、M * L <1/fであるクロックごとにMノードを割り当てます。
  • スケジューリングが成功した場合は、HDLでコーディングしてください
于 2012-11-11T20:48:13.550 に答える
0

最初に 16 個の値を持つ配列を設定します。そして、選択ソートのようなものを使用します:

  1. 最初の値が配列の最小値だと思います。
  2. 最初の要素である 2 番目の要素の値を比較して、それよりも小さい数値が見つかるまで続けます。
  3. それを新しい最小値として、それよりも低い数値が見つかるまで次の数値と比較します。
  4. 配列を完成させた場合、あなたが持っている数は最小であり、それを配列に保存してソース配列から除外し、ソリューション配列の 16 の位置を埋めるまで最初からやり直します。
于 2012-11-09T10:44:59.340 に答える