US5832272A — Apparatus and method for parallel computation

Claim 1

Independent Claim 145 words

Data processing apparatus for the execution of a sequential program, comprising at least one memory and a plurality of parallel processors all connected for mutual transfer of messages under the control of a control system; in which the processors are programmed each with part of the sequential program, those steps of each part, which would access or modify a data variable, being serially labelled in accordance with the intended sequence of the whole sequential program; in which the control system is arranged so as to label every message intended to access or modify the memory with a label corresponding to the serial label of the program step from which the message is derived; and in which the control system is arranged, for said at least one memory, to allow memory-accessing and -modifying operations only in the sequential order of the serial labels on the messages.

Claim 2

Dependent Claim 145 words

Data processing apparatus for the execution of a sequential program, comprising at least one memory and a plurality of parallel processors all connected for mutual transfer of messages under the control of a control system; in which the processors are programmed each with part of the sequential program, those steps of each part, which would access or modify a data variable, being serially labelled in accordance with the intended sequence of the whole sequential program; in which the control system is arranged so as to label every message intended to access or modify the memory with a label corresponding to the serial label of the program step from which the message is derived; and in which the control system is arranged, for said at least one memory, to allow memory-accessing and -modifying operations only in the sequential order of the serial labels on the messages.

Claim 3

Independent Claim 115 words

A method of executing a sequential program, comprising: labelling those steps of the sequential program, which would access or modify a data variable, with a serial label in accordance with the intended sequence of the program; parallelising the sequential program to derive a plurality of separate program segments, each step of which segments, which would access or modify a data variable, having a serial label corresponding to the serial label of that step in the original sequential program; and running the program segments in parallel on parallel processors under a control system which ensures that all memory-accessing and -modifying operations are executed only in the sequential order of the serial labels on the corresponding steps.

Claim 4

Independent Claim 115 words

A method of executing a sequential program, comprising: labelling those steps of the sequential program, which would access or modify a data variable, with a serial label in accordance with the intended sequence of the program; parallelising the sequential program to derive a plurality of separate program segments, each step of which segments, which would access or modify a data variable, having a serial label corresponding to the serial label of that step in the original sequential program; and running the program segments in parallel on parallel processors under a control system which ensures that all memory-accessing and -modifying operations are executed only in the sequential order of the serial labels on the corresponding steps.

Claim 5

Dependent Claim 142 words

Data processing apparatus for parallelising compilation of a sequential program, comprising means for reading the program code, a counter for applying a serial label to each statement of the program code which would access or modify a data variable, the label being indicative of its intended order of execution, and storing the label with the statement, means for decomposing the program into code segments intended for execution by respective parallel processors, according to predetermined parallelisation algorithms stored in the data processing apparatus, and output means for providing as an output the serially-labelled code segments suitable for execution, in parallel by processors controlled to respect the serial-labelling at every memory unit which might be accessed or modified when the parallel processors run the code segments, allowing memory-accessing or modifying operations only on the sequential order of the serial labels on the originating statement.

Claim 6

Dependent Claim 142 words

Data processing apparatus for parallelising compilation of a sequential program, comprising means for reading the program code, a counter for applying a serial label to each statement of the program code which would access or modify a data variable, the label being indicative of its intended order of execution, and storing the label with the statement, means for decomposing the program into code segments intended for execution by respective parallel processors, according to predetermined parallelisation algorithms stored in the data processing apparatus, and output means for providing as an output the serially-labelled code segments suitable for execution, in parallel by processors controlled to respect the serial-labelling at every memory unit which might be accessed or modified when the parallel processors run the code segments, allowing memory-accessing or modifying operations only on the sequential order of the serial labels on the originating statement.

Claim 7

Independent Claim 134 words

A method of compiling a sequential program for execution by parallel processors, comprising reading the program code, applying a serial label to each statement of the program code which would access or modify a data variable, the label being indicative of its intended order of execution, and storing the label with the statement, decomposing the program into code segments intended for execution by respective parallel processors, according to predetermined parallelisation algorithms stored in the data processing apparatus, and providing as an output the serially-labelled code segments suitable for execution, in parallel using processors controlled to respect the serial-labelling at every memory unit which might be accessed or modified when the parallel processors run the code segments, allowing memory-accessing or modifying operations only in the sequential order of the serial labels on the originating statement.

Claim 8

Independent Claim 134 words

A method of compiling a sequential program for execution by parallel processors, comprising reading the program code, applying a serial label to each statement of the program code which would access or modify a data variable, the label being indicative of its intended order of execution, and storing the label with the statement, decomposing the program into code segments intended for execution by respective parallel processors, according to predetermined parallelisation algorithms stored in the data processing apparatus, and providing as an output the serially-labelled code segments suitable for execution, in parallel using processors controlled to respect the serial-labelling at every memory unit which might be accessed or modified when the parallel processors run the code segments, allowing memory-accessing or modifying operations only in the sequential order of the serial labels on the originating statement.

Claim 9

Independent Claim 116 words

A method of parallel computation in which the program code, executed in local parallel processors accessing and modifying one or more global memories, includes a serial label associated with each code statement which would access or modify a data variable, the label being representative of the sequential order of execution of that statement in an equivalent sequential program which would always produce the same results as the parallel computation, comprising, for each global memory, reading the serial labels of all the messages from the processors instructing access or modification of the memory, and allowing such access or modification only in the sequence of the serial labels, irrespective of the actual time of receipt of such messages.

Claim 10

Independent Claim 116 words

A method of parallel computation in which the program code, executed in local parallel processors accessing and modifying one or more global memories, includes a serial label associated with each code statement which would access or modify a data variable, the label being representative of the sequential order of execution of that statement in an equivalent sequential program which would always produce the same results as the parallel computation, comprising, for each global memory, reading the serial labels of all the messages from the processors instructing access or modification of the memory, and allowing such access or modification only in the sequence of the serial labels, irrespective of the actual time of receipt of such messages.

Claim 11

Dependent Claim 129 words

A parallel computation system comprising parallel processors storing their own program code which may access and modify one or more memories common to two or more processors, a serial label being stored in association with each statement of the program code which would access or modify a data variable, the label being representative of the sequential order of execution of that statement in an equivalent sequential program which would always produce the same results as the parallel computation; and a control system arranged, for each common memory, to read the serial labels of all the messages from the processors instructing access or modification of the memory, and for ensuring their execution only in the sequence of the serial labels, irrespective of the actual time of receipt of such messages.

Claim 12

Dependent Claim 129 words

A parallel computation system comprising parallel processors storing their own program code which may access and modify one or more memories common to two or more processors, a serial label being stored in association with each statement of the program code which would access or modify a data variable, the label being representative of the sequential order of execution of that statement in an equivalent sequential program which would always produce the same results as the parallel computation; and a control system arranged, for each common memory, to read the serial labels of all the messages from the processors instructing access or modification of the memory, and for ensuring their execution only in the sequence of the serial labels, irrespective of the actual time of receipt of such messages.

Claim 13

Dependent Claim 95 words

Apparatus according to claim 1 or 3, or a system according to claim 6, comprising an active order-preserving memory for exploiting indirection functions to pre-schedule read and write operations into their respective locations, and means for sending run-time-determined parameters of such indirection functions at appropriate points during the program execution when these parameters become known, to the order-preserving memory to start execution of the skeleton of the code which would access or modify data variables, whereby a more efficient parallel execution is achieved than without such indirection functions, whilst preserving the proper sequence of tasks.

Claim 14

Dependent Claim 50 words

Apparatus according to claim 7, in which the control system comprises means for exchanging the labelled messages between the order-preserving memory and the processor nodes during execution, once the run-time parameters of the indirection functions required for that execution have been stored in the order-preserving memory and the processor nodes.

Claim 15

Dependent Claim 34 words

Apparatus according to claim 7, in which the control system comprises means for performing a time-space transformation on the indirection functions in the order-preserving memory during execution but before the execution of corresponding loops.

Claim 16

Dependent Claim 36 words

A method according to claim 2, 4 or 5, comprising executing indirection functions in an active memory, once the required parameters become available, and thereby anticipating and pre-scheduling read and write operations on the resident data.

Claim 17

Dependent Claim 28 words

A method according to claim 10, comprising performing a time-space transformation on the indirection functions in the order-preserving memory during execution but before the execution of corresponding loops.

Claim 18

Dependent Claim 21 words

Data processing apparatus or a method according to any of claims 1 to 6, in which the parallel processing is asynchronous.

Claim 19

Dependent Claim 23 words

Data processing apparatus or a method according to any of claims 1 to 6, in which the parallel processors are shared memory machines.

Claim 20

Dependent Claim 23 words

Data processing apparatus or a method according to any of claims 1 to 6, in which the parallel processors are distributed memory machines.

Claim 21

Dependent Claim 13 words

A system according to claim 6, in which the parallel processors are transputers.

Claim 22

Dependent Claim 38 words

Telecommunications apparatus for the transfer of data representing sounds or images, comprising data processing apparatus or a system according to claim 1, 3 or 6, in which the sequential program is a conventional program for controlling such transfer.

Claim 23

Dependent Claim 14 words

Telecommunications apparatus according to claim 16, in the form of a digital telephone exchange.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2001-11-02	2002-05-04	2002-11-03	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2005-11-02	2006-05-04	2006-11-03	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2009-11-02	2010-05-04	2010-11-03	$7700.00	Window Closed / Lapsed

Apparatus and method for parallel computation

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag