Home
Contact
Syllabus
Homework
Classnotes
Calendar
Cluster
Exam Sampler
Exam Sampler II
Exam Sampler III

Check your grades on Eagle

Homework is assigned on a weekly basis, during class.

Homework is due on the date indicated on the class calendar, as found in the course syllabus.   Actually, you can turn it in after the deadline with no loss of points, as long as it gets turned in before the grader is ready to grade it.  I promise that the grader won't get to it before 9:00am the day following the due date.

If you don't get your homework turned in before the grader is ready to grade it, then you should stop worrying about it and get on with your life, because it will not count toward your grade in the course.

To turn in your homework, visit http://eagle.cs.usu.edu .  

You can turn in your homework in plain text, word, rtf, or in html format.

Each homework assignment is worth 10 points.  I am much more interested in reading about how you solve a problem than in the actual answer you come up with.  Often times, two completely different answers will be graded as 'correct', based on the underlying assumptions the student(s) made when solving the problem.

hw1

Chapter 1, problems 1,2,3,4,5,7.  Here is a scan of the chapter 1 problems from text.  You may use any handy network to answer questions 4, 5, and 7.

If you wish, you may substitute problems  2.1, 2, 2, and 6 from the Kumar book for problems 1.4,5, and 7 of the Wilkinson book.

hw2

1. Chapter 1, problem 10.  Addendum: Focus on when to discard older processors.  Use your results from the next problem to illustrate your discard policy.
   
2. For fun, make a graph of processor speed versus price for the intel 8086/pentium processor family, based on information you can glean from the web.

hw3 

1. hw2 - Read http://arstechnica.com/cpu/2q00/klat2/klat2-1.html.
   
   To what switches might one hook 64 PCs to if one wanted to create a 64-node homegrown parallel processor using 24-port switches, and 4 NICs per PC?
   
2. Write an algorithm that uses a series of hypercube operations that can transform any source pE address into any destination PE address.
   

hw4

1. Show how any interconnection function that is performable on the binary n-cube (hypercube) in one step is performable on a PM2I network in exactly two steps.
   
2. Given an 8-input Omega network, determine which 8-PE PM2I interconnection functions are possible, and which are not.
   
3. Draw an 8-input Benes network, and show the proper switch settings for the following permutation 
   
   (0 1 2 3 4 5 6 7)  to (3 1 5 2 7 4 0 6)

hw5

Write an MPI program and execute it on the cluster.  

    Your program should add all the integers in a list.  

    Make your program in the "master/slave" style.

    Have the master process send data segments to the slave processes.

    How large should the list of integers be before using two 
    processors is advantageous?  4 processors?  8 processors?

hw6

Write a serial program that creates a 512x512-pixel mandelbrot image in ppm format and run it on one of the nodes in the

Your program should accept three doubles as input: Re0, Im0, and Re1.  Im1 should be calculated as Im0 + (Re1-Re0) (i.e. you should generate a square mandelbrot image).

Pick a nice color scheme for your Mandelbrot images, and look at a few of them, just for fun.

Try to get some timing results from running your program

Make your mandelbrot program run as quickly as possible  on the  cluster by taking advantage of MPI library routines.

Try to get some timing results from running your program.

Write up a report for me describing your experiences.  Let me know what your code is and what some of your timing results are.  Experiment.  Have fun with it.   A text-only report is acceptable, as long as you email it to me in the body of the email message, not as an attachment.  You may also create a webpage for your report and send me the URL.

hw7

Make a game of life.   Create a 'world' of 1024 by 1024 cells, without edge connections (i.e., the world is 'flat' with 'edges' that organisms can 'fall off' of).

The rules for the game of life are:

Test to see if your program is working by creating a 'glider' at one edge of the world and tracking it as it crosses the problem space.  A glider looks like this:

Where the black cells represent organisms and the white cells represent spaces.  A glider is a repeating pattern that slowly moves across the space.  If you track the total number of organisms (and the processor that contains them) in a space that starts with one glider, you'll find that the number of organisms does not vary, but the location does.

You might also try a glider 'gun' that periodically generates a glider and sends it out into the world:

After you are sure that your program is working correctly, seed the entire space with organisms so that there is a 1-in-5 probability that any one cell initially contains an organism.

Be sure to correctly implement pseudo-random number generators over your processor set.

That being accomplished, make your program run as quickly as possible.   Provide timing information on a 'per day' basis, and chart your program versus the number of processors used.

This program will be due Wednesday, April 5.

Try to get some timing results from running your program.

Write up a report for me describing your experiences.  Let me know what your code is and what some of your timing results are.  Experiment.  Have fun with it.   A text-only report is acceptable, as long as you email it to me in the body of the email message, not as an attachment.  You may also create a webpage for your report and send me the URL.

hw8

Sender-Initiated Distributed Random Dynamic Load Balancing with White/Black Ring Termination.

For this assignment, you are to write a system that performs sender-initiated distributed random dynamic load balancing.  Here are some of the particulars, which you should feel free to modify:

The basic unit of work, a task, is represented by an integer i in the range [1-1024], is to increment an integer i^2 times.

Each process has a queue in which it places tasks to perform.

Each process is to perform the following actions:

Additionally, your system is to implement  a white/black termination algorithm, so that your system terminates normally.

Your report should track discuss you implementation, and should track the number of tasks performed and overall utilization for each process.

hw9

Solve the traveling salesperson problem.   The traveling salesperson problem is to visit a number of cities in the minimum distance.   The following pairs of integers represent geographic locations of cities on a Cartesian grid.  The cost to travel between any two cities is equivalent to the Euclidian distance between them.  Your goal is to find a low-cost in a small amount of time.  One of the elements of your report is a graph showing your best solution so far versus the time your algorithm spends on it.

hw10

minimum sum vertex cover

For problems or questions regarding this site contact the class Web Lackey.
Last updated: January 07, 2008.