Implications of structured programming for machine architecture

ABSTRACT

Based on an empirical study of more than 10,000 lines of program text written in a GOTO-less language, a machine architecture specifically designed for structured programs is proposed. Since assignment, CALL, RETURN, and IF statements together account for 93 percent of all executable statements, special care is given to ensure that these statements can be implemented efficiently. A highly compact instruction encoding scheme is presented, which can reduce program size by a factor of 3. Unlike a Huffman code, which utilizes variable length fields, this method uses only fixed length (1-byte) opcode and address fields. The most frequent instructions consist of a single 1-byte field. As a consequence, instruction decoding time is minimized, and the machine is efficient with respect to both space and time.

REFERENCES

• 1: Alexander, W.G., and Wortman, D.B. Static and dynamic characteristics of XPL programs. Computer 8 (1975), 41-46.
• 2: Peter J. Denning, Is it not time to define "structured programming"?, ACM SIGOPS Operating Systems Review, v.8 n.1, p.6-7, January 1974 [doi>10.1145/775265.775266]
• 3: Foster, C.C., and Gonter, R.H. Conditional interpretation of operation codes. IEEE Trans. Comptrs. C-20, 1 (1971), 108-111.
• 4: Huffman, D. A method for the construction of minimum redundancy codes. Proc. IRE 40 (1952), 1098-1101.
• 5: K Jensen , N Wirth , A B Mickel , J F Miner, Pascal user manual and report; 3rd ed., Springer-Verlag New York, Inc., New York, NY, 1985
• 6: Knuth, D.E. An empirical study of FORTRAN programs. Software-Practice and Experience l (1971), 105-133.
• 7: Donald E. Knuth, Structured Programming with go to Statements, ACM Computing Surveys (CSUR), v.6 n.4, p.261-301, Dec. 1974 [doi>10.1145/356635.356640]
• 8: Richards, M. BCPL: A tool for compiler writing and system programming. Proc. AFIPS SJCC, Vol. 34, AFIPS Press, Montvale, N.J., 1969, pp. 557-566.
• 9: A Salvadori , J. Gordon , C. Capstick, Static profile of COBOL programs, ACM SIGPLAN Notices, v.10 n.8, p.20-33, August 1975 [doi>10.1145/956028.956031]
• 10: Tanenbaum, A.S. A programming language for writing operating systems. Rep. IR-3, Wiskundig Seminarium, Vrije U., Amsterdam, 1974.
• 11: Tanenbaum, A.S. A general purpose macro processor as a poor man's compiler. IEEE Trans. Software Eng. SE-2 (1976), 121-125.
• 12: van Wijngaarden, A., Mailloux, B., Peck, J.E.L., and Koster, C.H.A. Report on the algorithmic language ALGOL 68, Num. Math. 14 (1969), 79-218.
• 13: Wilner, W.T. Design of the Burroughs B1700. Proc. AFIPS FJCC, Vol. 4 1 ,4 9 7 , AFIPS Press, Montvale, N.J., 1972, pp. 489- 497.
• 14: Wilner, W.T. Burroughs B1700 Memory Utilization. Proc. AFIPS FJCC, Vol. 41, AFIPS Press, Montvale, N.J., 1972, 579- 586.
• 15: Wortman, D.B. A study of language directed computer design. CSRG-20, U. of Toronto, Toronto, Ont. (1972).
• 16: W. A. Wulf , D. B. Russell , A. N. Habermann, BLISS: a language for systems programming, Communications of the ACM, v.14 n.12, p.780-790, Dec. 1971 [doi>10.1145/362919.362936]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques
          Subjects: Structured programming

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

General Terms:
Design, Experimentation, Performance, Theory

Keywords:
computer architecture, computer organization, instruction set design, machine architecture, program characteristics