TDT 4200 -- FINAL Syllabus Spring 2004

Thursday lectures and recitations are in F6 and F3, respectively

NOTE: Monday and Tuesday lectures are all at 14:15 in ITV 454 on the dates indicated on the syllabus below

Readings are from Pacheco: Parallel Programming with MPI , unless otherwise noted.

  • Tuesday Jan. 6, 8:15-10 -- Lecture 1 & 2:
  • Thursday, Jan. 8, 10:15 -- Lecture 3:

  • Friday Jan. 9, 12:15 -- Recitation 1:

  • Thursday Jan. 15, 10:15 -- Lecture 4:
  • Friday Jan 16, 12:15 -- Recitation 2: Øving 1

  • Thurs Jan 22, 10:15 -- Lecture 5: Pacheco Ch 5: MPI Collective (tentative)
  • Friday Jan 23, 14:15 -- Lect. 6: More on MPI
  • Friday Jan 23, 16:15 -- Recitation 3: Work on Unix tutorial http://www.ee.surrey.ac.uk/Teaching/Unix/

    Please note that this tutorial uses the C Shell, while the default shell at NTNU is the bash shell (GNU Bourne-Again SHell). To change to C shell, just type

    csh

    when you've logged in.

    Section 3 introduces the a2ps command used for printing. To use it you need to know the name of the printer. Most IDI owned machines are configured to use the common printhost. For a list of printers, please see http://printhost.idi.ntnu.no/printers

    Also note that the IDI version of a2ps has a few "quirks", so it's best to use it in piped mode. For example, to print to the printer on our floor, I use the commands

    echo "Hei Hopp" | a2ps | lpr -Pitv443b

    or

    a2ps Makefile greetings.c greetings.pbs | lpr -Pitv443b

  • Monday Jan 26, 14:15 - 15:00 (ITV 454) Lect 7: Efficiency Guidelines/compiler optimizations (handout)
  • Thursday Jan 29, 10:15 -- Lect. 8: Pacheco Ch 6: Grouping Data for Comm.
  • Friday Jan 30, 12:15 -- Recitation 4: Øving 2 handed out

  • Monday Feb 2, 14:15 -- Lect. 9: Timing & Profiling (Ch 4 Goedecker & Hoise), and Optimizations (Handouts based on Ch 1&2 + 14 of Gerber)
  • Thursday Feb 5, 10:15 -- Lecture 10: Communicator & Topologies, e.g. MPI_Cart Slides
  • Friday Feb 6, 12:15 -- Recitation 5: Examples from text
  • Friday Feb 6, 12:30 -- Lecture 11: Pacheco Ch 8: MPI I/O Slides

  • TUESDAY Feb 10: 14:15 (ITV 454) Lecture 12: Pacheco Ch 9: Debugging
  • Thursday Feb 12, 10:15 Lecture 13: Guest lecture by Nils Høimyr, CERN
  • Friday Feb 13, 12:15 -- Recitation 6: Øving 2 -- help
  • Friday Feb 6, 12:30 -- Lecture 14: Pacheco Ch 10: Design and Coding of Parallel Programs
  • Friday Feb 6, 13:15 -- Lecture 15: Pacheco Ch 11: Performance

  • Monday Feb 16, 14:15 -- Lecture 16: Pacheco Ch 12: More on Performance
  • Thursday Feb 19, 10:15 -- Lecture 17: Memory bottlenecks (handout) -- see also Ch 6 in Gerber
  • Friday Feb 20, 12:15 -- NO RECITATION Øving 2 due, Øving 3 handed out electronically

  • Feb 23-March 8 -- NO CLASS -- WORK ON ØVING 3!!
  • Friday, Feb 27, 12:00-13:00 -- Recitation 8: Øving 3 help

  • Friday, March 5, 12:00-13:00 -- Recitation 9: Øving 3 help

  • TUESDAY March 9, 14:15 -- Lecture 18: Performance tools & compiler optimizations (handout) -- see also Gerber Ch 3
  • Thursday March 11, 10:15 -- Lecture 19: Hotspots & arch (handout)-- see also Gerber Ch 4&5)
  • Friday March 12, 12:15 -- No Recitation, but Øving 3 due
  • Friday March 12, 12:30 -- Lecture 20: Pentium 4 Archtitecture (handout) -- see also Gerber Ch 5)
  • Friday March 12, 1315-14:00 or 1500 -- Lecture 21: Guest lecture in Kjel 3

    Today (Friday) at 13:15, Professor Jan Telle from The University of Bergen will be giving two talks in IT-emner. We meet in Kjel 3. Everyone is welcome.

    Abstracts:

    An Introduction to Computer Algorithms

    Algorithms and their design and analysis are at the heart of information technology. Significant advances in algorithms are a crucial factor in the data processing underlying such technological developments as internet search engines, graphics applications and bioinformatics. It is a common misconception that as computers become faster the importance of the time complexity of the underlying algorithms becomes less significant. In fact, the opposite is true: Consider the size of the largest problem one can solve in a given amount of time. When the speed of the computer is increased the factor size(fast)/size(slow) between what an asymptotically fast algorithm and what a slow algorithm can solve will increase.

    Graph Algorithms and Their Applications >p> Many real-world problems are modelled by a binary relation and solved by techniques from the field of graph algorithms. An important goal in the field of graph algorithms is to find large classes of graphs for which large classes of problems are solvable efficiently with practical algorithms. The arguably strongest results in this direction are achieved by the class of graphs of bounded treewidth, containing for example the control-flow graphs of structured programs. We will show how the compiler optimization problem of register allocation can be solved by this connection to bounded treewidth graphs.

  • Monday March 15, 14:15 -- Lecture 22: Algorithms & performance (handout) -- See also Gerber Ch 6
  • Thursday March 18, 10:15 -- Lecture 23: More on algorithms incl. Bit-reversal (handout: Elster (IEEE ICASSP 1989) on "Fast Bit-reversal Algorithms")
  • Friday March 19, 12:15 -- Recitation 10: Review of Øving 3

  • Monday March 22, 14:15 -- Lecture 24: Branching (handout) -- see also Gerber Ch 7
  • Thursday March 25, 10:15 -- Lecture 25: More on Branching, Memory
  • Friday March 26, 12:15 -- Recitation 10: Øving 4 hints
  • Friday March 26, 12:30 -- Lecture 26: More on Memory -- see also Gerber Ch 8)
  • Friday March 26, 1315-14:00 -- Lecture 21: Memory, Approx. circuits (hand out from IEEE COMPUTER magazine March 2004 issue: Shh-Lien Lu: "Speeding up Processing with Approximation Circuits")

  • Monday March 29, 14:15 -- Lecture 27: Slow Operations -- see also Gerber Ch 10 TUESDAY March 30, 14:15 -- Lecture 28: Floating point (handout from Prof. James Demmel, UC Berkeley) -- also available here (PDF file)
  • Thursday April 1 -- NO CLASS
  • Friday April 2 -- Work on øving 4

  • April 3 - April 13 -- EASTER BREAK

  • April 15-20: Work on Øving

  • Monday April 19 -- NO CLASS! (INFOSAM 2020)
  • Thursday April 22, 10:15-11:00: CLASS CANCELLED (Elster on sick leave)
  • Friday April 23, 12-14 -- Attend IDI KDS info meeting for 4th year students

  • Monday April 26, 14:15-15:00 --Pacheco Ch 13: Advanceed Point-to-Point
  • Thursday April 29 -- NO CLASS -- IDI PhD Conference
  • Friday April 30, 12:15-1300 -- Øving review + AMD vs Intel (handout -- also avail on Thorvald's "øving's page")

  • Monday May 3, 14:15 -- Pacheco Ch 14: Parallel Algorithms
  • Thursday May 6, 10:15-11:00 -- Pacheco Ch 15: Parallel Libraries -- LAST CLASS!!

  • Tuesday May 11, 15:00-16:00 -- Review session (Spørretime), ITV 454

  • Thursday May 13, 9:00-13:00 -- FINAL EXAM

    Some material will also be taken from Goedecker & Hoise: Performance Optimization of Numerical Intensive Codes, SIAM 2001, and other handouts as indicated above.

    Re. Ch 15, I will cover PETsc in more detail than in text. See http://www-fp.mcs.anl.gov/petsc/ for details

    This page is maintained by : elster -at- idi.ntnu.no

    Comments welcome. All above notes and assignments for TDT 4200 are COPYRIGHTed by Dr. Elster and/or the author(s). Any copying or further publication without the authors' consent is a COPYRIGHT violation.