Shaotong Sun

This post is written for an assignment for CSC 252 based on my tutorial given at ACM Chapter workshop titled “General Introduction of Parallel Programming Schemes in Different Languages.”

Rust, like C or C++, is a system-level programming language, but unlike C and C++, it has more features on memory safety issues and useability. In other words, it “gives you the option to control low-level details (such as memory usage) without all the hassle traditionally associated with such control.”¹

For installation of the Rust, please refer to https://doc.rust-lang.org/book/ch01-01-installation.html.

Ownership in Rust

As mentioned above, Rust language is designed to focus on memory safety issues. To this end, Rust uses something called Ownership. “Ownership is Rust’s most unique feature and has deep implications for the rest of the language. It enables Rust to make memory safety guarantees without needing a garbage collector.”² On the highest level, ownership means that some variable owns some value, and the can only be one owner for a value at a time. Specifically, the Rust Book defines the ownership rules as:

Ownership Rules

• Each value in Rust has an owner.
• There can only be one owner at a time.
• When the owner goes out of scope, the value will be dropped.

https://doc.rust-lang.org/book/ch04-01-what-is-ownership.html

This ownership concept not only solves the memory safety issues but also makes writing concurrent programs much more accessible than expected. Having ownership makes issues such as data race compile-time errors rather than runtime errors in many cases.

Rayon in Rust

Like OpenMP and OpenCilk in C and C++, Rayon is a data-parallelism library in Rust that helps you write parallel code safely and quickly, which eases you from manual manipulation of threads.

There are two ways to use Rayon:

• High-level parallel constructs are the simplest way to use Rayon and also typically the most efficient.
  • Parallel iterators make it easy to convert a sequential iterator to execute in parallel.
    • The ParallelIterator trait defines general methods for all parallel iterators.
    • The IndexedParallelIterator trait adds methods for iterators that support random access.
  • The par_sort method sorts &mut [T] slices (or vectors) in parallel.
  • par_extend can be used to efficiently grow collections with items produced by a parallel iterator.
• Custom tasks let you divide your work into parallel tasks yourself.
  • join is used to subdivide a task into two pieces.
  • scope creates a scope within which you can create any number of parallel tasks.
  • ThreadPoolBuilder can be used to create your own thread pools or customize the global one.

https://docs.rs/rayon/latest/rayon/

This tutorial will only cover the most basic method of parallelizing matrix multiplication using Rayon, which is using parallel iterators (more can be found at: https://docs.rs/rayon/latest/rayon/).

The most naive way of matrix multiplication in Rust is shown below:

fn seq_mm(a: &[f64], b: &[f64], c: &mut [f64], n: usize) {
    for i in 0..n {
        for j in 0..n {
            for k in 0..n {
                c[i * n + j] += a[i * n + k] * b[k * n + j];
            }
        }
    }
}

By using par_chunks_mut, we can divide the matrix c into n distinct, separate sections, with each section smaller than or equal to n. Rayon then automatically processes these sections in parallel for us.

fn par_mm(a: &[f64], b: &[f64], c: &mut [f64], n: usize) {
    c.par_chunks_mut(n)
        .enumerate()
        .for_each(|(i, c_row)| {
            for j in 0..n {
                for k in 0..n {
                    c_row[j] += a[i * n + k] * b[k * n + j];
                }
            }
        });
}

With n=1000 and no other optimizations (meaning cargo run), the sequence matrix multiplication takes around 7 seconds to finish, while the parallel matrix multiplication takes only around 2 seconds.

Conclusion

In conclusion, Rayon in Rust seems to be beginner-friendly and easy to use, producing a relatively good performance without much work. If you are interested in Rayon or Rust, be sure to check out the Rust Book.

1. https://doc.rust-lang.org/book/ch00-00-introduction.html ↩︎
2. https://doc.rust-lang.org/book/ch04-00-understanding-ownership.html ↩︎

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.