Questions
- The labels in a d-dimensional hypercube use d bits. Fixing any k of these bits, prove that the nodes whose labels differ in the remaining d − k bit positions form a (d − k)- dimensional subcube. For this, prove that (a) each such node has exactly (d − k) neighbors at Hamming distance of 1 (Hamming distance between two binary numbers is the number of bit position that they differ), and (b) this subcube is composed of 2(d−k) nodes.
- A mesh of trees is a network that imposes a tree interconnection on a grid of processing nodes. A √p X√p mesh of trees is constructed as follows. Starting with a √p X√p grid, a complete binary tree is imposed on each row of the grid. Then a complete binary tree is imposed on each column of the grid. Figure 2.36 illustrates the construction of a 4 x 4 mesh of trees. Assume that the nodes at intermediate levels are switching nodes. Determine the bisection width, diameter, and total number of switching nodes in a √p X√p mesh of trees (only calculate the order, in terms of big-Oh notation).
- OpenMP Programming
(a) Write a shared memory OpenMP program on Fox server to multiply two n-by-n matrices using p processors with 1<= p <=12. Fill up the matrices with some constant values so that it would be easier for you to verify the resulting matrix for correctness.
(b) Prepare a speedup plot (Ts/Tp) or a table with varying n and vary number of processes in the available range. Use pure sequential time with three nested loop for Ts (see below).
Hint: You may implement the sequential code in the same program and time it, followed parallel code and time that, and calculate the speedup. Experiment and choose sufficiently large n for a reasonable speedup. Larger n may result in better speedup.
/* matrix-matrix product loop */
for (i = 0; i < dim; i++)
for (j = 0; i < dim; j++)
for (k = 0; k < dim; k++)
c[i][j] += a[i][k] * b[k][j];
