Differenze

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

--- magistraleinformaticanetworking:spm:spm14exe1 [11/11/2014 alle 16:00 (11 anni fa)] – [Eratostene Crivello] Marco Danelutto
+++ magistraleinformaticanetworking:spm:spm14exe1 [17/12/2014 alle 06:29 (11 anni fa)] (versione attuale) – Massimo Torquati
@@ Linea 67: / Linea 67: @@
       * discards the received number if it is a multiple of the stored integer
   * after EOS, each stage prints its stored number (a prime number)
+<code>
+
+[GEN] ---> [CHK( )] ---> [CHK( )] ---> [CHK( )] ---> [DISCARD]
+
+[GEN] ---> [CHK(2)] ---> [CHK( )] ---> [CHK( )] ---> [DISCARD]
+       3
+[GEN] ---> [CHK(2)] ---> [CHK( )] ---> [CHK( )] ---> [DISCARD]
+       (4)   3                                           4 discarded
+[GEN] ---> [CHK(2)] ---> [CHK( )] ---> [CHK( )] ---> [DISCARD]
+       5
+[GEN] ---> [CHK(2)] ---> [CHK(3)] ---> [CHK( )] ---> [DISCARD]
+       (6)   5                                           6 discarded
+[GEN] ---> [CHK(2)] ---> [CHK(3)] ---> [CHK( )] ---> [DISCARD]
+       7                   5
+[GEN] ---> [CHK(2)] ---> [CHK(3)] ---> [CHK(5)] ---> [DISCARD]
+</code>
 ==== Adding stages to a pipeline ====
 A pipeline may be created and stages may be added by invoking the method add_stage, e.g. as in <code>myPipe.add_stage(new Stage(...))</code>
+===== Prime numbers in an interval =====
+Consider the possibility to list all the prime numbers in an interval [MIn, MAX] by:
+  * splitting the interval in a number //nw// of subintervals
+  * assigning each subinterval to a farm worker
+  * the worker
+    * for each i in the interval
+      * checks if i is prime
+        * either using the test a^(i-1) mod i == 1?  (this may give false positives)
+        * or using the test at [[http://en.wikipedia.org/wiki/Primality_test|this page]]
+This implies using a completely different parallel pattern with respect to the previous exercise, of course.
+=== Sample solutions ===
+Sample solutions for the prime number examples [[sample_prime14|here]]
+====== Class work 3 ======
+===== Matrix multiplication =====
+Implement a C++ program computing the standard ijk matrix multiplication algorithm between two matrices A and B of size MxP and PxN, respectively.
+Then parallelize the code using the FastFlow ParallelFor and ParalleForReduce patterns. Implement three versions:
+  * ParallelFor applied to the first (external) loop (index //i//)
+  * ParallelFor applied to the second loop (index //j//)
+  * ParallelForReduce applied to the third loop (index //k//)
+The seq ijk matrix multiplication code looks as follows:
+<code>
+for(size_t i=0; i<M; i++)
+  for(size_t j=0; j<P; j++) {
+    C[i][j] = 0.0;
+    for(size_t k=0; k<P; k++)
+       C[i][j] += A[i][k]*B[k][j];
+  }
+</code>
+=== Sample solutions ===
+See the matmul example in the FastFlow tutorial source code.
+====== Class work 4 ======
+===== Macro Data-Flow matrix multiplication =====
+Implement by using the FastFlow MDF pattern (ff_mdf), the matrix multiplication algorithm starting from the following sequential code (matrices are of size NxN, double precision elements) :
+<code>
+for(size_t i=0;i<N; ++i)
+  for(size_t j=0;j<N;++j) {
+    A[i*N+j] = i+j;
+    B[i*N+j] = i*j;
+  }
+for(size_t i=0;i<N; ++i)
+  for(size_t j=0;j<N;++j) {
+    C[i*N +j] = 0;
+    for(size_t k=0;k<N;++k) {
+      C[i*N + j] += A[ i*N+k ]*B[ j*N+k ];  // B is transposed !
+    }
+  }
+</code>
+The initialization of the two matrices A and B has to be overlapped with the computation of the elements of the C matrix.
+{{ http://calvados.di.unipi.it/storage/teaching/SPM1415/matmul_mdf.png?500 }}
+=== Sample solutions ===
+Sample code [[sample_mmmdf14|here]].
+====== Class work 5 ======
+===== Map skeleton with dynamic scheduling =====
+=== Sample solutions ===
+Sample code [[sample_dynmap14|here]],