- talks - lists.cs.princeton.edu

Srinivas Narayana will present his Pre-FPO on Wednesday, November 11, 2015 at 1:30pm in CS 301
by Nicki Gotsis 04 Nov '15

04 Nov '15

Srinivas Narayana will present his Pre-FPO on Wednesday, November 11, 2015 at 1:30pm in CS 301. The members of his committee are: Jennifer Rexford (adviser), David Walker (reader), Sanjay Rao (Purdue, 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: Declarative Network Path Queries Abstract: Effective management of computer networks by operators is crucial to ensure the availability and performance of "always online" services that we depend on. Towards this goal, programmatic tools can remove slow and expensive human involvement in management. Recently, Software-Defined Networking (SDN) technology has eased programmatic *control* of networks, but there has been relatively little attention on programmatic *measurement* of networks. My thesis focuses on a broad class of network measurement questions that analyze the flow of traffic along network paths. Such questions are crucial for many network management tasks, including traffic engineering, diagnosing congestion, mitigating DDoS attacks, localizing packet loss in networks, and several others. With the current state-of-the-art, network operators measure traffic flow by "synthesizing" multiple data streams from the network---including updates to forwarding rules, traffic observations from counters and packet samples, and changes in network topology. However, this approach has significant limitations: it makes measurements indirect for operators to express, and forces operators to make a difficult trade-off up front between the accuracy and overhead of their measurements. In my thesis, I approach network path measurement with two key principles: (1) Enable operators to specify the measurements they need in a declarative query language; and (2) Drive network measurement according to operator-specified queries. This enables the collection of *exactly* the traffic that satisfies the operator-specified queries, with accurate results for those queries at low overhead. There are three important pieces in my research that realize these principles in practice. First, I will present an declarative query language that enables efficient path-based traffic monitoring. Path queries are specified as regular expressions over predicates on packet locations and header values, with SQL-like ``groupby'' constructs for aggregating results anywhere along a path. Packets can be captured either before or after they traverse a path that satisfies a query, returning results as packet or byte counters, entire packets (mirrored to collectors), or packet and flow sampled records (from commonly deployed packet-sampling technologies). A network operator writes each query indepedently of the forwarding policy in the network, as well as other queries, without worrying about the specifics of switch hardware. We show that she is able to specify several realistic measurement questions corresponding to network resource management, policy enforcement, and fault diagnosis. Second, I will present a query run-time system that translates the operator-specified queries into accurate data plane measurement that runs on commodity switch hardware. The run-time first compiles queries into a deterministic finite automaton. The automaton's transition function is then partitioned, compiled into `match-action' rules (which can run on commodity hardware), and distributed over the switches. Switches stamp packets with automaton states to track their progress towards fulfilling a query. Only when packets satisfy a query are they counted, sampled, or sent to collectors for further analysis. By processing queries in the data plane, users ``pay as they go'', as data-collection overhead is limited to exactly those packets that satisfy the query. Further, storing the automaton state requires only a small amount of extra space (2-4 bytes) on each packet---for example a VLAN or MPLS header. Third, I will present optimizations to our prototype run-time system that is built on top of the Pyretic SDN controller, an open source platform. These optimizations address fundamental bottlenecks in compilation, caused by queries and forwarding policies performing different actions on overlapping sets of packets. Combining such actions into a unified rule set can result in exponential increases in query compile time and the output rule set. The optimizations leverage key insights into the structure of the constituent policies, and recent advances in commodity hardware, to reduce compile times and rule set sizes by 3-4 orders of magnitude. Experiments indicate that the system can enable ``interactive debugging''---compiling multiple queries in a few seconds---while fitting rules comfortably in modern switch rule memories. Together, the query language and run-time system enable expressive measurement specification, as well as accurate and efficient network measurement, furthering the state-of-the-art of network management on commodity hardware.

1 0

Daniel Larkin will present his FPO, "Compressing Trees with a Sledgehammer" on Wednesday, 11/11/2015 at 10am in CS 402
by Nicki Gotsis 04 Nov '15

04 Nov '15

Daniel Larkin will present his FPO on Wednesday, 11/11/2015 at 10:00AM, 402 Computer Science. The members of his committee are: Readers: Robert Sedgewick and Jeff Erickson (University of Illinois at Urbana-Champaign); Examiners: Sanjeev Arora, Zeev Dvir and Robert Tarjan (adviser). A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. The talk title and abstract follow below: Title: "Compressing Trees with a Sledgehammer" Abstract: A variety of problems can be solved more efficiently with the use of compressed trees. The compressed tree method is flexible and can be applied in different ways to solutions for many problems including disjoint set union, nested set union, and path evaluation. The central contribution of this thesis is a unified framework for the analysis of the compressed tree method and a meta-theorem that proves an inverse-Ackermann-type bound for a class of algorithms. The meta-theorem requires only that the compaction method be well-structured and that the other operations maintain a forest structure that admits a well-behaved rank function. These are the weakest known conditions of any analysis to-date that proves such a bound. We use the framework to give a clean, compact alternative analysis of all but one of the known efficient algorithms for disjoint set union; we provide an explicit proof of optimality for the remaining known optimal method, splicing by rank, which was left as an exercise by Tarjan and van Leeuwen [24]; we prove that a new algorithm for disjoint set union called randomized linking is optimal, giving theoretical backing for some recent experimental results; and finally we proceed to explore the nested set union problem, giving an optimal algorithm for any constant number of partitions as well as a few alternatives for the restricted case of two partitions.

1 0

Colloquium Speaker Mayur Naik Mon, Oct 26, 4:30pm
by Nicole E. Wagenblast 26 Oct '15

26 Oct '15

Colloquium Speaker Mayur Naik , Georgia Institute of Technology Monday, October 26, 2015 - 4:30pm Computer Science 105 Programming Abstractions for Mobile-Cloud Computing As the computing landscape changes to provide a more personalized and targeted experience to users, the demand for compute-intensive tasks on mobile devices such as tablets, smartphones, and smart watches increases. However, this demand coincides with diminishing returns from transistor scaling as well as battery and power constraints that may curtail mobile devices from providing new capabilities. Mobile-cloud computing is an emerging approach that boosts mobile devices by offloading compute-intensive tasks in mobile applications to more powerful machines. A central challenge in mobile-cloud computing concerns orchestrating computation and communication between the mobile device and the remote system in a manner that allows computation gains to outweigh communication costs. To enable this tradeoff, we study two simple programming abstractions that allow the remote system to preserve state across disparately offloaded segments of a computation, and to communicate with the mobile device while performing offloaded computation. To evaluate the benefits of these abstractions, we have developed an efficient algorithm based on finding a min-cut of a graph that identifies the optimal offloading pattern. I will describe our experience applying these abstractions to partition several Android applications and obtain speedup, energy savings, and improved QoS under different network settings. Our experience also yields insights into how to further accelerate mobile-cloud computing through designing new networking protocols and leveraging advances in hardware approximation and acceleration. Mayur Naik is an Assistant Professor in the School of Computer Science at Georgia Tech since 2011. His research interests lie in areas related to programming systems, with a current emphasis on program analysis techniques for improving software quality and programmer productivity on modern computing platforms. He is a recipient of Distinguished Paper awards at FSE'15, PLDI'14, and ICSE'09, the Lockheed-Martin Dean's award for excellence in teaching at Georgia Tech (2015), and an NSF CAREER award (2013). He received his Ph.D. in Computer Science from Stanford University in 2008 and was a Research Scientist at Intel Labs, Berkeley from 2008 to 2011.

1 2

Talk- Byron Cook Tues, Oct 27, 10:30am
by Nicole E. Wagenblast 22 Oct '15

22 Oct '15

Talk Tuesday, Oct 27, 10:30am Computer Science 302 Byron Cook, University College London Proving that programs eventually do something good In this talk I will discuss research advances that led to practical tools for automatically proving program termination and related properties, e.g. liveness. Practical applications include automatically proving device driver correctness, and pharmaceutical research. Byron Cook is Professor of Computer Science at University College London. Byron is also a Senior Principal at Amazon. See http://www0.cs.ucl.ac.uk/staff/b.cook/ for more information.

1 1

Speaker- Suman Banerjee Today- 3pm
by Nicole E. Wagenblast 20 Oct '15

20 Oct '15

Suman Banerjee, University of Wisconsin, Madison Tuesday, October 20- 3pm Computer Science 402 ParaDrop: Enabling Third Party Apps in Home WiFi Gateways for Fun and Profit Over the last few years, we have been building a new home WiFi router platform that can allow 3rd party applications and services to be deployed on it. The system, called Paradrop, is all in software and is an extreme form of the popular notion known as edge computing. It leverages popular concepts of virtualization and software-defined networking. It also integrates techniques for better monitoring, management, and mitigation of RF interference experienced in these environments. It hopes to be to the home router market what the smartphones were to the cellphone market. We believe that ParaDrop can be a significant enabler for the emerging services for smarter homes that take advantage of Internet of Things applications. Furthermore, the platform can also be leveraged for delivering a more hands-on educational content on emerging topics, such as Internet-of-Things, mobile development, mobile and wireless systems design, and even basic computer networking. In this talk, I will describe some of the technical developments in creating this platform and outline our ongoing activities. Suman Banerjee is an Professor in Computer Sciences at UW-Madison where he is the founding director of the WiNGS laboratory which broadly focuses on research in wireless and mobile networking systems. He received his undergraduate degree from IIT Kanpur, and MS and PhD degrees from the University of Maryland. He is the inaugural recipient of the ACM SIGMOBILE Rockstar award and a recipient of the NSF Career Award. He is a recipient of multiple award papers at various conferences, such as ACM MobiCom, ACM CoNEXT, and IEEE Dyspan. Further, technology developed by Prof. Banerjee have won various accolades including the first prize at the Wisconsin Governor's Business Plan Competition in 2011 and in the Interdigital Innovation Challenge in 2012. He is currently serving as the chair of ACM SIGMOBILE.

1 0

Colloquium Speaker Catherine McGeoch today- 12:30pm
by Nicole E. Wagenblast 20 Oct '15

20 Oct '15

Colloquium Speaker Catherine McGeoch, Amherst College Benchmarking the D-Wave 2X: Challenges and Early Results Tuesday, October 20- 12:30pm Computer Science 105 Benchmarking the D-Wave 2X: Challenges and Early Results A D-Wave platform implements a quantum annealing algorithm in hardware, to solve an NP-hard problem known as Ising Model Optimization (also called Quadratic Unconstrained Boolean Optimization). The ``hardware'' is a processor chip containing qubits that exploit quantum properties such as superposition and entanglement to carry out the computation. This is a heuristic algorithm that belongs to the adiabatic quantum model of computation, an alternative to the more familiar quantum gate model of computation. The task of performance assessment for these novel platforms -- comparing classical heuristics implemented in software to a quantum analog heuristic implemented in hardware -- gives rise to a number of new methodological issues, on top of the usual challenges relating to evaluation of heuristics for NP-hard problems. I will discuss some of these issues and present some early performance results for the D-Wave 2X, a 1000-qubit processor launched in summer 2015.

1 0

EE Seminar Announcement - David Patterson, UC-Berkeley - November 11, 2015
by Nicole E. Wagenblast 19 Oct '15

19 Oct '15

Hi Res PRI_E_electrical_below_w-shield.jpg “Instruction Sets Want to Be Free: A Case for RISC-V” David Patterson, Professor, Electrical Engineering & Computer Science, University of California-Berkeley Wednesday, November 11, 2015 4:30 – 5:45 pm Reception to Follow Friend Center, Convocation Room Abstract: We start by quickly reviewing 50 years of computer architecture to show there is now widespread agreement on instruction set architecture (ISA). Unlike most other fields, despite this harmony there is no open alternative to proprietary offerings from ARM and Intel. Thus, we propose RISC-V (“RISC Five”), which targets Systems on a Chip (SoC). It has: * A small base of <50 classic RISC instructions that run a full open-source software stack. * Opcodes reserved for tailoring an SoC to applications. * Standard instruction extensions optionally included in an SoC. * Incorporated, as an open ISA, community suggestions before extensions are finalized. * A foundation to evolve the RISC-V slowly based solely on technical reasons voted on by members vs. by companies that inflate ISAs rapidly for business as well as technical reasons; ARM and Intel average about 2 new instructions per month. * No restrictions: there is no cost, no paperwork, and anyone can use it. Attendees will get a 2-page reference card (“green card”), which lists all RISC-V extensions, to contrast this minimal ISA with the 3,600-page x86 manual and the 5,400-page ARMv8 manual. We conclude by recapping 10 RISC-V chips built using Agile methods in just 4 years, including how shockingly cheap it is today to manufacture 100 2x2-mm, 28-nm chips. We used Chisel, a new hardware design language that reduces design effort by greatly increasing reuse. Bio: David Patterson joined UC Berkeley nearly 40 years ago. He has been Director of several research labs, Chair of Berkeley’s CS Division, Chair of the Computing Research Association, and President of ACM. His most successful projects are likely Reduced Instruction Set Computers (RISC), Redundant Arrays of Inexpensive Disks (RAID), and Network of Workstations (NOW), all of which helped lead to multi-billion-dollar industries. This research led to many papers, 6 books, and about 35 honors for him and his friends, including election to the National Academy of Engineering, the National Academy of Sciences, and the Silicon Valley Engineering Hall of Fame. He shared the IEEE von Neumann Medal and the NEC C&C Prize with John Hennessy, co-author of two of his books and President of Stanford University. This seminar is supported with funds from the Korhammer Lecture Series

1 0

Colloquium Speaker Catherine McGeoch Tues Oct 20- 12:30pm
by Nicole E. Wagenblast 19 Oct '15

19 Oct '15

Colloquium Speaker Catherine McGeoch, Amherst College Benchmarking the D-Wave 2X: Challenges and Early Results Tuesday, October 20- 12:30pm Computer Science 105 Benchmarking the D-Wave 2X: Challenges and Early Results A D-Wave platform implements a quantum annealing algorithm in hardware, to solve an NP-hard problem known as Ising Model Optimization (also called Quadratic Unconstrained Boolean Optimization). The ``hardware'' is a processor chip containing qubits that exploit quantum properties such as superposition and entanglement to carry out the computation. This is a heuristic algorithm that belongs to the adiabatic quantum model of computation, an alternative to the more familiar quantum gate model of computation. The task of performance assessment for these novel platforms -- comparing classical heuristics implemented in software to a quantum analog heuristic implemented in hardware -- gives rise to a number of new methodological issues, on top of the usual challenges relating to evaluation of heuristics for NP-hard problems. I will discuss some of these issues and present some early performance results for the D-Wave 2X, a 1000-qubit processor launched in summer 2015.

2 1

Fwd: Special Seminar: GoogleCar Team's Josh Herbach'08
by Jennifer Rexford 19 Oct '15

19 Oct '15

> From: Alain Kornhauser <alaink(a)princeton.edu> > Subject: Special Seminar: GoogleCar Team's Josh Herbach'08 > Date: October 18, 2015 at 10:45:35 PM EDT > To: orf467_f2015(a)princeton.edu > > Wednesday, Oct 21 1:30->2:50 > >

1 0

Colloquium Speaker Catherine McGeoch Tues Oct 20- 12:30pm
by Nicole E. Wagenblast 15 Oct '15

15 Oct '15

Colloquium Speaker Catherine McGeoch, Amherst College Benchmarking the D-Wave 2X: Challenges and Early Results Tuesday, October 20- 12:30pm Computer Science 105 Benchmarking the D-Wave 2X: Challenges and Early Results A D-Wave platform implements a quantum annealing algorithm in hardware, to solve an NP-hard problem known as Ising Model Optimization (also called Quadratic Unconstrained Boolean Optimization). The ``hardware'' is a processor chip containing qubits that exploit quantum properties such as superposition and entanglement to carry out the computation. This is a heuristic algorithm that belongs to the adiabatic quantum model of computation, an alternative to the more familiar quantum gate model of computation. The task of performance assessment for these novel platforms -- comparing classical heuristics implemented in software to a quantum analog heuristic implemented in hardware -- gives rise to a number of new methodological issues, on top of the usual challenges relating to evaluation of heuristics for NP-hard problems. I will discuss some of these issues and present some early performance results for the D-Wave 2X, a 1000-qubit processor launched in summer 2015.

1 0