- talks - lists.cs.princeton.edu

S Beard General Exam
by Melissa M. Lawson 12 Oct '11

12 Oct '11

Stephen Beard will present his research seminar/general exam on Wednesday October 19 at 10AM in Room 402. The members of his committee are; David August (advisor), Andrew Appel, and Vivek Pai. 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. --------------------------- Client Driven Memory Profiling Profiling provides vital insight to a program’s run-time characteristics including data and control information. Control flow profiling is popular because it improves compiler optimizations without excessive profiling overhead (less than 2×). While memory profiling can enable aggressive speculative optimizations to overcome the perennial limits of static memory analysis, it is rarely used due to its excessive profiling overhead (29× to 290×). To help address this problem, this paper presents Client Driven Memory Profiling (CDMP). Most speculative transformations are only concerned with some subset of the dependences in the program. Given this information, CDMP profiles only those dependences which are of use to the client optimizations. As a result, CDMP incurs a running time overhead of 66× averaged across the C/C++ SPEC CPU2006 benchmark suite, a 2.2× improvement over the 143× overhead incurred by a state-of-the-art memory profiler. After combining our client targeting optimization with sampling techniques found in prior work, CDMP achieve a running time overhead of 1.8×, a 4.1× improvement over the 7.3× overhead of sampling alone, with no additional error over sampling. Reading List 1.1 Textbooks 1. A. W. Appel. Modern Compiler Implementation in C. Cambridge University Press, 1998 2. S. Muchnick. Advanced Compiler Design and Implementation. Morgan-Kaufmann Publishers, San Francisco, CA, 1997 1.2 Performance and Path Profiling 3. S. L. Graham, P. B. Kessler, and M. K. Mckusick. Gprof: A call graph execution profiler. In Proceedings of the 1982 SIGPLAN symposium on Compiler construction, SIGPLAN ’82, pages 120–126, New York, NY, USA, 1982. ACM 4. T. Ball, P. Mataga, and M. Sagiv. Edge profiling versus path profiling: The showdown. In Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 134–148, January 1998 1.3 Dependence Profiling 5. T. Chen, J. Lin, X. Dai, W.-C. Hsu, and P.-C. Yew. Data dependence profiling for speculative optimizations. In E. Duesterwald, editor, Compiler Construction, volume 2985 of Lecture Notes in Computer Science, pages 2733–2733. Springer Berlin / Heidelberg, 2004 6. A. K. Peng Wu and C. Cascaval. Compiler-driven dependence profiling to guide program parallelization. In LCPC, pages 232–248, 2008 7. M. Kim, H. Kim, and C.-K. Luk. SD3 : A scalable approach to dynamic data-dependence profiling. In Proceedings of the 2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture, MICRO ’10, pages 535–546, Washington, DC, USA, 2010. IEEE Computer Society 1.4 Sampling 8. M. Arnold and B. G. Ryder. A framework for reducing the cost of instrumented code. In Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, PLDI ’01, pages 168–179, New York, NY, USA, 2001. ACM 1.5 Analysis 9. M. Hind. Pointer analysis: Haven’t we solved this problem yet? In 2001 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE’01), 2001 10. B. Hardekopf and C. Lin. Flow-sensitive pointer analysis for millions of lines of code. Code Generation and Optimization, IEEE/ACM International Symposium on, 0:289–298, 2011 1.6 Speculative Parallel Optimization 11. J. G. Steffan and T. C. Mowry. The potential for using thread-level data speculation to facilitate automatic parallelization. In Proceedings of the 4th International Symposium on High-Performance Computer Architecture, pages 2–13, February 1998

1 0

M Zoufaly general exam
by Melissa M. Lawson 04 Oct '11

04 Oct '11

Matt Zoufaly will present his research seminar/general exam on Tuesday October 11 at 8AM in Room 402. The members of his committee are: David August, advisor; Margaret Martonosi, JP Singh. 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. Title: A Framework for Runtime Parallelization Abstract: Performance no longer scales with the abundance of parallel resources provided by multicore devices. Prior work in manual parallelization as well as automatic static parallelization have shown promise, but a return to the era where processor improvements alone could be relied upon to consistently deliver improved application performance remains more desirable. To help address this problem, I present the HyPar dynamic parallelization framework for multicore systems. HyPar is a hybrid of lightweight hardware extensions and an efficient run-time parallelizer designed to provide the illusion of a single fast processor core for sequential binaries. In addition to a hot loop detector, each core in a HyPar system includes a memory characterizer. These memory characterizers guide memory speculation during parallelization, and they provide for distributed memory misspeculation detection during parallel execution. An instance of the HyPar framework, configured to use a custom memory characterizer and to perform the speculative DOALL transformation, yields a geomean speedup of 2.4x for 14 unmodified sequential x86 binaries on a commodity machine with four cores using simulated hardware components. Reading List: 1.1 Textbooks • A. W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998 • J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, San Francisco, CA, 1996 1.2 Binary Parallelization Papers • B. Hertzberg and K. Olukotun. Runtime automatic speculative parallelization. In Code Generation and Optimization (CGO), 2011 9th Annual IEEE/ACM International Symposium on, pages 64 –73, april 2011 • A. Kotha, K. Anand, M. Smithson, G. Yellareddy, and R. Barua. Automatic parallelization in a binary rewriter. In Proceedings of the 2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture, MICRO ’43, pages 547–557, Washington, DC, USA, 2010. IEEE Computer Society • C. Wang, Y. Wu, E. Borin, S. Hu, W. Liu, D. Sager, T. fook Ngai, and J. Fang. Dynamic parallelization of single-threaded binary programs using speculative slicing. In ICS’09, pages 158–168, 2009 • E. Yardimci and M. Franz. Dynamic parallelization and mapping of binary executables on hierarchical platforms. In CF ’06: Proceedings of the 3rd ACM International Conference on Computing Frontiers, pages 127–138, New York, NY, USA, 2006. ACM 1.3 Speculative Parallelization • L. Rauchwerger and D. Padua. The LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelization. ACM SIGPLAN Notices, 30(6):218–232, 1995 • 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, pages 1–12, June 2000 • H. Zhong, M. Mehrara, S. Lieberman, and S. Mahlke. Uncovering hidden loop level parallelism in sequential applications. In HPCA ’08: Proceedings of the 14th International Symposium on High-Performance Computer Architecture, 2008 1.4 Dynamic Optimizations • V. Bala, E. Duesterwald, and S. Banerjia. Dynamo: A transparent dynamic optimization system. In Proceedings of the ACM SIGPLAN ’00 Conference on Programming Language Design and Implementation, pages 1–12, June 2000 • A. Cristal, O. Santana, F. Cazorla, M. Galluzzi, T. Ramirez, M. Pericas, and M. Valero. Kilo-instruction processors: overcoming the memory wall. Micro, IEEE, 25(3):48 – 57, may-june 2005 • M. C. Merten, A. R. Trick, R. D. Barnes, E. M. Nystrom, C. N. George, J. C. Gyllenhaal, and W. W. Hwu. An architectural framework for runtime optimization. to appear in IEEE Transactions on Computers Special Issue on Dynamic Optimization, 2001 1.5 Memory Profiling • D. M. Gallagher, W. Y. Chen, S. A. Mahlke, J. C. Gyllenhaal, and W. W. Hwu. Dynamic memory disambiguation using the memory conflict buffer. In Proceedings of 6th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 183–193, October 1994 • 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 (ISCA), 1993

1 0

Colloquium Speaker Eric Xing: Thrus, Oct 6th- 4:30pm
by Nicole E. Wagenblast 04 Oct '11

04 Oct '11

Jointly Maximum Margin and Maximum Entropy Learning of Graphical Models Eric Xing, Carnegie Mellon University Thursday, October 6, 2011- 4:30pm Computer Science, 105 Graphical models (GMs) offer a powerful language to elegantly define expressive distributions, and a generic computational framework to support reasoning under uncertainty in a wide range of problems. Popular paradigms for training GMs include the maximum likelihood estimation, and more recently the max-margin learning, each enjoys some advantages, as well as weaknesses. For example, the maximum margin structured prediction model such as M3N lacks a straightforward probabilistic interpretation of the learning scheme and the prediction rule. Therefore its unique advantages such as support vector sparsity and kernel tricks cannot be easily conjoined with the merits of a probabilistic model such as Bayesian regularization, model averaging, and ability to model hidden variables. In this talk, I present a new general framework called Maximum Entropy Discrimination Markov Networks (MEDN), which integrates the margin-based and likelihood-based approaches and combines and extends their merits. This new learning paradigm naturally facilitates integration of the generative and discriminative principles under a unified framework, and the basic strategies can be generalized to learn arbitrary GMs, such as the generative Bayesian networks, models with structured hidden variables, and even nonparametric Bayesian models, with a desirable maximum margin effect on structured or unstructured predictions. I will discuss a number of theoretical properties of this approach, and show applications of MEDN to learning a wide range of GMs including: fully supervised structured i/o model, max-margin structured i/o models with hidden variables, a max-margin LDA-style model for jointly discovering “discriminative” latent topics and predicting document label/score of text documents, or total scene and objective categories in natural images, etc. Our empirical results strongly suggest that, for any GM with structured or unstructured labels, MEDN always leads to a more accurate predictive GM than the one trained under either MLE or Max Margin. Joint work with Jun Zhu. Dr. Eric Xing is an associate professor in the School of Computer Science at Carnegie Mellon University. His principal research interests lie in the development of machine learning and statistical methodology; especially for solving problems involving automated learning, reasoning, and decision-making in high-dimensional and dynamic possible worlds; and for building quantitative models and predictive understandings of biological systems. Professor Xing received a Ph.D. in Molecular Biology from Rutgers University, and another Ph.D. in Computer Science from UC Berkeley. His current work involves, 1) foundations of statistical learning, including theory and algorithms for estimating time/space varying-coefficient models, sparse structured input/output models, and nonparametric Bayesian models; 2) computational and statistical analysis of gene regulation, genetic variation, and disease associations; and 3) application of statistical learning in social networks, computer vision, and natural language processing. Professor Xing has published over 140 peer-reviewed papers, and is an associate editor of the Annals of Applied Statistics, the PLoS Journal of Computational Biology, and an Action Editor of the Machine Learning journal. He is a recipient of the NSF Career Award, the Alfred P. Sloan Research Fellowship in Computer Science, and the United States Air Force Young Investigator Award.

1 1

Colloquium speaker Swarat Chaudhuri Thurs Sept 29
by Nicole E. Wagenblast 28 Sep '11

28 Sep '11

Composing Composure: Reasoning about Robustness of Software Systems Swarat Chaudhuri, Rice University Thursday, September 29- 4:30pm Computer Science 105 Most software is inherently nonrobust--change the operating conditions of a typical program slightly, and you may obtain very different results. This lack of robustness can not only result in unpredictable runtime behavior, it also makes testing, approximation, and mathematical analysis of programs highly challenging. We will argue that methods for automated logical reasoning about programs provide a way to cope with this problem. Using a program analysis, we can sometimes determine if a given program is robust, and if so, exploit this property. On the other hand, if a program is not robust, logic can help us approximate it into one that is robust. Using applications from several different areas of computer science, I will show how these techniques can lead to more reliable program execution under uncertainty, opportunities for language-based approximate computation, and easier solutions to hard optimization problems involving programs. Swarat Chaudhuri is an Assistant Professor of Computer Science at Rice University. His research lies in the interface of automated reasoning and programming languages.

1 1

Distinguished Colloquium speaker, Cynthia Dwork, Wed Sept 21- 4:30pm
by Nicole E. Wagenblast 15 Sep '11

15 Sep '11

Distinguished Colloquium Series Speaker Fairness Through Awareness Cynthia Dwork, Microsoft Research, SVC Wednesday, September 21, 2011, 4:30 PM Computer Science 105 "Why was I not shown this advertisement? Why was my loan application denied? Why was I denied admission to this university?" In this work we initiate the formal study of fairness in classification, where the goal is to prevent discrimination against protected population subgroups in classification systems while simultaneously preserving utility for the party carrying out the classification (eg, the advertiser, bank, or admissions committee). We argue that a classification is fair only when individuals who are similar with respect to the classification task at hand are treated similarly, and this in turn requires understanding of sub cultures of the population. Similarity metrics are applied in many contexts, but these are often hidden. Our work explicitly exposes the metric, opening it to public debate. We then formalize and show how to achieve fairness in classification, given a similarity metric. We also give conditions on the metric under which our "local" notion ensures statistical parity: namely that the demographics of those receiving any given classification are the same as the demographics of the underlying population. In a complementary setting, we propose tools for what can be viewed as "fair affirmative action." Namely, we give methods for guaranteeing statistical parity for a group while treating similar individuals as similarly as possible. Finally, we discuss the relationship of fairness to privacy: to what extent might fairness imply privacy, and is it possible to employ tools developed in the context of differential privacy in order to obtain fairness. Joint work with Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Cynthia Dwork '79, Distinguished Scientist at Microsoft Research, is the world's foremost expert on placing privacy-preserving data analysis on a mathematically rigorous foundation. A cornerstone of this work is differential privacy, a strong privacy guarantee permitting highly accurate data analysis. Dr. Dwork has also made seminal contributions in cryptography and distributed computing, and is a recipient of the Edsger W. Dijkstra Prize, recognizing some of her earliest work establishing the pillars on which every fault-tolerant system has been built for decades. She is a member of the US National Academy of Engineering and a Fellow of the American Academy of Arts and Sciences.

1 0

Wei Dong FPO
by Melissa M. Lawson 08 Sep '11

08 Sep '11

Wei Dong will present his FPO on Wednesday September 14 at 9:30AM in Room 402. The members of his committee are: Kai Li, advisor; Moses Charikar and Andrea LaPaugh, readers; Brian Kernighan and Olga Troyanskaya, nonreaders. A copy of his thesis, "High-Dimensional Similarity Search for Large Datasets", is on display in Room 310. Everyone is invited to attend his talk.

1 0

A Feldman preFPO
by Melissa M. Lawson 30 Aug '11

30 Aug '11

Ari Feldman will present his preFPO on Friday September 2 at 2PM in Room 302 (note room). The members of his committee are: Ed Felten, advisor; Mike Freedman and Andrew Appel, readers; David Walker and Brian Kernighan, nonreaders. Everyone is invited to attend his talk. His abstract follows below. -------------------------------------------------- Title: Using Untrusted Resources Securely Abstract: In a myriad of applications, users depend on devices or services provided by third parties to perform functions that they cannot carry out themselves or that third parties can do better. For example, in public elections, voters cast their votes on voting machines or paper ballots provided by election officials because they do not have the means to prepare properly formatted ballots on their own. In addition, in applications from word processing to social networking, users are increasingly adopting services in which their data resides not on their own devices, but on servers run by third parties. Users are drawn to these services because they provide levels of availability, scalability, and accessibility that average users cannot match using only their own equipment. Unfortunately, depending on third parties has typically forced users to give up control over their data. They must rely on the third parties to preserve their data’s confidentiality and integrity, and a third party that is malicious or has been subject to attack or legal pressure can compromise them. Furthermore, users typically have little more than the third parties’ promises to assure them that their data is safe. In this dissertation, we aim to improve this situation. We present protocols and systems that allow users to utilize third-party resources while providing them with a means to verify that the third parties are performing their functions correctly so that they need not trust mere promises. Our work covers three areas: cryptographic voting, cloud-based group collaboration, and social networking. Our prior work shows that widely-deployed non-cryptographic voting systems can be infected with malicious software that changes votes, potentially without detection. Vulnerabilities of this kind inspired the development of cryptographic voting systems in which the encryption of every cast ballot is made public and the encrypted ballots can be tallied in a publicly-verifiable way. Although cryptographic voting has the potential to make elections more trustworthy, it still forces voters to depend on voting machines to encrypt their ballots. Indeed, we show that a malicious voting machine can compromise the secrecy of the ballot by manipulating the ciphertext of only a handful of the ballots that are made public. We then present a protocol that significantly reduces this threat by forcing voting machines to encrypt ballots using random values chosen in advance of the election and that provides a way for anyone to verify that the right random values were used for every ballot. For applications such as word processing and calendaring, users are increasingly adopting cloud deployment because it provides benefits such as scalability, high availability, global accessibility, and real-time group collaboration. Unfortunately, moving to the cloud currently comes at the cost of trusting the cloud provider with users’ data. To overcome this tradeoff, we present SPORC, a generic framework for building a wide variety of collaborative applications with untrusted servers. In SPORC, servers only observe encrypted data and cannot deviate from correct execution without being detected. SPORC allows concurrent, low-latency editing of shared state, permits disconnected operation, and supports dynamic access control even in the presence of concurrency. Current social networking applications also require users’ to trust service providers with the plaintext of their social interactions. In response, numerous works have proposed distributing users’ data across multiple servers controlled by different parties. But, unless users bear the burden of running their own servers, they are still forced to trust third parties. Instead, we present a social networking system that allows users’ data to be hosted entirely on untrusted servers while still protecting the data’s confidentiality and integrity. Our design includes novel data structures that support efficient membership operations even for large groups and provide strong protection against server equivocation for the append-only logs that social networking applications use extensively.

1 0

S Jafarpour FPO
by Melissa M. Lawson 25 Aug '11

25 Aug '11

Sina Jafarpour will present his FPO on Friday September 2 at 2PM in Room 402. The members of his committee are: Rob Calderbank (ELE/MAT), advisor; Rob Schapire and Ingrid Daubechies (MAT), readers; Bernard Chazelle and Amit Singer (MAT), nonreaders. A copy of his thesis, "Deterministic Compressed Sensing", is on display in Room 310. Everyone is invited to attend his talk.

1 0

I Mukherjee FPO
by Melissa M. Lawson 23 Aug '11

23 Aug '11

Indraneel Mukherjee will present his FPO on Monday August 29 at 2PM in Room 402. The members of his committee are: Rob Schapire, advisor; David Blei and Yoav Freund (UCSD), readers; Moses Charikar and Philippe Rigollet (ORF), nonreaders. A copy of his thesis, "Game Theory and Optimization in Boosting", is on display in Room 310. Everyone is invited to attend his talk.

1 0

Y Zhu FPO
by Melissa Lawson 18 Aug '11

18 Aug '11

Yaping Zhu will present her FPO on Thursday August 25 at 1PM in Room 402. The members of her committee are: Jennifer Rexford, advisor; Vivek Pai and Aman Shaikh (AT&T), readers; Michael Freedman and Andrea LaPaugh, nonreaders. A copy of her thesis, "Minimizing Wide-Area Performance Disruptions in Inter-Domain Routing", is on display in Room 310. Everyone is invited to attend her talk.

1 0