Thumbnail
Access Restriction
Subscribed

Author Schwartz, Eugene S.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1961
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1961-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 8
Issue Number 4
Page Count 25
Starting Page 513
Ending Page 537


Open content in new tab

   Open content in new tab
Source: ACM Digital Library