Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Teaching Parallelism

Expand Messages
  • Lance
    Uzi Vishkin wrote these ideas on how to teach a parallel computing course as a comment on my earlier parallelism post. The basic claim is that: - It does not
    Message 1 of 1 , May 9, 2008
      Uzi Vishkin wrote these ideas on how to teach a parallel computing course as a comment on my earlier parallelism post.

      The basic claim is that:

      • It does not make sense to have a new platform of general-purpose parallel computing succeed the established serial platform without having a one-to-one match of EVERYTHING, including algorithms and data structures.
      • In particular, it does not make sense to teach parallel programming without teaching parallel algorithms and data structures. The gap between programming and algorithms must be bridged, so that the continuum from algorithms and data-structures to programming will resemble as much as possible the continuum in serial computing.
      • Since the PRAM theory is the only serious candidate developed in nearly 3 decades of research, PRAM algorithms have got to be taught.
      I expect theorists to endorse this argument and use it to convince their colleagues that PRAM algorithms need to be taught. But, I have to be frank. I am concerned that some of us will do the following: teach a course on parallel algorithms as a purely theory course WITHOUT any connection to programming. This will miss the point as it ignores the need to relate algorithms to programming. The Q&A at the end of this text elaborate further on the programming issue.

      As others have implied, you can find several fine sources for PRAM algorithms. For this reason, my comments below mostly focus on a way to address the parallel programming issue:

      1. In class presentation.
        1. Read Section 2.1 entitled XMTC in FPGA-Based Prototype of a PRAM-On-Chip Processor. It reviews a modest extension to the C programming language called XMTC that allows PRAM-like programming. XMTC essentially adds only 2 basic commands to C: Spawn and PS (for prefix-sum).
        2. Devote a total of around 15-20 minutes similar to slides 37-39 in these slides to present XMTC. Slide 40 can guide a discussion.
      2. Supporting documentation. The students should then be referred to: the XMTC Manual and the XMTC tutorial.
      3. Programming assignments. Please look up under assignments on this course page.
      4. Running programming assignments. The UMD PRAM-On-Chip project is on track for public release by the end of June 2008 of:
        1. a cycle accurate simulator of the PRAM-On-Chip machine, and
        2. a compiler from XMTC to that machine.
        The will allow your students to run XMTC code on an emulated 64-processor PRAM-On-Chip machine. To remind you, a hardware prototype of such a machine (using FPGA technology) has been in use at UMD since January 2007. A compiler that translates XMTC to OpenMP will also be released, giving your students an alternative way to run their assignments.
      Finally, please note that this type of programming cannot be too difficult. I have given a 1-day parallel algorithms tutorial to a dozen high school students in Fall 2007 and subsequently some of them managed to do on their own 8 programming assignments. In fact, the above link to programming assignments gives these 8 programming assignments. The only help the high school student got was one office hour per week by an undergraduate teaching assistant. They did not get any school credit for their work. Their participation was in the context of a computer club after completing their regular school work (8 periods per day).

      If you are looking for code examples, you are welcome to write to me.

      Here are some Q&A:Q: I never learned parallel programming formally, but I picked up some ideas in my free time from Java/MPI/OpenMP/etc. How do any of these relate to XMTC parallel programming?A: XMTC parallel programming is simpler and different.

      Q: The problem of algorithms being taught independently of programming is present within the exclusively serial world. What would you say to the many theorists who are resistant to the idea of having a heavy programming component in their courses?A: IMHO the serial case is completely different. Most students have experienced/learned serial programming BEFORE taking the serial algorithms course. This is NOT the case for parallel programming. My experience is that students learn best if parallel programming is coupled with parallel algorithms. The main difference is that the parallel algorithms course is where parallel programming should be FIRST taught. The reason is that parallelism requires introduction of some first principles representing an "alien culture" to students. In contrast, serial computing is related to: (i) mathematical induction, (ii) the way our brain instructs our body (as a single processor), etc. There is nothing out there that prepares us for parallel computing.

      Q: What text do you use for teaching parallel algorithms?A: I have been using my class notes.

      Warm thanks to Adam Smith and Aravind Srinivasan for their helpful comments on an earlier draft of this text.

      Posted By Lance to Computational Complexity at 5/09/2008 05:29:00 AM

    Your message has been successfully submitted and would be delivered to recipients shortly.