none
サブルーチンの高速化

    質問

  • C#初心者です。御教授お願いします。
    現在、ある配列(仮にAA[i,j]とします)をひたすらループをまわして演算するという計算を行っています。
    メインのループ回数が膨大な量(10万回オーダ)になり、出来るだけ高速に演算を行うにはどうしたらいいものかと考えているところです

    コードとしては
    メイン関数
    do
    {
    サブルーチン
    }(while 条件判定文)

    サブルーチン内(例)
    {
      for(j; j++)
         for(i;i++)(コード省略)
    AA[i,j]=1/2*(AA[i-1,j]+AA[i,j+1])
    }

    教えて頂きたいことはmain関数内から何度もサブルーチンを繰り返し呼び出すのは実効的な遅延になるのでしょうか?
    出来ればプログラムの拡張性を考えて、サブルーチンを呼び出すというところを残しておきたいのですが。
    よろしくお願いします。長文乱文失礼いたしました。
    2009年11月18日 11:29

回答

  • >既にコメントが付いているように並列化するのが最善と思います。

    と思ってサンプルを書いてみましたが、この規模の計算だと並列化によるオーバーヘッドの方が大きくて、単純ループよりもむしろ遅くなってしまいました。

    特に今例で挙がっている演算は集計操作であるため、個々の演算を並列化して処理の効率化を狙っても、最終段の集計操作で帳消しになってしまうようです。
    • 回答としてマーク kenkou_t 2009年11月19日 8:15
    2009年11月19日 7:02
    モデレータ
  • for(j;j++)
      for(i;i++)
         AA[i,j]=c1*AA[i-1,j]+c2*AA[i+1,j]+c3*AA[i,j-1]+c4*AA[i,j+1];(c1~c4は定数)
    この式は正しいんですよね…AA[i-1,j]は、1回前のループで書き換えた直後の値を参照していていいんですよね?
    だとすると、このループは依存関係が厳しいですね。それでもLoop Unwindingは効きそう。
    • 回答としてマーク kenkou_t 2009年11月19日 15:32
    2009年11月19日 12:50
  • サンプルコードを読む限り、サブルーチンの呼び出しコストよりも、サブルーチン内の演算時間が圧倒的に思います。
    ちなみにC#の場合、実行時に最適化を行い、サブルーチン呼び出しをインライン展開することもあります。

    サブルーチン内を非同期実行 or マルチスレッド化すべきと思います。
    あとまだリリースされていませんが、次バージョンでは並列処理が強化されます。beta 2が出ていますので試してみるのもいいかもしれません。
    .NET Framework で並列プログラミング
    • 回答としてマーク kenkou_t 2009年11月18日 15:14
    2009年11月18日 14:00
  • パフォーマンスチューニングを行う場合は実際にかかった処理時間を測って比べるのが確実です。
    測らずに一般論で言うと
    対象の配列が小さい場合はメインのループが処理時間に影響してきますが、配列が大きく、サブルーチンが遅い場合はあまり影響がないと考えられます。
    一番内側のループ(最も多く実行される箇所)をチューニングするのが一番効果的です。

    ちなみに今回のコード例ですと、iとjのループを逆(iのループを外側、jのループを内側)にした方が速くなると思います。
    • 回答としてマーク kenkou_t 2009年11月18日 15:14
    2009年11月18日 14:17
  • 教えて頂きたいことはmain関数内から何度もサブルーチンを繰り返し呼び出すのは実効的な遅延になるのでしょうか?
    main 関数からサブルーチンを繰り返し読んだところで、順番に実行されるだけなのでスピードにも時間にも影響しません。


    なお、過去にこのようなスレッドがありました。参考になるとは言い切れませんが、目を通してみるのも良いかもしれません。

    C#で演算速度を早くする方法
    http://social.msdn.microsoft.com/Forums/ja-JP/csharpgeneralja/thread/307450c2-bdfe-497e-b93d-e4b8b9f71d49
    質問スレッドで解決した場合は、解決の参考になった投稿に対して「回答としてマーク」のボタンを押すことで、同じ問題に遭遇した別のユーザが役立つ投稿を見つけやすくなります。
    • 回答としてマーク kenkou_t 2009年11月18日 15:19
    2009年11月18日 14:25
    モデレータ
  • 早速のご回答ありがとうございます。forの順番によって演算速度が変わるというのははじめて知りました。
    お手間でなければもう少し教えて頂きたいのですが、上の質問では省略しましたが、実際のサブルーチン内は
    for(j;j++)
      for(i;i++)
         AA[i,j]=c1*AA[i-1,j]+c2*AA[i+1,j]+c3*AA[i,j-1]+c4*AA[i,j+1];(c1~c4は定数)

    となっております。この場合でもi,jの位置を交換する必要がありますか?
    そしてもう一つ質問なのですが、iとjでループ回数が異なるとき(iは2000程度,jは500程度)のときforの順番で演算速度に差は生じるのでしょうか?

    たくさん質問をしてしまいまして申し訳ありませんが、よろしくお願いします。

    変わらないですね。
    また呼び出しのオーバーヘッドをインライン化したところで多少は速くなっても体感速度は変わらないと思います。
    それよりも、配列からジェネリッククラスを使った処理に置き換えるとかした方が速くなるかも。
    ちょっと実験してみます。
    • 回答としてマーク kenkou_t 2009年11月19日 3:57
    2009年11月18日 15:29
    モデレータ
  • もう解決してスレも終息しているとは思いますが、後学のため、サブルーチンのオーバーヘッドについても調べてみました。

    class Program
    {
        static void Main(string[] args)
        {
            // 一千万回ループ
            const int RoopCount = 10000000;
    
            // 配列(for文)
            {
                int[] array = Enumerable.Range(1, RoopCount).ToArray();
                int total = 0;
                Stopwatch sw = new Stopwatch();
                sw.Start();
                for (int i = 0; i < RoopCount; i++)
                {
                    total += array[i] % 5 - 1;
                }
                sw.Stop();
                Console.WriteLine("{0} {1}", total, sw.ElapsedMilliseconds);
            }
    
            // 配列(for文)
            {
                int[] array = Enumerable.Range(1, RoopCount).ToArray();
                int total = 0;
                Stopwatch sw = new Stopwatch();
                sw.Start();
                for (int i = 0; i < RoopCount; i++)
                {
                    total += SubRutin(array[i]);
                }
                sw.Stop();
                Console.WriteLine("{0} {1}", total, sw.ElapsedMilliseconds);
            }
        }
    
        // サブルーチン
        private static int SubRutin(int value)
        {
            return value % 5 - 1;
        }
    }
    


    結果
    10000000 173
    10000000 325

    約二倍近いです。やはり一千万回もまわすと呼び出しのオーバーヘッドも無視できなくなりますね。

    もっともそんなにループするのは極めて特殊な事情ですし、
    仮にサブルーチンを数十万回呼び出してもオーバーヘッドは数十ミリ秒程度と思うので
    呼び出しのオーベーヘッドを気にするよりも、演算のアルゴリズムを検討した方がいいかと思います。

    • 回答としてマーク kenkou_t 2009年11月19日 3:56
    2009年11月19日 2:11
    モデレータ
  • >約二倍近いです。

    ひょっとして、Debug ビルドを実行していませんか?

    うちでは、Release ビルドを cmd.exe から実行して

    10000000 20
    10000000 23

    という結果で、2倍もの差はつきませんでした。
    • 回答としてマーク kenkou_t 2009年11月19日 8:18
    2009年11月19日 5:14
    モデレータ
  • > ちなみにサブルーチン内の二次元配列,定数c1~c4全てdouble型で定義しています。

    今度は配列の型を変えて調べてみました。
    ちなみに Visual Studio 2010 beta2 で リリースビルドで試しました。

    // 配列(int)
    {
        int[] array = Enumerable.Range(1, RoopCount).ToArray();
        int total = 0;
        Stopwatch sw = new Stopwatch();
        sw.Start();
        for (int i = 0; i < RoopCount; i++)
        {
            total += array[i] % 5 - 1;
        }
        sw.Stop();
        Console.WriteLine("{0} {1}", total, sw.ElapsedMilliseconds);
    }
    
    // 配列(double)
    {
        int[] array = Enumerable.Range(1, RoopCount).ToArray();
        double[] array2 = new double[RoopCount];
        for (int i = 0; i < RoopCount; i++)
        {
            array2[i] = (double)array[i];
        }
    
        double total = 0d;
        Stopwatch sw = new Stopwatch();
        sw.Start();
        for (int i = 0; i < RoopCount; i++)
        {
            total += array2[i] % 5d - 1d;
        }
        sw.Stop();
        Console.WriteLine("{0} {1}", total, sw.ElapsedMilliseconds);
    }
    
    // 配列(decimal)
    {
        int[] array = Enumerable.Range(1, RoopCount).ToArray();
        decimal[] array2 = new decimal[RoopCount];
        for (int i = 0; i < RoopCount; i++)
        {
            array2[i] = (decimal)array[i];
        }
    
        decimal total = 0m;
        Stopwatch sw = new Stopwatch();
        sw.Start();
        for (int i = 0; i < RoopCount; i++)
        {
            total += array2[i] % 5m - 1m;
        }
        sw.Stop();
        Console.WriteLine("{0} {1}", total, sw.ElapsedMilliseconds);
    }

    結果
    10000000 147
    10000000 274
    10000000 5454

    やっぱ double の方が少し遅い。decimal は速度的には論外ですね。(^ω^;

    • 回答としてマーク kenkou_t 2009年11月19日 15:44
    2009年11月19日 5:49
    モデレータ
  • >並列化(マルチスレッド?)しても性能が上がらないということが分かり

    早合点です。

    僕は「今現在あなたが取り組まれている演算の効率が、並列化しても向上することはない」とは、言っていません。

    「(ひらぽんさんが)例示されたサンプルコードを単純に(機械的に)並列化しただけでは性能が上がらなかった」と報告しただけです。

    データの持ち方や計算の手順を見直せば、「今現在あなたが取り組まれている演算」の効率が向上可能性はまだまだあります。

    ちなみに、「今現在あながた取り組まれている演算」の効率を高めるのに、どれくらいのコストが投入できますか?

    データの持ち方や計算の手順を入念に見直してでも、計算効率を高めたいですか?

    その場合、元の計算式がちょっとでも変更になると、↑の労力がその度に発生することになりますが、それでも行う価値が見出せるでしょうか?

    あるいは、(まじめな話で)「単にもっと計算速度の速いPCを購入する」という解決策もあると思います。

    また、労力を惜しまないで、ということなら GPGPU の利用なども検討する値があるのかもしれません。
    • 回答としてマーク kenkou_t 2009年11月20日 9:09
    2009年11月20日 1:53
    モデレータ
  • すみません、間違えました
    for(k=0;k<1000000;k++)
      for(j=1;j<500;j++)
        for(i=1;i<1000;i++)
           AA[i,j]=c1[i]*AA[i-1,j]+c2[i]*AA[i+1,j]+c3*AA[i,j-1]+c4*AA[i,j+1];(c1~c4は定数)

    AA[]は1001x501で定義していて、 AA の範囲外を参照することはありません
    そうでしたか。ではこの前提で思いつく方法を。

    C.Johnさんの指摘に近いですが、AA[]は1次元目と2次元目を入れ替えた方がいいです。メモリアクセスがシーケンシャルになり、アクセス効率が上がります。

    for(k=0;k<1000000;k++)
    for(j=1;j<500;j++)
    for(i=1;i<1000;i += 4){
    var i0 = i + 0;
    var i1 = i + 1;
    var i2 = i + 2;
    var i3 = i + 3;
    int a0, a1, a2;
    var b0 = AA[j,i1];
    var b1 = AA[j,i2];
    var b2 = AA[j,i3];
    var b3 = AA[j,i3+1];
    AA[j,i0]=a0=c1[i0]*AA[j,i0-1]+c2[i0]*b0+c3*AA[j-1,i0]+c4*AA[j+1,i0];
    AA[j,i1]=a1=c1[i1]*a0 +c2[i1]*b1+c3*AA[j-1,i1]+c4*AA[j+1,i1];
    AA[j,i2]=a2=c1[i2]*a1 +c2[i2]*b2+c3*AA[j-1,i2]+c4*AA[j+1,i2];
    AA[j,i3]= c1[i3]*a2 +c2[i3]*b3+c3*AA[j-1,i3]+c4*AA[j+1,i3];
    }
    適当にアンロールしてみました。…あってるのかなぁ
    # あんまり効率よさそうに見えないなぁ…。

    あとはunsafeを使うと配列の境界チェックを排除できるので、それでも高速化できそう。

    最後は、オーバーヘッドが大きいのでどこまで効くかわかりませんが、概要を。
    式はおおざっぱに A = 左 + 右 + 上 + 下 となっています。このうち右と下の加算は演算順序に依存関係がありません。
    そのため、 B = 右 + 下 をマルチスレッドで計算しておき、A = B + 左 + 上 を計算することができます。

    これ以上はC#よりもアセンブラを使った方がいいかと。SSE2とか。
    • 回答としてマーク kenkou_t 2009年11月21日 10:20
    2009年11月20日 14:48

すべての返信

  • サンプルコードを読む限り、サブルーチンの呼び出しコストよりも、サブルーチン内の演算時間が圧倒的に思います。
    ちなみにC#の場合、実行時に最適化を行い、サブルーチン呼び出しをインライン展開することもあります。

    サブルーチン内を非同期実行 or マルチスレッド化すべきと思います。
    あとまだリリースされていませんが、次バージョンでは並列処理が強化されます。beta 2が出ていますので試してみるのもいいかもしれません。
    .NET Framework で並列プログラミング
    • 回答としてマーク kenkou_t 2009年11月18日 15:14
    2009年11月18日 14:00
  • パフォーマンスチューニングを行う場合は実際にかかった処理時間を測って比べるのが確実です。
    測らずに一般論で言うと
    対象の配列が小さい場合はメインのループが処理時間に影響してきますが、配列が大きく、サブルーチンが遅い場合はあまり影響がないと考えられます。
    一番内側のループ(最も多く実行される箇所)をチューニングするのが一番効果的です。

    ちなみに今回のコード例ですと、iとjのループを逆(iのループを外側、jのループを内側)にした方が速くなると思います。
    • 回答としてマーク kenkou_t 2009年11月18日 15:14
    2009年11月18日 14:17
  • 教えて頂きたいことはmain関数内から何度もサブルーチンを繰り返し呼び出すのは実効的な遅延になるのでしょうか?
    main 関数からサブルーチンを繰り返し読んだところで、順番に実行されるだけなのでスピードにも時間にも影響しません。


    なお、過去にこのようなスレッドがありました。参考になるとは言い切れませんが、目を通してみるのも良いかもしれません。

    C#で演算速度を早くする方法
    http://social.msdn.microsoft.com/Forums/ja-JP/csharpgeneralja/thread/307450c2-bdfe-497e-b93d-e4b8b9f71d49
    質問スレッドで解決した場合は、解決の参考になった投稿に対して「回答としてマーク」のボタンを押すことで、同じ問題に遭遇した別のユーザが役立つ投稿を見つけやすくなります。
    • 回答としてマーク kenkou_t 2009年11月18日 15:19
    2009年11月18日 14:25
    モデレータ
  • 早速のご回答ありがとうございます。インライン展開については小耳に挟んだことがありました。
    もう少し詳しく教えて頂きたいのですが、強制的にインライン展開を行わせたいときに、何か特別なコードを記述する必要がありますか?
    それともコンパイル(ビルド?)の際にC#が勝手にインラインを行うのでしょうか?
    2009年11月18日 15:02
  • 早速のご回答ありがとうございます。forの順番によって演算速度が変わるというのははじめて知りました。
    お手間でなければもう少し教えて頂きたいのですが、上の質問では省略しましたが、実際のサブルーチン内は
    for(j;j++)
      for(i;i++)
         AA[i,j]=c1*AA[i-1,j]+c2*AA[i+1,j]+c3*AA[i,j-1]+c4*AA[i,j+1];(c1~c4は定数)

    となっております。この場合でもi,jの位置を交換する必要がありますか?
    そしてもう一つ質問なのですが、iとjでループ回数が異なるとき(iは2000程度,jは500程度)のときforの順番で演算速度に差は生じるのでしょうか?

    たくさん質問をしてしまいまして申し訳ありませんが、よろしくお願いします。
    2009年11月18日 15:14
  • 早速のご回答ありがとうございます。main 関数からサブルーチンを繰り返し読み込んでも演算の速度は変わらないのですね。拡張性を維持した状態でプログラムを組めることが分かり安心しました。
    2009年11月18日 15:19
  • 早速のご回答ありがとうございます。forの順番によって演算速度が変わるというのははじめて知りました。
    お手間でなければもう少し教えて頂きたいのですが、上の質問では省略しましたが、実際のサブルーチン内は
    for(j;j++)
      for(i;i++)
         AA[i,j]=c1*AA[i-1,j]+c2*AA[i+1,j]+c3*AA[i,j-1]+c4*AA[i,j+1];(c1~c4は定数)

    となっております。この場合でもi,jの位置を交換する必要がありますか?
    そしてもう一つ質問なのですが、iとjでループ回数が異なるとき(iは2000程度,jは500程度)のときforの順番で演算速度に差は生じるのでしょうか?

    たくさん質問をしてしまいまして申し訳ありませんが、よろしくお願いします。

    変わらないですね。
    また呼び出しのオーバーヘッドをインライン化したところで多少は速くなっても体感速度は変わらないと思います。
    それよりも、配列からジェネリッククラスを使った処理に置き換えるとかした方が速くなるかも。
    ちょっと実験してみます。
    • 回答としてマーク kenkou_t 2009年11月19日 3:57
    2009年11月18日 15:29
    モデレータ
  • ジェネリックと配列で比較してみました。

    class Program
    {
        static void Main(string[] args)
        {
            // 配列(for文)
            {
                int[] array = Enumerable.Range(1, 10000000).ToArray<int>();
                int total = 0;
                Stopwatch sw = new Stopwatch();
                sw.Start();
                for (int i = 0; i < 10000000; i++)
                {
                    total += array[i] % 5 - 1;
                }
                sw.Stop();
                Console.WriteLine("{0} {1}", total, sw.ElapsedMilliseconds);
            }
    
            // 配列(foreach文)
            {
                int[] array = Enumerable.Range(1, 10000000).ToArray<int>();
                int total = 0;
                Stopwatch sw = new Stopwatch();
                sw.Start();
                foreach (int i in array)
                {
                    total += i % 5 - 1;
                }
                sw.Stop();
                Console.WriteLine("{0} {1}", total, sw.ElapsedMilliseconds);
            }
    
            // ジェネリッククラス(foreach文)
            {
                List<int> list = Enumerable.Range(1, 10000000).ToList<int>();
                int total = 0;
                Stopwatch sw = new Stopwatch();
                sw.Start();
                foreach (int i in list)
                {
                    total += i % 5 - 1;
                }
                sw.Stop();
                Console.WriteLine("{0} {1}", total, sw.ElapsedMilliseconds);
            }
    
            // ジェネリッククラス(ForEach メソッド + ラムダ式)
            {
                List<int> list = Enumerable.Range(1, 10000000).ToList<int>();
                int total = 0;
                Stopwatch sw = new Stopwatch();
                sw.Start();
                list.ForEach(i => total += i % 5 - 1);
                sw.Stop();
                Console.WriteLine("{0} {1}", total, sw.ElapsedMilliseconds);
            }
        }
    }
    結果
    10000000 266
    10000000 277
    10000000 350
    10000000 301

    予想に反して、単純に配列を for 文で回すのが一番速かった・・・orz

    ちなみに

    > or(j;j++)
    >  for(i;i++)
    >     AA[i,j]=c1*AA[i-1,j]+c2*AA[i+1,j]+c3*AA[i,j-1]+c4*AA[i,j+1];(c1~c4は定数)

    この二次元配列に格納している型は何ですか?
    演算によって型変換とか起すようであれば、まだパフォーマンスを改善する余地はあるかも知れないけど・・・

    2009年11月18日 16:29
    モデレータ
  • もう解決してスレも終息しているとは思いますが、後学のため、サブルーチンのオーバーヘッドについても調べてみました。

    class Program
    {
        static void Main(string[] args)
        {
            // 一千万回ループ
            const int RoopCount = 10000000;
    
            // 配列(for文)
            {
                int[] array = Enumerable.Range(1, RoopCount).ToArray();
                int total = 0;
                Stopwatch sw = new Stopwatch();
                sw.Start();
                for (int i = 0; i < RoopCount; i++)
                {
                    total += array[i] % 5 - 1;
                }
                sw.Stop();
                Console.WriteLine("{0} {1}", total, sw.ElapsedMilliseconds);
            }
    
            // 配列(for文)
            {
                int[] array = Enumerable.Range(1, RoopCount).ToArray();
                int total = 0;
                Stopwatch sw = new Stopwatch();
                sw.Start();
                for (int i = 0; i < RoopCount; i++)
                {
                    total += SubRutin(array[i]);
                }
                sw.Stop();
                Console.WriteLine("{0} {1}", total, sw.ElapsedMilliseconds);
            }
        }
    
        // サブルーチン
        private static int SubRutin(int value)
        {
            return value % 5 - 1;
        }
    }
    


    結果
    10000000 173
    10000000 325

    約二倍近いです。やはり一千万回もまわすと呼び出しのオーバーヘッドも無視できなくなりますね。

    もっともそんなにループするのは極めて特殊な事情ですし、
    仮にサブルーチンを数十万回呼び出してもオーバーヘッドは数十ミリ秒程度と思うので
    呼び出しのオーベーヘッドを気にするよりも、演算のアルゴリズムを検討した方がいいかと思います。

    • 回答としてマーク kenkou_t 2009年11月19日 3:56
    2009年11月19日 2:11
    モデレータ
  • ひらぽん様ご回答ありがとうございます。実験までしていただいて、ありがたい限りです。
    サブルーチンを繰り返し読み出しても、体感速度は変わらないことが良く分かりました。やはりサブルーチン内ループをを改善するしかないようですね。
    ちなみにサブルーチン内の二次元配列,定数c1~c4全てdouble型で定義しています。
    2009年11月19日 4:19
  • >約二倍近いです。

    ひょっとして、Debug ビルドを実行していませんか?

    うちでは、Release ビルドを cmd.exe から実行して

    10000000 20
    10000000 23

    という結果で、2倍もの差はつきませんでした。
    • 回答としてマーク kenkou_t 2009年11月19日 8:18
    2009年11月19日 5:14
    モデレータ
  • > ひょっとして、Debug ビルドを実行していませんか?

    でした。(^ω^;

    リリースビルドに直したら

    10000000 133
    10000000 150

    になりましたです。<(_ _)>

    リリースビルドにすると、コンパイラがインライン展開するのかと思って
    ILDASM.exe で見たら、サブルーチンをきちんと呼び出していたので、
    そういうわけではなさそうですね。
    2009年11月19日 5:37
    モデレータ
  • > ちなみにサブルーチン内の二次元配列,定数c1~c4全てdouble型で定義しています。

    今度は配列の型を変えて調べてみました。
    ちなみに Visual Studio 2010 beta2 で リリースビルドで試しました。

    // 配列(int)
    {
        int[] array = Enumerable.Range(1, RoopCount).ToArray();
        int total = 0;
        Stopwatch sw = new Stopwatch();
        sw.Start();
        for (int i = 0; i < RoopCount; i++)
        {
            total += array[i] % 5 - 1;
        }
        sw.Stop();
        Console.WriteLine("{0} {1}", total, sw.ElapsedMilliseconds);
    }
    
    // 配列(double)
    {
        int[] array = Enumerable.Range(1, RoopCount).ToArray();
        double[] array2 = new double[RoopCount];
        for (int i = 0; i < RoopCount; i++)
        {
            array2[i] = (double)array[i];
        }
    
        double total = 0d;
        Stopwatch sw = new Stopwatch();
        sw.Start();
        for (int i = 0; i < RoopCount; i++)
        {
            total += array2[i] % 5d - 1d;
        }
        sw.Stop();
        Console.WriteLine("{0} {1}", total, sw.ElapsedMilliseconds);
    }
    
    // 配列(decimal)
    {
        int[] array = Enumerable.Range(1, RoopCount).ToArray();
        decimal[] array2 = new decimal[RoopCount];
        for (int i = 0; i < RoopCount; i++)
        {
            array2[i] = (decimal)array[i];
        }
    
        decimal total = 0m;
        Stopwatch sw = new Stopwatch();
        sw.Start();
        for (int i = 0; i < RoopCount; i++)
        {
            total += array2[i] % 5m - 1m;
        }
        sw.Stop();
        Console.WriteLine("{0} {1}", total, sw.ElapsedMilliseconds);
    }

    結果
    10000000 147
    10000000 274
    10000000 5454

    やっぱ double の方が少し遅い。decimal は速度的には論外ですね。(^ω^;

    • 回答としてマーク kenkou_t 2009年11月19日 15:44
    2009年11月19日 5:49
    モデレータ
  • プログラム的に練りこむのではなく、機械的に速くしたいなら、既にコメントが付いているように並列化するのが最善と思います。

    これも既出ですが、.NET Framework 4 には並列コンピューティングを支援するライブラリが追加されているので、単純なループは比較的簡単に並列化することができます。
    2009年11月19日 6:44
    モデレータ
  • >既にコメントが付いているように並列化するのが最善と思います。

    と思ってサンプルを書いてみましたが、この規模の計算だと並列化によるオーバーヘッドの方が大きくて、単純ループよりもむしろ遅くなってしまいました。

    特に今例で挙がっている演算は集計操作であるため、個々の演算を並列化して処理の効率化を狙っても、最終段の集計操作で帳消しになってしまうようです。
    • 回答としてマーク kenkou_t 2009年11月19日 8:15
    2009年11月19日 7:02
    モデレータ
  • for(j;j++)
      for(i;i++)
         AA[i,j]=c1*AA[i-1,j]+c2*AA[i+1,j]+c3*AA[i,j-1]+c4*AA[i,j+1];(c1~c4は定数)
    この式は正しいんですよね…AA[i-1,j]は、1回前のループで書き換えた直後の値を参照していていいんですよね?
    だとすると、このループは依存関係が厳しいですね。それでもLoop Unwindingは効きそう。
    • 回答としてマーク kenkou_t 2009年11月19日 15:32
    2009年11月19日 12:50
  • 渋木様、ご回答ありがとうございます。並列処理は検討の余地ありかなと思っておりましたが、なにぶん初心者なもので導入に躊躇していました。
    今回のご回答で、並列化(マルチスレッド?)しても性能が上がらないということが分かり、導入は見送ることで踏ん切りがつきました。
    重ね重ねありがとうございます。
    2009年11月19日 15:26
  • 佐祐理様,ご回答ありがとうございます。
    式は書いたもので正しいです。一度前の値を参照することを繰り返します。
    ループ展開のこと少し調べてみました。その手があったかというのが率直な感想です。ループの箇所に手を加えれば、もう少し速くなりそうな気がします。やってみます。ありがとうございました。
    2009年11月19日 15:41
  • 佐祐理様,ご回答ありがとうございます。
    式は書いたもので正しいです。一度前の値を参照することを繰り返します。
    ループ展開のこと少し調べてみました。その手があったかというのが率直な感想です。ループの箇所に手を加えれば、もう少し速くなりそうな気がします。やってみます。ありがとうございました。

    式の評価、検証を、どのようにして行いましたか?


    01 01 01
    01 01 01
    01 01 01

    という配列の場合、c1, c2, c3, c4 が 1 ならば、今のままでは次のようになります。

    02 04 05
    04 10 16
    05 16 32

    これで良いです?次のような物ではなく?

    02 03 02
    03 04 03
    02 03 02

    Jitta@わんくま同盟
    2009年11月19日 21:40
  • >並列化(マルチスレッド?)しても性能が上がらないということが分かり

    早合点です。

    僕は「今現在あなたが取り組まれている演算の効率が、並列化しても向上することはない」とは、言っていません。

    「(ひらぽんさんが)例示されたサンプルコードを単純に(機械的に)並列化しただけでは性能が上がらなかった」と報告しただけです。

    データの持ち方や計算の手順を見直せば、「今現在あなたが取り組まれている演算」の効率が向上可能性はまだまだあります。

    ちなみに、「今現在あながた取り組まれている演算」の効率を高めるのに、どれくらいのコストが投入できますか?

    データの持ち方や計算の手順を入念に見直してでも、計算効率を高めたいですか?

    その場合、元の計算式がちょっとでも変更になると、↑の労力がその度に発生することになりますが、それでも行う価値が見出せるでしょうか?

    あるいは、(まじめな話で)「単にもっと計算速度の速いPCを購入する」という解決策もあると思います。

    また、労力を惜しまないで、ということなら GPGPU の利用なども検討する値があるのかもしれません。
    • 回答としてマーク kenkou_t 2009年11月20日 9:09
    2009年11月20日 1:53
    モデレータ
  • Jitta様、ご回答ありがとうございます。
    正確に書きますと
    for(j;j++)
      for(i;i++)
         AA[i,j]=c1[i]*AA[i-1,j]+c2[i]*AA[i+1,j]+c3*AA[i,j-1]+c4*AA[i,j+1];(c1~c4は定数)
    でc3,c4は固定の定数ですが、c1,c2はiによって変わる値です。(例: c1[i]=1-2/iなど)
    私の場合はc1[i],c2[i]として、配列型で定義、かつ最初に計算で求め,ループ内で、計算しないようにしていてます。

    次にAA[i,j]の初期値ですが、一部が1、残りほとんどが0です。ただ、1の位置(洒落ではないですが)が複雑です。例えば、

    1 1 1 1 0 0
    1 1 1 0 0 0
    1 0 0 0 0 0
    0 0 0 0 0 0  など。
    しかも、この初期条件は、プログラムを走らせるたび異なるため、前回走らせて得た最終的なAA[i,j]を引き継げません。
    2009年11月20日 4:44
  • しかも、この初期条件は、プログラムを走らせるたび異なるため、前回走らせて得た最終的なAA[i,j]を引き継げません。
    この説明は、私&Jittaさんの指摘に答えられていません。

    例えばAA[3,4]を計算し、値を更新したとします。
    次にi++してAA[4,4]を計算する際、AA[i-1,j]とはAA[3,4]を参照することを意味します。
    この際に使用するAA[3,4]とは更新後の値なのですか? それとも更新前なのですか?
    # 普通、この手のベクトル演算はループ方向によらない式だと思うのですが。
    2009年11月20日 10:47
  • 正確に書きますと

    for(j;j++)
      for(i;i++)
         AA[i,j]=c1[i]*AA[i-1,j]+c2[i]*AA[i+1,j]+c3*AA[i,j-1]+c4*AA[i,j+1];(c1~c4は定数)
    

    でc3,c4は固定の定数ですが、c1,c2はiによって変わる値です。(例: c1[i]=1-2/iなど)

    次にAA[i,j]の初期値ですが、一部が1、残りほとんどが0です。ただ、1の位置(洒落ではないですが)が複雑です。

    しかも、この初期条件は、プログラムを走らせるたび異なるため、前回走らせて得た最終的なAA[i,j]を引き継げません。

    正確に申しますと、「for(j;j++)」は、文法エラーです。

    じゃなくて。ここに引用した文は、まったく当を得ていません。ある場所の計算結果は、他の場所の計算に影響を及ぼすのか?ということが、問題なのです。及ぼさないのであれば、並列化するのは容易です。及ぼすのであれば、並列化するのは難しくなります。つまり、「AA[i, j] = AA[i-1, j] + AA[i+1, j] + AA[i, j-1] + AA[i, j+1]」という式の、特に左辺は正しいのか、ということです。BB[i, j]を用意して、そちらに代入していかなければならない事はないですか?

    また、上記の for 文では i, j (特に i)が初期化されていないため、左辺がAA[i, j]であるなら、i, j の初期値によって結果が異なります。計算結果が正しいことをどうやって検証するのか、わかりません。

    とりあえず、[0, 0]から始まるとして、AA[i, j]に代入していくとした場合でも、マルチ スレッドで高速化を行うことが出来ないことはありません。

    一例。

    00 10 20 30 40
    01 11 21 31 41
    02 12 22 32 42
    03 13 23 33 43
    04 14 24 34 44

    [00]の計算が終わると、[10]と[01]の計算が可能です。[10]と[01]が終われば、[20], [02], [11]の計算が可能です。

    そこで、スレッドをいくつか用意します。そして、「ここの計算が出来ます」というバッファを用意します。スレッドは、「ここの計算が出来ますバッファ」から、計算するべき座標を取り出して計算します。計算が済むと、今計算した座標の右上、[01]を計算したなら[10]、[13]を計算したなら[22]の計算が済んでいるか確認し、済んでいれば右側の座標をバッファに登録します。また、左下を確認して、そこが済んでいるなら下側の座標をバッファに登録します。

    実際にコーディングする上で考えなければならないことは他にもたくさんありますが、それでも並列化できないわけではありません。


    Jitta@わんくま同盟
    2009年11月20日 11:27
  • 佐祐理様,jitta様、説明不足で申し訳ありません。

    佐祐理様コメントに対して答えさせて頂きますと、

    >>例えばAA[3,4]を計算し、値を更新したとします。
    >>次にi++してAA[4,4]を計算する際、AA[i-1,j]とはAA[3,4]を参照することを意味します。

    この際に使用するAA[3,4]とは更新後の値です。
    2009年11月20日 12:17
  • jitta様、失礼しました。正確にはこうです。


    for(k=0;k<1000000;k++)
      for(j=1;j<500;j++)
        for(i=1;i<1000;i++)
           AA[i,j]=c1[i]*AA[i-1,j]+c2[i]*AA[i+1,j]+c3*AA[i,j-1]+c4*AA[i,j+1];(c1~c4は定数)

    例えばAA[3,4]を計算し、値を更新したとします。
    次にi++してAA[4,4]を計算する際、使用するAA[3,4]とは一つ前に計算した更新後の値です。

    こういった計算を10万回~100万回程度繰り返し行います(kのループ箇所)。


    >>計算結果が正しいことをどうやって検証するのか、わかりません。

    このプログラムはある物理学のモデルをシミュレーションしていて、実際最終的なAA[i,j]が厳密な意味で正しいのかは分からないのです。ただ得られた解が一般的な物理法則を満たした状態になっているかを確認することでしか、計算結果が正しいか否かを検証するすべがありません。ただ計算結果を見ると、概ね物理法則を満たす結果が出ています。(あとこれでもう少し早く演算が終わればいうことはないのですが)
    • 編集済み kenkou_t 2009年11月20日 12:55
    2009年11月20日 12:35
  • >正確にはこうです。

    ほんとに?

    だとすると

    >for(i=0;i<1000;i++)
    >       AA[i,j]=c1[i]*AA[i-1,j]+c2[i]*AA[i+1,j]+c3*AA[i,j-1]+c4*AA[i,j+1];

    は i = 0 の時、配列 AA の範囲外を値を参照しようとして例外が発生するような気が。

    また、i, j がループが末尾に達した時、これまた AA の範囲外を参照したりはしませんか?

    それとも、実際には提示されたコード以外に範囲チェックのコードが入っていたりするんでしょうか?
    2009年11月20日 12:42
    モデレータ
  • すみません、間違えました
    for(k=0;k<1000000;k++)
      for(j=1;j<500;j++)
        for(i=1;i<1000;i++)
           AA[i,j]=c1[i]*AA[i-1,j]+c2[i]*AA[i+1,j]+c3*AA[i,j-1]+c4*AA[i,j+1];(c1~c4は定数)

    AA[]は1001x501で定義していて、 AA の範囲外を参照することはありません
    2009年11月20日 12:48
  • すみません、間違えました
    for(k=0;k<1000000;k++)
      for(j=1;j<500;j++)
        for(i=1;i<1000;i++)
           AA[i,j]=c1[i]*AA[i-1,j]+c2[i]*AA[i+1,j]+c3*AA[i,j-1]+c4*AA[i,j+1];(c1~c4は定数)

    AA[]は1001x501で定義していて、 AA の範囲外を参照することはありません
    そうでしたか。ではこの前提で思いつく方法を。

    C.Johnさんの指摘に近いですが、AA[]は1次元目と2次元目を入れ替えた方がいいです。メモリアクセスがシーケンシャルになり、アクセス効率が上がります。

    for(k=0;k<1000000;k++)
    for(j=1;j<500;j++)
    for(i=1;i<1000;i += 4){
    var i0 = i + 0;
    var i1 = i + 1;
    var i2 = i + 2;
    var i3 = i + 3;
    int a0, a1, a2;
    var b0 = AA[j,i1];
    var b1 = AA[j,i2];
    var b2 = AA[j,i3];
    var b3 = AA[j,i3+1];
    AA[j,i0]=a0=c1[i0]*AA[j,i0-1]+c2[i0]*b0+c3*AA[j-1,i0]+c4*AA[j+1,i0];
    AA[j,i1]=a1=c1[i1]*a0 +c2[i1]*b1+c3*AA[j-1,i1]+c4*AA[j+1,i1];
    AA[j,i2]=a2=c1[i2]*a1 +c2[i2]*b2+c3*AA[j-1,i2]+c4*AA[j+1,i2];
    AA[j,i3]= c1[i3]*a2 +c2[i3]*b3+c3*AA[j-1,i3]+c4*AA[j+1,i3];
    }
    適当にアンロールしてみました。…あってるのかなぁ
    # あんまり効率よさそうに見えないなぁ…。

    あとはunsafeを使うと配列の境界チェックを排除できるので、それでも高速化できそう。

    最後は、オーバーヘッドが大きいのでどこまで効くかわかりませんが、概要を。
    式はおおざっぱに A = 左 + 右 + 上 + 下 となっています。このうち右と下の加算は演算順序に依存関係がありません。
    そのため、 B = 右 + 下 をマルチスレッドで計算しておき、A = B + 左 + 上 を計算することができます。

    これ以上はC#よりもアセンブラを使った方がいいかと。SSE2とか。
    • 回答としてマーク kenkou_t 2009年11月21日 10:20
    2009年11月20日 14:48
  • 佐祐理様,ご回答ありがとうございました。
    確かにi,jの位置を変えると速くなりました。配列が大きい時顕著なようです。
    ありがとうございました。
    2009年11月23日 5:06
  • 2次元配列をやめてジャグ配列(というか、配列の配列)にするだけで速くなったりして。

    ちなみにメソッド呼び出しのインライン展開とかですが、ILへのコンパイル時ではなく、JIT時に行われますので、
    リリースビルドでかつデバッグ実行していない場合は多分インライン展開されてると思います。
    ※デバッグビルドでかつデバッグ実行してないときはどうだったかは、ちょっと覚えてませんが。

    2009年11月23日 14:05
  • 2次元配列をやめてジャグ配列(というか、配列の配列)にするだけで速くなったりして。

    ジャグ配列だとポインタデリファレンスが1段増えるので余計に遅くなると思います。
    .NET Frameworkの多次元配列は連続して配置される(はず)ため、先頭アドレスからのオフセットでアクセスできます。

    # 明示的に連続するという記述は見つけていませんがforeachすると連続する点と、unsafe & fixedでも連続したポインタが得られる点から。

    ところでこの配列、データ型は何なんでしょう? 0と1という記述はありましたが。
    2009年11月23日 22:54
  • なちゃ様、ご回答ありがとうございす。
    お蔭様で、インライン展開について自分の中での疑問が解消されました。
    2009年11月24日 7:45
  • 佐祐理様,ご回答ありがとうございます。
    AA[i,j]=c1[i]*AA[i-1,j]+c2[i]*AA[i+1,j]+c3*AA[i,j-1]+c4*AA[i,j+1];(c1~c4は定数)
    配列の定義はdouble型,c1~c4もdouble型で定義しています。(計算の性格上double型以外は使えないのです)
    2009年11月24日 7:48
  • ジャグ配列だとポインタデリファレンスが1段増えるので余計に遅くなると思います。
    .NET Frameworkの多次元配列は連続して配置される(はず)ため、先頭アドレスからのオフセットでアクセスできます。

    # 明示的に連続するという記述は見つけていませんがforeachすると連続する点と、unsafe & fixedでも連続したポインタが得られる点から。
    まず普通に考えてそう思うのは非常に理解出来るのですが、.NETの配列はC等の単純なメモリブロックへのアクセスとは異なり、まあ色々と特徴があるわけなんですね。
    少なくとも現行のCLRの実装では、例えデリファレンスが増えても、2次元配列へのアクセスと比較すると1次元の組み合わせの方が高速です。
    ※まあ、この辺はアクセスの仕方に依存する部分もありますので、絶対とは言えませんが。

    デリファレンスの増加は、うまくやればループの外に追い出すことができる場合もあります。
    2009年11月24日 11:42