並列グラフ探索問題用ライブラリpgraphのAPI

概要

ライブラリはいくつかの種類(=kind)のグラフを作成できる。kindは1--4(予定) の整数である。各種類において、いくつかの異なる大きさ(=class)のグラフを 作成できる。classは1--3(予定)の整数である。

各ノードは定数長(=nodesize, グラフ種類に依存する)のバイト列である。バ イト列の意味はユーザに知らされないので、ブラックボックス的に用いること。 ただしユーザはmemcmpなどによってノードの等価性を調べることができるし、 バイト列の中身からハッシュ値を生成することも自由である。バイト列を memcpyなどでコピーしても良いし、(同アーキテクチャの)分散環境において他 プロセッサに送信することもできる。

たとえば、ノードの等価性は以下のように調べられる。

int i;
for (i = 0; i < nodesize; i++) { 
      if (a[i] != b[i]) return DIFFERNT; 
}
return SAME;

使い方

  gcc [your-program].o pgraph.a -o [your-program] 

API

int pgraph_init(int kind, int cls)

kindはpgraphが作るグラフの種類を表す整数である。 classはグラフサイズを表す整数である。

size_t pgraph_node_size()

int pgraph_get_root(char *p)

int pgraph_max_successors()

int pgraph_num_successors(char *p)

int pgraph_get_children(char *p, char *c)

int pgraph_report(int num_nodes)

参考1: 経過時間はpgraph_init呼出時からpgraph_report呼出時までの 実時間(gettimeofday利用)である。

参考2: 出力例は以下の通りである。

***********************************************************
PGRAPH $xxx: pgraph.c,v 1.4 2002/12/02 06:35:46 endo Exp $
Reported answer: 271559
Elapsed time: 14.750 sec
***********************************************************

int pgraph_compare_and_swap(int *p, int oldn, int newn)

参考1: 疑似コードで表すと、以下のような操作をアトミックに行なう。

if (*p == oldn) { *p = newn; return 1; } else return 0;

参考2: SPARCプロセッサではcas命令を実行する。Intelプロセッサでは lock/cmpxchg 命令を実行する。

注意: 成功判定方法が授業の説明と異なるので注意。

void pgraph_sync()

参考: SPARCプロセッサでは membar #LoadLoad | #LoadStore | #StoreLoad | #StoreStore 命令を実行する。Intelプロセッサではcpuid命令を実行する。