This class wiki serves as both a blackboard for technical discussions and a billboard for information sharing. The organization of this wiki is made as simple as possible but hopefully also effective enough for discussion and Q&A. In general, postings go to one of the four sections below. The Announcements is basically used for reminding students of the class schedule and homework due dates. The on Administration is where you put questions about class administration, for instance, about grading criteria. The other two sections are the places for technical discussions. All the specific questions and issues about the assignments go to on Assignments. The other general questions and comments about the course content go to on Technical Content.

Following a good twiki style, every posting should better be tagged with the author name and the posting time.

-- TongxinBai - 23 Jan 2008

Access Control

Class Website


  • Assignment 1 due date: 2/1. Please use the turnin script on the graduate network to turn in your homework.
    Note: For some technical reason I haven't been granted access to the cs458 account yet. To turn in the the first part of the assignment 1, which is due on 1/28, please send emails to me directly. Sorry about the inconvenience.
    -- TongxinBai 27 Jan 2008
    The turnin script is up now.
    -- TongxinBai 28 Jan 2008

  • For all guest lectures this semester (beginning with Chen Ding's talk on Feb. 20), you are required to write a half-page summary and email it to the TA within two days. -- MichaelScott - 18 Feb 2008

on Administration

on Assignments

I recommend taking a look at /usr/grads/share when you're setting up your account on sync. I've installed, and am technically the maintainer of, up-to-date development tools for sync and swym. You should set your paths to use the current versions of applications as installed. There's no need to reinstall them yourself.

As a side note, the assignment 1 page recommends lung as a single-processor SPARC to test your code on. Keep in mind that lung is Solaris 8 (probably in v8plus mode) and sync is Solaris 10 (I think it's in v9 mode), so you're likely to need different compiler flags on the different architectures if you're doing anything interesting. Lung also mounts the NFS file system so you need to make sure that your .bashrc and .cshrc don't try and do anything funny with a non-SPARC binary when you log in, or you'll wind up with errors.

The installed tools are probably different versions as well, come to think of it. Maybe it's not such a great idea to use the modern tools on sync if you're going to be developing on lung... anyone else's comments are welcome.

-- LukeDalessandro - 24 Jan 2008

When turn in your programming assignments please always remember to include a README, a Makefile and a PDF file for performance evaluation if needed.
-- TongxinBai 28 Jan 2008

In class last time, Michael said to include a "README.pdf" with our submission. Do you (you're grading, right, Tongxin?) want our README file to be a PDF, or does it matter?

-- PaulArdis - 30 Jan 2008

I guess Michael's intention was to use a pdf to show performance data in a graphical manner. In that sense a PDF README is preferred, otherwise you have to include another PDF file for your result evaluation.

-- TongxinBai 30 Jan 2008

Another useful feature that can help with building on different environments is OS = $(shell gcc -dumpmachine | sed -e 's/.*-//' -e 's/[0-9].*//'). If you stick this in your Makefile you can figure out what operating system you are running on and make appropriate paths and things.

-- LukeDalessandro - 31 Jan 2008

It's been noticed that last night someone used the machine for an enormous amount of time causing other people had to wait overnight until they could start their tests. Since our resources are limited and shared, please be considerate and take good control of the time when you are about to launch any testing.

-- TongxinBai 1 Feb 2008

Minor question: When it says, "have each thread run a loop in which it repeatedly enqueues data to, or dequeues from (with 50-50 probability), a shared queue", does that mean that each thread should (for every iteration) flip a coin and decide whether to enqueue/dequeue this time, or should there be a 50% chance on spawning each thread that it is either an always-enqueue or always-dequeue thread? I wasn't sure how to read that "50-50". Thanks.

-- PaulArdis 5 Feb 2008

Based on the paragraph that follows the list of queue types it's the coin-flip style (otherwise there would be no reason to "preallocate" random numbers, and the "preallocation" of nodes would also be odd if a thread is always dequeueing).

-- LukeDalessandro - 06 Feb 2008

An issue that arises is how to deal with an empty queue. The easiest solution is to just fail the dequeue and go on and do whatever your next coinflip tells you to do. The problem with this approach is that this means that in the long run you're going to be enqueueing slightly more often than you dequeue, which will lead to an overall growth trend in the queue. You could precisely compute the probability of dequeueing from an empty queue for any particular insert and adjust your priority accordingly. You could have one "enqueue only" thread but that's going to change the kind of performance that you see. You could just take the easy approach, which is what I'm doing.

As a side note, an alternative to preallocating random bits, which can take up a lot of space and cause strange cache behavior, is to use rand_r which is a reentrant rand call that is thread safe. Also in this case it's possible that a thread can run out of local nodes. It makes sense to allocate another block of local nodes rather than waiting for a dequeue to become available.

-- LukeDalessandro - 07 Feb 2008

A note on unions. The easiest way to implement a counted pointer is with a union. You wind up with something like (in C++):

union counted_ptr {
    unsigned long long ull_for_casx_or_mvx;
    struct {
        Node* ptr;
        unsigned long count;

or, for a templated version:

template <typename T>
struct counted_ptr {
    union {
        unsigned long long ull_for_casx_or_mvx;
        struct {
            T* ptr;
            unsigned long count;

So if you have counted_ptr<Node> head; you can say if (head.ptr == NULL) and you can also say casX(&head.ull_for_casx_or_mvx, ...). This avoids explicit casting and makes code easier to figure out. If you're using C++ you can also give the union or struct members like T* operator->() or nice constructors to make it easier and safer to use.

As a side note, you should be able to template the union version directly, but I can't seem to get g++ to like it when I do. Hope this helps someone.

-- LukeDalessandro - 08 Feb 2008

Assignment 2

There is a question raised about the input format. For the convenience of testing and grading your program is supposed to take inputs from stdin to which I can redirect my test input sets when I test your program. The input format is described in the web page, the first line indicating the number of cities with the following lines giving out the coordinates.

-- TongxinBai - 14 Feb 2008

How to run on linux?

-- XiaomingGu - 15 Feb 2008

java Display <args>

-- MichaelScott - 18 Feb 2008

I've saved a couple of randomly generated inputs to ~cproscia/tsp100.txt and tsp1000.txt on sync. The average length of a random solution to the 1000 vertex problem should be about 5,000,000. I've put my best solutions so far in .sol text files, which should be viewable with

-- CoreyProscia - 21 Feb 2008

Isn't the average length dependent on the scale? Otherwise the absolute value is meaningless. This is just my understanding and has nothing to do with grading. smile

-- TongxinBai

The average length of a random tour should vary with the number of vertices. The range of coordinates should be from 0 to 10,000. I was thinking that the average distance between two vertices would be exactly 5,000, but that is not correct (it might be close though).

-- CoreyProscia - 22 Feb 2008

MPI and OpenMP

In your last programming assignment you'll be working on MPI and OpenMP. Besides the difference of message passing and shared memory, MPI is a library interface whereas OpenMP consists of a set of directives that need special compiler support. Although both of them are language independent we'll be mostly targeting on C. In this assignment your working environment will be on both the department's Linux cluster and the Sun machine (sync). The following guide could be served as a start point.


1. How to program?
Take a look at MPI tutorial from Lawrence Livermore National Lab.

2. Before build and run you might need to set proper values to some environment variables.
A quick solution is save the following script to ~/.cshrc.mpi

foreach n (`seq -s " " 33 64`)
    if (`hostname` == node$ then
        setenv MPI_HOME /u/cs458/mpich-1.2.7-install

if ( `hostname` == )  then
   setenv MPI_HOME /u/cs458/mpich-1.2.7-sync

setenv PATH ${MPI_HOME}/bin:${PATH}

and then copy the following line to the end of your .cshrc

source ~/.cshrc.mpi 

3. How to build?
Basically, like gcc, mpicc could run the errands of both compilation and linking. A detail Makefile could be found at /u/cs458/test_mpi. You may use the directory as a template and plug in your own programs.

4. How to run?
mpirun is the script for launching your mpi tasks. The syntax is

mpirun -np <np> -machinefile <machine-file-name> <program name and arguments> 
np specifying the number of processors to use and the machine file listing the processors to be selected from.

NOTE: All the jobs to be submitted to the cluster nodes ranging from node33 to node64 are subject to centralized management. For detail instructions, please refer to ClusterJobs. In short, you need to wrap your jobs in a shell script and then pass it as an argument to qsub.

Here I wrote a script that could be used in submitting your MPI jobs.

source ~/.cshrc.mpi

#set your machinefile
cat $PBS_NODEFILE > ./cluster_nodes 
#count how many nodes you reserve

#run mpi on these nodes
mpirun -np `cat ./cluster_nodes | wc -l` -machinefile ./cluster_nodes ./linux/<your-mpi-program>   > ./mpi.out

Now you ssh to, enter your mpi working directory and then copy and fix To run your mpi program, just type

qsub -l nodes=4

CAUTION: Since the cluster is a shared computation environment for real tasks you need to be careful to guarantee no running or zombie processes left unattended.

-- TongxinBai - 23 Feb 2008


GCC starts supporting OpenMP from version 4.2.0. On sync, gcc-4.2.0 is installed. To use it as your default gcc, you may save the following three lines to .cshrc.gcc42 and source it before you make and run your OpenMP programs.
setenv GCC_HOME /usr/grads/share/gcc-4.2.0
setenv PATH $GCC_HOME/bin:$PATH
GCC 4.1.2 on Fedora released Linux also supports OpenMP.

For programming guide you may refer to this tutorial.

-- TongxinBai - 23 Feb 2008

Compiling for OpenMP on sync

In addition to using gcc 4.2, you need to compile with the -fopenmp command-line option:
gcc -fopenmp -o foo foo.c

-- MichaelScott - 27 Feb 2008

Perl script for city generation

Here's a simple script that I've been using to generate random sets of cities. You can use it with the command line parameters -p for the number of points (cities), and -s to change the random seed. Output is deterministically the same when run with the same parameters.


use strict;
use warnings;

# command line arguments
my $points = 5;
my $seed = 0;

    # usage string
    my $usage = q(
usage: [p,s,h]
    -h              help
    -p              number of points to generate
    -s              random seed for point generation  

    use Getopt::Long;  
    my $help = '';
    die $usage if !GetOptions('p=i'   => \$points, 
                              's=i'   => \$seed,
                              'h|?' => \$help);
    if ($help) {
        print $usage;
        exit 0;

srand $seed;

    print $points."\n";
    for (my $i = 0; $i < $points; $i++) {
        print int(rand(10000))." ".int(rand(10000))."\n";

This lets you test your program with a command line like: ./ -p 100 | ./tsp | java Display, if the perl script is named and your executable is named tsp.

-- Main.LukeDalessandro - 28 Feb 2008


RSTM can be confusing and frustrating to use at first. Here are a few points that may help.

  • The transactional system only protects objects that inherit from the stm::Object class, that are accessed through smart pointers. Your implementation needs to be object-oriented, at least to the first approximation.
  • Shared class definitions shouldn't define any non-static-constant fields. All fields need to be generated using the GENERATE_FIELD/GENERATE_ARRAY macros, and accessed through the resulting accessors as defined in the "Programming with RSTM" documentation.
  • Shared arrays are currently considered to be one block object, so a thread reading an element of an array that is disjoint from an element that a different thread is writing will be considered a read-write conflict and will (most likely) result in an abort of the reader.
  • If you throw an exception from inside a transaction that is not handled within the transaction it will abort the transaction and then continue to propagate. This seems like the obvious implementation, but you need to remember that anything you did to shared data during the transaction has been "undone" by the abort mechanism. Do not embed any transactionally shared information inside an exception, or you could wind up segfaulting if you try and use it.
  • Be really careful with constructors, and the "this" pointer. Read the relevant sections in the "Programming with RSTM" documentation about them.

I'm sure there will be other issues that you run into. The point of the assignment (I think) isn't for us to struggle with the vagaries of the RSTM package, but to try and come up with an interesting transactional solution to TSP. As such, feel free to email me if you find yourself struggling with something that you think is RSTM specific.

-- Main.LukeDalessandro - 19 Mar 2008

on Technical Content

Edit | Attach | Watch | Print version | History: r36 < r35 < r34 < r33 < r32 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r33 - 2008-03-19 - LukeDalessandro
  • Edit
  • Attach
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback