Intel TBBの並列コンテナによる安全でスケーラブルな並列処理

マルチコアへの移行を容易にする並列コンテナクラスの利用

安全でないコンテナの使用を検知して置き換える方法

　既に述べたように、TBBのコンテナを使用すると、STLなどの他のライブラリを使ったのでは安全に実現できない（または粒度の粗い同期でラップしなければ安全が保証されない）ような並列処理が可能になります。とはいえ、これらの並列コンテナには、スレッドセーフでないコンテナよりもオーバーヘッドが大きいという難点があります。そのため、これらのスレッドセーフなコンテナを使用するのは、スレッドセーフを保証する必要がある場合か、同時並列性を高める必要がある場合に限るべきです。

　従って、「スレッドセーフでないか同時並列性の低いコンテナクラスの使用をどうやって検知するか」というのが最初に検討すべき課題となります。以降では、文字列カウントの例を使って、Intel TBBと共にIntel Threading Tools、Intel Thread Checker、Intel Thread Profiler（http://www.intel.com/software/products/threadingを参照）をどのように使用すればこうした厄介なコンテナクラスを検知して置き換えることができるかを示します。

文字列カウントの例

　次のコードでは、STLのmap<string, int> tableを使って、Data配列内で異なる文字列の出現回数を数えています。このコードは、Win32スレッド（NThread）を作成し、各スレッドにData配列のチャンクを処理させることで並列化されています。

　CountOccurrencesメソッドはスレッドを作成し、各スレッドに処理すべき範囲の配列要素を渡します。tallyメソッドは実際の計算を行います。ここで各スレッドがDataの担当部分を反復処理し、STLのmapテーブル内の対応する要素をインクリメントします。この例の30行目で、出現回数を数えるのに要した合計時間ならびに調べた文字列の合計数（これは常にデータセットサイズNに等しくならなければならない）を出力します。リスト1に、この例のすべてのバージョンの完全なコードを示します。

00: const size_t N = 1000000;
01: static string Data[N];
02: typedef map<string,int> StringTable;
03: StringTable table;

04: DWORD WINAPI tally ( LPVOID arg ) {
05:    pair<int, int> *range =
06:      reinterpret_cast< pair<int,int> * >(arg);
07:    for( int i=range->first; i < range->second; ++i )
08:        table[Data[i]] += 1;
09:    return 0;
10: }

11: static void CountOccurrences() {
12:  HANDLE worker[8];
13:  pair<int,int> range[8];

14:  int g = static_cast<int>(ceil(static_cast<double>(N) / NThread));

15:  tick_count t0 = tick_count::now();
16:  for (int i = 0; i < NThread; i++) {
17:    int start = i * g;
18:    range[i].first = start;
29:    range[i].second = (start + g) < N ? start + g : N;
20:    worker[i] =
21:      CreateThread( NULL, 0, tally, &range[i], 0, NULL );
22:  }
23:  WaitForMultipleObjects ( NThread, worker, TRUE, INFINITE );
24:  tick_count t1 = tick_count::now();

25:  int n = 0;
26:  for( StringTable::iterator i=table.begin();
27:          i!=table.end(); ++i )
28:    n+=i->second;
39:
30:  printf("total=%d time = %g\n",n,(t1-t0).seconds());
31: }

リスト1

/*================================================
Copyright 2005-2006 Intel Corporation.  All Rights Reserved.

The source code contained or described herein and all documents related
to the source code ("Material") are owned by Intel Corporation or its
suppliers or licensors.  Title to the Material remains with Intel
Corporation or its suppliers and licensors.  The Material is protected
by worldwide copyright laws and treaty provisions.  No part of the
Material may be used, copied, reproduced, modified, published, uploaded,
posted, transmitted, distributed, or disclosed in any way without
Intel's prior express written permission.

No license under any patent, copyright, trade secret or other
intellectual property right is granted to or conferred upon you by
disclosure or delivery of the Materials, either expressly, by
implication, inducement, estoppel or otherwise.  Any license under such
intellectual property rights must be express and approved by Intel in
writing.
=================================================*/

#include "tbb/concurrent_hash_map.h"
#include "tbb/scalable_allocator.h"
#include "tbb/tick_count.h"

#include <windows.h>
#include <cmath.h>

#include <string>
#include <utility>
#include <cstdio>

#if !defined(USE_TBB)
#include <map>
#endif

using namespace tbb;
using namespace std;

//! Set to true to counts.
static bool Verbose = false;
static int NThread = 1;

#if defined(USE_FAST_STRINGS)
typedef basic_string<char, char_traits<char>,
    scalable_allocator<char> > FastString;
#else
typedef string FastString;
#endif

const size_t N = 1000000;
static FastString Data[N];

#if defined(USE_TBB)

//! Structure that defines hashing and
//  comparison operations for user's type.
struct MyHashCompare {
    static size_t hash( const FastString& x ) {
        size_t h = 0;
        for( const char* s = x.c_str(); *s; s++ )
            h = (h*17)^*s;
        return h;
    }
    //! True if strings are equal
    static bool equal( const FastString& x, const FastString& y ) {
        return x==y;
    }
};

typedef concurrent_hash_map<FastString,int,MyHashCompare> StringTable;
#else
typedef map<FastString,int> StringTable;
#endif

StringTable table;

#if defined(USE_MUTEX)
HANDLE table_mutex;
#endif

#if defined(USE_CS)
CRITICAL_SECTION table_cs;
#endif

DWORD WINAPI tally ( LPVOID arg ) {
    pair<int, int> *range = reinterpret_cast< pair<int,int> * >(arg);

    for( int i=range->first; i < range->second; ++i ) {

#if defined(USE_TBB)
        StringTable::accessor a;
        table.insert( a, Data[i] );
        a->second += 1;
#else

#if defined(USE_MUTEX)
        WaitForSingleObject ( table_mutex, INFINITE );
#endif

#if defined(USE_CS)
        EnterCriticalSection(&table_cs);
#endif

        table[Data[i]] += 1;

#if defined(USE_MUTEX)
        ReleaseMutex ( table_mutex );
#endif

#if defined(USE_CS)
        LeaveCriticalSection(&table_cs);
#endif

#endif
    }

    return 0;
}

static void CountOccurrences() {
    HANDLE worker[8];
    pair<int,int> range[8];

    int g = static_cast<int>(ceil(static_cast<double>(N) / NThread));
    int r = N%NThread;

#if defined(USE_MUTEX)
    table_mutex = CreateMutex( NULL, false, NULL );
#endif

#if defined(USE_CS)
    InitializeCriticalSection(&table_cs);
#endif

    tick_count t0 = tick_count::now();

    for (int i = 0; i < NThread; i++) {
      int start = i * g;
      range[i].first = start;
      range[i].second = (start + g) < N ? start + g : N;
      worker[i] = CreateThread( NULL, 0, tally, &range[i], 0, NULL );
    }
    WaitForMultipleObjects ( NThread, worker, TRUE, INFINITE );

    tick_count t1 = tick_count::now();

    int n = 0;
    for( StringTable::iterator i=table.begin(); i!=table.end(); ++i ) {
        if( Verbose )
            printf("%s %d\n",i->first.c_str(),i->second);
        n+=i->second;
    }
    printf("total=%d time = %g\n",n,(t1-t0).seconds());

#if defined(USE_CS)
    DeleteCriticalSection(&table_cs);
#endif
}

static const FastString Adjective[] = {
    "sour",
    "sweet",
    "bitter",
    "salty",
    "big",
    "small"
};

static const FastString Noun[] = {
    "apple",
    "banana",
    "cherry",
    "date",
    "eggplant",
    "fig",
    "grape",
    "honeydew",
    "icao",
    "jujube"
};

static void CreateData() {
    size_t n_adjective = sizeof(Adjective)/sizeof(Adjective[0]);
    size_t n_noun = sizeof(Noun)/sizeof(Noun[0]);
    for( int i=0; i<N; ++i ) {
        Data[i] = Adjective[rand()%n_adjective];
        Data[i] += " ";
        Data[i] += Noun[rand()%n_noun];
    }
}

static void ParseCommandLine( int argc, char* argv[] ) {
    int i = 1;
    if( i<argc && strcmp( argv[i], "verbose" )==0 ) {
        Verbose = true;
        ++i;
    }
    if( i<argc && !isdigit(argv[i][0]) ) {
        fprintf(stderr,"Usage: %s [verbose] number-of-threads\n",
                argv[0]);
        exit(1);
    }
    if( i<argc ) NThread = strtol(argv[i++],0,0);
}

int main( int argc, char* argv[] ) {
    srand(2);
    ParseCommandLine( argc, argv );
    CreateData();
    CountOccurrences();
}