Scheduling strategies for optimistic parallel execution of irregular programs
Milind V. Kulkarni, Patrick Carribault, Keshav K. Pingali, Ganesh Ramanarayanan, Bruce Walter, Kavita Bala, L. Paul Chew · 2008
Recent application studies have shown that many irregular applications have a generalized data parallelism that manifests itself as iterative computations over worklists of different kinds. In general, there are complex dependencies between iterations. These dependencies cannot be elucidated statically because they depend on the inputs to the program; thus, optimistic parallel execution is the only tractable approach to parallelizing these applications.