マルチコア時代における並列化技術の重要性

なんだか相変わらずエラソーなタイトルだがいつものごとく大した内容ではないので安心するように（何

最近はCPUにコアが２つ乗っているのがだんだん普通になってきた。ちなみに私が会社で開発用に使っているのはコアが４つある。わがままを言って去年買ってもらった（ぉ　まあ、それまで使っていたPCが事務処理用だったので実際開発は苦しかったのだが。
ちなみに、リリース先のワークステーションはコアが８つという想定。詳しくは分からないが多分クアッドコアのCPUが二つのっているのであろう。おそろしや・・・。このまま着実に(少なくともワークステーションでは)コア数が増えていくことが予想されるので、並列化技術を持っていないアルゴ屋さんはお払い箱になる可能性もある。

並列化とは・・・て、さすがにそんなことを説明するつもりは無いので知らない人は適当に検索をかけること。一番簡単な方法はコアの数だけスレッドを立てればよい。OSがマルチコアに対応していれば各スレッドをそれぞれのコアで走らせるはずである。まあそんなわけで、マルチスレッドプログラムの知識があれば基本的に並列処理の実装はわりと簡単に出来る。

・・・とはいっても実際に実装するとなるとやや面倒な部分がある。だいたい難関は二つある。
１．アルゴリズム的に並列化が効くかどうか、若しくは並列処理が可能なようにアルゴリズム設計をどうするか？
２．並列処理を必要という時点で計算自体がクソ重い処理であることは間違いないので通常はC++なはず。で、C++はスレッドが標準化されていないので通常はAPIを直接叩く。他のAPIは知らないけど少なくともwindowsAPIのスレッドはC++と相性が悪い。つまり実装しにくい。

前者はアルゴリズム的な部分であり、これからアルゴ屋さんの課題になるだろう。シングルコアで最速でないアルゴリズムでも並列化によって最速アルゴリズムになる可能性もある。このあたりの微妙な調整がこれからの勝負になるだろう。場合によってはマルチコアかどうかで動的にアルゴリズムを切り替える・・・というのもそのうち勝負どころになるかもしれない。

で、問題は後者である。私が並列化を始めた頃はＡＰＩを直接叩いていたので実装が結構大変だった。最初はシングルコア用で作ってあとで並列化に改造するという手をとっていたのが変更箇所が多くてわりと参っていた。そんなわけでOpenMPのようにforで回すところを簡易的に並列化できる方法はないかな？とライブラリ設計を考えました。

んでまあ、JAVAのスレッドクラスを参考にしたりしてTemplateMethodパターンを利用して出来上がりました。

//--------------------------.h側-----------------------------------

#pragma once
#include <windows.h>
#include <process.h>
#include "CriticalSection.h"

class ParallelizationSameProcess
{
public:
	ParallelizationSameProcess();
	virtual ~ParallelizationSameProcess();

	//並列化の数。
	void SetThreadSize( unsigned int iThreadSize );
protected:
	//終了地点を設定する。
	void SetEnd( int iThreadLoopEnd );
	//並列化演算を開始する。各スレッドでのスタックサイズを指定できる。
	void ParallelizationStart( unsigned int iStackSize = 0 );

	//並列化演算で呼ばれる仮想関数。
	//引数は現在の処理の番号が入ってくる。
	virtual void ThreadExecute( unsigned int iNum ) = 0;
private:
	static unsigned int __stdcall ThreadFunct( void* p );
	unsigned int m_iThreadSize;

	//ループ変数
	int m_iThreadLoopEnd;
	volatile int m_iThreadLoop;

	//排他処理
	CriticalSection m_CriticalSection;
};

//--------------------------.cpp側-----------------------------------

ParallelizationSameProcess::ParallelizationSameProcess():
m_iThreadSize( 1 ),
m_iThreadLoopEnd( 0 ),
m_iThreadLoop( 0 ),
{
}

ParallelizationSameProcess::~ParallelizationSameProcess()
{
}

void ParallelizationSameProcess::SetThreadSize( unsigned int iThreadSize )
{
	m_iThreadSize = iThreadSize;
}

void ParallelizationSameProcess::SetStart( int iThreadLoopStart )
{
	m_iThreadLoopStart = iThreadLoopStart;
}

void ParallelizationSameProcess::ParallelizationStart( unsigned int iStackSize )
{
	//ループ変数の初期化
	m_iThreadLoop = 0;
	//スレッド作成
	HANDLE* ahThread = new HANDLE[m_iThreadSize];
	for( unsigned int iThread = 0; iThread < m_iThreadSize; ++iThread ){
		//スレッドの開始
		ahThread[iThread] = (HANDLE)_beginthreadex( NULL, iStackSize, ThreadFunct, this, 0, NULL );
	}
	//待機
	::WaitForMultipleObjects( iThreadSize, ahThread, TRUE, INFINITE );
	//後始末
	delete[] ahThread;

}

unsigned int __stdcall ParallelizationSameProcess::ThreadFunct( void* p )
{
	ParallelizationSameProcess* pThis = reinterpret_cast< ParallelizationSameProcess* >( p );

	for(;;){
		//ループ判定
		int iThreadLoop = 0;
		bool bEnd = false;

		//クリティカルセクションでロック
		pThis->m_CriticalSection.EnterCriticalSection();
		if( pThis->m_iThreadLoop < pThis->m_iThreadLoopEnd ){
			iThreadLoop = pThis->m_iThreadLoop;
			++(pThis->m_iThreadLoop);
		}else{
			bEnd = true;
		}
		pThis->m_CriticalSection.LeaveCriticalSection();

		if( bEnd ){
			break;
		}else{
			//処理の呼び出し
			pThis->ThreadExecute( iThreadLoop );
		}
	}
	return 0;
}

ちなみに、"CriticalSection.h"はその名の通り、クリティカルセクションクラスである。実装は以下の通りである。定番ですね。

class CriticalSection
{
public:
	CriticalSection(){
		::InitializeCriticalSection( &m_CriticalSection );
	}
	virtual ~CriticalSection(){
		::DeleteCriticalSection( &m_CriticalSection );
	}
	//排他処理区間に入る。
	void EnterCriticalSection(){
		::EnterCriticalSection( &m_CriticalSection );
	}
	//排他処理区間から出る。
	void LeaveCriticalSection(){
		::LeaveCriticalSection( &m_CriticalSection );
	}
private:
	::CRITICAL_SECTION m_CriticalSection;
};

実際の使い方だが、まずはこのクラスを並列処理を施したいに継承させる。そして、並列化したい計算部分をThreadExecuteにオーバーライドさせる。あとは終値を設定してParallelizationStart()を呼ぶだけである。実際に利用したい場合は先に並列化の数をSetThreadSize()で設定しておいて計算を始めればOK。簡単でしょ？（ぇ

具体的な例を以下で説明する。以下のような計算を行うクラスがあったとする。

class HeavyCalc
{
	void Calc(){
		for( int i = 0; i < m_iSize; ++i ){
			SingleCalc( i );
		}
	}
private:
	void SingleCalc( int i ){
		//クソ重い処理
	}
	int m_iSize;
};

ここで、void Heavy::SingleCalc(int)というメソッドがクソ重くて並列化したいという想定である。改造は以下のようになる。

class HeavyCalc:public ParallelizationSameProcess
{
	void Calc(){
		//for( int i = 0; i < m_iSize; ++i ){
		//	SingleCalc( i );
		//}
		SetEnd( m_iSize );
		ParallelizationStart();
	}
protected:
	virtual void ThreadExecute( unsigned int iNum ){
		SingleCalc( iNum );
	}
private:
	void SingleCalc( int i ){
		//クソ重い処理
	}
	int m_iSize;
};

これだけでなんと並列化が可能になる。これならたとえプログラムが苦手なアルゴ屋さんでも簡単に実装が出来ます。実際、うちのグループはこのクラスのおかげで開発の片手間で並列化が実現できています（＾＾；
なお、サンプルのクラスですが実際に使われているのはもっと汎用性が高くてしっかりしているんですがあまり公開しすぎると会社から叱られそうなので最低限部分しか載せていません。悪しからず。

えっと、自分的にはわりと貢献した実績だと思うんですが・・・会社の評定はどうなんだろうな（汗