- talks - lists.cs.princeton.edu

M Golightly general exam
by Melissa Lawson 12 May '09

12 May '09

Michael Golightly will present his research seminar/general exam on Friday May 15 at 10AM in Room 302 (note room). The members of his committee are: Vivek Pai, advisor, Larry Peterson, and Jen Rexford. 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: The PlanetLab global network testbed has grown to consist of over 1000 globally distributed nodes that run hundreds of research experiments concurrently, placing demands on its infrastructure that single- experiment testbeds do not face. While it is widely used in the networking community, very little research has examined the behavior of PlanetLab itself, particularly in the areas of workload and capacity analysis. In light of the number of papers and proposals devoted to resource allocation strategies, auction mechanisms, and testbed fairness, this lack of data is particularly surprising. In order to support continued successful growth of PlanetLab, and to help in planning future testbeds such as GENI, a detailed understanding of how the system is being used is essential. Toward this goal, our work presents a detailed analysis of both the current testbed state as well as some historical analysis using data provided by CoMon, a monitoring service for PlanetLab. We examine node- level behavior as well as experiment-centric behavior to understand how the system and its components are used in practice. We identify root causes of resource contention and workload imbalance, and offer solutions for abatement, finding that targeted investments in infrastructure have the potential to substantially alleviate contention. Through analyzing resource consumption, provision, and disparity, we identify the degree of altruism and selfishness among the users and sites that host PlanetLab nodes. Using this information, we explore the effectiveness of current policies that aim to provide fair sharing of resources. We then explore the appropriateness and feasibility of various resource allocation schemes using a data driven approach based on observed usage patterns. Reading List: [Text Book] [1] L. L. Peterson and B. S. Davie. Computer networks: a systems approach. Morgan Kaufmann, Amsterdam, 4th ed edition, 2007. [Papers] [2] N. Spring, L. Peterson, A. Bavier, and V. Pai. Using planetlab for network research: myths, realities, and best practices. SIGOPS Oper. Syst. Rev., 40(1):17-24, 2006. [3] B. Chun and A. Vahdat. Workload and failure characterization on a large-scale federated testbed. Technical Report IRB-TR-03-040, Intel Research Berkeley, Nov. 2003. [4] K. Park and V. S. Pai. Comon: a mostly-scalable monitoring system for planetlab. SIGOPS Oper. Syst. Rev., 40(1):65-74, 2006. [5] S. Bhatia, A. Kumar, M. Fiuczynski, and L. Peterson. Lightweight, high-resolution monitoring for troubleshooting production systems. In 8th USENIX Symposium on Operating System Design and Implementation (OSDI 2008), December 2008. [6] J. Shneidman, C. Ng, D. C. Parkes, A. AuYoung, A. C. Snoeren, A. Vahdat, and B. Chun. Why markets could (but don't currently) solve resource allocation problems in systems. In HOTOS'05: Proceedings of the 10th conference on Hot Topics in Operating Systems, pages 7-7, Berkeley, CA, USA, 2005. USENIX Association. [7] D. Oppenheimer, J. Albrecht, D. Patterson, and A. Vahdat. Design and implementation tradeoffs for wide-area resource discovery. In 14th IEEE International Symposium on High Performance Distributed Computing, 2005. HPDC-14. Proceedings, pages 113-124, 2005. [8] D. Oppenheimer, B. Chun, D. Patterson, A. C. Snoeren, and A. Vahdat. Service placement in a shared wide-area platform. In ATEC '06: Proceedings of the annual conference on USENIX '06 Annual Technical Conference, pages 26-26, Berkeley, CA, USA, 2006. USENIX Association. [9] Y. Fu, J. Chase, B. Chun, S. Schwab, and A. Vahdat. SHARP: An architecture for secure resource peering. In Proceedings of the nineteenth ACM symposium on Operating systems principles, pages 133- 148. ACM New York, NY, USA, 2003. [10] R. Ricci, D. Oppenheimer, J. Lepreau, and A. Vahdat. Lessons from resource allocators for large-scale multiuser testbeds. SIGOPS Oper. Syst. Rev., 40(1):25-32, 2006.

1 0

A Vijayaraghavan general exam
by Melissa Lawson 12 May '09

12 May '09

Aravindan Vijayaraghavan will present his research seminar/general exam on Friday May 15 at 2PM in Room 302 (note room). The members of his committee are: Moses Charikar, advisor, Sanjeev Arora, and Boaz Barak. 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 Many approximation algorithms proceed by finding a good partial solution and then recursing into a sub-instance to find the remaining solution. With this motivation, we study the problem of maximizing certain integer quadratic programs with a ratio objective. We first consider the Max-cut gain problem where the objective is to find a cut which maximizes the advantage over the random assignment, of the fraction of edges cut. Trevisan recently gave an algorithm, that uses just the eigenvector corresponding to the smallest eigenvalue (\lambda), which given a gain of G, obtains a cut with an exponentially small cut-gain ( exp(-1/ G)). He considers the 'gain ratio' (gain achieved by partial cuts i.e cuts (L,R) of a subset S of vertices) and obtains a exponential small gain-ratio (~ exp(-1/|\lambda|) ) and then progresses recursively. He further conjectures that a much better gain-ratio of \Omega(|\lambda|/log(|\lambda|)), which matches the SDP algorithm of Charikar-Wirth, is achievable. However, we refute this conjecture, by showing that the gain-ratio achieved by his algorithm is almost tight, thus showing that eigen-value based methods can only produce cuts with exponentially small gain (and gain-ratio). We then consider the ratio version of a general quadratic the program i.e maximize ratio of \sum_{ij} a_{ij}x_i x_j to the number of non-zero x_i values (where x_i can take values in {-1,0,1}). We strengthen the natural SDP relaxation with some additional constraints (similar to triangle inequalities) and give a rounding algorithm which obtains an approximation ratio of O(n^{1/3}). We also show an integrality gap of \Omega(n^{1/4}) for this stronger relaxation. (Based on joint work with Moses Charikar and Aditya Bhaskara) Reading list: Books/Surveys: 1. Approximation Algorithms by V.Vazirani - chapters 1-6, 12-21 2. Hoory, Linial, Wigderson. Expander graphs and their applications. (Chapters 2,3,4,7) 3. Arora, Barak. Complexity Theory: A Modern Approach. (PCP Chapters, 11,21,22) Research articles: 1. Luca Trevisan. Maxcut and the smallest eigenvalue. 2. Charikar, Wirth. Maximizing Quadratic programs:Extending the Groethendieck's inequality. 3. Alon, Naor. Approximating the Cut-Norm via Grothendieck's Inequality 4. Khot, O'Donnell. SDP gaps and UGC-hardness for Max-Cut-Gain 5. Khot, Kindler, Mossel, O'Donnell. Optimal inapproximability results for MAX-CUT and other two-variable CSPs? 6. Feige, Kortsartz, Peleg. The Dense k-subgraph problem. 7. Feige. Relations between average case complexity and approximation complexity 8. Feige, Selster. On the densest k-subgraph problem. 9. Alon, Krivelevich, Sudakov. Finding a large hidden clique in a random graph 10. Charikar, Makarychev, Makarychev. Near-optimal algorithms for unique games. 11. Charikar, Markarychev, Makarychev. Integrality Gaps for Sherali-Adams Relaxations. 12. Raecke. Optimal Hierarchical Decompositions for Congestion minimization in networks 13. Fakcharoenphol, Rao, Talwar. A tight bound on approximating arbitrary metrics by tree metrics 14. Arora, Khot, Kolla, Steurer, Tulsiani and Vishnoi. Unique Games on Expanding Constraint Graphs are Easy

1 0

Room Change - Huang generals tomorrow
by Melissa Lawson 11 May '09

11 May '09

Note room change for Jialu Huang's general exam tomorrow. Exam has been moved to Room 302; time remains same - 2PM --Melissa

1 0

FW: Max Welling, May 11, 12:30pm (lunch at 12pm)
by Ginny Hogan 11 May '09

11 May '09

Max Welling from UCI will give a talk on May 11 at 12:30 (lunch served at 12:00) in CS 302. He will also host a discussion group at 4:30pm. See end of this email for instructions on how to schedule a meeting with Max. Title: On Herding Dynamical Weights and Fractal Attractors Abstract: Learning the parameters of a Markov Random Field is intractable. To circumvent part of this intractability, I propose to give up on the idea of trying to obtain point estimates. Inspired by the concept of "dynamical synapses", a dynamical system is introduced that generates sequences of pseudo-samples that are guaranteed to satisfy the moment constraints of the associated maximum likelihood problem. This dynamical system is deterministic, yet non-periodic with Lyaponov exponents all equal to zero, and its attractor set has fractal properties. I will discuss how to leverage these ideas for classification and estimation and show experimental results for fully observed and restricted Boltzman machines. Title: On the Role of Smoothing in Topic Models (with Arthur Acuncion and Padhriac Smyth) Discussion Group @ 4:30PM, Location TBD Abstract: Latent Dirichlet analysis, or topic modeling, is a flexible latent variable framework for modeling high-dimensional, sparse count data. Various learning algorithms have been developed in recent years, including collapsed Gibbs sampling, variational inference, and maximum a posteriori estimation, and this variety motivates the need for careful empirical comparisons between these approaches. We first highlight the close connections between these approaches. We find that the main differences are attributable to the amount of smoothing applied to the counts. When the hyperparameters are optimized, the differences in performance among the algorithms diminish significantly. The ability of these algorithms to achieve similarly accurate solutions gives us the freedom to select computationally efficient approaches. On text corpora with thousands of documents, accurate topic models can be learned in several seconds, using the insights gained from this comparative study. If you'd like to meet Max on Monday, please: 1. Visit http://wass.princeton.edu. 2. Sign in using your OIT login. 3. Click on "Make an appointment." 4. Enter "mlvisit" where it says "Calendar owner's netid." 5. Reserve a spot on May 11 under "Meeting with Max Welling."

1 0

P Prabhu general exam - today
by Melissa Lawson 11 May '09

11 May '09

(short notice - scheduling conflict, exam will be today) Prakash Prabhu will present his research seminar/general exam **today, Monday May 11** at 1PM in Room 402. The members of his committee are: David August, advisor, David Walker, and 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. ----------------------------------------------------- Enabling Implicit Parallel Programming on Multi-Core Architectures With the advent of multi-core architectures in mainstream computing, the importance of thread-level parallelism in delivering application performance has become critical. Existing thread-centric programming paradigms like pthreads and OpenMP are explicit. Today, programmers explicitly specify parallelization techniques and manage access to data using locking constructs. Such explicitly written parallel programs, plagued by race conditions, deadlocks, and performance problems, are difficult to write, debug, and maintain. Even worse, they are also fragile and intimately tied to assumptions about the underlying parallel architecture. In contrast, automatic thread extraction is a promising alternative that does not suffer from these problems, but whose benefits are yet to be realized on real hardware for large programs. Recently, Bridges et al., proposed two extensions to a sequential programming language, showing substantial amounts of thread-level parallelism can be automatically extracted from sequential codes, while relying on state-of-the-art profiling and speculation techniques. These extensions are not explicitly parallel and change program semantics. Since these extensions may change a program's output, they cannot be automatically inferred. Following on the lines of Bridges et al., this work proposes a generalized set of implicitly parallel programming extensions to the C language, which enables a programmer to write correct code and reason sequentially. At the same time, it considerably enhances a compiler's ability to extract thread-level parallelism. This talk explains the semantics of these extensions and demonstrates their use in manual parallelization of several benchmark programs. [Text Books] [1] Modern Compiler Implementation in ML, by A. W. Appel, Cambridge University Press, 1998 [2] Compilers: Principles, Techniques, and Tools (2nd Edition) by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Addison Wesley, 2006. [Papers] [3] 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 (MICRO), December 2007. [4] Neil Vachharajani, Ram Rangan, Easwaran Raman, Matthew J. Bridges, Guilherme Ottoni and David I. August. Speculative Decoupled Software Pipelining. In Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques (PACT), September 2007 [5] Christoph von Praun, Luis Ceze, Calin Caşcaval. Implicit parallelism with ordered transactions. In Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP), 2007 [6] Wen-mei Hwu et al., Implicitly Parallel Programming Models for Thousand-Core Microprocessors, In Proceedings of the 44th Design Automation Conference (DAC), 2007 [7] Robert Bocchino, Vikram Adve, Sarita Adve and Marc Snir. Parallel Programming Must Be Deterministic By Default. First USENIX Workshop on Hot Topics in Parallelism (HotPar), March 2009. [8] Monica S. Lam and Martin C. Rinard. Coarse-grain parallel programming in Jade. In Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP), pages: 94-105, 1991. [9] Eduard Ayguad´e et al., The Design of OpenMP Tasks, IEEE Transactions on Parallel and Distributed Systems (TPDS), March 2009 [10] David J. Pearce, Paul H.J. Kelly and Chris Hankin. Efficient field-sensitive pointer analysis of C. ACM Transactions on Programming Languages and Systems (TOPLAS), 2007 [11] R. Ghiya, L. J. Hendren and Y. Zhu. Detecting Parallelism in C Programs with Recursive Data Structures, Proceedings of the 7th International Conference on Compiler Construction (CC), page 159-173, 1998. [12] Chris Lattner, Andrew Lenharth, Vikram Adve. Making context-sensitive points-to analysis with heap cloning practical for the real world. In the Proceedings of the 2007 Programming Languages Design and Implementation conference, 2007. [13] Justiani and Laurie J. Hendren. Supporting Array Dependence Testing for an Optimizing/Parallelizing C Compiler. In the Proceedings of the 5th International Conference on Compiler Construction (CC), pages 309-323, 1994. [14] A. Tineo, F. Corbera, A. Navarro, R. Asenjo, and E.L. Zapata. A Novel Approach for Detecting Heap-based Loop-carried Dependences, Proceedings of the International Conference on Parallel Processing(ICPP), 2005

1 0

A Bhaskara general exam
by Melissa Lawson 07 May '09

07 May '09

Aditya Bhaskara will present his research seminar/general exam on Thursday May 14 at 10AM in Room 302 (note room). The members of his committee are: Moses Charikar, advisor, Sanjeev Arora, and Bob Tarjan. 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 -------- We will look at the densest-k-subgraph (DkS) problem: Given a graph G(V,E) and a parameter k, find a set of k vertices such that the number of edges among them is maximized. The problem is quite well-studied, but there is a big gap between the known algorithms and inapproximability results. There are combinatorial (greedy, path-based), and SDP based approaches known for the problem, which do well in different ranges of the parameters (degree, k). A common barrier for these approaches is the case of random graphs G(n,p) with planted dense subgraphs of size $k$. We thus propose and study a "Dense-vs-Random" problem: Distinguish a random graph of degree \Delta from the class of graphs with a k-subgraph of density (average degree) d. The question is to find the smallest $d$ for which this is possible (in terms of n, \Delta). For random graphs of degree n^{q} (0 < q < 1), we design algorithms that distinguish them from graphs with k-subgraphs of average degree >> k^q. The idea is to do an appropriate "local" counting. Interestingly, for such local counting, k^q seems to be a barrier, while a simple SDP based approach does better when q < 1/2. The main contribution is to use these "local structures" in obtaining algorithms for dense k-subgraph. We show how to do this for structures of certain special kinds. It seems reasonable to conjecture that this can be done with all structures. Doing this would imply an n^{1/4} approximation algorithm for dense k-subgraph. Our current techniques allow us to obtain a slightly worse ratio of n^{3/11}. It is an interesting question to go beyond n^{1/4} -- this is the limit for both the SDP and the local counting approaches. (Joint work with Moses Charikar and Aravindan Vijayaraghavan) Reading list ------- ---- N. Alon, M. Krivelevich and B. Sudakov, Finding a large hidden clique in a random graph, Random Structures and Algorithms 13 (1998), 457-466. Frank McSherry, Spectral Partitioning of Random Graphs. Proceedings of FOCS 2001, 529-537. Moses Charikar and Anthony Wirth, Maximizing Quadratic Programs: Extending Grothendieck's Inequality. Noga Alon and Assaf Naor, Approximating the cut-norm via Grothendieck's inequality. Luca Trevisan, Max Cut and the Smallest Eigenvalue. Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani and Nisheeth K. Vishnoi, Unique games on expanding constraint graphs are easy. Moses Charikar, Konstantin Makarychev and Yury Makarychev, Near-Optimal Algorithms for Unique Games. Uriel Feige, Relations between Average Case Complexity and Approximation Complexity. U. Feige and M. Seltser, On the densest $k$-subgraph problems. Moses Charikar, Konstantin Makarychev and Yury Makarychev, Integrality Gaps for Sherali-Adams Relaxations. Uri Feige and Robert Krauthgamer, The probable value of the Lovasz-Schrijver relaxations for maximum independent set. Tom Leighton and Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Sanjeev Arora, Satish Rao and Umesh Vazirani, Expander Flows, Geometric Embeddings, and Graph Partitionings. Books ----- Vijay Vazirani, Approximation Algorithms (Chapters 1-6, 12, 16, 19-22). Shlomo Hoory, Nati Linial, Avi Wigderson, Expander Graphs and their Applications (Chapters 1-4, 7). Sanjeev Arora, Boaz Barak, Computational Complexity: A modern approach (Chapters 1-11, 13, 21-22).

1 0

C Park general exam
by Melissa Lawson 07 May '09

07 May '09

Chris Park will present his research seminar/general exam on Wednesday May 13 at 10AM in Room 402. The members of his committee are: Olga Troyanskaya, advisor, Rob Schapire, and David Blei. 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 Inferring heterogeneous biological networks from heterogeneous data. With the advancement of quantitative biology, there has been a dramatic increase in functional genomic data. Using these heterogeneous genomic data which includes protein-protein interaction, gene expression, localization, and gene knockout studies has enabled researchers to construct functional gene networks. In functional gene networks, each edge represents the probabilistic support for a functional relationship between two genes. However in practice, the goal of biology is to understand further depth of the relationship between genes, beyond the abstract notion of a functional relation. In this work, we expand the depth and breadth of functional gene networks. We use prior biological knowledge of gene interactions types to construct an interaction ontology, which enables us to predict interaction types between genes using a Bayesian hierarchical framework. Ultimately, our work provides further insight into the genetic wiring of the cell. ---------------------------------------- Reading list Book: [1] Pattern Recognition and Machine Learning. by C. M. Bishop. Chapter 1~4, 6~9, 12~14 Papers: 1. Hierarchical multi-label prediction of gene function. Barutcuoglu, Z.; Schapire, R.E.; Troyanskaya, O.G. , Bioinformatics, (2006) 2. Discovery of biological networks from diverse functional genomic data. Myers, C.L.; Robson, D.; Wible, A.; Hibbs, M.A.; Chiriac, C.; Theesfeld, C.L.; Dolinski, K.; Troyanskaya, O.G. , Genome Biology, (2005) 3. Using Bayesian networks to analyze expression data. Nir Friedman, Michal Linial, Iftach Nachman, and Dana Pe'er. In RECOMB 4, pages 127-135. ACM Press, 2000. 4. Causal protein-signaling networks derived from multiparameter single-cell data. Sachs, K., Perez, O., Pe'er, D., Lauffenburger, D. A. & Nolan, G. P. Science 308, 523-529 (2005). 5. Conserved patterns of protein interaction in multiple species. Sharan, R., Suthram, S., Kelley, R. M., Kuhn, T., McCuine, S., Uetz, P., Sittler, T., Karp, R. M., and Ideker, T. /Proc Natl Acad Sci U S A. / *8*:102(6) 1974-79 (2005) 6. Genomic analysis of regulatory network dynamics reveals large topological changes. Luscombe, N., & et al. (2004). Nature, 431, 308. 7. Statistical significance for genome-wide studies. Storey JD and Tibshirani R. Proceedings of the National Academy of Sciences, 100: 9440-9445 (2003). 8. Cluster analysis and display of genome-wide expression patterns. Michael B. Eisen, Paul T. Spellman, Patrick O. Brown, and David Botstein PNAS, Dec (1998); 95: 14863 - 14868. 9. Genetics of global gene expression. Rockman, Kruglyak (2006). Nature Review Genetics 7:862-72. 10. An improved map of conserved regulatory sites for Saccharomyces cerevisiae. MacIsaac KD, Wang T, Gordon DB, Gifford DK, Stormo GD, Fraenkel E. BMC Bioinformatics. 2006 Mar 7;7:113.

1 0

M Meola general exam
by Melissa Lawson 07 May '09

07 May '09

Matt Meola will present his research seminar/general exam on Wednesday May 13 at 2PM in Room 402. The members of his committee are: David Walker, advisor, Andrew Appel, and Ed Felten. 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 -------- As semiconductor manufacturing technologies improve, feature sizes get smaller, and transistors more densely packed, computer users face an ever-increasing chance that cosmic rays and other sources of high energy particles will disrupt the workings of their processors. When implementing cryptographic algorithms, security protocols, long-running simulations, and safety-critical systems, software developers must consider the possibility that such intermittent hardware faults will cause irreparable harm to their applications. Boneh, DeMillo, and Lipton were the first to show that a single fault could be exploited to break common implementations of RSA. Others followed, demonstrating exploits of cryptosystems and runtime systems achieved by inducing transient faults. To support the higher degrees of confidence required in these critical applications, we have developed a new logic for reasoning about faulty programs. Our logic allows the verification of programs even in the presence of transient faults. It operates over a standard language of imperative while programs augmented with a single new instruction to indicate the possibility of faults at particular program points. The logic itself is a relative of Separation Logic in which the separating conjunction is used to reason about the limits to which faults may affect different parts of program state. As much as is practical, the logic is intended to be agnostic of the particular model used to decide when faults may occur. In particular, our current work deals with standard fault models that allow a certain maximum number of faults to occur in program variables in a single run of the program and limits faults according to how they affect data (typically either allowing only a single bit flip or allowing arbitrary changes in value). Faults in control-flow and many control logic faults (such as misinterpretation of opcodes) are ignored, except where they can be simulated by data faults. We prove the logic is sound and illustrate how to use it on several simple examples, including a simplified, idealized version of the RSA message signing algorithm. We show how the introduction of a modal connective helps to simplify program assertions and facilitate the reasoning process. Books ----- Pierce, B.C. Types and Programming Languages. MIT Press, 2002. Ch 1, 2, 4, 5 of Huth, M.R.A. and Ryan, M.D. Logic in Computer Science: Modelling and Reasoning about Systems. Cambridge University Press, 2000. Papers ------ [1] Bar-El, H., Choukri, H., Naccache, D., Tunstall, M., and Whelan, C. The Sorcerers Apprentice Guide to Fault Attacks. Proc. IEEE, Vol. 94. 370-382, Feb. 2006. [2] Barthe, G., Grégoire, B., and Zanella Béguelin, S. 2009. Formal certification of code-based cryptographic proofs. In Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Savannah, GA, USA, January 21 - 23, 2009). POPL '09. ACM, New York, NY, 90-101. [3] Boneh, D., DeMillo, R., and Lipton, R., On the importance of checking cryptographic protocols for faults, Journal of Cryptology 14 (2001). 101-119. [4] Chang, J., G. A. Reis and D. I. August. Non-Uniform Fault Tolerance. In Proceedings of the 2nd Workshop on Architectural Reliability (WAR), December 2006. [5] Ishtiaq, S. and O'Hearn, P. Bi as an assertion language for mutable data structures. In Proceedings of the 28th ACM Symposium on Principles of Programming Languages, London, United Kingdom, 2001, 14-26. [6] Perry, F., Mackey, L., Reis, G. A., Ligatti, J., August, D. I., and Walker, D. 2007. Fault-tolerant typed assembly language. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation (San Diego, California, USA, June 10 - 13, 2007). PLDI '07. ACM, New York, NY, 42-53. [7] Rebaudengo, M., Sonza Reorda, M., Torchiano, M., and Violante, M., Soft-error Detection through Software Fault-Tolerance techniques, in: IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems, 1999, 210-218. [8] Reis, G. A., Chang, J., and August, D. I. 2007. Automatic Instruction-Level Software-Only Recovery. IEEE Micro 27, 1 (Jan. 2007), 36-47. [9] Shirvani, P. P., Saxena, N., and McCluskey, E. J. 2000. Software-implemented EDAC protection against SEUs. In IEEE Transactions on Reliability. Vol. 49. 273284. [10] Walker, D., Mackey, L., Ligatti, J., Reis, G. A., and August, D. I. 2006. Static typing for a faulty lambda calculus. In Proceedings of the Eleventh ACM SIGPLAN international Conference on Functional Programming (Portland, Oregon, USA, September 16 - 21, 2006). ICFP '06. ACM, New York, NY, 38-49.

1 0

J Huang general exam
by Melissa Lawson 05 May '09

05 May '09

Jialu Huang will present her research seminar/general exam on Tuesday May 12 at 2PM in room 402. The members of her committee are: David August, advisor, Brian Kernighan, and Andrew Appel. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. ============================================ General abstract: While multi-core systems have become prevalent, using them efficiently remains an unsolved problem. DOALL is a highly efficient parallelization technique, however, cross-iteration dependences limit DOALL's applicability. Decoupled software pipelining (DSWP) partitions the code into stages with dependences flowing unidirectionally from earlier stages to later stages. DSWP is more generally applicable than DOALL, but its scalability is limited by the number of stages and by the workload in each stage. Parallel stage decoupled software pipelining (PS-DSWP) addresses this problem by enabling DOALL parallelization to some stages of a DSWP pipeline in loops where DOALL wasn't originally applicable. Inspired by the idea that DSWP can make DOALL more applicable, this work proposes other parallelization techniques can become more broadly applicable through the use of DSWP. LOCALWRITE, which requires each thread to only update the data belonging only to itself, if applied alone, suffers from redundant computations. Introducing LOCALWRITE into a DSWP framework, removes this limitation, by having a separate DOALL stage produce the iteration state to the LOCALWRITE stages. Experiments show combining all three parallelizations (DOALL, LOCALWRITE, DSWP) yields performance superior to applying any of these techniques alone. Reading List: Books: [1] Modern Compiler Implementation in ML, by A. W. Appel, Cambridge University Press, 1998. Chapter 1~13, 17~21. [2] Compilers: Principles, Techniques, and Tools by Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman, Addison Wesley, 2001. Chapter 9, 10. Papers: [1] Raman, E., Ottoni, G., Raman, A., Bridges, M. J., and August, D. I. 2008. Parallel-stage decoupled software pipelining. In Proceedings of the Sixth Annual IEEE/ACM international Symposium on Code Generation and Optimization (Boston, MA, USA, April 05 - 09, 2008). CGO '08. ACM, New York, NY, 114-123. DOI= http://doi.acm.org/10.1145/1356058.1356074 [2] Guilherme Ottoni, Ram Rangan, Adam Stoler, and David I. August. Automatic Thread Extraction with Decoupled Software Pipelining. In Proceedings of the 38th IEEE/ACM International Symposium on Microarchitecture (MICRO), November 2005. [3] Matthew J. Bridges, Neil Vachharajani, Yun Zhang, Thomas Jablin, David I. August, "Revisiting the Sequential Programming Model for the Multicore Era," IEEE Micro, vol. 28, no. 1, pp. 12-20, Jan./Feb. 2008, doi:10.1109/MM.2008.13. [4] Vachharajani, N., Rangan, R., Raman, E., Bridges, M. J., Ottoni, G., and August, D. I. 2007. Speculative Decoupled Software Pipelining. In Proceedings of the 16th international Conference on Parallel Architecture and Compilation Techniques (September 15 - 19, 2007). PACT. IEEE Computer Society, Washington, DC, 49-59. DOI= http://dx.doi.org/10.1109/PACT.2007.66. [5] Singh, D. E., Martin, M. J., and Rivera, F. F. 2005. Runtime characterisation of irregular accesses applied to parallelisation of irregular reductions. Int. J. Comput. Sci. Eng. 1, 1 (Feb. 2005), 1-14. DOI= http://dx.doi.org/10.1504/IJCSE.2005.008906. [6] Gutiérrez, E., Plata, O. G., and Zapata, E. L. 1999. On Automatic Parallelization of Irregular Reductions on Scalable Shared Memory Systems. In Proceedings of the 5th international Euro-Par Conference on Parallel Processing (August 31 - September 03, 1999). P. Amestoy, P. Berger, M. J. Daydé, I. S. Duff, V. Frayssé, L. Giraud, and D. Ruiz, Eds. Lecture Notes In Computer Science, vol. 1685. Springer-Verlag, London, 422-429. [7] Eladio Gutiérrez, Oscar Plata, Emilio L. Zapata, "Improving Parallel Irregular Reductions Using Partial Array Expansion," sc,pp.56, ACM/IEEE SC 2001 Conference (SC 2001), 2001. [8] Saltz, J. H., Mirchandaney, R., and Crowley, K. 1989. The doconsider loop. In Proceedings of the 3rd international Conference on Supercomputing (Crete, Greece, June 05 - 09, 1989). ICS '89. ACM, New York, NY, 29-40. DOI= http://doi.acm.org/10.1145/318789.318794. [9] Y. Lin and D. Padua. On the Automatic Parallelization of Sparse and Irregular Fortran Programs. Scientific Programming, 7(1999), pp. 231-246. ISSN 1058-9244, IOS Press. [10] Y. Lin and D. Padua. Analysis of Irregular Single-indexed Arrays and Its Applications in Compiler Optimizations. In Proceedings of the 9th International Conference on Compiler Construction. Berlin, Germany, March 2000.

1 0

J Hung general exam
by Melissa Lawson 05 May '09

05 May '09

Jack Tzu-Han Hung will present his research seminar/general exam on Tuesday May 12 at 10AM 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. ----------------------------- Abstract: Recently, the multicore systems have emerged as the dominate and promising architecture in the computing area. Unfortunately, a parallelizing compiler is essential to extract the potential parallelism from the existing sequential programs and utilize the power of multicore systems. Independent multi-threading (e.g., DOALL) and pipelined multi-threading (e.g., decouple software pipelining, DSWP) parallelization techniques have been researched extensively. However, each has its own advantages and limitations. On one hand, DOALL exploits data parallelism and scales well to the number of cores; however, it requires the lack of loop-carried dependencies and thus suffers from its applicability. On the other hand, DSWP handles the program dependencies via the use of communication queue and makes it applicable to more programs; however, the scalability of this approach is limited by the number of stages in the pipeline, which is usually far less than the number of cores. In this work, we propose two techniques to enhance the scalability of DSWP. First, instead of being inner-loop-blind, as DSWP does, we examine the structure of inner loops in the pipeline and exploit the DOALL opportunities if applicable. This improves the scalability of DSWP since the additional cores could be used for executing DOALL inner loops. Second, we optimize the communication for loop live-in and live-out variables by performing pre- and post-partitioning analyses. The post-partitioning analysis leverages the existing liveness analysis and is applied for each partition, instead of the entire loop. The pre-partitioning analysis takes the communication cost into consideration and could achieve better partitioning. Our initial results show a speedup up to 5.4x for 052.alvinn and ECLAT. Reading List: [Text Books] * Modern Compiler Implementation in ML, by A. W. Appel, Cambridge University Press, 1998. * Compilers: Principles, Techniques, and Tools (2nd Edition) by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Addison Wesley, 2006. [Papers] * Thies, W., Chandrasekhar, V., and Amarasinghe, S. 2007. A Practical Approach to Exploiting Coarse-Grained Pipeline Parallelism in C Programs. In Proceedings of the 40th Annual IEEE/ACM international Symposium on Microarchitecture (December 01 - 05, 2007). * Gordon, M. I., Thies, W., and Amarasinghe, S. 2006. Exploiting coarse-grained task, data, and pipeline parallelism in stream programs. In Proceedings of the 12th international Conference on Architectural Support For Programming Languages and Operating Systems (San Jose, California, USA, October 21 - 25, 2006). * Hongtao Zhong, Mojtaba Mehrara, Steve Lieberman, Scott Mahlke. " Uncovering Hidden Loop Level Parallelism in Sequential Applications". The 14th International Symposium on High-Performance Computer Architecture (HPCA), February, 2008. * Guilherme Ottoni, Ram Rangan, Adam Stoler, and David I. August. Automatic Thread Extraction with Decoupled Software Pipelining. In Proceedings of the 38th IEEE/ACM International Symposium on Microarchitecture (MICRO), November 2005. * EaswaranRaman, Guilherme Ottoni, Arun Raman, Matthew Bridges, and David I. August. Parallel-Stage Decoupled Software Pipelining. In Proceedings of the 2008 International Symposium on Code Generation and Optimization (CGO), April 2008. * Neil Vachharajani, Ram Rangan, Easwaran Raman, Matthew J. Bridges, Guilherme Ottoni and David I. August. Speculative Decoupled Software Pipelining. In Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques (PACT), September 2007. * Guilherme Ottoni and David I. August. Global Multi-Threaded Instruction Scheduling: Technique and Initial Results. In Proceedings of the Sixth Workshop on Explicitly Parallel Instruction Computer Architectures and Compiler Technology (EPIC), March 2007. * J. R. B. Davies. Parallel loop constructs for multiprocessors. Master's thesis, Department of Computer Science, University of Illinois, Urbana, IL, May 1981. * J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems, 9:319-349, July 1987.

1 0