- talks - lists.cs.princeton.edu

M Ali general exam
by Melissa Lawson 14 May '10

14 May '10

Muneeb Ali will present his research seminar/general exam on Thursday May 20 at 10AM in Room 402. The members of his committee are: Mike Freedman (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. --------------------------------------------------- Title: SWAM: A System for Wide-Area Migration -- Abstract -- The recent interest in cloud services is driven by the industrialization of the datacenter as a reliable provider of computing needs. Datacenters typically employ virtualization technologies (e.g., VMware ESXi and Citrix Xen) to better utilize and manage the physical resources. Virtual machines (VMs) can migrate on-the-fly, from one physical machine to another, to improve utilization, handle load spikes, and/or save power. However, these benefits are typically limited to resources within a single datacenter or, even worse, a single broadcast domain. Wide-area migration can enable resource sharing across physically apart locations, but efficiently migrating VMs over the wide-area is non-trivial. We identify the practical challenges in wide-area VM migration and propose a system, called SWAM, that aims to achieve efficient wide-area migration by reducing the time needed to transfer large (typically 8-10 GB) virtual disk images. SWAM leverages the fact that a VM disk image will have similarities in binary content (e.g., OS or program files) with other VMs running in a datacenter. Often VM images are "cloned" from generic base images and this often leads to high similarity between the binary content of different VMs. Further, a VM may migrate back and forth between the same servers and old versions of the disk image may be available on (or near) the target host. Our primary goal is to reduce the total migration time, especially the time in which the VM is non-responsive. SWAM aims to achieve this goal by a) enabling parallel download of content chunks from local peers within a datacenter, and b) providing mechanisms for quickly detecting and transferring disk image changes (deltas). We present results from a prototype implementation using VM images of Xen and KVM. --Papers-- [1] M. Harchol-Balter and A. B. Downey, "Exploiting process lifetime distributions for dynamic load balancing", ACM Trans. Comput. Syst. 15(3), pp 253-285, Aug. 1997 [2] A. Muthitacharoen, B. Chen, and D. Mazieres, "A low-bandwidth network file system", SOSP 2001, pp 174�187, Banff, Canada, Oct. 2001 [3] C. A. Waldspurger, "Memory resource management in VMware ESX server", OSDI 2002, pp 181�194, Boston, MA, Dec. 2002 [4] C. P. Sapuntzakis, R. Chandra, B. Pfaff, J. Chow, M. S. Lam, and M. Rosenblum, "Optimizing the migration of virtual computers", OSDI 2002, pp 377�390, Boston, MA, Dec. 2002 [5] I. Stoica, D. Adkins, S. Zhuang, S. Shenker, and S. Surana, "Internet indirection infrastructure", SIGCOMM 2002, pp 73-86, Pittsburgh, PA, Aug 2002 [6] P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, and A. War?eld, "Xen and the art of virtualization", SOSP 2003, pp 164�177, Bolton Landing, NY, Oct. 2003 [7] I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. Frans Kaashoek, F. Dabek, and H. Balakrishnan, "Chord: a scalable peer-to-peer lookup protocol for internet applications", IEEE/ACM Trans. Netw. 11(1): 17-32 (2003) [8] C. Clark, K. Fraser, S. Hand, J. G. Hansen, E. Jul, C. Limpach, I. Pratt, and A. Warfield, "Live Migration of Virtual Machines", NSDI 2005, pp 273-286, Boston, MA, May 2005 [9] H. Pucha, D. G. Andersen, and M. Kaminsky, "Exploiting similarity for multi-source downloads using ?le handprints", NSDI 2007, Cambridge, MA, Apr. 2007 [10] D. Gupta, S. Lee, M. Vrable, S. Savage, A. Snoeren, G. Varghese, G. Voelker, and A. Vahdat, "Difference Engine: Harnessing memory redundancy in virtual machines", OSDI 2008, pp 309�322, San Diego, CA, Dec. 2008 --Textbook-- [11] L. L. Peterson and B. S. Davie, Computer Networks, Fourth Edition: a Systems Approach. 2007, Morgan Kaufmann Publishers Inc.

1 0

J Farnham general exam
by Melissa Lawson 14 May '10

14 May '10

Jesse Farnham will present his research seminar/general exam on Thursday May 20 at 2PM in Room 402. The members of his committee are: Mona Singh (advisor), Andrea LaPaugh, and Tom Funkhouser. 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: "Interface Proteins: Investigating Modular Structure of Protein Interaction Networks" Organisms are able to adapt to and survive in different environments due partially to complex networks of interacting proteins within cells. These protein-protein interaction (PPI) networks can be represented as graphs, in which nodes indicate proteins and edges signify physical interactions between proteins. PPI networks are known to be "modular;" that is, a given protein is more likely to interact with similar proteins than with proteins involved in unrelated biological processes. PPI networks contain many "functional modules" of functionally-related, interacting proteins. This work investigates the means by which information flows between separate biological processes through protein interactions. We identify two protein classes: "Interface proteins", which mediate physical interactions between distinct functional modules, and "Insulated proteins," which interact primarily with members of their own functional module. Thus, interface proteins facilitate crosstalk between distinct processes, allowing information to flow through the interaction network. Furthermore, we show that functional modules tend to reuse the same interface proteins to interact with unrelated modules, rather than interacting with each unrelated module through a distinct set of interface proteins. Reading list: Textbooks: Mount, David. Bioinformatics: Sequence and Genome Analysis, 2nd Edition. Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 2nd Edition. (Chapters 22-26: Graph Algorithms) Papers: Banks et al. Organization of Physical Interactomes as Uncovered by Network Schemas. PLoS Computational Biology 4:10 (2008). Banks et al. NetGrep: Fast network schema searches in interactomes. Genome Biology 9:9 (2008). De Lichtenberg et al. Dynamic complex formation during the yeast cell cycle. Science 307 (2005). Fraser H. Modularity and evolutionary constraint on proteins. Nature Genetics 37:4 (2005). Hartwell et al. From molecular to modular cell biology. Nature 402 (1999). Komurov K, and White M. Revealing static and dynamic modular architecture of the eukaryotic protein interaction network. Molecular Systems Biology 3:110 (2007). Missiuro et al. Information Flow Analysis of Interactome Networks. PLoS Computational Biology 5:4 (2009). Taylor et al. Dynamic modularity in protein interaction networks predicts breast cancer outcome. Nature Biotechnology 27:2 (2009). Zotenko et al. Why do hubs in the yeast protein interaction network tend to be essential: Reexamining the connection between the network topology and essentiality. PLoS Computational Biology 4:8 (2008).

1 0

A Venugopalan general exam
by Melissa Lawson 13 May '10

13 May '10

Anuradha Venugopalan will present her research seminar/general exam on Wednesday May 19 at 2PM in Room 402. The members of her committee are: Sanjeev Arora (advisor), Moses Charikar, and Bob Tarjan. 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. --------------------------------------------- Title: Investigating the 3-coloring and Vertex Cover problems Abstract: Mathematical programs and their hierarchies are currently the most commonly used approaches for approximating most combinatorial optimization problems. I shall talk about the existing SDP based algorithms for the coloring and Vertex Cover problems and show instances where these algorithms do not work well. In search of better algorithms for these problems, I shall make some observations about these instances. A recent work by Arora, Barak and Steurer offers better approximation guarantees than the SDP methods for some optimization problems including vertex cover. However, their algorithm uses time exponential in the threshold rank, that is, the number of 'large' eigenvalues of the graph. I shall show bounds on the threshold rank of the instances where the SDPs perform poorly and examine how the new algorithm performs on them. Reading List: -Unique Games on Expanding Constraint Graphs are Easy. : Arora Khot Kolla Steurer Tulsiani Vishnoi '08 -A 2^n^poly(\epsilon)-time Algorithm for Unique Games. : Arora Barak Steurer '10 -New Approximation Guarantee for Chromatic Number. : Arora Chlamtac Charikar '06 -Improved Approximation Guarantees Through Higher Levels of SDP Hierarchies. : Chlamtac Singh '08 -Optimal inapproximability results for max-cut and other 2-variable csps? : Khot Kindler Mossel O'Donnell '07 -SDP Integrality Gaps with Local l_1-Embeddability. : Khot Saket '09 -On semidefinite programming relaxations for graph coloring and vertex cover. : Charikar '02 -Integrality Gaps for Sherali-Adams Relaxations. : Charikar Makarychev Makarychev '09 -Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. : Alekhnovich Arora Tourlakis '05 -On the optimality of the random hyperplane rounding technique for max cut. : Feige Schechtman '02 -On the concentration of eigenvalues of random symmetric matrices. : Alon Krivelevich Vu '02 -A better approximation ratio for the Vertex Cover problem. : George Karakostas '05 -Computational Complexity: A modern approach. Chapters: 1-8 and the PCP chapters. : Arora Barak

1 0

S Li general exam
by Melissa Lawson 13 May '10

13 May '10

Shi Li will present his research seminar/general exam on Wednesday May 19 at 10AM in Room 402. 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. ---------------------------------------------------- Title : Vertex Sparsifiers and Abstract Rounding Algorithms The notion of vertex sparsification (in particular cut-sparsification) is introduced by Moitra. It was shown that for any graph $G = (V, E)$ and a subset of $k$ terminals $K \subset V$, there is a polynomial time algorithm to construct a graph $H = (K, E_H)$ on just the terminal set so that simultaneously for all cuts $(A, K-A)$, the value of the minimum cut in $G$ separating $A$ from $K -A$ is approximately the same as the value of the corresponding cut in $H$. Then approximation algorithms can be run directly on $H$ as a proxy for running on $G$, yielding approximation guarantees independent of the size of the graph. In this work, we consider how well cuts in the sparsifier $H$ can approximate the minimum cuts in $G$, and whether algorithms that use such reductions need to incur a multiplicative penalty in the approximation guarantee depending on the quality of the sparsifier. We give a construction for $O(log k/\log \log k)$-quality cut sparsifers, which matches the best existential result. This is done by solving a mixed covering and matching linear programming derived from the 0-sum game used in the existential proof. We give the first super-constant lower bounds for how well a cut-sparsifier $H$ can simultaneously approximate all minimum cuts in $G$. We prove a lower bound of $\Omega(\log^{1/4} k)$ -- this is polynomially-related to the known upper bound of $O(\log k/\log \log k)$. This is an exponential improvement on the $\Omega(\log \log k)$ bound given in \cite{LM} which in fact was for a stronger vertex sparsification guarantee, and did not apply to cut sparsifiers. If we restrict the cut sparsifers to be from a linear combination of 0-extensions, we can show a better lower bound of $\Omega(\sqrt{log k})$. This restriction is quite reasonable since all known constructions, as well as exsitential proofs, are based on 0-extensions. Despite this negative result, we show that for many natural problems, we do not need to incur a multiplicative penalty for our reduction. Roughly speaking, we show that many graph partitioning problems can be reduced to correspodent problems restricted to trees, at the price of $O(\log k)$ in the approximation ratio. For many problems, this saves an $O(\log k/\log\log k)$ multiplicative factor in the approximation ratio, compared to the algorithm where we first sparsify the graph and then solve the problem on the smaller graph. This result helps to explain the intrinsic robustness of graph partitioning problems - i.e. why does $O(\log k)$ always seem to be the right answer for the approximation ratio? Papers : [AFH+ 04] Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, and Eva Tardos. Approximate classification via earthmover metrics. In SODA '04: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1079-1087, Philadelphia, PA, USA, 2004. Society for Industrial and Applied Mathematics. [CKR01] Gruia Calinescu, Howard Karloff, and Yuval Rabani. Approximation algorithms for the 0-extension problem. In SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 8-16, Philadelphia, PA, USA, 2001. Society for Industrial and Applied Mathematics. [FHRT03] Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, and Kunal Talwar. An improved approximation algorithm for the 0-extension problem. In SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 257-265, Philadelphia, PA, USA, 2003. Society for Industrial and Applied Mathematics. [KKL88] J. Kahn, G. Kalai, and N. Linial. The influence of variables on boolean functions. In SFCS '88: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 68-80, Washington, DC, USA, 1988. IEEE Computer Society. [Moi09] Ankur Moitra. Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In FOCS, pages 3-12, 2009. [FRT03] Fakcharoenphol, Jittat, Rao, Satish, and Talwar, Kunal: A tight bound on approximating arbitrary metrics by tree metrics, STOC '03, ACM, 448-455, 2003 [AHK05] Arora, Sanjeev, Hazan, Elad, and Kale, Satyen: The multiplicative weights update method: a meta algorithm and applications, 2005 [You01] Young, Neal E.: Sequential and Parallel Algorithms for Mixed Packing and Covering, In 42nd Annual IEEE Symposium on Foundations of Computer Science, 538-546, 2001 Books : Computational complexity, a modern approach, by Sanjeev Arora and Boaz Barak, 2009. Chapters : 0 ~ 9, 11, 14, 19, 22 Appromixation Algorithms, by Vijay V. Vazirani, 2001 Chapters : 4, 11, 12, 15, 18 ~ 21, 26

1 0

Xiaojuan Ma FPO
by Melissa Lawson 13 May '10

13 May '10

Xiaojuan Ma will present her FPO on Thursday May 20 at 11AM in Room 302. The members of her committee are: Perry Cook, advisor; Christiane Fellbaum and Marilyn Tremaine (Rutgers), readers; Szymon Rusinkiewicz and Ken Steiglitz, nonreaders. A copy of her thesis, "Communication Beyond Words: Multimedia Approaches to Bridging Language Disabilities and Barriers", is on display in room 310. Everyone is invited to attend her talk.

1 0

Jordan Boyd-Graber FPO
by Melissa Lawson 13 May '10

13 May '10

Jordan Boyd-Graber will present his FPO on Wednesday May 19 at 11AM in Room 302. The members of his committee are: David Blei, advisor; Christiane Fellbaum and Ryan McDonald (Google), readers; Rob Schapire and Dan Osherson (PSY), nonreaders. A copy of his thesis, "Adding Linguistic Understanding to Topic Models", is on display in Room 310. Everyone is invited to attend his talk.

1 0

R Ge general exam
by Melissa Lawson 12 May '10

12 May '10

Rong Ge will present his research seminar/general exam on Tuesday May 18 at 2PM in Room 402. The members of his committee are: Sanjeev Arora (advisor), Boaz Barak, 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. ------------------------------------------------ Title: Computational Complexity and Information Asymmetry in Financial Products Abstract: Traditional economics argues that financial derivatives, like CDOs and CDSs, ameliorate the negative costs imposed by asymmetric information. This is because securitization via derivatives allows the informed party to find buyers for less information-sensitive part of the cash flow stream of an asset (e.g., a mortgage) and retain the remainder. In this paper we show that this viewpoint may need to be revised once computational complexity is brought into the picture. Using methods from theoretical computer science this paper shows that derivatives can actually amplify the costs of asymmetric information instead of reducing them. Note that computational complexity is only a small departure from full rationality since even highly sophisticated investors are boundedly rational due to a lack of requisite computational resources. Reading List: Books: Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 2009. Papers: Benny Applebaum, Boaz Barak, and Avi Wigderson. Public key cryptography from different assumptions. Available from the authors' web pages. To appear in STOC'10. Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uri Feige, and Aravindan Vijayaraghavan. Detecting high log-density: An o(n^{1/4})-approximation for densest k-subgraph. Manuscript in preparation, to appear in STOC'10. U. Feige, D. Peleg, and G. Kortsarz. The dense k-subgraph problem. Algorithmica, 29(3):410-421, 2001. S. Khot. Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique. In FOCS, pages 136-145, 2004. G.A. Akerlof. The market for "lemons": quality uncertainty and the market mechanism. The quarterly journal of economics, pages 488-500, 1970. P.M. DeMarzo. The pooling and tranching of securities: A model of informed intermediation. Review of Financial Studies, 18(1):1-35, 2005. M.K. Brunnermeier. Deciphering the 2007-08 liquidity and credit crunch. Journal of Economic Perspectives, 23(1):77-100, 2008

1 0

A Boyko general exam
by Melissa Lawson 12 May '10

12 May '10

Aleksey Boyko will present his research seminar/general exam on Tuesday May 18 at 10 AM in Room 402. The members of his committee are: Tom Funkhouser (advisor), Szymon Rusinkiewicz, and Adam Finkelstein. 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: Range scan data provides high resolution 3D information about the real life environment. Urban scans in the form of point clouds are becoming more available. However, point clouds are both noisy, very large, and they do not have semantic labels that associate each point of the scanned surfaces to a specific object. Our goal is to provide means for a meaningful classification of large scale point clouds derived from urban environment range scans. In my talk I will focus on two classes of objects. An important category of objects in an urban landscape consists of roads, streets and driveways. This category represents potentially the largest in size class of objects in a city - the road network. At the same time this class provides a context for other objects, both of a large and small scale - it separates the city into blocks and defines the position of large variety of small scale objects. In order to provide such context it is desirable to have a precise separation of the road surface from the sidewalks, which delimit the road surface. We present an algorithm that takes advantage of available online map information and uses dynamic contours (snakes) to provide an accurate extraction of points belonging to the road surface from the rest of the points. Addressing the rest of the objects we can separate them into large scale objects, such as buildings, and small-scale objects. Due to noisiness of the point cloud data it is harder to address the question of recognition of small-scale objects. [Golovinskiy, et al. 2009] offer numeric evaluation of how well supervised machine learning algorithms are at automatic classification of small objects in a point cloud of an urban environment. We research how making the classification user-guided can improve the rates and accuracy of the classification. We employ online learning (user-guided) and active learning (computer-guided) approach and show that giving user real-time control over the process of learning improves both the rate and the correctness of classification over blind selection of the training set. Reading list: [1] R. J. Campbell and P. J. Flynn. A survey of free-form object representationand recognition techniques. Computer Vision and Image Understanding, 81 doi: 10.1006/cviu.2000.0889 URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.1720&rep=rep1&t… [2] M. Carlberg, J. Andrews, P. Gao, and A. Zakhor. Fast surface reconstruction and segmentation with ground-based and airborne lidar range data. 3DPVT, 2008. URL http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-5.pdf [3] A. Frome, D. Huber, R. Kolluri, T. Bulow, and J. Malik. Recognizing objects in range data using regional point descriptors. ECCV doi: 10.1007/b97871 URL http://www.springerlink.com/content/d4ukq18fpbfe9la6/fulltext.pdf [4] A. Golovinskiy, V. G. Kim, and T. Funkhouser. Shape-based recognition of 3d point clouds in urban environments. ICCV, Sept. 2009. URL http://www.cs.princeton.edu/gfx/pubs/Golovinskiy_2009_SRO/paper.pdf [5] D. Hearn and M. Baker. Computer Graphics with OpenGL. Pearson PrenticeHall, 3 edition, 2004. URL http://www.pearsonhighered.com/educator/product/Computer-Graphics-with-Open… 6.page. [6] A. Jaakkola, J. Hyyppa, H. Hyyppa, and A. Kukko. Retrieval algorithms for road surface modelling using laser-based mobile mapping. Sensors, 8, 2008. doi: 10.3390/s8095238 URL http://www.mdpi.org/sensors/papers/s8095238.pdf [7] A. E. Johnson and M. Hebert. Using spin images for effcient object recognition in cluttered 3d scenes. IEEE PAMI, 1999. URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.8816&rep=rep1&t… [8] B. C. Matei, Y. Tan, H. S. Sawhney, and R. Kumar. Rapid and scalable 3d object recognition using lidar data. SPIE, 6234, 2006. doi: 10.1117/12.666235 URL http://spiedl.aip.org/getpdf/servlet/GetPDFServlet?filetype=pdf&id=PSISDG00… 1000001&idtype=cvips&prog=normal. [9] H. Mayer, I. Laptev, and A. Baumgartner. Multi-scale and snakes for automatic road extraction. ECCV, 1998. URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.8855&rep=rep1&t… [10] R. Schnabel, R. Wahl, R. Wessel, and R. Klein. Shape recognition in 3d point clouds. The 16-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision, 2008. URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.2344&rep=rep1&t… [11] B. Settles. Active learning literature survey. 2009. URL http://pages.cs.wisc.edu/~bsettles/active-learning/ [12] S.P.Clode, F.Rottensteiner, P.Kootsookos, and E.Zelniker. Detection and vectorization of roads from lidar data. PhEngRS, May 2007. URL http://www.asprs.org/publications/pers/2007journal/may/2007_may_517-535.pdf [13] G. Vosselman and Z. Liang. Detection of curbstones in airborne laser scanning data. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 38:3/W8, 2009. URL http://www.itc.nl/personal/vosselman/papers/vosselman2009.paris.pdf =========

1 0

1:30 Mon May 17 talk on network virtualization in CS 105
by Jennifer Rexford 11 May '10

11 May '10

Speaker: Dr. Sanjoy Paul, Infosys, Associate Vice President Title: Network Virtualization applied to the Network of a Communication Service Provider for Enabling Novel Services in Vertical Sectors Date/time: 1:30-2:30pm on Monday May 17 Location: CS 105 (small auditorium) Abstract: Communication technology has advanced significantly over the last decade enabling people to communicate anytime from anywhere using a multiplicity of devices. However, the power of this advancement in communication technology has hardly been leveraged in traditional services industry. Specifically, the vertical service providers, such as the Health Care industry, the Banking industry, the Education industry, and others who require network-based services to efficiently conduct their business reducing their operational expenses, and to provide novel value-added services to their customers generating additional revenue, have hardly been able to leverage the power of the network to their advantage. In the talk, I will describe several applications from the services industry that can be built on a platform (referred to as Network as a Service or NaaS platform) based on the concept of network virtualization and shows how various parties involved in providing the services are economically incentivized to make them feasible in real life. The NaaS platform enables Communication Service Providers (CSPs) to work collaboratively with Vertical Service Providers (VSPs) to offer novel services leveraging their existing network infrastructure through the techniques of network virtualization. This solution enables CSPs to generate new revenue without additional capital expenditure, and in addition, also enables VSPs to generate additional revenue via novel value-added service offerings to their customers without incurring any capital expenditure either. Thus, this model of offering services provides a win-win value proposition to both CSPs as well as to VSPs. NaaS Platform is being built at Infosys Technologies Limited. In course of my presentation, I’ll describe a high-level architecture of the platform and discuss how various functional blocks in the architecture are used synergistically to deliver a novel service called On Demand Health Care (ODHC). Bio: Sanjoy Paul (sanjoy_paul(a)infosys.com) is Associate Vice President, General Manager-Research and Head of Convergence Lab at Infosys Technologies Limited where he heads research and innovation in the field of Communications, Media and Entertainment. Prior to that, he was a Research Professor at WINLAB, Rutgers University, and Founder of RelevantAd Technologies Inc. Before that Sanjoy spent five years as the Director of Wireless Networking Research at Bell Labs, Lucent Technologies, and as the CTO of two start-up companies (Edgix and WhenU) based in New York. In a previous tenure at Bell Labs as a Distinguished Member of Technical Staff, Sanjoy was the chief architect of Lucent's IPWorX Caching and Content Distribution product line. Sanjoy has authored a book on Multicasting, published over 100 papers in International Journals and refereed Conference Proceedings, authored over 80 US patents (28 granted, 50+ pending), and is the co-recipient of 1997 William R. Bennett award from IEEE Communications Society for the best original paper in IEEE/ACM Transactions on Networking. He holds a Bachelor of Technology degree from IIT Kharagpur, India, an M.S and a Ph.D. degree from the University of Maryland, College Park, and an MBA from the Wharton Business School, University of Pennsylvania. Sanjoy is a Fellow of IEEE and a Member of the ACM.

1 0

A Soviani preFPO
by Melissa Lawson 11 May '10

11 May '10

Adrian Soviani will present his preFPO on Monday May 17 at 4PM in Room 402. The members of his committee are: J.P. Singh, advisor; Kai Li and David August, readers; Brian Kernighan and Ken Steiglitz, nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------------------------------- Building scalable parallel applications remains a difficult task due to implementation complexity, performance portability, and inability to understand hidden costs and bottlenecks. Specific machine architectures and software layers further influence application efficiency and performance transparency, making optimization a time consuming burden. The parallel programming model has a great impact on addressing these issues and reaching a good tradeoff between implementation effort and application efficiency. This thesis presents a hybrid SPMD - Coarse Grain Dataflow programming model (CGD) that describes data and task parallelism at high level. CGD applications are specified as dependencies between computation modules and data distributions while communication and synchronization are added automatically and optimized for specific architectures. We claim the CGD model can make application development and design space exploration simpler compared to message passing, at the same time providing similar or better performance. Results on the 128 CPU SGI Altix 4700 show our optimized CGD FT is 27% faster than the original NPB 2.3 MPI implementation, the optimized CGD stencil has a 41% advantage over handwritten MPI, while the CGD Barnes-Hut 1M particle benchmark is 15% faster than the pthreads Splash2 implementation. CGD takes advantage of its dataflow semantics and explicit distribution rules to automatically schedule computations and insert, aggregate and overlap communication, simplifying application development and optimization. E.g., the CGD NPB FT implementation requires 85 lines of dataflow and 700 lines of sequential C++ code, while the original MPI implementation has 1260 lines of code and exhibits poorer performance portability.

1 0