Questions

1. 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^(dk) nodes.

2. A mesh of trees is a network that imposes a tree interconnection on a grid of processing nodes. A p Xp mesh of trees is constructed as follows. Starting with a p Xp 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 Xp mesh of trees (only calculate the order, in terms of big-Oh notation).

3. 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 (T_s/T_p) or a table with varying n and vary number of processes in the available range. Use pure sequential time with three nested loop for T_s (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];