We present the curricular design, pedagogy, and goals of an introductory-level course on computer systems that introduces parallel and distributed computing (PDC) to students who have only a CS1 background. With the ubiquity of multicore processors, cloud computing, and hardware accelerators, PDC topics have become fundamental knowledge areas in the undergraduate CS curriculum. As a result, it is increasingly important for students to learn a common core of introductory parallel and distributed computing topics and to develop parallel thinking skills early in their CS studies. Our introductory-level course focuses on three main curricular goals: 1) understanding how a computer runs a program, 2) evaluating system costs associated with running a program, and 3) taking advantage of the power of parallel computing. We elaborate on the goals and details of our course's key modules, and we discuss our pedagogical approach that includes active-learning techniques. We also include an evaluation of our course and a discussion of our experiences teaching it since Fall 2012. We find that the PDC foundation gained through early exposure in our course helps students gain confidence in their ability to expand and apply their understanding of PDC concepts throughout their CS education.

We present a model for incorporating parallel and distributed computing (PDC) throughout an undergraduate CS curriculum. Our curriculum is designed to introduce students early to parallel and distributed computing topics and to expose students to these topics repeatedly in the context of a wide variety of CS courses. The key to our approach is the development of a required intermediate-level course that serves as an introduction to computer systems and parallel computing. It serves as a requirement for every CS major and minor and is a prerequisite to upper-level courses that expand on parallel and distributed computing topics in different contexts. With the addition of this new course, we are able to easily make room in upper-level courses to add and expand parallel and distributed computing topics. The goal of our curricular design is to ensure that every graduating CS major has exposure to parallel and distributed computing, with both a breadth and depth of coverage. Our curriculum is particularly designed for the constraints of a small liberal arts college, however, much of its ideas and its design are applicable to any undergraduate CS curriculum.

In line with institutions across the United States, the Computer Science Department at Swarthmore College has faced the challenge of maintaining a demographic composition of students that matches the student body as a whole. To combat this trend, our department has made a concerted effort to revamp our introductory course sequence to both attract and retain more women and minority students.

The proliferation of lidar technology in remote sensing has resulted in extremely large, high resolution point clouds covering a wide variety of terrain. Constructing a grid digital elevation model (DEM) from these large data sets requires extensive computational resources and ample disk space. We propose a framework for leveraging modern computing resources including multi-core distributed systems and general purpose GPU computing to reduce computational bottlenecks and accelerate DEM construction. We employ an I/O-efficient strategy using quad trees to automatically partition the lidar point clouds into a set of independent work bundles. We then distribute these work bundles to multiple GPU-equipped hosts which independently interpolate a portion of the DEM and return partial results. Finally, we gather the partial results and assemble the final DEM I/O-efficiently. Our approach balances I/O, computation, and network communication to reduce bottlenecks. Experimental results show that our approach scales linearly with the number of compute hosts, and achieves speed-ups of 25 × or greater using GPU computing. These results make it practical to use more complex interpolation methods such as regularized splines with tension, which provide geomorphological advantages over simpler interpolation methods such as linear interpolation, nearest neighbor interpolation, or natural neighbor interpolation.

Bare Earth gridded digital elevation models (DEMs) are often used to extract hydrologic features such as rivers and watersheds. DEMs must be conditioned by removing spurious sinks (or depressions) which impede water flow in the model, but are not true hydrologic barriers. This conditioning process is designed to enforce proper drainage and connect real hydrologic networks (rivers) that would otherwise be disconnected in the unconditioned DEM. Primary means of conditioning DEMs include filling sinks and cutting barriers.

We consider the problem of extracting a river network and a watershed hierarchy from a terrain given as a set of irregularly spaced points. We describe TERRASTREAM, a "pipelined" solution that consists of four main stages: construction of a digital elevation model (DEM), hydrological conditioning, extraction of river networks, and construction of a watershed hierarchy. Our approach has several advantages over existing methods. First, we design and implement the pipeline so that each stage is scalable to massive data sets; a single non-scalable stage would create a bottleneck and limit overall scalability. Second, we develop the algorithms in a general framework so that they work for both TIN and grid DEMs. Furthermore, TERRASTREAM is flexible and allows users to choose from various models and parameters, yet our pipeline is designed to reduce (or eliminate) the need for manual intervention between stages.

We develop cache-oblivious data structures for orthogonal range searching, the problem of finding all T points in a set of N points in IRd lying in a query hyper-rectangle. Cache-oblivious data structures are designed to be efficient in arbitrary memory hierarchies.We describe a dynamic linear-size data structure that answers d-dimensional queries in O((N/B)1-1/d+T/B) memory transfers, where B is the block size of any two levels of a multilevel memory hierarchy. A point can be inserted into or deleted from this data structure in O(log2B N) memory transfers. We also develop a static structure for the two-dimensional case that answers queries in O(logB N+T/B) memory transfers using O(N log22 N) space. The analysis of the latter structure requires that B=22c for some non-negative integer constant c.