初心者がマルチコアソフト開発に初挑戦(1)

マルチコアプログラミング未経験の人()が逐次処理プログラムをマルチコア化する挑戦記録を連載することになりました。

 

題材プログラムはマルチコア化できそうな、簡単な、演算処理プログラムです。

 

  • 2バイト×2バイトの結果が4バイトの16進数ABCDEF00となる演算の組み合わせを10件みつける
  • 掛け算の演算精度は1バイト×1バイトで行う(結果は2バイト)

 

計算のやり方は、小学校の時に習った筆算と同じです。

 

        3 4

      × 5 6

     -----------

        2 4 ・・・・・4 × 6

       1 8   ・・・・・3 × 6

       2 0   ・・・・・4 × 5

    +  1 5     ・・・・・3 × 5

  -------------------

      1 9 0 4

 

 

10進数による筆算の例ですが、2バイトどうしの掛け算を1バイトの掛け算を使って行う時もこれと同じやり方です。

  

ではまず、逐次プログラムを作ってみます。C言語です。

 

void sub(unsigned int i)

{

  unsigned int j;

 

  for ( j = 0 ; count && j <= 0xFFFF ; j++ )

  {

    a = i >> 8;         // 1バイト取り出す(左辺上位)

    b = i & 0xFF;       // 1バイト取り出す(左辺下位)

    c = j >> 8;         // 1バイト取り出す(右辺上位)

    d = j & 0xFF;       // 1バイト取り出す(右辺下位)

    mul22();            // 乗算1(下位×下位)

    mul12();            // 乗算2(上位×下位) << 8

    mul21();            // 乗算3(下位×上位) << 8

    mul11();            // 乗算4(上位×上位) << 16

    addCD();            // 加算1(乗算1+乗算3)

    addAB();            // 加算2(乗算2+乗算4)

    addEF();            // 加算3(加算1+加算2)

    if( check() )

    {

      count--;

      found[count].a = i;

      found[count].b = j;

      printf("%8.8X = %4.4X * %4.4X\n",X,i,j);

    }

  }

  return;

}

void main(void)

{

  unsigned int i;

 

  count = COUNT;

 

#pragma omp parallel for            // forループをよしなに分割してくれる

  for ( i = 0 ; i <= 0xFFFF ; i++ )

    sub(i);

 

  return;

 

}

  

このプログラムを実行すると、結果はこうなります。

  

ABCDEF00 = BB80 * EA92

ABCDEF00 = BBA8 * EA60

ABCDEF00 = C350 * E130

ABCDEF00 = E130 * C350

ABCDEF00 = EA60 * BBA8

ABCDEF00 = EA92 * BB80

  

10件見つけるのが目標でしたが、実際には6件しかありません。

結果的に、2バイト×2バイトの総当たりの演算を行うことになり、演算回数は 4,294,967,296回になります。

 

今回使うPCでは、この実行に約50秒かかりました。

PCのスペックは以下の通りで、コンパイラはCygwin環境のgccを使用しています。

  

Cygwin64 ( Windows10 Pro )

  Intel Core i7-7700 3.60GHz

  Core   4

  Thread 8

  Mem    16GB

  

このプログラムを3種類の方法で並列化してゆきます。

 

  • データ分割による並列化
  • ジョブ(タスク)による並列化
  • パイプライン処理による並列化

 

最初は「データ分割による並列化」に挑戦します。

C言語には並列化のための便利な言語拡張がありますので、gcc でも使用可能な OpenMP 拡張を使用して並列化を行います。

OpenMPには、forループを複数のループに分割してくれる記述がありますので、これを使います。

プログラムの見やすさも考慮して、少し構造も変えます。

 

  • 内側のforループを子関数化
  • 外側のforループは子関数を呼び出すだけ
  • 外側のforループをOpenMPのディレクティブ(指示)記述でスレッド分割してもらう

 

  main関数を書き換えました。

 

void sub(unsigned int i)

{

  unsigned int j;

 

  for ( j = 0 ; count && j <= 0xFFFF ; j++ )

  {

    a = i >> 8;         // 1バイト取り出す(左辺上位)

    b = i & 0xFF;       // 1バイト取り出す(左辺下位)

    c = j >> 8;         // 1バイト取り出す(右辺上位)

    d = j & 0xFF;       // 1バイト取り出す(右辺下位)

    mul22();            // 乗算1(下位×下位)

    mul12();            // 乗算2(上位×下位) << 8

    mul21();            // 乗算3(下位×上位) << 8

    mul11();            // 乗算4(上位×上位) << 16

    addCD();            // 加算1(乗算1+乗算3)

    addAB();            // 加算2(乗算2+乗算4)

    addEF();            // 加算3(加算1+加算2)

    if( check() )

    {

      count--;

      found[count].a = i;

      found[count].b = j;

      printf("%8.8X = %4.4X * %4.4X\n",X,i,j);

    }

  }

  return;

}

void main(void)

{

  unsigned int i;

 

  count = COUNT;

 

#pragma omp parallel for            // forループをよしなに分割してくれる

  for ( i = 0 ; i <= 0xFFFF ; i++ )

    sub(i);

 

  return;

 

}

 gcc の場合、OpenMP記述を有効にするために  -fopenmp オプションが必要です。

 

この指定を行わないと、分割は行われません。

 

プログラム構造を少し変えましたが、並列化のために追加したのは

  

#pragma omp parallel for

 

  の1行追加だけで、とても簡単です。

ただしこの記述を追加しても、OpenMPの言語拡張をサポートしていないコンパイラでは、何の効果もありません。コンパイラは、自分の知らない #pragma を無視するので。

 

  プログラムは明らかに高速化しました。

、まれに誤動作してしまいます。

 

 

次回は、誤動作の現象と原因、対策について説明します。