16

2つの4x4行列を互いに乗算する関数の最適化されたCまたはアセンブラーの実装を見つけようとしています。プラットフォームは、ARM6またはARM7ベースのiPhoneまたはiPodです。

現在、私はかなり標準的なアプローチを使用しています-ほんの少しのループ展開です。

#define O（y、x）（y +（x << 2））

static inline void Matrix4x4MultiplyBy4x4（float * src1、float * src2、float * dest）
{{
    *（dest + O（0,0））=（*（src1 + O（0,0））* *（src2 + O（0,0）））+（*（src1 + O（0,1）） * *（src2 + O（1,0）））+（*（src1 + O（0,2））* *（src2 + O（2,0）））+（*（src1 + O（0,3） ））* *（src2 + O（3,0）））;
    *（dest + O（0,1））=（*（src1 + O（0,0））* *（src2 + O（0,1）））+（*（src1 + O（0,1）） * *（src2 + O（1,1）））+（*（src1 + O（0,2））* *（src2 + O（2,1）））+（*（src1 + O（0,3） ））* *（src2 + O（3,1）））;
    *（dest + O（0,2））=（*（src1 + O（0,0））* *（src2 + O（0,2）））+（*（src1 + O（0,1）） * *（src2 + O（1,2）））+（*（src1 + O（0,2））* *（src2 + O（2,2）））+（*（src1 + O（0,3） ））* *（src2 + O（3,2）））;
    *（dest + O（0,3））=（*（src1 + O（0,0））* *（src2 + O（0,3）））+（*（src1 + O（0,1）） * *（src2 + O（1,3）））+（*（src1 + O（0,2））* *（src2 + O（2,3）））+（*（src1 + O（0,3） ））* *（src2 + O（3,3）））;
    *（dest + O（1,0））=（*（src1 + O（1,0））* *（src2 + O（0,0）））+（*（src1 + O（1,1）） * *（src2 + O（1,0）））+（*（src1 + O（1,2））* *（src2 + O（2,0）））+（*（src1 + O（1,3） ））* *（src2 + O（3,0）））;
    *（dest + O（1,1））=（*（src1 + O（1,0））* *（src2 + O（0,1）））+（*（src1 + O（1,1）） * *（src2 + O（1,1）））+（*（src1 + O（1,2））* *（src2 + O（2,1）））+（*（src1 + O（1,3 ））* *（src2 + O（3,1）））;
    *（dest + O（1,2））=（*（src1 + O（1,0））* *（src2 + O（0,2）））+（*（src1 + O（1,1）） * *（src2 + O（1,2）））+（*（src1 + O（1,2））* *（src2 + O（2,2）））+（*（src1 + O（1,3 ））* *（src2 + O（3,2）））;
    *（dest + O（1,3））=（*（src1 + O（1,0））* *（src2 + O（0,3）））+（*（src1 + O（1,1）） * *（src2 + O（1,3）））+（*（src1 + O（1,2））* *（src2 + O（2,3）））+（*（src1 + O（1,3） ））* *（src2 + O（3,3）））;
    *（dest + O（2,0））=（*（src1 + O（2,0））* *（src2 + O（0,0）））+（*（src1 + O（2,1）） * *（src2 + O（1,0）））+（*（src1 + O（2,2））* *（src2 + O（2,0）））+（*（src1 + O（2,3） ））* *（src2 + O（3,0）））;
    *（dest + O（2,1））=（*（src1 + O（2,0））* *（src2 + O（0,1）））+（*（src1 + O（2,1）） * *（src2 + O（1,1）））+（*（src1 + O（2,2））* *（src2 + O（2,1）））+（*（src1 + O（2,3 ））* *（src2 + O（3,1）））;
    *（dest + O（2,2））=（*（src1 + O（2,0））* *（src2 + O（0,2）））+（*（src1 + O（2,1）） * *（src2 + O（1,2）））+（*（src1 + O（2,2））* *（src2 + O（2,2）））+（*（src1 + O（2,3 ））* *（src2 + O（3,2）））;
    *（dest + O（2,3））=（*（src1 + O（2,0））* *（src2 + O（0,3）））+（*（src1 + O（2,1）） * *（src2 + O（1,3）））+（*（src1 + O（2,2））* *（src2 + O（2,3）））+（*（src1 + O（2,3） ））* *（src2 + O（3,3）））;
    *（dest + O（3,0））=（*（src1 + O（3,0））* *（src2 + O（0,0）））+（*（src1 + O（3,1）） * *（src2 + O（1,0）））+（*（src1 + O（3,2））* *（src2 + O（2,0）））+（*（src1 + O（3,3） ））* *（src2 + O（3,0）））;
    *（dest + O（3,1））=（*（src1 + O（3,0））* *（src2 + O（0,1）））+（*（src1 + O（3,1）） * *（src2 + O（1,1）））+（*（src1 + O（3,2））* *（src2 + O（2,1）））+（*（src1 + O（3,3 ））* *（src2 + O（3,1）））;
    *（dest + O（3,2））=（*（src1 + O（3,0））* *（src2 + O（0,2）））+（*（src1 + O（3,1）） * *（src2 + O（1,2）））+（*（src1 + O（3,2））* *（src2 + O（2,2）））+（*（src1 + O（3,3 ））* *（src2 + O（3,2）））;
    *（dest + O（3,3））=（*（src1 + O（3,0））* *（src2 + O（0,3）））+（*（src1 + O（3,1）） * *（src2 + O（1,3）））+（*（src1 + O（3,2））* *（src2 + O（2,3）））+（*（src1 + O（3,3） ））* *（src2 + O（3,3）））;
};

Strassen-またはCoppersmith-Winogradアルゴリズムを使用することでメリットがありますか？

4

5 に答える 5

36

いいえ、Strassen または Coppersmith-Winograd アルゴリズムは、ここでは大きな違いはありません。彼らは、より大きなマトリックスに対してのみ利益を上げ始めます。

行列乗算が実際にボトルネックである場合は、NEON SIMD 命令を使用してアルゴリズムを書き直すことができます。ただし、ARMv6にはこの拡張機能がないため、これはARMv7にのみ役立ちます。

あなたの場合、コンパイルされたCコードよりも3倍高速になると思います。

編集: ここで ARM-NEON の優れた実装を見つけることができます: http://code.google.com/p/math-neon/

C コードの場合、コードを高速化するためにできることが 2 つあります。

  1. 関数をインライン化しないでください。行列の乗算は展開時にかなりの量のコードを生成しますが、ARM には非常に小さな命令キャッシュしかありません。CPU がコードを実行する代わりにキャッシュにロードすることに忙殺されるため、過度のインライン展開はコードを遅くする可能性があります。

  2. restrict キーワードを使用して、ソース ポインターと宛先ポインターがメモリ内で重複しないことをコンパイラに伝えます。現在、コンパイラは、結果が書き込まれるたびにメモリからすべてのソース値をリロードする必要があります。これは、ソースと宛先が重複するか、同じメモリを指している可能性があると想定する必要があるためです。

于 2009-11-04T14:21:20.920 に答える
20

ただのつまらない。なぜ人々はまだ自発的にコードを難読化するのだろうか? C はすでに読みにくいので、追加する必要はありません。

static inline void Matrix4x4MultiplyBy4x4 (float src1[4][4], float src2[4][4], float dest[4][4])
{
dest[0][0] = src1[0][0] * src2[0][0] + src1[0][1] * src2[1][0] + src1[0][2] * src2[2][0] + src1[0][3] * src2[3][0]; 
dest[0][1] = src1[0][0] * src2[0][1] + src1[0][1] * src2[1][1] + src1[0][2] * src2[2][1] + src1[0][3] * src2[3][1]; 
dest[0][2] = src1[0][0] * src2[0][2] + src1[0][1] * src2[1][2] + src1[0][2] * src2[2][2] + src1[0][3] * src2[3][2]; 
dest[0][3] = src1[0][0] * src2[0][3] + src1[0][1] * src2[1][3] + src1[0][2] * src2[2][3] + src1[0][3] * src2[3][3]; 
dest[1][0] = src1[1][0] * src2[0][0] + src1[1][1] * src2[1][0] + src1[1][2] * src2[2][0] + src1[1][3] * src2[3][0]; 
dest[1][1] = src1[1][0] * src2[0][1] + src1[1][1] * src2[1][1] + src1[1][2] * src2[2][1] + src1[1][3] * src2[3][1]; 
dest[1][2] = src1[1][0] * src2[0][2] + src1[1][1] * src2[1][2] + src1[1][2] * src2[2][2] + src1[1][3] * src2[3][2]; 
dest[1][3] = src1[1][0] * src2[0][3] + src1[1][1] * src2[1][3] + src1[1][2] * src2[2][3] + src1[1][3] * src2[3][3]; 
dest[2][0] = src1[2][0] * src2[0][0] + src1[2][1] * src2[1][0] + src1[2][2] * src2[2][0] + src1[2][3] * src2[3][0]; 
dest[2][1] = src1[2][0] * src2[0][1] + src1[2][1] * src2[1][1] + src1[2][2] * src2[2][1] + src1[2][3] * src2[3][1]; 
dest[2][2] = src1[2][0] * src2[0][2] + src1[2][1] * src2[1][2] + src1[2][2] * src2[2][2] + src1[2][3] * src2[3][2]; 
dest[2][3] = src1[2][0] * src2[0][3] + src1[2][1] * src2[1][3] + src1[2][2] * src2[2][3] + src1[2][3] * src2[3][3]; 
dest[3][0] = src1[3][0] * src2[0][0] + src1[3][1] * src2[1][0] + src1[3][2] * src2[2][0] + src1[3][3] * src2[3][0]; 
dest[3][1] = src1[3][0] * src2[0][1] + src1[3][1] * src2[1][1] + src1[3][2] * src2[2][1] + src1[3][3] * src2[3][1]; 
dest[3][2] = src1[3][0] * src2[0][2] + src1[3][1] * src2[1][2] + src1[3][2] * src2[2][2] + src1[3][3] * src2[3][2]; 
dest[3][3] = src1[3][0] * src2[0][3] + src1[3][1] * src2[1][3] + src1[3][2] * src2[2][3] + src1[3][3] * src2[3][3]; 
};
于 2009-11-04T15:35:34.683 に答える
3

アンロールされたコードが明示的なループ ベースのアプローチよりも高速であると確信していますか? 通常、コンパイラは最適化を実行する人間よりも優れていることに注意してください。

実際、一連の「無関係な」ステートメントからよりも、適切に作成されたループからコンパイラーが自動的に SIMD 命令を発行する可能性の方が高いと思います...

引数宣言で行列サイズを指定することもできます。次に、通常のブラケット構文を使用して要素にアクセスできます。これは、コンパイラが最適化を行うための良いヒントにもなります。

于 2009-11-04T15:08:59.380 に答える
2

これらは任意の行列ですか、それとも対称性がありますか? もしそうなら、それらの対称性はしばしばパフォーマンスの向上のために利用できます (例えば、回転行列)。

また、上記の fortran に同意し、いくつかのタイミング テストを実行して、手動で展開したコードが最適化コンパイラが作成できる速度よりも高速であることを確認します。少なくとも、コードを単純化できる場合があります。

ポール

于 2009-11-04T16:09:07.980 に答える
2

完全に展開された従来の製品は、おそらくかなり高速です。

行列が小さすぎて、明示的なインデックスと分割コードを使用した従来の形式で Strassen 乗算を管理するという耳障りな問題を克服できません。そのオーバーヘッドに対する最適化の効果が失われる可能性があります。

しかし、高速にしたい場合は、利用可能な場合は SIMD 命令を使用します。最近の ARM チップにそれらが搭載されていないとしたら、私は驚きます。そうであれば、行/列のすべての製品を 1 つの命令で管理できます。SIMD が 8 幅の場合、1 つの命令で2 つの行/列の乗算を管理できます。その命令を実行するようにオペランドを設定するには、いくつかのダンスが必要になる場合があります。SIMD 命令は行 (隣接する値) を簡単に取得できますが、列 (非連続) は取得しません。また、行/列の積の合計を計算するには、多少の労力がかかる場合があります。

于 2009-11-04T14:25:05.880 に答える