2

割り当てのために、次のように記述された「スムーズな」関数のコードを最適化するように依頼されました。

平滑化関数は、ソース画像 src を入力として受け取り、平滑化された結果を宛先画像 dst に返します。実装の一部を次に示します。

void naive_smooth(int dim, pixel *src, pixel *dst) { 
  int i, j;
  for(i=0; i < dim; i++)
    for(j=0; j < dim; j++)
      dst[RIDX(i,j,dim)] = avg(dim, i, j, src); /* Smooth the (i,j)th pixel */
  return; }

struct ピクセルは、赤、緑、青の値 (整数) を格納します。関数 avg は、(i,j) 番目のピクセルの周囲のすべてのピクセルの平均を返します。あなたの仕事は、可能な限り高速に実行するためにスムーズ (および平均) を最適化することです。(注: 関数 avg はローカル関数であり、別の方法で Smooth を実装するためにそれを完全に取り除くことができます。) このコード (および avg の実装) はファイル kernels.c にあります。

これを最適化する方法についてアドバイスがあることを知っている人はいますか?

4

3 に答える 3

4

行列/画像を正方形のタイルに分割し、一度に 1 つのタイルを平滑化することにより、ループのループ タイリング/ループ ストリップ マイニングを実行できます。これにより、キャッシュの使用率が向上します。

現在のバージョンを検討してください。イメージを走査し、一度に 3 つの行にアクセスして、中央の行に書き込みます。

a[i-1][0], a[i-1][1], ..., a[i-1][dim-1]
a[i  ][0], a[i  ][1], ..., a[i  ][dim-1]
a[i+1][0], a[i+1][1], ..., a[i+1][dim-1]

画像の右端に到達するまでに、最初の列はおそらくキャッシュから破棄されます。しかし、アクセスが次のようになる次の行に移動すると、すぐに必要になります。

a[i  ][0], a[i  ][1], ..., a[i  ][dim-1]
a[i+1][0], a[i+1][1], ..., a[i+1][dim-1]
a[i+2][0], a[i+2][1], ..., a[i+2][dim-1]

代わりに、次のように画像をタイルで処理できます。

a[i  ][B], a[i  ][B+1], ..., a[i  ][B+B-1]
a[i+1][B], a[i+1][B+1], ..., a[i+1][B+B-1]
a[i+2][B], a[i+2][B+1], ..., a[i+2][B+B-1]

ここで、B はタイル サイズです。

または、より明確にするために写真を使用します。

000111222
000111222
000111222
333444555
333444555
333444555
666777888
666777888
666777888

ここでは、0 から 8 までの番号が付けられた 9 つのタイルに分割された 9x9 の画像があります。目標は、最初にタイル 0 のすべてのピクセルを滑らかにし、次にタイル 1 のすべてのピクセルを滑らかにし、次にすべてのピクセルを滑らかにするようにループを記述することです。タイル 2 のピクセルなど。順序は重要ではありません。各タイルを並行して実行することもできます。

もちろん、これは大きな画像や比較的大きなタイルの場合に有利です。たとえば、1 つまたは 2 つのキャッシュ ラインにまたがるタイル行から始めて、タイル サイズを試すことができます。

このアプローチの詳細については、ループ タイリングを確認してください。

とはいえ、コンパイラがこれを単独で行う必要があることに注意してください。

于 2012-12-05T22:00:26.310 に答える
2

コンパイラーの最適化が提供できるものに応じて、これは通常、ループの展開、明示的なベクトル化、ループのブロック、およびイメージが配置される方向に応じたループの交換などの標準の最適化の恩恵を受けます。これらはすべて、教科書またはコースノートに記載されている必要があります。そうでない場合は、オンラインで検索するキーワードです。

于 2012-12-05T21:54:35.217 に答える
1

画像の平滑化は、構造化グリッド アプリケーションの一般的な例です:構造化グリッド

あなたのアプリケーションは、ここで学ぶことができるループのアンローリングとループの並べ替え技術 (特にループ タイリング) の恩恵を受けるでしょう:最適化

構造化されたグリッドの計算を効率的に最適化することは、特に単一の時間ステップではそれほど簡単ではなく、人々はそれで博士号を取得 することに注意してください。ただし、ループ タイルの実装は面倒で、場合によっては逆効果になる可能性があります。任意のタイル次元でタイル コードをすばやく生成できるPlutoなどの多面体コンパイラを試してみることをお勧めします。適切なタイル ディメンションを選択することは、良好なパフォーマンスを達成するための基本であり、現在のアーキテクチャでは、長方形のタイルをプリフェッチするハードウェアが存在するため、より適切に機能します。キャッシュの最適化

于 2012-12-05T22:03:57.720 に答える