An Automatic Sequencing Procedure with Application to Parallel Programming

ABSTRACT

An automatic sequencing procedure for assigning sets of instructions to predesignated autonomous units of a multiprocessor is described. The procedure is based upon an assignment matrix developed from a precedence matrix. By associating a column vector whose elements are the operation time of each instruction set with the assignment matrix, numerical computation is made possible. A topological index, the precedence number, stating the position of each instruction set in relation to the last set in its path is contained in a second column vector. A transfer matrix in conjunction with an automatically derived path table is employed in a multipath program. Six generalized rules are derived for the procedure which proceeds directly to a solution without obtaining and testing all permutations of the sets of instructions, and seeks to establish a sequence of operations to minimize the total operation time while satisfying all precedence restrictions. Since the procedure does not require looking at the last instruction set before releasing the first sets for assignment to units, computer processing may start after the first assignment period is completed with processing and subsequent sequencing taking place concurrently. The procedure is readily adaptable to computer operation and automatic development of the assignment matrix is described. A flow chart of the procedure and its use for solution of a problem is presented. The solution obtained is guaranteed to be feasible although it is not necessarily unique. In the examples tested, an optimum or near optimum solution has been obtained. Computational experience with the procedure in complex problems is required to determine its effectiveness in such cases.

REFERENCES

• 1: I~OURIE, N ; SCttRIM}~F, I-t , REACH, R.; AND KAItN, W. Arithmetic and controI techniques in a multi-program computer. Proc. Eastern Joint Comput Conf., 1959.
• 2: LEINER, A. L ; Nowz, W. A., SMITII, J. L.; AND MARIMONT, R.B. Concurrently operating computer systems. Inte,'national Conf. Information Proc., UNESCO/NS/ ICIP/B 2.17, 1959.
• 3: PORTER, R. E Programming a polymorphic system. Conf Parallel Programming, May 1960
• 4: CODD, E.F. Multlprogram scheduling. IBM Corp., Paper TR 00.716, Apr. 1960.
• 5: HOLLAND, J A universal computer eapable of executing an arbitrary number of subprograms simultaneously Proc. Eastern Joint Comput. Conf, 1959.
• 6: SCHWARTZ, E S. Network properties of computer programs Armour Research Foun- (tation, 19fff) (unpublished paper).
• 7: PROSSER, }~ T Applicatmtt of Boolean matrices to the analysis of flow charts. Proc. Eastern Joint Comput. Conf., 1959.
• 8: K~l~P, g. M A note on She apphc~tmn of graph theory to digital computer program.- ruing Informal,on Con~r (June 1960), I79-190.
• 9: VEBLEN, O. Analysis Situs. Amer Math Soc. Colloquium Publ Vol. 5, Part 2, 2d Ed 1931, Ch. 1.
• 10: BARANKIN, E W. Precedence matrices. Management Sciences Ilesearch Prolect, Report 26, University of Cahfornia, Dec. 1953
• 11: JOHNSON, S M Optimal two- and three-stage production schedules w~th setup times included. Naval Res Log Qua~ t (Mar 1954), 61-68.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Design, Theory