LAZY THREADS - IMPLEMENTING A FAST PARALLEL CALL

In this paper, we describe lazy threads, a new approach for implementi ng multithreaded execution models on conventional machines. We show ho w they can implement a parallel call at nearly the efficiency of a seq uential call. The central idea is to specialize the representation of a parallel call so that it can execute as a parallel-ready sequential call. This allows excess parallelism to degrade into sequential calls with the attendant efficient stack management and direct transfer of c ontrol and data, yet a call that truly needs to execute in parallel, g ets its own thread of control. The efficiency of lazy threads is achie ved through a careful attention to storage management and a code gener ation strategy that allows us to represent potential parallel work wit h no overhead. (C) Academic Press, Inc.