CS160 Spring 2000 Berman/Papadopoulos Homework #1
Due at 14 April 2000
1. For the following machines describe
a. Type of processor used (bit-serial, vector, cache, proprietary)
b. Interconnection network (mesh, ring, torus, SMP, etc.)
c. Largest configuration supported
d. Its Flynn Taxonomy (SIMD, MIMD, etc)
Connection Machine CM-2, Cray T3E, Cray SV-1, Denelcor HEP, Intel Paragon,
SGI Origin 2000, Sun Enterprise 10000, Cray T90.
2. What is the diameter of
a. NxN 2D-Torus
b. D-dimensional mesh with N processors in each dimension
3. Suppose we want to embed a 5x5 mesh into a hypercube. What is the smallest dimension cube where this is possible? Make a 5x5 table and show the node mapping. In general, what is the smallest dimension cube needed to embed an NxM mesh.
4. Use the e-cube routing algorithm to show the hops taken in from the following pairs of nodes in a 10 dimensional hypercube
a. 0 to 1023
b. 313 to 418
c. 0 to 256
5. Go to www.netlib.org. What is the fastest machine according to the Nov 1999 Top 500 survey? Estimate the aggregate computing power of the top 20 machines (Peak and sustained). Of the top 10 machines, which one exhibits the highest efficiency?
6. Describe the key differences between a wormhole-routed network and a store-and-forward packet-switched network.
7. Suppose you want to transfer a 1000 byte message on 10^6 byte/sec network. Calculate the latency through 1, 5, and 10 hop networks
a. Circuit-switched network with control packet length of 50bytes
b. Store-and-forward Packet-switched network
c. Virtual-cut through network with header length 10 bytes
d. Wormhole-routed network with flit length of 1 byte
8. Devise an efficient way that a scatter operation can be done on an nxn mesh. What is the time complexity?
9. Write a data-parallel (SPMD) version (pseudo code) for the even-odd transposition sort algorithm on page 277.
10. Write pseudo code to implement MPI_SEND using MPI_ISEND. Write pseudo code to implement MPI_RECV using MPI_IRECV.