CS 470 Student Research Projects

When I teach CS 470 (Parallel and Distributed Systems), I teach it with a focus on high-performance computing (HPC) because of my background in that area. In addition, I try to cover many topics relevant to the current research areas in HPC. Thus, this course is an ideal setting for students to conduct research of their own. They do this in the form of a semester-long project conducted with my guidance.

Early in the course (but after we have covered enough introductory topics for the students to have an idea of what I expect), I ask students to submit a project idea and a list of teammates who are interested in that project. Over the first part of the semester, I work with each group to refine that idea into a concrete project proposal. The project usually includes software development, rigorous experimentation, and analysis of results. Over the second part of the semester, I continue to advise them as they complete the work. They submit a brief mid-project report and a project poster for the department symposium, and at the end they submit a final technical report (6-12 pages) alongside their code submission. For their final report I encourage them to use LaTeX and write in an academic style.

This semester-long project not only gives students a chance to experience research, but it requires them to learn how to design a scientific project, run experiments, and write a technical report about their findings. In some cases, I have recommended that exceptional projects revise and submit their final reports as papers to a regional peer-reviewed conference, where several have been accepted.

Here are some examples of projects that students have worked on in past semesters:

    Dolphin Network
  • Analysis of Parallel Implementations of Centrality Algorithms
    Students: Kevin H. Amrein, Sam P. Carswell, and Patricia D. Soriano

    This project explored parallel implementations of three network analysis algorithms for detecting node centrality: betweenness centrality, eigenvalue centrality, and degree and line importance. They wrote all solutions in the C programming language using OpenMP library for parallelization. They evaluated these implementations using five example networks. They then explored the notions of centrality encoded by each measure and compared the parallel scaling performance of each implementation.

  • JMU Cluster Performance Analysis
    Students: S. Paige Campbell, Matthew B. Rohlf, and Michael A. Traynor

    This project explored performance variation on our cluster, inspired by similar work at Kyushu University and Lawrence Livermore National Lab. Using the EP and UA benchmarks from the NAS benchmark suite, they ran single-core experiments to look for per-core variability. They also wrote their own bandwidth saturation test in MPI and used it to perform experiments that detected inter-node communication variation. They found a small amount of per-core variation but a significant amount of inter-node communication variation.

  • Parallelizing Shamir’s Secret Sharing Algorithm
    Students: Joseph K. Arbogast and Isaac B. Sumner

    Dolphin Network This project explored how Shamir’s secret sharing algorithm can be parallelized, decreasing the time required to generate key shares for secrets shared among a large group of participants. Using an open-source C implementation of Shamir’s algorithm and the OpenMP multiprocessing programming interface, they parallelized regions of the algorithm and reduced execution time significantly, seeing near-linear speedup in both phases of the algorithm.

  • Traveling Salesman: a Heuristic Scaling Analysis
    Students: Garrett L. Folks, Quincy E. Mast, and Zamua O. Nasrawt

    This project analyzed two heuristics that approximate solutions to the Traveling Salesman Problem: K-Opt search and Ant Colony Optimization (ACO), with the goal of exploring how these heuristics perform when run in parallel on multiple CPU cores as well as using GPU computing. They found that an existing K-Opt implementation showed impressive parallel performance scaling, especially when executed on a GPU. They also parallelized portions of an ACO implementation and demonstrated good scaling on a CPU, conjecturing that a GPU-based implementation would be even more efficient.