Method of synchronizing parallel processors employing channels and compiling method minimizing cross-processor data dependencies

Claim 2

A compiling method for scheduling data-dependent operations, describable as a directed acyclic graph of nodes, representing operations, and edges, representing data dependencies, into a plurality of parallel instruction streams for execution by a plurality of respective digital processors and for scheduling synchronizing data transfers on a plurality of inter-processor data transfer means, each being usable for transfer of synchronizing data from one to another of said processors, said method comprising: scheduling all nodes of said graph into said plurality of streams with each edge of said graph being describable as either an intra-stream edge directed between nodes scheduled in the same stream or an inter-stream edge directed between nodes scheduled in different streams, said nodes being scheduled in a manner that the intra-stream edges are directed in the same direction; identifying synchronization redundant edges among said inter-stream edges; and scheduling inter-stream edges which are not synchronization redundant as synchronizing data transfers on said inter-processor data transfer means.

Claim 3

The method of claim 1 wherein said scheduling all nodes is performed in a manner for substantially minimizing the number of inter-stream edges.

Claim 4

The method of claim 1 wherein said scheduling all nodes is determined generally inversely from the order in which the operations represented by said nodes are to be performed by said processors and comprises: identifying, among unscheduled nodes of said graph, a plurality of nodes having the greatest height; and scheduling nodes from said plurality of nodes of greatest height into different streams, while substantially minimizing the number of resulting inter-stream edges directed to scheduled nodes.

Claim 5

The method of claim 3 wherein said scheduling all nodes further comprises: identifying, for a plurality of said scheduled nodes from said plurality of nodes of greatest height, any sub-graphs rooted at said scheduled nodes; and scheduling, if possible, an equal number of nodes of the respective identified sub-graphs into the same respective streams as the scheduled nodes of greatest height rooting said respective sub-graphs, said scheduling of nodes of the respective identified sub-graphs being determined in order of descending node height from said scheduled nodes rooting said respective identified sub-graphs.

Claim 6

The method of claim 4 further comprising repeating said identifying among unscheduled nodes of said graph, a plurality of nodes having the greatest height after said scheduling, if possible, an equal number of nodes of the respective identified sub-graphs.

Claim 7

The method of claim 1 wherein said scheduling inter-stream edges which are not synchronization redundant comprises: identifying among said inter-stream edges which are not synchronization redundant, edges representing data dependencies which must be resolved in a definite order as candidates for scheduling by re-use of the same inter-processor data transfer means.

Claim 8

The method of claim 6 wherein said identifying among said inter-stream edges which are not synchronization redundant, edges as candidates for scheduling by re-use of the same inter-processor data transfer means, is such that re-use will not cause implicit synchronizations due to the possibility of blocking to writing on said data transfer means.

Claim 9

The method of claim 6 further comprising: identifying implicit synchronizations due to the possibility of blocking to reading on re-used inter-processor data transfer means; and identifying further inter-stream edges that would be rendered synchronization redundant by said implicit synchronizations.

Claim 10

A compiling method for scheduling data-dependent operations, describable as a directed acyclic graph of nodes, representing operations, and edges, representing data dependencies, into a plurality of parallel instruction streams for execution by a plurality of respective digital processors comprising: scheduling all nodes of said graph into said plurality of streams with each edge of said graph being describable as either an intra-stream edge directed between nodes in the same stream or an inter-stream edge directed between nodes in different streams, said nodes being scheduled in a manner such that the intra-stream edges are directed in the same direction; and wherein said scheduling all nodes is performed in a manner for minimizing the number of inter-stream edges.

Claim 11

A compiling method for scheduling data-dependent operations, describable as a directed acyclic graph of nodes, representing operations, and edges, representing data dependencies, into a plurality of parallel instruction streams for execution by a plurality of respective digital processors comprising: scheduling all nodes of said graph into said plurality of streams with each edge of said graph being describable as either an intra-stream edge directed between nodes in the same stream or an inter-stream edge directed between nodes in different streams, said nodes being scheduled in a manner such that the intra-stream edges are directed in the same direction; and wherein said scheduling all nodes is performed in a manner for minimizing the number of inter-stream edges.

Claim 12

The method of claim 9 wherein said scheduling all nodes is determined generally inversely from the order in which the operations represented by said nodes are to be performed by said processors and comprises: identifying, among unscheduled nodes of said graph, a plurality of nodes having the greatest height in said graph; and scheduling nodes from said plurality of nodes of greatest height into different streams while minimizing the number of resulting inter-stream edges directed to scheduled nodes.

Claim 13

The method of claim 10 further comprising: identifying, for a plurality of said nodes scheduled from said plurality of nodes of greatest height, any sub-graphs rooted at each said node; and scheduling, if possible, an equal number of nodes of the respective identified sub-graphs into the same respective streams as the scheduled nodes from said plurality of nodes of greatest height rooting said respective sub-graphs, said scheduling of nodes of the respective identified sub-graphs being determined in order of descending node height from said scheduled nodes rooting said respective identified sub-graphs.

Claim 14

The method of claim 11 further comprising repeating said identifying among unscheduled nodes of said graph, a plurality of nodes having the greatest height after said scheduling, if possible, an equal number of nodes of the respective identified sub-graphs.

Claim 15

In a multiprocessor having first and second parallel processors for performing sequential operations specified in respective first and second instruction streams having cross-stream data dependencies, a register channel accessible by said processors characterized by a synchronization bit indicating whether said register channel has been written to, and a memory accessible to said processors not having a synchronization bit, the method of passing plural cross-stream dependent data between said processors in a synchronizing fashion comprising: first writing, by said first processor to said memory, first cross-stream dependent data available to said first processor; second writing, by said first processor to said register channel, not earlier than said first writing, second cross-stream dependent data available to said first processor; waiting, if necessary, by said second processor until said synchronization bit indicates that said second writing has occurred; first reading, by said second processor, the second cross-stream dependent data from said register channel; and second reading, by said second processor, not earlier than said first reading of the first cross-stream dependent data from said memory.

Claim 16

In a multiprocessor having first and second parallel processors for performing sequential operations specified in respective first and second instruction streams having cross-stream data dependencies, a register channel accessible by said processors characterized by a synchronization bit indicating whether said register channel has been written to, and a memory accessible to said processors not having a synchronization bit, the method of passing plural cross-stream dependent data between said processors in a synchronizing fashion comprising: first writing, by said first processor to said memory, first cross-stream dependent data available to said first processor; second writing, by said first processor to said register channel, not earlier than said first writing, second cross-stream dependent data available to said first processor; waiting, if necessary, by said second processor until said synchronization bit indicates that said second writing has occurred; first reading, by said second processor, the second cross-stream dependent data from said register channel; and second reading, by said second processor, not earlier than said first reading of the first cross-stream dependent data from said memory.

Claim 17

In a multiprocessor having first, second and third parallel processors for performing sequential operations specified in respective first, second and third instruction streams having cross-stream data dependencies, first and second register channels accessible by said processors each characterized by a synchronization bit indicating whether said register channel has been written to, and a memory accessible to said processors not having a synchronization bit, the method of passing plural cross-stream dependent data between said processors in synchronizing fashion comprising: first writing, by said first processor to said memory, first cross-stream dependent data available to said first processor; second writing by said first processor to said first register channel, not earlier than said first writing, second cross-stream dependent data available to said first processor; first waiting, if necessary, by said second processor until said synchronization bit of said first register channel indicates that said second writing has occurred; first reading by said second processor of the second cross-stream dependent data from said first register channel; third writing, by said second processor to said second register channel, not earlier than said second reading, third cross-stream dependent data available to said second processor; second waiting, if necessary, by said third processor until said synchronization bit of said second register channel indicates that said third writing has occurred; second reading, by said third processor, the third cross-stream dependent data from said second register channel; and third reading by said third processor, not earlier than said second reading, the first cross-stream dependent data from said memory.

Claim 18

In a multiprocessor having first, second and third parallel processors for performing sequential operations specified in respective first, second and third instruction streams having cross-stream data dependencies, first and second register channels accessible by said processors each characterized by a synchronization bit indicating whether said register channel has been written to, and a memory accessible to said processors not having a synchronization bit, the method of passing plural cross-stream dependent data between said processors in synchronizing fashion comprising: first writing, by said first processor to said memory, first cross-stream dependent data available to said first processor; second writing by said first processor to said first register channel, not earlier than said first writing, second cross-stream dependent data available to said first processor; first waiting, if necessary, by said second processor until said synchronization bit of said first register channel indicates that said second writing has occurred; first reading by said second processor of the second cross-stream dependent data from said first register channel; third writing, by said second processor to said second register channel, not earlier than said second reading, third cross-stream dependent data available to said second processor; second waiting, if necessary, by said third processor until said synchronization bit of said second register channel indicates that said third writing has occurred; second reading, by said third processor, the third cross-stream dependent data from said second register channel; and third reading by said third processor, not earlier than said second reading, the first cross-stream dependent data from said memory.

Claim 19

In a multiprocessor having a plurality of parallel processors for performing sequential operations specified respectively in a plurality of instruction streams having cross-stream data dependencies, a plurality of register channels accessible by said processors for synchronizing data passing between said processors, and a memory accessible to said processors for non-synchronizing data passing between said processors, the method for passing plural cross-stream dependent data between processors in a synchronized fashion comprising: first writing, by one of said processors to said memory means, first cross-stream dependent data available to said first processor; last reading said first cross-stream dependent data from said memory means by another of said processors; and enforcing other cross-stream data dependencies by a sequence of one or more writing-reading pairs associated respectively with one or more register channels, said sequence beginning with a second writing to a register channel, not earlier than said first writing, and ending with a next-to-last reading, from the same or different register channel not later than said last reading.

Claim 20

In a multiprocessor having a plurality of parallel processors for performing sequential operations specified respectively in a plurality of instruction streams having cross-stream data dependencies, a plurality of register channels accessible by said processors for synchronizing data passing between said processors, and a memory accessible to said processors for non-synchronizing data passing between said processors, the method for passing plural cross-stream dependent data between processors in a synchronized fashion comprising: first writing, by one of said processors to said memory means, first cross-stream dependent data available to said first processor; last reading said first cross-stream dependent data from said memory means by another of said processors; and enforcing other cross-stream data dependencies by a sequence of one or more writing-reading pairs associated respectively with one or more register channels, said sequence beginning with a second writing to a register channel, not earlier than said first writing, and ending with a next-to-last reading, from the same or different register channel not later than said last reading.