- talks - lists.cs.princeton.edu

Wenhao Jia (ELE) presents FPO "Analysis and Optimization Techniques for Massively Parallel Processors" Wednesday, October 8 at 3pm, Equad Room J401
by Nicki Gotsis 01 Oct '14

01 Oct '14

Wenhao Jia FPO Date and Location: Wednesday, October 8 at 3pm, Equad Room J401 Thesis Committee: Co-advisors: Margaret Martonosi and Kelly Shaw; Reader: Niraj Jha; Non-readers: David August and Sharad Malik Thesis Title: Analysis and Optimization Techniques for Massively Parallel Processors Thesis Abstract: Heterogeneous parallelism has emerged as a widespread computing paradigm in the past decade or so. In particular, massively parallel processors such as graphics processing units (GPUs) have become the prevalent throughput computing element in heterogeneous systems. However, GPUs are difficult to program and design, primarily due to developers' general unfamiliarity with GPUs, a lack of hardware resource virtualization, and inadequate tailoring of conventionally designed components--such as general-purpose caches--to the massively parallel nature of GPU workloads. To overcome these challenges, this thesis proposes statistical analysis techniques and software and hardware optimizations that improve the performance, power efficiency, and programmability of GPUs. These proposals make it easier for programmers and designers to produce optimized GPU software and hardware designs. The first part of the thesis describes how statistical analysis can help users explore a GPU software or hardware design space with performance or power as the metric of interest. In particular, two fully automated tools--linear regression-based Stargazer and regression tree-based Starchart--are developed and presented. They help identify important design parameters and automate design decisions, while saving design exploration time by 300-3000 times compared to exhaustive approaches. Then, the second part of the thesis proposes two compile-time algorithms to automatically make two key GPU software design decisions: cache configuration and thread block size selection. The first algorithm uses instruction-level memory access pattern analysis and cache control to improve the performance benefits of caching from 5.8% to 18%. The second algorithm runs programs with thread counts estimated to trigger performance saturation, reducing GPU core resource usage by 27-62% while improving performance by 5-10%. Finally, the third part of the thesis proposes and evaluates the memory request prioritization buffer (MRPB). MRPB uses request reordering to reduce cache thrashing and uses cache bypassing to reduce resource stalls, improving performance by 1.3-2.7 times and easing GPU programming. In summary, using GPUs as an example, the high-level statistical tools and the more focused software and hardware studies presented in this thesis demonstrate how to use automation techniques to effectively improve the performance, power efficiency, and programmability of emerging heterogeneous computing platforms.

1 0

IEEE SSCS Distinguished Lecture Series at Princeton - October 16, 2014 - E-Quad B205
by Nicole E. Wagenblast 01 Oct '14

01 Oct '14

S ent on behalf of Prof. Kaushik Sengupta IEEE SSCS Lehigh/Princeton/Columbia Chapters Present Distinguished Lecture Colloquia, October 2014 October 16, 2014, 1:30–2:45 pm On-Chip Voltage and Timing Diagnostic Circuits Frank O’Mahony, Intel Abstract: This talk introduces a set of practical and powerful techniques and circuits to observe and characterize on-die circuitry. Measuring voltage and timing information on the chip itself alleviates the bandwidth and noise limitations associated with bringing signals off-chip to be measured. Specific applications of these techniques include measurement and characterization of power supply noise, power delivery impedance, clock skew, phase interpolator linearity, I/O eye margins, waveform capture, RX voltage noise and hysteresis, and RX clock-data jitter. Because the measurements are fully integrated, the rest of the system can be automatically adapted based on these metrics in a stand-alone manner. Best of all, many of these techniques leverage existing circuitry and are highly digital. October 16, 2014, 3:00–4:15 p.m. Millimeter-wave and Terahertz Integrated Circuits in Silicon Technologies: Challenges and Solutions Prof. Payam Hedari, University of California Irvine Abstract: The vastly under-utilized spectrum across millimeter-wave (mm-wave) and terahertz (THz) bands has generated great deal of excitement to investigate futuristic systems for 10+ gigabit short-range wireless as well as wideband sensing/imaging applications. Simply put, the shorter wavelength associated with the mm-wave/THz band is appealing since the physical dimensions of the antenna and associated electronics are reduced in size, making it possible to design multi-antenna structures to achieve beamforming, spatial diversity and multiplexing. Owing to aggressive scaling in feature size and device fT/fmax, nanoscale (Bi)CMOS technology potentially enables integration of sophisticated systems at THz frequency range, once only be implemented in compound III-IV semiconductor technologies. This talk will give an overview of recent advances in designing silicon-based integrated circuits will be capable of operating close to the maximum operation limits of silicon-based transistors. The talk then will discuss in depth about two case studies designed in UCI’s Nanoscale Communication Integrated Circuits (NCIC) Labs; namely, the world’s highest fundamental frequency fully differential transceiver in CMOS at 210 GHz, and the world’s highest frequency PLL-based Synthesizer in Silicon at 300GHz with a wide tuning range. October 16, 2014, 4:30–5:45 p.m. Low-Power, High-Bandwidth, and Ultra-Small Memory Module Design Prof. R. Jacob Baker, University of Nevada, Las Vegas Abstract: This work proposes a novel DRAM module and interconnect architectures in an attempt to improve computing energy use and performance. A low cost advanced packaging technology is used to propose an 8 die and 32-die memory module. The 32-die memory module measures less than 2 cm3. The size and packaging technique allow the memory module to consume less power than conventional module designs. A 4 Gb DRAM architecture utilizing 64 data pins is proposed. The DRAM architecture is inline with ITRS roadmaps and can consume 50% less power while increasing bandwidth by 100%. The large number of data pins are supported by a low power capacitive-coupled interconnect. The receivers developed for the capacitive interface were fabricated in 0.5 μm and 65 nm CMOS technologies. The 0.5 μm design operated at 200 Mbps, used a coupling capacitor of 100 fF, and consumed less than 3 pJ/bit of energy. The 65 nm design operated at 4 Gbps, used a coupling capacitor of 15 fF, and consumed less than 15 fJ/bit and order of magnitude smaller consumptions than previously reported receiver designs. Contact Info: Nagi Naganathan, nagisub(a)gmail.com or Kaushik Sengupta, kaushiks(a)princeton.edu

1 0

Princeton Day of Statistics
by Nicole E. Wagenblast 29 Sep '14

29 Sep '14

Dear all, We are pleased to announce the 4th Princeton Day of Statistics. This bi-annual event will take place on Friday, October 17, 2014 in Sherrerd 101. Seven speakers will deliver talks on the most recent advances in statistics. * Marten Wegkamp (Cornell University) * Tony Cai (University of Pennsylvania) * Christopher Genovese (Carnegie Mellon University) * Jun Liu (Harvard University) * Regina Liu (Rutgers University) * Richard A. Davis (Columbia University) * Kung-Sik Chan (University of Iowa) For more information and registration, visit http://orfe.princeton.edu/statlab/events/pds Registration is required to attend, deadline is October 10th. Regards, Han Liu Assistant professor Operations Research & Financial Engineering Dept. -- Carol Smith Academic Assistant & Events Coordinator 609-258-9863 Fax: 609-258-4363 carols(a)princeton.edu

1 0

4:30pm Tue Oct 7 talk on multipath routing in CS 402
by Jennifer Rexford 26 Sep '14

26 Sep '14

Speaker: Deep Medhi, University of Missouri-Kansas City Title: Is Multipath Routing Beneficial? Date/time: 4:30pm Tuesday October 7 Location: CS 402 Abstract: It's often believed that multipath routing is always beneficial. Taking a traffic engineering perspective, we consider commonly used goals such as congestion minimization, minimum average delay, and minimum cost routing. Using a well-known result from linear programming, we show that numbers of paths taken by all demands at optimality is limited by the total number of demands and links in a network. When all node pairs (demands) in a network have traffic, multipath routing essentially becomes single-path routing, especially as the network becomes large. Under certain traffic conditions, single-path routing is found to be optimal. We will also present results on a number of traffic scenarios and load conditions using topologies used by ISPs and in data center networks. These observations are counter-intuitive due to our commonly held belief about multipath routing. Bio: Deep Medhi is Curators' Professor in the Department of Computer Science and Electrical Engineering at the University of Missouri-Kansas City, USA. He received B.Sc. in Mathematics from Cotton College, Gauhati University, India, M.Sc. in Mathematics from the University of Delhi, India, and his Ph.D. in Computer Sciences from the University of Wisconsin-Madison, USA. Prior to joining UMKC in 1989, he was a member of the technical staff at AT&T Bell Laboratories. He was an invited visiting professor at the Technical University of Denmark, a visiting research fellow at Lund Institute of Technology, Sweden, a research visitor at University of Campinas, Brazil under the Brazilian Science Mobility Program and served as a Fulbright Senior Specialist. He is the Editor-in-Chief of Springer’s Journal of Network and Systems Management, and is on the editorial board of IEEE/ACM Transactions on Networking, IEEE Transactions on Network and Service Management, and IEEE Communications Surveys & Tutorials. He is co-author of the books, Routing, Flow, and Capacity Design in Communication and Computer Networks (2004) and Network Routing: Algorithms, Protocols, and Architectures (2007), both published by Morgan Kauffman/Elsevier.

1 0

Colloquium Speaker Partha Mitra Wed Sept 17, 4:30pm
by Nicole E. Wagenblast 17 Sep '14

17 Sep '14

Mapping Neural Circuits in the Whole Mouse Brain Partha Mitra, Cold Spring Harbor Wednesday, September 17, 4:30pm Computer Science 105 Neuroanatomy, a century old subject, is currently undergoing a computational technology-driven make-over. Fall in data storage prices as well as automated equipment for digital histology and imaging, has made it possible for entire mammalian brains to be digitized using light microscopy. The talk will describe an ongoing effort to systematically uncover the neural circuit architecture of the whole mouse brain by scaling up classical neuroanatomical methods ( http://mouse.brainarchitecture.org ). The resulting petabyte-sized data sets are larger than any previously encountered in neuroscience and pose new and interesting data-analysis challenges. Partha Mitra received his B Sc in physics from Presidency College, Calcutta and his PhD in theoretical physics from Harvard University. He was an Assistant Professor of Physics at Caltech (1996) and a member of Theoretical Physics department at Bell Laboratories (1995-2003). He is currently Crick-Clay Professor of Biomathematics at Cold Spring Harbor Laboratory. His research combines experimental, theoretical and computational approaches to gain an understanding of how brains work.

1 2

Electrical Engineering Seminar Speaker Dr. Aryeh Kontorovich 9/18-4:30pm
by Nicole E. Wagenblast 15 Sep '14

15 Sep '14

DEPARTMENT OF ELECTRICAL ENGINEERING SEMINAR SERIES Speaker: Dr. Aryeh Kontorovich Ben-Gurion University of the Negev Title: Good Margins Make Good Neighbors Date: Thursday, September 18, 2014 Time: 4:30 p.m. Room: E-Quad, B205 Host: Prof. Sergio Verdu Abstract: Although well-known by practitioners to be an effective classification tool, nearest-neighbor methods have been somewhat neglected by learning theory of late. The goal of this talk is to revive interest in this time-tested technique by recasting it in a modern perspective. We will present a paradigm of margin-regularized 1-nearest neighbor classification which: (i) is Bayes-consistent (ii) yields simple, usable finite-sample error bounds (iii) provides for very efficient algorithms with a principled speed-accuracy tradeoff (iv) allows for near-optimal sample compression. Further extensions include multiclass, regression, and metric dimensionality reduction. I will argue that the regularized 1-nearest neighbor is superior to k-nearest neighbors in several crucial statistical and computational aspects. Based on a series of works with: Lee-Ad Gottlieb, Robert Krauthgamer, Roi Weiss Bio: Aryeh Kontorovich received his undergraduate degree in mathematics with a certificate in applied mathematics from Princeton University in 2001. His M.Sc. and Ph.D. are from Carnegie Mellon University, where he graduated in 2007. After a postdoctoral fellowship at the Weizmann Institute of Science, he joined the Computer Science department at Ben-Gurion University of the Negev in 2009 as an assistant professor; this is his current position. His research interests are mainly in machine learning, with a focus on probability, statistics, automata theory and metric spaces.

1 0

Aaron Wong Pre-FPO 9/16/14 @ 9:30am in CS 402
by Nicki Gotsis 15 Sep '14

15 Sep '14

Aaron Wong will present his Pre FPO Tuesday, September 16 at 9:30am in CS 402. The members of his committee are Olga Troyanskaya, advisor; Mona Singh, reader; Barbara Engelhardt, reader; Moses Charikar, non-reader; Kai Li, non-reader. The title and abstract are below. All are welcome to join. Title: Tissue- and disease-specific analysis of genome-scale data to inform biological experiments Biologists using modern experimental methods are generating a massive number of genome-scale datasets. In particular, the rate of large-scale data creation in most organisms is quickly outpacing biologists’ ability to perform detailed follow-up experiments. We address this growing disparity by developing methods to improve functional annotation coverage, methods to predict tissue specific function even though most genomic data are not resolved to specific tissues, and tools enabling biologists to make experimental discoveries. We demonstrate a method to systematically transfer experimental knowledge by identifying a gene’s “functional analogs” based on both sequence similarity and pathway partners inferred from high-throughput experimental data. Our methodology improves the coverage and accuracy of function predictions across six diverse organisms and machine learning methods. We created IMP (imp.princeton.edu), a web server that enables biologists to explore multi-species functional predictions and relationships for seven organisms, and worked with zebrafish biologists to experimentally validate gene predictions for heart left/right asymmetry. Tissue and cell-type identity lie at the core of human physiology and disease. However, we still lack tools to systematically explore the genes and interactions that shape specialized cellular functions. We develop a method that leverages large data compendia to build genome-scale tissue-specific functional maps in human by integrating thousands of genome-scale datasets. Our method can extract both functional and tissue/cell-type signals even when genomic data are not resolved for the tissue. We demonstrate the broad applicability of these networks by applying them to predict IL1B responsive genes and re-prioritize genome-wide association data. Finally, we created GIANT (giant.princeton.edu), which provides access to functional networks for 144 tissues/cell-types, and enables multi-network comparisons. Almost all functional genomic methods require biologists to pose biological questions as sets of genes of interest. However, biologists are generating and trying to make sense of massive high-throughput datasets, and their biological questions can be more precisely addressed within the biological context of their experiment. We develop a dataset-driven method for integration and search of gene expression compendia and show substantial predictive improvement in identifying functionally related co-expressed genes and experimentally similar datasets.

1 0

Omri Weinstein will present his pre-FPO Sept 16, 2014 at 11am in CS Room 401 (Title: Interactive Information Complexity and Applications)
by Nicki Gotsis 11 Sep '14

11 Sep '14

Omri Weinstein will present his pre-FPO on September 16, 2014 at 11am in CS Room 401. The members of his committee are: Mark Braverman, advisor; Anup Rao(University of Washington), reader; Zeev Dvir, reader; Sanjeev Arora, non-reader; Michael Saks(Rutgers), non-reader. Everyone is invited to attend his talk. The talk title and abstract follow below: Title: Interactive Information Complexity and Applications Abstract: ======= Few models in the history of theoretical computer science have affected the field in so many ways as profoundly as communication complexity. With applications in nearly every area of computer science, this model constitutes one of the few known techniques for proving unconditional lower bounds - the holy grail of complexity theory. Developing tools in communication complexity is therefore a promising approach for making progress in other computational models such as streaming, property testing, distributed computing, circuit complexity and data structures. One striking example of such tool is information theory, introduced by Shannon in the late 1940's in the context of the one way data transmission problem. Shannon's work revealed the intimate connection between information and communication, namely, that the amortized transmission cost of a random message is equal to the amount of information it contains. Classical information theory, however, does not readily convert to interactive setups, where two (or more) parties must engage in a multi-round conversation in order to accomplish a desirable task. The goal of our ongoing research is to extend this theory, develop the right tools, and understand how information behaves in interactive setups, such as the communication complexity model. Our main measure if interest is the Information Complexity of a function, which informally captures the least amount of information the parties need to disclose each other about their inputs in order to solve the underlying task. We demonstrate the broad power of this theory via applications to communication complexity, data streaming, circuit lower bounds, privacy and economics. In particular, I will discuss how information complexity helped us make progress on some of the most fundamental questions in communication complexity, including the limits of parallel computation, interactive compression, and the KRW conjecture.

1 0

Fwd: EE SEMINAR : Thursday September 18th, 4:30pm, E-Quad B205- Aryeh Kontorovich-Good Margins Make Good Neighbors
by Jennifer Rexford 10 Sep '14

10 Sep '14

An EE seminar that may be of interest to folks in CS, too... Begin forwarded message: > From: "Lisa R. Lewis" <ll2(a)Princeton.EDU> > Subject: EE SEMINAR : Thursday September 18th, 4:30pm, E-Quad B205- Aryeh Kontorovich-Good Margins Make Good Neighbors > Date: September 10, 2014 at 10:29:06 AM EDT > To: ee-seminar(a)Princeton.EDU > Reply-To: "Lisa R. Lewis" <ll2(a)Princeton.EDU> > > > > > DEPARTMENT OF > ELECTRICAL ENGINEERING > SEMINAR SERIES > > > > > Speaker: Dr. Aryeh Kontorovich > Ben-Gurion University of the Negev > Title: Good Margins Make Good Neighbors > Date: Thursday, September 18, 2014 > Time: 4:30 p.m. > Room: E-Quad, B205 > Host: Prof. Sergio Verdu > > > Abstract: Although well-known by practitioners to be an effective classification tool, nearest-neighbor methods have been somewhat neglected by learning theory of late. The goal of this talk is to revive interest in this time-tested technique by recasting it in a modern perspective. We will present a paradigm of margin-regularized 1-nearest neighbor classification which: (i) is Bayes-consistent (ii) yields simple, usable finite-sample error bounds (iii) provides for very efficient algorithms with a principled speed-accuracy tradeoff (iv) allows for near-optimal sample compression. Further extensions include multiclass, regression, and metric dimensionality reduction. I will argue that the regularized 1-nearest neighbor is superior to k-nearest neighbors in several crucial statistical and computational aspects. > > Based on a series of works with: Lee-Ad Gottlieb, Robert Krauthgamer, Roi Weiss > > > > Bio: Aryeh Kontorovich received his undergraduate degree in mathematics with a certificate in applied mathematics from Princeton University in 2001. His M.Sc. and Ph.D. are from Carnegie Mellon University, where he graduated in 2007. After a postdoctoral fellowship at the Weizmann Institute of Science, he joined the Computer Science department at Ben-Gurion University of the Negev in 2009 as an assistant professor; this is his current position. His research interests are mainly in machine learning, with a focus on probability, statistics, automata theory and metric spaces. > >

1 0

2-3pm Fri Aug 29 talk on scaling social search
by Jennifer Rexford 29 Aug '14

29 Aug '14

Speaker: Siddhartha Bannerjee Title: Scaling Social Search - PageRank Estimation for Large Networks When and Where: 29th August (Friday) at 2:00 PM in Room 402 in the CS bldg. Abstract: Although effective search is one of the great successes of the internet, social search lags far behind. A major hurdle is the complexity of existing algorithms for estimating Personalized PageRank -- a generalization of PageRank which measures centrality with respect to a fixed node in a network. In particular, to estimate PageRank values up to the required accuracies, existing algorithms need time which scales linearly in the network size -- this renders them infeasible for real-time social search. In this talk, I will present FAST-PPR, the first algorithm for Personalized PageRank estimation with an average running-time guarantee which is sublinear in the network size. This speedup is achieved via a combination of linear algebraic techniques and random walks; this new approach may prove useful in other estimation problems on networks. Moreover, I'll present detailed empirical studies on numerous large networks, wherein FAST-PPR dramatically outperforms existing algorithms -- for example, with target nodes sampled according to popularity, on the 2010 Twitter graph with 1.5 billion edges, FAST-PPR has a 160 factor speedup compared to the state-of-the-art. Joint work with Peter Lofgren, Ashish Goel and C. Seshadri. Paper available at http://arxiv.org/abs/1404.3181.

1 1