Campus Event Calendar
Event Entry
What and Who
Concurrent Disjoint Set Union
Prof. Robert E. Tarjan
Princeton University
Talk
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI
MPI Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 16 September 2016
11:00
45 Minutes
E1 3 - Hörsaal Gebäude
002
Saarbrücken
Abstract
The disjoint set union problem is a classical problem in data structures with a
simple and efficient sequential solution that has a notoriously complicated
analysis. One application is to find strongly connected components in huge,
implicitly defined graphs arising in model checking. In this application, the
use of multiprocessors has the potential to produce significant speedups. We
explore this possibility. We devise and analyze wait-free concurrent
implementations of standard sequential algorithms using single and double
compare-and-swap primitives for synchronization. We obtain work bounds that grow
logarithmically with the number of processors, suggesting the possibility of
significant speedup in practice. This is joint work with Siddhartha Jayanti, an
undergraduate at Princeton.
Robert E. Tarjan is the James S. McDonnell Distinguished University Professor of
Computer Science at Princeton University and the Chief Scientist of Intertrust
Technologies. He has held academic positions at NYU, Stanford, U.C. Berkeley,
and Cornell, and industrial research positions at Microsoft, HP, NEC, and Bell
Labs. He is a world expert in the design and analysis of data structures and
graph and network algorithms. He is a member of the U.S. National Academy of
Sciences, the U.S. National Academy of Engineering . the American Philosophical
Society, and the American Academy of Arts and Sciences. He was awarded the
A.C.M Turing Award in 1986 and the Nevanlinna Prize of the International
Congress of Mathematicians in 1982.
simple and efficient sequential solution that has a notoriously complicated
analysis. One application is to find strongly connected components in huge,
implicitly defined graphs arising in model checking. In this application, the
use of multiprocessors has the potential to produce significant speedups. We
explore this possibility. We devise and analyze wait-free concurrent
implementations of standard sequential algorithms using single and double
compare-and-swap primitives for synchronization. We obtain work bounds that grow
logarithmically with the number of processors, suggesting the possibility of
significant speedup in practice. This is joint work with Siddhartha Jayanti, an
undergraduate at Princeton.
Robert E. Tarjan is the James S. McDonnell Distinguished University Professor of
Computer Science at Princeton University and the Chief Scientist of Intertrust
Technologies. He has held academic positions at NYU, Stanford, U.C. Berkeley,
and Cornell, and industrial research positions at Microsoft, HP, NEC, and Bell
Labs. He is a world expert in the design and analysis of data structures and
graph and network algorithms. He is a member of the U.S. National Academy of
Sciences, the U.S. National Academy of Engineering . the American Philosophical
Society, and the American Academy of Arts and Sciences. He was awarded the
A.C.M Turing Award in 1986 and the Nevanlinna Prize of the International
Congress of Mathematicians in 1982.
Contact
Christina Fries
--email hidden
passcode not visible
logged in users only
Christina Fries, 09/15/2016 15:41 -- Created document.