On the combination of hardware and software concurrency extraction methods

ABSTRACT

It has been shown that parallelism is a very promising alternative for enhancing computer performance. Parallelism, however, introduces much complexity to the programming effort. This has lead to the development of automatic concurrency extraction techniques. Prior work has demonstrated that static program restructuring via compiler based techniques provides a large degree of parallelism to the target machine. Purely hardware based extraction techniques (without software preprocessing) have also demonstrated significant (but lesser) degrees of parallelism. This paper considers the performance effects of the combination of both hardware and software techniques. The concurrency extracted from a given set of benchmarks by each technique separately, and together, is determined via simulations and/or analysis. The “common parallelism” extracted by the two methods is thus also considered, using new metrics. The analytic techniques for predicting the performance of specific programs are also described.

REFERENCES

• 1: R D Acosta , J Kjelstrup , H C Torng, An instruction issuing approach to enhancing performance in multiple functinal unit processors, IEEE Transactions on Computers, v.35 n.9, p.815-828, Sept. 1986 [doi>10.1109/TC.1986.1676841]
• 2: Utpal Banerjee, Speedup of ordinary programs, 1979
• 3: Chamberlin, D. D. The Single-Assignment Approach to Parallel Processing. In Fall Joint Computer Conference, pages 263-269. AFIPS. 1971.
• 4: Cytron, R. G. Doacross: Beyond Vectorization for Multiprocessors (Extended Abstract). In Proceedinns of the 1986 International Conference on Parallel Proiesshg, pages 836-844. Pennsylvania State University and the IEEE Computer Society, August, 1986.
• 5: W. Hwu , Y. N. Patt, HPSm, a high performance restricted data flow architecture having minimal functionality, Proceedings of the 13th annual international symposium on Computer architecture, p.297-306, June 02-05, 1986, Tokyo, Japan
• 6: Robert M. Keller, Look-Ahead Processors, ACM Computing Surveys (CSUR), v.7 n.4, p.177-195, Dec. 1975 [doi>10.1145/356654.356657]
• 7: Kolen. J. F. Characterization of Concurrently Executed Programs. 1987. Undergraduate project report, Dept. of Electrical Engineering and Computer Sciences, University of California at San Diego, La Jolla, CA.
• 8: Kuck, D. J., Muraoka, Y. and Chen, S.-C. On the Number of Operations Simultaneously Executable in Fortran-Like Programs and Their Resulting Speedup. IEEE Transactions on Computers C-21(12):1293-1310, December, 1972.
• 9: David J. Kuck, A Survey of Parallel Machine Organization and Programming, ACM Computing Surveys (CSUR), v.9 n.1, p.29-59, March 1977 [doi>10.1145/356683.356686]
• 10: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 11: Kuck, D. J., Kuhn. R. H.. Leasure. B.. and Wolfe. M. The Structure of an Advanced Vectorizer for Pipelined Processors. In Proceedings of the Fourth International Computer Software and Applications Conference, ACM, October, 1980.
• 12: Y. N. Patt , W. M. Hwu , M. Shebanow, HPS, a new microarchitecture: rationale and introduction, Proceedings of the 18th annual workshop on Microprogramming, p.103-108, December 03-06, 1985, Pacific Grove, California, United States
• 13: C. D. Polychronopoulos , David J. Kuck , David A. Padua, Utilizing Multidimensional Loop Parallelism on Large Scale Parallel Processor Systems, IEEE Transactions on Computers, v.38 n.9, p.1285-1296, September 1989 [doi>10.1109/12.29467]
• 14: Constantine Demetrios Polychronopoulos, On program restructuring, scheduling, and communication for parallel processor systems, 1986
• 15: C. D. Polychronopoulus , U. Banerjee, Processor allocation for horizontal and vertical parallelism and related speedup networks, IEEE Transactions on Computers, v.36 n.4, p.410-420, April 1987 [doi>10.1109/TC.1987.1676923]
• 16: C. D. Polychronopoulos , D. J. Kuck, Guided self-scheduling: A practical scheduling scheme for parallel supercomputers, IEEE Transactions on Computers, v.36 n.12, p.1425-1439, Dec. 1987 [doi>10.1109/TC.1987.5009495]
• 17: Thorton, J. E. Parallel Operation in the Control Data 6600. In Proceedings of the Fall Joint Computer Conference, pages 33-40. AFIPS, 1964.
• 18: Garold Stephen Tjaden, Representation and detection of concurrency using ordering-matrices., 1972
• 19: Tjaden, G. S. and Flynn, M. J. Representation of Concurrency with Ordering Matrices. IEEE Transactions on Computers C-22(8):752-761, August, 1973.
• 20: Tomasulo, R. M. An Efficient Algorithm for Expoiting Multiple Arithmetic Units. IBM Journal:25-33, January, 1967.
• 21: Augustus Kinzel Uht, Hardware extraction of low-level concurrency from sequential instruction streams (parallelism, implementation, architecture, dependencies, semantics), 1985
• 22: Uht, A. K. An Efficient Hardware Algorithm to Extract Concurrency From General-Purpose Code. In Proceedings of the Nineteenth Annual Hawaii International Conference on System Sciences. University of Hawaii, in cooperation with the ACM and the IEEE Computer Society, January, 1986.
• 23: Uht, A. K. and Wedig, R. G. Hardware Extraction of Low-level Concurrency from Serial Instruction Streams. In Proceedings of the International Conference on Parallel Processing, pages 729-736. IEEE Computer Society and the Association for Computing Machinery, August, 1986.
• 24: A. K. Uht, Incremental performance contributions of hardware concurrency extraction techniques, Proceedings of the 1st International Conference on Supercomputing, p.355-376, March 1988, Athens, Greece
• 25: Wedig, R. G. Detection of Concurrency in Directly Executed Language Instruction Streams. PhD thesis, Stanford University, June, 1982.