Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

--- magistraleinformaticanetworking:spd:13-14-projectproposals [14/07/2014 alle 10:45 (10 anni fa)] – Project description updated Massimo Coppola
+++ magistraleinformaticanetworking:spd:13-14-projectproposals [29/07/2014 alle 14:49 (10 anni fa)] (versione attuale) – [SPD Project Proposals for academic year 2013-2014] Massimo Coppola
@@ Linea 1: / Linea 1: @@
 ===== SPD Project Proposals for academic year 2013-2014 =====
 This SPD project for the current academic year can be selected by any of the students. As explained during the course, the project development and test is still an individual work.
+**The description of the project and the support code can also be dowloaded as an RTF file {{:magistraleinformaticanetworking:spd:spd-13-14-project_description.rtf|here}}, and a zipped text file {{:magistraleinformaticanetworking:spd:spd-13-14-snqueens.c.zip|here}}.**
+**Note (29/07/2014)** -- Additional explanations about some aspects of the project and its algorithm were given to the students in private talks in June and July. They are reported at the end of this web page, [[magistraleinformaticanetworking:spd:13-14-projectproposals#Additional explanations|here]].
 ==== Rules ====
@@ Linea 43: / Linea 47: @@
 http://en.wikipedia.org/wiki/Eight_queens_puzzle
-Other Bibliography on the problem:
+//Other Bibliography on the problem//
 Rodolfo Toledo, Eric Tanter, José Piquer, Denis Caromel, Mario Leyton, "Using Reflexd For A Grid Solution To The N-Queens Problem: A Case Study", in  Achievements in European Research on Grid Systems, Springer, 2008.
@@ Linea 90: / Linea 94: @@
 The example code for the N-queen problem is made available in C, to ease the porting to MPI, TBB or OpenCL kernels.
+<code C>
+#include <stdio.h>
+/*********
+ * reference sequential code for the N Queen problem, SPD course
+ * 2013-2014, Computer Science and Networking, University of Pisa.
+ *
+ * The code is a derivative work of material from wikibooks.org, and
+ * as such the Creative Commons Attribution-ShareAlike License applies
+ * to this code. M. Coppola
+ */
+/** global definitions ******************************************************/
+// largest board size
+#define MAXBOARDSIZE 24
+/*********
+ * levels we expand the problem of before calling the solver
+ * (i.e. before spawning parallel work!)
+ */
+#define EXPANDLEVELS 3
+/********
+ * this type can be used if we need to reliably copy information about
+ * a set of subproblem across parallel instances, regardless of the
+ * program parameters; you will likely need to define functions that
+ * copy/transfer this kind of structures across processes, threads or
+ * larger arrays in order to match your parallelizatin framework of
+ * choice
+*/
+typedef struct boardplus{
+  int size; // board size
+  int x; // this is where we need to restart
+  int y; // idem
+  int board[MAXBOARDSIZE]; // the actual board, padded to largest instance
+} subproblem;
+/********
+ * static variable defining the board size; you may want to make it an
+ * explicit parameter in your code like it's done in function main()
+*/
+static int board_size = 8;
+/********
+ * static variable counting solutions found; in a parallel settings,
+ * you will need to devise a different solution
+*/
+static int solution_count = 0;
+/* count the subproblems spawned from the expander function */
+static int spawned_tasks=0;
+/** utility functions ******************************************************/
+/********
+ * human-readable output; you may need to rewrite it in order to make
+ * it really flexible */
+void putboard(int rows[board_size])
+{
+    int x, y;
+    printf("\nSolution #%d:\n------------------------------------------------------------------\n", ++solution_count);
+    for (y=0; y < board_size; ++y) {
+        for (x=0; x < board_size; ++x)
+            printf(x == rows[y] ? "| Q " : "|   ");
+        printf("|\n------------------------------------------------------------------\n");
+    }
+}
+// simpler printout suitable for automatic analysis
+void dump_board(int rows[board_size])
+{
+  int y;
+  printf("%d", ++solution_count);
+  for (y=0; y<board_size; ++y)
+    printf("\t%d",rows[y]);
+  printf("\n");
+}
+/** computing functions ******************************************************/
+/*******
+ * check that a board position is safe so far; we only need to check
+ * columns and diagonals, as rows are mutually safe by construction */
+int is_safe(int rows[board_size], int x, int y)
+{
+    int i;
+    if (y == 0)
+            return 1;
+    for (i=0; i < y; ++i) {
+       if (rows[i] == x || rows[i] == x + y - i || rows[i] == x - y +i)
+            return 0;
+    }
+    return 1;
+}
+/******* this routine fully expands a sub-instance of the problem
+ * depth first, generating the corresponding set of solutions; it CAN
+ * be used on the whole problem directly, if it is small enough to be
+ * dealt with sequentially */
+void n_queens_solver(int rows[board_size], int y)
+{
+    int x;
+    for (x=0; x < board_size; ++x) {
+        if (is_safe(rows, x, y)) {
+            rows[y] = x;
+            if (y == board_size-1) {
+	      //            putboard(rows);
+	      dump_board(rows);
+	    }
+            else
+              n_queens_solver(rows, y+1);
+        }
+    }
+}
+/******** this routine partially expands the problem by running the
+ * combinatorial search only for the first levels; everything deeper
+ * than that is passed to the solver routine, which is actually where
+ * you can plug in some parallelism
+*/
+void n_queens_expander(int rows[board_size], int y, int expand_levels)
+{
+  int x;
+  for (x=0; x < board_size; ++x) {
+    if (is_safe(rows, x, y)) // early check pruning dead branches
+      {
+	rows[y] = x;
+	if (y == expand_levels-1) {
+	  printf("New subtask %d\n", ++spawned_tasks);
+	  /*******
+	   * here you can spawn parallel work by filling in a
+	   * supbproblem structure wit the available rows, x, y and
+	   * board_size
+	   */
+	  n_queens_solver(rows, y+1);
+	}
+	else
+	  n_queens_expander(rows, y+1, expand_levels);
+      }
+  }
+}
+/** main program ******************************************************/
+/*******
+ * Note: this very simple version of the algorithm always prints all
+ * solutions. You will need to add checks to make this optional */
+int main(int argc, char **argv)
+{
+  int rows[board_size]; // the main board variable
+  int temp;
+  if (argc ==2) {
+    if (temp=atoi(argv[1]), temp >EXPANDLEVELS && temp <=MAXBOARDSIZE)
+      board_size = temp;
+      else {
+	printf("Wrong Size parameter: %d\n",temp);
+	return -1;
+      }
+  }
+  //  n_queens_solver(rows, 0);
+  /******
+   *  expand three levels, then call the full solver routine; note
+   *  that this value is one of the parameters to be tuned when
+   *  parallelizing
+   */
+  n_queens_expander(rows, 0, 3);
+  printf("Found %d solutions over % d taks/subproblems\n",solution_count,spawned_tasks);
+  return 0;
+}
+</code>
+==== Additional explanations ====
+The following should be obvious but it was asked recently.
+  - Students may optimize or replace the sequential code, but are not strictly required to do that. On the one hand, a strongly optimized sequential code will dwarven the parallel speedup of your solution, and spending most of your time in this will not address the key issue and will not raise your evaluation. On the other hand, depending on the parallel solution and technology, some optimizations may be unavoidable in order to achieve a good speedup or obey the limits of your computing platform (memory size and/or bandwidth, parallelism degree, acceptable computation time, degree of software lockout or computation/communication superposition). Recognizing which optimizations are necessary and which ones are not will simplify the development work.
+  - The problem is naturally divided in three stages, from an abstract point of view. It is up to the student to decide if a different decomposition of the work is actually more suited to their technology. The student is expected to be able to explain and discuss his/her choices and motivate them, both in the case they match the abstract problem description and in the case they depart from it. The key question to ask yourself should sound like "would it be possible, sticking to the same platform and framework, to enhance the parallelisation of the problem by changing the parallel structure adopted?"
+  - Unique solutions (also called fundamental solutions) are those which remain after we identify those which happen to be mirrored or rotated of each other. Of course you can choose a representative in each equivalence class in the set of solutionns, then you can only store that representative in the dictionary structure of stage 2 of the problem. Choosing wisely what is the representative and how to find it greatly simplifies the implementation.
+  - Explaining you choices in terms of measured features of the evolving code DOES give extra point. That is, tracing code behaviour in different conditions and for specific subproblems in terms of observable features like memory size, number of recursive calls, achieved load balancing and so on will help you achieve a better solution and be able to analyze it.