• Sun Dec 21 (11:00 am): Project grades for on-campus students are now available. Again, this does not include the grades for the report, so it is out of 80. If you have any questions, email us as soon as possible. Also, please send emails to both Sanjay and I, since I won't be available after tonight. --Tomofumi
• Tue Dec 16 (2:30 pm): Please submit one tar file/pdf per group for the project. Make sure both names are clearly given in the README and in the report.
• Tue Dec 16 (2:00 pm): Program grades for HW4 have been posted for on campus students. The assignment is out of 200 since it was combined with HW5, but since the report grades are not ready, it is currently out of 180.
• Tue Dec 16 (11:00 am): The due date for the project has been moved to 17th Wed. 5pm.
• Tue Dec 16 (0:00 am): Sorry, but columnwise.c had another bug. It might produce incorrect results with problems with small weights. This was caused by the program not initializing buffer_storage array. Please use a loop to initialize all elements of buffer_storage to 0 to fix thi bug. (This won't fix the previously posted bug)
• Sun Dec 14 (2:00 pm): Please note that columnwise.c has a bug. If the weight of an object is 1, it breaks the program (segfaults and incorrect answers). Until a fix is posted, please don't call it with unit weights.
• Sat Dec 13 (7:30 am): It looks like the divide-and-conquer is still not clear to many students. Here's some more information. In order to solve a KP problem with n objects and capacity c, first check if n=1, if so you can return yes or no depending on whether it's weight is smaller or not than c. If n is greater than 1, then
  1. Find the (last row of) objects 1 ... n/2. Call it T_1.
  2. Find the (last row of) objects n/2+1 ... n. Call it T_2.
  3. Add the two arrays up pairwise but REVERSE one first, so P(k) = T_1(k) + T_2(c-k).
  4. Find the value of k where P is maximized (note that this can be done without actually allocating and storing the P array, just read through T_1 and T_2. Let that value of k be c'.
  5. Recurse on two problems solving the first half with capacity c' and the second half with capacity c-c'.
  There is no backtracking.
• Sat Dec 13 (4:10 am): Note to all students. The enrollments in many CS senior and grad level classes for Spring 2009 is currently very low. If this continues to hold, some classes may be cancelled. If you need a particular class to graduate, and/or if you are particularly interested in a subject, please be sure to register early.
• Wed Dec 11: As if you didn't have enough to do in finals week, here's yet another talk that might be of interest. The speaker is Michael Mantor, Senior GPU Compute Architect/Fellow AMD Graphics Product Group. He will speak on the emerging future of parallel computing. The title is "Entering the Golden Age of Heterogeneous Computing (Multi-core CPUs and Multi-teraflops GPUs, & AMD Stream Computing)." Here are other details (including the teaser of the abstract):
  • What: The rapid advances in the visual compute capabilities of the commodity PC platform are bringing forth a new era of Heterogeneous computing. The combination of powerful multi-core CPUs and multi-teraflop GPUs provide a significant acceleration opportunity for many workloads. Innovative parallel programming models are also emerging to be the main focus in the software community. This talk compares and contrasts the GPU with CPU architectures and also introduces some of the programming interfaces such as Brook+/CAL, Dx11 Compute Shaders and OpenCL for GPU architectures.
  • Where: Lory Student Center room 213-215
  • When: Monday December 15, 2008, 11:00 Reception 11:30 Seminar.
• Tue Dec 9 (8:10 am): We have posted some more details on the project.
• Mon Dec 8 (2:18 pm): Downtime is scheduled for bassi on 12/11/08 from 9 AM to 3 PM. Plan accordingly.
• Sat Dec 6 (4:30 am): Some more good news: thanks to our very diligent systems administrators, we now have access to five more 8-core machines in the department. They are artichoke, arugula, asparagus, bean and beet. N'joy!
• Sat Dec 6 (4:30 am): Contrary to what was previously posted, THERE WILL BE A LAB ON MONDAY DEC 8. It will cover Hybrid MPI-OpenMP programming, since it will be useful for the extra credit part of your project.
• Fri Dec 5 (11:12 pm): This is the list of students who do not (yet) have project partners: Cassie (cdee@simla.colostate.edu), Robert (rwrisley@engr.colostate.edu), Donovan (donovan.mikrot@gmail.com). (This list is current as of posting time).
• Fri Dec 5 (1:51 pm): Lab for Monday, Dec 8 has been posted.
• Tue Dec 2 (12:20 pm): Sanjay's office hours today are cancelled.
• Mon Dec 1 (2:14 pm): A description of the dynamic programming algorithm (including the memory efficient divide-and-conquer algorithm) was posted off the schedule page.
• Mon Dec 1 (2:10 pm): On campus students who do not yet have a project partner should email Kaustubh at kaustubh [at] cs.colostate.edu as soon as possible.
• Mon Dec 1 (10:31 am): Lab today will be an open lab.
• Sun Nov 23 (3:30 pm): Here's some more information on the term project

  The project will be done with a partner of your choice. Here is the list of minumum requirements.

  • Implementation of the complete memory efficient DP algorithm to solve the KP (sequential, and including the divide-and-conquer strategy). It should call the programs you were given for previous assignments.
  • Parallelization of the above in MPI and OpenMP, by simply calling the functions you wrote for the previous assignments.
  • Comparison and analysis of the speedup from each method.
  • Parallelization of the columnwise algorithm in either MPI or OpenMP.
  • For extra credit, you may explore hybrid parallelization (outer MPI, inner OpenMP) of one or more of the earlier parallel algorithms.
• Thu Nov 20 (7:30 am): Information on the term project guidelines will be posted here soon. Happy Thanksgiving

This course will train you to be ready for this challenge. It will teach you the basic concepts of writing, debugging, analyzing, benchmarking, and designing parallel programs. It covers the two main paradigms: shared memory, and message passing. We will also examine a number of parallel algorithms for a range of problems. The class is intended to be very hands-on: you will

1. write a number of programs (in C);
2. run them on the CS department's Unix platforms and on a large scale supercomputer;
3. measure the running time as a function of two parameters (problem size and number of processors);
4. analyze your observations; and
5. write reports on your observations and analyses.

Prerequisites: CS 370 System Architecture and Software or instructor consent. Another key prerequisite is intellectual curiosity.

Tentative Syllabus & Schedule

• Class meets: Tuesday, Thursday 2:00-3:15 PM in Clark A 206.
• Instructor: Sanjay Rajopadhye USC 223, (email: Sanjay.Rajopadhye@colostate.edu), (phone: 491-7323).
  Office Hours: Please see Sanjay's weekly schedule.
• Graduate Teaching Assistants: Tomofumi Yuki (email: yuki@cs.colostate.edu) and Kaustubh Gadkari (email: kaustubh@cs.colostate.edu)
  Office Hours: Fri 10-12 in North Lab.
• Textbook: Parallel Programming in C with MPI and OpenMP, Michael J. Quinn (Mc Graw Hill, 2003 ISBN 0-07-282256-2).
• Tentative Grading: Homework/Labs 50%, Midterms 30%, Final Project 20%.
  • Most homeworks will involve writing programs and analyzing them, both analytically and empirically. Assignments must be submitted at the beginning of class on the due date. Programming assignments must be checked in by the time indicated. Late assignments will not be accepted (exceptions may be announced in class or posted).
  • There will be two midterms and a project, but no final exam.
• Final Project For your final project, you will work with a partner and parallelize a complete application, or do a comparative study of different approaches to parallel programming. More on this later.

  The university calendar has scheduled the final exam on Thursday, December 18, 5:50-7:50 PM, in the classroom. We do not have a final exam. Your final project report (the last thing that you will turn in for this class) will be due on Wednesday, December 17 at 5:00 pm.

• Important Information: Be sure to read the Computer Science Department Student Information Sheet. You are expected to be aware of the policies outlined there.