Parallelizing while loops for multiprocessor systems

Research output: Contribution to journalConference articlepeer-review

Abstract

Current parallelizing compilers treat while loops and do loops with conditional exits as sequential constructs because their iteration space is unknown. Because these types of loops arise frequently in practice, we have developed techniques that can automatically transform them for parallel execution. We succeed in parallelizing loops involving linked lists traversals - something that has not been done before. This is an important problem since linked list traversals arise frequently in loops with irregular access patterns, such as sparse matrix computations. The methods can even be applied to loops whose data dependence relations cannot be analyzed at compile-time. Experimental results on loops from the PERFECT Benchmarks and sparse matrix packages show that these techniques can yield significant speedups.

Original languageEnglish (US)
Pages (from-to)347-355
Number of pages9
JournalIEEE Symposium on Parallel and Distributed Processing - Proceedings
StatePublished - Jan 1 1995
EventProceedings of the IEEE 9th International Parallel Processing Symposium - Santa Barbara, CA, USA
Duration: Apr 25 1995Apr 28 1995

ASJC Scopus subject areas

  • Engineering(all)

Cite this