[Brown CS Talks] Brown CS Colloquium: Michael Scott in Lubrano on March 14, 2002 at 4 pm.

[talks-admin@list.cs.brown.edu]

			   BROWN UNIVERSITY

		     COMPUTER SCIENCE COLLOQUIUM

				
			       presents

			   Michael L. Scott
			     
		       University of Rochester

		 
		 Thursday, March 14, 2002 at 4:00 pm
	       Lubrano Conference Room (CIT 4th floor)
		Refreshments will be served at 3:45 pm
			      

	       ``SCALABLE USER-LEVEL SYNCHRONIZATION''

			       
			       Abstract

Parallel programs employ synchronization algorithms to coordinate the
activities of threads.  Busy-wait synchronization, in which threads
actively poll for a desired condition, tends to outperform
scheduler-based synchronization when expected wait times are small.
Spin locks in particular are heavily used in parallel operating
systems.  Somewhat surprisingly, they are also heavily used in certain
commercially important user-level programs, including Oracle Parallel
Server and IBM DB2.  The locks in these applications incorporate a
timeout mechanism to recover from transaction deadlock and from
accidental preemption of the thread that is holding a lock.
Unfortunately, while timeout is easy to implement in a traditional
(e.g. test-and-set) spin lock, such locks do not scale well beyond a
small handful of processors.  As a consequence, lock overhead has
become a key performance bottleneck on large commercial servers.

I will present a family of algorithms in which a timed-out thread can
link itself out of an explicit queue of waiting threads, in an atomic,
lock-free manner, even if neighboring threads are also in the process
of timing out.  Work in progress aims to minimize the number of remote
operations performed on both cache-coherent and non-cache-coherent
machines; accommodate machines with different sets of atomic
primitives; provide standard, binary-compatible APIs; and integrate
scalable synchronization into existing schedulers and language runtime
packages.  I am also interested, longer term, in practical
general-purpose techniques for non-blocking synchronization.  As
customers demand increasingly powerful (i.e. more highly parallel)
servers, such algorithms should prove increasingly important.

Further information can be found at
www.cs.rochester.edu/~scott/synchronization/.

			   
		   Host: Professor Maurice Herlihy