N-QueensをPARDSで並列化

できた。昨日のC++版N-Queensを若干変更。
変更点は、「答えリスト」だけを特別扱いして、共有メモリ上に確保。あと、答えリストの中身は配列で表現することで、共有メモリ確保のオーバヘッドを減らした。
また、やたらプロセスを生成してもオーバヘッドが増えるので、関数"qu"の１段目だけを"qudist"という別関数にして、この関数の中でだけSPAWNすることにした。関数中１回しかSPAWNしないので、サイズが１３だと、１３プロセスしか生成しない。ので、負荷の不均衡がおこる可能性がある。

サイズ = 13、Macbook (Core 2 Duo)で、

• 元のプログラム：5.7秒
• プログラム変更、SPAWNせず：６秒
• プログラム変更、SPAWN(2台）：3.2秒

なので、まずまず、というところか？

PARDSを利用したプログラムスタイルとして、

• 並列化前の関数で返り値だった値をSync変数にくるんで引数として与える
• （上述の返り値がポインタである場合は特に）Sync変数に対するread/writeのみで通信するのではなく、共有メモリを用いて通信する

というのがパターン、かなあ？

プログラムは以下の通り：

#include "Sync.h"

template <class T> class List{
public:
  T value;
  List<T>* next;
};

class AnsList{
public:
  int ans[32];
  AnsList* next;
  static void* operator new(size_t size);
  static void operator delete(void* obj);
};

void* AnsList::operator new(size_t size)
{
  void* ptr = pards_shmalloc(size);
  return ptr;
}

void AnsList::operator delete(void* obj)
{
  pards_shmfree(obj);
  return;
}

List<int>* generate(int n){
  if(n > 0) {
    List<int>* c = new List<int>;
    c->value = n; c->next = generate(n-1);
    return c;
  } else {
    return 0;
  }
}

template <class T> List<T>* append(List<T>* a, List<T>* b){
  if(a != 0){
    T h = a->value;
    List<T>* t = a->next;
    List<T>* res = new List<T>;
    res->value = h;
    res->next = append(t,b);
    return res;
  } else {
    return b;
  }
}

AnsList* appendAnsList(AnsList* a, AnsList* b){
  if(a == 0) return b;
  else {
    AnsList* tmp = a;
    while(tmp->next != 0) tmp = tmp->next;
    tmp->next = b;
    return a;
  }
}

void ListToAnsList(List<int>* l, AnsList* a){
  List<int>* crnt = l;
  for(int i = 0; crnt != 0 ;i++){
    a->ans[i] = crnt->value;
    crnt = crnt->next;
  }
}

void qudist(List<int>* plu, List<int>* ls, List<int>* lp, Sync<AnsList*> ans){
  if(plu == 0) {
    if(ls == 0) {
      AnsList* res = new AnsList;
      ListToAnsList(lp,res);
      res->next = 0;
      ans.write(res);
      return;
    } else {
      ans.write(0);
      return;
    }
  } else {
    AnsList* check(int, int, List<int>*, List<int>*, List<int>*);

    List<int>*  lu = plu->next;
    int p = plu->value;
    List<int>* lr = append<int>(lu, ls);

    List<int>* nls = new List<int>;
    nls->value = p;
    nls->next = ls;

    Sync<AnsList*> syncans2;
    SPAWN(qudist(lu, nls, lp, syncans2));
    AnsList* ans1 = check(p, 1, lr, lp, lp);

    AnsList* ans2 = syncans2.read();
    ans.write(appendAnsList(ans1, ans2));
  }
}

AnsList* qu(List<int>* plu, List<int>* ls, List<int>* lp){
  if(plu == 0) {
    if(ls == 0) {
      AnsList* res = new AnsList;
      ListToAnsList(lp,res);
      res->next = 0;
      return res;
    } else {
      return 0;
    }
  } else {
    AnsList* check(int, int, List<int>*, List<int>*, List<int>*);

    List<int>*  lu = plu->next;
    int p = plu->value;
    List<int>* lr = append<int>(lu, ls);
    AnsList* ans1 = check(p, 1, lr, lp, lp);
    List<int>* nls = new List<int>;
    nls->value = p;
    nls->next = ls;
    AnsList* ans2 = qu(lu, nls, lp);
    return appendAnsList(ans1, ans2);
  }
}

AnsList* check(int p, int d, List<int>* l, List<int>* qlp0, List<int>* lp){
  if(qlp0 == 0) {
    List<int>* plp = new List<int>;
    plp->value = p;
    plp->next = lp;
    return qu(l,0,plp);
  } else {
    int q = qlp0->value;
    if(q + d == p || q - d == p)
      return 0;
    else{
      List<int>* lp0 = qlp0->next;
      return check(p,d+1,l,lp0,lp);
    }
  }
}

int main(int argc, char* argv[])
{
  if(argc < 2) {
    printf("qu NUM\n");
    exit(0);
  }

  int num = atoi(argv[1]);

  pards_init();

  List<int>* gen = generate(num);
  Sync<AnsList*> ans;
  qudist(gen,0,0,ans);

  AnsList* res = ans.read();
  
  int i = 0;
  for(; res != 0; res = res->next, i++){
    /*    for(int i = 0; i < num; i++)
	  printf("%d ", res->ans[i]);
	  printf("\n"); */
  }
  printf("num = %d\n",i);

  pards_finalize();
}