April 2013 - talks - lists.cs.princeton.edu

W Lloyd FPO
by Melissa M. Lawson 25 Apr '13

25 Apr '13

Wyatt Lloyd will present his FPO on Thursday May 2 at 10AM in Room 402. The members of his committee are: Michael Freedman, advisor; Vivek Pai and David Andersen (CMU), readers; Jennifer Rexford and Margaret Martonosi, nonreaders. A copy of his thesis, "Stronger Consistency and Semantics for Low-latency Geo-Replicated Storage", is on display in Room 310. Everyone is invited to attend his talk.

1 0

Fwd: thesis info
by Melissa M. Lawson 25 Apr '13

25 Apr '13

Arpan Ghosh will present his MSE thesis talk on Wednesday May 1 at 3PM in Room 301 (note room!). the members of his committee are: Mung Chiang, ELE (advisor) and Andrea LaPaugh (reader). Everyone is invited to attend his talk. His abstract follows below. ------------------------------------ Abstract: Tracking the Business Pulse Using Twitter While Twitter surged to popularity soon after its creation, it took a few years to find legitimate & profitable uses for it. Just like it brought fans closer than ever to celebrities, people closer to real-time news and voters closer to presidential candidates, today it is helping define a new paradigm for consumer businesses to interact with their past, present and future customers. Twitter makes it very easy for businesses to directly ‘reach-out’ to the customers that follow them, for the purposes of announcements, promotions and advertising. The return path of the communication loop wherein a company would like to analyze customer needs, sentiment, feedback, reviews and grievances, is much harder for several reasons. Twitter as a data stream is very sparse and has a low signal to noise ratio as it continues to be dominated by tweets that are basically about nothing: personal conversations, random observations or spam. It is a slight exaggeration to classify tweets as semi-structured data, even with the presence of hashtags, due to the dynamic method of Hashtag creation and their longevity. Twitter also provides very sparse information about the users authoring tweets. This work is driven by the vision of building a tool that allows businesses to monitor, analyze and gain insights, in near real-time, of the opinion, sentiment and feedback that exists about them on social networks like twitter, analogous to what Google finance accomplishes for the financial aspect of businesses. To this end we make the following contributions: 1) A quantitative analysis of twitter usage to determine its suitability for this business-oriented use case. 2) A classifier filter out ‘irrelevant’ tweets for the aforementioned use-case. 3) An algorithm to detect trending increased activity on twitter pertaining to a business and cluster periods of high activity into logically separable stories/events in the business’ timeline. 4) An algorithm to classify people talking about a business on twitter based on their expertise/influence in the area/topic that the business specializes in.

1 1

EE Seminar - May 13, 2013, 12:30 pm, E-Quad B205 - Dr. Simon Moore
by Nicole E. Wagenblast 25 Apr '13

25 Apr '13

SeminarLogo.jpg Speaker: Dr. Simon Moore University of Cambridge Title: Does Rigorous Computer Systems Research Demand Open Source Hardware? Date: Monday, May 13, 2013 Time: 12:30 p.m. (Light lunch will be served.) Room: E-Quad, Room B205 Host: Prof. Ruby Lee Abstract: Computer systems research relies heavily on open source software like the LLVM compiler framework, operating systems like FreeBSD and Linux, para virtualisation like Xen, etc. However, much of this research is bounded by the availability of commodity hardware which provides an unnecessary fixed point in the design space exploration process. In this talk I argue that we need more open source and rigorously engineered hardware platforms to facilitate computer systems research which straddles traditional boundaries. To illustrate the point, the CHERI processor (a 64-bit RISC based capability machine soon to be open sourced) will be introduced together with observations from associated compilation (LLVM based) and operating system (FreeBSD based) research into fine grained sand boxing. By making changes all the way from the gate-level to the application-level we believe that much more secure computer systems can be constructed whilst providing a migration path for legacy systems. Bio: Simon Moore is Reader (Associate Professor in USA terms) in Computer Architecture at the University of Cambridge Computer Laboratory in England, where he undertakes research and teaching in the general area of computer design with particular interests in massively parallel secure computer architecture. Dr. Moore is the senior member of the Computer Architecture research group < http://www.cl.cam.ac.uk/research/comparch/ >. This work was undertaken in collaboration with SRI International. Portions of this work were sponsored by the Defense Advanced Research Projects Agency (DARPA) and the Air Force Research Laboratory (AFRL), under contract FA8750-10-C-0237. The views, opinions, and/or findings contained in this report are those of the author and should not be interpreted as representing the official views or policies, either expressed or implied, of the Defense Advanced Research Projects Agency or the Department of Defense.

1 0

Seminar: Prof. Josep Torrellas, UIUC. Tuesday April 30.
by Margaret Martonosi 25 Apr '13

25 Apr '13

Hello-- Prof. Josep Torrellas from UIUC will be visiting Princeton and giving a seminar on Tuesday April 30. The seminar will be from 12:30-1:30 in CS Room 302, with pizza beforehand starting at noon. Title/abstract below. I have reserved a 1-hour slot for him to meet with grad students from 2:30-3:30pm that day. That will occur in CS room 401. If you are interested in a one-on-one slot with Josep, please email me---he has a couple morning slots still available. Thanks, Margaret ----------------------------------------------------------------- Toward Programmable High-Performance Multicores Josep Torrellas University of Illinois, Urbana-Champaign http://iacoma.cs.uiuc.edu/~torrellas One of the biggest challenges facing us today is how to design parallel architectures that attain high performance while efficiently supporting a programmable environment. In this talk, I describe novel organizations that will make the next generation of multicores more programmable and higher performance. Specifically, I show how to automatically reuse the upcoming transactional memory hardware for optimized code generation. Next, I describe a prototype of Record&Replay hardware that brings program monitoring for debugging and security to the next level of capability. I also describe a new design of hardware fences that is overhead-free and requires no software support. Finally, if time permits, I will outline architectural support to detect sequential consistency violations transparently. BIO: Josep Torrellas is a Professor of Computer Science and Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign (UIUC). He is a Fellow of IEEE and ACM. He is the Director of the Center for Programmable Extreme-Scale Computing, a center funded by DARPA, DOE, and NSF that focuses on architectures for extreme energy and power efficiency. He also directs the Intel-Illinois Parallelism Center (I2PC), a center created by Intel to advance parallel computing in clients. He has made contributions to parallel computer architecture in the areas of shared-memory multiprocessor organizations, cache hierarchies and coherence protocols, thread-level speculation, and hardware and software reliability. He received a Ph.D. from Stanford University. ------------------------------------------------------------ Margaret Martonosi Hugh Trumbull Adams '35 Professor of Computer Science Princeton University http://www.princeton.edu/~mrm mrm(a)princeton.edu

1 0

V Kim FPO
by Melissa M. Lawson 24 Apr '13

24 Apr '13

Vladimir Kim will present his FPO on Wednesday May 1 at 4PM in Room 302 (note room!). The members of his committee are: Tom Funkhouser, advisor; Szymon Rusinkiewicz and Wilmot Li (Adobe), readers; David Dobkin and Adam Finkelstein, nonreaders. A copy of his thesis, "Understanding the Structure of Large, Diverse Collections of Shapes", is on display in Room 310. Everyone is invited to attend his talk.

1 0

Mark Browning MSE thesis talk
by Melissa M. Lawson 24 Apr '13

24 Apr '13

Mark Browning will present his MSE thesis talk on Tuesday April 30 at 3PM in Room 302 (note room!). The members of his committee are Adam Finkelstein, advisor and Szymon Rusinkiewicz, reader. Everyone is invited to attend his talk. His abstract follows below. ----- Original Message ----- Stylized Keyframe Animation Using Motion Field Guided Morphs Traditional 2D animation is a challenging task, because each frame must be drawn or synthesized such that it is both temporally and stylistically coherent with neighboring frames. We present a method that makes this process easier when the desired motion of the animation is available. Our method combines stylized keyframes with motion fields describing the transitions between the keyframes to produce inbetweens that: 1) are in the visual style of the keyframes, and 2) follow the given motion fields. By automatically generating the inbetweens, our system reduces the number of frames that must be drawn by up to an order of magnitude and relaxes the animator's burden of ensuring coherence. Our work builds on regenerative morphing/image melding, a recent advance in morphing that generates temporally and stylistically coherent transitions between two images. We extend this method to produce transitions that additionally respect a given motion field, and adapt it to multi-keyframe sequences. We demonstrate that our system can be used to animate fluids, apply single-frame filters to video in a temporally coherent way, and rotoscope video.

1 0

Dan Larkin general exam
by Melissa M. Lawson 24 Apr '13

24 Apr '13

Dan Larkin will present his research seminar/general exam on Tuesday April 30 at 2PM in Room 402. The members of his committee are: Bob Tarjan (advisor), Bob Sedgewick, and Moses Charikar. 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. ----- Original Message ----- TITLE Experimental Heaps: a Comparative Study of Priority Queues ABSTRACT In many areas the theory-practice gap is neglected. One such divide which has widened in the past decade is that pertaining to priority queue variants. Most implementations in use today are based on classical binary heaps and some slight variations thereof, with a few libraries implementing binomial queues or other quick-melding structures developed in the 1980s. These choices are accompanied by experimentally backed claims that more complicated, and better-in-theory structures simply run slower on real-world workloads. This hasn't seemed to deter the theory community though, as a flurry of results has been published recently establishing new structures which achieve optimal theoretical bounds while claiming in some way to be better than older variants. Whether this claimed improvement is in theoretical elegance, implementational efficiency, or pedagogical convenience, the claims have not been thoroughly tested. Furthermore, previously published experimental work is outdated or suffers from a limited scope. This work seeks to reopen the discussion on narrowing the gap. Implementing both some classic structures and several new, untested variants, we collect a variety of performance metrics across several types of workloads. We include both relatively realistic workloads and purely contrived randomized workloads, which can nevertheless help shed light on practical properties of different structures. We also show that one such contrived workload, a very natural operation sequence found in a benchmark suite, is fundamentally degenerate. We identify trends which may help provide guidance to future practitioners and theoreticians alike. READING LIST Textbook: "Introduction to Algorithms," 2nd ed., T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Structures implemented: "Algorithm 232 heapsort," J. W. J. Williams. "A data structure for manipulating priority queues," J. Vuillemin. "Fibonacci heaps and their uses in improved network optimization algorithms," M. L. Fredman, R. E. Tarjan. "The pairing heap: A new form of self-adjusting heap," M. L. Fredman, R. Sedgewick, D. D. Sleator, R. E. Tarjan. "The weak-heap family of priority queues in theory and praxis," S. Edelkamp, A. Elmasry, J. Katajainen. "The violation heap: A relaxed Fibonacci-like heap," A. Elmasry. "Quake heaps: a simple alternative to Fibonacci heaps," T. M. Chan. "Rank-pairing heaps," B. Haeupler, S. Sen, R. E. Tarjan. "Strict fibonacci heaps," G. S. Brodal, G. Lagogiannis, R. E. Tarjan. Some previous experimental studies on heaps: "Pairing heaps: experiments and analysis," J. T. Stasko, J. S. Vitter. "The influence of caches on the performance of heaps," A. LaMarca, R. E. Ladner. "Fast priority queues for cached memory," P. Sanders.

1 0

Matvey Arye general exam
by Melissa M. Lawson 23 Apr '13

23 Apr '13

Matvey Arye will present his research seminar/general exam on Monday April 29 at 12:30 PM in Room 401 (note room!). The members of his committee are: Michael Freedman (advisor), Vivek Pai, and Kai Li. 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. ----- Original Message ----- Abstract: Global-scale services generate data that is both widely distributed and big, such as system logs and video feeds. Unfortunately, traditional approaches for backhauling and analyzing this data centrally are slow and expensive, due to the high cost or availability of wide-area network bandwidth. Moreover, they require the analyst to commit to a data-collection policy upfront, making it agnostic to current and future resource conditions. Jetstream is a system that allows adaptive and real-time analysis of large, distributed data sets. It uses dispersed, structured storage to enable data collection without a fixed policy, and adapts the fidelity of collection in response to changes in network conditions. Namely, if a given user query cannot be satisfied within the available bandwidth, Jetstream automatically transforms the query, trading precision for bandwidth. One key ingredient in Jetstream’s architecture is its storage abstraction: a novel adaptation of the data cube from OLAP databases, which we use to represent aggregations and approximations of distributed data. The cube model helps us define a range of data-degradation transforms, all of which can be implemented as standard operators in a user’s query graph. The evaluation is conducted on a system stretching between clusters in Europe and North America and demonstrates the ability to maintain real-time responsiveness, save significant bandwidth through in-place aggregation and approximation, and dynamically adapt the data degradation policies based on changing resource constraints and input data rates. Current Reading List: (9 papers and 1 textbook) Principles of Computer System Design: An Introduction Saltzer and Kaashoek The Design of the Borealis Stream Processing Engine Abadi et al., CIDR 2005 Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly EuroSys, 2007 TAG: A Tiny Aggregation Service for Ad-Hoc Sensor Networks Madden et al., OSDI, 2002 A Cost-Space Approach to Distributed Query Optimization in Stream Based Overlays Shneidman et al., NetDB 2005 BlinkDB: Queries with Bounded Errors and Bounded Response Times on Very Large Data Sameer Agarwal, Aurojit Panda, Barzan Mozafari, Samuel Madden, Ion Stoica To Appear in ACM EuroSys 2013 DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views Yanif Ahmad, Oliver Kennedy, Christoph Koch, and Milos Nikolic VLDB 2012 MapReduce: Simplified Data Processing on Large Clusters Jeffrey Dean and Sanjay Ghemawat, OSDI 2004 Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals Jim Gray, et al., Data Mining and Knowledge Discover 1997. Discretized Streams: An Efﬁcient and Fault-Tolerant Model for Stream Processing on Large Clusters Matei Zaharia, et al., HotCloud, 2012.

1 0

Xin Jin general exam
by Melissa M. Lawson 23 Apr '13

23 Apr '13

Xin Jin will present his research seminar/general exam on Monday April 29 at 2:30PM in Room 401 (note room!). The members of his committee are: Jennifer Rexford (advisor), Michael Freedman, and Kai Li. 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. ----- Original Message ----- The title is "SoftCell: Taking Control of Cellular Core Networks". Existing cellular networks suffer from inflexible and expensive equipment, and complex control-plane protocols. To address these challenges, we present SoftCell, a scalable architecture for supporting fine-grained policies for mobile devices in cellular core networks. The SoftCell controller realizes high-level service polices by directing traffic over paths that traverse a sequence of middleboxes, optimized to the network conditions and user locations. To ensure scalability, the core switches forward traffic on hierarchical addresses (grouped by base station) and policy tags (identifying paths through middleboxes). This minimizes data-plane state in the core switches, and pushes all fine-grained state to software switches at the base stations. These access switches apply fine-grained rules, specified by the controller, to map all traffic to the appropriate addresses and tags. SoftCell guarantees that packets in the same connection traverse the same sequence of middleboxes in both directions, even in the presence of mobility. Our characterization of real LTE workloads, micro-benchmarks on our prototype controller, and large-scale simulations demonstrate that SoftCell improves the flexibility of cellular core networks, while enabling the use of inexpensive commodity switches and middleboxes. [1] L. L. Peterson and B. S. Davie, Computer networks: a systems approach. Morgan Kaufmann, 2007. [2] J. H. Saltzer, D. P. Reed, and D. D. Clark, “End-to-end arguments in system design,” ACM Transactions on Computer Systems (TOCS), vol. 2, no. 4, 1984. [3] M. Casado, M. J. Freedman, J. Pettit, J. Luo, N. Gude, N. McKeown, and S. Shenker, “Rethinking enterprise network control,” IEEE/ACM Trans. Networking, vol. 17, August 2009 . [4] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “OpenFlow: Enabling innovation in campus networks,” SIGCOMM Computer Communications Review, vol. 38, no. 2, 2008. [5] A. R. Curtis, J. C. Mogul, J. Tourrilhes, P. Yalagandula, P. Sharma, and S. Banerjee, “DevoFlow: Scaling flow management for high-performance networks,” in ACM SIGCOMM, August 2011 . [6] A. Greenberg, J. R. Hamilton, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. A. Maltz, P. Patel, and S. Sengupta, “VL2: A scalable and flexible data center network,” in ACM SIGCOMM, August 2009 . [7] R. Niranjan Mysore, A. Pamboris, N. Farrington, N. Huang, P. Miri, S. Radhakrishnan, V. Subramanya, and A. Vahdat, “PortLand: a scalable fault-tolerant layer 2 data center network fabric,” in ACM SIGCOMM, August 2009 . [8] D. Joseph, A. Tavakoli, and I. Stoica, “A policy-aware switching layer for data centers,” in ACM SIGCOMM, August 2008 . [9] Z. Wang, Z. Qian, Q. Xu, Z. Mao, and M. Zhang, “An untold story of middleboxes in cellular networks,” in ACM SIGCOMM, August 2011 . [10] M. Z. Shafiq, L. Ji, A. X. Liu, and J. Wang, “Characterizing and modeling internet traffic dynamics of cellular devices,” in ACM SIGMETRICS, June 2011 . [11] K.-K. Yap, R. Sherwood, M. Kobayashi, T.-Y. Huang, M. Chan, N. Handigol, N. McKeown, and G. Parulkar, “Blueprint for introducing innovation into wireless mobile networks,” in ACM VISA Workshop, August 2010 .

1 0

D Shue preFPO
by Melissa M. Lawson 18 Apr '13

18 Apr '13

David Shue will present his preFPO on Thursday April 25 at 9AM in Room 402. The members of his committee are: Michael Freedman, advisor; Jennifer Rexford and Anees Shaikh (IBM Research), readers; Vivek Pai and Margaret Martonosi, nonreaders. Everyone is invited to attend his talk. His abstract follows below. -------------------------------------------- Title: Performance Isolation and Fairness for Multi-Tenant Cloud Storage Abstract: Shared storage services enjoy wide adoption in commercial clouds. But most systems today provide weak performance isolation and fairness between tenants, if at all. Misbehaving or high-demand tenants can overload the shared service and disrupt other well-behaved tenants, leading to unpredictable performance and violating SLAs. In this thesis, we present Pisces, a system for achieving datacenter-wide per-tenant performance isolation and fairness in shared key-value storage. Today’s approaches for multi-tenant resource allocation are based either on per-VM allocations or hard rate limits that assume uniform workloads to achieve high utilization. Pisces provides per-tenant weighted fair shares (or minimal rates) of the aggregate resources over the entire service, even when different tenants’ partitions are co-located and when demand for different partitions is skewed, time-varying, or bottlenecked by different server resources. Our key insight was to decompose the system-wide fair sharing problem into a combination of four complementary mechanisms—partition placement, weight allocation, replica selection, and weighted fair queuing—that operate on different time-scales and combine to achieve per-tenant max-min fairness. While Pisces provides fairness for key-value storage systems that leverage asynchronous writes for performance, many storage systems require stronger durability guarantees and often provide rich data models that can support arbitrary computation in the form of UDF's or map/reduce functionality. Achieving predictable performance in these systems requires fine-grained per-tenant resource allocation over multiple resources (e.g network, disk, and CPU). In the second part of this thesis, w e generalize and extend the PIsces per-node scheduling model with Libra, a multi-resource allocation library for building predictable shared services.

1 0