Quick links

Talk

Programming Parallel Accelerators at the \

Date and Time
Thursday, May 20, 2010 - 3:30pm to 4:30pm
Location
Computer Science 302
Type
Talk
Speaker
Ben Ylvisaker, from University of Washington
Parallel accelerators like FPGAs and GPUs have been shown to provide huge performance and energy efficiency advantages on a wide range of applications, from video coding to scientific simulation to wireless communication. However, accelerators are still harder to program than conventional processors, which is almost certainly limiting their use. I advocate for "C level" programming of accelerators, and in this talk I will describe several projects I have worked on to enable that. Specifically, I will discuss a new approach to pipelining complex loops, probabilistic auto-tuning, and relaxed I/O ordering operational semantics.

Ben Ylvisaker is almost finished being a graduate student at the University of Washington. There he is advised by Carl Ebeling and Scott Hauck, and works in the Mosaic group, which does research on architectures, tools and applications for parallel accelerators. Before coming to UW, he earned a master's degree at Carnegie Mellon, where he also got an undergrad degree a few years earlier. Interspersed between the academic adventures, Ben has worked at a number of startup companies, none of which exist anymore.

Data Aware Scheduling for Multi-threaded Applications on SMP Machines

Date and Time
Tuesday, February 16, 2010 - 12:30pm to 1:30pm
Location
Computer Science 402
Type
Talk
Host
Andrea LaPaugh
Extensive use of multi-threaded applications that run on SMP machines justifies modifications in thread scheduling algorithms to consider threads' characteristics in order to improve performance. Current schedulers (e.g. in Linux, AIX) avoid migrating tasks between CPUs unless absolutely necessary. Unwarranted data cache misses occur when tasks that share data run on different CPUs, or are far apart time-wise on the same CPU. This work presents an extension to the Linux scheduler that exploits inter-task data relations to reduce data cache misses in multi-threaded applications running on SMP platforms, thus improving runtime, memory throughput, and energy consumption. Our approach schedules the tasks to the CPU that holds the relevant data rather than to the one with highest affinity. We observed improvements in CPU time and throughput on several benchmarks. For the Chat benchmark the improvement in CPU time and cache misses is over 30% on average.

Dr. Pinter was a research specialist at MIT before receiving her Ph.D. in computer science from Boston University. Following her Ph. D., she joined the faculty of the Electrical Engineering Department of Technion (Israel), remaining for twelve years before joining the IBM research lab in Haifa as member of research staff. She recently left IBM to become CTO of Rascal Software Security. She is also an adjunct faculty member of the Department of Computer Science, Haifa University, supervising graduate student research.

A Universal Calculus for Stream Processing Languages

Date and Time
Tuesday, May 18, 2010 - 11:00am to 12:00pm
Location
Computer Science 302
Type
Talk
Speaker
Robert Soule, from New York University
Stream processing applications such as algorithmic trading, MPEG processing, and web content analysis are ubiquitous and essential to business and entertainment. Language designers have developed numerous domain-specific languages that are both tailored to the needs of their applications, and optimized for performance on their particular target platforms. Unfortunately, the goals of generality and performance are frequently at odds, and prior work on the formal semantics of stream processing languages does not capture the details necessary for reasoning about implementations. This talk presents Brooklet, a core calculus for stream processing that allows us to reason about how to map languages to platforms and how to optimize stream programs. We translate from three representative languages, CQL, StreamIt, and Sawzall, to Brooklet, and show that the translations are correct. We formalize three popular and vital optimizations, data-parallel computation, operator fusion, and operator re-ordering, and show under which conditions they are correct. Language designers can use Brooklet to specify exactly how new features or languages behave. Language implementors can use Brooklet to show exactly under which circumstances new optimizations are correct. In on-going work, we are developing an intermediate language for streaming that is based on Brooklet. We are implementing our intermediate language on System S, IBM's high-performance streaming middleware.

This work is based upon the paper "A Universal Calculus for Stream Processing Languages" by Robert Soule, Martin Hirzel, Robert Grimm, Buğra Gedik, Henrique Andrade, Vibhore Kumar, and Kun-Lung Wu, in the Proceedings of ESOP 2010.

Robert Soule is a Ph.D. candidate at New York University, working with Professor Robert Grimm, and a research co-op in the Data Intensive Systems and Analytics Group at IBM T. J. Watson Research Center, under the guidance of Martin Hirzel. His research interests are in distributed systems, and language support for building systems.

Robust and Efficient TCAM-Based Packet Classification

Date and Time
Wednesday, May 19, 2010 - 12:30pm to 1:30pm
Location
Computer Science 402
Type
Talk
Speaker
Dr. David Hay, from Columbia
Host
Jennifer Rexford
Ternary content-addressable memory (TCAM) devices are increasingly used for performing high-speed packet classification, one of the most challenging tasks in router design today. TCAM enables parallel matching of a key against all TCAM entries, which consist of ``0'',``1'' and ``*'' (don't care) bits, in O(1) time. In this talk we tackle two challenges related to these devices. First, we present PEDS, a novel parallel error detection scheme that locates the erroneous entries in a TCAM device. Time permitting, we will also discuss how one can use TCAM to boost memory-efficiency of Aho-Corasick-like Deep Packet Inspection (DPI) algorithms; this is done by efficiently encoding transitions into prefixes and applying Longest Prefix Matching rule.

These works appear in INFOCOM 2010 and INFOCOM 2009 (runner-up to best paper) and in ACM/IEEE Transactions on Networking. Joint work with Anat Bremler-Barr (IDC), Yaron Koral (IDC), Danny Hendler (BGU) and Ron M. Roth (Technion).

David Hay received his BA (summa cum laude) and PhD degree in computer science from the Technion - Israel Institute of Technology in 2001 and 2007, respectively. He is currently a post-doctoral research scientist at the department of electrical engineering, Columbia University, NY, USA. His main research interests are algorithmic aspects of high-performance switches and routers; in particular: Packet classification, QoS provisioning and competitive analysis. Between 1999-2002, David Hay was with IBM Haifa Research Labs. During summer 2006, he was interning at the Data Center Business Unit of Cisco Systems, San Jose. He was also a post-doc fellow at the department of computer science, Ben Gurion University of the Negev, Israel (2007-2008), and at the departmenty of electrical engineering, Politecnico di Torino, Italy (2008-2009). In October 2009, he is expected to join the school of Computer Science of the Hebrew University of Jerusalem, Israel.

Exploring the Stratified Shortest Paths Problem

Date and Time
Tuesday, May 4, 2010 - 3:00pm to 4:00pm
Location
Computer Science 302
Type
Talk
Speaker
Tim Griffin, from University of Cambridge
Host
Jennifer Rexford
The Border Gateway Protocol (BGP) is the keystone among Internet routing protocols as it maintains connectivity in the entire global Internet. BGP has evolved into a rather mysterious beast. Theoretical work over the last ten years has made it clear that BGP represents something novel in the context of routing protocols: BGP does not compute globally optimal paths, but only locally optimal paths. The talk will explain how this exotic type of routing can be understood in an algebraic setting. The Stratified Shortest-Paths Problem (SSPP) is presented as a very simple example of this type of algebra. The SSPP is meant to capture the essence of a BGP-like path problem without BGP's many operational complexities.

Tim Griffin is a Senior Lecturer and Fellow at King's College, University of Cambridge. His research interests include network protocol design and analysis, with a focus on Internet routing protocols.

Network Virtualization applied to the Network of a Communication Service Provider for Enabling Novel Services in Vertical Sectors

Date and Time
Monday, May 17, 2010 - 1:30pm to 2:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
Talk
Speaker
Dr. Sanjoy Paul, from Infosys, Associate Vice President
Host
Jennifer Rexford
Communication technology has advanced significantly over the last decade enabling people to communicate anytime from anywhere using a multiplicity of devices. However, the power of this advancement in communication technology has hardly been leveraged in traditional services industry. Specifically, the vertical service providers, such as the Health Care industry, the Banking industry, the Education industry, and others who require network-based services to efficiently conduct their business reducing their operational expenses, and to provide novel value-added services to their customers generating additional revenue, have hardly been able to leverage the power of the network to their advantage. In the talk, I will describe several applications from the services industry that can be built on a platform (referred to as Network as a Service or NaaS platform) based on the concept of network virtualization and shows how various parties involved in providing the services are economically incentivized to make them feasible in real life.

The NaaS platform enables Communication Service Providers (CSPs) to work collaboratively with Vertical Service Providers (VSPs) to offer novel services leveraging their existing network infrastructure through the techniques of network virtualization. This solution enables CSPs to generate new revenue without additional capital expenditure, and in addition, also enables VSPs to generate additional revenue via novel value-added service offerings to their customers without incurring any capital expenditure either. Thus, this model of offering services provides a win-win value proposition to both CSPs as well as to VSPs.

NaaS Platform is being built at Infosys Technologies Limited. In course of my presentation, I'll describe a high-level architecture of the platform and discuss how various functional blocks in the architecture are used synergistically to deliver a novel service called On Demand Health Care (ODHC).

Sanjoy Paul (sanjoy_paul@infosys.com) is Associate Vice President, General Manager-Research and Head of Convergence Lab at Infosys Technologies Limited where he heads research and innovation in the field of Communications, Media and Entertainment. Prior to that, he was a Research Professor at WINLAB, Rutgers University, and Founder of RelevantAd Technologies Inc. Before that Sanjoy spent five years as the Director of Wireless Networking Research at Bell Labs, Lucent Technologies, and as the CTO of two start-up companies (Edgix and WhenU) based in New York. In a previous tenure at Bell Labs as a Distinguished Member of Technical Staff, Sanjoy was the chief architect of Lucent's IPWorX Caching and Content Distribution product line. Sanjoy has authored a book on Multicasting, published over 100 papers in International Journals and refereed Conference Proceedings, authored over 80 US patents (28 granted, 50+ pending), and is the co-recipient of 1997 William R. Bennett award from IEEE Communications Society for the best original paper in IEEE/ACM Transactions on Networking. He holds a Bachelor of Technology degree from IIT Kharagpur, India, an M.S and a Ph.D. degree from the University of Maryland, College Park, and an MBA from the Wharton Business School, University of Pennsylvania. Sanjoy is a Fellow of IEEE and a Member of the ACM.

SPAIN: COTS Data-Center Ethernet for Multipathing over Arbitrary Topologies

Date and Time
Wednesday, May 5, 2010 - 11:00am to 12:00pm
Location
Computer Science 402
Type
Talk
Speaker
Jeff Mogul, HP Labs
Host
Jennifer Rexford
Operators of data centers want a scalable network fabric that supports high bisection bandwidth and host mobility, but which costs very little to purchase and administer. Ethernet almost solves the problem -- it is cheap and supports high link bandwidths -- but traditional Ethernet does not scale, because its spanning-tree topology forces traffic onto a single tree. Many researchers have described "scalable Ethernet" designs to solve the scaling problem, by enabling the use of multiple paths through the network. However, most such designs require specific wiring topologies, which can create deployment problems, or changes to the network switches, which could obviate the commodity pricing of these parts.

In this talk, I will describe SPAIN ("Smart Path Assignment In Networks"). SPAIN provides multipath forwarding using inexpensive, commodity off-the-shelf COTS) Ethernet switches, over arbitrary topologies. SPAIN pre-computes a set of paths that exploit the redundancy in a given network topology, then merges these paths into a set of trees; each tree is mapped as a separate VLAN onto the physical Ethernet. SPAIN requires only minor end-host software modifications, including a simple algorithm that chooses between pre-installed paths to efficiently spread load over the network. We demonstrate SPAIN's ability to improve bisection bandwidth over both simulated and experimental data-center networks.

Joint work with Jayaram Mudigonda and Praveen Yalagandula, and with Mohammad Al-Fares (UCSD)

Haggle: Content-Centric Opportunistic Communication for Mobile Phones

Date and Time
Friday, April 9, 2010 - 2:00pm to 3:00pm
Location
Computer Science 402
Type
Talk
Speaker
Erik Nordstrom, from Princeton University, Computer Science Department
Host
Jennifer Rexford
Today, mobile phones are increasingly used for content-centric communication, whereby users access and share content with each other (e.g., pictures on Facebook). However, content sharing is limited to infrastructure networks and legacy Internet technologies are ill suited for content-centric communication. Moreover, the Internet protocols and APIs do not work well in highly mobile and disruptive environments, where intermittent connectivity is the norm rather than the exception. These deficiencies make it is cumbersome, or even impossible, to share content directly between mobile phones, leading to high stress on existing infrastructure and high costs for the consumer, while putting limitations on the possibilities for developing new and innovative applications.

In this talk, I will present Haggle, a novel network architecture built from the ground up to support opportunistic content-centric communication directly between mobile phones. Haggle addresses content rather than hosts, which makes it irrelevant from where a user receives a content item. The content-centric communication is driven by a novel distributed search-based resolution scheme, which draws inspiration from online search engines. The search scheme resolves the mappings between the content and its interest group, i.e., the nodes that have an interest in the content. Search has the benefit of ranking, and therefore provides a natural limitation and ordering mechanism for content dissemination. This means that content, in general, has a higher likelihood of being disseminated if there is a high interest in it in the network.

After the talk, I will demonstrate Haggle using a visualization tool that shows how photos taken with a phone's camera are shared with other mobile phones or devices.

Acting Locally: Civic Media and the Information Needs of Communities

Date and Time
Thursday, February 18, 2010 - 4:30pm to 6:00pm
Location
Sherrerd Hall 101
Type
Talk
Speaker
Christopher Csikszentmihalyi
Reception immediately following 3rd Floor Atrium

The MIT Center for Future Civic Media is a multidisciplinary research group that develops sociotechnical systems to strengthen geographic communities. Working in urban and rural communities, from the US to Peru, our civic projects focus on a community's ownership of its own information and the ability to turn that information into constructive social change. This lecture will give an overview of recent activity at the Center, and cover lessons learned in the process of fieldwork and deployment.

Chris Csikszentmihalyi directs the MIT Center for Future Civic Media, dedicated to developing technologies that strengthen communities. He also founded and directs the Media Lab's Computing Culture group, which works to create unique media technologies for cultural applications. He has worked in the intersection of new technologies, media, politics, and the arts for 16 years, lecturing, showing new media work, and presenting installations on five continents and one subcontinent.

The Intellectual Prehistory of Computing

Date and Time
Thursday, February 11, 2010 - 4:30pm to Wednesday, December 16, 2009 - 6:00pm
Location
Computer Science Small Auditorium (Room 105)
Type
Talk
Host
Kenneth Steiglitz
Hellenic Studies has invited Professor Christos Papademetriou, Computer Science Division, University of California, Berkeley, to give a lecture entitled "Logicomix" with a reception to follow in the gallery. Hosts: Dimitri Gondicas and Ken Steiglitz
Follow us: Facebook Twitter Linkedin