3

ランレングスコーディングを最適化しようとしています。SIMDで実装することを考えていました。アルゴの作業に数時間を費やしましたが、あまり先に進むことができませんでした。試してみる価値はありますか？私はネオンに取り組んでいます。

ありがとう。

4

1 に答える 1

7

あなたの問題は、JPEGでエンコードされたACブロック係数のRLEにあると思います。

JPEG で使用される RLE のバリアントは非常に特殊です。8x8 ピクセルの各ブロックは、DCT で変換され、量子化されます。次に、DCT 出力 (64 係数) は、最初の DC 係数と 63 の AC 係数に分離されます。AC coefs の 8x8 ブロックは、ジグザグ パターンを使用して線形配列に変換され、RLE エンコードされます。

ウィキメディアの ZigZag (ファイル:JPEG_ZigZag.svg、Alex Khristov、PD)

通常、ZigZag は RLE 実行と組み合わされるため、RLE には非線形メモリ アクセスがあり、両方の機能を最適化する必要があります。

警告！JPEG の RLE は、要素がゼロの場合にのみ使用されます。ISO/IEC 10918-1 : 1993標準の F.1.2.2.1、 F.1.2.2.3、および図 F.2を確認してください。

いくつかの実装:

libjpeg-tubro (ホームページはlibjpeg-turbo.org ) があり、2010 年から 2011 年に Linaro によって ARM 用に最適化されたフォークがいくつかあります。

このフォークには最適化のリストがあります。

  • 10 - 「forward_DCT」の量子化コードの ARM NEON 最適化 (浮動小数点乗算に置き換えられた整数除算。...この最適化された関数は、元の C バリアントよりもほぼ 3 倍高速になりました - jcdctmgr.c - Siarhei Siamashka 2010-11-10
  • 9 - 「encode_one_block」の ARM アセンブリの最適化 ( 「encode_one_block」のARM アセンブリの最適化。元の C バリアントよりもほぼ 2 倍高速です。) - jchuff.c - Siarhei Siamashka 2010-11-10
  • 8 - 「rgb_ycc_convert」の ARM NEON 最適化バージョン - Siarhei Siamashka 2010-11-10
  • 7 - 「ycc_rgb_convert」の ARM NEON 最適化バージョン - Siarhei Siamashka 2010-11-10
  • 6 - 「convsamp」のマイナーな ARM NEON 最適化 - Siarhei Siamashka 2010-11-10
  • 5 - 「jpeg_fdct_ifast」の ARM NEON 最適化バージョン - Siarhei Siamashka 2010-11-10
  • 4 - 「jpeg_idct_ifast」の ARM NEON 最適化バージョン - Siarhei Siamashka 2010-11-10
  • 3 - 「jpeg_idct_4x4」の ARM NEON 最適化バージョン - Siarhei Siamashka 2010-11-10

リビジョン 9は、ブロックの AC コンポーネントと DC コンポーネントの両方をエンコードするjchuff.cfunction のファイルの ARM 最適化でしencode_one_blockただし、NEONを使用せずに行われます

/* Encode a single block's worth of coefficients */
LOCAL(boolean)   encode_one_block

実際、RLE は最適化されていませんでした。find_last_nonzero_indexただし、ZigZag と最後のゼロ係数検出は、ヘルパー関数の ARM アセンブリに実装されました 。( ruby​​ generatorを使用して生成されました) またはlinaro git で。デュアルイシューの Cortex-A8 が予定されていました。

* Find last nonzero coefficient and produce output in natural order,
* instructions are scheduled to make use of ARM Cortex-A8 dual-issue
* capability

これは、関数の対応する C コードです。

LOCAL(int)
find_last_nonzero_index (JCOEFPTR block, JCOEFPTR out)
{
  int tmp, i, n = 0;
  for (i = 1; i < DCTSIZE2; i++) {
    if ((tmp = block[jpeg_natural_order[i]]) != 0)
      n = i;
    out[i] = tmp;
}
return n;

ここには RLE 自体の ARM または NEON の最適化がありますが、この asm コードは RLE に役立ち、線形メモリ アクセス バージョンに変換すると思います (encode_one_blockの下ifdef __arm__):

  for (k = 2; k <= last_nonzero_index; k += 2) {
      innerloop(k);
  }

rマクロで使用されるinnerloopのは RLE カウンターです。

手動でコーディングされた ZigZag (Cortex-A8 用) を使用したこの線形 RLE は、Cortex-A9 の場合でも、元の C バージョンよりも高速になるはずです。Siarhei Siamashkaに感謝します！

PS: 現在のバージョンの libjpeg-turbo には、この RLE にアームの最適化がありません: encode_one_block、jchuff.c の 454 行目、rev929 - innerloop は のようにわずかに書き直されましkloopたが、RLE はまだ非線形の方法で行われています。それからジグザグに離れていません。

NEONについてのいくつかの考え

NEON には、それぞれ 64 ビット幅 (D0..D31; Anderson @ ELC 2011 によると、 5 ページ) の 32 個のレジスタのセットがあり、理論的には、64 個の 16 ビット係数を格納し、ZigZag+RLE を実装するために使用できます。まだ実装を探しています...

MPEG 規格にも同様のジグザグ + RLE があり、x86 および arm 用の SIMD 実装の取り組みがいくつかあります。x264devにブログ投稿があります。8x8 ジグザグx264_zigzag_scan_8x8_frameは、SSSE3 を使用する x86 用に実装されました。しかし、ARM の場合、x264には4x4 NEON ジグザグしかありません。

PS: 私と Jpeg の内部構造を知らない人向けです。Cardiff CM0340 の講義スライドに、JPEG コーディングの簡潔でわかりやすい紹介があります。

PPS (2013 年 2 月 18 日 13:30 更新): RLE エンコーディングを最適化するために、AC 係数の中央にあるゼロを事前スキャン検索してから、この事前計算されたデータを処理できます。一部の NEON reg では、ハーフバイトまたはビットとして保存することもできます

2 月 18 日更新: パッチ作成者は、コミット 9 のコメントが不正確であると述べています。このコードを libjpeg-turbo ではなく jpeg6b と比較すると、2 倍の改善がありました。彼は、(libjpeg-tubro のように) 63 までの展開は、この asm ソリューションとほぼ同じ速度であると述べています (一部のテストでは、他のテストではわずかに優れています)。

于 2013-02-17T12:50:10.977 に答える