In the Spring 2023 semester, a group of Parallel and Distributed Programming (CSC 248/448) students showcased their remarkable research and implementations in a series of presentations. Their projects span a wide range of fields, from optimization algorithms to parallel computing frameworks. Here is some brief Information about their presentations.

1. Aayush Poudel: Ant Colony Optimization (ACO) for the Traveling Salesman Problem (TSP)
   • Aayush Poudel’s presentation revolved around the fascinating application of Ant Colony Optimization to solve the Traveling Salesman Problem.
   • 
2. Matt Nappo: GPU Implementation of ACO for TSP In his presentation
   • By harnessing the parallel processing capabilities of GPUs, Matt demonstrated an efficient implementation of ACO for the Traveling Salesman Problem.
3. Yifan Zhu and Zeliang Zhang: Parallel ANN Framework in Rust
   • Yifan Zhu and Zeliang Zhang collaborated on a project that involved building a parallel Artificial Neural Network (ANN) framework using the Rust programming language. Their framework leveraged the inherent parallelism in neural networks, unlocking increased performance and scalability.
   • 
4. Jiakun Fan: Implementing Software Transactional Memory using Rust
   • Jiakun Fan delved into concurrency control by implementing Software Transactional Memory (STM) using the Rust programming language. STM provides an alternative approach to traditional lock-based synchronization, allowing for simplified concurrent programming. Jiakun’s project showcased the feasibility of utilizing Rust’s unique features to build concurrent systems.
   • 
5. Shaotong Sun and Jionghao Han: PLUSS Sampler Optimization
   • Shaotong Sun and Jionghao Han collaborated on a project to optimize the PLUSS sampler. Their work involved enhancing the performance and efficiency of the sampler through parallelization techniques.
   • 
6. Yiming Leng: Survey Study of Parallel A*
   • Yiming Leng undertook a comprehensive survey study exploring the parallelization of the A* search algorithm. A* is widely used in pathfinding and optimization problems, and Yiming’s research focused on the potential benefits and challenges of parallelizing this popular algorithm.
   • 
7. Ziqi Feng: Design and Evaluation of a Parallel SAT Solver
   • Ziqi Feng’s presentation concerned designing and evaluating a parallel SAT (Satisfiability) solver. SAT solvers play a crucial role in solving Boolean satisfiability problems, and Ziqi’s project aimed to enhance their performance by leveraging parallel computing techniques.
   • 
8. Suumil Roy: Parallel Video Compression using MPI
   • Suumil Roy’s project focused on leveraging the Message Passing Interface (MPI) for parallel video compression. Video compression is crucial in various domains, including streaming and storage. By leveraging the power of parallel computing, Suumil demonstrated how MPI enables the efficient distribution of computational tasks across multiple processing units.
   • 
9. Muhammad Qasim: A RAFT-based Key-Value Store Implementation
   • Muhammad Qasim’s presentation focused on implementing a distributed key-value store using the RAFT consensus algorithm. Key-value stores are fundamental data structures in distributed systems, and the RAFT consensus algorithm ensures fault tolerance and consistency among distributed nodes.
   • 
10. Donovan Zhong: RAFT-based Key-Value Storage Implementation
    • Donovan Zhong’s project complemented Muhammad’s work by presenting another RAFT-based key-value storage implementation perspective. Donovan’s implementation provided insights into the challenges and intricacies of building fault-tolerant and distributed key-value storage systems.
11. Luchuan Song: Highly Parallel Tensor Computation for Classical Simulation of Quantum Circuits Using GPUs
    • Luchuan Song’s presentation unveiled an approach to parallel tensor computation for the classical simulation of quantum circuits. Quantum computing has the potential to revolutionize various industries, but its simulation on classical computers remains a challenging task. Luchuan’s project harnessed the power of Graphics Processing Units (GPUs) to accelerate tensor operations, allowing for efficient and scalable simulation of quantum circuits.
    • 
12. Woody Wu and Will Nguyen: Parallel N-Body Simulation in Rust Programming Language
    • Working together as a team, Woody Wu and Will Nguyen tackled the intricate task of simulating N-body systems. N-body simulations involve modeling the interactions and movements of particles or celestial bodies, making them essential in various scientific domains. In collaboration, they presented their project using various parallel programming frameworks such as Rust Rayon, MPI, and OpenMP. By leveraging these powerful tools, they explored the realm of high-performance computing to achieve efficient and scalable simulations.
    • 

The presentation slides can be found at https://github.com/dcompiler/258s23

Leasing by Learning Access Modes and Architectures (LLAMA)
Jonathan Waxman

November 2022

Lease caching and similar technologies yield high performance in both theoretical and practical caching spaces. This thesis proposes a method of lease caching in fixed-size caches that is robust against thrashing, implemented and evaluated in Rust.

Collaborative Programming and Software Design

Prerequisites: CSC 172 or equivalent for CSC 253.  CSC 172 and CSC 252 or equivalent for CSC 453 and TCS 453.

Modern software is complex and more than a single person can fully comprehend. This course teaches collaborative programming which is multi-person construction of software where each person’s contribution is non-trivial and clearly defined and documented.  The material to study includes design principles, safe and modular programming in modern programming languages including Rust, software teams and development processes, design patterns, and productivity tools.  The assignments include collaborative programming and software design and development in teams.  Students in CSC 453 and TCS 453 have additional reading and requirements.

Syllabus

• SOFTWARE DESIGN
  • Essential Difficulties
    • Complexity, conformity, changeability, invisibility. Their definitions, causes, and examples. Social and societal impacts of computing.
  • Module Design Concepts
    • Thinking like a computer and its problems. Four criteria for a module. Modularization by flowcharts vs information hiding. The module structure of a complex system. Module specification.
  • Software Design Principles
    • Multi-version software design, i.e. program families. Stepwise refinement vs. module specification. Design for prototyping and extension. USE relation.
  • Software Engineering Practice
    • Unified software development process, and its five workflows and four phases. CMM Maturity.
  • Teamwork
    • Types of teams: democratic, chief programmer, hybrids. Independence, diversity, and principles of liberty. Ethics and code of conducts.
• PROGRAM DESIGN USING RUST
  • Safe Programming
    • Variant types and pattern matching. Slices. Mutability. Ownership, borrow, and lifetime annotations. Smart pointers.
  • Abstraction and Code Reuse
    • Iterators. Error processing. Generic types and traits. Writing tests. Modules, crates, and packages. Design patterns: iterators, builders, decorators, newtype, strategy, rail, state. Meta-programming.
  • Meta-programming (453 Only)
    • Declarative and procedural macros. Derived traits.
  • Software Tools
    • Distributed version control. Logging. Serialization.

The full course information and material are released through learn.rochester.edu.

A summary of the student evaluation for the 2021 course.

Workshop Program

Call for Presentations

Data movement is now often the most significant constraint on speed, throughput, and power consumption for applications in a wide range of domains. Unfortunately, modern memory systems are almost always hierarchical, parallel, dynamically allocated and shared, making them hard to model and analyze. In addition, the complexity of these systems is rapidly increasing due to the advent of new technologies such as Intel Optane and high-bandwidth memory (HBM).

Conventional solutions to memory hierarchy optimization problems are often compartmentalized and heuristic-driven; in the modern era of complex memory systems these lack the rigor and robustness to be fully effective. Going forward, research on performance in the memory hierarchy must adapt, ideally creating theories of memory that aim at formal, rigorous performance and correctness models, as well as optimizations that are based on mathematics, ensure reproducible results, and have provable guarantees.

PMHO 2021 is a forum dedicated to the theoretical aspect of memory hierarchies as well as their programming models and optimization.

Format and Topics

PMHO 2021 will be a specialized and topic-driven workshop to present ongoing, under review, or previously published work related to the following non-exhaustive topic list:

• Mathematical and theoretical models of memory hierarchies including CPU/GPU/accelerator caches, software caching systems, key-value stores, network caches and storage system caches
• Algorithmic and formal aspects of cache management including virtual memory
• Programming models and compiler optimization of hierarchical complex memory systems

There will be no formal peer review process or publication, and presentations will be a mix of selections from submissions and invited presentations.

The workshop will take place online Sunday February 28, 2021.

Submission

Submit your presentation proposal to save-g4jFdqmK9rqH@3.basecamp.com. Submissions should consist of an one-page abstract of the topic you intend to present alongside any (optional) pertinent publications or preprints.

The submission deadline is Friday January 22, 2021 AOE.

Organizers

Faculty:

• Chen Ding, University of Rochester
• Xipeng Shen, North Carolina State University

Student:

• Wesley Smith, University of Rochester

Elias Neuman-Donihue, University of Rochester, May 2020

A small correction to Li et. al.’s paper: in section 3.2, the length of a time window is defined as “its end time minus its start time plus one.” However, in section 3.2.1, there is a reference to “windows of length k from 0 k n,” the lower bound of which refers to windows with their end index before their start. This also leads to some mathematical inconsistencies in sections 3.2.1 and 3.2.2.

One such error is the calculation of reuse(1): by the stated definition, an interval of length k=1 has only one allocation, so the reuse should be one if the window also contains a matching free operation and 0 otherwise. Therefore, since there are a total of n windows of length 1, the average reuse of all such windows should be:

However, by the formulae stated in 3.2.2:

In order to standardize the equations with the provided definition of window length, a few changes must be made:

In Eq. 1 and Eq. 2, every instance of should instead read

Then in Eq. 2,

The recursive equations should then read