December 2008 - talks - lists.cs.princeton.edu

H Kim general exam
by Melissa Lawson 31 Dec '08

31 Dec '08

Hanjun Kim will present his research seminar/general exam on Tuesday January 6 at 2PM in Room 402. The members of his committee are: David August (advisor), Margaret Martonosi, and Doug Clark. 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. --- Software Multithreaded Transactional Memory Abstract As chip multiprocessors have become ubiquitous, programs must be parallelized to effectively use computing resources. Recently proposed techniques, such as those by Bridges et al., by Theis et al., and by Tian et al., have demonstrated significant performance improvement by partitioning loops into long-running threads organized into a pipeline. Various studies have shown that speculation is the key to unlocking the full potential of these techniques for general purpose applications. Speculative pipelined multi-threading needs multi-threaded transactional memory that supports atomic units of code across multiple threads, but most transactional memory proposals cannot be used because they only support single-threaded atomic units. Multi-threaded transactions (MTX) address this problem, but they require expensive hardware support as currently proposed. Tian et al. offer CorD, a software technique which runs on existing hardware. CorD's limitations, that it does not support loops that speculatively write pointer addresses and that it only supports certain patterns of parallelism, restrict its utility. This work proposes a software MTX (SMTX) system that combines the applicability of hardware MTX with CorD's performance on real hardware. Across a set of sequential applications, SMTX yields a geomean speedup of 353% on a real dual 4-core CMP (8 cores in total) machine running speculatively parallelized applications. Reading List Books: [1] Modern Compiler Implementation in ML, by A. W. Appel, Cambridge University Press, 1998 [2] Computer Architecture: A Quantitative Approach 4th Edition, by J. L. Hennessy & D. A. Patterson, Morgan Kaufmann, 2006 Paper: [3] K. Agrawal, J. Fineman, and J. Sukha. Nested parallelism in transactional memory. In Proceedings of the Second ACM SIGPLAN Workshop on Transactional Computing, August 2007. [4] M. J. Bridges, N. Vachharajani, Y. Zhang, T. Jablin, and D. I. August. Revisiting the sequential programming model for multi-core. In Proceedings of the 40th Annual ACM/IEEE International Symposium on Microarchitecture, December 2007. [5] J. Giacomoni, T. Moseley, and M. Vachharajani. FastForward for efficient pipeline parallelism: a cache-optimized concurrent lock-free queue. In PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, 2008. [6] L. Hammond, B. D. Carlstrom, V. Wong, M. Chen, C. Kozyrakis, and K. Olukotun. Transactional coherence and consistency: Simplifying parallel hardware and software. IEEE Micro, 24(6), Nov-Dec 2004. [7] M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. In Proceedings of the 20th Annual International Symposium on Computer Architecture, 1993. [8] L. Lamport. Specifying concurrent program modules. ACM Trans. Program. Lang. Syst., 5(2):190-222, 1983. [9] S. Papadimitriou and T. C. Mowry. Exploring thread-level speculation in software: The effects of memory access tracking granularity. Technical report, 2001. [10] E. Raman, G. Ottoni, A. Raman, M. Bridges, and D. I. August. Parallel-Stage Decoupled Software Pipelining. In Proceeding of the 2008 International Symposium on Code generation and Optimization, April 2008. [11] R. Rangan, N. Vachharajani, M. Vachharajani, and D. I. August. Decoupled software pipelining with the synchronization array. In Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, September 2004. [12] J. G. Steffan, C. B. Colohan, A. Zhai, and T. C. Mowry. A scalable approach to thread-level speculation. In Proceedings of the 27th International Symposium on Computer Architecture, June 2000. [13] H. Sutter. The free lunch is over: A fundamental turn toward concurrency in software. Dr. Dobb's Journal, 30(3), 2005. [14] W. Thies, V. Chandrasekhar, and S. Amarasinghe. A practical approach to exploiting coarse-grained pipeline parallelism in C programs. In Proceedings of the 40th Annual ACM/IEEE International Symposium on Microarchitecture, 2007. [15] C. Tian, M. Feng, V. Nagarajan, and R. Gupta. Copy or discard execution model for speculative parallelization on multicores. In Proceedings of the 41st International Symposium on Microarchitecture, November 2008. [16] N. Vachharajani, R. Rangan, E. Raman, M. J. Bridges, G. Ottoni, and D. I. August. Speculative decoupled software pipelining. In Proceedings of the 16th International Conference on Parallel Architectures and Compilation Techniques, September 2007.

1 0

1-2pm Fri Dec 12 talk in B-205 on wireless interference by Ramakrishna Gummadi
by Jennifer Rexford 12 Dec '08

12 Dec '08

Highly recommended for folks interested in randomized algorithms, networking, or systems. Will also include a demo of their FPGA-based programmable wireless system... Speaker: Dr. Ramakrishna Gummadi, MIT Title: Interference rendered significantly harmless Location: B205 in the E-Quad (note: talk in ELE wing of E-Quad, *not* in CS building) Date/time: 1-2pm Friday December 12 Abstract: The throughput of existing wireless networks is often limited by interference. One fundamental reason is that the current designs are constrained by a "one-transmission-at-a-time" model at the link layer and a fixed-width spectrum allocation at the physical layer. We present a new wireless design that exploits traffic burstiness and node heterogeneity, thereby improving concurrency and spectrum usage. The main challenge is the unmanaged nature of many wireless networks such as 802.11 and mesh, which makes centralized resource allocation impractical. We show through analysis and implementation that simple randomized allocation policies can overcome this challenge, and improve throughput by 2x or more. This work is joint with Rabin Patra, Hari Balakrishnan and Eric Brewer. Bio: Ramakrishna Gummadi is a post-doc at the MIT Computer Science and Artificial Intelligence Laboratoray (CSAIL). He obtained his B.Tech. from IIT-Madras, M.S. from UC Berkeley and Ph.D. from USC, all in Computer Science. His dissertation was about reliable and efficient programming languages for sensor networks. He is interested in building scalable and reliable systems and networks based on sound principles. His awards include a UC Regents Graduate Fellowship, a best paper awarded out of all 2001 Journal of Computer Networks papers, a best poster/demo award at SenSys 2004, and an award at the ACM Student Research Competition (SRC) held at PLDI 2007.

1 0

Distinguished colloquium today: Eva Tardos
by Sanjeev Arora 11 Dec '08

11 Dec '08

In Room 105 of CS Building, 4:30pm. --------- Games in Networks: the price of anarchy and learning Eva Tardos Cornell Network games play a fundamental role in understanding behavior in many domains, ranging from communication networks through markets to social networks. Such networks are used, and also evolve due to selfish behavior of the users and owners. In light of these competing forces, it is surprising how efficient these networks are. It is an exciting challenge to understand the operation and success of these networks in game theoretic terms: what principles of interaction lead selfish participants to form such efficient networks? We will focus on congestion games, and study the degradation of quality of solution caused by the selfish behavior of users. We model users as learning algorithms, and show that natural learning behavior can avoid bad outcomes predicted by the price of anarchy in atomic congestion games such as the load-balancing game. We use tools from the theory of dynamical systems and algebraic geometry to show when players use a class of natural learning algorithms the distribution of play converges to the set of weakly stable equilibria, and that the set of weakly stable equilibria are the pure Nash equilibria with probability 1 when congestion costs are selected at random independently on each edge (from any monotonically parametrized distribution). The talk is a survey and self-contained. ----- About the speaker: Eva Tardos is a Professor of Computer Science at Cornell University where she is currently chair. Her research is in Algorithm Design and Algorithmic Game Theory. Algorithmic game theory is an emerging new area of designing systems and algorithms for selfish users. She is a winner of the Fulkerson Prize and the Dantzig Prize.

1 0

[Fwd: Lunch 'n Learn today at noon: Computational Intractability]
by Scott Karlin 10 Dec '08

10 Dec '08

-------- Original Message -------- Subject: Lunch 'n Learn today at noon: Computational Intractability Date: Wed, 10 Dec 2008 09:39:42 -0500 From: Jon Edwards <jedwards(a)Princeton.EDU> Reply-To: Jon Edwards <jedwards(a)Princeton.EDU> To: EOS-ANNOUNCE(a)Princeton.EDU Lunch 'n Learn banner Wednesday, December 10, 12:00 noon Computational Intractability: A Barrier for Computers, Man, and Science Sanjeev Arora Computers are increasingly important in society as well as every area of scholastic inquiry. Nevertheless, there appear to be tasks that are infeasible for current computers. In recent decades, we have begun to develop an understanding of what makes computational tasks "intractable" not just for current computers but for all foreseeable computers. This has implications for many scientific fields. The study of intractability can also yield positive benefits, such as cryptographic schemes, secure e-voting, and e-commerce. Recently the National Science Foundation decided to fund an "Expedition" center headquartered at Princeton that will study computational intractability. I will give an overview of both the field and what our center is trying to accomplish. *Sanjeev Arora* is a Professor of Computer Science and the Director of the Center for Theoretical Computer Science and the Director of the Center for Intractability. Most Lunch 'n Learn presentations take place in *Frist Multipurpose Room B*. Cookies and beverages are provided. /Bring your lunch and learn! / *Additional news:* facebookFacebook users take note. Lunch 'n Learn now has a Facebook page <http://www.facebook.com/pages/Princeton-NJ/Lunch-n-Learn-Information-Techno…>. Become a fan to keep up with our activities. For other Education and Outreach services offerings, visit our web site <http://www.princeton.edu/%7Eeos>.

1 0

Talk on Thursday -12/11/2008
by Ginny Hogan 09 Dec '08

09 Dec '08

Eva Tardos, Cornell University will present her Talk. "Games in Networks: the price of anarchy and learning"- at 4:15pm Computer Science Room 105.

1 0

H Ringberg preFPO - correction
by Melissa Lawson 08 Dec '08

08 Dec '08

The committee should be; Jennifer Rexford, Mike Freedman, Nicholas Duffield (AT&T), Rob Calderbank, and Brian Kernighan. --Melissa

1 0

H Ringberg preFPO
by Melissa Lawson 08 Dec '08

08 Dec '08

Haakon Ringberg will present his preFPO on Friday December 12 at 10AM in Room 302. The members of his committee are: Jennifer Rexford, advisor; Nicholas Duffield (AT&T), Mike Freedman, Vivek Pai, and Rob Calderbank. Everyone is invited to attend his talk. His abstract follows below. ---------------------------------------------- Unwanted traffic is a major concern in the Internet today. The algorithms that attempt to identify this unwanted traffic are called network anomaly detectors, and their task is challenging in part because many network attacks mimic the behavior of normal traffic. The victims of these attacks should therefore collaborate by correlating their attack data, under the assumption that a given malicious host is likely to affect more than one victim. The major obstacle to such collaboration is that the corporations who manage these networks are hesitant to openly share information about the hosts (customers) that use their services. In this thesis, we propose and evaluate the feasibility of an architecture for privacy-preserving collaborative anomaly detection. First, we study the potential gain from collaboration on traces from operational networks. We do this by calculating the fraction of detected network anomalies (viz., IP scans, port scans, and DoS attacks) that could have been mitigated in these traces if some subset of the victim hosts collaborated to block attackers. Second, we propose and evaluate the efficiency of a novel cryptographic protocol that allows victims to collaborate to identify the hosts sending unwanted traffic. The protocol allows each participant to submit a set of IP addresses that they suspect might be engaging in said activity. The protocol preserves privacy because it never reveals who suspected whom, and a submitted IP address is only revealed when more than n participating networks suspect it. Finally, we close the loop by evaluating the feasibility of making a commonly-used single vantage-point anomaly detector faster and more scalable. Specifically, we propose and evaluate a system that leverages machine learning to bring the classification intelligence of the signature- and packet-based intrusion detection system (IDS) Snort to the IP flow realm. We demonstrate that our system can effectively learn to classify many Snort alarms on IP flows. In sum, the thesis presents a complete collaborative anomaly detection architecture, from the high-confidence detection of unwanted traffic at single networks to a privacy-preserving protocol that allows these networks to collectively increase their confidence in their detections.

1 0

Talk Today 4:15 - COS 105
by Ginny Hogan 03 Dec '08

03 Dec '08

Vladlen Koltun, Stanford University will present his talk, "Computer Graphics as a Telecommunication Medium " ,at 4:15pm today Computer Science Room 105 - Tea will be at 3:30 -

1 0

Colloquium: Vladlen Koltun on Wednesday, Dec 3, 4:00-5:00pm
by Michael J. Freedman 01 Dec '08

01 Dec '08

Hi, This Wednesday at 4:00pm, Vladlen Koltun from Stanford University will be giving the department colloquium. The talk is located in the small auditorium (CS Room 105). I looking forward to seeing you there. Thanks, --mike Abstract -------- I will argue that the primary contribution of computer graphics in the next decade will be to enable richer social interaction at a distance. The integration of real-time computer graphics and large-scale distributed systems will give rise to a rich telecommunication medium, currently referred to as virtual worlds. The medium provides open-ended face-to-face communication among ad-hoc groups of people in custom environments and decouples shared spatial experiences from geographic constraints. I will outline a research agenda for enabling and advancing the medium. The three driving themes are system architectures, content creation, and interaction. System architectures aim to support the medium at planetary scale. Content creation aims to enable untrained participants to create high-quality three-dimensional content. Interaction aims to make virtual world communication seamless and natural. I will demonstrate preliminary results in each area. Bio: Vladlen Koltun is an Assistant Professor of Computer Science at Stanford University. He directs the Virtual Worlds Group, which explores how scalable virtual world systems can be built, populated, and used. His prior work in computational geometry and theoretical computer science was recognized with the NSF CAREER Award, the Alfred P. Sloan Fellowship, and the Machtey Award.

1 0

1:30-2:30pm Fri Dec 5 talk on Effective Diagnosis of Routing Disruptions from End Systems
by Jennifer Rexford 30 Nov '08

30 Nov '08

Invited talk, note the unusual room (CS 102). Please let me know if you would like to meet with Morley Mao while she is here. Speaker: Professor Morley Mao, U. Michigan Title: Effective Diagnosis of Routing Disruptions from End Systems Date/time: 1:30-2:30pm Friday December 5 Room: 102 in the CS building Abstract: Internet routing events are known to introduce severe disruption to application performance. So far effective diagnosis of routing events has relied on proprietary ISP data feeds, resulting in limited ISP-centric views not easily accessible by customers or other ISPs. In this work, we propose a novel approach to diagnosing significant routing events associated with any large networks from the perspective of end systems. Our approach is based on scalable, collaborative probing launched from end systems and does not require proprietary data from ISPs. Using a greedy scheme for event correlation and root cause inference, we can diagnose both interdomain and intradomain routing events. Unlike existing methods based on passive route monitoring, our approach is able to measure the impact of routing events on end-to-end network performance as well. We demonstrate the effectiveness of our approach by studying five large ISPs over more than three and half months. We validate the accuracy of our approach by comparing with the existing ISP-centric method and with events reported on NANOG mailing lists. Our work is the first to scalably and accurately diagnose routing events associated with large networks purely from end systems. Bio: Z. Morley Mao is an assistant professor of Computer Science and Engineering at the University of Michigan. Morley received her Ph.D., M.S., and B.S. from the University of California at Berkeley. She is a recipient of the NSF CAREER award in 2007, an IBM Faculty Award in 2008, and was recently named the Morris Wellman Faculty Development Professor. Her research interests include network measurements, routing protocols, distributed systems, and network security.

1 1