- talks - lists.cs.princeton.edu

Naga Katta will present his Pre-FPO Thursday, March 24, 2016 at 10am in CS 402.
by Nicki Gotsis 21 Mar '16

21 Mar '16

Naga Katta will present his Pre-FPO Thursday, March 24, 2016 at 10am in CS 402. The members of his committee are as follows: Jennifer Rexford (Adviser), Mike Freedman (Reader), Dave Walker (Reader), Nick Feamster (Non-reader) and Aarti Gupta (Non-reader). Everyone is invited to attend his talk. The talk title and abstract follow below: Title: Building reliable and efficient software-defined networks Abstract: Software-defined networking (SDN) promises flexible network control by enforcing fine-grained policies in the dataplane through a centralized controller. However, despite this promise, operators accustomed to fast and fault-tolerant routing using traditional protocols find two important properties lacking in SDNs - efficiency and reliability. In particular, they face the following problems while deploying SDN - One, the control plane timescales are too slow to enforce fault-tolerant load balancing in order to efficiently use the available network capacity. Second, the commodity SDN switches have limited space to enforce fine-grained policy rules which undermines the promise of flexible control. Third, the centralized controller itself is a single point of failure which is unacceptable for operators used to running distributed fault-tolerant network protocols. My thesis aims to mitigate these problems using novel algorithms that exploit advanced data plane capabilities and enhancements to the control plane software. At the same time, we also provide simple abstractions on top of these systems so that network operators writing control programs need not worry about low-level details of how these problems are dealt with. First, I will present HULA, which gives the abstraction of one big efficient non-blocking switch. Instead of asking the control plane to choose the best path for each new flow, HULA efficiently routes traffic on least congested paths in the dataplane. HULA uses advanced hardware data plane capabilities to infer global congestion information and uses that information to do fine-grained load balancing at RTT timescales. HULA is congestion-aware, scales to large topologies and is robust to topology failures. Second, I will present CacheFlow which helps enforcing fine-grained policies by proposing the abstraction of a switch with logically infinite rule space. CacheFlow uses a combination of software and hardware data paths to bring the best of both worlds to policy enforcement. By dynamically caching a small number of heavy hitting rules in the hardware switch and the rest of the rules in the software data path, it achieves both high throughput and high rule capacity. Since cross-rule dependencies make rule caching difficult, CacheFlow uses novel algorithms to do dependency-aware, efficient and transparent rule caching. Finally, I will present Ravana which gives the abstraction of one logically centralized controller. Given this abstraction, the network operator only writes programs for one controller and the Ravana runtime takes care of replicating the control logic for fault-tolerance. Since network switches carry additional state external to the controller state, Ravana uses an enhanced version of traditional replicated state machine protocols to ensure ordered and exactly-once execution of network events. Together these systems propose a new architecture where basic routing is done efficiently at dataplane timescales, policy enforcement is done scalably with the help of software data planes and the control plane is fault-tolerant. This new architecture has the properties of fast routing and fault-tolerance of traditional networks while delivering the promise of efficient enforcement of fine-grained control policies.

1 0

Colloquium Speaker Stefanie Mueller, Monday March 28th, 12:30pm
by Mitra D. Kelly 21 Mar '16

21 Mar '16

Colloquium Speaker Stefanie Mueller, Human-Computer Interaction Lab at Hasso Plattner Institute Monday March 28th, 12:30pm Computer Science 105 Talk Title: Interacting with Personal Fabrication Machines Abstract: In anticipation of 3D printers reaching millions of users, I am investigating how to allow future users to interact with the new hardware. I present a series of interactive software+hardware systems that I created to answer this question. They are characterized by two main properties. First, they produce physical output quickly, allowing users not only to see their results, but also to touch and test their mechanical properties as users work towards a solution. Second, the systems allow users to interact directly with the workpiece, i.e., rather than using a digital 3D editor, users manipulate the workpiece located inside the 3D printer by pointing at it, causing the machine to then modify the workpiece accordingly. I put my research into perspective by drawing analogies to the evolution of interactive computing from batch processing, to turn taking, to direct manipulation. Bio: Stefanie Mueller is a PhD student working with Patrick Baudisch at the Human-Computer Interaction Lab at Hasso Plattner Institute. In her research, she develops novel hardware and software systems that advance personal fabrication technologies. Stefanie has published 10 papers at the most selective HCI venues CHI and UIST, for which she received a best paper award and two best paper nominees. She is also serving on the CHI and UIST program committees as an associate chair. In addition, Stefanie has been an invited speaker at universities and research labs, such as MIT, Stanford, UC Berkeley, Microsoft Research, Disney Research, and Adobe Research. Mitra Kelly Academic Secretary Princeton University Computer Science Dept 35 Olden Street Princeton NJ 08540 mkelly(a)cs.princeton.edu <mailto:mkelly@cs.princeton.edu> 609-258-4562

1 0

Jonathan Ragan-Kelley , Tuesday March 22, 12:30pm
by Mitra D. Kelly 21 Mar '16

21 Mar '16

Jonathan Ragan-Kelley, Stanford March 22, 12:30pm Computer Science 105 Title: Organizing Computation for High-Performance Visual Computing Abstract: Future visual computing applications-from photorealistic real-time rendering, to 4D light field cameras, to pervasive sensing and computer vision-demand orders of magnitude more computation than we currently have. >From data centers to mobile devices, performance and energy scaling is limited by locality (the distance over which data has to move, e.g., from nearby caches, far away main memory, or across networks) and parallelism. Because of this, I argue that we should think of the performance and efficiency of an application as determined not just by the algorithm and the hardware on which it runs, but critically also by the organization of computations and data. For algorithms with the same complexity-even the exact same set of arithmetic operations and data-executing on the same hardware, the order and granularity of execution and placement of data can easily change performance by an order of magnitude because of locality and parallelism. To extract the full potential of our machines, we must treat the organization of computation as a first class concern while working across all levels from algorithms and data structures, to compilers, to hardware. This talk will present facets of this philosophy in systems I have built for visual computing applications from image processing and vision, to 3D rendering, simulation, optimization, and 3D printing. I will show that, for data-parallel pipelines common in graphics, imaging, and other data-intensive applications, the organization of computations and data for a given algorithm is constrained by a fundamental tension between parallelism, locality, and redundant computation of shared values. I will focus particularly on the Halide language and compiler for image processing, which explicitly separates what computations define an algorithm from the choices of organization which determine parallelism, locality, memory footprint, and synchronization. I will show how this approach can enable much simpler programs to deliver performance often many times faster than the best prior hand-tuned C, assembly, and CUDA implementations, while scaling across radically different architectures, from ARM cores, to massively parallel GPUs, to FPGAs and custom ASICs. Bio: Jonathan Ragan-Kelley is a postdoc in computer science at Stanford. He works on high-efficiency visual computing, including systems, compilers, and architectures for image processing, vision, 3D rendering, 3D printing, physical simulation, and scientific computing. He earned his PhD in Computer Science at MIT in 2014, where he built the Halide language for high-performance image processing. Halide is now used throughout industry to deploy code to hundreds of millions of smartphones and process tens of billions of images per day. Jonathan previously built the Lightspeed preview system, which was used on over a dozen films at Industrial Light & Magic and was a finalist for an Academy Technical Achievement Award. He has worked in GPU architecture, compilers, and research at NVIDIA, Intel, and ATI. Mitra Kelly Academic Secretary Princeton University Computer Science Dept 35 Olden Street Princeton NJ 08540 mkelly(a)cs.princeton.edu <mailto:mkelly@cs.princeton.edu> 609-258-4562

1 0

Guangda Hu will present his Pre FPO on Friday, March 25, 2016 at 10:30am in CS 301.
by Nicki Gotsis 21 Mar '16

21 Mar '16

Guangda Hu will present his Pre FPO on Friday, March 25, 2016 at 10:30am in CS 301. The members of his committee are: Zeev Dvir (adviser), Readers: Shubhangi Saraf (Rutgers), Sanjeev Arora; Non-readers: Mark Braverman, Elad Hazan. Everyone is invited to attend his talk. The talk title and abstract follow below: Title: Results on the complexity of codes with nice recovering capabilities Abstract: In both practice and theory, much research has been done on error correcting codes with nice recovering capabilities. In this thesis, we will discuss two types of such codes, namely Locally Decodable/Correctable Codes (LDCs/LCCs) and Maximally Recoverable (MR) Codes. LDCs are error correcting codes that each symbol of the original message can be recovered by making a small number of queries even if a constant fraction of the codeword is corrupted. LCCs are similar to LDCs except that we can correct every symbol in the codeword and not just the original message. LDCs/LCCs play an important role in theoretical computer science but are still not well understood. For the case that the query number is very small (constant greater than 2 for example), the best known constructions are the Matching-Vector codes [DGY11] which have subexponential (but superpolynomial) code lengths, and the best lower bound is super quadratic for 3-LCC over reals [DSW14]. It is a great challenge to make this huge gap smaller. We will discuss two results towards better understandings about the lower bounds of constant query LDCs/LCCs. First, we consider codes over real numbers and discuss an approximate version of LDCs. The problem of approximate codes itself is interesting and it is also related to notion of [DSW14] which gives the first super quadratic lower bound for 3-LCCs. We obtain bounds for approximate codes that are similar to the best known ones for exact codes. Second, we consider a generalization of the Sylvester-Gallai theorem in geometry. Basically LCCs and the Sylvecter-Gallai theorem are both questions about configurations of points with many local dependencies, and the connection between them has been studied in several previous works. We give a subspace version of Sylvester-Gallai and generalize an important tool used in [DSW14]. In distributed data storage systems, one common practice is to partition data into local groups and there are both local checksums for each local group and global checksums that depend on all data. MR codes are systematic codes that have the information theoretically optimal erasure recovering capability. It is known that there are explicit constructions for MR codes in any common reasonable topology of group partitioning [GHJY14]. However, the problem is that all known constructions require the alphabet to be very large and this is inefficient for both storing and recovering. In practice, it is actually observed that there is a tradeoff between "efficiency" and "reliability", though there was no theoretical proof. We give the first lower bound for the alphabet size of MR codes of a common topology. This shows that a storage system that is maximally recoverable cannot be efficient and is the first proof of the tradeoff. We also give new constructions with new techniques of MR codes that improves the previous results for various parameters. Based on joint works with Jop Briet, Zeev Dvir, Parikshit Gopalan, Swastik Kopparty, Shubhangi Saraf, Carol Wang, Sergey Yekhanin.

1 0

Colloquium Speaker: Igor Mordatch, Wednesday, March 23, 4:30pm- reminder
by Nicole E. Wagenblast 18 Mar '16

18 Mar '16

Colloquium Speaker Igor Mordatch, University of California, Berkeley Wednesday, March 23, 4:30pm Computer Science 105 Automated Discovery and Learning of Complex Movement Behaviours In order to create truly autonomous physical robots, understand the underlying principles behind human movement, or tell narratives in animated films and interactive games, it is necessary to synthesize movement behaviours with the same wide variety, richness and complexity observed in humans and other animals. Moreover, these behaviours should be discovered automatically from only a few core principles, and not be a result of extensive manual engineering or a mimicking of demonstrations. In this talk at the intersection of robotics, computer graphics and biomechanics, I will show work on novel trajectory and policy optimization methods that give rise to a range of behaviours such getting up, climbing, moving objects, hand manipulation, acrobatics, and various cooperative actions involving multiple characters all in a single system. The resulting movements can be used to successfully control a physical bipedal robot and coupled with detailed models of human physiology, motions that match real human motion can be produced de novo, giving the predictive power to conduct virtual biomechanics experiments. The approach is fully automatic, based on general neural network policy representations and does not require domain knowledge specific to each behaviour, pre-existing examples or motion capture data. Although discovery and learning are computationally-expensive and rely on cloud and GPU computing, the interactive animation can run in real-time on any hardware once the controllers are learned. Igor Mordatch is a post-doctoral fellow working with professor Pieter Abbeel at University of California, Berkeley. He received his PhD at University of Washington under supervision of Emanuel Todorov and Zoran Popovic and undergraduate degree in Computer Science and Mathematics at University of Toronto. He worked as a visiting researcher at Stanford University and Pixar Research. His research interests lie in the development and use of optimal control and machine learning techniques for robotics, computer graphics, and biomechanics.

1 0

Colloquium Speaker: Mayank Goel Friday, March 25- 12:30pm
by Nicole E. Wagenblast 17 Mar '16

17 Mar '16

Colloquium Speaker Mayank Goel , University of Washington Friday, March 25, 2016 - 12:30pm Computer Science 105 Teaching Old Sensors New Tricks A fundamental issue with any new sensing technology is the deployment burden. The new technology often comes with a rigid and perhaps expensive list of pre-requisites; and it affects the overall cost-effectiveness, deployability, and accessibility of the solution. For example, a user might find it hard to buy and carry a medical device with them everyday. The primary theme of my Ph.D. research has been to reduce the adoption and deployment barriers of new sensing technologies by using the sensors that are already around us. In this talk, I will present my research on extending the capabilities of the on-board sensors on consumer devices for various applications. First, I will discuss how we can leverage the on-device sensors to enable novel human-computer interactions and make the mobile devices more usable. Next, I will discuss my work on using the on-device sensors for building health technologies that work as well as their clinically-approved counterparts and they continue to evolve through deployments in various parts of the world. Finally, I will discuss how my recent work in extending the on-device sensors is shaping my future interests and how I plan to continue to lower the adoption barriers for new sensing technologies. Mayank Goel is a Ph.D. candidate in Computer Science and Engineering in the Ubiquitous Computing (UbiComp) Lab at the University of Washington, advised by Shwetak Patel and Gaetano Borriello. His research focuses on building sensing systems to solve hard problems in diverse application areas, ranging from health sensing, technologies for the developing world to novel user interaction; with an eye toward reducing deployment barriers. His research in the area of health technologies is currently used by hundreds of patients every week, around the world. He was awarded the Microsoft Research Ph.D. Fellowship in 2014, a University of Washington CSE Fellowship, and 7 Best Paper Nominations. He received an M.S. in Computer Science from Georgia Institute of Technology in 2009, where he was advised by Gregory Abowd and specialized in mobile and ubiquitous computing.

1 0

Colloquium Speaker, Jonathan Ragan-Kelley, March 22, 12:30pm
by Mitra D. Kelly 16 Mar '16

16 Mar '16

Colloquium Speaker Jonathan Ragan-Kelley, Stanford March 22, 12:30pm Computer Science 105 Organizing Computation for High-Performance Visual Computing Future visual computing applications-from photorealistic real-time rendering, to 4D light field cameras, to pervasive sensing and computer vision-demand orders of magnitude more computation than we currently have. >From data centers to mobile devices, performance and energy scaling is limited by locality (the distance over which data has to move, e.g., from nearby caches, far away main memory, or across networks) and parallelism. Because of this, I argue that we should think of the performance and efficiency of an application as determined not just by the algorithm and the hardware on which it runs, but critically also by the organization of computations and data. For algorithms with the same complexity-even the exact same set of arithmetic operations and data-executing on the same hardware, the order and granularity of execution and placement of data can easily change performance by an order of magnitude because of locality and parallelism. To extract the full potential of our machines, we must treat the organization of computation as a first class concern while working across all levels from algorithms and data structures, to compilers, to hardware. This talk will present facets of this philosophy in systems I have built for visual computing applications from image processing and vision, to 3D rendering, simulation, optimization, and 3D printing. I will show that, for data-parallel pipelines common in graphics, imaging, and other data-intensive applications, the organization of computations and data for a given algorithm is constrained by a fundamental tension between parallelism, locality, and redundant computation of shared values. I will focus particularly on the Halide language and compiler for image processing, which explicitly separates what computations define an algorithm from the choices of organization which determine parallelism, locality, memory footprint, and synchronization. I will show how this approach can enable much simpler programs to deliver performance often many times faster than the best prior hand-tuned C, assembly, and CUDA implementations, while scaling across radically different architectures, from ARM cores, to massively parallel GPUs, to FPGAs and custom ASICs. Jonathan Ragan-Kelley is a postdoc in computer science at Stanford. He works on high-efficiency visual computing, including systems, compilers, and architectures for image processing, vision, 3D rendering, 3D printing, physical simulation, and scientific computing. He earned his PhD in Computer Science at MIT in 2014, where he built the Halide language for high-performance image processing. Halide is now used throughout industry to deploy code to hundreds of millions of smartphones and process tens of billions of images per day. Jonathan previously built the Lightspeed preview system, which was used on over a dozen films at Industrial Light & Magic and was a finalist for an Academy Technical Achievement Award. He has worked in GPU architecture, compilers, and research at NVIDIA, Intel, and ATI. Mitra Kelly Academic Secretary Princeton University Computer Science Dept 35 Olden Street Princeton NJ 08540 mkelly(a)cs.princeton.edu <mailto:mkelly@cs.princeton.edu> 609-258-4562

1 0

Colloquium Speaker: Adam Belay, Thursday, March 24- 12:30pm
by Nicole E. Wagenblast 16 Mar '16

16 Mar '16

Colloquium Speaker Adam Belay, Stanford University Thursday, March 24, 12:30pm Computer Science 105 Unleashing Hardware Potential through Better OS Abstractions Datacenter workloads have demanding performance requirements, including the simultaneous need for high throughput, low tail latency, and high server utilization. While modern hardware is compatible with these goals, modern operating systems remain a bottleneck. Better OS abstractions could significantly improve performance, yet deploying these abstractions has become intractable given the size and complexity of today's systems. I will first discuss Dune, a kernel extension that allows OS developers to sidestep software and hardware complexity by running an OS within an ordinary Linux process. With Dune, developers can both access the capabilities of raw hardware and fall back on the functionality of a full Linux environment where convenient. I will then discuss IX and Shinjuku, two generations of new datacenter-focused operating systems that were enabled by Dune. IX provides a novel system call interface that greatly improves network throughput without sacrificing latency. For example, IX improves Memcached's TCP throughput by 5x over Linux. Shinjuku, an ongoing research effort, aims to significantly increase CPU utilization through a centralized approach to intra-server load balancing. Adam Belay is a Ph.D. candidate in Computer Science at Stanford University, where he is a member of the Secure Computer Systems Group and the Multiscale Architecture and Systems Team. Previously, he worked on storage virtualization at VMware Inc. and contributed substantial power management code to the Linux Kernel project. Adam's research area is operating systems and networking. Much of his work has focused on restructuring computer systems so that developers can more easily reach the full performance potential of hardware. Adam has received a Stanford Graduate Fellowship, a VMware Graduate Fellowship, and an OSDI Jay Lepreau Best Paper Award.

1 0

Colloquium Speaker: Dimitris Papailiopoulos Today- 12:30pm
by Nicole E. Wagenblast 07 Mar '16

07 Mar '16

Please note: The Large Auditorium does not permit food, therefore lunch will not be served. Colloquium Speaker Dimitris Papailiopoulos , University of California, Berkeley Monday, March 7, 2016 - 12:30pm Computer Science Large Auditorium, 104 Less Talking, More Learning: Avoiding Coordination In Parallel Machine Learning Algorithms The recent success of machine learning (ML) in both science and industry has generated an increasing demand to support ML algorithms at scale. In this talk, I will discuss strategies to gracefully scale machine learning on modern parallel computational platforms. A common approach to such scaling is coordination-free parallel algorithms, where individual processors run independently without communication, thus maximizing the time they compute. However, analyzing the performance of these algorithms can be challenging, as they often introduce race conditions and synchronization problems. In this talk, I will introduce a general methodology for analyzing asynchronous parallel algorithms. The key idea is to model the effects of core asynchrony as noise in the algorithmic input. This allows us to understand the performance of several popular asynchronous machine learning approaches, and to determine when asynchrony effects might overwhelm them. To overcome these effects, I will propose a new framework for parallelizing ML algorithms, where all memory conflicts and race conditions can be completely avoided. I will discuss the implementation of these ideas in practice, and demonstrate that they outperform the state-of-the-art across a large number of ML tasks on gigabyte-scale data sets. Dimitris Papailiopoulos is a postdoctoral researcher in the Department of Electrical Engineering and Computer Sciences at UC Berkeley and a member of the AMPLab. His research interests span machine learning, coding theory, and parallel and distributed algorithms, with a current focus on coordination-free parallel machine learning, large-scale data and graph analytics, and the use of codes to speed up distributed computation. Dimitris completed his Ph.D. in electrical and computer engineering at UT Austin in 2014. At Austin he worked under the supervision of Alex Dimakis. In 2015, he received the IEEE Signal Processing Society, Young Author Best Paper Award.

1 0

Colloquium Speaker: Dimitris Papailiopoulos Monday, March 7- 12:30pm- reminder
by Nicole E. Wagenblast 06 Mar '16

06 Mar '16

Please note: The Large Auditorium does not permit food, therefore lunch will not be served. Colloquium Speaker Dimitris Papailiopoulos , University of California, Berkeley Monday, March 7, 2016 - 12:30pm Computer Science Large Auditorium, 104 Less Talking, More Learning: Avoiding Coordination In Parallel Machine Learning Algorithms The recent success of machine learning (ML) in both science and industry has generated an increasing demand to support ML algorithms at scale. In this talk, I will discuss strategies to gracefully scale machine learning on modern parallel computational platforms. A common approach to such scaling is coordination-free parallel algorithms, where individual processors run independently without communication, thus maximizing the time they compute. However, analyzing the performance of these algorithms can be challenging, as they often introduce race conditions and synchronization problems. In this talk, I will introduce a general methodology for analyzing asynchronous parallel algorithms. The key idea is to model the effects of core asynchrony as noise in the algorithmic input. This allows us to understand the performance of several popular asynchronous machine learning approaches, and to determine when asynchrony effects might overwhelm them. To overcome these effects, I will propose a new framework for parallelizing ML algorithms, where all memory conflicts and race conditions can be completely avoided. I will discuss the implementation of these ideas in practice, and demonstrate that they outperform the state-of-the-art across a large number of ML tasks on gigabyte-scale data sets. Dimitris Papailiopoulos is a postdoctoral researcher in the Department of Electrical Engineering and Computer Sciences at UC Berkeley and a member of the AMPLab. His research interests span machine learning, coding theory, and parallel and distributed algorithms, with a current focus on coordination-free parallel machine learning, large-scale data and graph analytics, and the use of codes to speed up distributed computation. Dimitris completed his Ph.D. in electrical and computer engineering at UT Austin in 2014. At Austin he worked under the supervision of Alex Dimakis. In 2015, he received the IEEE Signal Processing Society, Young Author Best Paper Award.

1 0