Browse Prior Art Database

Pipelined Execution of Loops With Iteration Dependencies

IP.com Disclosure Number: IPCOM000039438D
Original Publication Date: 1987-Jun-01
Included in the Prior Art Database: 2005-Feb-01
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Darema-Rogers, F: AUTHOR [+4]

Abstract

Execution of loops in parallel is a major target in parallel processing. Where an iteration of the loop requires data from at least one preceding loop, such as in recursive programming, parallel processing has previously been mostly unavailable.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 1 of 2

Pipelined Execution of Loops With Iteration Dependencies

Execution of loops in parallel is a major target in parallel processing. Where an iteration of the loop requires data from at least one preceding loop, such as in recursive programming, parallel processing has previously been mostly unavailable. However, the technique herein disclosed provides for executing loops with iteration dependencies in a parallel processing system, and comprises: reserving a control character for indicating to a preprocessor the location of high-level parallelizing specifications; defining a pair of iteration dependency specification statements, wherein a first iteration dependency specification statement indicates the accomplishment of an iteration, and the second iteration dependency specification statement requires the execution of a given iteration prior to its execution of a next iteration; using said iteration dependency specification statements in conjunction with said reserved control character; and defining a control variable in shared memory for implementing each pair of defined iteration dependency specifications. In order for a preprocessor for a parallel processing system to locate high-level specifications, particular control characters, such as an @ character, are reserved and used for identifying the high-level specifications. If desired, high-level statements may be used in conjunction with the reserved control character. The high-level statements may then be implemented by the preprocessor such as is used in the VM/EPEX system. For performing parallel processing on a loop dependent on a previous iteration of the loop, two statements are defined. A high-level specification WAIT statement is inserted directly before the statement of the loop requiring the results of a previous iteration. The WAIT statement forces the particular processor to wait until the required result is obtained before proceeding. The processor is informed that the required result is available by the RELEASE statement which is inserted after the statement which provides the required result. The high-level RELEASE and WAIT statements may be implemented by the use of a control variable set up by the preprocessor and located in shared memory. The control variable would be incremented (due to the RELEASE statement) upon each performance of the required result statement. When the variable reached the required value (e.g., L-1...