Computer Sciences Weekly Good News

Prof Bilge Mutlu and students received support from the Google Award for Inclusion Research (AIR) Program for their work titled “Supporting Social Participation for Older Adults through Robotic Telepresence”. [1]

The CDIS Job Fair drew nearly 2000 students and nearly 50 employers (in late September when it took place). Thanks to Prof Bart Miller and the many others who helped create such a wonderful event for our students! [2]

The 2023 Rosser lecture was given by Prof Zvi Galil, Professor and former Dean at Georgia Tech. Thank you to Prof Jin-Yi Cai for hosting! [3]

Prof Matt Sinclair gave an invited talk entitled “Leveraging open source simulators to enable HW/SW co-design of next-generation HPC systems” at Exascale Simulation of Next-Generation Computing Architectures.

Notes:

[1] Prof. Mutlu and students received support from the Google Award for Inclusion Research (AIR) Program for their work titled “Supporting Social Participation for Older Adults through Robotic Telepresence.”

More information on the program: The Award for Inclusion Research Program recognizes and supports academic research in computing and technology that addresses the needs of historically marginalized groups globally. Launched in 2020, the Award for Inclusion Research (AIR) Program is an ongoing effort to support innovative research and professors working to create positive societal impact.

Link: https://research.google/outreach/air-program/

[2] https://cdis.wisc.edu/cdis-job-fair-draws-thousands/

Over 1,800 students stopped by the School of Computer, Data, and Information Sciences job fair held on September 26 to network with local and national businesses looking for talent for internships and full-time career opportunities. Students networked with 48 employers including DraftKings, Google, Epic, Fetch, Raven, and more.

Read more at the link above.

[3] https://www.cs.wisc.edu/2023/09/05/rosser-lecture-zvi-galil/

The Rosser Lecture series is back! The 2023 lecture will feature Dr. Zvi Galil, Professor and former Dean of Computer Science at Georgia Institute of Technology, speaking about ”Georgia Tech’s online MOOC-based Master’s Program and the future of higher education.” Dr. Galil will discuss the success of the online master’s in computer science at Georgia Tech (OMSCS), launched in 2014.

Read more at the link above.

[4] “Leveraging open source simulators to enable HW/SW co-design of next-generation HPC systems”

Matt Sinclair

Exascale Simulation of Next-Generation Computing Architectures

Abstract: In this talk, I discuss our approach to address these challenges and modernize simulation approaches.  More specifically, I will discuss our efforts to develop new gem5-SST based simulation & modeling techniques to enable hardware-software co-design efforts that can model and prototype future HPC-scale systems.  Since no single methodology can provide the required accuracy, detail, or scale, we believe the path forward is through “multi-fidelity simulation.” Multi-fidelity simulation combines detailed cycle-level simulators with scalable simulation to create a multi-fidelity system which scales to model future supercomputers without compromising accuracy.  Moreover, multi-fidelity simulation in time and space will provide accurate exascale performance predictions that enable design space trade-offs exploration. This unified simulation framework will integrate best in class models—the fastest with good high-level behavioral accuracy and the most detailed with cycle-level accuracy—in the same simulation instance in both time and space. This talk also discusses the current status of multi-fidelity simulation and where improvements are needed to reach these lofty goals.

• Prof Miron Livny and colleagues ran the HTCondor European Workshop in Orsay, France. [1]
• Prof Somesh Jha and colleagues are running a GenAI Risks workshop this October.  [2]
• Prof Yudong Chen, Ilias Diakonikolas, Prof Jelena Diakonikolas, Prof Josiah Hanna, Prof Somesh Jha, Prof Kirthi Kandasamy, Prof Yong Jae Lee, Prof Sharon Li, Prof Yingyu Liang, Prof Christos Tzamos, Prof Jerry Zhu, our Chair Prof Steve Wright, and many colleagues published 30 papers at NeurIPS this year, including a number of Spotlight papers.  [3]

Notes:

[1] The week of September 17th, the Irene-Joliot Curie Lab, in Orsay, France hosted the annual HTCondor European Workshop.  41 attendees representing 20 institutions from 9 countries, including members of the CS Department’s Center for High Throughput Computing, met to discuss progress, challenges and future goals for deploying and operating distributed High Throughput systems using the HTCondor Software Suite. Highlights include benchmark results from the CMS experiment at CERN, showing that, if needed, they can scale their computing cluster to support over 800,000 concurrent running jobs, the European Weather Cloud’s adoption of HTCondor for their computing, and news about Pelican, a new distributed storage system intended to support distributed high throughput workloads.

[2] Here is the website for the GenAI Risks workshop this October 16 in Reston, VA:

https://sites.google.com/view/genai-risks-workshop-oct-2023

The agenda is shaping up around GenAI policy, alignment, and watermarking and detection, and will be online asap.

We’d like your help in broadening the attendance a bit. If you have students, colleagues, and collaborators interested in participating in the discussion, please forward this message with the website to them or simply point them to the RSVP page on the website:

https://docs.google.com/forms/d/e/1FAIpQLSe49qQFGH9Vs2H7uttT5n6VXjazRJyC5JxwTio63XpHcv5D-Q/viewform

We look forward to seeing you there.

Thank you,

Mihai Christodorescu (Google)

Somesh Jha (UW-Madison and Google)

Khawaja Shams (Google)

John Mitchell (Stanford)

[3] Here is the list gathered:

1 – “First Order Stochastic Optimization with Oblivious Noise”

I. Diakonikolas, S. Karmalkar, J. Park, C. Tzamos

This paper gives the first efficient method for stochastic first order optimization with noise, broadly generalizing the heavy-tailed setting.

2 – “SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions”

I. Diakonikolas, D. Kane, L. Ren, Y. Sun

This paper greatly strengthens a general methodology (developed by the first two named authors and Alistair Stewart in FOCS 2017) to establish information-computation tradeoffs for high-dimensional statistical tasks. As a corollary, it gives new such tradeoffs for a range of ML problems.

3 – “SQ Lower Bounds for Learning Mixtures of Linear Classifiers”

I. Diakonikolas, D. Kane, Y. Sun

This paper proves an information-computation tradeoff showing that known algorithms for learning mixtures of linear classifiers are essentially best possible.

4 – “Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression”

I. Diakonikolas, D. Kane, A. Pensia, T. Pittas

This paper revisits the classical problems of mean estimation and linear regression of a multivariate Gaussian in Huber’s contamination model. It gives optimal algorithms for these basic tasks with respect to sample size, runtime, and accuracy guarantees.

5 – “Efficient Testable Learning of Halfspaces with Adversarial Label Noise”

I. Diakonikolas, D. Kane, V. Kontonis, S. Liu, N. Zarifis

This paper gives the first efficient algorithm for learning linear separation with adversarial labe noise in the testable framework, in which we can trust the accuracy of our hypothesis independent of the assumptions.

6 – “A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm” [Spotlight]

I. Diakonikolas, D. Kane, J. Lee, A. Pensia, T. Pittas

This paper gives a fast and provable algorithm for list-decodable covariance estimation in the presence of a majority of outliers. It implies the first efficient algorithm for robustly learning arbitrary mixtures of Gaussians that does not require solving a large convex program.

7 – “Grounding Neural Inference with Satisfiability Modulo Theories” [Spotlight]

Matt Fredrikson, Kaiji Lu, Somesh Jha, Saranya Vijayakumar, Vijay Ganesh, Zifan Wang

This paper enhances grounding in ML models by incorporating satisfiability modulo solvers (SMT), such as Z3.

8 – “Doubly Robust Peer-To-Peer Learning Protocol”

Nicholas Franzese, Adam Dziedzic, Christopher A. Choquette-Choo, Mark R. Thomas, Muhammad Ahmad Kaleem, Stephan Rabanser, Congyu Fang, Somesh Jha, Nicolas Papernot, Xiao Wang

This paper uses techniques from secure multiparty computation (SMC) to make peer-to-peer learning (such as various federated learning algorithms) more robust to malicious participants.

9 – “Block-Coordinate Methods and Restarting for Solving Extensive-Form Games”

D. Chakrabarti, J. Diakonikolas, C. Kroer,

The paper provides a cyclic block coordinate method for solving extensive-form games. The method is the first block coordinate-type method for such problems and the results are surprising from at least two aspects: (1) that it is possible at all to get convergence results for a block coordinate-type method, as the feasible set is not block separable, and (2) it is the first cyclic method that provably does not converge slower than full vector-update methods in the worst case (all other cyclic methods are slower by a factor scaling polynomially with the number of blocks in the worst case). The paper also provides a restarting strategy that empirically speeds up the algorithm.

10 – “Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise”

I. Diakonikolas, J. Diakonikolas, D.M. Kane, P. Wang, N. Zarifis

This paper provides matching upper and lower bounds for “efficient” algorithms addressing one of the most fundamental learning problems: linear classification where the data points follow standard Gaussian distribution and the labels are determined by a biased halfspace + random classification noise. The paper provides a statistical query (SQ) lower bound, which applies to all standard approaches for addressing this problem, that shows that there is an inherent information-computation gap for this problem: all polynomial-time SQ algorithms in the worst case need more samples than suggested by the information-theoretic lower bound. A surprising aspect of the upper bound is that we obtain an optimization algorithm (a variant of Riemannian gradient descent) that obtains linear convergence (with geometrically reducing error) for a nonconvex piecewise-linear optimization problem on a sphere.

11 – “Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing”

S.Li, Y. Cheng, I. Diakonikolas, J. Diakonikolas, R. Ge, S. Wright,

This paper provides the first algorithm for finding second-order stationary points in  nonconvex optimization in the outlier-robust setting, and with dimension-independent error guarantees. It further demonstrates how these general results can be applied to low rank matrix sensing problems, where outliers are likely to arise and second order stationarity suffices as a criterion of convergence.

12 – “Geometry-Aware Adaptation for Pretrained Models”

Nicholas Roberts, Xintong Li, Dyah Adila, Sonia Cromp, Tzu-Heng Huang, Jitian Zhao, Frederic Sala

13 – “Mitigating Source Bias for Fairer Weak Supervision”

Changho Shin, Sonia Cromp, Dyah Adila, Frederic Sala

14 – “Promises and Pitfalls of Threshold-based Auto-labeling” [Spotlight]

Harit Vishwakarma, Heguang Lin, Frederic Sala, Ramya Vinayak

15 – “Train ‘n Trade: Foundations of Parameter Markets”

Tzu-Heng Huang, Harit Vishwakarma, Frederic Sala

16 – “Skill-it! A Data-driven Skills Framework for Understanding and Training Language Models” [Spotlight]

ayee F Chen (Stanford), Nicholas Roberts, Kush Bhatia (Stanford), Jue WANG (Together AI), Ce Zhang (Together AI), Frederic Sala, Christopher Re (Stanford)

17 – “Embroid: Unsupervised Prediction Smoothing Can Improve Few-Shot Classification”

Neel Guha (Stanford), Mayee F Chen (Stanford), Kush Bhatia (Stanford), Azalia Mirhoseini (Anthropic AI), Frederic Sala, Christopher Re (Stanford)

18 – “Visual Instruction Tuning” [Oral]

Haotian Liu*, Chunyuan Li*, Qingyang Wu, and Yong Jae Lee

(*equal contribution)

This paper introduces LLaVA (Large Language and Vision Assistant), a large multimodal model that connects a vision encoder and LLM for general-purpose visual and language understanding.

https://llava-vl.github.io/

LLaVA is able to explain that the artwork is a parody of the Mona Lisa.

19 – “Dissecting Knowledge Distillation: An Exploration of its Inner Workings and Applications”

Utkarsh Ojha*, Yuheng Li*, Anirudh Sundara Rajan*, Yingyu Liang, and Yong Jae Lee

(*equal contribution)

This paper presents a comprehensive study to try to answer the following question: what is the knowledge that gets distilled in knowledge distillation? That is, in what ways does the student become similar to the teacher? Does it start to localize objects in the same way? Does it get fooled by the same adversarial samples? Does its data invariance properties become similar?

20 – “Visual Instruction Inversion: Image Editing via Image Prompting”

Thao Nguyen, Yuheng Li, Utkarsh Ojha, and Yong Jae Lee

This paper presents a framework for inverting visual prompts (i.e., before-and-after reference images) into editing instructions for controllable text-to-image generation.

https://thaoshibe.github.io/visii/

21 – “Segment Everything Everywhere All at Once”

Xueyan Zou, Jianwei Yang, Hao Zhang, Feng Li, Linjie Li, Jianfeng Wang, Lijuan Wang, Jianfeng Gao, and Yong Jae Lee

This paper presents an interactive model for segmenting images.  The model can be prompted with visual prompts (points, marks, boxes, scribbles and image segments) and language prompts (text and audio).

https://github.com/UX-Decoder/Segment-Everything-Everywhere-All-At-Once

22 – “Conditional Mutual Information for Disentangled Representations in Reinforcement Learning” [spotlight]

Mhairi Dunion, Trevor McInroe, Kevin Luck, Josiah Hanna, and Stefano Albrecht

23 – “State-Action Similarity-Based Representations for Off-Policy Evaluation”

Brahma Pavse, Josiah Hanna

24 – “Multi-task Representation Learning for Pure Exploration in Bilinear Bandits”

Subhojyoti Mukherjee, Qiaomin Xie, Josiah Hanna, Robert Nowak

25 – “Mechanism Design for Collaborative Normal Mean Estimation” [spotlight]

Yiding Chen, Xiaojin Zhu, Kirthevasan Kandasamy

26 – “A Graph-Theoretic Framework for Understanding Open-World Representation Learning” [spotlight]

Yiyou Sun, Zhenmei Shi, Yixuan (Sharon) Li

Open-world representation learning aims at inferring both known and novel classes in unlabeled data, by harnessing prior knowledge from a labeled set with known classes.  Despite its importance, there is a lack of theoretical foundations for this problem. This paper bridges the gap by formalizing a graph-theoretic framework tailored for the open-world setting, where the clustering can be theoretically characterized by graph factorization. Based on our graph formulation, we introduce a new algorithm called Spectral Open-world Representation Learning (SORL), and show that minimizing our loss is equivalent to performing spectral decomposition on the graph. Such equivalence allows us to derive a provable error bound on the clustering performance for both known and novel classes, and analyze rigorously when labeled data helps.

27 – “Dream the Impossible: Outlier Imagination with Diffusion Models”

Xuefeng Du, Yiyou Sun, Xiaojin (Jerry) Zhu, Yixuan (Sharon) Li

Generating photo-realistic outliers in the high dimensional pixel space has been an open challenge for the field.  To tackle the problem, this paper proposes a new framework DREAM-OOD, which enables imagining photo-realistic outliers by way of diffusion models, provided with only the in-distribution (ID) data and classes.

28 – “Learning to Augment Distributions for Out-of-distribution Detection”

Qizhou Wang, Zhen Fang, Yonggang Zhang, Feng Liu, Yixuan (Sharon) Li, Bo Han

This paper derives learning theory analyzing the distribution discrepancy between the auxiliary and the unseen real OOD data, and how it affects the open-world OOD detection performance.

29 – “Provable Guarantees for Neural Networks via Gradient Feature Learning”

Zhenmei Shi, Jenny Wei, Yingyu Liang

This paper proposes a unified analysis framework for two-layer networks trained by gradient descent, including several existing analyses as special cases. It also sheds light on several interesting network learning phenomena.

30 – “Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption” [spotlight]

Yige Hong, Qiaomin Xie, Yudong Chen, and Weina Wang

• Prof Mohit Gupta and many different colleagues had six(!) papers accepted into IEEE ICCV (the International Conference on Computer Vision). [1]
• An L&S Magazine article, entitled “I Spy”, about Prof Rahul Chatterjee’s work on helping victims of domestic abuse is available here. [2]
• Prof Somesh Jha and colleagues (including CS affiliate Prof Kassem Fawaz from ECE, in one instance) had two papers accepted into ACM CCS ‘23, entitled “Zero-Knowledge Proofs of Training” and “Stateful Defenses for Machine Learning Models Are Not Yet Secure Against Black-box Attacks”. [3]
• Prof Efty Sifakis had the following work (on face simulation for the movie Avatar 2), entitled “Simulation-aided face strain extraction for ML animation systems”, presented at ACM SIGGRAPH.  [4]

[1] All six to appear at IEEE ICCV

[a] SoDaCam: Software-defined Cameras via Single-Photon Imaging (*oral presentation) [Project Page]

Varun Sundar (UW), Andrei Ardelean (EPFL), Tristan Swedish (Ubicept), Claudio Brusschini (EPFL), Edoardo Charbon (EPFL), Mohit Gupta (UW)

[b] Eventful Transformers: Leveraging Temporal Redundancy in Vision Transformers [Project Page]

Matthew Dutson (UW), Yin Li (UW), Mohit Gupta (UW)

[c] Computational 3D Imaging with Position Sensors (*oral presentation) [Project Page]

Jeremy Klotz (Columbia), Mohit Gupta (UW), Aswin Sankaranarayanan (CMU)

[d] Learned Compressive Representations for Single-Photon 3D Imaging [Project Page]

Felipe Gutierrez-Barragan (UW), Fangzhou Mu (UW), Andrei Ardelean (EPFL), Atul Ingle (Portland), Claudio Bruschini (EPFL), Edoardo Charbon (EPFL), Yin Li (UW), Mohit Gupta (UW), Andreas Velten (UW)

[e] Eulerian Single-Photon Vision [Project Page]

Shantanu Gupta (UW), Mohit Gupta (UW)

[f] Panoramas from Photons [Project Page]

Sacha Jungerman (UW), Atul Ingle (Portland), Mohit Gupta (UW)

[2] “I Spy”

by Aaron Conklin

“Rahul Chatterjee and his team have created a clinic to help victims of domestic abuse whose attackers may be using technology to stalk them.”

Read the rest here.

[3] To appear in ACM CCS 2023

https://www.sigsac.org/ccs/CCS2023/

“Zero-Knowledge Proofs of Training”

Sanjam Garg (University of California, Berkeley and NTT Research)

Aarushi Goel (NTT Research)

Somesh Jha (University of Wisconsin)

Saeed Mahloujifar (Meta)

Mohammad Mahmoody (University of Virginia)

Guru-Vamsi Policharla (UC Berkeley)

Mingyuan Wang (UC Berkeley)

How can a model owner prove that they trained their model according to the correct

specification? More importantly, how can they do so while preserving the privacy of the underlying dataset and the final model? We study this problem and formulate the notion of zero-knowledge proof of training (zkPoT), which formalizes rigorous security guarantees that should be achieved by a privacy-preserving proof of training. We then design novel zkPoT protocol, that is provably secure, based on MPC-in-the-head techniques combined with ideas from the zkSNARKs literature to achieve the best of both worlds in terms of communication efficiency and computational resources needed. Importantly, our protocol is streaming friendly and does not require RAM proportional to the size of the circuit being trained and hence can be adapted to the requirements of available hardware. We implement and evaluate our protocol for training a logistic regression model and estimate that for a dataset of 1 million records with 1024 features, the online prover time is about one

hour.

“Stateful Defenses for Machine Learning Models Are Not Yet Secure Against Black-box Attacks”

Ryan Feng (University of Michigan)

Ashish Hooda (University of Wisconsin-Madison)

Neal Mangaokar (University of Michigan)

Kassem Fawaz (University of Wisconsin-Madison)

Somesh Jha (University of Wisconsin-Madison)

Atul Prakash (University of Michigan)

Recent work has proposed stateful defense models (SDMs) as a compelling strategy to defend against a black-box attacker who only has query access to the model, as is common for online machine learning platforms. Such stateful defenses aim to defend against black-box attacks by tracking the query history and detecting and rejecting queries that are “similar” and thus preventing black-box attacks from finding useful gradients and making progress towards finding adversarial attacks within a reasonable query budget. Recent SDMs (e.g., Blacklight and PIHA) have shown remarkable success in defending against state-of-the-art black-box attacks. In this paper, we show that SDMs are highly vulnerable to a new class of adaptive black-box attacks. We propose a novel adaptive black-box attack strategy called Oracle-Guided Adaptive Rejection Sampling (OGARS) that involves two stages: (1) use initial query patterns to infer key properties about an SDM’s defense; and, (2) leverage those extracted properties to design subsequent query patterns to evade the SDM’s defense while making progress towards finding adversarial inputs. OGARS is broadly applicable as an enhancement to existing black-box attacks — we show how to apply the strategy to enhance six common black-box attacks to be more effective against current class of SDMs. For example, OGARS-enhanced versions of black-box attacks improved attack success rate against recent stateful defenses from almost 0% to to almost 100% for multiple datasets within reasonable query budgets.

[4]  “Simulation-aided face strain extraction for ML animation systems”

G. Klar, S. Ward, A. Moffat, E. Sifakis and K. Museth

ACM SIGGRAPH Talks, pp. 63:1-2

https://doi.org/10.1145/3587421.3595454

Abstract: We present a volumetric, simulation-based pipeline for the automatic creation of strain-based descriptors from facial performance capture provided as surface meshes. Strain descriptors encode facial poses via length elongation/contraction ratios of curves embedded in the flesh volume. Strains are anatomically motivated, correlate strongly to muscle action, and offer excellent coverage of the pose space. Our proposed framework extracts such descriptors from surface-only performance capture data, by extrapolating this deformation into the flesh volume in a physics-based fashion that respects collisions and filters non-physical capture defects. The result of our system feeds into Machine Learning facial animation tools, as employed in Avatar: The Way of Water.

• Cool article entitled “Complexity Theory’s 50-Year Journey to the Limits of Knowledge” in Quanta Magazine here; check out the article and the timeline below which highlights Prof Jin-Yi Cai’s contributions.  [1]
• Prof Mohit Gupta and colleagues had the paper “Mitigating AC and DC Interference in Multi-ToF-Camera Environments” accepted at IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI).  [2]
• The Fall Semester is about to begin, and yes, the faculty contract has already done so; this means you are being paid! These events are always worth celebrating, but particularly so when one is away on sabbatical. [3]

————-

[1] Title: Complexity Theory’s 50-Year Journey to the Limits of Knowledge

by Ben Brubaker

“How hard is it to prove that problems are hard to solve? Meta-complexity theorists have been asking questions like this for decades. A string of recent results has started to deliver answers.”

Read the rest:

https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/

Cool timeline from the article:

Also, thanks Prof Aws Albarghouthi for the pointer!

[2] “Mitigating AC and DC Interference in Multi-ToF-Camera Environments”

Authors:  Jongho Lee and Mohit Gupta

Webpage: https://wisionlab.com/project/stochastictdma/

Abstract: Multi-camera interference (MCI) is an important challenge faced by continuous-wave time-of-flight (C-ToF) cameras. In the presence of other cameras, a C-ToF camera may receive light from other cameras’ sources, resulting in potentially large depth errors. We propose stochastic exposure coding (SEC), a novel approach to mitigate MCI. In SEC, the camera integration time is divided into multiple time slots. Each camera is turned on during a slot with an optimal probability to avoid interference while maintaining a high signal-to-noise ratio (SNR). The proposed approach has the following benefits. First, SEC can filter out both the AC and DC components of interfering signals effectively, which simultaneously achieves high SNR and mitigates depth errors. Second, time-slotting in SEC enables 3D imaging without saturation in the high photon flux regime. Third, the energy savings due to camera turning on during only a fraction of integration time can be utilized to amplify the source peak power, which increases the robustness of SEC to ambient light. Lastly, SEC can be implemented without modifying the C-ToF camera’s coding functions, and thus, can be used with a wide range of cameras with minimal changes. We demonstrate the performance benefits of SEC with thorough theoretical analysis, simulations and real experiments, across a wide range of imaging scenarios.

[3] The Academic Calendar is good to check out:

https://secfac.wisc.edu/academic-calendar/

Especially for new folks!

• Prof Matt Sinclair and student and colleagues had a paper accepted at IISWC entitled “Tale of Two Cs: Computation vs. Communication Scaling for Future Transformers on Future Hardware”.  [1]
• Prof Somesh Jha’s former student, Matt Fredrikson, was part of a recent effort that showed how GPT guardrails can be circumvented, with a NY Times article about it.  [2]
• Prof Ming Liu and collaborators had a three-year proposal entitled “Fast and Accurate Modeling and Performance Analysis of CXL-Centric Data Center Networks” by Intel.  [3]
• Prof Matt Sinclair and collaborators had the proposals entitled “DOE Express: Leveraging Open Source Simulators to Enable HW/SW Co-Design of Next-Generation HPC Systems” funded.  [4]
• Prof Matt Sinclair and Prof Shivaram Venkataraman had the proposal “Collaborative Research: CSR: Medium: Fortuna: Characterizing and Harnessing Performance Variability in Accelerator-rich Clusters” funded.  [5]
• Prof Andrea Arpaci-Dusseau gave a talk about her advisor, David Culler, at his Festschrift at UC Berkeley, and also chaired the session about his first era at Berkeley on parallel and distributed computing.  [6]

—–

[1]  Paper Name: Tale of Two Cs: Computation vs. Communication Scaling for Future Transformers on Future Hardware

Authors: Suchita Pati, Shaizeen Aga, Mahzabeen Islam, Nuwan Jayasena, Matthew D. Sinclair

Abstract: Scaling neural network models has delivered dramatic quality gains across ML problems. However, this scaling has increased the reliance on efficient distributed training techniques. Accordingly, as with other distributed computing scenarios, it is important to understand how will compute and communication scale relative to one another as models scale and hardware evolves? A careful study which answers this question can better guide the design of future systems which can efficiently train future large models.

Accordingly, this work provides a comprehensive multi-axial (algorithmic, empirical, hardware evolution) analysis of compute vs. communication (Comp-vs.-Comm) scaling for future Transformer models on future hardware. First, our algorithmic analysis shows that compute generally enjoys an edge over communication as models scale. However, since memory capacity scales slower than compute, these trends are being stressed. Next, we quantify this edge by empirically studying how Comp-vs.-Comm scales for future models on future hardware. To avoid profiling numerous Transformer models across many setups, we extract execution regions and project costs using operator models. This allows a spectrum (hundreds) of future model/hardware scenarios to be accurately studied (< 15% error) and reduces profiling costs by 2100×. Our experiments show that communication will be a significant portion (40-75%) of runtime as models and hardware evolve. Moreover, communication which is hidden by overlapped computation in today’s models often cannot be hidden in future, larger models. Overall, this work highlights the increasingly large role communication will play as models scale and we conclude with a discussion of promising techniques that stand to tackle communication and also discuss how our analysis influences their betterment.

[2] https://www.nytimes.com/2023/07/27/business/ai-chatgpt-safety-research.html

From the article: “A new report indicates that the guardrails for widely used chatbots can be thwarted, leading to an increasingly unpredictable environment for the technology.”

Underlying paper found here: https://llm-attacks.org/

[3]  Prof Ming Liu, Prof. Umit Y. Orgas (ECE), Qiaomin Xie (Industrial and System Engineering)

“Fast and Accurate Modeling and Performance Analysis of CXL-Centric Data Center Networks”

Intel, 3-year proposal

Summary: Modern data center networks consist of thousands of end nodes, such as CPUs, GPUs, and storage, connected by multi-layer networks and protocols, such as Compute Express Link (CXL). Applications running on the end nodes impose large throughput (~100 Gbps) and low latency (<10 ms) requirements on the data center networks (DCN). To satisfy these requirements, the DCN designers employ more complex network switches and topologies. At the same time, the network protocols and algorithms running on these devices, such as congestion control, grow in complexity. As a result, fast and accurate pre-silicon exploration and optimization of DCN at server, rack, and DCN scales becomes both more important and challenging. Widely accepted simulation frameworks, such as ns3, enable accurate performance evaluations. However, the accuracy comes at a steep increase in exploration time, which can severely limit the scope and fidelity of pre-silicon evaluations. Therefore, we propose fast and accurate performance analysis and optimization exploration at the server, rack, and DCN levels. We plan to achieve this by (1) performing a systematic characterization over real-world systems and applications using Intel’s Sapphire Rapids system at server-/rack-scale; (2) developing pragmatic modeling abstractions that facilitate modeling accuracy and performance (encompassing a performance model for Flex Bus and CXL layered protocol, an abstract communication substrate, and an abstract routing architecture); (3) conducting large-scale simulations by integrating the modeling techniques into existing simulation frameworks.

[4] “DOE Express: Leveraging Open Source Simulators to Enable HW/SW Co-Design of Next-Generation HPC Systems”

PIs: Oscar Hernandez (ORNL), Matt Sinclair (UW)

Co-PIs: William Godoy (ORNL), Jason Lowe-Power (UC, Davis), Bobby Bruce (UC, Davis)

Link: https://science.osti.gov/ascr/-/media/funding/pdf/Awards-Lists/2950-ASCR-EXPRESS-Awards-List.pdf

Money: $1.3M Total, $400K for UW

Shortened, Good News Friendly Abstract: This multi-institutional project aims at developing new simulation and modeling techniques based on gem5-SST to enable hardware-software co-design efforts to achieve 100 ExaFlops using 20 MW of power. Currently, state-of-the-art architecture simulators are too high level to accurately model important details, too inflexible, or too slow to provide accurate and detailed cross-stack software and hardware (SW/HW) optimizations. This project proposes a “multi-fidelity simulation” in time and space to provide accurate exascale performance predictions in time scales that enable design space trade-offs exploration. The project also aims to improve simulation efficiency by identifying key regions of interest in applications through the use of hints via parallel programming models.

[5] Title: Collaborative Research: CSR: Medium: Fortuna: Characterizing and Harnessing Performance Variability in Accelerator-rich Clusters

PIs: Shivaram Venkataraman (UW), Zhao Zhang (TACC/Rutgers)

Co-PI: Matt Sinclair (UW)

Money: $1M total, $670K for UW

Abstract: Large computing clusters, including data centers and supercomputers, are used for a variety of applications including scientific computations and machine learning. Modern compute clusters typically use specialized accelerator hardware to speed up computations. Operators of accelerator-rich clusters aim to have high resource utilization across all users of the cluster. However, these systems are often under-utilized due to performance variability across accelerators; that is, application performance can vary across accelerators even when the same application is run on the same type of accelerator. This proposal will develop Fortuna, a set of tools that can be used by cluster operators and researchers to characterize and harness variability across accelerators. First, Fortuna will use new methodologies to characterize how much performance variability exists across a wide range of accelerator hardware. Second, Fortuna will identify which applications are more likely to suffer from performance variability. Finally, Fortuna will include new scheduling mechanisms that can use variability measurements and knowledge about applications to improve utilization.

Broader impacts of the proposed research include open-source implementations of algorithms and tools, which will be applicable to many large-scale clusters and lay the groundwork for wider industry adoption. The project will also create course modules on system design principles with heterogeneous hardware and software, based on the tools developed as a part of the proposal. This will teach the next generation of students how to design hardware and software to improve utilization of future systems.

[6] https://cullerfest.cs.berkeley.edu/

In academia, a Festschrift is a book honoring a respected person, especially an academic, and presented during their lifetime. It generally takes the form of an edited volume, containing contributions from the honoree’s colleagues, former pupils, and friends. Festschriften are often titled something like Essays in Honour of… or Essays Presented to… . [Wikipedia]

This Festschrift was a little less formal, consisting of a large number of talks from former students and collaborators of David’s.

• Prof Ming Liu and Prof Mike Swift and collaborators published “LogNIC: A High-Level Performance Model for SmartNICs” at IEEE Micro.  [1]
• Prof Paul Barford and collaborators had two NSF proposals funded, entitled “Large Scale Analysis of Configurations and Management Practices in the Domain Name System” and “Methods for Active Measurement of the Domain Name System” with Barford as PI.  [2]
• Prof Fred Sala and Prof Jerry Zhu created a short talk about what ChatGPT is, made for a general audience; it was distributed via “Sift and Winnow” (L&S’s monthly mailing).  [3]

———–

[1] Title: LogNIC: A High-Level Performance Model for SmartNICs

Authors: Zerui Guo, Jiaxin Lin, Yuebin Bai, Daehyeok Kim, Mike Swift, Aditya Akella, Ming Liu

Abstract: SmartNICs have become an indispensable communication fabric and computing substrate in today’s data centers and enterprise clusters, providing in-network computing capabilities for traversed packets and benefiting a range of applications across the system stack. Building an efficient SmartNIC-assisted solution is generally non-trivial and tedious as it requires programmers to understand the SmartNIC architecture, refactor application logic to match the device’s capabilities and limitations, and correlate an application execution with traffic characteristics. A high-level SmartNIC performance model can decouple the underlying SmartNIC hardware device from its offloaded software implementations and execution contexts, thereby drastically simplifying and facilitating the development process. However, prior architectural models can hardly be applied due to their ineptness in dissecting the SmartNIC-offloaded program’s complexity, capturing the nondeterministic overlapping between computation and I/O, and perceiving diverse traffic profiles.

This paper presents the LogNIC model that systematically analyzes the performance characteristics of a SmartNIC-offloaded program. Unlike conventional execution flow-based modeling, LogNIC employs a packet-centric approach that examines SmartNIC execution based on how packets traverse heterogeneous computing domains, on-/off-chip interconnects, and memory subsystems. It abstracts away the low-level device details, represents a deployed program as an execution graph, retains a handful of configurable parameters, and generates latency/throughput estimation for a given traffic profile. It further exposes a couple of extensions to handle multi-tenancy, traffic interleaving, and accelerator peculiarity. We demonstrate the LogNIC model’s capabilities using both commodity SmartNICs and an academic prototype under five application scenarios. Our evaluations show that LogNIC can estimate performance bounds, explore software optimization strategies, and provide guidelines for new hardware designs.

[2] Title:  Collaborative Research: NeTS: Medium: Large Scale Analysis of Configurations and Management Practices in the Domain Name System

Investigators:  P. Barford (PI), M. Crovella (co-PI) and J. Sommers (co-PI)

Abstract:

This project will build a broad and fundamental body of knowledge on the characteristics of configurations and management practices used in the operation of the Internet’s Domain Name System. Large public datasets will be used to analyze and statistically model the DNS contents. Graph-based analysis will be used to characterize and quantify activities performed by registrars and domain operators. Tools will be developed for the research community to support machine learning applications for the DNS, anomaly detection in the DNS, and a “DNS Workbench” enabling synthetic DNS workload generation for simulation and laboratory-based research on DNS configuration, management and performance.

This project consists of two complementary components. The scientific component will focus on empirical characterization of the DNS as a whole and in parts by developing and applying techniques from graph theory, statistics and machine learning. The engineering component will use findings from the empirical analysis to identify operational practices, to inform investigation of tools and to drive new insights about how the DNS is used in practice. The project will deliver new insights about how the DNS can be improved as well as new tools for deriving and replicating those insights.

This project will contribute a deeper understanding of what is usual, and what is unusual, with respect to the contents of the DNS. New techniques and findings from this project will lead to a more robust, manageable, and better performing DNS, which has potential to positively impact society as a whole. New materials for networking and data science courses will be developed based on our research. The students who work on the project will receive guidance and mentorship. Research results will be disseminated by publishing in respected academic conferences and workshops, and all software and data artifacts will be made available to the community.

The project webpage will be hosted at https://macro-dns.github.io The webpage will include an overview of the project, project participants, updates on latest results and publications. It will also include all software and data artifacts developed during the project. The webpage and associated repositories will be available on github on an on-going basis after the conclusion of the project.

Title:  Collaborative Research: IMR: MM-1C: Methods for Active Measurement of the Domain Name System

Investigators:  P. Barford (PI), M. Crovella (co-PI) and J. Sommers (co-PI)

Abstract: This project will investigate techniques for measuring the contents of the Domain Name System (DNS) toward the goal of producing a comprehensive census of all record types. The project will focus on developing methods for generating domain names that will be used in queries of the global DNS. Strategies for name generation that will be considered include making use of underutilized data sources and machine learning techniques including Large Language Models. New metrics and a system called EverDNS will be developed to evaluate the effectiveness of the name generation methods by sending high-speed queries to the DNS from different Internet vantage points.

The first component of this project will investigate techniques for assembling the largest-feasible collection of domain names that will be used as targets to query the global DNS. The second component will assess these techniques by developing EverDNS, which will include a prototype data collector and a centralized controller. EverDNS will build on state-of-the-art DNS measurement tools and augment their methods to capture the greatest amount of information within a limited measurement budget. This project will deliver new insights about how to assemble a comprehensive census of the DNS and new data sets for research that will be made available to the community.

The techniques created by this project will enable generation of data sets that will advance scientific understanding of the DNS. It is expected that the insights gained through this research will enable methods for ensuring a more robust, manageable, and better performing DNS. Given the critical role of DNS in the Internet, this project has the potential to positively impact society as a whole. New materials for networking and data science courses will be developed as a direct result of this project. Research results will be disseminated by publishing in respected academic conferences and workshops, and all software and data artifacts will be made available to the community.

The project webpage will be hosted at https://everdns.github.io The webpage will include an overview of the project, project participants, updates on latest results and publications. It will also include all software and data artifacts developed during the project. The webpage and associated repositories will be available on github on an on-going basis after the conclusion of the project.

[3] https://explore.wisc.edu/siftwinnow-july-2023

If you’re not exactly sure what ChatGPT is, Computer Science Professors Jerry Zhu and Fred Sala will get you up to speed in this video where they discuss the rise of this ever-evolving artificial intelligence tool that can “seemingly” answer any question you pitch to it. But what are its limitations? Our AI experts will explain.

https://www.youtube.com/watch?v=fxPoX5llT04

• Prof Yea-Seul Kim and her student had their paper, “Making Data-Driven Articles More Accessible: An Active Preference Learning Approach to Data Fact Personalization” receive an honorable mention award at DIS 2023. Well done! [1]
• Prof Kirthi Kandasamy and colleagues had their work, “Leveraging Reviews: Learning to Price with Buyer and Seller Uncertainty”, recognized as the Exemplary Artificial Intelligence Track paper at the ACM Conference on Economics and Computation (EC’23). Great job! [2]
• Prof Fred Sala and colleagues had their paper “Resonant Anomaly Detection with Multiple Reference Datasets” accepted into the Journal of High Energy Physics. Wonderful! [3]
• Prof Mohit Gupta and colleagues are organizing the IEEE ICCP (International Conference on Computational Photography) in Madison this year (July 28-30). More details here. Mohit encourages any and all who are around to attend. How cool! [4]
• Included below is \a summary of recent success from Security folks here at UW-Madison, who had eleven papers published at USENIX Security ‘23. Well done to all! (including Profs Barford, Chatterjee, Fawaz, Jha, McDaniel, Zhao) [5]
• Prof Tom Reps and colleagues received the 2023 CAV Award, for “the introduction of context-bounded analysis and its application to systematic testing of concurrent programs”. Amazing! Congratulations! See below for some of the cool history behind the work. [6]

————–

[1] https://dis.acm.org/2023/dis-2023-program/

 “Making Data-Driven Articles More Accessible: An Active Preference Learning Approach to Data Fact Personalization” received an honorable mention from DIS 2023.

Authors: Yanan Wang, Yea-Seul Kim

Data-driven news articles are widely used to communicate societal phenomena with concrete evidence. These articles are often accompanied by a visualization, helping readers to contextualize content. However, blind and low vision (BLV) individuals have limited access to visualizations, hindering a deep understanding of data. We explore the possibility of dynamically generating data facts (texts describing data patterns in a chart) for BLV individuals based on their preferences to aid the reading of such articles. We conduct a formative study to understand how they perceive system-generated data facts and the factors influencing their preferences. The results indicate the preferences are highly varied among individuals, and a simple preference elicitation alone induces noise. Based on the findings, we developed a method to personalize the data facts generation using an active learning approach. The evaluation studies demonstrate that our model converges effectively and provides more preferable sets of data facts than the baseline.

[2] https://ec23.sigecom.org/program/plenary-speakers/

“Leveraging Reviews: Learning to Price with Buyer and Seller Uncertainty”

Authors: Wenshuo Guo (UC Berkeley); Nika Haghtalab (UC Berkeley); Kirthevasan Kandasamy (UW Madison); Ellen Vitercik (Stanford University)

Abstract: In online marketplaces, customers have access to hundreds of reviews for a single product. Buyers often use reviews from other customers that share their type—such as height for clothing, skin type for skincare products, and location for outdoor furniture—to estimate their values, which they may not know a priori. Customers with few relevant reviews may hesitate to make a purchase except at a low price, so for the seller, there is a tension between setting high prices and ensuring that there are enough reviews so that buyers can confidently estimate their values. Simultaneously, sellers may use reviews to gauge the demand for items they wish to sell. In this work, we study this pricing problem in an online learning setting where the seller interacts with a set of buyers of finitely-many types, one-by-one, over a series of T rounds. At each round, the seller first sets a price. Then a buyer arrives and examines the reviews of the previous buyers with the same type, which reveal those buyers’ ex-post values. Based on the reviews, the buyer decides to purchase if they have good reason to believe that their ex-ante utility is positive. Crucially, the seller does not know the buyer’s type when setting the price, nor even the distribution over types. We provide a no-regret algorithm that the seller can use to obtain high revenue. When there are d types, after T rounds, our algorithm achieves a problem independent O˜(T 2/3d 1/3 ) regret bound. However, when the smallest probability qmin that any given type appears is large, specifically when qmin ∈ Ω(d −2/3T −1/3 ), then the same algorithm achieves a O˜(T 1/2 q −1/2 min ) regret bound. Our algorithm starts by setting lower prices initially, so as to (i) boost the number of reviews and increase the accuracy of future buyers’ value estimates while also (ii) allowing the seller to identify which customers need to be targeted to maximize revenue. This mimics real-world pricing dynamics. We complement these upper bounds with matching lower bounds in both regimes, showing that our algorithm is minimax optimal up to lower order terms

[3] “Resonant Anomaly Detection with Multiple Reference Datasets”

Authors: Mayee F. Chen, Benjamin Nachman, and Frederic Sala

Journal of High Energy Physics (JHEP)

Abstract: An important class of techniques for resonant anomaly detection in high energy physics builds models that can distinguish between reference and target datasets, where only the latter has appreciable signal. Such techniques, including Classification Without Labels (CWoLa) and  Simulation Assisted Likelihood-free Anomaly Detection (SALAD) rely on a single reference dataset. They cannot take advantage of commonly-available multiple datasets and thus cannot fully exploit available information. In this work, we propose generalizations of CWoLa and SALAD for settings where multiple reference datasets are available, building on weak supervision techniques. We demonstrate improved performance in a number of settings with realistic and synthetic data. As an added benefit, our generalizations enable us to provide finite-sample guarantees, improving on existing asymptotic analyses.

[4] https://iccp2023.iccp-conference.org/conference-program/

From Prof Gupta: “ICCP, over the past 15 years, has evolved into a highly inter-disciplinary venue for presenting novel imaging technologies – with presence from various communities, including imaging, optics, computer vision and ML. This year, we have a wonderful lineup of speakers (including several of our UW colleagues). If anyone is around and interested, please feel free to attend, and let me know if you have any questions.”

[5] CS at UW-Madison had 11 papers published at the top-tier conference USENIX Security 2023!  Topics in these areas are wide-ranging:

Abuse Vectors: A Framework for Conceptualizing IoT-Enabled Interpersonal Abuse

Sophie Stephenson and Majed Almansoori, University of Wisconsin–Madison; Pardis Emami-Naeini, Duke University; Danny Yuxing Huang, New York University; Rahul Chatterjee, University of Wisconsin–Madison

“It’s the Equivalent of Feeling Like You’re in Jail”: Lessons from Firsthand and Secondhand Accounts of IoT-Enabled Intimate Partner Abuse

Sophie Stephenson and Majed Almansoori, University of Wisconsin—Madison; Pardis Emami-Naeini, Duke University; Rahul Chatterjee, University of Wisconsin—Madison

Sneaky Spy Devices and Defective Detectors: The Ecosystem of Intimate Partner Surveillance with Covert Devices

Rose Ceccio and Sophie Stephenson, University of Wisconsin—Madison; Varun Chadha, Capital One; Danny Yuxing Huang, New York University; Rahul Chatterjee, University of Wisconsin—Madison

Tubes Among Us: Analog Attack on Automatic Speaker Identification

Shimaa Ahmed and Yash Wani, University of Wisconsin-Madison; Ali Shahin Shamsabadi, Alan Turing Institute; Mohammad Yaghini, University of Toronto and Vector Institute; Ilia Shumailov, Vector Institute and University of Oxford; Nicolas Papernot, University of Toronto and Vector Institute; Kassem Fawaz, University of Wisconsin-Madison

Araña: Discovering and Characterizing Password Guessing Attacks in Practice

Mazharul Islam, University of Wisconsin–Madison; Marina Sanusi Bohuk, Cornell Tech; Paul Chung, University of Wisconsin–Madison; Thomas Ristenpart, Cornell Tech; Rahul Chatterjee, University of Wisconsin–Madison

Automated Cookie Notice Analysis and Enforcement

Rishabh Khandelwal and Asmit Nayak, University of Wisconsin—Madison; Hamza Harkous, Google, Inc.; Kassem Fawaz, University of Wisconsin—Madison

The Space of Adversarial Strategies

Ryan Sheatsley, Blaine Hoak, Eric Pauley, and Patrick McDaniel, University of Wisconsin-Madison

Guarding Serverless Applications with Kalium

Deepak Sirone Jegan, University of Wisconsin-Madison; Liang Wang, Princeton University; Siddhant Bhagat, Microsoft; Michael Swift, University of Wisconsin-Madison

“If sighted people know, I should be able to know:” Privacy Perceptions of Bystanders with Visual Impairments around Camera-based Technology

Yuhang Zhao, University of Wisconsin—Madison; Yaxing Yao, University of Maryland, Baltimore County; Jiaru Fu and Nihan Zhou, University of Wisconsin—Madison

DScope: A Cloud-Native Internet Telescope

Eric Pauley, Paul Barford, and Patrick McDaniel, University of Wisconsin–Madison

Fairness Properties of Face Recognition and Obfuscation Systems

Harrison Rosenberg, University of Wisconsin–Madison; Brian Tang, University of Michigan; Kassem Fawaz and Somesh Jha, University of Wisconsin–Madison

[6] Tom Reps and his former Ph.D. student Akash Lal (now at MSR-India) are two of a group of five who received the 2023 CAV Award (http://i-cav.org/cav-award/), given annually at the CAV conference for fundamental contributions to the field of Computer-Aided Verification.

They were honored “for the introduction of context-bounded analysis and its application to systematic testing of concurrent programs.”  The other recipients are Shaz Qadeer (Meta), Madan Musuvathi (MSR), and Jakob Rehof (TU Dortmand).

The UW CS department has had one previous CAV Award recipient, Somesh Jha, who received it in 2015 for his part in the development of counterexample-guided abstraction refinement.

Backstory to the work, as shared by Tom:

In 2008, Akash and Reps, along with former student Nick Kidd and Tayssir Touili (CNRS), had developed a quite interesting, but complicated-to-explain, technique for context-bounded analysis.  Akash pointed out that he could greatly simplify the implementation task by just performing an equivalent source-to-source transformation.  He was just planning to implement the technique, but wasn’t thinking about writing a paper describing it.  Apparently, Reps said the opposite—and that became the paper for which we received the award (and journal version).  Although Reps has no memory of having insisted that he write it up, Akash said he was absolutely sure about it because their conversation was just six days before the CAV 2008 paper deadline.  Apparently, he got very little sleep during the following six days!  The moral of the story is “always listen to your advisor!”  😊

After Akash joined Microsoft Research India in 2009, he and others at Microsoft incorporated some of the ideas into an important tool for testing concurrent software, called Coyote, which was released open-source and also has had widespread adoption in the Azure components for compute, networking, storage, blockchain, and logistics, as well as Microsoft Teams.

• Emeritus Prof David Wood was selected for the ACM SIGARCH Alan D. Berenbaum Distinguished Service Award for “his exemplary stewardship of the SIGARCH-SIGHPC transition and his decades of leadership in the SIGARCH and broader computer architecture community”.  [1]
• Prof Christos Tzamos and Prof Ilias Diakonikolas had a paper at STOC ‘23 that somehow we missed last week in the FCRC round up (apologies!), entitled “A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning”.  [2]
• Prof Fred Sala was awarded a $100K seedling grant from the Army Research Lab STRONG program, for a proposal entitled “Leveling Up Human-Machine Collaborations by Leveraging Distributed Causal Insights”.  [3]
• Prof Yudong Chen’s SIGMETRICS paper (mentioned last week), entitled “Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure” received the best student paper award from SIGMETRICS.  [4]
• Prof Matt Sinclair participated on a panel entitled “The future of gem5” at the Gem5 workshop.  [5]
• Prof Paris Koutris and students’ paper “Space-Time Tradeoffs for Conjunctive Queries with Access Patterns” won a PODS Distinguished paper award.  [6]
• Prof Shiv Venkataraman and collaborators had a paper accepted to Supercomputing 2023 entitled “Mirage: Towards Low-interruption Services on Batch GPU Clusters with Reinforcement Learning”.  [7]

——————————–

[1] https://www.sigarch.org/benefit/awards/acm-sigarch-distinguished-service-award/

The award is presented annually at the International Symposium on Computer Architecture Awards Banquet. This year’s recipient will be invited to accept the award at ISCA 2023. Recipients receive a memento engraved with their name along with a $1000 honorarium. The award recipient also receives up to $2000 towards support for travel costs, including airfare, hotel, and conference registration for ISCA. The recipient is listed with a citation for their award on the SIGARCH Alan D. Berenbaum Distinguished Service Award webpage.

Past winners include:

Kathryn S McKinley, Per Stenström, Alvin R. Lebeck (UW alum and David’s Ph.D. student), Margaret Martonosi, Koen De Bosschere, Michael Flynn, Doug DeGroot, Norman P. Jouppi, David A. Patterson, Janie Irwin, Mark D. Hill (UW Emeritus Professor), and Alan Berenbaum.

[2] “A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning”

Ilias Diakonikolas, Christos Tzamos (UW Madison); Daniel Kane (UCSD)

STOC ‘23

https://dl.acm.org/doi/10.1145/3564246.3585191

The Forster transform is a method of regularizing a dataset by placing it in radial isotropic position while maintaining some of its essential properties. Forster transforms have played a key role in a diverse range of settings spanning computer science and functional analysis. Prior work had given weakly polynomial time algorithms for computing Forster transforms, when they exist. Our main result is the first strongly polynomial time algorithm to compute an approximate Forster transform of a given dataset or certify that no such transformation exists. By leveraging our strongly polynomial Forster algorithm, we obtain the first strongly polynomial time algorithm for distribution-free PAC learning of halfspaces. This learning result is surprising because proper PAC learning of halfspaces is equivalent to linear programming. Our learning approach extends to give a strongly polynomial halfspace learner in the presence of random classification noise and, more generally, Massart noise.

[3] https://www.arl.army.mil/cras/strong-cra/

[4] https://www.sigmetrics.org/sigmetrics2023/

[5] ISCA 2023: GEM5 WORKSHOP

Panel: The future of gem5

Panel Members: Mohammad Alian, Brad Beckmann, Gabriel Busnot, Jason Lowe-Power, Miquel Moreto, Matt Sinclair

Link: https://www.gem5.org/events/isca-2023

The gem5 Workshop is an opportunity for members of the gem5 community to give presentations on their contributions to gem5 and gem5-related research. This year’s workshop will start with a 25 minute keynote by Dr. Bobby R. Bruce, titled “gem5 v22, v23 and the future”, and will continue with presentations and discussion panels on gem5 topics.

[6] https://2023.sigmod.org/program_pods.shtml

[7] https://arxiv.org/abs/2306.14086

Mirage: Towards Low-interruption Services on Batch GPU Clusters with Reinforcement Learning

Qiyang Ding, Pengfei Zheng, Shreyas Kudari, Shivaram Venkataraman, Zhao Zhang

Accommodating long-running deep learning (DL) training and inference jobs is challenging on GPU clusters that use traditional batch schedulers, such as Slurm. Given fixed wall clock time limits, DL researchers usually need to run a sequence of batch jobs and experience long interruptions on overloaded machines. Such interruptions significantly lower the research productivity and QoS for services that are deployed in production. To mitigate the issues from interruption, we investigate a set of statistical learning and reinforcement learning (RL) techniques, including random forest, xgboost, Deep Q-Network, and policy gradient to design a proactive provisioner using production job traces from three GPU clusters. We follow the standard machine learning practice by partitioning each job trace into training and validation subsets, then train each model using the training subset and evaluate the generality using the validation subset. We introduce Mirage, a Slurm-compatible resource provisioner that integrates the candidate RL methods. Our experiments show that the Mirage can reduce the interruption by 17-100% and safeguard 23%-76% of jobs with zero interruption across varying load levels on the three clusters.

Congratulations to Prof Sharon Li for her NSF CAREER award entitled “Foundations of Human-Centered Machine Learning in the Wild”. Well done! [1]

It’s FCRC, which means a number of our colleagues are presenting their work in various conferences. Great job to all for their work! [2]

“Synthesizing Quantum-Circuit Optimizers”

PLDI ‘23

by Prof Swamit Tannu and Prof Aws Albarghouthi

“Psym: Efficient Symbolic Exploration of Distributed Systems”

PLDI ‘23
by Prof Aws Albarghouthi’s post-doc Lauren Pick and colleagues

“Towards Accelerating Data Intensive Application’s Shuffle Process Using SmartNICs” SIGMETRICS ‘23

by Prof Xiangyao Yu and colleagues

“Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes”

SIGMETRICS ‘23

by Prof Yudong Chen and colleagues

“Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with

Latent Low-Rank Structure”

SIGMETRICS ‘23

by Prof Yudong Chen and colleagues

“Scaling Qubit Readout with Hardware Efficient Machine Learning Architectures”

ISCA ‘23

by Prof Swammit Tannu and colleagues

“Enabling High Performance Debugging for Variational Quantum Algorithms

using Compressed Sensing”

ISCA ‘23

by Prof Swammit Tannu and colleagues

“The complexity of counting planar graph homomorphisms of domain size 3”

STOC ‘23

by Prof Jin-Yi Cai and colleague

———

[1] https://www.nsf.gov/awardsearch/showAward?AWD_ID=2237037&HistoricalAwards=false

Machine learning models today must operate amid increasingly dynamic and open environments. One important characteristic of open environments is that the intelligent system will encounter new contexts and out-of-distribution data; that is, data that were not used to train the algorithms the original system. However, current supervised learning is brittle, lacking a reliable understanding of the way data evolves over time and how to respond to changing environments. This introduces a set of new challenges and drives the need for rethinking the design of machine learning algorithms, that can detect out-of-distribution data and repair the learned model under evolving data in the wild. The project will directly impact many real-world domains including autonomous transportation, healthcare, commerce, and scientific discovery.

The objective of this project is to lay new foundations for safe, adaptive, and long-term beneficial learning algorithms in open-world environments. The project has a continuum of three research aims that will fundamentally transform the way that machine learning models are trained, updated, and monitored in the wild: (1) create a new learning framework for reliable decisions, rendering strong safety against unknowns upon deploying machine learning models in the wild; (2) accelerate model adaptation, learning to classify new concepts emerging in the wild while minimizing human supervision required; (3) characterize and understand dynamics in terms of long-term accuracy and safety, maximizing the impact of models as they evolve and operate in the long run. The education plan will publicize the power of open-world machine learning through a new course, a new undergraduate mentorship program ‘Entering AI Research’ and outreach efforts.

[2] https://fcrc.acm.org/

Lots to look through there; check it out?

• Congratulations to Prof Ilias Diakonikolas, for his promotion to Full Professor.
• Congratulations to Prof Yingyu Liang, for his promotion to Associate Professor.
• Congratulations to Prof Efty Sifakis, for his promotion to Full Professor.

• Prof Ilias Diakonikolas
• Prof Jelena Diakonikolas
• Prof Christos Tzamos
• Prof Dimitris Papailiopoulos (ECE)

• Emeritus Prof Jeff Naughton’s student, Joe Hellerstein (Ph.D., ‘95, Prof at UC Berkeley since then), won this year’s Edgar F. Codd Innovations Award, which is given for “innovative and highly significant contributions of enduring value to the development, understanding, or use of database systems and databases.” This is the seventh person with Wisconsin roots/connections to have won the award! (David DeWitt, Rakesh Agrawal, Michael Carey, Goetz Graefe, Raghu Ramakrishnan, Anastasia Ailamaki being the others). [1]
• Prof Matt Sinclair gave a talk entitled “Simulating and Modeling Hardware for Machine Learning Workloads at Scale” at an SRC AIHW Annual Review. [2]
• Prof Mike Gleicher and colleagues have a paper entitled “A Problem Space for Designing Visualizations” set to appear IEEE Computer Graphics and Applications. [3]
• Check out this video about incoming Provost Prof Charles Isbell[4]

Notes:

[1] The SIGMOD Edgar F. Codd Innovations Award is given for innovative and highly significant contributions of enduring value to the development, understanding, or use of database systems and databases. Until 2003, this award was known as the “SIGMOD Innovations Award.” In 2004, SIGMOD, with the unanimous approval of ACM Council, decided to rename the award to honor Dr. E.F. (Ted) Codd (1923 – 2003) who invented the relational data model and was responsible for the significant development of the database field as a scientific discipline.

https://sigmod.org/sigmod-awards/sigmod-edgar-f-codd-innovations-award/

[2] Title: Simulating and Modeling Hardware for Machine Learning Workloads at Scale

Abstract: As both the size of Machine Learning (ML) and Artificial Intelligence (AI) hardware and the data they operate on scale-up, there is a growing challenge in performing early-system exploration based on sound simulation methodology. Using existing tools and infrastructure, a detailed simulation of a contemporary deep neural network can take years. In addition, the difficult task of modeling energy at scale, without working RTL for a newly proposed accelerator, or accelerator component (i.e., Tensor Cores), remains an important research challenge. In particular modeling energy in a way that is flexible and can be extended to both different types of programmable accelerators (like GPUs) and to more bespoke discrete accelerators (like TPUs) is needed.

The broad goals of this proposal are to (1) reduce detailed simulation time, particularly on ML training and inference workloads, by characterizing execution in silicon, validated with detailed simulation, to find representative program slices, (2) develop a flexible energy model for accelerators, and (3) develop infrastructure to model the multi-GPU and multi-accelerator system of the future. To tackle these problems, we propose to extend existing simulation infrastructure, such as gem5, to create a scalable, parallel simulation framework that models diverse system components with varying levels of detail. In this talk, I discuss our on-going efforts to identify the most important parts of the applications to simulate at high fidelity while reducing simulation time.

[3] https://arxiv.org/abs/2303.06257

“A Problem Space for Designing Visualizations”

Michael Gleicher, Maria Riveiro, Tatiana von Landesberger, Oliver Deussen, Remco Chang, Christina Gillman

To appear in IEEE CG&A this summer

Abstract: Visualization researchers and visualization professionals seek appropriate abstractions of visualization requirements that permit considering visualization solutions independently from specific problems. Abstractions can help us design, analyze, organize, and evaluate the things we create. The literature has many task structures (taxonomies, typologies, etc.), design spaces, and related “frameworks” that provide abstractions of the problems a visualization is meant to address. In this viewpoint, we introduce a different one, a problem space that complements existing frameworks by focusing on the needs that a visualization is meant to solve. We believe it provides a valuable conceptual tool for designing and discussing visualizations.

[4] Video: https://youtu.be/njMJ7lPIfsw

Title: “Charles Isbell”

Prof Ming Liu, Prof Mike Swift, and students had the paper “LEED: A Low-Power, Fast Persistent Key-Value Store on SmartNIC JBOFs” accepted into SIGCOMM ‘23.  [1]

Prof Mike Gleicher’s student Keaton Leppanen won a Chateaubriand Fellowship to spend a semester collaborating with colleagues in Paris [2].

Incoming Provost, and soon-to-be CS Prof Charles Isbell, won the 2023 Richard A. Tapia Achievement Award for Scientific Scholarship, Civic Science, and Diversifying Computing. [3]

Notes:

[1] “LEED: A Low-Power, Fast Persistent Key-Value Store on SmartNIC JBOFs”

Zerui Guo, Hua Zhang, Chenxingyu Zhao, Yuebin Bai, Michael Swift, Ming Liu
SIGCOMM ‘23

Abstract: The recent emergence of low-power high-throughput programmable storage platforms–SmartNIC JBOF (just-a-bunch- of-flash)–motivates us to rethink the cluster architecture and system stack for energy-efficient large-scale data-intensive workloads. Unlike conventional systems that use an array of server JBOFs or embedded storage nodes, the introduction of SmartNIC JBOFs has drastically changed the cluster compute, memory, and I/O configurations. Such an extremely imbalanced architecture makes prior system design philosophies and techniques either ineffective or invalid.

This paper presents LEED, a distributed, replicated, and persistent key-value store over an array of SmartNIC JBOFs. Our key ideas to tackle the unique challenges induced by a SmartNIC JBOF are: trading excessive I/O bandwidth for scarce SmartNIC core computing cycles and memory capacity; making scheduling decisions as early as possible to streamline the request execution flow. LEED systematically revamps the software stack and proposes techniques across per-SSD, intra-JBOF, and inter-JBOF levels. Our prototyped system based on Broadcom Stingray outperforms existing solutions that use beefy server JBOFs and wimpy embedded storage nodes by 4.2X/3.8X and 17.5X/19.1X in terms of requests per Joule for 256B/1KB key-value objects.

[2] https://www.chateaubriand-fellowship.org/

The Chateaubriand Fellowship is a grant offered by the Embassy of France in the United States. It supports outstanding PhD students from U.S. institutions who wish to conduct part of their doctoral research in France for a period ranging from 4 to 8/9 months. Chateaubriand fellows are selected through a merit-based competition, with expert evaluation in France and in the United States.

[3] https://tapiaconference.cmd-it.org/about/richard-tapia-award/

CMD-IT proudly announces Dr. Charles Isbell as the 2023 recipient of the Richard A. Tapia Achievement Award for Scientific Scholarship, Civic Science, and Diversifying Computing. Dr. Isbell is currently The John P. Imlay Dean of the College of Computing at Georgia Tech. This fall, he will be joining the University of Wisconsin–Madison’s leadership team as the next Provost. Throughout his career, Dr. Isbell has contributed to broadening participation in computing, including serving as the founding Executive Director for the Constellations Center for Equity in Computing.

The Richard A. Tapia Achievement Award for Scientific Scholarship, Civic Science, and Diversifying Computing is presented to a distinguished computational scientist, computer scientist, or computer engineer who is making significant contributions to computing and civic areas, including teaching, mentoring, advising, and building and serving diverse communities. The award winner represents extraordinary leadership in computing scholarship and the mission to increase participation of groups who are underrepresented in computing.

The award presentation will take place during the awards ceremony at the CMD-IT/ACM Richard Tapia Celebration of Diversity in Computing Conference in Dallas, Texas, September 13-15, 2023.

Prof Swamit Tannu will be giving talks at the Next Steps in Quantum Computing Workshop and at Chalmers and Uppsala universities in Sweden, with talks entitled “Scaling and Sustaining Quantum Cloud Computing Paradigm” and “Scalable Quantum Computer Architecture: A Frontier for Systems and Computer Architects”. [1]

Prof Bilge Mutlu with collaborators from ECE (Kassam Fawaz – CS Affiliate) and SOHE (Heather Kirkorian) received new NSF funding, titled “SaTC: CORE: Medium: Designing Privacy-Aware Social Companion Robots.”  [2]

Prof Karu Sankaralingam and many collaborators at WiSys and across campus were awarded an NSF Regional Innovation Engine award. This is one of two awards across the state, and of 43 awards nationally, and comes from NSF’s new Directorate for Technology, Innovation and Partnerships as authorized by the “CHIPS and Science Act of 2022”.  [3]

Prof Bilge Mutlu and student Amy Koike have a new paper accepted to 2023 ACM Designing Interactive Systems, titled “Exploring the Design Space of Extra-Linguistic Expression for Robots.” [4]

The CS department held its biggest graduation ceremonies ever, celebrating the graduation of over 700 undergraduates, 75 masters students, and 10 or so Ph.D. students, over four ceremonies (two undergraduate ones were needed).

Notes:

[1] “Scaling and Sustaining Quantum Cloud Computing Paradigm”

Swamit Tannu

Venue: Next Steps in Quantum Computing Workshop https://cra.org/ccc/events/5-year-update-to-the-next-steps-in-quantum-computing-workshop/

“Scalable Quantum Computer Architecture: A Frontier for Systems and Computer Architects”

Swamit Tannu

Chalmers University (Sweden) and Uppsala University (Sweden)

Abstract: Quantum computers leverage fundamental quantum-mechanical properties of their constituent quantum bits (qubits) to gain a computational advantage for a class of problems. Today, scientists and engineers are racing to build larger, more-reliable quantum computers and demonstrate their effectiveness at evaluating increasingly complex quantum algorithms. Unfortunately, qubits are extremely sensitive to noise. Thus the ultimate goal is to build a large-scale quantum computer that can run quantum error correction to enable fault-tolerant computations to demonstrate a computational advantage for significant scientific and commercial problems. However, scaling quantum computers is challenging on several fronts, including technology, engineering, systems, and economics. Computer architects will play a crucial role in building quantum computing ecosystems.

In this talk, I will introduce a few challenges in building fundamental architectural blocks for quantum computers and strategies we can adopt to mitigate those challenges.

[2] SaTC: CORE: Medium: Designing Privacy-Aware Social Companion Robots

Bilge Mutlu, Kassam Fawaz, Heather Kirkorian

Social companion robots can interact with people in a human-like way, using speech, gestures, and physical presence. They are designed to help families with activities like meal planning, child development, and communication. However, their advanced sensing and reasoning capabilities can lead to privacy concerns, as they can collect, infer, and share personal information about their users. For instance, they can overhear private conversations as they move and act in the home. They also require access to sensitive environments, such as bedrooms, and can be designed to look like familiar objects or people, which can lead to people oversharing personal information. They might also inappropriately disclose information they learned with other home occupants or visitors. Therefore, it is crucial to design more “privacy-aware” social companion robots that can reason about when to collect and share data, and when not to, in ways that are context-appropriate and match people’s needs for privacy. This interdisciplinary project aims to create privacy-aware design principles for privacy-aware social robots to improve human-robot interactions in home environments. These principles will inform how robots are designed, used, and accepted in homes, workplaces, schools, and healthcare. Further, through outreach activities, the project will improve families’ understanding of privacy in smart environments through media coverage, workshops, and office hours. The educational activities of the project will train K-12 and college students in privacy systems, family studies, and human-computer interaction. Finally, the project team will share code, publications, prototypes, and datasets based on the work.

This project develops, implements, and evaluates a novel privacy framework for human-robot interaction in four phases. This framework models users’ privacy expectations, employs novel concepts grounded in human-robot interaction, develops new methods to help users manage their own privacy, and enables a study of privacy dynamics within families. Specifically, Phase I models users’ privacy concerns and expectations regarding social robots, developing a privacy framework to identify everyday situations in which privacy awareness is most important. Phase II instantiates the framework as a privacy controller for the robot’s actions that captures the dynamics of social privacy. At the core of the privacy controller is a customizable architecture that extracts high-level contextual factors from the robot’s environment, such as location in the house and number of people present, and generates privacy-aware actions. Phase III explores how the robot can leverage the privacy controller architecture to signal, demonstrate, or explain the robot’s privacy-aware actions to users. Through deployment studies, Phase IV assesses the impact of privacy awareness on the robot’s management of the complex privacy trade-offs involved in participation in family life. The findings of these studies will provide an empirical basis for understanding a privacy-aware social robot’s benefits, effects, and limitations on family dynamics.

[3]  Prof Sankaralingam, along with a team led by WiSys, was awarded an NSF Regional Innovation Engine award. This is one of two awards across the state, and of 43 awards nationally. Launched by NSF’s new Directorate for Technology, Innovation and Partnerships and authorized by the “CHIPS and Science Act of 2022,” the NSF Engines program uniquely harnesses the nation’s science and technology research and development enterprise and regional-level resources. NSF Engines aspire to catalyze robust partnerships to positively impact the economy within a geographic region, address societal challenges, advance national competitiveness and create local, high-wage jobs. The WiSys engine in particular is on Agtech and Sustainable agriculture driven by Artificial Intelligence, Advanced Materials, Disaster Mitigation/Prevention, Energy & Industrial Efficiency Tech, BigData and Cybersecurity. Senator Tammy Baldwin’s office has a press release on this announcement and WiSys press release has more details on the project.

https://www.baldwin.senate.gov/news/press-releases/senator-baldwin-helps-secure-funding-for-regional-innovation-engines-in-wisconsin

https://www.wisys.org/news-media/wisys-led-partnership-wins-1-million-nsf-grant-to-make-wisconsin-a-global-leader-in-sustainable-ag

[4] “Exploring the Design Space of Extra-Linguistic Expression for Robots”

Prof. Mutlu and CS graduate student Amy Koike

2023 ACM Designing Interactive Systems

We explore the new design space of extra-linguistic cues inspired from graphical tropes used in graphic novels and animation to enhance the expressiveness of social robots. To achieve this, we identified a set of cues that can be used to generate expressions, including smoke/steam/fog, water droplets, and bubbles. We prototyped devices that can generate these fluid expressions for a robot and conducted design sessions where eight designers explored the use and utility of the cues in conveying the robot’s internal states in various design scenarios. Our analysis of the 22 designs, the associated design justifications, and the interviews with designers revealed patterns in how each cue was used, how they were combined with nonverbal cues, and where the participants drew their inspiration from. These findings informed the design of an integrated module called EmoPack, which can be used to augment the expressive capabilities of any robot platform.

Prof Kirthi Kandasamy and collaborators had the paper “Leveraging Reviews: Learning to Price with Buyer and Seller Uncertainty” accepted at the ACM Conference on Economics and Computation (EC’23).  [1]

Prof Matt Sinclair and collaborators had four papers accepted into the gem5 Users’ workshop entitled “Closing the Gap: Improving the Accuracy of gem5’s GPU Models”, “Improving gem5’s GPUFS Support”, “Analyzing the Benefits of More Complex Cache Replacement Policies in Moderns GPU LLCs”, and “Improving the Speed of gem5’s GPU Regression Tests”.  [2]

Prof Bart Miller gave a Distinguished Lecture at the CISPA security research center (the largest federally funded security center in Germany) at the University of Saarbruecke entitled “Random Testing with ‘Fuzz’: 30 Years of Finding Bugs”. [3]

Prof Karu Sankaralingam and collaborators had the paper “Making Transformers Compute-lite for CPU inference” accepted at ICML. [4]

Prof Paris Koutris and collaborators published “The Fine-Grained Complexity of Boolean Conjunctive Queries and Sum-Product Problems” at ICALP ‘23. [5]

Prof Jignesh Patel (with collaboration from our partners at gener8tor) ran another successful instantiation of the NEST competition, which provides year-long training and exposure for students in entrepreneurship.  [6].

Notes:

[1] “Leveraging Reviews: Learning to Price with Buyer and Seller Uncertainty”

Authors: Wenshuo Guo (UC Berkeley); Nika Haghtalab (UC Berkeley); Kirthevasan Kandasamy (UW Madison); Ellen Vitercik (Stanford University)

Abstract: In online marketplaces, customers have access to hundreds of reviews for a single product. Buyers often use reviews from other customers that share their type—such as height for clothing, skin type for skincare products, and location for outdoor furniture—to estimate their values, which they may not know a priori. Customers with few relevant reviews may hesitate to make a purchase except at a low price, so for the seller, there is a tension between setting high prices and ensuring that there are enough reviews so that buyers can confidently estimate their values. Simultaneously, sellers may use reviews to gauge the demand for items they wish to sell. In this work, we study this pricing problem in an online learning setting where the seller interacts with a set of buyers of finitely-many types, one-by-one, over a series of T rounds. At each round, the seller first sets a price. Then a buyer arrives and examines the reviews of the previous buyers with the same type, which reveal those buyers’ ex-post values. Based on the reviews, the buyer decides to purchase if they have good reason to believe that their ex-ante utility is positive. Crucially, the seller does not know the buyer’s type when setting the price, nor even the distribution over types. We provide a no-regret algorithm that the seller can use to obtain high revenue. When there are d types, after T rounds, our algorithm achieves a problem independent O˜(T 2/3d 1/3 ) regret bound. However, when the smallest probability qmin that any given type appears is large, specifically when qmin ∈ Ω(d −2/3T −1/3 ), then the same algorithm achieves a O˜(T 1/2 q −1/2 min ) regret bound. Our algorithm starts by setting lower prices initially, so as to (i) boost the number of reviews and increase the accuracy of future buyers’ value estimates while also (ii) allowing the seller to identify which customers need to be targeted to maximize revenue. This mimics real-world pricing dynamics. We complement these upper bounds with matching lower bounds in both regimes, showing that our algorithm is minimax optimal up to lower order terms

[2] The gem5 Users’ workshop details are found here:

https://www.gem5.org/events/isca-2023

[A] “Closing the Gap: Improving the Accuracy of gem5’s GPU Models”

Authors: Vishnu Ramadas, Daniel Kouchekinia, Ndubuisi Osuji, and Matthew D. Sinclair

Abstract: In recent years, we have been enhancing and updating gem5’s GPU support, including enhanced gem5’s GPU support to enable running ML workloads. Moreover, we created, validated, and released a Docker image with the proper software and libraries needed to run AMD’s GCN3 and Vega GPU models in gem5. With this container, users can run the gem5 GPU model, as well as build the ROCm applications that they want to run in the GPU model, out of the box without needing to properly install the appropriate ROCm software and libraries. Additionally, we updated gem5 to make it easier to reproduce results, including releasing support for a number of GPU workloads in gem5-resources and enabling continuous integration testing for a variety of GPU workloads.

Current gem5 support focuses on Carrizo- and Vega-class GPUs. Unfortunately, these models do not always provide high accuracy relative to the equivalent ”real” GPUs. This leads to a mismatch in expectations: when prototyping new optimizations in gem5 users may draw the wrong conclusions about the efficacy of proposed optimizations if gem5’s GPU models do not provide high fidelity. Accordingly, to help bridge this divide, we design a series of micro-benchmarks designed expose the latencies, bandwidths, and sizes of a variety of GPU components on real GPUs. By iteratively applying fixes and improvements to gem’s GPU model, we significantly improve its fidelity relative to real AMD GPUs.

[B] “Improving gem5’s GPUFS Support”

Authors: Vishnu Ramadas, Matthew Poremba, Bradford M. Beckmann, and Matthew D. Sinclair

Abstract: With the waning of Moore’s Law and the end of Dennard’s Scaling, systems are turning towards heterogeneity, mixing conventional cores and specialized accelerators to continue scaling performance and energy efficiency. Specialized accelerators are frequently used to improve the efficiency of computations that run inefficiently on conventional, general-purpose processors. As a result, systems ranging from smartphones to data-centers, hyper-scalars, and supercomputers are increasingly using large numbers of accelerators to provide better efficiency than CPU-based solutions. However, heterogeneous systems face key challenges: changes to the underlying technology which threaten continued scaling, as well as the voracious scaling from applications, which require additional research to address. Traditionally, simulators could be used to perform early exploration for this research. However, existing simulators lack important support for these key challenges.

Detailed simulation of modern systems can take extremely long times in existing tools and infrastructure. Furthermore, prototyping optimizations at scale can also be challenging, especially for newly proposed accelerators. Although other simulators such as Accel-Sim, SCALE-Sim, and Gemmini enable some early experiments, they are limited in their ability to target a wide variety of accelerators. In comparison, gem5 has support for various CPUs, GPUs, DSPs, and many other important accelerators. However, efficiently simulating large-scale workloads on gem5’s cycle-level models requires prohibitively long times. In this work we discuss our efforts to enhance gem5’s support to make running these workloads practical while retaining accuracy.

[C] “Analyzing the Benefits of More Complex Cache Replacement Policies in Moderns GPU LLCs”

Authors: Jarvis Jia and Matthew D. Sinclair

Abstract: The gem5 simulator offers Classic and Ruby as two separate memory models for simulating on-chip caches. The Classic model, which originated from M5, is a quick and simple option that allows for easy configuration, but only supports a basic MOESI coherence protocol. On the other hand, the Ruby model, which was developed by GEMS, is a more advanced and flexible option that can accurately simulate a wider range of cache coherence protocols and features. However, choosing between the two memory system models in gem5 is challenging for researchers as each has advantages and limitations which can be inconvenient. In particular, this has led to a bifurcation of effort where prior work has added replacement policies to Classic and Ruby in parallel – duplicating effort unnecessarily and preventing users from using a desired replacement policy if it is not implemented in the desired memory model (e.g., users could only use RRIP in Classic).

Accordingly, we merged the cache replacement policies from Classic to Ruby, enabling users to use any of the replacement policies in either memory model. Gem5 currently has the capability to support 13 replacement policies, which can be used exchangeable within the Classic and Ruby cache models, including commonly used options like LRU, FIFO, PseudoLRU, and different types of RRIPs. After combining the replacement policies for the Classic and Ruby cache models, we designed and integrated (into gem5’s nightly regressions) multiple corner case tests to verify and ensure the continued correct functionality of these policies. Through these tests, we identified and fixed several bugs to ensure that the  replacement policies operate correctly. Finally, with the newly enabled and verified functionality, since there is limited information about how different replacement policies affects GPU performance, we decided to use gem5 to study these policies in a GPU context. Specifically, we study GPU LLC caches, and show how different replacement policies impact performance for both WT and WB LLC caches of various sizes.

[D] Improving the Speed of gem5’s GPU Regression Tests

Authors: James Braun and Matthew D. Sinclair

Abstract: In recent years, we have been enhancing and updating gem5’s GPU support, including enhanced gem5’s GPU support to enable running ML workloads. Moreover, we created, validated, and released a Docker image with the proper software and libraries needed to run AMD’s GCN3 and Vega GPU models in gem5. With this container, users can run the gem5 GPU model, as well as build the ROCm applications that they want to run in the GPU model, out of the box without needing to properly install the appropriate ROCm software and libraries. Additionally, we updated gem5 to make it easier to reproduce results, including releasing support for a number of GPU workloads in gem5-resources and enabling continuous integration testing for a variety of GPU workloads.

However, in an effort to provide sufficient coverage, the current testing support for GPU tests requires significant runtime both for the nightly and weekly regression tests. Currently most of these regression tests test the GPU SE mode support, since GPU FS mode support is still nascent. Unfortunately, much of this time is spent parsing input files to create arrays and other data structures that the GPU subsequently computes on. Although SE mode does not simulate the system calls needed to read these input files, nevertheless this still represents a significant overhead that increases runtime and prevents other tests (potentially providing additional coverage) from being run in that same timeframe. In an effort to address this, in the work we utilize SE mode’s avoiding modeling system calls to speed up the runtime of the GPU regression tests. Specifically, we redesign the input reading phase of these GPU tests to create and use mmap’d files for their input arrays (which SE mode completes all at once) instead of reading in the files entry by entry. In doing so, we reduce runtime by at least 41%

[3] “Random Testing with ‘Fuzz’: 30 Years of Finding Bugs”

Barton Miller

Fuzz testing has passed its 30th birthday and, in that time, has gone from a disparaged and mocked technique to one that is the foundation of many efforts in software engineering and testing. The key idea behind fuzz testing is using random input and having an extremely simple test oracle that only looks for crashes or hangs in the program. Importantly, in all our studies, all our tools, test data, and results were made public so that others could reproduce the work. In addition, we located the cause of each failure that we caused and identified the common causes of such failures.

In the last several years, there has been a huge amount of progress and new developments in fuzz testing. Hundreds of papers have been published on the subject and dozens of PhD dissertations have been produced. In this talk, I will review the progress over the last 30 years describing our simple approach – using what is now called black box generational testing – and show how it is still relevant and effective today.

In 1990, we published the results of a study of the reliability of standard UNIX application/utility programs. This study showed that by using simple (almost simplistic) random testing techniques, we could crash or hang 25-33% of these utility programs. In 1995, we repeated and significantly extended this study using the same basic techniques: subjecting programs to random input streams. This study also included X-Window applications and servers. A distressingly large number of UNIX applications still crashed with our tests. X-window applications were at least as unreliable as command-line applications. The commercial versions of UNIX fared slightly better than in 1990, but the biggest surprise was that Linux and GNU applications were significantly more reliable than the commercial versions.

In 2000, we took another stab at random testing, this time testing applications running on Microsoft Windows. Given valid random mouse and keyboard input streams, we could crash or hang 45% (NT) to 64% (Win2K) of these applications. In 2006, we continued the study, looking at both command-line and GUI-based applications on the relatively new Mac OS X operating system. While the command-line tests had a reasonable 7% failure rate, the GUI-based applications, from a variety of vendors, had a distressing 73% failure rate. Recently, we decided to revisit our basic techniques on commonly used UNIX systems. We were interested to see that these techniques were still effective and useful.

In this talk, I will discuss our testing techniques and then present the various test results in more details. These results include, in many cases, identification of the bugs and the coding practices that caused the bugs. In several cases, these bugs introduced issues relating to system security. The talk will conclude with some philosophical musings on the current state of software development. Papers on the four studies (1990, 1995, 2000, 2006, and 2020), the software and the bug reports can be found at the UW fuzz home page:

http://www.cs.wisc.edu/~bart/fuzz/

More details: https://cispa.de/dls-miller

[4] “Making Transformers Compute-lite for CPU inference”

Authors: Zhanpeng Zeng, Michael Davies, Pranav Pulijala, Karthikeyan Sankaralingam, Vikas Singh

While GPU clusters remain the de facto choice for training large deep neural network (DNN) models today, a number of reasons including ease of workflow/deployment, security and cost have led to efforts investigating whether CPUs may be viable platforms for inference in day-to-day use across many sectors of the industry. But the imbalance between the compute capabilities of GPUs and CPUs is huge, which has prompted both specialized hardware enhancements from major vendors as well as evaluating which algorithmic modifications can make deployment more CPU friendly. Motivated by these considerations, we study a module which is a workhorse within modern DNN architectures, Feed Forward Networks (FFNs) and assess to what extent it can be made compute- (or FLOP-) lite. Our formulation recasts most essential operations as a memory look-up, leveraging the trade-off between the two resources on any platform: compute and memory (since CPUs offer it in abundance). Our development involves a careful redesign of each operation in a FFN, complemented with a detailed hardware profiling of strategies that will maximize efficiency — not just on contemporary hardware but on products that will be offered in the near/medium term future. While our use case is CPU inference, our method is differentiable and can be trained in an end-to-end manner via back-propagation, which enables easy training and integration into common DNN models.

[5] “The Fine-Grained Complexity of Boolean Conjunctive Queries and Sum-Product Problems”

Authors: Austen Z. Fan, Paraschos Koutris, Hangdong Zhao

ICALP ‘23

Abstract: We study the fine-grained complexity of evaluating Boolean Conjunctive Queries and their generalization to sum-of-product problems over an arbitrary semiring. For these problems, we present a general semiring-oblivious reduction from the k-clique problem to any query structure (hypergraph). Our reduction uses the notion of embedding a graph to a hypergraph, first introduced by Marx. As a consequence of our reduction, we can show tight conditional lower bounds for many classes of hypergraphs, including cycles, Loomis-Whitney joins, some bipartite graphs, and chordal graphs. These lower bounds have a dependence on what we call the clique embedding power of a hypergraph H, which we believe is a quantity of independent interest. We show that the clique embedding power is always less than the submodular width of the hypergraph, and present a decidable algorithm for computing it.

[6] NEST Competition results:

Congratulations to the 2023 CS NEST Pitch Competition Winners!!

1st: Crib – $5,000 (Isaac Lee, Vinesh Janarthanan)

2nd: PhD Insiders – $2,500 (Jake Khoussine)

3rd: Stuniverse – $1,500 (Nikolai Grin, Takuzen Lu)

WI Idea: GünGellir – $1,000 (Asude Aydagul)

We were fortunate enough to have a highly experienced judging panel providing feedback and questions to all the presenting teams. Huge thanks to them!

Dave Fuhrmann – Epic, Senior VP

Jack Koziol – UW-Madison, Entrepreneur in Residence & Infosec, Exited Founder

Adhira Sunkara – WiSys, Assistant Director

Wes Schroll – Fetch, Founder & CEO

To anyone interested in creating new technologies or launching a business – join us next semester! CS NEST is a venture creation program designed to help entrepreneurially minded students, postdocs, and recent alumni create high growth startups. CS NEST is a partnership between UW Computer Sciences, WARF, and gener8tor.

Each April we end the program with a pitch competition and the opportunity for teams to win prize money.

For more info about the program and/or competition, reach out to the CS NEST Director, Jake Pollastrini at jake.pollastrini@gener8tor.com

Prof Ming Liu had the paper “Fabric-Centric Computing” accepted into the HotOS ‘23 workshop.  [1]

Prof Yea-Seul Kim (with help from the curriculum committee and other HCI faculty) had the following course approved: COMP SCI 565: Introduction to Data Visualization. [2]

Prof Mohit Gupta (with help from the curriculum committee and other Vision faculty) had the following course approved: COMP SCI 566: Introduction to Computer Vision. [3]

Prof Suman Banerjee, Prof Mohit Gupta, and colleagues had the paper “QfaR: Location-Guided Scanning of Visual Codes from Long Distances” accepted into MobiCom ‘23.  [4]

Prof Andrea Arpaci-Dusseau and Prof Remzi Arpaci-Dusseau and colleagues had the paper “WiscSort: External Sorting For Byte-Addressable Storage” accepted into PVLDB. [5]

There was a wonderful article about Prof Miron Livny and his recent Vilas honors here. [6]

Prof Rahul Chatterjee’s (and affiliated Prof Kassem Fawaz’s) student Paul Chung wins the Goldwater Scholarship.  [7]

Notes:

[1] Title: Fabric-Centric Computing

Author: Ming Liu

Abstract:

Emerging memory fabrics and the resulting composable infrastructure have fundamentally challenged our conventional wisdom on how to build efficient rack/cluster-scale systems atop. This position paper proposes a new computing paradigm–called Fabric-Centric Computing (FCC)–that views the memory fabric as the first-class citizen to instantiate, orchestrate, and reclaim computations over composable infrastructure. We describe its design principles, report our early experiences, and discuss a new intermediate system stack proposal that harnesses the uniqueness of this cluster interconnect and realizes the version of FCC.

[2] COMP SCI 565: Introduction to Data Visualization

Created by Prof Yea-Seul Kim

Introduction to topics such as perception, cognition, communication, design, implementation, applications, tools, and evaluation. Provides a broad survey of the field and covers fundamental concepts, theory, and tools in data visualization with opportunities for hands-on activities. Gain real-world experience in designing and evaluating visualizations.

[3] COMP SCI 566: Introduction to Computer Vision

Created by Prof Mohit Gupta

Topics include image formation, feature detection, motion estimation, image mosaics, 3D shape reconstruction, and object recognition. Applications of these techniques include building 3D maps, creating virtual characters, organizing photo and video databases, human computer interaction, video surveillance, and automatic vehicle navigation. Broad overview of various computer vision and machine learning techniques and sensing and imaging technologies used in computer vision applications. This is a project-based course.

[4] QfaR: Location-Guided Scanning of Visual Codes from Long Distances

Authors: Sizhuo Ma (Snap Research), Jian Wang (Snap Research), Wenzheng Chen (U. Toronto), Suman Banerjee, Mohit Gupta, and Shree Nayar (Snap Research)

Abstract: Visual codes such as QR codes provide a low-cost and convenient communication channel between physical objects and mobile devices, but typically operate when the code and the device are in close physical proximity. We propose a system, called QfaR, which enables mobile devices to scan visual codes across long distances even where the image resolution of the visual codes is extremely low. QfaR is based on {\em location-guided code scanning}, where we utilize a crowdsourced database of physical locations of codes. Our key observation is that if the approximate location of the codes and the user is known, the space of possible codes can be dramatically pruned down. Then, even if every “single bit” from the low-resolution code cannot be recovered, QfaR can still identify the visual code from the pruned list with high probability. By applying computer vision techniques, QfaR is also robust against challenging imaging conditions, such as tilt, motion blur,\etc. Experimental results with common iOS and Android devices show that QfaR can significantly enhance distances at which codes can be scanned, \eg 3.6cm-sized codes can be scanned at a distance of 7.5 meters, and 0.5m-sized codes at about 100 meters. QfaR has many potential applications, and beyond our diverse experiments, we also conduct a simple case study on its use for efficiently scanning QR code-based badges to estimate event attendance.

[5] WiscSort: External Sorting For Byte-Addressable Storage

Vinay Banakar, Kan Wu (Google), Yuvraj Patel (Edinburgh), Kim Keeton (Google), Andrea Arpaci-Dusseau, Remzi Arpaci-Dusseau

PVLDB ‘23

Abstract: We present WiscSort, a new approach to high-performance con- current sorting for existing and future byte-addressable storage (BAS) devices. WiscSort carefully reduces writes, exploits random reads by splitting keys and values during sorting, and performs interference-aware scheduling with thread pool sizing to avoid I/O bandwidth degradation. We introduce the BRAID model which encompasses the unique characteristics of BAS devices. Many state- of-the-art sorting systems do not comply with the BRAID model and deliver sub-optimal performance, whereas WiscSort demonstrates the effectiveness of complying with BRAID. We show that WiscSort is 2-7x faster than competing approaches on a standard sort benchmark. We evaluate the effectiveness of key-value sepa- ration on different key-value sizes and compare our concurrency optimizations with various other concurrency models. Finally, we emulate generic BAS devices and show how our techniques perform well with various combinations of hardware properties.

[6] Article: Here.

Pioneering University of Wisconsin–Madison researchers Stacey J. Lee, a scholar of the education of immigrant communities, and Miron Livny, a leader in high-throughput computing, have been named Vilas Research Professors.

[7] Student Paul Chung wins the Goldwater Scholarship. Link: Here.

Chung is majoring in computer sciences and data science with comprehensive honors. He began his cybersecurity research while still in high school in his native South Korea, working with Professor Chang Hoon Kim at Daegu University. Chung’s family immigrated to the U.S. to provide him with more educational and research opportunities. At UW–Madison, he has undertaken research with professors Rahul Chatterjee and Kassem Fawaz at MadS&P, the computer security and privacy research group on campus, and he has interned with the university’s Office of Cybersecurity. Additionally, in summer 2022, Chung completed a research opportunity with Dr. Hanan Hibshi at the Information Networking Institute at Carnegie Mellon University. Chung is the first author on one published manuscript and the co-author on two others, and he currently has four additional manuscripts under submission. Chung plans to pursue a doctorate in computer science. He will be visiting the Max Planck Institute in Germany this summer for additional research opportunities.

Prof Ming Liu and colleagues’ ASPLOS ‘23 paper, “A Generic Service to Provide In-Network Aggregation for Key-Value Streams”, was selected as a Distinguished Paper. Great job! [1]

Prof Kirthi Kandasamy and colleagues had a paper conditionally accepted into OSDI ‘23, entitled “Cilantro: A Framework for Performance-Aware Resource Allocation for General Objectives via Online Feedback”. Great work! [2]

Two graduate students in our department won NSF graduate fellowships: Hailey Johnson (advised by Prof Bilge Mutlu) and Ivan Hu (advised by Prof Dieter van Melkebeek). Congratulations to all of you! [3]

Prof Bilge Mutlu and colleagues had two further papers accepted into the ACM Interaction Design and Children (IDC) Conference, entitled “My Unconditional Homework Buddy:” Designing Augmented Homework Experiences for Children with a Social Learning Companion Robot” and “Family Theories in Child-Robot Interactions: Understanding Families as a Whole for Child-Robot Interaction Design”. Well done! [4]

Notes:

[1] See https://asplos-conference.org for details.

Paper title: A Generic Service to Provide In-Network Aggregation for Key-Value Streams

Authors: Yongchao He, Wenfei Wu, Yanfang Le, Ming Liu, ChonLam Lao

Abstract: Key-value stream aggregation is a common operation in distributed systems, which requires intensive computation and network resources. We propose a generic in-network aggregation service for key-value streams, ASK, to accelerate the aggregation operations in diverse distributed applications. ASK is a switch-host co-designed system, where the programmable switch provides a best-effort aggregation service, and the host runs a daemon to interact with applications. ASK makes in-depth optimization tailored to traffic characteristics, hardware restrictions, and network unreliable natures: it vectorizes multiple key-value tuples’ aggregation of one packet in one switch pipeline pass, which improves the per-host’s goodput; it develops a lightweight reliability mechanism for key-value stream’s asynchronous aggregation, which guarantees computation correctness; it designs a hot-key agnostic prioritization for key-skewed workloads, which improves the switch memory utilization. We prototype ASK and use it to support Spark and BytePS. The evaluation shows that ASK could accelerate pure key-value aggregation tasks by up to 155 times and big data jobs by 3-5 times, and be backward compatible with existing INA-empowered distributed training solutions with the same speedup.

[2] Cilantro: A Framework for Performance-Aware Resource Allocation for General Objectives via Online Feedback

Authors: R. Bhardwaj*, K. Kandasamy*, A. Biswal, W. Guo, B. Hindman, J. Gonzalez, M. Jordan, I. Stoica

Abstract: Traditional systems for allocating finite cluster resources among competing jobs have either aimed at providing fairness, relied on users to specify their resource requirements, or have estimated these requirements via surrogate metrics (e.g. CPU utilization). These approaches do not account for a job’s real world performance (e.g. P95 latency). Existing performance-aware systems use offline profiled data and/or are designed for specific allocation objectives. In this work, we argue that resource allocation systems should directly account for real-world performance and the varied allocation objectives of users. In this pursuit, we build Cilantro.

At the core of Cilantro is an online learning mechanism which forms feedback loops with the jobs to estimate the resource to performance mappings and load shifts. This relieves users from the onerous task of job profiling and collects reliable real-time feedback. This is then used to achieve a variety of user-specified scheduling objectives. Cilantro handles the uncertainty in the learned models by adapting the underlying policy to work with confidence bounds. We demonstrate this in two settings. First, in a multi-tenant 1000-CPU cluster with 20 independent jobs, three of Cilantro’s policies outperform 9 other baselines on three different performance-aware scheduling objectives, improving user utilities by up to 1.2 − 3.7x. Second, in a microservices setting, where 160 CPUs must be distributed between 19 inter-dependent microservices, Cilantro outperforms 3 other baselines, reducing the end-to-end P99 latency to x0.57 the next best baseline.

[3] https://www.nsfgrfp.org/

The NSF Graduate Research Fellowship Program (GRFP) helps ensure the vitality of the human resource base of science and engineering in the United States and reinforces its diversity. The program recognizes and supports outstanding graduate students in NSF-supported science, technology, engineering, and mathematics disciplines who are pursuing research-based master’s and doctoral degrees at accredited United States institutions.

As the oldest graduate fellowship of its kind, the GRFP has a long history of selecting recipients who achieve high levels of success in their future academic and professional careers. The reputation of the GRFP follows recipients and often helps them become life-long leaders that contribute significantly to both scientific innovation and teaching. Past fellows include numerous Nobel Prize winners, former U.S. Secretary of Energy, Steven Chu, Google founder, Sergey Brin and Freakonomics co-author, Steven Levitt.

Fellows share in the prestige and opportunities that become available when they are selected. Fellowships provide the student with a three-year annual stipend of $37,000 along with a $12,000 cost of education allowance for tuition and fees (paid to the institution), as well as access to opportunities for professional development available to NSF-supported graduate students. Fellowships may only be used for an eligible graduate degree program at an academic institution accredited in, and having a campus located in, the US, its territories, possessions, or the Commonwealth of Puerto Rico.

NSF Fellows are anticipated to become knowledge experts who can contribute significantly to research, teaching, and innovations in science and engineering. These individuals are crucial to maintaining and advancing the nation’s technological infrastructure and national security as well as contributing to the economic well-being of society at large.

So that the nation can build fully upon the strength and creativity of a diverse society, the Foundation welcomes applications from all qualified individuals. Women, under-represented minorities and people with disabilities are encouraged to apply.

The fellowship is competitive, and those planning to apply should devote a sincere effort to their application. See the Applicants section for more information.

[4] Bengisu Cagiltay, Bilge Mutlu, Joseph Michaelis, “My Unconditional Homework Buddy: Designing Augmented Homework Experiences for Children with a Social Learning Companion Robot”

We aim to design robotic educational support systems that can promote socially and intellectually meaningful learning experiences for students while they complete school work outside of class. To pursue this goal, we conducted participatory design studies with 10 children (aged 10–12) to explore their design needs for robot-assisted homework. We investigated children’s current ways of doing homework, the type of support they receive while doing homework, and co-designed the speech and expressiveness of a homework companion robot. Children and parents attending our design sessions explained that an emotionally expressive social robot as a homework aid can support students’ motivation and engagement, as well as their affective state. Children primarily perceived the robot as a dedicated assistant at home, capable of forming meaningful friendships, or a shared classroom learning resource. We present key design recommendations for augmenting students’ homework experiences with a learning companion robot to support their educational experiences.

Bengisu Cagiltay, Bilge Mutlu, Margaret Kerr, “Family Theories in Child-Robot Interactions: Understanding Families as a Whole for Child-Robot Interaction Design”

In this work we discuss a theoretically motivated family-centered design approach for child-robot interactions, adapted by Family Systems Theory (FST) and Family Ecological Model (FEM). Long-term engagement and acceptance of robots in the home is influenced by factors that surround the child and family, such as child-sibling-parent relationships, family routines, rituals, and values. A family-centered approach to interaction design is essential when developing in-home technology for children, especially for social agents like robots that can form relationships and connections with them. We review related literature in family theories and connect it with child-robot interaction and child-computer interaction research. We present two case studies that exemplify how family theories, FST and FEM, can inform how robots might be integrated into homes when applied to research in child-robot and family-robot interaction design. Finally, we pose five overarching recommendations for a family centered design approach in child-robot interactions.

Prof Ming Liu and collaborators had their paper “ZNS: An Elastic Zoned Namespace for Commodity ZNS SSDs” accepted into OSDI ‘23. Awesome! [1]

Prof Bilge Mutlu and collaborators had the paper “Designing Parent-child-robot Interactions to Facilitate In-Home Parental Math Talk with Young Children” accepted into IDC ‘23. Well done! [2]

Prof Mohit Gupta and collaborators had the paper “Seeing Photons in Color” accepted into SIGGRAPH ‘23. (link to video) Great work! [3]

Prof Paris Koutris and collaborators had the paper “Space-Time Tradeoffs for Conjunctive Queries with Access Patterns” accepted into PODS ‘23. Fantastic! [4]

Prof Matt Sinclair was selected as an ARLIS faculty mentor for this summer. Cool! [5]

Prof Jerry Zhu captured a lovely picture of the Aurora Borealis display last week. We include it here because of how cool it was.

Notes:

[1] ZNS: An Elastic Zoned Namespace for Commodity ZNS SSDs

Authors: Jaehong Min, Chenxingyu Zhao, Ming Liu, Arvind Krishnamurthy

Emerging Zoned Namespace (ZNS) SSDs, providing the coarse-grained zone abstraction, hold the potential to significantly boost the cost-efficiency of future storage infrastructure and mitigate performance unpredictability. However, existing ZNS SSDs have a static zoned interface, making them in-adaptable to workload runtime behavior, unscalable to underlying hardware capabilities, and interfering with co-located zones. Applications either under-provision the zone resources yielding unsatisfied throughput, create over-provisioned zones that squander the cost, or experience unexpected I/O latencies.

We propose eZNS, an elastic zoned namespace interface that exposes an identical zone with predictable characteristics. eZNS comprises two major components: a zone arbiter that manages zone allocation and active resources on the control- plane, a hierarchical I/O scheduler with read congestion control and write admission control on the data-plane. Together, eZNS enables the transparent use of a ZNS SSD and closes the gap between application requirements and zone interface properties. Our evaluations over RocksDB demonstrate that eZNS outperforms a static zoned interface by 84.5% and 52.1% in throughput and tail latency, respectively, at most.

[2] Hui-Ro Hi, Nathan White, Edward Hubbard, Bilge Mutlu, “Designing Parent-child-robot Interactions to Facilitate In-Home Parental Math Talk with Young Children”

 ACM Interaction Design and Children (IDC) Conference

Parent-child interaction is critical for child development, yet parents may need guidance in some aspects of their engagement with their children. Current research on educational math robots focuses on child-robot interactions but falls short of including the parents and integrating the critical role they play in children’s learning. We explore how educational robots can be designed to facilitate parent-child conversations, focusing on math talk, a predictor of later math ability in children. We prototyped capabilities for a social robot to support math talk via reading and play activities and conducted an exploratory Wizard-of-Oz in-home study for parent-child interactions facilitated by a robot. Our findings yield insights into how parents were inspired by the robot’s prompts, their desired interaction styles and methods for the robot, and how they wanted to include the robot in the activities, leading to guidelines for the design of parent-child-robot interaction in educational contexts.

[3] Seeing Photons in Color

Sizhuo Ma, Varun Sundar, Paul Mos, Claudio Bruschini, Edoardo Charbon, and Mohit Gupta

SIGGRAPH ‘23

Abstract: Megapixel single-photon avalanche diode (SPAD) arrays have been developed recently, opening up the possibility of deploying SPADs as passive, general-purpose cameras for computer vision and photography. However, most previous works on SPADs have focused on monochrome imaging. We propose a computational photography approach that reconstructs high-quality color images from mosaicked binary image sequences captured by a SPAD array, even for high-dynamic-range scenes with complex and rapid motion. Inspired by conventional burst photography techniques, we design algorithms that jointly denoise and demosaick quanta image sequences. Based on the observation that motion effectively increases the color sample rate, we design a blue-noise pseudorandom RGBW color filter array for SPADs, which is tailored for imaging dark, dynamic scenes. Results on simulated data, as well as real data captured with a fabricated color SPAD hardware prototype shows that the proposed method can reconstruct high-quality images with minimal color artifacts even for challenging low-light, high-dynamic-range and fast-moving scenes. We hope this paper, by adding color to computational single-photon imaging, spurs rapid adoption of SPADs for real-world passive imaging applications.

[4] “Space-Time Tradeoffs for Conjunctive Queries with Access Patterns”

Hangdong Zhao, Shaleen Deep, Paris Koutris
PODS ‘23

Abstract: In this paper, we investigate space-time tradeoffs for answering conjunctive queries with access patterns (CQAPs). The goal is to create a space-efficient data structure in an initial preprocessing phase and use it for answering (multiple) queries in an online phase. Previous work has developed data structures that trade-off space usage for answering time

for queries of practical interest, such as the path and triangle query. However, most of these results cater to only those queries, lack a comprehensive framework, and are not generalizable.

Our main contribution is a general algorithmic framework for obtaining space-time tradeoffs for any CQAP. Our framework builds upon the PANDA algorithm and tree decomposition techniques. We demonstrate that our framework captures all state-of-the-art tradeoffs that were independently produced for various queries. Further, we falsify two conjectures proposed in the existing literature that relates to the space-time lower bound for path queries and triangle detection by proposing improved (and surprising) tradeoffs.

[5] See https://www.arlis.umd.edu/risc_faculty_mentors

The Applied Research Laboratory for Intelligence and Security (ARLIS) at the University of Maryland, College Park, is seeking faculty mentors to provide technical support for its summer internship program, Research for Intelligence & Security Challenges (RISC). This exciting 10-week paid program will pair students with mentors from UMD, INSURE consortium members, and other top universities. Those teams work in collaboration with sponsors from the Department of Defense (DOD) and Intelligence Community (IC) communities. Participating students are considered for security clearance sponsorship and then have the potential opportunity to be considered for continued work through the academic year or future employment with ARLIS or the US government.

Prof Miron Livny, as you have heard, was selected as a Vilas Research Professor, one of campus’s highest honors.  [1]

Prof Swamit Tannu and collaborators have two papers accepted for appearance at ISCA ‘23 (the 50th ISCA!). Titles: “Enabling High-Performance Debugging for Variational Quantum Algorithms using Compressed Sensing” and “ Scaling Qubit Readout with Hardware-Efficient Machine Learning Architectures”. [2]

Prof Bilge Mutlu and students won the “Best Systems Paper Award” at HRI ‘23 for their work on “Lively: Enabling Multimodal, Lifelike, and Extensible Real-time Robot Motion”.  [3]

Prof Yong Jae Lee received a Sony Focused Research Award for the proposal “Controllable High-Quality Image Generation using Diffusion Models”.  [4]

Prof Suman Banerjee and Prof Mohit Gupta had their paper “When Two Cameras Are a Crowd: Understanding and Handling Interference Across Multiple Active Cameras” accepted into Communications of the ACM as a review article.  [5]

Notes

[1] Per Amos: The Vilas Research Professorship (VRP) is the most prestigious endowed chair on our Campus.  There are 20 VRP chairs allotted to Campus by the Vilas board of trustees. Traditionally, the holders of the distinction have it for life (i.e., until retirement). So, a Campus-wide competition for a new VRP happens if and when one of the current holders retires. A necessary condition for becoming a VRP holder is to be one of the best known UW faculty internationally, and to be one of the most impactful UW faculty. In the last 35 years,  members of our department won a VRP exactly twice (Sohi, now Livny).

https://rsp.wisc.edu/Vilas/index.cfm

[2] “Enabling High-Performance Debugging for Variational Quantum Algorithms using Compressed Sensing”

Authors: Tianyi Hao, Kun Liu, Swamit Tannu

Abstract: Variational quantum algorithms (VQAs) have the potential to solve practical problems using contemporary Noisy Intermediate Scale Quantum (NISQ) computers in the near term. VQAs find near-optimal solutions in the presence of qubit errors by classically optimizing a loss function computed by parameterized quantum circuits. However, developing and testing VQAs is challenging due to the limited availability of quantum hardware, their high error rates, and the significant overhead of classical simulations. Furthermore, VQA researchers must pick the right initialization for circuit parameters, utilize suitable classical optimizer configurations, and deploy appropriate error mitigation methods. Unfortunately, these tasks are done in an ad-hoc manner today, as there are no software tools to configure and tune the VQA hyperparameters.

In this paper, we present OSCAR (cOmpressed Sensing based Cost lAndscape Reconstruction) to help VQA researchers configure: 1) correct initialization, 2) noise mitigation techniques, and 3) classical optimizers to maximize the quality of the solution on NISQ hardware. OSCAR enables efficient debugging and performance tuning by providing users with the loss function landscape without running thousands of quantum circuits as required by the grid search. Using the compressed sensing technique, we can accurately reconstruct the complete cost function landscape with a 20X to 100X speedup. Furthermore, OSCAR can compute an optimizer function query in an instant by interpolating a computed landscape, thus enabling the trial run of a VQA configuration with considerably reduced overhead.

“Scaling Qubit Readout with Hardware-Efficient Machine Learning Architectures”

Authors: Satvik Maurya, Chaithanya Naik, William Oliver, Benjamin Lienhard, Swamit Tannu

Abstract: Reading a qubit is a fundamental operation in quantum computing. It translates quantum information into classical information enabling subsequent classification to assign the qubit to the `0′ or `1′ state.

Unfortunately, qubit readout is one of the most error-prone and slowest operations on a superconducting quantum processor. On state-of-the-art superconducting quantum processors, readout errors can range from 1-10\%. These errors occur for various reasons — crosstalk, spontaneous state transitions, and excitation caused by the readout pulse. The error-prone nature of readout has resulted in significant research to design better discriminators to achieve higher qubit-readout accuracies. The readout accuracy impacts the benchmark fidelity for Noisy Intermediate Scale Quantum (NISQ) applications or the logical error rate in error-correcting codes such as the surface code.

Prior works have used machine-learning-assisted single-shot qubit-state classification, where a deep neural network was used for more robust discrimination by compensating for crosstalk errors. However, the neural network size can limit the scalability of systems, especially if fast hardware discrimination is required. This state-of-the-art baseline design cannot be implemented on off-the-shelf FPGAs or Cryogenic ASICs used for the control and readout of superconducting qubits in most systems, which increases the overall readout latency since discrimination has to be performed in software. In this work, we propose HERQULES, a scalable approach to improving qubit-state inference using matched filters in conjunction with a significantly smaller and scalable neural network for qubit-state discrimination. We achieve substantially higher readout accuracies (42\% relative improvement) than the baseline with a scalable design that can be readily implemented on off-the-shelf FPGAs. We also show that HERQULES is more versatile and can support shorter readout durations than the baseline design without additional training overheads.

[3]  “Lively: Enabling Multimodal, Lifelike, and Extensible Real-time Robot Motion”

Andrew Schoen, Dakota Sullivan, Ze Dong Zhang, Daniel Rakita, Bilge Mutlu

ACM/IEEE International Conference on Human-Robot Interaction (HRI 2023)

Robots designed to interact with people in collaborative or social scenarios must move in ways that are consistent with the robot’s task and communication goals. However, combining these goals in a naïve manner can result in mutually exclusive solutions, or infeasible or problematic states and actions. In this paper, we present Lively, a framework which supports configurable, real-time, task-based and communicative or socially-expressive motion for collaborative and social robotics across multiple levels of programmatic accessibility. Lively supports a wide range of control methods (ie, position, orientation, and joint-space goals), and balances them with complex procedural behaviors for natural, lifelike motion that are effective in collaborative and social contexts. We discuss the design of three levels of programmatic accessibility of Lively, including a graphical user interface for visual design called LivelyStudio, the core library Lively for full access to its capabilities for developers, and an extensible architecture for greater customizability and capability.

Photo of the lead authors, CS grad students Andy Schoen and Dakota Sullivan, who just presented the paper in Stockholm:

[4] “Controllable High-Quality Image Generation using Diffusion Models”

Yong Jae Lee

Sony Focused Research Award

https://www.sony.com/en/SonyInfo/research-award-program/#FocusedResearchAward

Abstract: This project proposes novel diffusion-based image generation algorithms for controllable visual content creation. While text-to-image diffusion models have shown astounding performance in the past couple of years, existing models lack precise control over the generated content. In this project, we will equip the models with the ability to control the location, size, and category of the generated objects in complex scenes. We will achieve this by conditioning the diffusion model on an input scene layout that provides the bounding box and category information of each object instance in the desired generated image. The proposed algorithm could be useful for content creators who want to generate realistic images by providing both a text prompt describing the scene as well as the objects’ localization information.

[5]  “When Two Cameras Are a Crowd: Understanding and Handling Interference Across Multiple Active Cameras”

Jongho Lee, Mohit Gupta, Bhuvana Krishnaswamy, Suman Banerjee

Project webpage: https://wisionlab.com/project/stochastictdma/

Abstract: Vision and robotics systems enabled by cameras which recover 3D scene geometry are revolutionizing several aspects of our lives via technologies such as autonomous transportation, robotic surgery, and `hands-free’ user interfaces. Modern 3D cameras are active devices, where a programmable light source emits coded illumination. The emitted light gets reflected from the scene, and is received by a sensor to infer the 3D structure of the surroundings. In a multi-camera environment, such active 3D cameras may receive light from the sources of other cameras, resulting in large depth errors. This problem is becoming increasingly important due to the emergence of low-cost and compact active 3D cameras, which are becoming ubiquitous across a wide range of applications, from consumer devices to vehicular vision systems. We observe that the multi-camera interference (MCI) problem shares several similarities and dissimilarities with the common interference problems in the RF domain. Based on this observation, we describe new and emerging challenges when multiple active 3D cameras operate in the same spatio-temporal region. We also outline some solution approaches and more importantly, highlight the next steps ahead.

Prof Bart Miller and assorted folks – including stellar work from Gigi Mitchell – ran another successful Job Fair over at Union South on Feb 20th. Over 400 students, over 20 companies. Well done! [1]

Prof Shivaram Venkataraman’s student Jason Mahoney was selected as an Apple AI/ML Scholar. Awesome! [2]

Prof Patrick McDaniel and students had their paper, “Understanding the Ethical Frameworks of Internet Measurement Studies”, win a best paper award at the EthiCS workshop at NDSS ‘23. Great job! [3]

Prof Jin-Yi Cai and students had the paper “A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory” accepted into Computational Complexity. Wonderful news! [4]

Notes:

[1]  On February 20th, we held the spring CDIS Job Fair in Union South. Over 400 UW students from across CDIS attended the fair, meeting with more than 20 companies. In addition, students were invited to attend from smaller colleges in our region, including Beloit College, Edgewood College, UW Whitewater, and Carthage College. Varsity Hall was busy from the 10am opening until the 5pm closing. Usually, the spring job fair is much smaller, but there seemed to be increased interest this year. Congrats to Gigi, who does such an amazing job organizing the event.

[2] https://machinelearning.apple.com/updates/apple-scholars-aiml-2023

Apple is proud to announce the 2023 recipients of the Apple Scholars in AI/ML PhD fellowship.

We are committed to supporting the academic research community by amplifying emerging leaders in their field and their cutting-edge machine learning research.

The Apple Scholars in AI/ML PhD fellowship recognizes the contributions of researchers in computer science and engineering at the graduate and postgraduate level. Each Scholar receives funding as they pursue their PhD, internship opportunities, and mentorship with an Apple researcher in their field. Apple Scholars in AI/ML are selected based on their innovative research, record as thought leaders and collaborators, and commitment to advancing their respective fields.

[3] Eric Pauley and Patrick McDaniel, “Understanding the Ethical Frameworks of Internet Measurement Studies”, The 2nd International Workshop on Ethics in Computer Security (EthiCS 2023) hosted at NDSS, February, 2023. San Diego, CA.

https://www.ndss-symposium.org/wp-content/uploads/2023/02/ethics2023-239547-paper.pdf

Workshop: https://ethics-workshop.github.io/2023/

Abstract: Measurement of network data received from or transmitted over the public Internet has yielded a myriad of insights towards improving the security and privacy of deployed services. Yet, the collection and analysis of this data necessarily involves the processing of data that could impact human subjects, and anonymization often destroys the very phenomena under study. As a result, Internet measurement faces the unique challenge of studying data from human subjects who could not conceivably consent to its collection, and yet the measurement community has tacitly concluded that such measurement is beneficial and even necessary for its positive impacts. We are thus at an impasse: academics and practitioners routinely collect and analyze sensitive user data, and yet there exists no cohesive set of ethical norms for the community that justifies these studies. In this work, we examine the ethical considerations of Internet traffic measurement and analysis, analyzing the ethical considerations and remediations in prior works and general trends in the community. We further analyze ethical expectations in calls-for-papers, finding a general lack of cohesion across venues. Through our analysis and recommendations, we hope to inform future studies and venue expectations towards maintaining positive impact while respecting and protecting end users.

[4] “A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory” by Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair, Michael Kowalczyk. Accepted into Computational Complexity.

Suppose φ and ψ are two angles satisfying tan(φ)=2 tan(ψ)>0. We prove that under this condition φ and ψ cannot be both rational multiples of π. We use this number theoretic result to prove a classification of the computational complexity of spin systems on k-regular graphs with general (not necessarily symmetric) real valued edge weights. We establish explicit criteria, according to which the partition functions of all such systems are classified into three classes: (1) Polynomial time computable, (2) #P-hard in general but polynomial time computable on planar graphs, and (3) #P-hard on planar graphs. In particular, problems in (2) are precisely those that can be transformed by a holo-graphic reduction to a form solvable by the Fisher-Kasteleyn-Temperley algorithm for counting perfect matchings in a planar graph.

Prof Dieter van Melkebeek once again led many Wisconsin student teams to great success in this year’s International Collegiate Programming Contest (ICPC), including placing 1st, 5th, 13th, 14th, 26th, and 29th among the 116 teams present. Amazing! [1]

Prof Mohit Gupta and collaborators had the paper “CASPI: Collaborative Photon Processing for Active Single-Photon Imaging” accepted into Nature Communications. Well done! [2]

Prof Paul Barford and collaborators had the paper “PowerPing: Measuring the Impact of Power Outages on Internet Hosts in the US” accepted into the IFIP International Conference on Critical Infrastructure Protection. Great work! [3]

Prof Matt Sinclair is co-hosting/running a gem5 tutorial co-located with HPCA. Great! [4]

And last, but certainly not least, Prof Line Roald (ECE) and Prof Shivaram Venkataraman (CS) collaborated on a new, long term, joint project known as “parenthood”. It began with the introduction of Arjun Roald-Raman, born Friday afternoon on February 24th. A warm congratulations to all three of them as they embark on this new life adventure!

Notes:

[1] Yesterday was the regional round of this year’s International Collegiate Programming Contest (ICPC). UW-Madison participated with 6 full teams of 3 students each, and one 2-student team. We had a very new cohort this year – 15 of the 17 team members other than our top team were first-time participants. Our full teams placed 1st, 5th, 13th, 14th, 26th, and 29th among the 116 teams in our region. See the scoreboard for more details.

Some statistics – This is the 4th year in a row that UW-Madison places first in the regional competition, and the 14th year in the 22 years since we started participating in 2001. The top team advances to the North America Championship in May, from where about 15 North American teams advance to the world finals. UW-Madison has advanced to the world finals every year since 2001, a title no other school in North America can claim. I have good hopes that we will be able to extend that stretch by one more year!

Dieter would like to thank the people at Epic for running a regional site on their campus, and to Nitit Jongsawatsataporn and Mingrui Liu (two of our world finalists from last year) for help coaching our teams this year.

The UW-Madison teams that participated in the regional competition:

• – debug with cout (1st place): Joseph Cai, Ivan Hu, Boying Li

• NonAutomatic Automaton (5th place): Anton Cheng, Leos Nguyen, Kiet Pham

• Ain’t No Way (13th place): Pranav Pulijala, Pranav Pullabhotla, Raymond Zhao

• Spaghetti Sort (14th place): Huaiyuan Jing, Abhay Punjabi, Lucas Scharenbroch

• GEKOta (26th place): Ruixuan Tu, Jeffrey Wang, Boyuan Zou

• CrazyThursdayVme_50 (29th place): Zhilin Du, Jonathan Yang, Hongtao Zhang

• Least Contrived Implementation: Pramod Anandarao, Chen Li, (third member had to drop out two days before the contest)

[2] CASPI: Collaborative Photon Processing for Active Single-Photon Imaging

Jongho Lee, Atul Ingle, Jenu Chacko, Kevin Eliceiri, and Mohit Gupta

Abstract: Image sensors capable of capturing individual photons have made tremendous technological progress in recent years. Single-photon cameras, which once used to be a niche technology with very few pixels, have now achieved kilo-to-megapixel resolution and have found their way into commercial devices such as smartphones. However, this technology faces a major limitation—because they capture scene information at the individual photon level, the raw data is extremely sparse and noisy. Unlike conventional CMOS image sensors that have mature image processing pipelines implemented on-chip, single-photon cameras currently do not have any standard well-agreed-upon processing pipelines. Here we propose CASPI: Collaborative Photon Processing for Active Single-Photon Imaging. CASPI is a technology-agnostic, application-agnostic, training-free, and blind photon processing pipeline for emerging high-resolution single-photon cameras. CASPI exploits the abundant spatio-temporal correlations that are present in the raw photon data cubes captured by a single-photon camera. Our key observation is that if both local and non-local correlations in the cubes are collaboratively exploited, we can estimate scene properties reliably even under extreme illumination conditions. CASPI is versatile and can be integrated into a wide range of imaging applications that could benefit from the high-speed and high-resolution single-photon camera data, including fluorescence microscopy, machine vision, and long-range 3D imaging. We experimentally demonstrate LiDAR imaging over a wide range of photon flux levels, from a sub-photon regime ($<1$ average signal photon per pixel) to extremely high ambient sunlight regime ($>20,000$ lux) and live-cell autofluorescence FLIM in extremely low photon count regimes ($10$ photons per pixel) where state-of-the-art methods fail to provide reliable lifetime estimates. We envision CASPI as a basic building block of general-purpose \emph{photon processing units} (analogous to conventional image processing units) that will be implemented on-chip in future single-photon camera sensor hardware.

Project: https://wisionlab.com/project/caspi/

[3] Scott Anderson, Tucker Bell, Patrick Egan, Nathan Weinshenker, and Paul Barford, “PowerPing: Measuring the Impact of Power Outages on Internet Hosts in the US”, To appear in Proceedings of the 17th IFIP International Conference on Critical Infrastructure Protection, Washington DC, March, 2023.

Abstract:

Power outage is a well-known threat to Internet communication systems.  While service providers address this threat via power-backup systems (e.g., diesel generators and UPS) in PoPs and datacenters, office buildings or private homes may not have similar capabilities. In this paper we describe an empirical study that assesses how power outages in the US impact end-host access to the Internet.  To conduct this study we built a system named PowerPing that monitors a power outage reporting website poweroutage.us) and measures end-host responsiveness in the affected areas.  We use PowerPing to collect power outage and end-host responsiveness data over one year from June 2020 through July 2021. We find that power outages that affect more than 10% of customers in a county occur at a rate of about 50 events/day; each outage typically affects about 3k customers, and service is typically restored in just under 2 hours.  We also report on the end-host responsiveness characteristics for typical power-outage events and on several major outage events that occurred during our study.  Surprisingly, we find only a weak correlation between power-outage impact and service restoration periods vs. end-host responsiveness. Our findings suggest that improving backup power for network devices in both the home as well as at the ISP may improve end-host connectivity during typical power outages.

[4] Some details are here: https://www.gem5.org/events/hpca-2023

The gem5 Tutorial will be held in the morning session and will focus on teaching those new to gem5 how to use the latest version. It will be “crash course” in gem5 and assume no prior knowledge of using computer architecture simulators. The tutorial will focus heavily on new features in gem5, such as the gem5 standard library, so may be suitable for those who have used gem5 before but wish to refresh their skills.

Prof Mohit Gupta received a Cruise Research Award for his proposal “Analysis of Single-Photon Sensors for Long-range 3D Imaging”. Well done! [1]

Prof Jelena Diakonikolas received the Meritorious Service Award from the journal Mathematical Programming for “exceptional diligence in their service” to the journal. Wonderful job! [2]

Prof Jin-Yi Cai and student had their paper “Dichotomy Result on 3-Regular Bipartite Non-negative Functions” appear in the journal Theoretical Computer Science. Great job! [3]

Prof Andrea Arpaci-Dusseau and Prof Remzi Arpaci-Dusseau received the UC Berkeley EECS Distinguished Alumni award for “outstanding innovation in the fields of storage and operating systems and their leadership in education and outreach”. [4]

Notes:

[1] Cruise Research Award (1 year)

Title: Analysis of Single-Photon Sensors for Long-range 3D Imaging

PI: Mohit Gupta

Abstract: We propose a theoretical analysis of single-photon 3D imaging cameras to assess their suitability for use in challenging scenarios, including sensor and scene motion, strong sunlight, and non-cooperative objects such as retro-reflectors. We will develop a probabilistic image formation model for coded single-photon imaging, and a mathematical framework for exploring and analyzing the space of coding functions. Based on this framework, we will derive physical and estimation-theoretic limits of this novel sensing modality via mathematical tools such as Cramer-Rao lower bound analysis. This foundational analysis will be summarized to provide practical guidelines on when (and whether) to use single-photon sensors (SPADs) for high-resolution, long-range 3D imaging under adverse sensing conditions.

[2] https://www.springer.com/journal/10107

Mathematical Programming rests on the knowledge and fortitude of its referees who willingly volunteer their time to provide timely, judicious, and considerate reviews. The Meritorious Service Award was created to acknowledge these continued efforts. In 2022 our Editorial Board assessed the referees who have demonstrated exceptional diligence in their service to the journal. After a detailed examination of all the referee reports, you have been selected to receive the 2022 Meritorious Service Award due to your outstanding contributions.

Congratulations! Your name will be listed on the journal website along with the other winners. We will also send you an award certificate as a token of our deep gratitude for your dedicated service.

[3] Dichotomy Result on 3-Regular Bipartite Non-negative Functions

Jin-Yi Cai and student Auten Fan

Theoretical Computer Science

We prove a complexity dichotomy theorem for a class of Holant problems on 3-regular bipartite graphs. Given an arbitrary nonnegative weighted symmetric constraint function f = [x_0, x_1, x_2, x_3], we prove that the bipartite Holant problem Holant(f | (=_3)) is either computable in polynomial time or \#P-hard. The dichotomy criterion on f is explicit.

[4] Distinguished Alumni Awards winners are selected each year by the EE and CS Chairs in consultation with the EECS Faculty Awards Committee and with input from the EECS faculty. Winners receive a plaque awarded at a departmental event such as the BEARS conference or the L&S CS Commencement.

This year’s info: https://eecs.berkeley.edu/research/bears/2023/distinguished-alumni

List of previous winners: https://eecs.berkeley.edu/people/alumni/cs-distinguished-alumni

Citation: For outstanding innovation in the fields of storage and operating systems and their leadership in education and outreach.

Prof Mohit Gupta received a Sony Faculty Innovation Award entitled “Photon-Starved Scene Inference Using Single-Photon Cameras”. Great! [1]

Prof Jin-Yi Cai and students had the paper “The complexity of counting planar graph homomorphisms of domain size 3” accepted into STOC ‘23 and the paper “Bipartite 3-Regular Counting Problems with Mixed Signs” accepted into the Journal of Computer and System Sciences. Great job! [2]

Prof Matt Sinclair gave an invited talk at ORNL entitled “Characterizing and Harnessing Performance Variability in Accelerator-rich HPC Systems”. Well done! [3]

Notes:

[1] Sony Faculty Innovation Award

Title: Photon-Starved Scene Inference Using Single-Photon Cameras

PI: Mohit Gupta

Abstract: The goal of this proposal is to develop vision systems that can recover scene information under practical constraints such as limited power, latency and bandwidth. Imagine a robot exploring an underground cave, a robot arm performing inspection of dark machine parts, or a telescope imaging distant galaxies. In such extreme conditions, images captured by conventional cameras get overwhelmed by noise, causing the signal-to-noise ratio (SNR) to dip below the threshold required for downstream inference algorithms to extract meaningful scene information. To achieve these goals, we propose developing novel signal-processing, computer vision and machine learning algorithms for raw data captured by single-photon cameras. Broadly, the proposed work will consist of (a) designing algorithms for recovering low-level image features such as edges and corners directly from photon streams, (b) designing photon-processing and filtering algorithms for active single-photon imaging (e.g., to support long-range LiDAR), and (c) develop novel photon-stream representations for power- and bandwidth-efficient single-photon imaging (both passive and active scenarios).

[2] The complexity of counting planar graph homomorphisms of domain size 3

Jin-Yi Cai and Ashwin Maran

STOC 2023.

We prove a complexity dichotomy theorem for counting planar graph homomorphisms of domain size 3. Given any 3 by 3 real valued symmetric matrix H defining a graph homomorphism from all planar graphs G \mapsto Z_H(G), we completely classify the computational complexity of this problem according to  the matrix H. We show that for every H, the problem is either polynomial time computable or \#P-hard. The P-time computable cases consist of precisely those that are  P-time computable for general graphs (a complete classification is known) or computable by Valiant’s holographic algorithm via matchgates. We also prove several results about planar graph homomorphisms for general domain size q. The proof uses mainly analytic arguments.

and

Bipartite 3-Regular Counting Problems with Mixed Signs

Jin-Yi Cai and Auten Fan and Hugh Liu

Journal of Computer and System Sciences

We prove a complexity dichotomy for a class of counting problems expressible as bipartite 3-regular Holant problems. These are also counting CSP problems where every constraint has arity 3 and every variable is read-thrice. The constraint function can take both positive and negative values, allowing for cancellations.

[3] Characterizing and Harnessing Performance Variability in Accelerator-rich HPC Systems

Matt Sinclair talk at ORNL

Abstract: Scientists are increasingly exploring and utilizing the massive parallelism of general-purpose accelerators such as GPUs for scientific breakthroughs. As a result, datacenters, hyperscalers, national computing centers, and supercomputers have procured hardware to support this evolving application paradigm. These systems contain hundreds to tens of thousands of accelerators, enabling peta- and exa-scale levels of compute for scientific workloads. Recent work demonstrated that power management (PM) can impact application performance in CPU-based HPC systems, even when machines have the same architecture and SKU (stock keeping unit). This variation occurs due to manufacturing variability and the chip’s PM. However, while modern HPC systems widely employ accelerators such as GPUs, it is unclear how much this variability affects applications. In this talk, I will discuss our work on characterizing the extent of variation due to GPU PM in modern HPC and supercomputing systems across five large-scale computing centers with modern GPUs: Oak Ridge’s Summit, Sandia’s Vortex, TACC’s Frontera and Longhorn, and Livermore’s Corona. Regardless of the application, cluster, GPU vendor, and cooling method, our results show significant variation: 8% (max 22%) average performance variation even though the GPU architecture and vendor SKU are identical within each cluster, with outliers up to 1.5X slower than the median GPU. These results highlight the difficulty in efficiently using existing GPU clusters for modern HPC and scientific workloads, and the need to embrace variability in future accelerator-based systems.  In the second half of the talk, I will discuss our efforts to embrace this variability.