page 1  (1 pages)

CE 110: Homework #10 Parallel Programming and Abstractions (Last Assignment!)March 1, 1996 1

CE 110: Homework #10

Parallel Programming and Abstractions

(Last Assignment!)

Winter 1996

Instructor: Craig M. Wittenbrink

Office: Applied Science Bldg. #309

Phone: (408) 459 4099

Due: Monday, March 11, 1996. Assignments are due at the beginning of class. Please put your full name, and the assignment number on the upper right of the assignment.

Reading assignment: Reader: handouts Choi, Rothnie, Valiant, Chinn, Fulgham, and LaMarca. Complete and turn in the following problems:

P10.A, (Choi) Given that a hypercube link (wire between nodes) costs, c, and a processing

node costs for a hypercube (or -cube) ( ), calculate the cost for a machine that

has 20 nodes, connected like a hypercube (you?ll have to cut wires, or put the extra connections somewhere. Describe what other alternatives are possible (briefly), and why yours is superior to them.

P10.B, (Rothnie) i) What type of cache coherency policy does the KSR-1 use? (recall chapter 9) ii) Describe whether the architecture is a distributed memory, or centralized memory. iii) Describe whether the KSR-1 is a shared address or distributed address machine

P10.C (Chinn/LaMarca) What is the single most important thing for simulation and performance studies?

P10.D (Chinn/LaMarca) The easiest method for a performance analysis is a back of the envelope calculation. Describe the fundamental reason that one cannot rely on these calculations.

P10.E (Chinn/LaMarca) Using a PRAM (parallel random access machine) write a program to compute the product of all values in time O(N/P + logP) time. Use PRAM pseudo code, and comment your program so that one of your classmates would be able to easily read it.

P10.F i) (Valiant/LaMarca)In two sentences, define a bridging model.
ii) in three sentences define slackness.
P10.( optional) do you think slackness will work and/or will TERA succeed?

c2n n c2 c?