Type of Talk: UTCS Colloquium

Speaker/Affi

liation: Lars Nyland/NVIDIA

Date/Time: Monday February 11 2008

Noon

Location: TAY 3.128

Host: Keshav Pingali

Talk T

itle: Speculation on Lock-Free Parallel Sorting

Talk Abstract:
T

his research talk will pull apart the title word by word. I''ll first
review sorting focusing on a few key sorting methods. Then
I''ll l

ook at parallelization strategies for achieving high performance
with
an overview of what the costs are. Following that we''ll consider
w

hat it means to be lock-free (and perhaps wait-free) an area of
concu

rrent computing that strives to keep as many threads of
computation mak

ing progress as possible. Then we''ll turn to the
G80 architecture a

highly parallel computing architecture that has
support for lock-free
programming (atomic operations). Finally I''ll
pull the entire title
together discussing a few sorting algorithms written
in a lock-free s

tyle. We will end with a discussion about what other
methods might be

good approaches to high-performance sorting on
the G80.

Speaker

Bio:
Lars Nyland is a senior architect in the ''''compute'''' group at N

VIDIA
where he designs develops and tests architectural features to s

upport
non-traditional uses of graphics processors. Prior to joining NVI

DIA
Lars was an associate professor of computer science at the Colorad

o
School of Mines in Golden Colorado. He ran the Thunder Graphics Lab

where demanding computational applications were coupled with
immers

ive 3D graphics. Between Lars'' PhD and his position in Colorado
he

was a member of the research faculty at UNC Chapel Hill where he
was

a member of the high-performance computing and image-based
rendering gro

ups. Some notable achievements were the development
of the DeltaSphere

scene digitizer and its use at Monticello to provide
an immersive exper

ience for visitors to the New Orleans Museum of Art''s
Jefferson and Nap

oleon exhibit. He also spent considerable time studying
N-Body algorithm

s parallelizing N-Body algorithms for Molecular Dynamics
and parallel

programming languages. Lars earned his PhD at Duke Univ.
in 1991 under t

he direction of John Reif exploring high-level parallel
programming lan

guages.