Vous pouvez vous abonner à nos annonces de séminaires
		    http://gallium.inria.fr/seminaires/

			     S E M I N A I R E
			   __
			  / _`  _   /  /  o
			 /   ) __) /  /  / /  / /\/|
			(___/ (_/ (_ (_ / (__/ /   |

			     I N R I A - Paris
                 2 rue Simone Iff (ou: 41 rue du Charolais)
                          Salle Lions 2, bâtiment C

                          Lundi 26 septembre, 10h30

                                 -----------
                                 Mike Rainey
                                 -----------

                                 Inria Paris

                  ==========================================
                  Theory and practice of granularity control
                  ==========================================

A classic problem in parallel computing is determining whether to
execute a thread in parallel or sequentially. If small threads are
executed in parallel, the overheads due to thread creation can
overwhelm the benefits of parallelism, resulting in suboptimal
efficiency and performance.  If large threads are executed
sequentially, processors may spin idle, resulting again in suboptimal
efficiency and performance. This granularity problem is especially
important in implicitly parallel languages, where the programmer
expresses all potential for parallelism, leaving it to the system to
exploit parallelism by creating threads as necessary. Although this
problem has been identified as an important problem, it is not well
understood. Broadly applicable solutions remain elusive.

In this talk, I present results from two of our studies, one that
addresses all fork-join programs and another for a particular
graph-traversal algorithm that falls outside the fork-join model. The
former is a language-based approach for controlling granularity
automatically, and the latter one particular algorithm. I will first
cover the main results from the former publication and then go into
more depth on the latter. In both cases, we have established
theoretical bounds showing the effectiveness of our techniques in
realistic cost models, and we have performed experiments to test our
granularity-control techniques in Parallel ML and C++.