Fourth Homework
Posted 9 Oct 2004 by herman

This programming assignment uses Python to illustrate the specialist approach to parallel programming.

The homework is due anytime on Thursday 14 October.

Submit your homework using the submit command. The submit command (executed on a CS department machine) will copy a directory containing your homework programs. The command will ask you for a target directory: respond c118/hw4 to that question.

You can actually prepare and test your homework on any computer (at home, under Windows), but you should make sure it works on the CS department linux machines, because that's where we will test it. This homework depends on using the Python implementation of Linda. You can download Linda.py (right-click and download) to the same directory where you'll prepare and test your programs.

Summing over a Vector in Parallel

It's not exactly parallel (using Threads instead of networked hosts), but it is an easy introduction. Your task is to supply missing code to Pyramid.py. The program Pyramid.py imports two subprograms, called pow2lenvec.py and rowaddvec.py.

To make your job easier, you can independently program and test pow2lenvec.py and rowaddvec.py. Once these are working, then test Pyramid.py in the same directory, and it should work.

Problem 1

Download pow2lenvec.py and write the missing code to get it working. It will use Linda operations (T.In and T.Out, as explained in class on Friday 1st October) to remove tuples from the tuplespace and add tuples to the tuplespace. Informally, pow2lenvec transforms one vector into another, but using the "tuple" way of representing vectors; the transform changes tuple names and pads the vector if needed so that the size of the vector is a power of 2. Examples in the docstring of pow2lenvec.py make this clear.

Problem 2

Download rowaddvec.py and write code to get it working. The purpose of rowaddvec is to add pairs of tuples representing a row in the "pyramid" to obtain the row above. See the docstring of rowaddvec.py for examples.

Problem 3

This should be simple: test Pyramid.py using the code you wrote for Problems 1 and 2.

Hints

  • The "T.Dump()" method is a debugging tool, to see what is the content of the tuplespace.

  • Notice that while Linda.py supplies a class called threadingTupleSpace, Problem 1 and Problem 2 do not have any threads. This means that the technique of using the Linda "In" method of fetching a matching tuple cannot wait for another thread to supply the tuple. Fortunately, for these two specific programming problems, there will be an existing tuple present in the tuplespace -- unless you have some bug in your implementation.

  • If you test Pyramid.py and there is a mistake in a program, it may be that the threads get "stuck" waiting. It is my experience (at least on Unix machines) that even a Control-C or Control-D cannot get out of this situation. Usually I open another terminal window on the same machine and enter the command "killall python" to force the stuck program to abort.

Home PageHelp PageView ArticlesView Public DocumentsLogin, do stuff (record diaries)List Group MembersList of Projects