Browse Prior Art Database

Control Matrix for Parallel Processing Digital Computers in a Multi-Job Environment

IP.com Disclosure Number: IPCOM000049278D
Original Publication Date: 1982-Apr-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 3 page(s) / 47K

Publishing Venue

IBM

Related People

Cases, M: AUTHOR [+4]

Abstract

In a parallelly structured computer system, a control structure or priority matrix is required among a given unordered set of tasks to determine the minimum number of precedential steps required to perform the tasks if parallelism is allowed. As is known, a fully determined precedence matrix, H, defines a scheduling of precedence among a set of tasks. In forming the precedence matrices, the fact that task number "i", for example, must precede number "j" is expressed by writing a "1" in the element corresponding to the "i"/th/ row and "j"/th/ column, but not conversely. By performing manipulations on these matrices, aside from obtaining all implicit priority statements, also redundant ordering restrictions and hidden contradictions can be disclosed.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Control Matrix for Parallel Processing Digital Computers in a Multi-Job Environment

In a parallelly structured computer system, a control structure or priority matrix is required among a given unordered set of tasks to determine the minimum number of precedential steps required to perform the tasks if parallelism is allowed. As is known, a fully determined precedence matrix, H, defines a scheduling of precedence among a set of tasks. In forming the precedence matrices, the fact that task number "i", for example, must precede number "j" is expressed by writing a "1" in the element corresponding to the "i"/th/ row and "j"/th/ column, but not conversely. By performing manipulations on these matrices, aside from obtaining all implicit priority statements, also redundant ordering restrictions and hidden contradictions can be disclosed.

In scanning the columns of H, the columns whose elements are all zeros determine the tasks that can be started first. These tasks can be done in parallel since there exists no precedence requirements among them. Once these tasks are done, then the elements in the rows corresponding to these tasks are all turned to zero. Now the columns are scanned again as before, and those columns whose elements are all zeros determine the tasks that can be done in parallel next. This procedure is continued until all columns are zero. Those columns which are the last ones to become all zeros are the tasks that are finished last.

In accordance with the present scheme the aforementioned procedure is extended to a multi-job environment to detect if two or more tasks can be executed in parallel because their subtasks have no precedences among an unordered set of jobs. Although this scheme can be generalized to any set of jobs, it is best depicted with a simple example. If job #1 and job #2 hav...