Computer Sciences Weekly Good News

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.