Tangential to CSC 253/453 on software design but fun to explain when there is enough time in a lecture are these two math problems which are general composite properties that can be proved easily using simple building blocks.
Theorem: If a complex value is a root of a polynomial of real-valued coefficients, so is its conjugate.
To prove this for ALL such polynomials, we need just two properties of complex number arithmetic: (1) the conjugate of the sum is the sum of the conjugates, and (2) the conjugate of the product is the product of the conjugates. These are binary operations and can be shown easily. Then for any real-valued polynomial f(x), we have f(~x) = ~f(x) = ~0 = 0, and the theorem is proved.
Theorem: In a triangle, a median is a line from an end point to the center of the opposite side. For any triangle, its three medians meet at one point which is 1/3 the way from the end point to the edge.
To prove this for ALL triangles, we use a property of a single line segment. Let P be a mid-point on the line segment P1P2. Let the (complex-plane) coordinates of P1, P2, P be x, y, z, and the ratio r = P1P / PP2, then we have z = (x + ry) / (1 + r). If we use this equation to compute the coordinate of the 1/3-way point of the three medians, we’ll see that they are identical: 1/3(x1+x2+x3), where xs are the coordinates of the three end-points of the triangle.
Source: An Imaginary Tale — The Story of i, by Paul J. Nahin, Princeton U Press, 1998.
Photo credit: AI generated by Kaave Hosseini for CSC 484 for “dimension reduction”
Chen Ding, Professor of Computer Science MWs 3:25pm to 4:40 Hylan 202
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, software teams and development processes, design patterns, and productivity tools. The assignments include collaborative programming and software design and development in teams. The primary programming language taught and used in the assignments is Rust. Students in CSC 453 have additional reading and requirements.
Behavioral Design Patterns: Command, New Type, RAII Guards, Strategy
Creational Design Pattern: Builder
Trait Object and State Pattern
Meta Programming
Logging and Serialization
Software Engineering
Team
Unified Software Development Process
Testing
Code Review
Human Values
Apportionment
Algorithmic Fairness
Fallibility and Truth Seeking
Past Students’ Comments
“Separation of concern is perhaps my favorite topic in software development right now; I love making software as modular and reusable as possible. Taking CSC 253 also helped me to understand the MVC architecture in mobile app development class almost immediately.” (Fall 2022)
“A huge part of the course is graded on a complete group project. You’re assigned a random group, and you better pray to get group members who show up to class and do their parts.” (Feb. 2023)
“The lessons on iterators truly opened my eyes to a whole new world of thinking about programming, and thinking about modules helped me understand the concept of information hiding and team collaboration, and especially communication and just how important it is. I will be bringing my learnings from your class to Seattle this summer for sure!” (Fall 2022)
“The most meaningful part is doing the final project – DVCS in group with other 4 outstanding classmates. In this project, I learned how Git works, how to apply the design principles into practice, and how to collaborate well with others in programming. The reward didn’t show up immediately when and after the class, but afterward when I looked for an SDE job and prepared for the interviews, I was reminded of what I learned in the CSC453 course and found out how useful it is to my career.” (Fall 2021)
On Rust
“Speaking of languages, it’s time to halt starting any new projects in C/C++ and use Rust for those scenarios where a non-GC language is required. For the sake of security and reliability. the industry should declare those languages as deprecated.” – Mark Russinovich, CTO of Microsoft Azure, author of novels Rogue Code, Zero Day and Trojan Horse, Windows Internals, Sysinternals tools, author of novels Rogue Code, Zero Day and Trojan Horse, Windows Internals, Sysinternals tools, 9/19/2022
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Logic in Coq. Logical Connectives: Conjunction, Disjunction, Falsehood and Negation, Truth, Logical Equivalence, Logical Equivalence, Existential Quantification. Programming with Propositions. Applying Theorems to Arguments. Coq vs. Set Theory: Functional Extensionality, Propositions vs. Booleans, Classical vs. Constructive Logic.
Inductively Defined Propositions. Induction Principles for Propositions. Induction Over an Inductively Defined Set and an Inductively Defined Proposition.
The Curry-Howard Correspondence. Natural Deduction. Typed Lambda Calculus. Proof Scripts. Quantifiers, Implications, Functions. Logical Connectives as Inductive Types.
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.
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.
CSC 253/453 and TCS 453 Collaborative Programming and Software Design
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, software teams and development processes, design patterns, and productivity tools. The assignments include collaborative programming and software design and development in teams. The primary programming language taught and used in the assignments is Rust. Students in CSC 453 have additional reading and requirements.
Prerequisites: CSC 172 or equivalent for CSC 253 and TCS 453. CSC 172 and CSC 252 or equivalent for CSC 453.
Fall 2020 Student Evaluation
Anonymous inputs were collected by the university before the final exam. 14 out of 33 students (44%) submitted the evaluation.
The overall Instructor Rating is 4.21 and Course Rating 4.00.
Among the individual questions, the highest are 4.79 (The instructor was willing to listen to student questions and/or opinions), 4.71 (The instructor demonstrated sincere respect for students), and two COVID related questions both are 4.54 (the instructor clearly articulated course expectations to students, and the instructor noticed when students did not understand course material and adjusted accordingly). The lowest are 3.71 (The exams/assignments were clearly worded) and 3.93 (The instructor used examples that helped with understanding the material).
Recent Advances in the Modeling and Optimization of Caches
Donald F. Towsley, Distinguished Professor, University of Massachusetts Amherst
The keynote lecture covers the following results.
An optimization-based approach to caching
A simple, very accurate model of LRU and variants
A new approach to bounding performance of caching policies based on a very simple ordering of failure rates of request distribution along with an application to on-line caching.
The material is based on the following publications: Deghgan et al. “A Utility Optimization Approach to Network Cache Design,” IEEE/ACM Transactions on Networking, 27(3), 1013-1027, June 2019; “Sharing Cache Resources among Content Providers: A Utility-Based Approach,” IEEE/ACM Transactions on Networking, 27(2), 477-490, April 2019; Jiang et al. “On the Convergence of the TTL Approximation for an LRU Cache under Independent Stationary Request Processes”, ACM TOMPECS, 3(4), 20:1-20:31, September 2018; Panigrahy et al. “A new upper bound on cache hit probability for non-anticipative caching polices,” IFIP WG 7.3 Performance 2020; and Yan et al. “Learning from Optimal Caching for Content Delivery,” Proc. CoNEXT 2021, December 2021.
Workshop Program
PPoPP Workshop on Principles of Memory Hierarchy Optimization (PMHO)
Saturday 4/2/2022 1pm to 5pm US EDT (GMT -4), 6pm to 10pm Germany, 10:30pm to 2:30am India, 1am to 5am China, 2am to 6am Korea
Welcome and Introduction (1pm)
Keynote (1:10pm to 2:00pm)
Don Towsley: “Recent Advances in the Modeling and Optimization of Caches”.
Session 1 (2:00pm to 2:40pm)
Xian-He Sun: “A Study on Modeling and Optimization of Memory Systems”. JCST Jan. ’21. (2:00pm to 2:20pm)
Karim Elsayed: “On the Impact of Network Delays in Time-To-Live Caching”. Unpublished. (2:20pm to 2:40pm)
Break (2:40pm to 2:50pm)
Chen Ding: “CARL: Compiler Assigned Reference Leasing”. TACO March ’22. (2:50pm to 3:10pm).
Nirav Atre: “Caching with Delayed Hits”. SIGCOMM ’20. (3:10pm to 3:30pm)
Benjamin Carleton: “Evaluating the Impact of Delayed Hits in Multi-Level Caches”. SOSP ’21 SRC Undergraduate Winner. (3:30pm to 3:40pm).
Break (3:40pm to 3:50pm)
Nathan Beckmann: “LHD: Improving Cache Hit Rate by Maximizing Hit Density”. NSDI ’18. (3:50pm to 4:10pm)
Wesley Smith: “Beyond Time Complexity: Data Movement Complexity Analysis for Matrix Multiplication”. Under review. (4:10pm to 4:30pm)
Ke Yang (Video): “Random Walks on Huge Graphs at Cache Efficiency”. SOSP ’21. (4:30pm to 4:45pm)
Open discussion(4:45pm to 5:00pm)
For people who cannot attend, we plan to make the talk videos available as we have done in the 2021 workshop.
Organizers
Faculty:
Chen Ding, University of Rochester
Nathan Tallent, Pacific Northwest National Laboratory
Student:
Wesley Smith, University of Rochester
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.
Format and Topics
PMHO is an annual 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 2022 workshop will take place online during the weekend of April 2 (Exact date TBD). It is hosted by the PPoPP 2022 conference.
Submission
Submit your presentation proposal to save-DyfTNd4RHy3y@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 Monday March 7, 2022 AOE.
PPoPP Workshop on Principles of Memory Hierarchy Optimization (PMHO)
Sunday 2/28/2021 9am to 1pm US EST (China 10pm to 2am, Europe 3pm to 7pm, US PST 6am to 10pm, US MST 7 am to 11 am)
Opening and Logistics (9am)
Session 1: Algorithm Locality (9:10am to 9:50am)
Data Movement Distance: An Asymptotic and Algorithmic Measure of Memory Cost, Chen Ding, with Donovan Snyder, University of Rochester, unpublished (video)
KEYNOTE: Working Sets, Locality, and System Performance, Peter Denning, Naval Post Graduate School, ACM Computing Surveys 2021 (video)
Session 2: Optimality (10:30am to 11:30am)
Some mathematical facts about optimal cache replacement, Pierre Michaud, Inria, ACM TACO 2016 (video)
Practical Bounds on Optimal Caching with Variable Object Sizes, Nathan Beckmann, Cargenie Mellon University, ACM SIGMetrics 2018 (video)
Category Theory in the Memory Hierarchy, Wesley Smith, University of Rochester, Unpublished (video)
Session 3: Applied Theories (11:40am to 1pm)
Optimal Data Placement for Heterogeneous Cache, Memory, and Storage Systems, Lei Zhang and Ymir Vigfusson, with Reza Karimi and Irfan Ahmad, Emory University, ACM SIGMetrics 2020 (video)
PHOEBE: Reuse-Aware Online Caching with Reinforcement Learning for Emergin Storage Models, Pengcheng Li, with Nan Wu, Alibaba, arxiv 2020 (video)
Data-Model Convergence and Runtime Support for Data Analytics and Graph Algorithms, Antonino Tumeo, Pacific Northwest National Laboratory, ACM Computing Frontiers 2019 (video)
Performance Prediction Toolkit for GPUs Cache Memories, Yehia Arafa and Hameed Badawy, New Mexico State University, ACM International Conference on Supercomputing (ICS) 2020 (video)
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.
Rochester Programming Systems Reseach 