- talks - lists.cs.princeton.edu

Friday Feb 22 noon: Ian Buck->John Danskin, nVidia, "GPU Computing"
by Adam Finkelstein 22 Feb '08

22 Feb '08

The talk is as planned at noon; however, due to a canceled flight we have a change of speaker and slight change in emphasis: Speaker: John Danskin Title: NVIDIA GeForce 8800 Graphics Processor: development and direction Time/Place: Today, noon, Computer Science Bldg, room 302 Abstract: The GeForce 8800 and its derivative architectures are the fastest available graphics processors. In an architectural departure, they are significantly more flexible than previouos processors. In this talk Dr. Danskin will discuss our goals for the 8800, the decision making process, new architectural features, performance, and some challenges for the future. Dr. Danskin is Vice President of GPU Architecture at NVIDIA, Chief Architect for the GeForce 8800 GPU, and holds a PhD in Computer Science from Princeton University. On Wed, Feb 20, 2008 at 10:58 PM, Adam Finkelstein <af(a)cs.princeton.edu> wrote: > Talk announcement: > > Speaker: Ian Buck, nVidia > Title: GPU Computing > Time/Place: Friday, noon, Computer Science Bldg, room 302 > > Abstract: > > Many researchers have observed that general purpose computing with > programmable graphics hardware (GPUs) has shown promise to solve many of > the world's compute intensive problems, many orders of magnitude faster > the conventional CPUs. The challenge has been working within the > constraints of a graphics programming environment to leverage this huge > performance potential. GPU computing with CUDA is a new approach to > computing where hundreds of on-chip processor cores simultaneously > communicate and cooperate to solve complex computing problems, > transforming the GPU into a massively parallel processor. The NVIDIA > C-compiler for the GPU provides a complete development environment gives > developers the tools they need to solve new problems in > computation-intensive applications such as product design, data > analysis, technical computing, and game physics. In this talk, I will > provide a brief history of computing with GPUs, how CUDA can solve > compute intensive problems, and where GPU computing will be going in the > future. > > Bio: > > Ian Buck completed his Ph.D. at the Stanford Graphics Lab in 2004. His > thesis was titled "Stream Computing on Graphics Hardware," researching > programming models and computing strategies for using graphics hardware > as a general purpose computing platform. His work included developing > the "Brook" software toolchain for abstracting the GPU as a general > purpose streaming coprocessor. Ian received is B.S.E from Princeton and > was a proud member of the Princeton CS Graphics Group. He currently > works for NVIDIA as the GPU-Compute software manager. >

1 0

Z Barutcuoglu preFPO
by Melissa M Lawson 21 Feb '08

21 Feb '08

Zafer Barutcuoglu will present his preFPO on Thursday February 28 at 1:30 PM in Room 402. The members of his committee are: Rob Schapire (advisor); Olga Troyanskaya and David Blei (readers); Mona Singh and Fei-Fei Li (non-readers). Everyone is invited to attend his talk. His abstract follows below. ---------------------------------- Classification problems encountered in real-life applications often have domain-specific structural information available on the measured data, which cannot be readily accommodated by conventional machine learning algorithms. Ignoring the structure and blindly running a conventional algorithm on the numerical data can compromise the quality of solutions. This thesis provides answers to two such complementary settings; one where there is a hierarchy among multiple class labels (output structure), and one where the input features are known to be sequentially correlated (input structure). Probabilistic graphical models are used to encode the dependencies, and efficient Bayesian inference algorithms are used for parameter estimation. While both scenarios are motivated by real bioinformatics problems, namely gene function prediction and aneuploidy-based cancer classification, they have applications in other domains as well, such as computer graphics, music, and text classification.

1 0

Friday Feb 22 noon: Ian Buck, nVidia, "GPU Computing"
by Adam Finkelstein 20 Feb '08

20 Feb '08

Talk announcement: Speaker: Ian Buck, nVidia Title: GPU Computing Time/Place: Friday, noon, Computer Science Bldg, room 302 Abstract: Many researchers have observed that general purpose computing with programmable graphics hardware (GPUs) has shown promise to solve many of the world's compute intensive problems, many orders of magnitude faster the conventional CPUs. The challenge has been working within the constraints of a graphics programming environment to leverage this huge performance potential. GPU computing with CUDA is a new approach to computing where hundreds of on-chip processor cores simultaneously communicate and cooperate to solve complex computing problems, transforming the GPU into a massively parallel processor. The NVIDIA C-compiler for the GPU provides a complete development environment gives developers the tools they need to solve new problems in computation-intensive applications such as product design, data analysis, technical computing, and game physics. In this talk, I will provide a brief history of computing with GPUs, how CUDA can solve compute intensive problems, and where GPU computing will be going in the future. Bio: Ian Buck completed his Ph.D. at the Stanford Graphics Lab in 2004. His thesis was titled "Stream Computing on Graphics Hardware," researching programming models and computing strategies for using graphics hardware as a general purpose computing platform. His work included developing the "Brook" software toolchain for abstracting the GPU as a general purpose streaming coprocessor. Ian received is B.S.E from Princeton and was a proud member of the Princeton CS Graphics Group. He currently works for NVIDIA as the GPU-Compute software manager.

1 0

Speaker Today - 4:15pm
by Ginny Hogan 19 Feb '08

19 Feb '08

Christos Papadimitriou, UC Berkeley will present his talk "The Algorithmic Lens: How the Computational Perspective is Transforming the Sciences" today at 4:15pm Computer Science Room 105.

1 0

/@rts: Tuesday, 2/19 - David Stork - "When Computers Look at Art: Computer Vision and Image Analysis in Humanistic Studies of the Visual Arts"
by Perry R Cook 18 Feb '08

18 Feb '08

Hey all, Please forward to any friends you might have that might be interested in art, art history, art fraud, etc. David is an old friend and collaborator, and always gives really entertaining talks. For the last couple of years he's been embroiled in the controversy about whether the masters used machines and optics to make their perspective drawings and paintings. David is the "Stork" in Duda, Hart and Stork, "Pattern Classification, 2nd edition" This talk is certain to have lots of computer vision, machine learning, and art in it. PRC 2/19 - David Stork - "When Computers Look at Art: Computer Vision and Image Analysis in Humanistic Studies of the Visual Arts" "When Computers Look at Art: Computer Vision and Image Analysis in Humanistic Studies of the Visual Arts" scientist David Stork - Tuesday, February 19, 4:30 pm 185 Nassau Street, James Stewart Theater New computer methods have been used to shed light on a number of recent controversies in the study of art. For example, computer fractal analysis has been used in authentication studies of paintings attributed to Jackson Pollock recently discovered by Alex Matter. Computer wavelet analysis has been used for attribution of the contributors in Perugino's Holy Family. An international group of computer and image scientists is studying the brushstrokes in paintings by van Gogh for detecting forgeries. Sophisticated computer analysis of perspective, shading, color and form has shed light on David Hockney's bold claim that as early as 1420, Renaissance artists employed optical devices such as concave mirrors to project images onto their canvases. How do these computer methods work? What can computers reveal about images that even the best-trained connoisseurs, art historians and artist cannot? How much more powerful and revealing will these methods become? In short, how is computer image analysis changing our understanding of art? This profusely illustrate lecture for non-scientists will include works by Jackson Pollock, Vincent van Gogh, Jan van Eyck, Hans Memling, Lorenzo Lotto, and others. You may never see paintings the same way again. Bio: Dr. David G. Stork is Chief Scientist of Ricoh Innovations and Visiting Scholar at Stanford University, where he has held appointments, taught, and sat on dissertation committees frequently over the last 17 years in the departments of Computer Science, Electrical Engineering, Statistics, Psychology and Art and Art History. He has published in optics and art for over two decades, including Seeing the Light: Optics in Nature, Photography, Color, vision and Holography (Wiley), the leading textbook on optics in the arts. A graduate in physics of the Massachusetts Institute of Technology and the University of Maryland at College Park, he also studied art history at Wellesley College and was Artist-in-Residence through the New York State Council of the Arts. His anamorphic photographs and graphics (based on late Renaissance methods) have appeared in small art journals as well as Optics and Photonics News and Scientific American magazine. He has taught courses such as ''Light, color and visual phenomena,'' ''The physics of aesthetics and perception,'' and ''Optics, perspective and Renaissance painting'' over the last quarter century variously at leading liberal arts and research universities such as Wellesley College, Swarthmore College, Clark University and Stanford University. He is a member of the International Foundation for Art Research and co-editor of Computer Image Analysis in the Study of Art (SPIE 2008), the first symposium volume on the topic. He holds 35 US patents and has published numerous technical papers on human and machine learning and perception of patterns, physiological optics, image understanding, concurrency theory, theoretical mechanics, optics, image processing, as well as five books, including Pattern Classification (2nd ed.), the world's all-time best-selling textbook in the field, translated into three languages and used in courses in over 250 universities worldwide. He has served on the editorial boards of five international journals and has delivered over 45 plenary, invited or distinguished lectures at universities and conferences (atop nearly 200 traditional invited colloquia and seminars). He created the PBS television documentary 2001: HAL's Legacy, based on his book HAL's Legacy: 2001's Computer as Dream and Reality (MIT). He was one of four scientists invited to comment on Mr. Hockney's theory at the December 2001 Art and Optics Symposium at the New York Institute for the Humanities and one of two scientists invited to present a lecture in the symposium exploring the possible use of optics by Renaissance painters at the Optical Society of America's Annual Meeting in Rochester, NY, October 2004. URLs: http://www.diatrope.com/stork/FAQs.html

1 0

Distinguished colloquium on Tues Feb 19: Christos Papadimitriou
by Sanjeev Arora 17 Feb '08

17 Feb '08

Christos Papadimitriou of UC Berkeley will speak in our Distinguished Colloquium series on Tues Feb 19 at 4:15pm. He gave this talk as a plenary speaker at FCRC and also at several depts around the country. I recommend it highly. Please let me know if you would like to meet with Christos on Mon or Tues afternoon. Sanjeev --- *The Algorithmic Lens: How the Computational Perspective is Transforming the Sciences * *Christos Papadimitriou* UC Berkeley Computational research transforms the sciences (physical, mathematical, life or social) not just by empowering them analytically, but mainly by providing a novel and powerful perspective which often leads to unforeseen insights. Examples abound: quantum computation provides the right forum for questioning and testing some of the most basic tenets of quantum physics, while statistical mechanics has found in the efficiency of randomized algorithms a powerful metaphor for phase transitions. In mathematics, the P vs. NP problem has joined the list of the most profound and consequential problems, and in economics considerations of computational complexity revise predictions of economic behavior and affect the design of economic mechanisms such as auctions. Finally, in biology some of the most fundamental problems, such as understanding the brain and evolution, can be productively recast in computational terms. My talk is structured around eight vignettes exemplifying this pattern.

1 0

Y Makarychev FPO
by Melissa M Lawson 06 Feb '08

06 Feb '08

Yury Makarychev will present his FPO on Tuesday February 12 at 1PM in room 302. The members of his committee are Moses Charikar, advisor; Bernard Chazelle and Assaf Naor (NYU), readers; Boaz Barak and Rob Schapire, nonreaders. A copy of his thesis, "Approximation Algorithms for Constraint Satisfaction Problems", is on display in room 310. Everyone is welcome to attend his talk.

1 0

Anirudh Badam general exam
by Melissa M Lawson 16 Jan '08

16 Jan '08

Anirudh Badam will present his research seminar/general exam on Thursday January 24 at 1PM 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: Web Caching is the caching of web documents in order to reduce bandwidth usage, server load and perceived download time for the web object download. A web cache stores copies of web objects when they are accessed through cache. The stored objects can be used to server subsequent requests. Web caching has been extensive studied and a plethora of techniques exist today. Solutions are based on developing good cache replacement algorithms which are used to figure out storing what objects can provide more savings, improving file systems which usually involves optimizing file systems for frequent additions, deletions and accesses, etc. However, the existing solutions have scalability problems with respect to memory. Some techniques impose lower bounds on the amount of memory needed for a web cache. Other techniques have huge virtual memory requirements leading to frequent swapping in low memory systems. Cache replacement policies need metadata for better functionality and file systems need huge lists or trees (preferably in memory) for any access to files that it stores. This requires the physical memory to scale as an increasing function of the number of web objects that the cache can store. This restricts not only the number of objects that can be stored in a web cache but also the economical affordability of the system. Hence, we propose a web caching mechanism, the HashCache, a file system optimization approach, which uses hashing to reduce the physical memory requirements. HashCache uses hashing techniques to map files to the disk locations. Hashing makes the cache maintenance and usage to be mostly memory less. Hashing mechanism also allows more flexible mechanisms for metadata maintenance and does not impose lower bounds on the requirements of memory to provide performance guarantees. HashCache exploits the distribution of sizes and contents of web objects to enable an efficient usage of the secondary storage (optimal bucket sizes). Also, with the help of experiments on an implementation of the HashCache architecture we show the usefulness of HashCache. 1. Computer Networks by Peterson and Davie 2. Operating System Concepts by Silberschatz, Galvin and Gagne 3. P. Danzig, R. Hall, and M. Schwartz, A Case for Caching File Objects inside Internetworks, Tech. Report CU-CS-642-93, Dept. of Computer Science, Univ. of Colorado, Boulder, Colo., 1993. 4. S. Acharya and S.B. Zdonik, An Efficient Scheme for Dynamic Data Replication, Tech. Report CS-93-43, Dept. of Computer Science, Brown Univ., Providence, R.I., 1993. 5. M.M. Recker and J.E. Pitkow, Predicting Document Access in Large, Multimedia Repositories, Tech. Report VU-GIT-94-35, Graphics, Visualization, and Usability Center, Georgia Tech, Atlanta, 1994. 6. D.D. Sleator, R.E. Trajan, Amortized efficiency of list update and paging rules, Commun. ACM, Vol. 2, p 202-208, 1985. 7. D. Wessels, K. Claffy, ICP and the Squid Web Cache, IEEE JSAC, Vol. 16, No. 3. 1998. 8. H. Bahn, S.H. Noh, L. Min, K. Koh, Using Full Reference History For Efficient Document Replacement In Web Caches, In Proc. USITS, Colorado, Boulder, 1999. 9. E.P. Markatos, M.G.H. Katevenis, D. Pnevmatikatos, M. Flouris, Secondary Storage Management For Web Proxies, In Proc Usits 99, Boulder, Colorado, 1999. 10. A. Sweeney, Scalability in the XFS File System, In Proc USENIX 96, San Diego, California, 1996. 11. L. Breslau, P. Cao, L. Fan, G. Phillips, Scott Shenker, Web Caching and Zipf-like Distributions: Evidence and Implications , In Proc. IEEE Infocom, 1999. 12 C. Agarwal, J. L. Wolf, P. S. Yu, Caching on the World Wide Web, IEEE Tran. Knowledge and Data Engineering, Vol. 11, No. 1, January, 1999.

1 0

Martin Suchara General Exam
by Melissa M Lawson 15 Jan '08

15 Jan '08

Martin Suchara will present his research seminar/general exam on Monday January 21 at 1PM in Room 402. The members of his committee are: Jennifer Rexford (advisor), Larry Peterson, and David August. 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. Securing Interdomain Routing in Small Groups Although the Internet's routing system has serious security vulnerabilities, none of the existing proposals for a secure variant of BGP has been successfully deployed in practice. This is not surprising since deploying protocols that require the cooperation of tens of thousands of independently-operated networks is problematic. Instead, we argue that small groups should be the basis for securing BGP. We offer a new design in which interdomain routing is secured by as few as 5-10 participating ASes, adding to the effort to secure BGP incrementally. Existence of well accepted cryptographic protocols that secure integrity and confidentiality of data delivery allows us to focus primarily on securing availability of communication. We conduct extensive simulations on a realistic Internet topology, and identify conditions for small groups to be effective. Even though the non-participants outnumber the group members by several orders of magnitude, 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 enlisting 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 the proposed technique allows small groups to secure interdomain routing efficiently. Reading List 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. Gao, "On inferring autonomous systems relationships in the Internet," IEEE/ACM Transactions on Networking, Vol. 9, No. 6, pp. 733-745, Dec. 2001. [3] O. Nordstrom, and C. Dovrolis, "Beware of BGP attacks," ACM SIGCOMM Computer Communication Review, Vol. 34, No. 2, pp. 1-8, Apr. 2004. [4] R. White, "Securing BGP through secure origin BGP," The Internet Protocol Journal, Vol. 6, No. 3, pp. 15-22, Sep. 2003. [5] S. Kent, C. Lynn, and K. Seo, "Secure Border Gateway Protocol (Secure-BGP)," IEEE Journal on Selected Areas in Communications, Vol. 18, No. 4, pp. 582-592, Apr. 2000. [6] Y. Hu, A. Perrig, and M. Sirbu, "SPV: Secure path vector routing for securing BGP," ACM SIGCOMM Computer Communication Review, Vol. 34, No. 4, pp. 179-192, Aug. 2004. [7] H. Chan, D. Dash, A. Perrig, and H. Zhang, "Modeling adoptability of secure BGP protocols," ACM SIGCOMM Computer Communication Review, Vol. 36, No. 4, pp. 279-290, Aug. 2006. [8] J. Karlin, S. Forrest, and J. Rexford, "Pretty Good BGP: Improving BGP by cautiously adopting routes," in Proc. IEEE International Conference on Network Protocols, pp. 290-299, Nov. 2006. [9] D. Wendlandt, I. Avramopoulos, D. Andersen, and J. Rexford, "Don't secure routing protocols, secure data delivery," in Proc. ACM SIGCOMM HotNets Workshop, Nov. 2006. [10] D. Andersen, H. Balakrishnan, F. Kaashoek, and R. Morris, "Resilient overlay networks," in Proc. 18th ACM Symposium on Operating System Principles, Vol. 35, No. 5, pp. 131-145, Oct. 2001.

1 0

Minlan Yugeneral exam
by Melissa M Lawson 15 Jan '08

15 Jan '08

Minlan Yu will present her research seminar/general exam on Monday January 21 at 10AM in Room 402. The members of her committee are: Jennifer Rexford (advisor), Kai Li, and David August. 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. Rethinking Virtual Network Embedding: Substrate Support for Path Splitting and Migration Abstract: Network virtualization is a powerful way to run multiple architectures or experiments simultaneously on a shared infrastructure. However, making efficient use of the underlying resources requires effective techniques for virtual network embedding --- mapping each virtual network to specific nodes and links in the substrate network. Since the general embedding problem is computationally intractable, past research has focused on two main approaches: (i) significantly restricting the problem space to allow efficient solutions or (ii) proposing heuristic algorithms that do not use the substrate resources efficiently. In this paper, we advocate a different approach: rethinking the design of the substrate network to enable simpler embedding algorithms and more efficient use of resources, without restricting the problem space. In particular, we simplify virtual link embedding by: i) allowing the substrate network to split a virtual link over multiple substrate paths and ii) employing path migration to periodically re-optimize the utilization of the substrate network. We also explore node-mapping algorithms that are customized to common classes of virtual-network topologies. Our simulation experiments show that path splitting, path migration, and customized embedding algorithms enable a substrate network to satisfy a much larger mix of virtual networks. A paper in submission about this work is available online at http://www.cs.princeton.edu/~minlanyu/embed-CCR.pdf <http://www.cs.princeton.edu/%7Eminlanyu/embed-CCR.pdf> Book: L. Peterson, and B. Davie, "Computer Networks: A Systems Approach", Morgan Kaufmann, 3e, 2003 Papers: D. Clark, "The Design Philosophy of the DARPA Internet Protocols," ACM SIGCOMM, August 1988 J.Saltzer, D.Reed and D.Clark, "End-to-End Arguments in System Design", ACM Transactions on Computer Systems, Nov 1984. T. Anderson, L. Peterson, S. Shenker, and J. Turner, "Overcoming the Internet impasse through virtualization," IEEE Computer Magazine, vol. 38, no. 4, pp. 34-41, 2005. 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. N. Feamster, L. Gao, and J. Rexford, "How to lease the Internet in your spare time," SIGCOMM Comput. Commun. Rev., vol. 37, no. 1, pp. 61-64, 2007. Y. Zhu and M. Ammar, "Algorithms for assigning substrate network resources to virtual network components," in Proc. IEEE INFOCOM, 2006. R. Ricci, C. Alfeld, and J. Lepreau, "A solver for the network testbed mapping problem," ACM Computer Communication Review, vol. 33, no. 2, pp. 65-81, 2003. J. Fan and M. Ammar, "Dynamic topology configuration in service overlay network: A study of reconfiguration policies", in Proc. IEEE INFOCOM, 2006. J. Lu and J. Turner, "Efficient mapping of virtual networks onto a shared substrate", Washington University, Technical Report WUCSE-2006-35, 2006. N. G. Duffield, P. Goyal, A. Greenberg, P. Mishra, K. K. Ramakrishnan, and J. E. van der Merwe, "Resource management with hoses: Point-to- cloud services for virtual private networks," IEEE/ACM Trans. Netw., vol. 10, no. 5, pp. 679-692, 2002.

1 0