MIME-Version: 1.0 Server: CERN/3.0 Date: Monday, 16-Dec-96 23:50:30 GMT Content-Type: text/html Content-Length: 6601 Last-Modified: Tuesday, 27-Feb-96 18:48:42 GMT Homework 2

Homework 2

Handed out: Tue, Feb 13th
Due: Part 1 on Tue, Feb 20th
Part 2 on Tue, Feb 27th

This assignment must be done in groups of two with a different partner than homework 1.Hand in one solution per group (printed, not manuscript).

The little problems below will get you started with writing Split-C programs on the SP-2

1 Measure the LogP parameters for "Split-C/SP2"

Write a program that determines the LogP parameters for the various Split-C remote access primitives. You should determine (produce a table):

  1. the processor overhead on the requesting side

  2. the processor overhead on the serving side

  3. the gap between successive requests

  4. the latency

for the following Split-C primitives:

a. read of an int
b. write of an int
c. get of an int
d. put of an int
e. store of an int

Remember to always time chunks of code in a loop long enough to overcome the granularity and overhead of the clock.

2 Heat diffusion - a small Split-C application

Write a small Split-C program that simulates the diffusion of heat on a surface of arbitrary shape. Display the simulation in an X window.

Background

The dissipation of heat in an object is an example of a diffusive process, which is modeled by a differential equation which, if we assume the material is uniform takes the form:

where is the temperature of the object at position x at time t.

In this problem set, we will look at one and two dimensional objects (wires and plates), but the generalization to 3-D is obvious.

Heat Dissipation in a wire

For an infinite wire with an initial temperature distribution of it can be shown analytically that the temperature distribution at time t=0.25 is

In order to discretize the problem, we first restict ourselves to a finite length of wire, say from x=-2 to x=2 and divide the wire into N sections of length dx = 4/N. The temperature function u(x) becomes u[0...N], where we will let segment 0 be centered at x=-2 and segment N be centered at X=2, so segment N/2 is centered at x=0.

We will also have finite time steps of length dt. As a convenient notation, we will write to mean the temperature of the i-th segment after n time steps. We may approximate the derivatives by

and then replace the differential equation by the ``finite difference equation'':

which allows us to immediately generate one time step from the previous one:

2.1 Sequential test

Use the above scheme on our test problem, i.e., take and run until t = 0.25 holding u[0] = u[N] = 0 for all time. Compare the results to the analytical solution. Try it (on a workstation) for N=64, 128, 256, ... each time varying dt by orders of magnitude. For example, with N=64 try dt = 0.01, 0.001, 0.0001, ... . Hand in a plot of the analytical solution and your experimental one when N=64 and dt=0.001. This approximation scheme is not stable (i.e. the numerical solution will not converge to the true solution) when dt*N*N > 8. Explain your experimental results using this fact.

2.2 Sequential program for 2-D heat diffusion

The generalization of the heat transfer formula for 2-D problems is (assuming dx=dy): Write a program for your favorite workstation that simulates arbitrary shaped plates on a fixed 2-D grid. The easiest is if you use a bitmap editor to draw 2-D shapes and read that into your program. Then allow the user to enter a "hot-spot" and start simulating. Your program should display the progress of the simulation using X-windows. Display every N-th time-step and allow the user to determine N. Keep the display code simple - you're not doing this to win a graphical design contest. Make your 2-D grid cover an area of x in [-2,2] and y in [-2,2].

2.3 Parallel 2-D heat diffusion

Parallelize your heat diffusion code. You should "somehow" divide the 2-D grid among the processors and have each processor simulate its subgrid independently. You obviously need to worry about communicating the boudary regions. Also, be sure to choose the grid size and time step wisely so that your solution will converge.

Simulate the following shapes: a large disk with a hot spot in the center, a long skinny rectangle placed in the upper part of your 2-D workspace with a hot-spot anywhere, and a barbell with a hot spot in the center of one disk. In each case measure the Mflops you achieve per processor. Also measure the ratio between the busiest and the least busy processor.

Note that the part you should parallelize is the actual computation. Don't worry about the initialization or the X-windows display: do that on one processor. For the timings you probably need to turn the display output off (display the first and last time step so you can see that everything worked fine).

For 2.2 and 2.3, produce snapshots of your simulation for the three shapes defined above, with t=0, t=ft/4, t=(3/4)*ft, and t=ft (ft is the final time). For each shape, make sure you use the same grid size, time step, and ft for both the sequential and parallel simulation. Please provide us with the URL to a web page with the snapshots (with enough annotations so that we know which plot corresponds to which case). Color printouts are strictly forbidden.