Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information
Date and Time: Friday, June 17, 2016, 12:15 pm
Duration: 30 minutes
Location: CAB G11
Speaker: Robert E. Tarjan (Princeton University)
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 question. We devise and analyze wait-free concurrent implementations of standard sequential algorithms using single and double compare-and-swap primitives. 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.
Automatic MiSe System Software Version 1.4803M | admin login