Q&A
転置行列になってますか?
###質問内容
行列の回転(転置させてあと，行の順序の反転)をなるべく効率よく行いたいと考えているのですが，愚直な方法しか思い浮かびません，効率化の方法としてはどのようなものが考えられますでしょうか．
二回転置していて，一回目のほうはCPUとキャッシュを温めるために行っています．
現状のコードは次のようになっています．
C
1#include<stdio.h> 2#include <stdlib.h> 3#include <time.h> 4#include "clock.h" 5#define N 64 6#define data_t double 7 8 9 int src[N][N], dst[N][N]; 10 11void naive_rotate(int n, int src[n][n], int dst[n][n]) 12{ 13 int i, j; 14 for (i = 0; i < n; i++) 15 for (j = 0; j < n; j++) 16 dst[n-1-j][i] = src[i][j]; 17 return; 18} 19 20 21int main(void){ 22 double t; 23 srand((unsigned int)time(NULL)); 24 25 for(int i = 0; i < N; i++){ 26 for(int j = 0; j < N; j++){ 27 src[i][j] = rand() % 10; 28 //printf("%d ",src[i][j]); 29 } 30 //printf("\n"); 31 } 32 33 naive_rotate(N, src, dst); 34 35 start_counter(); 36 naive_rotate(N, src, dst); 37 t = get_counter(); 38 printf("%7.4f\n", t); 39 40 41 return 0; 42 43}
回答3件
0
一般論で言うと、不連続書込みのペナルティは不連続読み出しのペナルティよりも大きいので
C
1 for (i = 0; i < n; i++) 2 for (j = 0; j < n; j++) 3 dst[n-1-j][i] = src[i][j]; 4
は
C
1 for (j = 0; j < n; j++) 2 for (i = 0; i < n; i++) 3 dst[n-1-j][i] = src[i][j]; 4
とした方が速くなります。
ただし、コンパイラの最適化が、前者のコードを後者に変換して機械命令を生成している場合は性能は変わりません。
投稿2021/07/25 00:01
総合スコア24670
0
ベストアンサー
dst[n-1-j][i] = src[i][j]; だと転置ではなく回転です。
転置なら、det[j][i] = src[i][j]; です。
愚直なら、二重ループで、これは (n* n)回実行されます。
しかし次のようにするとループの回数が約半分になります。
C
1 for (i = 0; i < n; i++) 2 for (j = 0; j <= i; j++) { 3 dst[j][i] = src[i][j]; 4 dst[i][j] = src[j][i]; 5 }
代入回数は対角成分の分だけ増えますが、
ループ回数の減少のほうが大きく効いてくるでしょう。
配列をポインタに置き換えると高速になることがありますが、
最近のコンパイラは最適化でこれを勝手にやってくれたりします。
追記
回転なら愚直に (n*n)回ループするしかないでしょう。
ただ、dst[n-1-j][i] = src[i][j]; のように
dst を飛び飛びにして、src を連続にするよりも、
dst[i][j] = src[j][n-1-i]; のように
dst を連続にして、src を飛び飛びにするほうがほんのわずか速いかもしれません。
追記2
ポインタにしてみました。添字の計算で掛け算がなくなり速くなるかもしれません。
配列のアドレスより前を指すので規格違反ですが、そこはアクセスしません。
C
1void naive_rotate(int n, int src[n][n], int dst[n][n]) 2{ 3 int *dp = dst[0], *sp = src[0] - 1, m = n*n + 1; 4 for (int i = 0; i < n; i++) { 5 for (int j = 0; j < n; j++) 6 *dp++ = *(sp += n); 7 sp -= m; 8 } 9}
もちろん、コンパイル時には最適化オプションを指定してください。
追記3
今回はN=64~2048の2の冪乗の数で計測しようとしています．
それなら、可変長配列なんか使わず、次のようにすれば速くなるのではありませんか？
#define N 64 void naive_rotate(int n, int src[N][N], dst[N][N]) { for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) dst[i][j] = src[j][N-1-i]; }
引数の int n は使っていないので不要ですが、呼び出し元を変更しないで済む
ように残しています。
投稿2021/07/24 04:32
編集2021/07/25 13:48
総合スコア8224
説明が不十分でした，転置と反転の操作を行っているので，おっしゃる通り回転で，私が行いたいものも回転です．
回転についても転置でおっしゃっていただいた上記のような結果になりますでしょうか．
代入回数は変わらんけど条件判定は半分になるから多少は速くなりそう...
せやけどNが小さいとほとんど変わらんだろなー
O(N^2) を O(N)とかO(√N)とかにしたいんですよね?
計算量はできるだけ小さくはしたいですね
キャッシュなども考慮するのが良いのでしょうか．
ひとまず，教えていただいたように，srcの方で飛ばしてみます．
>>オーダの話。これ、オーダ下げられますか？オーダを下げることができるとは思えないです。データ列がランダムなので省く余地があると思えません。
遅延評価(つまりデータのメモリ上の位置と行列の各要素との対応についてはフラグで管理し、実際に行列演算をする段階になってから処理する)すれば処理によっては下げられるくらいでしょうか。
こんなチューニングしても差が出るかどうかわからないようなところをいじるより、他にいじるところがありそうです。
たとえば、二つの行列をそれぞれ回転させてから加算する場合、回転を二回行ってから加算するという順番だと、演算が回転、回転、加算の三回行われます。
これを、加算してから回転するという順番に変えると、演算が加算、回転の二回に抑えられます。
私が先ほどコメントした遅延評価というのは、実際には回転させず、回転したというフラグだけ付与します。
すると、回転、回転、加算の順番で行っても、回転にはほとんど処理時間がかからないため、実際の演算は加算のみの一回で済みます。
>>これ、オーダ下げられますか？オーダを下げることができるとは思えないです。データ列がランダムなので省く余地があると思えません。
私もオーダーを小さくできる方法は一切思い浮かばないのですが，もしあるのならばその方が好ましいです，くらいのニュアンスです．確かに完全にランダムなので，厳しいとは思います．
>>たとえば、二つの行列をそれぞれ回転させてから加算する場合、回転を二回行ってから加算するという順番だと、演算が回転、回転、加算の三回行われます。
考慮するのは回転までで，演算についての高速化は現状考量しないつもりです．ですが，確かにおっしゃる通りの方法で演算時には高速化を図ることが出来そうなので，参考にさせていただきます．
回転した後に他の演算を行わないのであれば、何のために回転するんでしょうか？
そういう課題ですか？
>>回転した後に他の演算を行わないのであれば、何のために回転するんでしょうか？
勉強する際に参考している資料でループの階層構造は階層をいじるなどによって高速化することが出来るといった内容があり，その箇所のやってみよう，みたいな感じのものです．回答例等が載っていないので質問させていただきました．
>>dst[i][j] = src[j][n-1-i]; のように
dst を連続にして、src を飛び飛びにするほうがほんのわずか速いかもしれません。
この方法で試してみたところ，Nを512にしたくらいから速度の差が出てきて，早くなっていました．
> ループの階層構造は階層をいじるなどによって高速化することが出来る
この目的を、資料に載っていた具体例とともに質問に書いておいてください。
そうすればそれに沿った回答がつく可能性があります。
この回答は階層を全く変えていません。
たとえば行列のサイズが限られている場合、次のような方法が考えられます。
1 2 3
4 5 6
この行列は二次元配列として表せますが、メモリ上の配置は 1 2 3 4 5 6 になります。
これを回転して次の形にした場合
4 1
5 2
6 3
メモリ上の配置は 4 1 5 2 6 3 になります。
つまり、1 2 3 4 5 6 を 4 1 5 2 6 3 に並べなおすためのテーブル 1 3 5 0 2 4 を用意すれば、元のデータの最初の要素である 1 はテーブルの最初の要素である 1 に従って 0 ベースの二番目の位置に移動し、2 はテーブルの二番目の要素である 3 に従って 4 番目の位置に移動し、のようにシーケンシャルに移動できます。
行列の大きさが決まっているならテーブルは予め作成しておいてもいいし、決まっていないなら同じサイズの行列の大量の回転が必要になる直前に一度作成してもいいでしょう。
階層構造をいじらなくてもいいなら、並列処理を採用することによって複数の CPU を同時に使用して処理時間を短くすることができるのではないかと思います。
>>この目的を、資料に載っていた具体例とともに質問に書いておいてください
行列の積を具体例にしていて，三つのループijkの順番を変更することで速度が変わるというものなのですが，そのパターンをすべて記載するのは見にくくなるのではないでしょうか．
また高速化は階層構造を変える制限は文意にはないと思うので，上記の回答でも問題ないと思われます．
文意はここに書いてないので知りません。
私が知りえるのは、あなたが書いたものだけです。
あと、テーブルの作成はプログラムでできるので、見にくくはならないでしょう。
3D-graphicsに用いるとかならNは高々4でしょう。
ならばfor-loopをほどいて代入式をN*N個書き並べるのが最速っちゃー最速かも。
>>あと、テーブルの作成はプログラムでできるので、見にくくはならないでしょう
そうなのですね，行ったことがないので少し調べてみます．
>>>3D-graphicsに用いるとかならNは高々4でしょう。
今回はN=64~2048の2の冪乗の数で計測しようとしています．
3D-graphicsはあまりサイズが大きくならないのですね
座標変換(拡大/縮小/回転/移動/etc.)の類なら点(x,y,z,t)に4x4行列を作用させることで実現できますから。
オーダを下げることができないならば、時間利益は大して得られません。機械語レベルでのコーディングをすれば若干の利益は得られるでしょうが、私ならば別の部分での利益を模索します。
私の提案したのは、コードの一部ではなく最終的なものを見てオーダーを下げる方法と、並列化して時間短縮することの二つです。
Nがかなり大きいならGPU-computing: cuBLAS あたりを使えばかなり高速になります > 並列化
解決になっていますが、複数の回答からどれを採用して、どのように解決したのですか？
どの程度高速化されたのですか？
飛び地にすつ添え字を変えてたり，一気に複数行みるなどして4倍程度高速になりました
0
専用命令とかコンパイラの最適化くらいですかね。
データ列がランダムならば、愚直な方法しか存在しません。
投稿2021/07/24 02:45
総合スコア4830
専用命令としたら，例えばどのような方針のモノが有効なのか，方針などあったりしますでしょうか．
専用命令は環境依存なので一概には言えません。そして、これはハードウェア的な方法なので、望ましい方法ではないです。（互換性が低下する等のデメリットを伴う）
そうなのですね，ご回答ありがとうございます．
あなたの回答
tips
プレビュー
