Quick links

CS Department Colloquium Series

Making Parallelism Pervasive with the Swarm Architecture

Date and Time
Tuesday, May 29, 2018 - 12:30pm to 1:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
Host
Margaret Martonosi

Daniel Sanchez
With Moore's Law coming to an end, architects must find ways to sustain performance growth without technology scaling. The most promising path is to build highly parallel systems that harness thousands of simple and efficient cores. But this approach will require new techniques to make massive parallelism practical, as current multicores fall short of this goal: they squander most of the parallelism available in applications and are too hard to program.

I will present Swarm, a new architecture that successfully parallelizes algorithms that are often considered sequential and is much easier to program than conventional multicores. Swarm programs consist of tiny tasks, as small as tens of instructions each. Parallelism is implicit: all tasks follow a programmer-specified total or partial order, eliminating the correctness pitfalls of explicit synchronization (e.g., deadlock, data races, etc.). To scale, Swarm executes tasks speculatively and out of order, and efficiently speculates thousands of tasks ahead of the earliest active task to uncover enough parallelism.

Swarm builds on decades of work on speculative architectures and contributes new techniques to scale to large core counts, including a new execution model, speculation-aware hardware task management, selective aborts, and scalable ordered task commits. Swarm also incorporates new techniques to exploit locality and to harness nested parallelism, making parallel algorithms easy to compose and uncovering abundant parallelism in large applications.

Swarm accelerates challenging irregular applications from a broad set of domains, including graph analytics, machine learning, simulation, and databases. At 256 cores, Swarm is 53-561x faster than a single-core system, and outperforms state-of-the-art software-only parallel algorithms by one to two orders of magnitude. Besides achieving near-linear scalability, the resulting Swarm programs are almost as simple as their sequential counterparts, as they do not use explicit synchronization.

Bio:
Daniel Sanchez is an Associate Professor of Electrical Engineering and Computer Science at MIT. His research interests include parallel computer systems, scalable and efficient memory hierarchies, architectural support for parallelization, and architectures with quality-of-service guarantees. He earned a Ph.D. in Electrical Engineering from Stanford University in 2012 and received the NSF CAREER award in 2015.

Better Understanding of Efficient Dynamic Data Structures

Date and Time
Tuesday, May 8, 2018 - 12:30pm to 1:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Ran Raz

Huacheng Yu
Data structures have applications and connections to algorithm design, database systems, streaming algorithms and other areas of computer science. Understanding what efficient data structures can do (and what they cannot do) is crucial to these applications. In this talk, I will present my work in analyzing efficient data structures and proving what they cannot accomplish. I will focus on the recent development in building new connections between dynamic data structures and communication complexity, as well as a new approach to analyzing dynamic data structures with Boolean outputs and super-logarithmic time.

Bio:
Huacheng Yu is a postdoctoral researcher in the Theory of Computing group at Harvard University. He obtained his PhD from Stanford University in 2017 under the supervision of Ryan Williams and Omer Reingold. He also holds a Bachelor's degree from Tsinghua University (2012). His primary research interests are data structure lower bounds. He also works in algorithm design and communication complexity.

Machine Learning Algorithms for Exploiting Spectral Structures of Biological Networks

Date and Time
Friday, April 27, 2018 - 12:30pm to 1:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Mona Singh

Bo Wang
Networks are ubiquitous in biology where they encode connectivity patterns at all scales of organization, from populations to a single cell.  How to extract and understand non-trivial topological features and structures inherent in the networks is critical to understanding interactions within complicated biological systems. In this talk, I will introduce recent developments of machine learning algorithms that exploit spectral structures of networks for a wide range of biological applications, ranging from single-cell analysis to function prediction on protein-protein interaction networks. Specifically, I will first present a new method named SIMLR, combining both low-rank spectral regularization and multiple- kernel learning, to construct cell networks for sparse noisy single-cell RNA-seq data. The learned cell networks will enable effective dimension reduction, clustering and visualization. Second, I will discuss a novel method, Network Enhancement (NE), that aims to de-noise complex networks such as protein-protein interaction networks without corrupting spectral structures of the networks, therefore improving function prediction accuracy. Last, I will also briefly introduce recent advances where deep convolutional neural network is applied on biological networks (e.g., drug-target network) as a first-order spectral approximation of network structures.

Bio: 
Bo Wang is a recent PhD graduate in Computer Science at Stanford University, an IEEE and CVF Fellow and an NSF Graduate Research Fellow.  His research focuses on machine learning (particularly deep learning) on many applications in computer vision (e.g., image segmentation, object detection) and computational biology (e.g., single-cell analysis, integrative cancer subtyping). Prior to Stanford, he received his master degree at University of Toronto, majoring in numerical analysis. 

Solving the DRAM Scaling Challenge

Date and Time
Tuesday, April 3, 2018 - 12:30pm to 1:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Margaret Martonosi

Samira Khan
Technology scaling of DRAM cells has enabled higher capacity memory for the last few decades. Unfortunately, DRAM cells become vulnerable to failure as they scale down to a smaller size. Enabling high-performance, energy-efficient, scalable memory systems without sacrificing the reliability is a major research challenge. My work focuses on designing a scalable memory system by rethinking the traditional assumptions in abstraction and separation of responsibilities across system layers. 

In this talk, I will discuss three fundamental ways to enable DRAM scaling. First, we can enable scaling by letting the manufacturers build smaller cells without providing any strict reliability guarantee.  I envision manufacturers shipping DRAMs without fully ensuring correct operation, and the system being responsible for detecting and mitigating DRAM failures while operating in the field. However, designing such a system is difficult due to intermittent DRAM failures. In this talk, I will discuss a system design, capable of providing reliability guarantees even in the presence of intermittent failures. Second, we can enable high-capacity memory leveraging the emerging non-volatile memory technologies that are predicted to be more scalable. I will present my vision to redefine the hardware and operating system interface to unify memory and storage system with non-volatile memory and discuss the opportunities and challenges of such a system. Third, tolerating failures in the application can improve memory scalability. The fundamental challenge of such a system is how to assure, verify, and quantify the quality of the results. I envision a system that limits the impact of memory failures such that it is possible to statically determine the worst-case results from the maximum possible error in the input. 

Bio:
Samira Khan is an Assistant Professor at the University of Virginia (UVa). Prior to joining UVa, she was a Post Doctoral Researcher at Carnegie Mellon University, funded by Intel Labs. Her research focuses on improving the performance, efficiency, and reliability of the memory system. She is the recipient of NSF CRII Award, NSF GOALI Award, and Rising Stars in EECS Award. She received her PhD from the University of Texas at San Antonio. During her graduate studies, she worked at Intel, AMD, and EPFL. 

Scaling Security Practices: Automated Approaches to Eliminate Security Vulnerabilities

Date and Time
Thursday, April 19, 2018 - 12:30pm to 1:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Arvind Narayanan

Taesoo Kim
Computer systems are highly vulnerable; attackers everyday discover new security vulnerabilities and exploit them to compromise the target systems. This talk will present our approaches to automatically prevent software vulnerabilities from exploitation. In particular, this talk will describe in detail two classes of vulnerabilities: an emerging class, called "type confusion" (or "bad casting"), that are commonly seen in modern web browsers, and a new class that we discovered, called "uninitialized padding," causing information leakage in the Linux kernel. This talk will explain what these vulnerabilities are, how attackers exploit them, why/how developers introduced them, and why it is non-trivial to avoid them in complex, real-world programs. Finally, our approaches to automatically eliminate them in practice will be demonstrated.

Bio:
Taesoo Kim is a Catherine M. and James E. Allchin Early Career Assistant Professor in the School Computer Science at the Georgia Institute of Technology (Georgia Tech). He also serves as the director of the Georgia Tech Systems Software and Security Center (GTS3). He is genuinely interested in building a system that prioritizes security principles first and foremost. Those principles include the total design of the system, analysis of its implementation, elimination of certain classes of vulnerabilities, and clear separation of its trusted components.  His thesis work, in particular, focused on detecting and recovering from attacks on computer systems, known as "undo computing." Taesoo holds a S.M. (2011) and a Ph.D. (2014) from MIT.

Learning from Language

Date and Time
Monday, April 16, 2018 - 12:30pm to 1:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Sanjeev Arora

Jacob Andreas
Natural language is built from a library of concepts and compositional operators that provide a rich source of information about how humans understand the world.  Can this information help us build better machine learning models? In this talk, we'll explore three ways of integrating compositional linguistic structure and learning: using language as a source of modular reasoning operators for question answering, as a scaffold for fast and generalizable reinforcement learning, and as a tool for understanding representations in neural networks.

Bio:
Jacob Andreas is a fifth-year PhD student at UC Berkeley working in natural language processing. He holds a B.S. from Columbia and an M.Phil. from Cambridge, where he studied as a Churchill scholar. His papers were recognized at NAACL 2016 and ICML 2017. Jacob has been an NSF graduate fellow, a Huawei--Berkeley AI fellow, and a Facebook fellow.

Closing the Loop on Secure System Design

Date and Time
Tuesday, April 10, 2018 - 12:30pm to 1:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Mike Freedman

Amit Levy
Despite decades of research building secure operating systems, many deployed systems must still choose between flexible application APIs and security. As a result, the vast majority of programmers are unable to improve these systems. This is not merely a result of poor system building. It is hard to design highly  extensible systems that are both secure and useful. Moreover, evaluating novel  designs with actual developers is critical in order to make sure system builders  can adopt research systems in practice.

Fortunately, in emerging application domains, such as the Internet of Things, there are no entrenched operating systems and application portability is less important. This makes it possible evaluate research techniques for building more secure and extensible systems with developers who are willing to adopt them.

I'll describe Tock, an operating system for microcontrollers that enables third-party developers to extend the system. Tock uses the Rust type-system to isolate kernel extensions and the hardware to isolate applications. I'll discuss  how we continuously evaluate Tock by engaging with practitioners, and how  lessons from practitioners have fed back into the system's design.

Bio:
Amit Levy is a PhD candidate in Computer Science at Stanford University.  He builds secure operating system kernels, web platforms, and network systems  that help make computers more programmable by third-party application  developers.

Mixed-Autonomy Mobility: Scalable Learning and Optimization

Date and Time
Monday, March 26, 2018 - 4:30pm to 5:30pm
Location
Bowen Hall 222
Type
CS Department Colloquium Series
Host
Szymon Rusinkiewicz (CS) & Prateek Mittal (EE)

How will self-driving cars change urban mobility? This talk describes contributions in machine learning and optimization critical for enabling mixed-autonomy mobility, the gradual and complex integration of automated vehicles into the existing transportation system. The talk first explores and quantifies the potential impact of a small fraction of automated vehicles on low-level traffic flow dynamics such as traffic congestion, using novel techniques in model-free deep reinforcement learning. Second, the talk presents generic reinforcement learning techniques for improved variance reduction, developed for large-scale control systems such as traffic networks and robotic manipulation. To anchor this work in a broader mobility planning context, the coordination of automated vehicles relies on accurate traffic flow sensing. To this end, a new convex optimization method for cellular network measurements from AT&T for all of California is introduced to address a flow estimation problem previously believed to be intractable. Finally, automated vehicles are expected to increase transportation demand through a phenomenon called induced demand. To address this, joint work with Microsoft Research is presented, which provides theoretical justification for the application of widely used clustering algorithms to ridesharing problems, designed to mitigate the strain on existing infrastructure. Together, these contributions demonstrate, through principled learning and optimization methods, that a small number of vehicles and sensors can be harnessed for significant impact on urban mobility.

Bio:
Cathy Wu is a PhD candidate in machine learning in Electrical Engineering and Computer Sciences (EECS) at UC Berkeley, the Berkeley Artificial Intelligence Research lab, Berkeley DeepDrive, California PATH, and the Berkeley RISELab. She is interested in developing principled computational tools to enable reliable and complex decision-making for critical societal infrastructure, such as transportation systems. Cathy received her Masters and Bachelors degrees in EECS from MIT.  She is the recipient of several fellowships including the NSF graduate fellowship, the Berkeley Chancellor's fellowship, the NDSEG fellowship, and the Dwight David Eisenhower graduate fellowship.  Her work was acknowledged by several awards, including the 2016 IEEE ITSC Best Paper Award and the 2017 ITS Outstanding Graduate Student Award. Her leadership, in particular as the Research Lead of the Learning Traffic Team at Berkeley, was recognized by numerous awards and invitations, such as the 2017 IEEE Leaders Summit and multiple NSF early-career investigator workshops on cyber-physical systems.  Throughout her career, Cathy has collaborated or interned broadly across fields, including civil engineering, mechanical engineering, urban planning, and public policy, and institutions, including OpenAI, Microsoft Research, the Google Self-Driving Car Team, AT&T, Facebook, and Dropbox.  As the founder and Chair of the Interdisciplinary Research Initiative within the ACM Future of Computing Academy, she is actively working to create international programs to further enable and support interdisciplinary research in computing.

Learning Interactive Agents

Date and Time
Tuesday, March 13, 2018 - 12:30pm to 1:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
Host
Barbara Engelhardt

He He
AI has made huge advancement into our daily life and increasingly we require intelligent agents that work intimately with people in a changing environment. However, current systems mostly work in a passive mode: waiting for requests from users and processing them one at a time. An interactive agent must handle real-time, sequential inputs and actively collaborate with people through communication. In this talk, I will present my recent work addressing challenges in real-time language processing and collaborative dialogue. The first part involves making predictions with incremental inputs. I will focus on the application of simultaneous machine interpretation and show how we can produce both accurate and prompt translations. Then, I will present my work on building agents that collaborate with people through goal-oriented conversation. I will conclude by discussing future directions towards adaptive, active agents.

Bio:
He He is a postdoctoral researcher at Stanford University. She earned her Ph.D. in Computer Science at the University of Maryland, College Park. She is interested in natural language processing and machine learning. Her research focuses on building intelligent agents that work in a changing environment and interact with people, with an emphasis on language-related problems. Specific applications include dependency parsing, simultaneous machine interpretation, and goal-oriented dialogue. She is the recipient of the 2016 Larry S. Davis doctoral dissertation award.

Analyzing Human Behavior to Make Computing More Useful

Date and Time
Monday, March 5, 2018 - 12:30pm to 1:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Arvind Narayanan

Brian Smith

Computing devices play a more significant role in our lives than ever before, so it is more important than ever for them to understand who we are as people on a deep level. But many of today’s user interfaces do not have such an understanding: rather, their designs are based on developers’ intuitions alone. This often leads to mismatches between how useful computing systems promise to be and how useful they are in practice.

In this talk, I will show how analyzing and even modeling human behavior can unlock insights that help resolve such mismatches, resulting in systems that are significantly more useful than what they would otherwise be. I will discuss four results that I have worked on: (1) a system for interacting with objects by looking at them, (2) a system for typing on smartphones more quickly and with much fewer errors, (3) a system that can recognize players and recommend video game levels from controller inputs alone, and (4) a system that makes it possible for people who are blind to play the same types of racing games that sighted players can play with the same speed and sense of control that sighted players have.

Bio:
Brian A. Smith is a Ph.D. candidate in Computer Science at Columbia University, where he is a member of the Computer Vision Laboratory and the Computer Graphics and User Interfaces Laboratory. His research is in human–computer interaction, accessibility, and game design, and focuses on analyzing human behavior to make computing more useful. He has been awarded the NDSEG Fellowship, an NSF IGERT data science traineeship, and Columbia Engineering’s Extraordinary Teaching Assistant Award. He received his MS and BS in Computer Science from Columbia University.

Follow us: Facebook Twitter Linkedin