September 2007 - talks - lists.cs.princeton.edu

B Brown preFPO - reannounce with room
by Melissa M Lawson 28 Sep '07

28 Sep '07

Benedict Brown will present his preFPO on Monday October 1 at 2PM. His talk will be in Friend 305, which is located inside the Engineering Library. The members of his committee are: Szymon Rusinkiewicz, advisor; David Dobkin and Tom Funkhouser, readers; Adam Finkelstein and Ken Steiglitz, nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------------------- Title: Registration and Matching of Large Geometric Datasets for Cultural Heritage Applications Over the last decade, there has been growing interest in acquiring high resolution digital representations of cultural heritage. This includes not only high resolution photographs, but also detailed 3-D models of statues, buildings, paintings, archeological objects, etc. These applications raise a number of challenges in data management, and in designing affordable acquisition systems which are practical, efficient, and usable. This thesis looks at how to handle alignment applications in this framework. We show how to align range scans in the presence of calibration error, as is the case in large, high-resolution models such as the Digital Michelangelo models. At the other extreme, we show how to align small fresco pieces from the Thera project completely automatically; in this case each individual model is small, but because there are tens of thousands of fragments, efficiency and automation are paramount. We also show how registration techniques extend to the problem of matching these fragments to each other. Finally, we look at the problem of aligning high-quality 2-D images of these fragments to the 3-D models. _______________________________________________ talks mailing list talks(a)lists.cs.princeton.edu https://lists.cs.princeton.edu/mailman/listinfo/talks

1 0

J Calandrino generals
by Melissa M Lawson 26 Sep '07

26 Sep '07

Joe Calandrino will present his research seminar/general exam on Tuesday October 2 at 2PM in Room 402. The members of his committee are Ed Felten, Andrew Appel, and David Walker. 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: Machine-Assisted Election Auditing Abstract: Election audit procedures usually rely on precinct-based audits, in which workers manually review all paper ballots from selected polling places, but these audits can be expensive due to the labor required. In this talk, I propose an alternative audit strategy that allows machines to perform most of the work. Precincts are audited using recounting machines, and their output is manually audited using efficient ballot sampling techniques. This strategy can achieve equal or greater confidence than precinct-based auditing at a significantly lower cost while protecting voter privacy better than previous ballot-based auditing methods. I show how to determine which ballots to audit against the auditing machines' records and compare this new approach to precinct-based audits in the context of Virginia's November 2006 election. Far fewer ballots need to be audited by hand using our approach. I also explore extensions to these techniques, such as varying individual ballots' audit probabilities based on the votes they contain, that promise further efficiency gains. Reading List: 1. R. Anderson. Security Engineering. 2001. 2. N. Ferguson, B. Schneier. Practical Cryptography. 2003. 3. R. G. Saltman. The History and Politics of Voting Technology. 2006. 4. 110TH CONGRESS. H.R. 811: Voter Confidence and Increased Accessibility Act of 2007. 5. A. W. Appel. Effective Audit Policy for Voter-Verified Paper Ballots in New Jersey. 2007. 6. A. Cordero, D. Wagner, D. Dill. The Role of Dice in Election Audits. In Proc. 2006 IAVoSS Workshop On Trustworthy Elections (WOTE 2006). 7. D. Jefferson, E. Ginnold, K. Midstokke, K. Alexander, P. Stark, A. Lehmkuhl. Post-Election Audit Standards Working Group Report: Evaluation of Audit Sampling Models and Options for Strengthening California's Manual Count. 2007. 8. K. C. Johnson. Election Certification by Statistical Audit of Voter-Verified Paper Ballots. 2004. 9. C. A. Neff. Election Confidence: A Comparision of Methodologies and their Relative Effectiveness at Achieving It. 2003. 10. L. Norden, A. Burstein, J. L. Hall, M. Chen. Post-Election Audits: Restoring Trust in Elections. 2007. 11. J. A. Aslam, R. A. Popa, R. L. Rivest. On Estimating the Size and Confidence of a Statistical Audit. In Proc. 2007 USENIX/ACCURATE Electronic Voting Technology Workshop (EVT '07). 12. R. L. Rivest. On Auditing Elections when Precincts Have Different Sizes. 2007.

1 0

FW: (no subject)
by Ginny Hogan 25 Sep '07

25 Sep '07

-----Original Message----- From: Michele Brown [mailto:mjbrown@CS.Princeton.EDU] Sent: Tuesday, September 25, 2007 10:34 AM To: gch(a)CS.Princeton.EDU Subject: (no subject) *Internet visionaries 're-imagine the Internet'* Robert Kahn, considered one of the fathers of the Internet, will join Larry Peterson, chair of the computer science department, in a public talk on the future of the Internet at 4:30 p.m. Thursday, Sept. 27, in the Friend Center auditorium. http://engineering.princeton.edu/news/kahn_internet

1 0

G Ottoni preFPO
by Melissa M Lawson 24 Sep '07

24 Sep '07

Guilherme Ottoni will present his preFPO on Monday October 1 at 11AM in Room 301. The members of his committee are: David August, advisor; Sharad Malik (EE) and Vivek Sarkar (Rice), readers; Margaret Martonosi and David Walker, nonreaders. Everyone is invited to attend his talk. His abstract follows below. -------------------- Global Instruction Scheduling for Multi-Threaded Architectures Recently, the microprocessor industry has moved toward chip multiprocessor (CMP) designs as a means of utilizing the increasing transistor counts in the face of physical and micro-architectural limitations. Despite this move, CMPs do not directly improve the performance of single-threaded codes, a characteristic of most applications. In effect, the move to CMPs has shifted even more the task of improving performance from the hardware to the software. Since developing parallel applications has long been recognized as significantly harder than developing sequential ones, it is very desirable to have automatic tools to extract parallelism from sequential applications. Unfortunately, automatic parallelization has only been successful in the restricted domain of scientific and data-parallel applications, which usually have regular array-based memory accesses and little control flow. In order to support parallelization of general-purpose applications, computer architects have proposed CMPs with light-weight, fine-grained (scalar) communication mechanisms. Despite such support, most existing compiler multi-threading techniques have generally demonstrated little effectiveness in extracting parallelism from non-scientific applications. The main reason for this is that such techniques are mostly restricted to extracting parallelism within local, straight-line regions of code. As observed in several limit studies, local regions of code have limited parallelism, and control dependence analysis and multiple control units are necessary to extract most of the parallelism opportunities. In this talk, I will describe a general compiler framework to perform Global Multi-Threaded (GMT) instruction scheduling, based on a Program Dependence Graph (PDG) representation, graph partitioning algorithms, and a novel Multi-Threaded Code Generation (MTCG) algorithm. Based on this framework, two techniques to perform GMT instructions scheduling are proposed. The first one, Decoupled Software Pipelining (DSWP), extracts pipeline parallelism from arbitrary loop nests. The second technique, GREMIO, is applicable to arbitrary (intra-procedural) code regions, and can also exploit other forms of parallelism. Finally, I will present several communication optimizations to improve the MTCG algorithm, and thus all GMT instruction scheduling techniques based on it. All these techniques are implemented in the VELOCITY compiler and evaluated on an accurate CMP simulator built on top of validated Itanium 2 core models. The results demonstrate the effectiveness of the proposed compiler techniques, with speedups on a number of real applications written in C.

1 0

B Brown preFPO
by Melissa M Lawson 24 Sep '07

24 Sep '07

Benedict Brown will present his preFPO on Monday October 1 at 2PM. Room will be announced later. The members of his committee are; Szymon Rusinkiewicz, advisor; David Dobkin and Tom Funkhouser, readers; Adam Finkelstein and Ken Steiglitz, nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------------------- Title: Registration and Matching of Large Geometric Datasets for Cultural Heritage Applications Over the last decade, there has been growing interest in acquiring high resolution digital representations of cultural heritage. This includes not only high resolution photographs, but also detailed 3-D models of statues, buildings, paintings, archeological objects, etc. These applications raise a number of challenges in data management, and in designing affordable acquisition systems which are practical, efficient, and usable. This thesis looks at how to handle alignment applications in this framework. We show how to align range scans in the presence of calibration error, as is the case in large, high-resolution models such as the Digital Michelangelo models. At the other extreme, we show how to align small fresco pieces from the Thera project completely automatically; in this case each individual model is small, but because there are tens of thousands of fragments, efficiency and automation are paramount. We also show how registration techniques extend to the problem of matching these fragments to each other. Finally, we look at the problem of aligning high-quality 2-D images of these fragments to the 3-D models.

1 0

KATIE POLLARD talk TODAY in Genomics at 4:15
by Mona Singh 24 Sep '07

24 Sep '07

Hi everyone, Katie Pollard from UC Davis Biostatistics will be speaking in Genomics today about what makes us different from chimps ... See below, Mona TITLE: Accelerated and biased nucleotide evolution in the human lineage. SPEAKER: Katherine Pollard, UC Davis, Dept of Statistics/Genome Center TIME: 4:15 LOCATION: Carl Ichan Lab 101 ABSTRACT: Comparative genomics allows us to search the whole human genome for examples of lineage-specific evolution. Using a novel likelihood ratio testing approach, we recently identified 202 Human Accelerated Regions (HARs) that were extensively changed in the last ~6 million years since divergence from our common ancestor with chimpanzee, but are highly conserved in other species and thus are likely to be functional. The HARs are mostly non-coding sequences, and the set of genes near HARs is enriched for transcription factors, suggesting a role for HARs in the evolution of human gene regulation. We will describe a few of the most intriguing HARs before turning to a curious observation about the HAR sequences: the most accelerated regions show a striking bias for AT to GC ("weak-to-strong") nucleotide substitutions. To investigate whether this association between rate of substitutions and nucleotide bias is a genome-wide phenomenon, we quantified substitution density and bias across the human and chimp genomes. While there is no weak-to-strong bias overall, clusters of nearby substitutions (5 or more within 300bp) are highly biased. Interestingly, human polymorphisms do not show the same pattern, suggesting a fixation (rather than mutation) bias. We found a strong correlation between nucleotide bias and male recombination rates. This observation will be used to speculate about the cause of rapid, biased evolution in the primate genome and to date the chromosome fusion that formed human chr2.

1 0

Invited Talk 3 pm Today
by kzhu＠CS.Princeton.EDU 21 Sep '07

21 Sep '07

> All are welcome! > > Title: Whole System Monitoring in Windows > > Venue: CS 105 > > Time: 3 pm - 4 pm, Friday, 09/21/2007 > > Abstract: > > Operating Systems like Windows are extremely complex and often there are many > interactions between the software and services running in the system which > changes its persistent state. Managing, diagnosing and also securing > one or more Windows systems can be difficult unless one is able to understand > and deal with the complex persistent state system interactions. > In this talk, we describe WinResMon, a monitoring infrastructure for Windows > which does whole-level system monitoring. By looking at all the system > interactions, we are able to explain questions about resource usage, > dependencies and interactions over time. > Ideally, one should capture all interesting system interactions continuously > but such continuous monitoring raises its own challenges. We will discuss > some of these during the talk. > > Bio: > > Roland Yap is an associate professor at the Department of Computer Science, > National University of Singapore. He is one of the primary authors > of the CLP(R) system which was the first CLP language with arithmetic > constraints. His current research interests are in the area of > constraints, programming languages, security and bioinformatics. > He obtained his B.Sc and Ph.D from Monash University, Australia. > > URL: http://www.comp.nus.edu.sg/~ryap/ > _______________________________________________ > Systems-lunch mailing list > Systems-lunch(a)lists.cs.princeton.edu > https://lists.cs.princeton.edu/mailman/listinfo/systems-lunch >

1 0

Refreshments -
by Ginny Hogan 19 Sep '07

19 Sep '07

Refreshments are now available in the tea room -

1 0

Tea today
by Ginny Hogan 19 Sep '07

19 Sep '07

Food is late in arriving so the tea will be delayed until 4:00pm ish -sorry about the mix up - Ginny

1 0

Talk today -
by Ginny Hogan 19 Sep '07

19 Sep '07

Doug Comer, VP of Research, Cisco Systems will present his talk, "Lessons Learned from The Internet Project" at 4:15 today - COS Room 105 Tea will be at 3:45 -

1 0

Talk Tomorrow - 4:15 - COS 105
by Ginny Hogan 18 Sep '07

18 Sep '07

Talk tomorrow 4:15 PM Doug Comer, VP of Research, Cisco Systems - Title: Lessons Learned from the Internet Project - Refreshments will be available in the tea room At 3:45 -

1 0

A Hobor preFPO
by Melissa M Lawson 17 Sep '07

17 Sep '07

Aquinas Hobor will present his preFPO Thursday September 20 at 10AM in room 402. The members of his committee are: Advisor Andrew Appel, Readers David Walker, Peter O'Hearn (Queen Mary College, University of London) Non-Readers: Vivek Pai, Brian Kernighan. Everyone is invited to attend his talk. His abstract follows below. Title: "Oracle Semantics for Concurrent Separation Logic" Abstract: <<< I present a model for a generalized Concurrent Separation Logic with first-class locks and threads, and prove its soundness with respect to the operational semantics of Concurrent C minor, a language with shared memory, spawnable threads, and sufficient expressive power to be the target of a C, Java, or ML compiler. The model is modular in the sense that one can reason about sequential features knowing almost nothing about concurrency, and concurrent features knowing almost nothing about sequential control flow. There are substantial, but at this point incomplete, proofs of the correctness of the system in Coq. Using the modularity principle it should be relatively straightforward to generalize Leroy's proof of C minor compiler correctness to the concurrent case without becoming deeply entangled in the issues of concurrency. Thus we will obtain end-to-end proofs: the properties you prove in Concurrent Separation Logic will be true of the program that actually executes on the machine. >>> Thanks, Aquinas

1 0

N Vachharajani preFPO
by Melissa M Lawson 04 Sep '07

04 Sep '07

Neil Vachharajani will present his preFPO on Friday, September 7 at 1:30pm in Room 402. The members of his committee are: David August, advisor; Sharad Malik (ELE) and Scott Mahlke (U Michigan), readers; Andrew Appel and Li-Shiuan Peh (ELE), nonreaders. Everyone is invited to attend his talk. His abstract follows below. ----------------------------------- INTELLIGENT PIPELINED MULTITHREADING SPECULATION In recent years, microprocessor manufacturers have shifted their focus from single-core to multicore processors. To avoid burdening programmers with the responsibility of parallelizing their applications, some researchers have advocated automatic thread extraction. Within the scientific computing domain automatic parallelization techniques have been successful, but in the general purpose computing domain few, if any, techniques have achieved comparable success. Despite this, recent progress hints at mechanisms to unlock parallelism from general purpose applications. In particular, two promising proposals exist in the literature. The first, a group of techniques loosely classified as thread-level speculation (TLS), attempts to adapt techniques successful in the scientific domain, such as DOALL and DOACROSS parallelization, to the general purpose domain by using speculation to overcome complex control flow and data access patterns not easily analyzed statically. The second, a non-speculative technique called Decoupled Software Pipelining, partitions loops into long-running, fine-grained threads organized into a pipeline (pipelined multithreading or PMT). DSWP effectively extends the reach of conventional software pipeling to codes with complex control flow and variable latency operations. Unfortunately, both techniques suffer key limitations. TLS techniques either suffer from over speculation, in an attempt to speculatively transform a loop into a DOALL loop, or realize little parallelism in practice because DOACROSS parallelization puts core-to-core communication latency on the critical path. DSWP avoids these pitfalls with its pipeline organization and decoupled execution using inter-core communication queues. However, its non-speculative nature and restrictions needed to ensure a pipeline organization prevent DSWP from achieving balanced parallelism on many key application loops. This dissertation advances automatic parallelization of general purpose applications with two key contributions. First, we propose extending pipelined multithreaded execution with intelligent speculation. Rather than speculating all loop-carried dependences to transform loops into DOALL loops, we propose speculating only key predictable dependences that inhibit balanced, pipelined execution. We demonstrate this technique is effective with an automatic compiler implementation of Speculative DSWP. Second, to support decoupled speculative execution, this dissertation explores extending a multi-core architecture's memory subsystem with versioning. The proposed memory systems resemble those present in TLS architectures, but provide efficient execution in the presence of large transactions, many simultaneous outstanding transactions, and eager data forwarding between uncommitted transactions. In addition to supporting usage patterns exhibited by speculative pipelined multithreading, the proposed memory system facilitates existing and future speculative threading techniques.

1 0