可用電腦打! Problem 1 Let’s develop a parallel version for the sequential code below: for (i=0; i<n; i++) for (j=0; j<n; j++) a[i][j]=foo(a[i][j],a[i-1][j],a[i+1][j]); For correctness, the code should check for boundary conditions, but let’s ignore that for now Answering the following questions would help you parallelize the code: Do loop-carried dependencies exist in the code? Where are they? Can we parallelize the code by partitioning index i? Can we parallelize the code by partitioning index j? Can we interchange the outer and inner loop indices? Write two parallel versions: one with higher granularity and one with lower granularity ================================================ Problem 2 For the sequential code below: for (i=0; i<n; i++) for (j=0; j<n; j++) a[i][j]=foo(a[i][j],a[i-1][j],a[i][j-1]); Answering the following questions: Do loop-carried dependencies exist in the code? Where are they? Can we parallelize the code by partitioning index i or j? Let’s analyze a case with n=5 Draw a 5x5 array and use arrows to indicate loop-carried dependencies Can you find any degree of parallelism in the dependency graph that you have just drawn? Develop a parallel version that gives the same results ================================================ Problem 3 For the work of the sequential code in Problem 2, someone developed a different algorithm: for (i=0; i<n; i=i+2) for (j=0; j<n; j++) a[i][j]=foo(a[i][j],a[i-1][j],a[i][j-1]); for (i=1; i<n; i=i+2) for (j=0; j<n; j++) a[i][j]=foo(a[i][j],a[i-1][j],a[i][j-1]); Does the new algorithm give the same results? (Again, please ignore boundary conditions). Why? Assume that the new algorithm delivers acceptable results, how would you parallelize it? --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.137.95 ※ 編輯: enswin 來自: 140.112.137.95 (10/29 17:23)