2

QTCビデオ コーデックを最適化して、適切なパフォーマンスで Raspberry Pi で動作するようにしようとしています。重要なボトルネックの 1 つは、範囲デコーダーで行われる 32 ビットの整数除算であり、デコード時間の 18% を考慮に入れます。デバイスの ARM プロセッサには明らかに整数除算命令がないため、これを簡単に最適化できると思います。分割は正確でなければなりません。

その特定の除算の被除数と除数は呼び出しごとに異なりますが、除数は常に 65536 より小さいことが知られています。逆除数の値のルックアップ テーブルを作成することを考えました。そのテーブルを使用すると、除算の代わりに乗算を使用できます。ルックアップ テーブルのサイズは 256 キビバイトになります。

質問

  1. その最適化を実行することは良い考えですか?
  2. ソフトウェア部門をなくすためのより良い方法はありますか?
  3. 除算がないようにアルゴリズムを実装する別の方法はありますか?
  4. 他のアイデア?
4

2 に答える 2

5

Raspberry Pi には、整数除算のソフトウェア エミュレーションよりも高速な倍精度 FP 除算を実行できる FP ユニットが含まれているという事実を利用することもできます。すべての整数除算を置き換えるa = b / ca = (double)b / (double)cうまくいきます。

于 2012-08-03T01:08:14.160 に答える
2

魔法の乗算 + LUT を使用する場合は、次のコードを使用します。

ランダム除数をテストする単純なテスター i.すべての i を徹底的にテストしたわけではありませんが、実行した短い期間は機能しました。テストした i の被除数 (j=0..2^32-1) のすべての 32 ビット状態で動作するようです。

実際には、i=2..64k-1 またはそのような範囲のルックアップ テーブルを事前計算します (値/0 が定義されていないため i=0 は機能せず、その魔法の乗数がすぐ外側にあるため i=1 は機能しません)。 32 ビット数の範囲)。次に、ルックアップ インデックスとして i を使用する方程式を使用して、魔法の乗数 'm' を取得します。必要に応じて変更し、私のスタイルを嫌いにならないでください。:P

#include <stdio.h>

int main() {
  unsigned int i,j,k,m,c;

  // compute j/i,
  // compute k = 2^32/i
  // instead of j/i, use m = ~(j*k)>>32
  srand(time(0));
  for(c=0;c<64;c++) {
    // generate random divisor i's for testing, then fully test every j
    i = rand()&0x7fff;      
    // precompute these and put into a lookup table, index on [i]
    k = (((__int64)1)<<32)/i;  
    for(j=0;j!=-1;j++) {
      // status updater so we know it's working...
      if(!(j&0xfffff)) { printf("%d : %d     \r", i, j); fflush(0); }    
      // multiply instead of divide!
      m = (((__int64)j*k)+k/2)>>32; 
      // rare fixup
      if(j - m*i >= i) m++;                          
      if(m != j/i) {
        // as long as this line doesn't print, we're ok
        printf("wrong : %d %d %d   got: %d  should be: %d\n", 
            i, j, k, m, j/i);    
      }
    }
  }
}
于 2012-08-03T00:32:15.520 に答える