Integrating task and data parallelism in an irregular application: a case study

Recently, there has been growing interest in simultaneous exploitation of task and data parallelism in scientific applications and in compiler and runtime support of this combined form of parallelism. In this paper we report on the integration of task and data parallelism on an important irregular application from the VLSI computer-aided design field, namely VLSI layout verification. We report on the implementation, and experimental results of our study on a SUN Sparcserver 1000 shared memory multiprocessor, a CM-5 distributed memory multiprocessor