- talks - lists.cs.princeton.edu

Distinguished Colloquium Speaker Mark Hill Tues Nov 30
by Nicole E. Wagenblast 29 Nov '10

29 Nov '10

Amdahl's Law in the Multicore Era Mark Hill, University of Wisconsin- Madison Tuesday November 30, 2010, 4:30pm Computer Science Small Auditorium, CS105 Over the last several decades computer architects have been phenomenally successful turning the transistor bounty provided by Moore's Law into chips with ever increasing single-threaded performance. During many of these successful years, however, many researchers paid scant attention to multiprocessor work. Now as vendors turn to multicore chips, researchers are reacting with more papers on multi-threaded systems. While this is good, we are concerned that further work on single-thread performance will be squashed. To help understand future high-level trade-offs, we develop a corollary to Amdahl's Law for multicore chips [Hill& Marty, IEEE Computer 2008]. It models fixed chip resources for alternative designs that use symmetric cores, asymmetric cores, or dynamic techniques that allow cores to work together on sequential execution. Our results encourage multicore designers to view performance of the entire chip rather than focus on core efficiencies. Moreover, we observe that obtaining optimal multicore performance requires further research BOTH in extracting more parallelism and making sequential cores faster. This talk is based on an HPCA 2008 keynote address. Mark D. Hill (http://www.cs.wisc.edu/~markhill) is professor in both the Computer Sciences Department and the Electrical and Computer Engineering Department at the University of Wisconsin-Madison, where he also co-leads the Wisconsin Multifacet project with David Wood. He earned a Ph.D. from the University of California, Berkeley. He is an ACM Fellow and a Fellow of the IEEE. His past work ranges from refining multiprocessor memory consistency models to developing the 3C model of cache behavior (compulsory, capacity, and conflict misses).

1 1

C Bienia FPO
by Melissa Lawson 29 Nov '10

29 Nov '10

Chris Bienia will present his FPO on Thursday December 2 at 9AM in Room 402. The members of his committee are: Kai Li, advisor; J.P. Singh and David August, readers; Jennifer Rexford and Margaret Martonosi, nonreaders. A copy of his thesis, "Benchmarking Modern Multiprocessors", is on display in room 310. Everyone is invited to attend his talk.

1 0

W Dong preFPO
by Melissa Lawson 29 Nov '10

29 Nov '10

Wei Dong will present his preFPO on Thursday December 2 at 2PM in Room 402. The members of his committee are: Kai Li, advisor; Moses Charikar and Andrea LaPaugh, readers; Tom Funkhouser and Olga Troyanskaya, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ---------------------------------- Title: High-Dimensional Similarity Search for Large Datasets Images and other non-text feature-rich data are predominant in today's exponentially growing digital universe. How to organize such data at large scale for efficient content-based search is an increasingly important problem, which remains open after two decades of intensive research. The challenge is that feature-rich data are usually of high dimensionality, and the dimensionality curse indicates that as dimensionality grows, any search strategy is subject to an increasingly large candidate set (the portion of the dataset necessary to be examined), and eventually degenerate to brute-force scan. This thesis approaches the problem by addressing two aspects of candidate set size: the number of items and the size of each item. Specifically, we made the following contributions. First, we substantially improved Locality-Sensitive Hashing, the state of the art of high-dimensional similarity search. We developed an accurate performance model for automatic parameter tuning with sampled data, and a method to improve search results with an offline computed K-Nearest Neighbor (K-NN) graph. Second, we developed compact data representations optimized for similarity search tasks, where we only need to approximate distances in a roughly fixed small range. Further more, with an asymmetric distance estimation method to exploit the uncompressed query data, we are able to further compress the indexed dataset. Third, we developed an efficient method for offline K-NN graph construction, i.e. jointly solving K-NN search for every point, based on the idea that a K-NN graph approximation can be improved by comparing each point to its neighbors' neighbors. Finally, we demonstrated some of the proposed techniques by building a large-scale near-duplicate image search system, which serves more than 70 million web images on a single commodity server and responses to queries within a few seconds.

1 0

Vapnik talk, mon, 11/29, 3pm, CS sm. aud.
by Robert Schapire 22 Nov '10

22 Nov '10

Vladimir Vapnik, who is renowned for his pioneering and extremely high-impact work on machine learning, will give a talk this coming Monday, November 29, at 3pm in the small auditorium (room 105) of the Computer Science building. See the abstract below. A NEW LEARNING PARADIGM: LEARNING WITH TEACHER Vladimir Vapnik Abstract. The existing machine learning paradigm considers a simple scheme: given a set of training examples find in a given collection of functions the one that in the best possible way approximates the unknown decision rule. In such a paradigm a teacher does not play any role. In human learning, however, the role of a teacher is very important: along with examples a teacher provides students with explanations, comments, comparisons, and so on. In this talk I will introduce elements of human teaching in machine learning. I will introduce an advanced learning paradigm called learning using privileged information (LUPI), where at the training stage a teacher gives some additional information about training examples. This privileged information will not be available during test stage. I will consider LUPI paradigm for support vector machine type of algorithms and demonstrate big superiority of the advanced learning paradigm over classical one. The new learning paradigm is general; it can be apply to almost any learning problem.

2 1

M Suchara preFPO
by Melissa Lawson 16 Nov '10

16 Nov '10

Martin Suchara will present his preFPO on Tuesday November 23 at 10AM in Room 402. The members of his committee are: Jennifer Rexford, advisor; Mung Chiang (ELE) and Gordon Wilfong (Bell Labs), readers; Mike Freedman and Ed Felten, nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------------------------- Reliable Internet Routing The network routing system is a critical infrastructure that enables communication of hosts connected to the Internet. Despite its importance, the design is vulnerable to hardware faults, routing policy misconfigurations, as well as malicious attacks. Each of these vulnerabilities may either cause loss of availability, or degrade network performance. This thesis provides several complementary mechanisms that address these reliability, security and performance concerns. The design of each of these mechanisms takes into account practical considerations, such as the incentives for adoption, ease of deployment, or computational complexity of the required calculations. Preventing BGP Route Oscillations The Internet consists of tens of thousands of separately administered autonomous systems with independently chosen routing policies. Policy interactions may cause permanent route oscillations in the interdomain routing protocol (BGP), leading to degraded network performance as well as unnecessary message-processing overhead. The first step towards only using "safe" policies is to understand the exact conditions when these policies guarantee convergence, and to provide an efficient algorithm that allows such safety verification. To that end, we develop DPVP, a new theoretical model of routing that is more amenable to analysis. DPVP includes several BGP implementation features that have been omitted in the previous theoretical models. In particular, our model allows "spurious" announcements of less-preferred routes that may be caused by a variety of mechanisms integrated in BGP. In this new, more robust model, we derive the necessary and sufficient condition for safety, which furthermore admits an efficient algorithm for checking BGP safety in most practical circumstances -- two complementary results that have been elusive in the past decade's worth of classical studies of BGP convergence in more simple models. Securing BGP against Attacks Integrity of the interdomain routing system is threatened by compromised routers which announce address prefixes that they do not own. Deployment of the many countermeasures that have been proposed in the past decade is complicated by the requirement for cooperation of all of the independently administered autonomous systems. Instead of requiring unilateral cooperation, we argue that small groups should be the basis for securing interdomain routing, and we offer a new design where routing is secured by a few (e.g., 5--10) participating autonomous systems. We conduct extensive simulations and identify conditions for small groups to be effective. In particular, the participants can achieve remarkable security gains by filtering compromised interdomain routes, cooperating to expose additional path diversity, inducing non-participants to select valid routes, and convincing a few large ISPs to participate. We also propose two novel mechanisms that the group members can employ to achieve these goals, namely secure overlay routing and the cooperative announcement of each other's address space. Our experiments show that combining these two techniques allows small groups to secure interdomain routing. Making Routing Failure Resilient Unexpected hardware failures often result in loss of connectivity or poor performance while the routing system converges to a new set of paths. To enable reliable data delivery and balance load in the presence of failures, this thesis proposes a new mechanism that combines path protection and traffic engineering. The key benefit of our solution is its simplicity, allowing for fast recovery while imposing minimal requirements on the routers. To provide resilience against every failure scenario from a known set, we advocate using a fixed set of parallel end-to-end paths for each traffic demand. Upon detecting a path failure, the ingress router uses a local rule to rebalance the outgoing traffic on the remaining available paths. We describe several candidate rebalancing algorithms, and analyze their performance. Although calculating the optimal set of paths and the path-splitting parameters for each router is NP-hard, our extensive simulations on a tier-1 IP backbone demonstrate that our easy-to-calculate heuristic suffices to achieve nearly optimal load balancing. Planned Work In addition to the above, I plan to answer the following questions: (i) This work uses the DPVP model to study the dynamics of interdomain routing (eBGP). How applicable is the model to intradomain routing (iBGP) and what new insights can we gain? (ii) We provide an algorithm that determines routing safety in polynomial time for virtually all policies that are used by network operators in practice. Is it possible to formalize the conditions under which the algorithm runs in polynomial time?

1 0

M Yu preFPO
by Melissa Lawson 16 Nov '10

16 Nov '10

Minlan Yu will present her preFPO on Wednesday November 24 at 9AM in Room 402. The members of her committee are: Jennifer Rexford, advisor; Mike Freedman and Albert Greenberg (Microsoft), readers; Vivek Pai and Ed Felten, nonreaders. Everyone is invited to attend her talk. Her abstract follows below. ---------------------------------- Title: Supporting Flexible Policies in Large Enterprise and Data-Center Networks Abstract: Enterprise and data center networks are growing larger and becoming more complicated to manage. These networks consist of two layers: the management layer that defines routing, enforces high-level policies, and diagnoses performance problems; the data plane that forwards packets, applies fine-grained rules, and monitors traffic. To make management layer simpler and easier to operate, people have proposed flat addressing to support host mobility, shortest-path routing to improve performance, and flow-based switches to enable fine-grained policies. However, these techniques raise scalability challenges in the data plane with many hosts, switches, flow rules, and applications, forcing the use of expensive switches with large, power-hungry memory for processing and monitoring data packets. This thesis proposes a new scalable data plane for enterprises and data centers. We improve the scalability of enterprise networks through a combination of new data structures that make effective use of limited memory, traffic indirection that minimizes the state required at each switch, and end-host based monitoring to reduce the overhead at switches. Our proposed system consists of three parts: (i) BUFFALO: A scalable packet forwarding architecture that uses Bloom filters to reduce the switch memory usage, and gracefully handles false positives by sending packets through a slightly longer path. (ii) DIFANE: A distributed management architecture that leverages emerging flow-based switches to scalably forward packets based on policies. (iii) SNAP: A network performance diagnosis architecture for data center applications that passively logs traffic statistics in the end-host network stack and pinpoint problems that occur at the network device, network stack and the application software. BUFFALO and DIFANE can be easily implemented with small modifications in today's switches, as demonstrated by our prototypes built using the Click modular router. SNAP was deployed in a large data center networks and helped operators and developers to pinpoint performance problems.

1 0

I Mukherjee preFPO
by Melissa Lawson 09 Nov '10

09 Nov '10

Indraneel Mukherjee will present his preFPO on Tuesday November 16 at 2PM in Room 402. The members of his committee are: Rob Schapire, advisor; Yoav Freund (UCSD) and David Blei, readers; Moses Charikar and Philippe Rigollet (ORFE), nonreaders. Everyone is invited to attend his talk. His abstract and reading list follow below. Title: Results on Boosting: Abstract: Boosting is a highly popular off-the-shelf machine learning algorithm. Yet its understanding is incomplete. In this thesis, we study two theoretical questions related to boosting. In the first project, we study boosting algorithms for multiclass classification. Boosting combines weak classifiers to form highly accurate predictors. Although the case of binary classification is well understood, in the multiclass setting, the "correct" requirements on the weak classifier, or the notion of the most efficient boosting algorithms are missing. In this paper, we create a broad and general framework, within which we make precise and identify the optimal requirements on the weak-classifier, as well as design the most effective, in a certain game-theoretic sense, boosting algorithms that assume such requirements. Secondly, we consider the problem of learning to predict as well as the best in a group of experts making continuous predictions, which is related to finding the optimal boosting algorithm with confidence rated weak-learners. We propose a new master strategy that achieves the best possible performance when the number of experts is sufficiently high. Our ideas are based on drifting games, a generalization of boosting and on-line learning algorithms. A surprising consequence of our work is that continuous experts are only as powerful as experts making binary or no prediction in each round.

1 0

Colloquium Speaker, Fri Oct 22- Chandu Thekkath- 1:30pm
by Nicole E. Wagenblast 19 Oct '10

19 Oct '10

Enabling Large-Scale Data Intensive Computations Chandu Thekkath, Microsoft Research Friday, October 22, 1:30pm This talk describes a set of distributed services developed at Microsoft Research Silicon Valley to enable efficient parallel programming on very large datasets. Parallel programs arise naturally within scientific, data mining, and business applications. Central to our philosophy is the notion that parallel programs do not have to be difficult to write and that the same program must seamlessly run on a laptop, desktop, a small cluster, or on a large data center without the author having to worry about the details of parallelization, synchronization, or fault-tolerance. We have built several services (Dryad, DryadLINQ, TidyFS, and Nectar) that embody this belief. Our goal is to enable users, particularly scientists of all disciplines, to treat a computer cluster as a forensic, diagnostic, or analytic tool. The talk will describe the details of our infrastructure and the characteristics of some of the applications that have been run on it. Chandu Thekkath is a researcher at Microsoft Research Silicon Valley. He received his Ph.D. in Computer Science from the University of Washington in 1994. Since then, except for a sabbatical year at Stanford in 2000, he has been in industrial research labs at DEC, Compaq, and Microsoft. He is a fellow of the ACM.

1 0

D Steurer FPO
by Melissa Lawson 18 Oct '10

18 Oct '10

David Steurer will present his FPO on Thursday October 21 at 4:30PM in Room 402. The members of his committee are: Sanjeev Arora, advisor; Boaz Barak and Russell Impagliazzo (IAS), readers; Moses Charikar and Bernard Chazelle, nonreaders. A copy of his thesis, "On the Complexity of Unique Games and Graph Expansion", is on display in Room 310. Everyone is invited to attend his talk.

1 0

Y Pritykin generals
by Melissa Lawson 14 Oct '10

14 Oct '10

Yury Pritykin will present his research seminar/general exam on Wednesday October 20 at 10AM in Room 402. The members of his committee are: Mona Singh, advisor, Tom Funkhouser, 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. --------------------------------- Abstract ======== Biological networks at different organization levels have proved useful for understanding of basic biological principles. Two complementary types of networks can be considered on a cellular level. One is the network of interactions between genes and proteins in a cell. It can be represented as a graph with directed and undirected edges of different types. Various methods have been used to study these kinds of networks in order to improve our understanding of functioning of cells and organisms. Another technique of expression and protein quantitative trait loci (eQTLs and pQTLs) aims to detect associations of locations in the genome with variation in a quantitative trait, in this case gene activity measured as transcript expression or protein abundance. The result of such analysis can be represented as a bipartite graph with linkages between genetic loci and genes or proteins. This talk will show advantage of mutual analysis of the above two types of networks. As an example, we show that using eQTL linkage information integrated with interaction information can help to infer more pQTLs linkages than the standard approach. Reading list ============ D. Mount. Bioinformatics: Sequence and Genome Analysis. 2nd Edition, Cold Spring Harbor Laboratory Press, 2004. Chapters 1-7, 10. T. Ideker, O. Ozier, B. Schwikowski, A. F. Siegel. Discovering regulatory and signalling circuits in molecular interaction networks. Bioinformatics, 18 Suppl 1, 2002, p. S233-40. V. Spirin, L. Mirny. Protein complexes and functional modules in molecular networks. Proceedings of the National Academy of Sciences of the United States of America. 100, 2003, pp. 12123-12128. M. V. Rockman, L. Kruglyak. Genetics of global gene expression. Nature reviews. Genetics, 7 (11), 2006, p. 862-72. X. Zhu, M. Gerstein, M. Snyder. Getting connected: analysis and principles of biological networks. Genes & development, 21 (9), 2007, p. 1010-24. T. M. Przytycka, M. Singh, D. K. Slonim. Toward the dynamic interactome: it's about time. Briefings in bioinformatics, 11 (1), 2010, p. 15-29. S. Suthram, A. Beyer, R. M. Karp, Y. Eldar, T. Ideker. eQED: an efficient method for interpreting eQTL associations using protein networks. Molecular systems biology, 4 (162), 2008, p. 162. J. Zhu, B. Zhang, E. N. Smith, B. Drees, R. B. Brem, L. Kruglyak, R. E. Bumgarner, E. E. Schadt. Integrating large-scale functional genomic data to dissect the complexity of yeast regulatory networks. Nature genetics, 40 (7), 2008, p. 854-61. Y. Huang, S. Wuchty, M. T. Ferdig, T. M. Przytycka. Graph theoretical approach to study eQTL: a case study of Plasmodium falciparum. Bioinformatics (Oxford, England), 25 (12), 2009, p. i15-20. S. Lee, A. M. Dudley, D. Drubin, P. A. Silver, N. J. Krogan, D. Pe'er, D. Koller. Learning a prior on regulatory potential from eQTL data. PLoS genetics, 5 (1), 2009, p. e1000358.

1 0