Add the NQueen example
authorYanhua Yanhua <sun51@illinois.edu>
Tue, 23 Feb 2010 21:50:28 +0000 (15:50 -0600)
committerYanhua Yanhua <sun51@illinois.edu>
Fri, 5 Mar 2010 23:06:15 +0000 (17:06 -0600)
examples/charm++/NQueen/Makefile [new file with mode: 0644]
examples/charm++/NQueen/counter.C [new file with mode: 0644]
examples/charm++/NQueen/counter.ci [new file with mode: 0644]
examples/charm++/NQueen/counter.h [new file with mode: 0644]
examples/charm++/NQueen/main.C [new file with mode: 0644]
examples/charm++/NQueen/main.ci [new file with mode: 0644]
examples/charm++/NQueen/main.h [new file with mode: 0644]
examples/charm++/NQueen/nqueen.C [new file with mode: 0644]
examples/charm++/NQueen/nqueen.h [new file with mode: 0644]

diff --git a/examples/charm++/NQueen/Makefile b/examples/charm++/NQueen/Makefile
new file mode 100644 (file)
index 0000000..eb87b0d
--- /dev/null
@@ -0,0 +1,45 @@
+CHARMDIR = /expand/home/jessie/PPL/git/charm/mpi-linux-x86_64
+#CHARMDIR = /Users/yanhuasun/PPL/charm/charm-6.1.2/multicore-darwin-x86_64
+CHARMC = $(CHARMDIR)/bin/charmc $(OPTS) 
+default: all
+all: nqueen nqueen_prj nqueen_greedy nqueen_refine nqueen_spray nqueen_neighbor
+
+nqueen : main.o nqueen.o counter.o
+       $(CHARMC) -language charm++ -o nqueen main.o nqueen.o counter.o
+
+nqueen_spray : main.o nqueen.o counter.o
+       $(CHARMC) -language charm++ -balance spray -o nqueen_spray main.o nqueen.o counter.o
+
+nqueen_neighbor : main.o nqueen.o counter.o
+       $(CHARMC) -language charm++ -balance neighbor -o nqueen_neighbor main.o nqueen.o counter.o
+
+nqueen_prj : main.o nqueen.o counter.o
+       $(CHARMC) -language charm++ -tracemode projections -o nqueen_prj main.o nqueen.o counter.o
+
+nqueen_greedy : main.o nqueen.o counter.o
+       $(CHARMC) -language charm++ -balancer GreedyCommLB  -o nqueen_greedy main.o nqueen.o counter.o
+
+nqueen_refine : main.o nqueen.o counter.o
+       $(CHARMC) -language charm++ -balancer RefineLB  -o nqueen_refine main.o nqueen.o counter.o
+main.o : main.C main.h counter.decl.h counter.def.h  main.decl.h main.def.h
+       $(CHARMC) -o main.o main.C
+
+nqueen.o : nqueen.C nqueen.h counter.decl.h counter.def.h main.decl.h
+       $(CHARMC) -o nqueen.o nqueen.C
+
+counter.o: counter.C
+       $(CHARMC) -o counter.o counter.C
+
+main.decl.h main.def.h : main.ci
+       $(CHARMC) main.ci
+       
+counter.decl.h counter.def.h : counter.ci
+       $(CHARMC) counter.ci
+
+clean:
+       rm -f main.decl.h main.def.h main.o
+       rm -f counter.decl.h counter.def.h nqueen.o
+       rm -f nqueen nqueen_refine nqueen_greedy nqueen_prj nqueen_rand nqueen_spray nqueen_neighbor charmrun
+       rm *.o *.def.h *.decl.h
+       rm *.log *.sts *.projrc
+
diff --git a/examples/charm++/NQueen/counter.C b/examples/charm++/NQueen/counter.C
new file mode 100644 (file)
index 0000000..d65862e
--- /dev/null
@@ -0,0 +1,54 @@
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+#include "charm++.h"
+
+#include "counter.h"
+#include "Counter.def.h"
+
+counter::counter(DUMMY *m)
+{ 
+  // initialize the local count;
+  mygrp = thisgroup;
+  myCount = totalCount = 0;
+  waitFor = CkNumPes(); // wait for all processors to report
+  threadId = NULL;
+}
+
+void counter::increment()
+{
+  myCount++;
+}
+
+void counter::sendCounts(DUMMY *m)
+  // This method is invoked via a broadcast. Each branch then reports 
+  // its count to the branch on 0 (or via a spanning tree.)
+{
+  CProxy_counter grp(mygrp);
+  grp[0].childCount(new countMsg(myCount));
+  delete m;
+}
+
+void counter::childCount(countMsg *m)
+{
+  totalCount += m->count;
+  waitFor--;
+  if (waitFor == 0) 
+    if (threadId) { CthAwaken(threadId);}
+}
+
+int counter::getTotalCount()
+{
+  CProxy_counter grp(mygrp);
+  grp.sendCounts(new DUMMY);//this is a broadcast, as no processor is mentioned
+  threadId = CthSelf();
+  while (waitFor != 0)  CthSuspend(); 
+  return totalCount;
+}
+CkGroupID  counterInit()
+{
+  DUMMY *m = new  DUMMY;
+  CkGroupID g =CProxy_counter::ckNew(m);  // create a new group of class "counter"
+  return g;
+}
diff --git a/examples/charm++/NQueen/counter.ci b/examples/charm++/NQueen/counter.ci
new file mode 100644 (file)
index 0000000..d545458
--- /dev/null
@@ -0,0 +1,10 @@
+module Counter {
+  message countMsg;
+  message DUMMY;
+  
+  group counter {
+    entry counter(DUMMY *);
+    entry void sendCounts(DUMMY *);
+    entry void childCount(countMsg *);
+  };
+};
diff --git a/examples/charm++/NQueen/counter.h b/examples/charm++/NQueen/counter.h
new file mode 100644 (file)
index 0000000..81717ae
--- /dev/null
@@ -0,0 +1,30 @@
+#include "Counter.decl.h"
+
+extern CkGroupID counterInit();
+extern int counterReport();
+extern void counterIncrement();
+
+class countMsg : public CMessage_countMsg {
+public:
+  int count;
+  countMsg(int c) : count(c) {};
+};
+
+class DUMMY : public CMessage_DUMMY {
+};
+
+class counter: public Group {
+private:
+  CkGroupID mygrp;
+  int myCount;
+  int totalCount;
+  int waitFor;
+  CthThread threadId;
+public:
+  counter(CkMigrateMessage *m) {}
+  counter(DUMMY *);
+  void childCount(countMsg *);
+  void increment();
+  void sendCounts(DUMMY *);
+  int  getTotalCount();
+};
diff --git a/examples/charm++/NQueen/main.C b/examples/charm++/NQueen/main.C
new file mode 100644 (file)
index 0000000..0cc194d
--- /dev/null
@@ -0,0 +1,57 @@
+/*
+ * N Queen solver 
+ * Feb 1st
+ *
+ * Copyright by PPL
+ * problem report sun51@uiuc.edu
+*/
+
+#include "main.decl.h"
+#include "main.h"
+#include "nqueen.h"
+#include "counter.h"
+
+Main::Main(CkArgMsg* msg)
+{
+
+    //CkPrintf(" Usage: nqueen Num\n");
+
+    numQueens = 5;
+    grainsize = 3;
+    if(msg->argc > 2)
+    {
+        numQueens = atoi(msg->argv[1]);
+        grainsize = atoi(msg->argv[2]);   
+    }
+    delete msg;
+
+    CkPrintf(" Usage: nqueen numQueen grainsize (%d, g=%d, np=%d)\n", numQueens, grainsize, CkNumPes());
+
+    CkVec<int> initStatus(numQueens);
+    for(int i=0; i<numQueens; i++)
+        initStatus[i] = -1;
+
+    /* timer */
+    mainhandle=thishandle;
+   
+    QueenState *qmsg = new QueenState;
+    qmsg->row = -1; 
+    CProxy_NQueen::ckNew(qmsg);
+    
+    starttimer = CkTimer();
+    counterGroup = counterInit();
+    CkStartQD(CkIndex_Main::Quiescence1((DUMMYMSG *)0), &mainhandle);
+}
+
+Main::Main(CkMigrateMessage* msg) {}
+
+void Main::Quiescence1(DUMMYMSG *msg)
+{
+    int numSolutions = CProxy_counter(counterGroup).ckLocalBranch()->getTotalCount();
+    double endtimer = CkTimer();
+    CkPrintf("There are %d Solutions to %d queens. Finish time=%f\n",
+        numSolutions, numQueens, endtimer-starttimer);
+    CkExit();
+}
+
+#include "main.def.h"
diff --git a/examples/charm++/NQueen/main.ci b/examples/charm++/NQueen/main.ci
new file mode 100644 (file)
index 0000000..78e3202
--- /dev/null
@@ -0,0 +1,22 @@
+mainmodule main {
+
+    extern module Counter;
+    readonly int numQueens;
+    readonly int grainsize;
+    readonly CkGroupID counterGroup;
+    
+
+    message QueenState; 
+    message DUMMYMSG;
+    
+    mainchare Main{
+        entry Main(CkArgMsg* msg);
+        entry [threaded] void Quiescence1(DUMMYMSG *);
+    
+    };
+
+    chare NQueen {
+        entry NQueen(QueenState *);
+    };
+
+};
diff --git a/examples/charm++/NQueen/main.h b/examples/charm++/NQueen/main.h
new file mode 100644 (file)
index 0000000..13a56f8
--- /dev/null
@@ -0,0 +1,21 @@
+#ifndef _MAIN_H_
+#define _MAIN_H_
+
+/* readonly */ int numQueens; 
+/* readonly */ int grainsize;
+/* readonly */ CkGroupID counterGroup;
+/* readonly */ CkChareID mainhandle;
+
+
+class Main : public CBase_Main{
+
+public:
+    Main(CkArgMsg* msg);
+    Main(CkMigrateMessage* msg);
+    void Quiescence1(DUMMYMSG *msg);
+
+private:
+    double starttimer;
+};
+
+#endif
diff --git a/examples/charm++/NQueen/nqueen.C b/examples/charm++/NQueen/nqueen.C
new file mode 100644 (file)
index 0000000..b3dc39b
--- /dev/null
@@ -0,0 +1,111 @@
+#include "main.decl.h"
+#include "nqueen.h"
+#include "counter.h"
+
+extern int numQueens;
+extern CProxy_Main mainProxy;
+extern int grainsize;
+extern CkGroupID counterGroup;
+
+NQueen::NQueen(CkMigrateMessage *msg) {}
+
+NQueen::NQueen(QueenState *m)
+{
+    current_row = m->row;
+    QueenState *new_msg;
+    /*for all possible places in next row */
+    if(current_row == numQueens-1)
+    {
+        CProxy_counter(counterGroup).ckLocalBranch()->increment();
+        //printSolution(m->queenInWhichColum);
+        return;
+    }
+
+    bool conflict = false;
+    for(int i_colm=0; i_colm< numQueens; i_colm++)
+    {
+       /* conflict check (row+1, i_colm)*/
+        conflict = false;
+        for(int j_row=0; j_row <= current_row; j_row++)
+        {
+            //conflict for the same colum
+            if(m->queenInWhichColum[j_row] == i_colm || i_colm - m->queenInWhichColum[j_row] == (current_row+1 - j_row) || i_colm - m->queenInWhichColum[j_row] == -(current_row+1 - j_row) )
+            {
+                conflict = true;
+                break;
+            }
+        }
+        if(conflict){
+            continue;
+        }else
+        {
+             // the next step is reasonable. fire a new child
+            if(numQueens - current_row > grainsize)
+            {
+                new_msg = new QueenState;
+                new_msg->row = current_row+1;
+                for(int __i=0; __i<current_row+1;__i++)
+                    new_msg->queenInWhichColum[__i] = m->queenInWhichColum[__i];
+                new_msg->queenInWhichColum[current_row+1] = i_colm; 
+                CProxy_NQueen::ckNew(new_msg);
+            }else
+            {
+                //sequential solve
+                sequentialSolve(m->queenInWhichColum, current_row+1, i_colm);
+            }
+        }
+    }
+}
+
+void NQueen::sequentialSolve(int queenInWhichColum[], int row, int colum)
+{
+
+    queenInWhichColum[row] = colum;
+    if(row == numQueens -1){
+        CProxy_counter(counterGroup).ckLocalBranch()->increment();
+        //CkPrintf("[%d, %d]\n", row, colum);
+        //printSolution(queenInWhichColum);
+        return;
+    }   
+    bool conflict = false;
+    for(int i_colm=0; i_colm< numQueens; i_colm++)
+    {
+        /* conflict check (row+1, i_colm)*/        /*all existing queens */
+        conflict = false;
+        for(int j_row=0; j_row <= row; j_row++)
+        {
+            //conflict for the same colum
+            if(queenInWhichColum[j_row] == i_colm || i_colm-queenInWhichColum[j_row] == (row+1 - j_row) || i_colm - queenInWhichColum[j_row] == -(row+1 - j_row) )
+            {
+                conflict = true;
+                break;
+            }
+        }
+        // all colums are checked
+        if(conflict){
+            continue;
+        }else
+        {
+            /* the last row , get  a solution. stop */
+             /* the next step is reasonable. fire a new child */
+                sequentialSolve(queenInWhichColum, row+1, i_colm);
+        }
+
+    }
+}
+void NQueen::printSolution(int queens[])
+{
+    for(int i=0; i<numQueens; i++)
+    {
+        CkPrintf("[%d, %d] ", i, queens[i]); 
+    }
+    CkPrintf("\n");
+}
+
+/*
+void NQueen::pup(PUP::er &p)
+{
+    p | current_row;
+    p | queenInWhichColum;
+}
+*/
diff --git a/examples/charm++/NQueen/nqueen.h b/examples/charm++/NQueen/nqueen.h
new file mode 100644 (file)
index 0000000..b757fcd
--- /dev/null
@@ -0,0 +1,34 @@
+#ifndef _NQueenState_H_
+#define _NQueenState_H_
+
+#define MAX 20
+class NQueen : public CBase_NQueen {
+
+public:
+
+    NQueen(QueenState *);
+    NQueen(CkMigrateMessage *msg);
+    
+private:
+    //place another queen
+
+    void printSolution(int[]);
+    void sequentialSolve(int[], int row, int colum);
+
+    //indicate which colum has a queen for each row
+    int current_row;
+
+};
+
+class QueenState: public CMessage_QueenState {
+
+public:
+    int row;
+    int queenInWhichColum[MAX]; 
+};
+
+class DUMMYMSG : public CMessage_DUMMYMSG {
+public:
+};
+
+#endif