ENEE459P/ENEE699: Parallel Algorithms
Fall 2010
This page will be updated frequently during the progress of the course.
The updates will include links to corrections and some announcements.
Contact: Please see each
specific programming assignment for contact information.
Announcements
9/28/2010
XMT-HW 1 posted.
10/03/2010
XMT-HW 1 updated: typo fix in XMT-HW 1 (URL at the end of page 1).
10/8/2010
XMT-HW 1 updated: Please fix the typo in the src/Makefile -- /opt/xmt/class10/make/matvec.mk should be replaced with /opt/xmt/class10_fall/make/matvec.mk. Alternatively you can download the homework package again.
10/20/2010 XMT-HW 2 posted.
10/27/2010 XMT-HW 2 update: Please see the announcement.
11/8/2010 XMT-HW 3 posted.
11/22/2010 XMT-HW 3 update: Due date is extended to November 23, 2010, 11:59pm
11/28/2010 XMT-HW 4 posted.
12/1/2010 XMT-HW 4 definition is updated. Please download again.
12/1/2010 XMT-HW 4 update: Please see the announcement.
Essential documents and links
Assignments
Additional Helpful Documents
Additional information for the assignments
- To connect to the class server, you will need an
account and password. These have been handed out in class individually.
- Use an ssh client to connect to the class server.
Use paraleap.ece.umd.edu as
the server name, and the account and password from above to
authenticate.
Additional Information About the XMT-HW4 (Floyd's Algorithm)
- You should put your README file in the doc directory.
- Do not create a file named TIMINGS. Put your timing information in table.txt in the doc directory.
Additional Information About the XMT-HW2 (Breadth-First Search)
Question 1: How do I check the correctness of my solution?
You can check the correctness of the result for the hexagon graph by inspecting the printed output and comparing it to Fig. 2 in the homework definition. Correctness of the result for the large dataset can also be verified by inspecting the output. See the note in Sec. 3.3, the "large" item.
If you are confident that your serial program is correct, you can check the parallel version by putting both serial and parallel codes in the same XMTC program and comparing the level output from serial and parallel versions.
Question 2: Can I use the single-spawns (sspawn) in my code?
The parallel solution should be programmed without using any sspawns. Instead use nested spawns i.e. "spawn(){ ... spawn(){...} ... }". Some students pointed out that the user's manual inscorrectly states: "spawn statements cannot be nested". We are revising the user's manual to say the following instead: "if spawn statements are nested, the current compiler will replace inner spawn statements by (sequential) for-loops.".
Question 3: What is the antiparallel array in Figure 1?
The antiparallel array was accidentally left in the figure during the revision of the homework. It is irrelevant and removed from the figure now.
Question 4: What is the "locks" array in the homework definition used for?
The locks array was accidentally left in the homework definition during the revisions. It is irrelevant and removed from the definition now. However if you have used it in your code you do not need to change anything. The array is not removed from the header files.
Question 5: Why do I get the "Execution terminated with timeout." message from the FPGA?
FPGA times out when your code has a deadlock or it takes a long time to execute. All jobs in the FPGA is given a time limit that should be sufficient for the homework so one job does not starve the server.
If your code goes into deadlock when you REMOVE or ADD a print statement, I would say you have a parallelism bug (such as a race condition). It is typical for these bugs to appear randomly: sometimes a code that seems to be working (correctly or not) might change its behavior when you add a new statement or even run it on a different machine. Note that a parallel program is correct only if all execution paths that result from indeterministic factors (such as the ones caused by ps instructions, for example) terminate correctly. In your case, I think your program takes a correct path when you add the print statement and takes a wrong one when you remove it.
Question 6: What does $ return inside of the inner spawn? How do you access both thread numbers inside the nested spawn?
$ always refers to the ID of the virtual-thread of the current spawn block. For example
spawn (lo, hi) {
$ = outer_$;
spawn (lo_inner, hi_inner) {
$ = inner_$;
}
$ = outer_$;
}
Think of $ as a local variable declared at the beginning of a spawn. An inner spawn declared a local variable of the same name that hides the outer one for the scope of the inner spawn-block. To access both in the inner spawn block you will have to assign the outer_$ value to an other local variable of the outer spawn (one that is visible to the inner spawn block).