Abstract
Modulo scheduling theory can be applied successfully to overlap Fortran DO loops on pipelined computers issuing multiple operations per cycle both with and without special loop architectural support. This paper shows that a broader class of loops—REPEAT-UNTIL, WHILE, and loops with more than one exit, in which the trip count is not known beforehand—can also be overlapped efficiently on multiple-issue pipelined machines. The approach is described with respect to a specific machine model, but it can be extended to other models. Special features in the architecture, as well as compiler representations for accelerating these loop constructs, are discussed. Performance results are presented for a few select examples.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aho, A.V., Sethi, R., and Ullman, J.D. 1988. Compilers: Principles, Techniques and Tools. Addison-Wesley, Reading, Mass.
Allen, J.R., Kennedy, K., Porterfield, C., and Warren, J. 1983. Conversion of control dependence to data dependence. In Conf. Proc.—The 10th Annual ACM Symp. on Principles of Programming Languages (Austin, Tex., Jan. 24–26), pp. 177–189.
Charlesworth, A.E. 1981. An approach to scientific array processing: The architectural design of the AP-120B/FPS-164 family. IEEE Comp., 14, 9 (Sept.), 18–27.
Colwell, R.P., Nix, R.P., O'Donnell, J.J., Papworth, D.B., and Rodman, P.K. 1987. A VLIW architecture for a trace scheduling compiler. In Conf. Proc.—The 2nd Internat. Conf. on Architectural Support for Programming Languages and Operating Systems (Palo Alto, Calif., Oct. 5–8), pp. 180–192.
Dehnert, J.C., Hsu, P.Y.-T., and Bratt, J.P. 1989. Overlapped loop support in the Cydra 5. In Conf. Proc.—The 3rd Internat. Conf. on Architectural Support for Programming Languages and Operating Systems (Boston, Mass., Apr. 3–6), pp. 26–38.
Ellis, J.R. 1986. Bulldog: A Compiler for VLIW Architectures. MIT Press, Cambridge, Mass.
Fisher, J.A. 1983. Very long instruction word architectures and the ELI-512. In Conf. Proc.—The 10th Annual Internat. Symp. on Computer Architecture (Stockholm, Sweden, June 13–17), pp. 140–150.
Joshi, S.M., and Dhamdhere, D.M. 1982. A composite hoisting—strength reduction transformation for global program optimization, parts I and II. Internat. J. Comp. Math., 2: 21–41, 111–126.
Lam, M. 1988. Software pipelining: An effective scheduling technique for VLIW machines. In Conf. Proc.—The ACM SIGPLAN Conf. on Programming Language Design and Implementation (Atlanta, June 22–24), pp. 318–328.
McMahon, F.H. 1986. The Livermore Fortran kernels: A computer test of the numerical performance range. Tech. Rept. UCRL-53745, Lawrence Livermore Nat. Lab., Livermore, Calif.
Press, W.H., Flannery, B.P., Teukolsky, S.A., and Vetterling, W.T. 1986. Numerical Recipes—The Art of Scientific Computing. Cambridge Univ. Press, Cambridge, United Kingdom, p. 374.
Rau, B.R. 1988. Cydra 5 Directed Dataflow architecture. In Conf. Proc.—Spring COMPCON (San Francisco, Feb. 29–Mar. 4), pp. 106–113.
Rau, B.R., and Glaeser, C.D. 1981. Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing. In Conf. Proc.—The 14th Annual Microprogramming Workshop (Chatham, Mass., Oct. 12–15), pp. 183–198.
Rau, B.R., Yen, D.W.L., Yen, W., and Towle, R.A. 1989. The Cydra 5 departmental supercomputer: Design philosophies, decisions and trade-offs. IEEE Comp., 22, 1 (Jan.), 12–35.
Schlansker, M., and McNamara, M. 1988. The Cydra 5 computer system architecture. In Conf. Proc.—The 1988 IEEE Internat. Conf. on Computer Design: VLSI in Computers and Processors (Rye Brook, N.Y., Oct. 3–5), pp. 302–306.
Touzeau, R.F. 1984. A Fortran compiler for the FPS-164 computer. In Conf. Proc.—SIGPLAN Symp. on Compiler Construction (Montreal, June 17–22), pp. 48–57.
Towle, R.A. 1976. Control and data dependence for program transformations. Ph.D. thesis, University of Ill. at Urbana-Champaign, Urbana, Ill.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Tirumalai, P.P., Lee, M. & Schlansker, M.S. Parallelization of WHILE loops on pipelined architectures. J Supercomput 5, 119–136 (1991). https://doi.org/10.1007/BF00127840
Issue date:
DOI: https://doi.org/10.1007/BF00127840
