- talks - lists.cs.princeton.edu

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

D Nehab FPO
by Melissa M Lawson 29 Aug '07

29 Aug '07

Diego Nehab will present his FPO on Wednesday September 5 at 2PM in Room 402. The members of his committee are; Szymon Rusinkiewicz, advisor; Tom Funkhouser and James Davis (UC Santa Cruz), readers; Kai Li and Adam Finkelstein, nonreaders. A copy of his thesis, "Advances in 3D Shape Acquisition", is on display in Room 310. Everyone is invited to attend his talk.

1 0

M Dudik FPO
by Melissa M Lawson 21 Aug '07

21 Aug '07

Miro Dudik will present his FPO on Monday August 27 at 2PM in Room 402. The members of his committee are Rob Schapire, advisor; David Blei and Steven Phillips (AT&T), readers; Moses Charikar and Olga Troyanskaya, nonreaders. A copy of his thesis "Maximum Entropy Density Estimation and Modeling Geographic Distributions of Species" is on display in Room 310. Everyone is invited to attend his talk.

1 0

E Nabieva FPO
by Melissa M Lawson 16 Aug '07

16 Aug '07

Elena Nabieva will present her FPO on Thursday August 23 at 3PM in room 402. The members of her committee are Mona Singh, advisor; Bernard Chazelle and Olga Troyanskaya, readers; Szymon Rusinkiewicz and Ned Wingreen (MolBio). A copy of her thesis, "Topology and Function in Protein Interaction Networks" is on display in Room 310. Everyone is invited to attend her talk.

1 0

D Dantas FPO
by Melissa M Lawson 16 Aug '07

16 Aug '07

Daniel Dantas will present his FPO on Wednesday August 22 at 2PM in Room 402. The members of his committee are David Walker, advisor; Andrew Appel and Stephanie Weirich (U Penn), readers; Ed Felten and David August, nonreaders. A copy of is thesis, "Analyzing Security Advice in Functional Aspect-oriented Programming Languages" is on display in Room 310. Everyone is invited to attend his talk.

1 0

M Bridges preFPO
by Melissa M Lawson 07 Aug '07

07 Aug '07

Matt Bridges will present his preFPO on Monday August 13 at 2PM in Room 402. The members of his committee are: David August, advisor; Kai Li and Dan Lavery (Intel), readers; Margaret Martonosi (ELE) and Doug Clark, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ------------------------------ Title: Unlocking the Potential of Automatic Parallelization Abstract: Multiprocessor systems, particularly chip multiprocessors, have emerged as the predominant organization for future microprocessors. Systems with 4 cores are already shipping and a future with 32 or more cores is easily conceivable. Unfortunately, multiple cores do not directly result in improved application performance, particularly for legacy applications. Consequently, parallelizing applications to execute on multiple cores is essential. Parallel programming models and languages could be used to create multithreaded applications. However, moving to a parallel programming model only increases the complexity and cost involved in software development. To address these costs, automatic thread extraction techniques, such as TLS and DSWP, have been explored. Unfortunately, the amount of parallelism that has been automatically extracted is generally insufficient to keep many cores busy. First, many important loops are not parallelized because the compiler lacks the necessary scope to apply the optimization. Second, the sequential programming model forces programmers to define a single legal application outcome, rather than allowing for a range of legal outcomes, leading to conservative dependences that prevent parallelization. This dissertation explores the performance of key existing, state-of-the-art methodologies in automatic thread extraction. The potential of these methodologies is significantly increased by combining them with an expanded optimization scope, which facilitates the optimization of large loops, leading to parallelism at higher levels in the application. Finally, natural, simple extensions to the sequential programming model are presented to break the limitations which can prevent the extraction of scalable parallelism. Through a case study of several applications, including all C benchmarks in the SPEC CINT2000 suite, this dissertation shows how scalable parallelism can be extracted. For the SPEC CINT2000 suite, our experience demonstrates that, by changing only 56 source code lines, all of the applications were parallelizable by automatic thread extraction. This process, constrained by the limits of modern optimizing compilers, yielded a speedup of 540%.

1 0