## CSC 579 Spring 2023(R 9:40am to 10:55 Lechase 103)

### Syllabus

• The Need for Training Thought: The Values of Thought. Tendencies Needing Constant Regulation.  Regulation Transforms Inference into Proof.
• Type Systems.  Operational Semantics. Progress. Type Preservation. Type Soundness.
• Functional Programming in Coq: Data and Functions.  Proof by Simplification, Rewriting and Case Analysis.
• Proof by Induction. Proofs Within Proofs.  Formal vs. Informal Proof.
• Lists, Options, Partial Maps.
• Basic Tactics: apply, apply with, injection, discriminate, unfold, destruct.
• 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.

## 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.

University of Rochester Computer Science

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).

PPoPP Workshop on Principles of Memory Hierarchy Optimization (PMHO)

Video recordings of this year’s talks:

CARL: Compiler Assigned Reference Leasing. Chen Ding.

Caching With Delayed Hits. Nirav Atre.

Delayed Hits in Multi-Level Caches. Benjamin Carleton.

LHD: Improving Cache Hit Rate by Maximizing Hit Density. Nathan Beckmann.

On the Impact of Network Delays on Time-to-live Caching. Karim Elsayed.

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

Meeting ID/Passcode: 920 4275 6839 / PPoPP@2022

KEYNOTE

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.

1. An optimization-based approach to caching
2. A simple, very accurate model of LRU and variants
3. 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 Networking27(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

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.

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 $\leq$ k $\leq$ 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:

$reuse(1)$ $=\frac{\sum_{i=1}^{m}I(e_i-s_i=0)}{n}$

However, by the formulae stated in 3.2.2:

$reuse(1)$ $=\frac{\sum_{i=1}^{m}I(e_i-s_i=1)s_i - \sum_{i=1}^{m}I(e_i-s_i=1)(s_i + 1) + 2\sum_{i=1}^{m}I(e_i-s_i=1)}{n}$

$reuse(1)$ $=\frac{\sum_{i=1}^{m}I(e_i-s_i=1)}{n}$ $\neq$ $\frac{\sum_{i=1}^{m}I(e_i-s_i=0)}{n}$

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 $e_i - s_i \le k$ should instead read $e_i - s_i < k$

Then in Eq. 2,
$Z(k)=$ $\frac{\sum_{i=1}^{m}I(e_i - s_i < k) \cdot k}{n-k+1}$

The recursive equations should then read

$X(1) = \sum_{i=1}^{m}I(e_i - s_i = 0)s_i$

$X(k) = X(k-1) + \sum_{i=1}^{m}I(s_i\ge n-(k-1)) + \sum_{i=1}^{m}I(e_i-s_i+1=k)min(n-k, s_i)$

$Y(1) = \sum_{i=1}^{m}I(e_i - s_i = 0)e_i$

$Y(k) = Y(k-1) + \sum_{i=1}^{m}I(e_i\le k-1) + \sum_{i=1}^{m}I(e_i-s_i+1=k)max(k, e_i)$

$Z(1) = \sum_{i=1}^{m}I(e_i - s_i = 0)$

$Z(k) = Z(k-1) + \sum_{i=1}^{m}I(e_i-s_i < k) + \sum_{i=1}^{m}I(e_i-s_i+1=k) \cdot k$

(Sent to my class on the exam day)

NY Times collects and publishes New York city stories submitted by its readers at https://www.nytimes.com/column/metropolitan-diary.  The May 3 entry was Christopher Fryer who remembered “joys of city life walking every day from our apartment on the Upper West Side through Central Park, and then down Sixth Avenue to my office at 46th Street”, found “a shining Lincoln head on the penultimate step”, “paused to pick it up, being careful not to impede either the people coming up behind me or those who were heading down into the station”, and “a man on his way down the stairs spoke without breaking stride.

“Hey,” he said. “ I saw one of those at 125th Street. If you hurry you can probably get that one, too.”

Re finding pennies and other coins, I was always told that they had to be face up to be “good luck.”  I read somewhere a long time ago about a kind soul who would turn coins over when found face down so the next person to see them would have good luck, so I do that. It’s a little like being Santa Claus.

This is yet another proof of the CSC 200H theme: even good luck requires collaboration.

This slideshow requires JavaScript.

On Friday I received the Frederick D. and Susan Rice Lewis College Award for Undergraduate Teaching and Research Mentorship.  It was delightful to see everyone including many of my current and former students.  I prepared and delivered the following speech:

Thanks to Fred and Susan Lewis for creating this award and for being here, to Dean Runner, Mike, Cesar, and Chris for your generous words, to Department Chair Dr. Dwarkadas for the nomination, and Ms. Logory for organizing today’s event.

Thanks to the terrific computer science department, to our staff, especially the tireless work of Eileen Pullara.  Countless times I have asked her: can I hire another undergrad.  It is a community of support. I’m standing on the shoulder of not just the department, but also the university community and the scientific community.

Let me first state my teaching philosophy by quoting the Chinese philosopher Confucious from 2000 years ago, who he himself was a teacher. He said, and I translate: Achieve independence by making others independent. Achieve prosperity by making others prosperous.

As university faculty, we are Stewards of Knowledge.  My colleague Randal Nelson once compared education and business, he said, I quote: “The fundamental currency of a university is knowledge; while that of a corporation is capital. Both traffic information, money, and talented human beings, … but the bottom-line metric differs. ” Money, resource and capital have limits. It is often called a zero sum game. Knowledge knows no limits.

In teaching, I specialize in programming languages and systems. I show students a cartoon. This is an interview room at Ikea. The text in black instructs the nervous interviewee: “make a chair and take a seat”, the text in red is for my class “invent a language and talk.”

Interesting problems are abound: How do we describe a language when we do not yet have a language? Similar circular problems in Cesar’s research then and Mike’s research now in memory allocation. Similarly in my Confucious motto: independence and prosperity are problems that cannot be solved in isolation.

In most courses I teach, students learn by doing. Alan Perlis, the first recipient of Turing award in 1966, said “You think you know when you can learn, are more sure when you can write, even more when you can teach, but certain when you can program.” To understand a programming language, you must not just learn it but to build it.

How do we create knowledge?

We discover it through science, first by measuring. We are in the dark and remain so until we measure. The Unite State’s response to the coronavirus is hampered by a president who communicates by tweets, by politicizing the response to the crisis, and most damaging by anti-science arrogance and idiocy.

The first step it missed and still missing is testing. Without testing there is no science, and there is no knowledge.  This ignorance puts medical personnels and emergency responders and their family in danger and we begin to see disproportional fatalities in poor city neighborhoods, indigent population and people with disabilities.

This Wednesday I was most proud to see our University News photo: our medical school colleagues return from helping in NYC.  In teaching, as in medicine, we work with knowledge and skill.

Like our medical colleagues, we work together. We collaborate.

The best teacher-student relation is symbiotic. I confess when I first taught computer organization, the evaluation wasn’t good. A common criticism, believe it or not, was that the professor gave too many extensions. The next year, I set a schedule and followed it. Then the department machines had to be shut down for days due to the cooling water system repair in the building. I held the line and told my students that we don’t need extensions for lack of cooling, not in the middle of the winter, not in Rochester. I received high scores for that course.

At a research university like ours, teaching keeps a close pace with technology.
This semester I am teaching new material of machine-checked proofs.
Knowledge is not just the truth but more importantly the proof.  Proof is knowledge about knowledge — how do we know we know.

This is unprecedented material which combines the programming language and the language of logic. (1) Programming encodes reasoning, (2) reasoning verifies programming. (3) With computers, programming automates reasoning. (4) Even more exciting is the new way to collaborate — our reasoning can be combined as our programs can.  (5) Most exciting is where our students will go taking the knowledge. Three undergrads and their TA are “programming” a proof for a joint paper with my colleagues and may introduce machine-checked proofs to the database community.

We teach technology. We collaborate to develop technology. We also teach and develop technology to amplify collaborative work.

University of Rochester, its size, not too big and not too small, and its combination of research and liberal arts education, make it a best place to collaborate.

The best collaboration is to inspire and be inspired. Let me take just one minute to give two examples.

Lane Hemaspaandra created the honor course I’m teaching now and he continues to help and model for me in teaching collaborative problem solving.

Chris Tice when he was a student solved an extra credit problem after the assignment was due. So why doing extra work for no credit. He said that he didn’t have time to work on it, but he was interested so he went back once he had time. When a student is not there just for the grade, a teacher is not here just for grading. It is what Hajim said at every commencement, if you love your work, you never have to work.

To summarize, I have started with my motto of independence and prosperity and highlighted three ingredients of a happy life: to collaborate, discover, and inspire. To help you remember, the initials CDI are the first three letters of my university NetId.

I want to thank people who inspired me the most: my longest time colleagues, mentors and supporters Michael Scott and Sandhya Dwarkadas, my graduate advisors late Dr. Ken Kennedy and Philip Sweany, my mother Ruizhe Liu who’s currently battling cancer, for her unyielding courage and support, my father Shengyao, my brother Rui, my dear wife and Rochester graduate Dr. Linlin Chen and our two children Yawen and Shuwen who were both born in Rochester.

Last, let me share a few road trip photos.   In 2016, we went to conference in DC, we zoomed by at 90 miles an hour in Pennsylvania but then sit still in traffic the minute we got to Baltimore, but had fun counting the many Rs. Once arrived, undergrads had homework. The book on the table was Michael’s popular textbook, in its fourth edition. At the award banquet, we were the Rochester 9, the following year we had a smaller group and Google flew one of the undergrads out for interview, but in this photo we were the largest group and was so recognized.

This slideshow requires JavaScript.

I received an award for that exact reason — the award for being the largest group attending the conference.  Inspired, I told my students: you see — 100% of success is just showing up.

Then it was literally true for that award. Today I feel the same for this award. It is most humbling. Thank you all.

Other than the people I thanked above, I am also grateful for the many who joined the meeting and for the spontaneous comments following the event by my colleagues Michael Scott and Sandhya Dwarkadas and my former doctoral graduates Xiaoming Gu, Chengliang (Cheng) Zhang, Pengcheng Li, and Xipeng Shen.  Quoting Dr. Cheng Zhang who was attending from home in Seattle and said that through his work in Microsoft, Amazon and now Google, he collaborate in a team and he work to lift others.

It was most fun, heart warming, and well organized.  There wasn’t even problems with the network.