May 2016 - talks - lists.cs.princeton.edu

4:30pm Tue May 10 talk in E-Quad B205 on intersection of biological diversity and robotics
by Jennifer Rexford 03 May '16

03 May '16

> > From: "Heather L. Evans" <heathere(a)Princeton.EDU> > Subject: EE Department Seminar - Amanda Prorok - May 10th > Date: May 3, 2016 at 9:22:00 AM EDT > To: ee-seminar(a)Princeton.EDU > Reply-To: "Heather L. Evans" <heathere(a)Princeton.EDU> > > > Speaker: > Amanda Prorok, University of Pennsylvania > Title: > Diversity and Heterogeneity in Multi-Robot Systems > Day: > Tuesday, May 10, 2016 > > > Time: > 4:30on > Room: > B205, E-Quad > Host: > Prof. Peter Ramadge > > > > > > > > > Abstract: > Nature demonstrates the benefits of biological diversity with ecosystems that are resilient, adaptable, and productive over long time-spans. In robotics research, we are interested in a principled study of diversity with the aim of building on nature's inventions. In this talk, I shed light on the effects and implications of diversity and heterogeneity in multi-robot systems. I begin by displaying empirical results that stem from a collaborative positioning problem. As the need for foundational approaches becomes evident, my focus shifts to the question of how to formalize diversity. I answer this question in the context of heterogeneous robot swarms, with insights that pertain to the particular aspects of performance and security. > > Bio: > Amanda Prorok is currently a Postdoc in the General Robotics, Automation, Sensing and Perception (GRASP) Laboratory at the University of Pennsylvania, where she works with Prof. Vijay Kumar on heterogeneous robot swarms. She completed her PhD at EPFL, Switzerland, where she addressed the topic of localization with ultra-wideband sensing for large-scale, collaborative systems. Her dissertation was awarded the Asea Brown Boveri (ABB) award for the best thesis at EPFL in the fields of Computer Sciences, Automatics and Telecommunications. She was selected as an MIT Rising Star in 2015, and won a Best Paper Award at BICT 2015. > > > > > > Heather Evans > Assistant to the Chair > Department of Electrical Engineering > Princeton University > Engineering Quadrangle, B-210 > Olden Street > Princeton, NJ 08544 > (p): 609-258-7282 > (f): 609-258-0119 > heathere(a)princeton.edu <mailto:heathere@princeton.edu>

1 0

Nayana Prasad Nagendra will present her general exam on Friday, May 13, 2016 at 10am in CS 402
by Nicki Gotsis 03 May '16

03 May '16

Nayana Prasad Nagendra will present her general exam on Friday, May 13, 2016 at 10am in CS 402 The members of her committee are David August (adviser), David Wentzlaff, and Aarti Gupta. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. For a full calendar view of all of the upcoming general exams, FPO's and Pre-FPO's, please go to the following link . HW-DSWP Abstract: Automatic parallelization by compiler is one way to better utilize multiple cores. Unfortunately, the best performing compiler techniques, such as those in the DSWP (Decoupled Software Pipelining) family of transformations, employ speculation and rely on dynamic information obtained by profiling, a technique unpopular with developers. Runtime techniques, such as Just-In-Time compilers, can address the popularity-of-profiling problem, but they are limited in the amount of dynamic information they can collect without negatively impacting overall program performance. Noting that existing processors already include structures that gather the type of information speculative thread extraction techniques need, I explore the possibility of performing thread extraction transformations in hardware and propose HW-DSWP (Hardware - DSWP) parallelization technique. The framework identifies hot loops based on the trace of backward branches, calculates dependency depth of instructions and segregates the instruction stream into critical and non-critical set which would then be executed on the main thread and additional thread respectively. Books: [1] John L. Hennessy and David A. Patterson, Computer Architecture: A Quantitative Approach (5th Edition), 2011. [2] Andrew W. Appel, Modern Compiler Implementation in ML. Cambridge University Press, 1998 Reading List: [1] G. Ottoni, R. Rangan, A. Stoler, and D. August. “Automatic Thread Extraction with Decoupled Software Pipelining”. In 38th International Symposium on Microarchitecture (MICRO), November 2005 [2] E. Raman, G. Ottoni, A. Raman, M. J. Bridges, and D. August. “Parallel-Stage Decoupled Software Pipelining”. In the International Symposium on Code Generation and Optimization (CGO), April 2008 [3] R. Rangan, N. Vachharajani, M. Vachharajani, and D. I. August. “Decoupled Software Pipelining with the Synchronization Array”. In 13th International Conference on Parallel Architectures and Compilation Techniques (PACT), September 2004 [4] A. Cristal, O. Santana, F. Cazorla, M. Galluzzi, T. Ramirez, M. Pericas, and M.Valero. “Kilo-Instruction Processors: Overcoming the Memory Wall”. IEEE Micro, 25(3), May 2005. [5] S. Srinath, B. Ilbeyi, M. Tan, G. Liu, Z. Zhang, and C. Batten, “Architectural Specialization for Inter-Iteration Loop Dependence Patterns”. In the International Symposium on Microarchitecture (MICRO), December 2014 [6] S. Campanoni, K. Brownell, S. Kanev, T. M. Jones, G.-Y. Wei, and D. Brooks, “HELIX-RC: An Architecture-Compiler Co-Design for Automatic Parallelization of Irregular Programs”. In 41st International Symposium on Computer Architecture (ISCA), June 2014. [7] V. Govindaraju, C. H. Ho, and K. Sankaralingam. “Dynamically Specialized Datapaths for Energy Efficient Computing”. In 17th International Symposium on High-Performance Computer Architecture (HPCA), 2011 [8] S. Campanoni, T. M. Jones, G. Holloway, V. J. Reddi, G. Wei, and D. Brooks. "HELIX: Automatic Parallelization of Irregular Programs for Chip Multiprocessing". In CGO, 2012. [9] J. Yang, K. Skadron, M. Soffa, and K. Whitehouse. “Feasibility of Dynamic Binary Parallelization”. In 4th USENIX conference on Hot Topics in Parallelism, 2011 [10] F. Liu, H. Ahn, S. Beard, T. Oh, and D. August, “DynaSpAM: Dynamic Spatial Architecture Mapping Using out of Order Instruction Schedules”. In 42nd International Symposium on Computer Architecture (ISCA), 2015

1 0

Colloquium Speaker: John Langford, Friday May 6, 12:30pm
by Nicole E. Wagenblast 02 May '16

02 May '16

Colloquium Speaker John Langford, Microsoft Research Friday, May 6, 12:30pm Computer Science 105 How to make an Infovore An Infovore is an information-based entity that explores the world, learns, and applies these learnings effectively. In essence: a form of weak AI. We have been working on a general-purpose infovore for making decisions using elements of contextual bandits, systems, and experts-style learning that has now been successfully deployed at large scale. I will discuss the architecture of the infovore, the key results upon which it relies, and how everything works together to enable true open-loop learning in the real world.

1 0

Olivier Savary Belanger will present his general exam Wednesday, May 11, 2016 at 10am in CS 302.
by Nicki Gotsis 02 May '16

02 May '16

Olivier Savary Belanger will present his general exam Wednesday, May 11, 2016 at 10am in CS 302. The members of his committee are Andrew Appel (adviser), Aarti Gupta, and Davis August. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Abstract: An increasing amount of software is written and proven correct in proof assistants. For example, an optimizing compiler for C, CompCert, has been developed and fully verified in Coq, an interactive theorem prover. For interactive theorem provers to become credible programming environments, their compilation pipelines must generate production quality code. Moreover, these compilation pipelines should be proven correct, lest the guarantees achieved in the interactive theorem provers will not apply to the program being run. We have begun working on a verified compiler for Coq. In addition to being formally verified to preserve semantics from end-to-end, it will include some of the optimizations which are at the heart of fast functional language compilers such as SML/NJ and the OCaml compiler. As preliminary work, I have implemented a shrink-reducer performing reductions analogous to dead-code elimination and function inlining over a CPS intermediate language, and proven it correct for a subset of the language. I will report on the performance of our implementation compared to alternatives which use impure features, and discuss the next few steps towards completing the compilation pipeline. Textbooks: - B. C. Pierce. Types and Programming Languages. ISBN 0262162091. The MIT Press, 2002 Part I (Untyped Systems) Part II (Simple Types) Part IV (Recursive Types) Part V (Polymorphism) Ch. 22-25 - B. C. Pierce. Advanced Topics in Types and Programming Languages. ISBN 0262162288. The MIT Press, 2004. Dependent Types (Ch. 2) - A. W. Appel. Compiling with Continuations. ISBN 0521416957. Cambridge University Press, 1992. Papers: - O. Danvy and A. Filinski. Representing control: a study of the CPS transformation. MSCS 1992. - A. W. Appel and T. Jim. Shrinking Lambda Expressions in Linear Time. JFP 1997. - O. Danvy and L. R. Nielsen. A first-order one-pass CPS transformation. TCS 2003 - P. Letouzey. A New Extraction for Coq. TYPES 2002. - A. Kennedy. Compiling with continuations, continued. ICFP 2007. - R. Kumar et al. CakeML: A Verified Implementation of ML. POPL 2014

1 0

Nora Willett will be presenting her general exam on Tuesday, May 10, 2016 at 10am in CS 402.
by Nicki Gotsis 02 May '16

02 May '16

Nora Willett will be presenting her general exam on Tuesday, May 10, 2016 at 10am in CS 402. The members of her committee are Adam Finkelstein (adviser), Tom Funkhouser, and Szymon Rusinkiewicz. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. abstract: When bringing animated characters to life, artists often augment the primary motion of a character by adding secondary animation such as wrinkling cloth, jiggling bulges, or hair and leaves blown by wind. Such effects can often be achieved for 3D animation through physical simulation. However, 2D animations typically lack sufficient information about the structure of the characters to support such simulations. Animators therefore can only add secondary motion to animated illustrations through arduous manual effort. This paper presents a set of physically-inspired building blocks that attach to layered, illustrated characters in order to propagate motion in a way that produces controllable, composable secondary animation. These components can be easily rigged and controlled via a small number of parameters that produce an expressive range of effects. Our approach supports a wide range of the most common secondary effects, which we demonstrate with an assortment of characters of varying complexity. reading list: 1. A. Jacobson, I. Baran, J. Popovic, and O. Sorkine. Bounded biharmonic weights for real-time deformation. *ACM Trans. Graph*., 30(4):78, 2011. 2. A. Rivers, T. Igarashi, and F. Durand. 2.5 d cartoon models. In *ACM Transactions on Graphics (TOG)*, volume 29, page 59. ACM, 2010. 3. S. C. Hsu and I. H. Lee. Drawing and animation using skeletal strokes. In *Proceedings of the 21st annual conference on Computer graphics and interactive techniques*, pages 109–118. ACM, 1994. 4. S. Chenney, M. Pingel, R. Iverson, and M. Szymanski. Simulating cartoon style animation. In *Proceedings of the 2nd international symposium on Nonphotorealistic animation and rendering*, pages 133– 138. ACM, 2002. 5. R. Barzel, J. R. Hughes, and D. N. Wood. Plausible motion simulation for computer graphics animation. In *Computer Animation and Simulation’96*, pages 183–197. Springer, 1996. 6. R. Barzel. Faking dynamics of ropes and springs. *IEEE Computer Graphics and Applications*, (3):31– 39, 1997. 7. R. Barzel and A. H. Barr. A modeling system based on dynamic constraints. In *ACM SIGGRAPH Computer Graphics*, volume 22, pages 179–188. ACM, 1988. 8. R. C. Davis, B. Colwell, and J. A. Landay. K-sketch: a ’kinetic’ sketch pad for novice animators. In *Proceedings of the SIGCHI Conference on Human Factors in Computing Systems*, pages 413–422. ACM, 2008. 9. R. H. Kazi, F. Chevalier, T. Grossman, and G. Fitzmaurice. Kitty: sketching dynamic and interactive illustrations. In *Proceedings of the 27th annual ACM symposium on User interface software and technology*, pages 395–405. ACM, 2014. 10. P. Shirley, M. Ashikhmin, and S. Marschner. Fundamentals of computer graphics. *CRC Press*, 2009.

1 0

Muhammad Shahbaz will present his generals exam on Wednesday, May 11, 2016 at 2:30pm in CS 302
by Nicki Gotsis 02 May '16

02 May '16

Muhammad Shahbaz will present his generals exam on Wednesday, May 11, 2016 at 2:30pm in CS 302 The members of his committee are Nick Feamster (adviser), Jennifer Rexford, and Kyle Jamieson. *Title:* PISCES: A Programmable, Protocol-Independent Software Switch Abstract: Virtualized data centers use software hypervisor switches to steer packets to and from virtual machines (VMs). The switch frequently needs upgrading and customization—to support new protocol headers or encapsulations for tunneling or overlays, to improve measurement and debugging features, and even to add middlebox-like functions. Software switches are typically based on a large body of code, including kernel code. Changing the switch is a formidable undertaking requiring domain mastery of network protocol design and developing, testing, and maintaining a large, complex codebase. In this talk, we will argue that changing how a software switch forwards packets should not require intimate knowledge of its implementation. Instead, it should be possible to specify how packets are processed and forwarded in a high-level domain-specific language (DSL) such as P4, then compiled down to run on the underlying software switch. I will present PISCES, a software switch that is not hard-wired to specific protocols, which eases adding new features. We will also show how the compiler can analyze the high-level specification to optimize forwarding performance. Our evaluation shows that PISCES performs comparably to Open vSwitch, a hardwired hypervisor switch, and that PISCES programs are about 40 times shorter than equivalent Open vSwitch programs. *Reading List:* *Textbook* L. L. Peterson and B. S. Davie. "Computer Networks, Fifth Edition: A Systems Approach." Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 5th edition, 2011. *Papers* 1. Jose, Lavanya, et al. "Compiling packet programs to reconfigurable switches." NSDI 15. 2. Bosshart, Pat, et al. "P4: Programming protocol-independent packet processors." CCR 14. 3. Song, Haoyu. "Protocol-oblivious forwarding: Unleash the power of SDN through a future-proof forwarding plane." HotSDN 13. 4. Lattner, Chris, and Vikram Adve. "LLVM: A compilation framework for lifelong program analysis & transformation." CGO 04. 5. Adve, Vikram, et al. "LLVA: A low-level virtual instruction set architecture." MICRO 03. 6. Pfaff, Ben, et al. "The design and implementation of open vswitch." NSDI 15. 7. Belay, Adam, et al. "IX: A protected dataplane operating system for high throughput and low latency." OSDI 14. 8. Morris, Robert, et al. "The Click modular router." SOSP 99. 9. McCanne, Steven, and Van Jacobson. "The BSD packet filter: A new architecture for user-level packet capture." USENIX 93. 10. Bosshart, Pat, et al. "Forwarding metamorphosis: Fast programmable match-action processing in hardware for SDN."SIGCOMM 13. 11. Anwer, Muhammad Bilal, et al. "Switchblade: a platform for rapid deployment of network protocols on programmable hardware." SIGCOMM 10. 12. Emmerich, Paul, et al. "MoonGen: A Scriptable High-Speed Packet Generator." IMC 15. 13. Katta, Naga, et al. "HULA: Scalable Load Balancing Using Programmable Data Planes." SOSR 16. 14. Sivaraman, Anirudh, et al. "Towards Programmable Packet Scheduling." HotNets 15. 15. Jeyakumar, Vimalkumar, et al. "Millions of little minions: Using packets for low latency network programming and visibility." SIGCOMM 14.

1 0

Yinda Zhang will present his general exam on Monday, May 09, 2016 at 10am in CS 402.
by Nicki Gotsis 02 May '16

02 May '16

Yinda Zhang will present his general exam on Monday, May 09, 2016 at 10am in CS 402. The members of his committee are Jianxiong Xiao (adviser), Tom Funkhouser, and Szymon Rusinkiewicz. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Reading list: [DalalTriggs] Histograms of oriented gradients for human detection. [SIFT] Distinctive image features from scale-invariant keypoints. [ExemplarSVMs] Ensemble of exemplar-svms for object detection and beyond. [DPM] Object Detection with Discriminatively Trained Part Based Models. [SelectiveSearch] Segmentation as selective search for object recognition. [Context] Auto-context and Its Application to High-level Vision Tasks [RCNN] Rich feature hierarchies for accurate object detection and semantic segmentation [Places] Learning Deep Features for Scene Recognition using Places Database. [Room Layout] Ecient Exact Inference for 3D Indoor SceneUnderstanding [Geometric Context] Geometric Context from a Single Image [Spatial Layout] Recovering the Spatial Layout of Cluttered Rooms Text book: Richard Szeliski, Computer Vision: Algorithm and Application Abstract: My research mainly focus on scene understanding, which includes a variety of topics to allow computer to perceive and interact with the surrounding environment. These topics, e.g. scene parsing, eye gaze tracking, scene classification, act as important roles in many critical robotics applications. The goal of scene parsing is to understand the spatial layout of the environment and localize objects in 3D space. Apart from traditional object recognition, scene parsing analyze the input image from a large scale that involves multiple objects, which allows the investigation of relationships among objects. Scene parsing also takes advantage of evidence beyond the visual appearance shown in the color or depth image, like past and future states of the object, underlying physics rule, functionality and interaction between human and objects. All of these key factors for scene understanding is more invariant and natural to be modeled in 3D space. Our first effort for 3D scene parsing is the PanoContext, which models an entire scene in 3D space. The experiments show that based solely on 3D context, PanoContext can achieve comparable performance with the state-of-the-art 2D object detectors. The output of the algorithm can be directly rendered in 3D for a virtual exploration of the indoor environment. Recently, we proposed a context-aware deep learning architecture for scene parsing. We hardwires the prior context knowledge into the network, which can be optimized end-to-end. The model requires only a single pass of the data to detect all the major objects in the room, and therefore is very efficient. Besides these, I also worked actively on creating large scaled dataset for scene classification, eye tracking saliency, and room layout estimation. Building a dataset with several magnitudes of bigger than the state of arts requires new interface and algorithm to enable data collection on crowd sourcing platform and achieve efficiency sub-linear to the scale of the data. While the scale of the 2D image dataset already goes to millions, RGBD images dataset still contains roughly 10K images, mostly due to the laborious labelling procedure. We are currently working on utilizing a large amount of unlabelled 3D reconstructed scene to learn a better feature representation for 3D object, and thus achieve better 3D object recognition performance.

1 0

Hansen Zhang will be presenting his general exam on Monday, May 9, 2016 at 1pm in CS 402.
by Nicki Gotsis 02 May '16

02 May '16

Hansen Zhang will be presenting his general exam on Monday, May 9,2016 at 1pm in CS 402. The members of his committee are David August (adviser), David Wentzlaff and Arvind Narayanan. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Abstract: The TrustGuard architecture prevents the leakage of users’ information in the presence of malicious system components (processor and memory). The basis of trust in the system is a pluggable hardware element called the Sentry which physically separates the untrusted components and the interface to the outside world. To gain access to the external interfaces of the system, the untrusted components have to prove to the Sentry that their intended communication results from the correct execution of trusted software. This work improves upon the original TrustGuard design in two ways. First, it introduces optimizations that reduce the bandwidth requirements between the untrusted processor and the Sentry. Second, it adds protection from replay attacks to the original TrustGuard design. Simulation results show that the new design is able to reduce bandwidth by 60% while maintaining the performance of the original design and add protection from replay attacks. Reading List: Textbooks: John L. Hennessy and David A. Patterson. 2011. Computer Architecture, Fifth Edition: A Quantitative Approach (5th ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. Ross J. Anderson. 2008. Security Engineering: A Guide to Building Dependable Distributed Systems (2 ed.). Wiley Publishing. Chapter 3,4,5,11,16 Papers: 1, Secure processors/coprocessors [1] G.E. Suh, D Clarke, B. Gassend, M. van Dijk, S. Devadas. AEGIS: architecture for tamper-evident and tamper-resistant processing. In Proceedings of the 17th annual international conference on Supercomputing, ICS’03, pages 160-171 [2] D. Y. Deng, D. Lo, G. Malysa, S. Schneider and G. E. Suh, "Flexible and Efficient Instruction-Grained Run-Time Monitoring Using On-Chip Reconfigurable Fabric," Microarchitecture (MICRO), 2010 43rd Annual IEEE/ACM International Symposium on, Atlanta, GA, 2010, pp. 137-148. [3] R. Kannavara and N. G. Bourbakis, "Surveying secure processors," in IEEE Potentials, vol. 28, no. 1, pp. 28-34, January-February 2009. [4] T. M. Austin, "DIVA: a reliable substrate for deep submicron microarchitecture design," Microarchitecture, 1999. MICRO-32. Proceedings. 32nd Annual International Symposium on, Haifa, 1999, pp. 196-207. 2, High Performance Caching [5] M. K. Qureshi, A. Jaleel, Y. N. Patt, S. C. Steely, and J. Emer. Adaptive insertion policies for high performance caching. In Proceedings of the 34th annual international symposium on Computer architecture (ISCA '07). ACM, New York, NY, USA, 381-391 [6] A. Jaleel, K. B. Theobald, S. C. Steely, Jr., and J. Emer. High performance cache replacement using re-reference interval prediction (RRIP). In Proceedings of the 37th annual international symposium on Computer architecture (ISCA '10). ACM, New York, NY, USA, 60-71 3, Compression [7] M. Thuresson, L. Spracklen and P. Stenstrom, "Memory-Link Compression Schemes: A Value Locality Perspective," in IEEE Transactions on Computers, vol. 57, no. 7, pp. 916-927, July 2008. [8] X. Chen, L. Yang, R. Dick, L. Shang and H. Lekatsas, "C-Pack: A High-Performance Microprocessor Cache Compression Algorithm," in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 18, no. 8, pp. 1196-1208, Aug. 2010. 4, Memory Integrity Verification [9] B. Gassend, G. E. Suh, D. Clarke, M. van Dijk and S. Devadas, "Caches and hash trees for efficient memory integrity verification," High-Performance Computer Architecture, 2003. HPCA-9 2003. Proceedings. The Ninth International Symposium on, 2003, pp. 295-306. [10] B. Rogers, S. Chhabra, M. Prvulovic and Y. Solihin, "Using Address Independent Seed Encryption and Bonsai Merkle Trees to Make Secure Processors OS- and Performance-Friendly," Microarchitecture, 2007. MICRO 2007. 40th Annual IEEE/ACM International Symposium on, Chicago, IL, 2007, pp. 183-196.

1 0

systems lunch talk 12:30-1:30pm (with noon-12:30pm lunch) on Monday May 2 in CS 302
by Jennifer Rexford 01 May '16

01 May '16

Speaker: Asaf Cidon, Stanford Unviersity Title: Cliffhanger: Scaling Performance Cliffs in Web Memory Caches Date/time: 12:30-1:30pm Monday May 2, with lunch available starting at noon Location: CS 302 Abstract: Web-scale applications are heavily reliant on memory cache systems such as Memcached to improve throughput and reduce user latency. Small performance improvements in these systems can result in large end-to-end gains. By analyzing measurements from a widely used caching service, Memcachier, we demonstrate that existing cache allocation techniques leave significant room for improvement. We develop Cliffhanger, a lightweight iterative algorithm that runs on memory cache servers, which incrementally optimizes the resource allocations across and within applications based on dynamically changing workloads. We also present our long term vision for a centrally controlled data center caching layer that manages applications' varying workloads across heterogeneous caches. Bio: Asaf Cidon is the CEO and co-founder of Sookasa, which was acquired by Barracuda Networks in March 2016. He completed his PhD at the Stanford University Computer Systems Lab, where he conducted research on cloud storage under Professors Mendel Rosenblum and Sachin Katti. Asaf previously worked at Google Israel in the web search team and served as a team leader in the Israeli army. He obtained his PhD and MS in Electrical Engineering from Stanford and his BS in Computer and Software Engineering Cum Laude from the Technion. In addition, he is a recipient of the Stanford Graduate Fellowship and Sohnis Promising Scientist Award.

1 0