Substantial parallelism exists in all of the Perfect Club Benchmarks codes, although existing automatic techniques are able to find only a small portion of it [Eig92][EHLP91]. Exposing this parallelism required a careful, manual examination of all the dependences that appeared to prevent parallelism, and the development and manual application of new program transformations that have not yet been automated. It is therefore helpful to identify those parts of the program that might contain unexploited parallelism, and manually examine only those locations.
We have developed [PW93b] techniques that compute both upper and lower bounds on dependences, which are used to compute upper and lower bounds on the amount of parallelism in each part of the program. Any place where the upper and lower bounds on parallelism differ is targeted for manual examination.
Our techniques provide feedback on the transformations that may be required to exploit the parallelism. We can detect when we may need to apply: