This offering of CS315B will be a course in advanced topics and new paradigms in programming supercomputers, with a focus on modern tasking runtimes. As supercomputers have grown much larger and more complex, tasking as emerged as one of the leading alternatives to current bulk synchronous programming models, with the promise of both higher performance and more productive software development.

The course will consist of lectures on supercomputer architectures, a survey of current standard and alternative programming models, and in-depth lectures on proposals for tasking. Students will be given the opportunity to program in Regent (regent-lang.org), a high-level language for the Legion tasking model. Regent provides a high level of programming abstraction while still enabling programmers to target and efficiently exploit massive supercomputers. There will be a number of lectures on and programming exercises in Regent, and there will also be a course project in which students will write a significant supercomputer application of their own choosing.

The course is open to both computer scientists and computational scientists who are interested in learning about new approaches to programming modern supercomputers. Because it is desirable to have such a mix of students, the course will not assume much background, though good programming skills will be needed to get the most out of the course.

- Time: Tuesdays and Thursdays, 3:00pm - 4:20pm
- Location: School of Education Room 206
- Readings: There is no textbook, but there will be readings assigned from lecture notes and research papers.
- Assignments: Four short programming assignments and a final project.
- Exams: There will be no exams.
- Piazza: https://piazza.com/stanford/fall2018/cs315b/home

Date | Topic | Readings | Lecture Notes |
---|---|---|---|

9/25 (Tue) | Course Introduction | Lecture 1 | |

9/27 (Thu) | Bulk Synchronous and SPMD Programming | [1] | Lecture 2 |

10/02 (Tue) | Introduction to Tasking and Regent Programming | [2], [Regent examples] | Lecture 3 |

10/04 (Thu) | Regions | [Regent examples] | Lecture 4 |

10/09 (Tue) | More on Regions | [3], [Regent examples] | Lecture 5 |

10/11 (Thu) | Circuit Example & Mapping | Lecture 6 | |

10/16 (Tue) | Metaprogramming | [4], [Regent examples] | Lecture 7 |

10/18 (Thu) | I/O and Explicit Parallel Programming | [5], [Regent examples] | Lecture 8 |

10/23 (Tue) | Sequoia | [6] | Lecture 9 |

10/25 (Thu) | Project Proposal Meetings | ||

10/30 (Tue) | Charm++ | [7], [8] | Lecture 10 |

11/01 (Thu) | StarPU | [9], [10] | Lecture 11 |

11/06 (Tue) | Chapel and X10 | [11], [12] | Lecture 12 |

11/08 (Thu) | OpenMP | Lecture 13 | |

11/13 (Tue) | The Case for Tasking | Lecture 14 | |

11/15 (Thu) | Big Data Systems | Lecture 15 | |

11/20 (Tue) | Thanksgiving break |
||

11/22 (Thu) | Thanksgiving break |
||

11/27 (Tue) | Project Meetings | ||

11/29 (Thu) | Review Lecture | Lecture 16 | |

12/04 (Tue) | Project presentations |
||

12/06 (Thu) | Project presentations |

Students are given access to the Certainty cluster for programming assignments. Once the access is granted, it is highly recommended students start assignment 0 early so that students get themselves familiar to the programming environment. Students can also run Regent programs locally on their own machines. For setting up and running Regent, please refer to regent-lang.org.

Title | Due | Code |
---|---|---|

Assignment 0: Running a Regent program on GCP | 10/09 (Tue) | |

Assignment 1: Edge Detection | 10/18 (Thu) | assignment1.tar.gz, test outputs |

Assignment 2: Parallel Edge Detection | 10/25 (Thu) | assignment2.tar.gz |

Assignment 3: PageRank | 11/01 (Thu) | assignment3.tar.gz, TA's solution |

Assignment 4: Parallel PageRank | 11/09 (Fri) | assignment4.tar.gz |

Important: students should send a short project proposal (up to 2 paragraphs) to by Thursday 10/25.

For their final projects, students are expected to write a significant Regent program that can scale up to tens or hundreds of nodes on Certainty. **Students are welcome to come up with their own ideas, especially the ones related to their own research.** For students who do not have a specific topic in mind, here is a list of some project ideas:

Create a code for the solution of the compressible Euler / Navier-Stokes equations, which are statements of mass, momentum, and energy conservation in a fluid, on uniform structured grids (2D or 3D). Use a second-order discretization in space (centered or upwind schemes for the convective term, e.g., JST or Roe, and a centered scheme for the viscous fluxes) and an explicit time integration scheme (e.g., classical fourth-order Runge-Kutta). For an example of this type of fluid solver (and some test cases), see the Soleil-X code.

Port a code for solving the incompressible Navier-Stokes equations (Boussinesq approximation) for computing the flow within a thermally driven 2D cavity. The code uses structured, collocated grids with an implicit discretization (SIMPLE fractional step). Time integration is accomplished through a first- or second-order backward difference formula (BDF). An incomplete LU decomposition is used for solving the linear systems, including a pressure Poisson solve. Examples and details can be found in Computational Methods for Fluid Dynamics, Ferziger & Peric.

Create a linear solver for symmetric, positive definite matrices using the Conjugate Gradient (CG) method. For example, the poisson equation with a known source term on a uniform 2D mesh can be solved. Other Krylov methods can be considered instead, such as GMRES or Bi-CGSTAB, which handle more general matrix types. Similarly, unstructured meshes could also be considered here, leading to sparse matrices that can be stored in Compressed Sparse Row (CSR) format.

- An Introduction to the Conjugate Gradient Method Without the Agonizing Pain
- OpenMP implementation that solves the Poisson equation with CG using a CSR matrix representation

Solve the Poisson equation on a regular 2D grid with a multigrid method. Use a second-order finite difference discretization with Dirichlet boundary conditions. The discretization results in a linear system with a banded matrix structure, which can be solved with classical iterative methods alone or a geometric multigrid method that uses the classical iterative methods as smoothers on the various mesh levels.

Solve the radiative transfer equation on a structured 2D grid using the discrete ordinates method. Implement the source iteration solver with full-domain sweeps. Angular discretization is accomplished using level symmetric quadrature sets or quadrature sets constructed on the fly. Spatial discretization will use the finite volume method with a first- or second-order accurate method (step or diamond differencing).

Implement a fast multipole algorithm in Regent. Fast multipole algorithm is a scalable algorithm for N-body simulation whose time complexity is O(N) and has a wide range of applications including electrostatics, fluid simulations, and astrophysics.

- A Fast Algorithm for Particle Simulations
- A short primer on the fast multipole method
- ExaFMM, an open source FMM implementation
- Legion implementation also available upon request.

Implement parallel fast Fourier transform in Regent. An efficient implementation of parallel FFT has many applications such as dark matter, plasma, and incompressible fluid simulations (to name just a few!). Oddly, the widely used implementations parallelize 3D FFTs in only one dimension, resulting in limited scalability. A 3D FFT implementation that parallelizes in two dimensions should be clean to express in Regent and an interesting computation to map to heterogeneous hardware.

Adaptive mesh refinement is a technique to adjust the resolution depending on the sensitivity or criticality of parts within a simulation. This technique often yields more precise solutions than those that assign resolution uniformly across the mesh. However, the technique also poses challenges in finding the right regions in a mesh to refine and balancing computations between nodes. Writing scalable AMR code in Regent should be an interesting project as the features in Regent, such as asynchronous task scheduling and dynamic task mapping, can help solve some of these challenges.

Implement parallel wavelet compression. Wavelet transforms are one of the most popular time-frequency-transformations and are widely used for data compression, especially image compression; notable applications include JPEG 2000 and DjVu. For good resolution on high-frequency terms, the wavelet compression shows a better compression performance for images that have transient signals.

Implement a two-threshold peak finder algorithm for locating "peaks" in images. This algorithm is currently used for processing data produced by the Linac Coherent Light Source (LCLS) at SLAC. Peak finding is a data processing step that locates regions of charge in the image produced by a detector. The most common peak finding algorithm consists of two steps: First, it finds the initial peaks, the pixels whose intensity is above the higher threshold. Then, it searches for neighboring pixels within a given radius whose intensity is above the lower threshold.

- Peak Finding page at SLAC wiki
- Hit and Peak Finding Algorithms page at SLAC wiki

Today’s X-ray free-electron lasers can generate pulses at 120 Hz, so the pixel-array imaging detectors need to also work at that speed. Furthermore since all the photons are detected in 40 fs, we cannot use the more accurate method of counting each photon on each pixel individually, rather we have to compromise and use the “integrating” approach: each pixel has independent circuitry to count electrons, and the sensor material (silicon) develops a negative charge that is proportional to the number of X-ray photons striking the pixel. It is thus absolutely critical for us to know the gain of the detector, that is, the conversion factor between electronic signal in “counts” and number of photons. (signal counts = gain x photon count, in our definition). Unfortunately, knowledge of the gain has been very difficult to acquire. It differs from pixel to pixel within the pixel array, and is a function of temperature and X-ray energy.

To calibrate the gain field we use a “flood field” source: somehow we rig it up so that several photons will hit each pixel on each image. We don’t know the number of incident photons, and it is not even uniform over the image, but the flux is slowly varying in space, so we can assume that the true flux at pixel A is very similar to the true flux on each of the surrounding pixels. We are assuming Poisson statistics here — the variance in the photon count is equal to the number of photons. The signals we measure are probably in the range of 20 photons per pixel per image. As stated above the critical complication is that the gain varies from pixel to pixel, so for example, the true gain is probably in the range of 8 counts/photon to 30 counts/photon. So we need to determine a gain for each pixel, not a constant value over the whole detector. Also, critically, for each imaging event the detector electronics imparts a “common mode” offset, or DC-offset, such that a random integer number of counts is added to each pixel value. The common mode offset is a random value for each shot (for example it might have a Gaussian distribution with a mean of zero and a standard deviation of 10) but it is constant across all pixels within the shot. But we need to determine it’s unknown value for each shot. So the unknowns to determine are the gain for each pixel, and the common mode correction for each shot. How do we determine these unknowns from the image data?

The basic sensor is a 370 x 190 pixel array. The entire CSPAD detector consists of 32 of these sensor panels. Each has a separate common mode correction for each image, so they should be treated as separate detectors. Assume that we collect a lot of images, say 1000. In the analysis of the data, we should only accept signals that vary smoothly from pixel to pixel where we can assume that the true photon field is locally constant. In other words, Bragg spots and other edge-type features probably have to be rejected on each image.

Port one of the mini-apps developed in the national labs. These mini-apps represent an interesting subset of requirements from the real scientific workloads, so it is worth to explore how well the Regent programming model can fit into those requirements. Here are some mini-apps that are interesting to port:

- LULESH, an unstructured Lagrangian explicit shock hydrodynamics proxy application.
- CoMD, a classical molecular dynamics proxy application.
- CloverLeaf, a Lagrangian-Eulerian hydrodynamics benchmark.

Write a ray tracer in Regent. Choose on your own how much physical phenomena to capture in the ray tracer, but try to make it better than the accompanied reference in terms of image quality.

- Paper about a parallel ray tracer implementation with MPI/OpenMP
- MPI/OpenMP implementation

- Office: Gates 276
- Hours: Monday 4pm - 5pm, Wednesday 11am - 12pm
- E-mail:

- Office: Gates 416
- Hours: Wednesday 1pm - 3pm, Friday 1pm - 3pm
- E-mail: