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

E Raman preFPO
by Melissa M Lawson 22 May '08

22 May '08

Easwaran Raman will present his preFPO on Thursday May 29, 2PM, in room 402. The members of his committee are: David August, advisor; Teresa Johnson (HP) and Doug Clark, readers; David Walker and Vivek Pai, nonreaders. Everyone is welcome to attend his talk. His abstract follows below. -------------------------------- Title: Extracting Iteration-Level Parallelism from Loops with Inter-Iteration Dependences Abstract --------------- The continuing exponential growth in transistor density and the limitations in using the additional transistors to boost uniprocessor performance has caused processor manufactures to pack multiple processor cores onto a single chip. These processors, known as chip multiprocessors (CMPs) or multicore processors, do not ensure that single-threaded applications continue to run faster unless those applications are parallelized. Automatic parallelization by compilers has a key role to play in utilizing the CMP architecture to improve single-threaded application performance. One of the most common compiler techniques to automatically parallelize loops is DOALL parallelization. DOALL extracts iteration-level parallelism by executing different iterations of the loop concurrently. The advantage of DOALL lies in its scalability with the iteration count of the loop, but its applicability is severely limited by the presence of inter-iteration or loop-carried dependences. My thesis proposes two new techniques to extract iteration-level parallelism from loops with loop-carried dependences. The first technique, known as Speculative Iteration Chunk Execution (Spice), uses value speculation to break loop-carried dependences, enabling speculative execution of chunks of iterations in parallel. Unlike most value-speculation based parallelization techniques, Spice speculates only a few values to unlock parallelism using a software-based value predictor. The second technique is known as Parallel-Stage Decoupled Software Pipelining (PS-DSWP). PS-DSWP extracts both pipelined parallelism and iteration-level parallelism from loops, thereby generalizing two well-known parallelization techniques, DOALL and Decoupled Software Pipelining (DSWP). PS-DSWP partitions a loop into a sequence of pipeline stages that are executed concurrently by different threads, resulting in pipelined parallelism. Iteration-level parallelism is extracted by allowing those stages that do not have any loop-carried dependences, known as parallel stages, to be executed by multiple threads concurrently in a DOALL-like fashion. The applicability and effectiveness of PS-DSWP is further enhanced by using speculation to remove certain dependences. Both these techniques are implemented in the VELOCITY compiler and evaluated on an Itanium 2 CMP simulator. The results demonstrate the ability of these techniques to significantly out-perform prior techniques on several important loops from real applications.

1 0

L Poole general tomorrow - time change
by Melissa M Lawson 21 May '08

21 May '08

Lindsey Poole's general exam scheduled for tomorrow, Thursday May 22, has been moved to 1PM in Room 402.

1 0

L Poole general exam
by Melissa M Lawson 16 May '08

16 May '08

Lindsey Poole will present his research seminar/general exam on Thursday May 22 at 3PM in Room 402. The members of his committee are: Vivek Pai (advisor), Jennifer Rexford, and Larry Peterson. 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 While cooperative DNS resolver systems, such as CoDNS, have demonstrated improved reliability and performance over standard approaches, their security has been weaker, since any corruption or misbehavior of a single resolver can easily propagate throughout the system. We address this weakness in a new system called ConfiDNS, which augments the cooperative lookup process with configurable policies that utilize multi-site agreement and per-site lookup histories. Not only does ConfiDNS provide better security than cooperative approaches, but for up to 99.8% of unique lookups, ConfiDNS exceeds the security of standard DNS resolvers. ConfiDNS provides these benefits while retaining the other benefits of CoDNS, such as incremental deployability, higher reliability, and improved performance, in some cases faster than CoDNS. We discuss the implementation of ConfiDNS and the challenges of running a distributed agreement protocol in an environment where DNS-based redirection is is used to facilitate load-balancing and localized content distribution. Textbook [1] L. Peterson, and B. Davie, Computer Networks: A Systems Approach, 3rd edition, Morgan Kaufmann Publishers, May 2003. Research Papers [1] D. Clark, "The design philosophy of the DARPA Internet protocols," ACM SIGCOMM Computer Communication Review, Vol. 18, No. 4, pp. 106-114, Aug. 1988. [2] L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web Caching and Zipf-like Distributions: Evidence and Implications. In 'In Proceedings of IEEE INFOCOM', New York, NY, March 1999. [3] A. Lioy, F. Maino, M. Marian, and D. Mazzocchi. Dns security. In Proceedings of the TERENA Networking Conference, Lisbon, Portugal, May 2000. [4] H. B. Jaeyeon Jung, Emil Sit and R. Morris. DNS Performance and the Effectiveness of Caching. In Proceedings of the ACM SIGCOMM Internet Measurement Workshop '01, San Francisco, California, November 2001. [5] K. Park, V. S. Pai, L. Peterson, and Z. Wang. CoDNS: Improving DNS Performance and Reliability via Cooperative Lookups. In Proceedings of the Sixth Symposium on Operating Systems Design and Implementation (OSDI), San Franscisco, CA, December 2004. [6] P. Mockapetris and K. Dunlap. Development of the Domain Name System. In In Proceedings of the ACM SIGCOMM Conference, Stanford, CA, August 1988. [7] A. Shaikh, R. Tewari, and M. Agrawal. On the effectiveness of dns- based server selection. In Proceedings of INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, Anchorage, AK, April 2001. [8] B. Krishnamurthy, C. Wills, and Y. Zhang. On the use and performance of content distribution networks. In Proceedings of SIGCOMM Internet Measurement Workshop, San Francisco, CA, November 2001. [9] H. Ballani and P. Francis. A Simple Approach to DNS DoS Mitigation. In Proceedings of the 5th ACM Workshop on Hot Topics in Networks (HotNets '06), Irvine, CA, November 2006. [10] L. Wang, K. Park, R. Pang, V. Pai, and L. Peterson. Reliability and Security in the CoDeeN Content Distribution Network. In In Proceedings of the USENIX Annual Technical Conference, Boston, MA, June 2004. [11] J. Yin, J. Martin, A. Venkataramani, L. Alvisi, and M. Dahlin. Separating agreement from execution for byzantine fault tolerant services. In In Proceedings of the 19th ACM Symposium on Operating Systems Principles (SOSP-2003), Lake George, NY, October 2003. [12] M. Castro and B. Liskov. Practical byzantine fault tolerance. In In Proceedings of the Symposium on Operating Systems Design and Implementation (OSDI), New Orleans, LA, February 1999.

1 0

Z Khan general exam
by Melissa M Lawson 16 May '08

16 May '08

Zia Khan will present his research seminar/general exam on Wednesday May 21 at 3PM in Carl Icahn Lab Room 280. The members of his committee are: Mona Singh (advisor) Leonid Kruglyak, and Olga Troyanskaya. 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: Proteins are the workhorse molecules of the cell. They play critical roles in a range of processes, from copying and protecting DNA to regulating chemical reactions important for survival. Recent experimental technologies have enabled identification of which proteins are present in the cell and how much of these proteins are in a cell relative to a control sample. This measurement process is not possible without computational analysis because cells can contain thousands of different types of proteins. As a result, algorithms play a key role in determining the identity and relative abundance of proteins present in an experimental sample. The specific computational challenge associated with determining the relative abundance of proteins is a direct result of the instrument commonly used to make such measurements: a tandem mass spectrometer. When combined with another instrument called a liquid chromatography column, a mass spectrometer generates massive data sets in which noisy patterns represent relative protein abundances. My research has focused on analyzing this data. The algorithms I have designed efficiently find patterns which correspond to proteins and associate these patterns with protein identities. My approach shows state of the art performance on benchmark and real data sets. The algorithms generalize to data from several different experimental conditions, organisms, and instrument types. More importantly, this work enables unprecedented surveys of protein abundances and thus promises to reveal new biology. Reading list: ** Textbook (Broad subject area: Bioinformatics & Computational Biology): [1] An Introduction to Bioinformatics Algorithms. Neil C. Jones, Pavel A. Pevzner. The MIT Press; 1 edition (August 1, 2004) ** Chosen Specialization (Proteomics): [2] The biological impact of mass-spectrometry-based proteomics. Benjamin F. Cravatt, Gabriel M. Simon, John R. Yates III Nature 450, 991-1000 (13 December 2007) [3] Mass spectrometry-based proteomics in the life sciences. C. S. Lane Cell Mol Life Sci. 2005 April 62(7-8):848-69. ** Research subarea (protein quantification for genetic analysis of proteome variation): Protein quantification: [4] Analysis and validation of proteomic data generated by tandem mass spectrometry Alexey I. Nesvizhskii and Olga Vitek and Ruedi Aebersold Nature Methods 4, 787-797 (2007). [5] Statistical and Computational Methods for Comparative Proteomic Profiling Using Liquid Chromatography-Tandem Mass Spectrometry Molecular & Cellular Proteomics 4:419-434, 2005. Jennifer Listgarten and Andrew Emili. Genetic Analysis of Protein/Transcript Abundance: [6] Genetic basis of proteome variation in yeast. Eric J. Foss and Dragan Radulovic and Scott A. Shaffer and Douglas M. Ruderfer and Antonio Bedalov and David R. Goodlett and Leonid Kruglyak. Nature Genetics 39, 1369 - 1375 (2007). [7] Rockman, MV, & L Kruglyak. 2006. Genetics of global gene expression. Nat. Rev. Genet. 7, 862-872 [8] E. S. Lander and D. Botstein. Mapping Mendelian Factors Underlying Quantitative Traits Using RFLP Linkage Maps. Genetics 121:185-199. [9] G. A. Churchill and R. W. Doerge. Empirical Threshold Values for Quantitative Trait Mapping. Genetics 138: 963-971. 1994.

1 0

Juan Chen talk today 12:30 rm 302
by Andrew W. Appel 16 May '08

16 May '08

1 0

S Ihm general exam
by Melissa M Lawson 15 May '08

15 May '08

Sunghwan Ihm will present his research seminar/general exam on Wednesday May 21 at 10AM in room 402. The members of his committee are: Vivek Pai (advisor), Jennifer Rexford, and Mike Freedman. 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] In the developing world, Internet access is often expensive, low-bandwidth, and high latency. The situation gets even worse since even low-capacity links are shared by many people. However, there may also be much redundant network traffic due to the sharing. Wide-area network (WAN) acceleration is a protocol-independent approach to caching redundant traffic to avoid sending duplicate data over slow links. Among the many techniques for eliminating redundancy, content-based naming (CBN) scheme is one of the most effective approaches. CBN breaks data into position-independent chunks based on its content, and names them with their hash values, so that they can be shared across different transfers. While recent CBN-based systems have shown the effectiveness of this approach, they are often designed to be point-to-point systems, and do not take advantage of groups of local users. Further, they are often targeted to specific environments, and have design-based limits on performance. In this work, we propose Waprox, a high-performance WAN accelerator using CBN. Waprox uses a novel multi-resolution chunking (MRC) scheme to address the tradeoff between chunk size and performance. The intuition is to use small chunk sizes when needed to eliminate redundancy, but use larger chunk sizes when possible, in order to improve performance. We demonstrate the effectiveness of MRC by a trace-based simulation analysis. We also implement a prototype of Waprox, and show that it consumes 18% less bandwidth while having 21% higher throughput. [Text Book] L. Peterson, and B. Davie, Computer Networks: A Systems Approach, 4th Edition, Morgan Kaufmann Publishers, March 2007. [Papers] 1. N. T. Spring and D. Wetherall. A protocol-independent technique for eliminating redundant network traffic. In SIGCOMM, Aug. 2000. 2. A. Muthitacharoen, B. Chen, and D. Mazieres. A low-bandwidth network file system. In Proc. 18th SOSP, pages 174--187, Oct. 2001. 3. V. S. Pai, M. Aron, G. Banga, M. Svendsen, P. Druschel, W. Zwaenepoel, and E. Nahum. Locality-Aware Request Distribution in Cluster-based Network Servers. In Proceedings of the 8th ACM Conference on Architectural Support for Programming Languages and Operating Systems, San Jose, CA, Oct. 1998. 4. L. Wang, V. Pai, and L. Peterson. The effectiveness of request redirection on CDN robustness. In Proceedings of The Fifth Symposium on Operating Systems Design and Implementation (OSDI'02), Boston, MA, December 2002. 5. J. C. Mogul, Y. M. Chan, and T. Kelly. Design, implementation, and evaluation of duplicate transfer detection in HTTP. In Proc. First Symposium on Networked Systems Design and Implementation (NSDI), San Francisco, CA, Mar. 2004. 6. H. Pucha, D. G. Andersen, and M. Kaminsky. Exploiting similarity for multi-source downloads using file handprints. In Proceedings of the 4th USENIX/ACM Symposium on Networked Systems Design and Implementation(NSDI'07), 2007. 7. N. Tolia, M. Kaminsky, D. G. Andersen, and S. Patil. An architecture for Internet data transfer. In Proc. 3rd Symposium on Networked Systems Design and Implementation (NSDI), San Jose, CA, May 2006. 8. S. Annapureddy, M. J. Freedman, and D. Mazières. Shark: Scaling file servers via cooperative caching. In Proc. 2nd USENIX NSDI, Boston, MA, May 2005. 9. R. CHAKRAVORTY, A. CLARK AND I. PRATT. Optimizing Web Delivery over Wireless Links: Design, Implementation and Experiences. IEEE Journal of Selected Areas in Communications (JSAC) 10. S. Rhea, K. Liang, and E. Brewer. Value-based web caching. In Proc. of the 12th Int. World Wide Web Conference, May 2003.

1 0

Y Zhang general exam
by Melissa M Lawson 14 May '08

14 May '08

Yun Zhang will present her research seminar/general exam on Tuesday May 20 at 10AM in room 402. The members of her committee are: David August (advisor), Andrew Appel, and Doug Clark. 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. ---------------------------- Abstract: Limited memory alias analysis inhibits automatic parallelization for multi-core architecture. Alias analysis generally considers memory accesses to separated parts of recursive data structures, especially cyclic ones, dependent since the analysis has no shape information indicating how the program traverses the data structure. For example, accesses to the left child of a binary tree node are separated from accesses to the right child, but current memory analysis methods conservatively conclude the accesses may alias with each other. This work proposes a three-step memory alias analysis that performs dependence tests on loops that traverse recursive data structures to benefit automatic code parallelization. The first step captures shape information of recursive data structures using separation logic, the second performs backward data flow analysis to form two pointers' definition chains, and the third combines the two definition chains with the shape information of the data structure to see if the two pointer accesses separate or alias between loop iterations. The experimental results show that this new alias analysis technique can effectively locate real cross-iteration dependences, which unveils opportunities for automatic parallelization, eases the work of instruction distribution and reduces data communications between cores. Reading List Books: 1. Modern Compiler Implementation in ML, by A. W. Appel, Cambridge University Press, 1998 2. Advanced compiler design and implementation, by S. S. Muchnick, Morgan Kaufman, 1997 Papers: 3. Shape Analysis with Inductive Recursion Synthesis. B. Guo, N. Vachharajani, and D. I. August, Proceedings of the ACM SIGPLAN 2007 Conference on Programming Language Design and Implementation (PLDI), June 2007. 4. Detecting Parallelism in C Programs with Recursive Data Sturctures, R. Ghiya, L. J. Hendren and Y. Zhu, Computational Complexity, page 159-173, 1998 5. Practical and Accurate Low-level Pointer Analysis, B. Guo, M.J. Bridges, S. Triantafyllis, G. Ottoni, E. Raman, and D. I. August, Proceedings of the Third International Symposium on Code Generation and Optimization (CGO), March 2005. 6. Identifying Parallelism in Programs with Cyclic Graphs, Y. Hwang and J. Saltz, Proceedings of the Proceedings of the 2000 International Conference on Parallel Processing(ICPP), 2000 7. Separation Logic: A Logic for Shared Mutable Data Structures, J. Reynold, Invited Paper, LICS 2002 8. Analysis of Pointers and Structures, D. R. Chase, M. Wegman, F. K. Zadeck, Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, pp. 296-310, 1990. 9. Automatic Thread Extraction with Decoupled Software Pipelining, G. Ottoni, R. Rangan, A. Stoler, D. I. August, Proceedings of the 38th IEEE/ACM International Symposium on Microarchitecture (MICRO), November 2005 10. Revisiting the Sequential Programming Model for Multi-core, M. Bridges, N. Vachharajani, Y. Zhang, T. Jablin, D. I. August, Proceedings of the 40th IEEE/ACM International Symposium on Microarchitecture (MICRO), 2007 11. Points-to analysis by type inference in programs with structures and unions, B. Steensgaard, Lecture Notes in Computer Science, 1060 (T. Gyimothy, ed.), pp. 136-150, Springer-Verlag, 1996. Proceedings from the International Conference on Compiler Construction. 12. Relevant context inference, R. Chatterjee, B. G. Ryder, and W. A. Landi, Proceedings of the ACM Symposium on Principles of Programming Languages, pp. 133-146, January 1999.

1 0

G Wang FPO
by Melissa M Lawson 12 May '08

12 May '08

Ge Wang will present his FPO on Friday may 16 at 2PM in Room 302. The members of his committee are: Perry Cook, advisor; Paul Lansky (Music) and Roger Dannenberg (CMU), readers; Andrew Appel and Brian Kernighan, nonreaders. A copy of his thesis, "The ChucK Audio Programming Language "A Strongly-timed and On-the-fly Environ/mentality" " is on display in Room 310. Everyone is invited to attend his talk.

1 0

S Sevinc general exam
by Melissa M Lawson 12 May '08

12 May '08

Soner Sevinc will present his research seminar/general exam on Friday May 16 at 10AM in Room 402. The members of his committee are: Larry Peterson (advisor), Jennifer Rexford, 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. ------------------------------------- Large-scale network systems often must support users from multiple organizations that want to use resources owned by other organizations. Managing resources in such an environment must, therefore, be decentralized. Such systems require unique, immutable and verifiable naming of entities, and a security architecture that includes a fine grained authorization. Verification should allow multiple levels of trust to make the security system decentralized. Fail safety is necessary for correct operation of such a large system, limiting the damage a malicious or mis-operating entity can have to a short period of time. PlanetLab being one of such systems is in the stage of decentralization with federation with other similar systems or separating into several autonomous pieces. PlanetLab's current identity based authorization architecture makes decentralization difficult. The features of a more manageable system should include making the sources of authorization explicit, separating identity from rights, and allowing delegation of those rights. The protocols used within the system should support secure communication, possibly leveraging existing security schemes. My talk describes an architecture developed in the context of PlanetLab. The design includes a naming system, support for decentralized trust, and a fine-grained authorization mechanism. I will also describe a prototype implementation that leverages PlanetLab. " Reading List: 1. L.Peterson and B.Davie, "Computer Networks: A Systems Approach", 3rd Edition. 2. Larry Peterson, Andy Bavier, Marc E. Fiuczynski, and Steve Muir, "Experiences Building Planetlab", OSDI 2006 3. A.Bavier, N.Feamster, M.Huang, L.Peterson, and J.Rexford, "In VINI Veritas: Realistic and Controlled Network Experimentation", in Proc. ACM SIGCOMM, Sep 2006. 4. T. Anderson, Timothy Roscoe, "Learning from PlanetLab", 2006, Proceedings of the 3rd conference on USENIX Workshop on Real, Large Distributed Systems - Volume 3 5. M. Blaze, J. Feigenbaum and J. Lacy, "Decentralized trust management", In Proceedings of the 1996 IEEE Symposium on Security and Privacy, pages 164-173, May 1996. 6. Thomas Anderson and Michael Reiter, "*GENI Facility Security*," /GENI Design Document 06-23/, Distributed Services Working Group, September 2006. 7. E. Wobber, M. Abadi, M. Burrows and B. Lampson, "Authentication in the Taos operating system", ACM Transactions on Computer Systems 12(1):3-32, February 1994. 8. T. Jim, "SD3: A trust management system with certified evaluation", In Proceedings of the 2001 IEEE Symposium on Security and Privacy, pages 106-115, May 2001. 9. Jie Dai, Jim Alves-Foss, "Logic Based Authorization Engineering"

1 0

I Mukherjee general exam
by Melissa M Lawson 12 May '08

12 May '08

Indraneel Mukherjee will present his research seminar/general exam on Friday May 16 at 2PM in Room 402. The members of his committee are: Rob Schapire (advisor), David Blei, and Ken Steiglitz. 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 consider the problem of learning to predict as well as the best in a group of experts making continuous predictions. We assume the learning algorithm has prior knowledge of the maximum number of mistakes of the best expert. We propose a new master strategy that achieves the best known performance for online learning with continuous experts in the mistake bounded model. Our ideas are based on drifting games, a generalization of boosting and online learning algorithms. We also prove new lower bounds based on the drifting games framework which, though not as tight as previous bounds, have simpler proofs and do not require an enormous number of experts. Papers: ======= 1. Yoav Freund and Manfred Opper. Drifting games and Brownian motion. Journal of Computer and System Sciences, 64:113--132, 2002. A preliminary version appeared in the Proceedings of the 13th Annual Conference on Computational Learning Theory, 2000. 2. Yoav Freund. An adaptive version of the boost by majority algorithm. Machine Learning, 43(3):293--318, June 2001. A preliminary version appeared in the Proceedings of the 12th Annual Conference on Computational Learning Theory, 1999. 3. Yoav Freund. Boosting a weak learning algorithm by majority. Information and Computation, 121(2):256--285, 1995. Preliminary versions appeared in the Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990, and in the Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory, 1992. 4. Robert E. Schapire. Drifting games. Machine Learning, 43(3):265-291, 2001. 5. N. Cesa-Bianchi, Y. Freund, D.P. Helmbold, D. Haussler, R. Schapire, and M.K. Warmuth How to use expert advice Journal of the ACM, 44(3):427-485, 1997. 6. N. Cesa-Bianchi, Y. Freund, D.P. Helmbold, and M.K. Warmuth On-line prediction and conversion strategies Machine Learning, 25:71-110, 1996. 7. J. Abernethy, J. Langford, M. Warmuth Continuous Experts and the Binning Algorithm COLT 2006 8. Nick Littlestone and Manfred K. Warmuth The weighted majority algorithm. Information and Computation, 108:212-261, 1994. 9. Joel Spencer Ulam's searching game with a fixed number of lies. Theoretical Computer Science, 95(2):307-321, 1992 10. David Blackwell An analog of the minmax theorem for vector payoffs. Pacific J. Math. Volume 6, Number 1 (1956), 1-8. Books: ====== 1. Stuart Russell, Peter Norvig. Artificial Intelligence: A modern approach. Chapters: 3.1-3.5 4.1-4.3 6 7.1-7.6 11.1-11.5 8.1-8.3 13.1-13.6 14.1-14.5 15.1-15.6 16.1-16.3 17.1-17.4 18.1-18.5 20.1-20.3,20.5-20.6 21.1-21.4 26 2. Luc Devroye, Laszlo Gyorfi, Gabor Lugosi A Probabilistic Theory of Pattern Recognition Chapters: 2,4,6.1,6.2,6.7,6.8 7,8,12,13,14,15,16, 28, 29, 30 3. Nicolo Cesa Bianchi, Gabor Lugosi Prediction Learning and Games Chapters: 2,3, 4.1-4.3, 6.1-6.3,6.7-6.9, 7.1-7.3, 7.7 - 7.8, 8, 9.1-9.5, 9.8 - 9.11, all of 10 except 10.6, 11.1 - 11.5

1 0