「Intel Concurrent Collections」のデバッグとチューニング

　「Intel Concurrent Collection」（以下、CnC）の概要と基本的な使い方は前回解説しましたが、まだあと少し、語っていないトピックが残っています。CnCのデバッグとチューニングに関するお話。

フィボナッチ数列

　デバッグとチューニングのお話の前に、おさらいを兼ねてフィボナッチ数列の第n項:fib(n)を求めるサンプルを書いてみましょうか。フィボナッチ数列:0,1,1,2,3,5,8...の第n項:fib(n)は、以下のように再帰的に定義されます。

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)  if n > 1

　この定義に忠実にCnCで実装します。上記の定義をそのままstep内で求め、得られた結果をn番目のitemに出力するとしましょう。step内の処理は：

switch ( n ) {
case 0: itemのn番目に 0 をputする
case 1: itemのn番目に 1 をputする
default: 
  itemのn-1番目をgetする
  itemのn-2番目をgetする
 ふたつを加えてitemのn番目にputする
}

となります。このstepを0,1,...nで着火すればitemのn番目にfib(n)が求まります。

　CnCのチュートリアルには、こんなコードが示されていました。

list01

// 実害のない warning を抑止する
#define _CRT_SECURE_NO_DEPRECATE 

#include <cnc/cnc.h>
#include <cnc/debug.h> // デバッグのために追加

// フィボナッチ数 に十分な大きさの型
typedef unsigned long long fib_type;

// forward declaration
struct fib_context;

// フィボナッチ数を求める step
struct fib_step {
  // declaration of execute method goes here
  int execute( const int & tag, fib_context & c ) const;
};

// コンテキスト: tag/step/itemの集合およびそれらの依存関係を束ねる
struct fib_context : public CnC::context< fib_context > {
  CnC::step_collection< fib_step >       m_steps;
  CnC::item_collection< int, fib_type >  m_fibs;
  CnC::tag_collection< int >             m_tags;

  // コンストラクタ
  fib_context();
};

fib_context::fib_context()
  : CnC::context< fib_context >(),
    m_steps( *this ),
    m_fibs( *this ),
    m_tags( *this ) {
  m_tags.prescribes( m_steps, *this ); // m_tags は m_step に指示する
  m_steps.consumes( m_fibs );          // m_steps は m_fibs を消費する
  m_steps.produces( m_fibs );          // m_steps は m_fibs を生産する
}

// フィボナッチ数列の第tag項を求める
int fib_step::execute( const int & tag, fib_context & ctxt ) const {
  switch ( tag ) {
  case 0 :   // fib(0) = 0
    ctxt.m_fibs.put( tag, 0 ); break;
  case 1 :  // fib(1) = 1
    ctxt.m_fibs.put( tag, 1 ); break; 
  default : // fib(n) = fib(n-1) + fib(n-2) 
    // 前の二つを手に入れて
    fib_type f_1; ctxt.m_fibs.get( tag - 1, f_1 );
    fib_type f_2; ctxt.m_fibs.get( tag - 2, f_2 );
    // 加えたものが結果となる
    ctxt.m_fibs.put( tag, f_1 + f_2 );
  }
  return CnC::CNC_Success;
}

int main( int argc, char* argv[] ) {
  int n = 42;
  // eval command line args
  if ( argc < 2 ) {
    std::cerr << "usage: " << argv[0] << " n\nUsing default value " << n << std::endl;
  } else {
    n = atol( argv[1] );
  }

  // コンテキストを生成し
  fib_context ctxt; 

  // tagをputして
  for( int i = 0; i <= n; ++i ) ctxt.m_tags.put( i );

  // 終了を待ち
  ctxt.wait(); 

  // 結果を取得して
  fib_type res2;
  ctxt.m_fibs.get( n, res2 );

  // 出力する
  std::cout << "fib (" << n << "): " << res2 << std::endl;

  return 0;
}