Speaker: Guri Sohi, University of Wisconsin-Madison
Abstract: Nondeterministic execution of conventional, multithreaded programs complicates multiprocessor programming and system use in general. To eliminate nondeterminism from multiprocessor programs, we propose an ordered approach. It performs totally ordered execution of parallel algorithms expressed as programs with ordered semantics.
We present a runtime system to implement this approach. The runtime provides APIs to express such programs and incorporates mechanisms to parallelize their execution. The runtime reaps the available parallelism by using dataflow and disciplined speculative execution. Further, it uses the program’s task sequence to provide an appearance of total order. We evaluate the ordered approach for expressiveness and performance, by implementing a range of parallel algorithms using it. Experiments on stock machines show that the developed programs, although semantically ordered, can match multithreaded programs in expressing parallelism. They can also match multithreaded programs in performance, in all but cases of very small task sizes and highly nondeterministic algorithms. This work is in collaboration with Gagan Gupta for his Ph.D thesis.
Biography: Guri Sohi has been a faculty member at the University of Wisconsin-Madison since 1985 where he currently a Vils Research Professor, the John P. Morgridge Professor and the E. David Cronon Professor of Computer Sciences. He was the Chair of the Computer Sciences Department from 2004 until 2008. Sohi's research has been in the design of high-performance microprocessors and computer systems. Results from his research can be found in almost every high-end microprocessor in the market today.
He received the 1999 ACM SIGARCH Maurice Wilkes award "for seminal contributions in the areas of high issue rate processors and instruction level parallelism" and the 2011 ACM/IEEE Eckert-Mauchly Award "for pioneering widely used micro-architectural techniques for instruction-level parallelism". At the University of Wisconsin he was selected as a Vilas Associate in 1997, awarded the WARF Kellett Mid-Career Faculty Researcher award in 2000, and was selected as a WARF Named Professor in 2007. He is a Fellow of both the ACM and the IEEE and was elected to the National Academy of Engineering in 2009.