タスク並列化 OpenMP vs pthread

OpenMPとpthreadでそれぞれタスク並列化を実装して比較した。



#include

#define N 90000000

int a[N];

int b[N];

int c[N];

int d[N];



int main()

{

int i=0;

int k=0;

int l=0;

int j=0;

//#pragma pomp inst begin(foo)

#pragma omp parallel

#pragma omp sections nowait

	{

#pragma omp section

		{

			printf("a");

			for(i=0;i

pthreadのコード


#include 

#include 

#include 
#define N 90000000

#define THREAD_NUM 4

  int a[N];

  int b[N];

  int c[N];

  int d[N];



void thread_func(void *arg)

{

  long tid;

  tid = (long)arg;
  

  int i=0;

  int k=0;

  int l=0;

  int j=0;
		switch(tid)

		{

			case 0:

			for(i=0;i



    

  • 実行時間の比較(4スレッド)

    • 

real    0m30.565s

user    1m51.666s

sys     0m1.317s



    

  • 

      

    • pthread版
      • 

    • 

real    0m3.604s

user    0m11.973s

sys     0m1.757s



    

  • 

      

    • 逐次処理
      • 

    • 

real    0m6.833s

user    0m5.890s

sys     0m0.926s
OpenMPはオーバーヘッドが非常に大きいことがわかる。

OpenMPによるタスク並列化

研究

タスク並列化はsections,sectionで行う。ただし、オーバーヘッドが大きいので注意。



#define N 90000000

int a[N];

int b[N];

int c[N];

int d[N];

int main()

{

int i=0;

int k=0;

int l=0;

int j=0;

#pragma omp parallel

#pragma omp sections

	{

#pragma omp section

		{

			for(i=0;i

タスク並列化しない場合

real    0m3.620s

user    0m2.729s

sys     0m0.888s
タスク並列化した場合

real    0m13.968s

user    0m53.998s

sys     0m1.366s

OpenMPの実験

研究

OpenMPによる並列化の効果を確認する実験。単純なコードをOpenMPで並列化。



#define N 10000

int a[N][N];

int main()

{

int i=0;

int j=0;

#pragma omp parallel

{

#pragma omp for private(i)

for(j=0;j

OpenMPを使う場合:Core2Duo Quad(4core)

real    0m1.573s

user    0m5.615s

sys     0m0.576s

使わない場合:1core

real    0m4.599s

user    0m4.320s

sys     0m0.278s

ちゃんと並列化の効果が現れた

ちょっとした実験

研究

ちょっとした実験。配列へのアクセスパターンで実行時間が
どのくらい変わるか。



#define N 10000

int a[N][N];

int main()

{

int i=0;

int j=0;
for(j=0;j

real    0m1.360s

user    0m1.045s

sys     0m0.308s


#define N 10000

int a[N][N];

int main()

{

int i=0;

int j=0;
for(j=0;j

real    0m0.514s

user    0m0.265s

sys     0m0.245s
3倍も変わるのが驚き

ちょっとした実験

研究

ちょっとした実験。配列へのアクセスパターンで実行時間がどのくらい変わるか。



#define N 10000

int a[N][N];

int main()

{

int i=0;

int j=0;
for(j=0;j

real    0m1.360s

user    0m1.045s

sys     0m0.308s


#define N 10000

int a[N][N];

int main()

{

int i=0;

int j=0;
for(j=0;j

real    0m0.514s

user    0m0.265s

sys     0m0.245s
3倍も変わるのが驚き
valgrindによる、キャッシュミスの測定もしてみた。まず前者


==7912== I   refs:      800,175,357

==7912== I1  misses:            568

==7912== L2i misses:            564

==7912== I1  miss rate:        0.00%

==7912== L2i miss rate:        0.00%

==7912== 

==7912== D   refs:      500,096,605  (400,070,837 rd   + 100,025,768 wr)

==7912== D1  misses:    100,001,142  (        962 rd   + 100,000,180 wr)

==7912== L2d misses:      6,261,058  (        886 rd   +   6,260,172 wr)

==7912== D1  miss rate:        19.9% (        0.0%     +        99.9%  )

==7912== L2d miss rate:         1.2% (        0.0%     +         6.2%  )

==7912== 

==7912== L2 refs:       100,001,710  (      1,530 rd   + 100,000,180 wr)

==7912== L2 misses:       6,261,622  (      1,450 rd   +   6,260,172 wr)

==7912== L2 miss rate:          0.4% (        0.0%     +         6.2%  )
次に後者


==7973== I   refs:      106,678

==7973== I1  misses:        683

==7973== L2i misses:        678

==7973== I1  miss rate:    0.64%

==7973== L2i miss rate:    0.63%

==7973== 

==7973== D   refs:       56,049  (38,316 rd   + 17,733 wr)

==7973== D1  misses:        784  (   609 rd   +    175 wr)

==7973== L2d misses:        725  (   561 rd   +    164 wr)

==7973== D1  miss rate:     1.3% (   1.5%     +    0.9%  )

==7973== L2d miss rate:     1.2% (   1.4%     +    0.9%  )

==7973== 

==7973== L2 refs:         1,467  ( 1,292 rd   +    175 wr)

==7973== L2 misses:       1,403  ( 1,239 rd   +    164 wr)

==7973== L2 miss rate:      0.8% (   0.8%     +    0.9%  )
D1キャッシュミスが19.9%=>1.3%にも激減している。

ちょっとした実験

研究

メモリアクセスパターンによって実行速度がどのくらい変わるかを調査してみた。各所で散々やられている実験だけど、自分でやったことはなかったので・・・

  • 1.配列に行=>列のようにアクセスする場合



#define N 10000

int a[N][N];

int main()

{

int i=0;

int j=0;
for(j=0;j



    

  • 2.配列に列=>行のようにアクセスする場合
    • 



#define N 10000

int a[N][N];

int main()

{

int i=0;

int j=0;
for(j=0;j

結果



    

  • 

      

    • 1の場合
      • 

    • 

real    0m1.434s

user    0m1.143s

sys     0m0.287s



    

  • 

      

    • 2の場合
      • 

    • 

real    0m0.528s

user    0m0.294s

sys     0m0.233s
やっぱりかなり変わる。しかし、3倍近くも違うのは驚き

高度区分試験

高度区分も卒業までには一つくらい押さえたいところ

情報処理教科書 [春期]高度試験午前対策 2010年度版

情報処理教科書 [春期]高度試験午前対策 2010年度版