EECS 419: TAKE HOME TEST 3 3 December 2019
Due: December 11, 2019
Please do all required problems 1-9. You must also do one of problems 10 or 11.
Deliver your answers in Hardcopy form. (source code, results and a README note
delivered by email in a zip file.)
Work your responses to the test problems individually.
Problem 1. – The object of this problem is to explore numerical calculations for the continuum
computation model on mesh or grid type multiple processors. You should model your problem in
C/C++. Assume that you have a square array of points, 16×16, and that the value of the electric
potential function on the boundary is zero on the top row, 20 on the bottom, and 10 along all other
boundary points.
1.1 Initialize the potential function to 0 on all interior points. Calculate the Poisson solution
for the values of all interior points by replacing each interior point with the average value of
each of its neighboring points.
Compute the new values for all interior points before updating any interior points. Run this
simulation for five iterations and show the answers you obtain at the end.
Note: The values on the boundary are fixed and do not change during the computation.
1.2 Repeat the process in the previous problem part 1.1, except update a point as soon as
have computed the new value and use the new value when you reach a neighboring point.
You should scan the interior points row by row from top to bottom and from left to right
within rows.
1.3 The second process seems to converge faster. Give an intuitive explanation of why this
might be the case.
1.4 How do your findings relate to the interconnection structure of a processor for solving
this problem?
Problem 2. – The purpose of this problem is to show the effect of information propagation within
a calculation. Use the Poisson problem (discussed in Problem 1 previously) and write a computer
program in C/C++ that iterates until no point value changes by more than 0.1 percent. Let this be
the initial state of the problem for the following problem parts below, 2.1, 2.2 and 2.3.
2.1 Increase the boundary point at the upper left corner to a new value of 20. Perform five
iterations of the Poisson solver and observe the values obtained.
2.2 Now restore the mesh to the initial state for problem 2.1. Change the problem so that, in
effect, the upper left corner is rotated to the bottom right corner. To do this, scan the rows
from right to left instead of left to right and scan from bottom to top instead of top to bottom.
Perform five iterations of the Poisson solver and observe the values obtained.
2.3 Both problem parts 2.1 and 2.2 eventually converge to the same solution because the
initial data are the same and the physical process modeled is the same. However, the results
obtained from problem parts 2.1 and 2.2 are different after five iterations of the Poisson
solver. Explain why they are different. Which of the two problems has faster convergence?
Why?
Problem 3. – Domain decomposition is a well known technique to solve parallel numerical
problems for large computational grids, i.e. over 106 grid points. The idea is illustrated in Figure
3.1. The original grid is partitioned into small domains of subgrids and then the numerical problem
is solved in parallel in each domain using a uniprocessor architecture. Care should be taken though
to communicate results of processors located in neighboring domains as the computation goes on.
As the number of processors and hence domains is usually rather small, say an order of less than
100, this technique provides modest speedup because it suffers from communication bottlenecks at
the processor domain interfaces. However, the cost of resources is reasonable provided the number
of processors is kept relatively small.
P1 P2
P4P3
Figure 3.1: Domain decomposition Figure 3.2: Mesh of meshes arch
It is proposed to modify the domain decomposition by a parallel mesh-of-meshes architec-
ture style as shown in Figure 3.2 for a 2× 2 domain decomposition. Every grid point of each
2
domain will contain an embedded virtual processor, however, only the top left corner domain,
Domain(0,0), will contain a corresponding mesh of physical processors. The computational
model is simple. The processor mesh computes in parallel Domain(0,0) then it switches onto
Domain(0,1), Domain(0,2) and so on, sweeping through the domains horizontally and vertically,
step by step, until it reaches the bottom right corner domain.
In general, let N×N be the original grid matrix which is partitioned into Q×Q domains such
that every domain has M×M grid nodes where N = M×Q. Thus every full iteration through the
entire grid consists of Q2 iterations through each of the Q2 domains.
To achieves this, every physical processor node should have sufficient local storage to hold
the intermediate results of corresponding nodes when going from domain to domain. However,
to allow for inter communications between near neighboring domain nodes, we will use a wrap
around or torus structure for the physical processor mesh shown in Fig. 3.3.
In what follows we assume that we will use the above Q×Q architecture Figs 3.2, 3.3 to solve
the Poisson potential equation on a N×N grid. The context switching time from domain to domain
may be few cycles, say 5 (instruction) cycles. The grid has been initialized and the initials of every
node are stored in the corresponding processors. Specifically, the initial potential value of the top
grid nodes is 100 whereas all others are initialized to zero.
P12
P8
P4
P0 P1 P2 P3
P5 P6 P7
P11
P15
P10
P14P13
P9
Figure 3.3: Mesh domain architecture
3.1 Formalize the computational model in the form of an algorithmic procedure for the Pois-
son potential equation assuming we use the standard iterative solver.
3.2 Estimate the computation time for your solution assuming that the problem converges
after 1000 iterations.
3.3 Estimate the speedup of the proposed approach (if any) in comparison to the standard
3
domain decomposition technique in Figure 3.1. To be fair you should use the same number
of processors Q2 and same grid size N×N for the domain decomposition in Figure 3.1.
3.4 You should write a C/C++ model for your Poisson solver and simulate your solution to
find the convergence values of all nodes in the mesh assuming that the top boundary initial
values do not change. Assume that N = 104 and Q= 103.
3.5 Get some additional results for different grid sizes N×N. However, only a fraction of
your results will be needed in your answers.
Problem 4. – Consider a 5-dimensional hypercube system, Hyper-5. Assume that you are to
calculate all partial sums of the i items up to the sum of 32 items.
4.1 Construct a program for Hyper-5 that performs this operation in a time that grows as
O(logN) if the number of processors is N. Assume that every processor node in the computer
executes the same program, although the program can be slightly different from node to node
since the processors in the Hyper-5 are independent.
4.2 Show explicitly the instructions that send and receive data between processors. Invent
instructions as you need them and describe what the instructions do. Include some type
of instructions for synchronization that forces a processor to be idle until a neighboring
processor sends a message sends a message or datum that enables computation to continue.
4.3 Which communication steps if any in your answers require communications with pro-
cessors that are not among the five processors directly connected to a given processor? How
do you propose to implement such communication in software (assume that the hardware
itself does not provide remote communication as a basic instruction) ?
Problem 5. Consider a homogeneous multicore machine containing two single-thread processor
cores and four shared memory modules, M1, M2, M3, M4. The cores and memories are connected
via a 2× 4 cross bar switch. A program to be executed on the multicore system is represented
by the data dependency graph of the following figure involving the instructions I1, I2, ..., I12. We
assume instruction execution time 1 cycle, cross bar time 2 cycles and memory reference time 2
cycles. We also assume that the instruction execution and memory reference is consolidated or
not pipelined. The memory access requirements for each instruction are given in the table. We do
consider memory conflicts and cross bar conflicts.
There is a host processor which holds initially the instruction program. The host is responsible
for loading this program on the multicore system. Based on the data dependencies, the host will
load instruction parts to each core for parallel execution. Because of this loading, the cores do not
go through the instruction fetch phase. Assume the decoding time is subsumed by the loading.
4
Then for every instruction, each core needs to access the memory through the crossbar, follow the
access patterns, and get the data back to the core again through the crossbar. At the end of the
computation, the results are in the registers of each core.
5.1 Make a suitable allocation mapping of instructions into the processors of the multicore
system which requires as short as possible computation time.
5.2 Design an algorithm that will systematically solve this problem in this environment, i.e
the 2-processor, 2× 4 cross bar and 4-memory homogeneous multicore system, assuming
acyclic program dependency graph.
5.3 Suppose that the single threaded 2-core system is replaced by 2-threaded single processor
core, keeping the four memory modules and replacing the cross bar by a bus. However, the
instruction execution time is now 2 cycles, the bus transport time averages 1 cycle and the
memory reference time remains 2 cycles. Consider that the data flow program graph consists
of two program threads, i.e.
T1 : I1, I3, I4, I5, I6, I7, I8, I10 and T2 : I2, I9, I11, I12
Redo the above mapping problem 5.1 for the 2-threaded single core system assuming an
additional 1 cycle context-switching penalty. Compare the results to the single threaded
2-core system, problem 5.1.
5
M1 M2 M3 M4
Core 1 Core 2
Multicore Architecture
Host System
1
23
5 6
7 8 9
10 11
4
12
1
2
3
4
5
6
7
8
9
10
11
12
X
X X
X
X
X
X
X
X
X
X
X
X
X
X
Data Dependency Graph Memory Access Patterns
M 1 M 2 M 3 M 4
Problem 6. – A multiprocessor node must sometimes send a message to more than one other
processor, a task referred to as ”broadcasting”. Suppose that a node P0 in an n-dimensional hyper-
cube system has to broadcast a message to all 2n − 1 other processors. The broadcasting is subject
to the constraints that the message can be forwarded (retransmitted) by a node only to a neigh-
6
boring node, and each node can transmit only one message at a time. Assume that each message
transmission between adjacent nodes requires only one time unit. In a two-dimensional system,
for example, P0 could broadcast a message MESS as follows. At time t = 0, P0 sends MESS to P1.
At t = 1, P0 sends MESS to P2 and P1 sends MESS to P3, thus completing the broadcast in 2 time
units.
6.1 Construct a general broadcasting algorithm for the n-dimensional case that allows a mes-
sage to reach all nodes in n time units. Specify clearly the algorithm used by each node to
determine the neighboring nodes to which it should forward an incoming message.
6.2 Apply your algorithm on the designing the 8× 8 heat-flow program (Laplace equation)
to run on a 64-processor hypercube computer that simulates a mesh computer. Specify com-
pletely the function you use to map the problem’s gridpoints onto the nodes of the hypercube.
6.3 Simulate the 16×16 heat-flow problem, i.e. build a C/C++ program to simulate the oper-
ation of a net of 2×2 processor nodes, assuming reasonable communication cost. Tabulate
your results. Comment how would the problem scale to a 256×256 heat-flow problem?
Problem 7. – Consider the following arithmetic expression:
F = (A0 + A1 + · · ·+ A7) × (B0 + B1 + · · ·+ B7)
7.1 Show a minimal height tree implementation of F assuming unlimited processors. Com-
pute the speedup S1 and the efficiency E1.
7.2 Find a minimal height tree implementation of F assuming 4 (four) processors available
each being able to execute the addition or multiplication operation in one time step. Compute
the speedup and efficiency, S2 and E2, respectively.
7.3 Suppose you want to implement F using a 4× 4 mesh connected network. a) Describe
a procedure that implements F in minimal time on the mesh network, also find the speedup
and efficiency of your parallel mesh implementation. b) If your boundary processors are
connected by end-around or wrap-around connections (toroidal connections), show how your
solution improves in terms of the speedup and efficiency.
7.4 Suppose you want to implement F using 8 (eight) processors connected into a 8 node
shuffle network using 4 switching elements and feedback paths (similar network shown in
class). Describe an algorithm that implements F in minimal time using this shuffle network.
Assume that the switches can shuffle a data set in one time step, during the same time the
processors perform an operation on another data set. Compute the speedup and efficiency,
S3 and E3, respectively.
7
7.5 Suppose that we want to implement F using a 4-dimensional hypercube network. As-
sume that the 16 variables Ai and Bi, i= 0,1,...,7 have already been loaded to the 16 nodes of
the cube. Describe an algorithm that will implement F in minimal time using this hypercube
network. Compute S4 and E4.
7.6 Discuss the pros and cons of the above 5 implementations.
Problem 8. – The purpose of this problem is to explore some of the properties of the perfect
shuffle scheme.
8.1 Consider a processor that has the perfect shuffle and pair-wise exchange connections
shown in Figure bellow. For an eight-processor system, show that the permutation that
cyclically shifts the input vector by three positions is realized by some setting of the ex-
change modules. Draw the network unrolled in time to show the setting that realizes this
permutation.
8.2 Repeat the above problem question to show that a cyclical shift of two positions is real-
izable.
8.3 Prove a shuffle-exchange network can realize any cyclical shift in log2N iterations for an
N-processor system when N is a power of 2.
Perfect shuffle network. Tall boxes depict modules that can exchage their inputs.
Shaded modules are reached from Processor 3 via some sequence of shuffle−exchange
8
Problem 9. – Consider the use of a four-PE array processor (PE means processing element or
processor) to multiply two 3×3 matrices. The interconnection structure of the four PEs is shown
in Figure below. Wraparound connections appear in all rows and columns of the array. You need
to map the matrix elements initially one onto each of the processors. All the three multiplications
needed for each output element ci j must be performed in the same PE in order to accumulate the
sum of products. Of course, you are allowed to shift the matrix elements around if needed.
PE 3 PE 4
PE 1
X B = CA
PE 2
9.1 Show the initial mapping of the A and B matrix elements to the processors before the
first multiplication is carried out. (You may have to wrap around the matrix.)
9.2 What are the initial multiplications to be carried out in each processor (there may be
more than one multiplication in each processor) without any data shifting?
9.3 Parallel shifts are carried out in the horizontal and vertical directions. Show the mapping
of the A and B matrix elements before the second group of multiplications can be carried
out.
9.4 What are the multiplications to be carried out in each processor without any further
shifting? (Don’t bother with summing with the previous terms. Summation operations in
dot product operations are embeded in the multiply hardware automatically.)
9.5 Suppose the two matrices have already been allocated as in problem part 9.1. Assume
each processor can perform one multiplication per unit time or one shift in a single direction
9
per unit time for each number. (If you shift two numbers, it takes two units of time.) Deter-
mine the time units needed to complete parts 9.1, 9.2, 9.3, 9.4, respectively. Minimizing the
total time delay is the design goal.
Problem 10. Consruct a shuffle network to compute a second degree polynomial in one variable:
Q(x) = Ax2 + Bx + C. Now consider a second degree polynomial in two variables:
P(x,y) = A2x2y2 + A1x2y + A0x2 + B2xy2 + B1xy + B0x + C2y2 + C1y + C0 (1)
It is desired to evaluate this polynomial on the basis of the shuffle construction for polynomials
in one variable. To do this, you may apply the following transformation:
P(x,y) = Q2(x)y2 + Q1(x)y + Q0(x) (2)
You may assume that that you have four processors available so that each processor can execute
three additions and em multiplications, concurrently. Masking of these operations is possible and
the masks should be shuffled through the computation network. Broadcasting of x and y powers is
possible from the last processor. The four processors are interconnected by a) shuffle connections;
b) linear shift connections (to perform inter-processor additions).
10.1 Construct a shuffle/exchange network to evaluate the second degree polynomial P(x,y).
10.2 Summarize all the steps taken to solve above question.
Problem 11. – Consider the following polynomial in two variables.
P(x,y) = Ax3 +Bx2y + Cxy2 + Dy3
It is desired to evaluate this polynomial on the basis of the shuffle construction for polynomials
in one variable. You may assume that that you have up to eight processors available and each
processor can execute additions and multiplications. The variables x and y are initially shifted into
the processors together with the cofficients A, B, C, D. The processors are interconnected by a)
shuffle connections; b) linear shift connections. Appropriate values are to be shuffled through the
network as arguments of addition or multiplication operations performed by the processors.
11.1 Construct a shuffle/exchange network to evaluate the polynomial P(x,y).
11.2 Summarize all the steps taken to solve the above question.
11.3 Calculate the number of computation time units required to evaluate the polynomial
P(x,y). Assume that it takes one time unit for an addition or multiplication within a proces-
sor, and one time unit for communication or broadcasting between two processors.
11.4 What is the minimum number of processors, and hence the simplest shuffle network, to
solve this problem.
10