US4591971A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for parallel processing of digital signals using multiple independent signal processors
Assignee: National Research Development Corp UK
•
Filing: 1985-01-02
•
Granted: 1986-05-27
•
Expires: 2005-01-02
Abstract
Abstract A digital computer has an addressable store 1, which may comprise segments 1a, 1b, etc. and a plurality of independent digital processing units 3a, 3b, etc. all communicating with the store 1 through a communication facility 2. Addresses in store 1 containing packets of digital data which require processing are held in a group of identifier stores 4a, 4b, etc. to which group the processing units all have access. Where processing results in the generation of fresh packets of data addresses for such data in store 1 are held in a second group of identifier stores 5a, 5b to which the processing units also have access. Controllers 6a, 6b, etc. and 7a, 7b, etc. ensure even transfer of identifier address among the stores of a group and act as interfaces between the identifier stores and the processing units.
Inventors
- 👤 John Darlington
- 👤 Michael J. Reeve
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 22:16
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/44; G06F9/448; G06F9/4494
Claims Analysis
Total Claims: 57
Claim 1
Independent Claim
127 words
A digital computer comprising: digital store means for storing digital data at identifiable locations in the form of packets comprising both instructions and other data for processing in accordance with such instructions; a plurality of independent digital processing units for processing said packets; communication means for transferring data between the processing units and the digital store means; a first group of discrete digital stores arranged to store identifiers of packets which require processing; and transfer and interface means connected to said first group of stores for enabling any identifier stored in any store of said first group to be transferred to any other store within that group and to enable transfer of identifiers in either direction between the processing units and the first group of identifier stores.
Claim 2
Dependent Claim
127 words
A digital computer comprising: digital store means for storing digital data at identifiable locations in the form of packets comprising both instructions and other data for processing in accordance with such instructions; a plurality of independent digital processing units for processing said packets; communication means for transferring data between the processing units and the digital store means; a first group of discrete digital stores arranged to store identifiers of packets which require processing; and transfer and interface means connected to said first group of stores for enabling any identifier stored in any store of said first group to be transferred to any other store within that group and to enable transfer of identifiers in either direction between the processing units and the first group of identifier stores.
Claim 3
Dependent Claim
43 words
The digital computer as claimed in claim 1 in which the number of identifier stores in the group corresponds to the number of processing units and the transfer and interface means couples each processing unit to an individual identifier store of that group.
Claim 4
Dependent Claim
20 words
The digital computer as claimed in claim 1 in which the digital store means comprises a plurality of storage segments.
Claim 5
Dependent Claim
22 words
The digital computer as claimed in claim 3 in which the number of storage segments corresponds to the number of processing units.
Claim 6
Dependent Claim
31 words
A digital computer as in claim 3 wherein said communication means enables transfer of packets to take place between any one of said processing units and any of said storage segments.
Claim 7
Dependent Claim
60 words
The digital computer as in claim 1 further including: means for storing identifiers of locations in the digital store means which are available to receive packets; and means for transferring said location identifiers from said locations identifiers storing means to the processing units when packets processed by said processing units are required to be stored in the digital store means.
Claim 8
Dependent Claim
91 words
The digital computer as in claim 1 further including: a second group of discrete stores arranged to store identifiers of ones of the locations in the digital store means which are available to receive packets; and a further transfer and interface means associated with said second group of stores for enabling any identifier stored in any of said stores of said second group to be transferred to any other store within said second group and for coupling the processing units to at least one of the stores in the second group.
Claim 9
Dependent Claim
44 words
A digital computer as in claim 7 wherein: the number of identifier stores in said second group corresponds to the number of processing units; and the further transfer and interface means couples each processing unit to a respective identifier store in said second group.
Claim 10
Dependent Claim
156 words
A digital computer comprising: digital store means for storing digital data at identifiable locations in the form of packets comprising both instructions and other data for processing in accordance with such instructions; a plurality of independent digital processing units for processing said packets; communication means for transferring data between the processing units and the digital store means; a first group of discrete digital stores arranged to store identifiers of packets which require processing; a second group of discrete stores arranged to store identifiers of ones of the locations in said digital store means which are available to receive packets; and separate transfer and interface means connected to each of said first and second groups of stores for enabling any identifier stored in any store of a group to be transferred to any other store within that group and to enable transfer of identifiers in either direction between the processing units and the groups of identifier stores.
Claim 11
Dependent Claim
156 words
A digital computer comprising: digital store means for storing digital data at identifiable locations in the form of packets comprising both instructions and other data for processing in accordance with such instructions; a plurality of independent digital processing units for processing said packets; communication means for transferring data between the processing units and the digital store means; a first group of discrete digital stores arranged to store identifiers of packets which require processing; a second group of discrete stores arranged to store identifiers of ones of the locations in said digital store means which are available to receive packets; and separate transfer and interface means connected to each of said first and second groups of stores for enabling any identifier stored in any store of a group to be transferred to any other store within that group and to enable transfer of identifiers in either direction between the processing units and the groups of identifier stores.
Claim 12
Dependent Claim
29 words
The digital computer as claimed in claim 9 in which the identifier stores of the respective groups are coupled together in ring-like fashion through said transfer and interface means.
Claim 13
Dependent Claim
47 words
A digital computer as in claim 9 wherein: the number of identifier stores in each group correspond to the number of processing units; and said transfer and interface means associated with each group of stores couples each processing unit to a respective identifier store of each group.
Claim 14
Dependent Claim
18 words
A digital computer as in claim 9 wherein said digital store means comprises a plurality of storage segments.
Claim 15
Dependent Claim
20 words
A digital computer as in claim 12 wherein the number of storage segments corresponds to the number of processing units.
Claim 16
Independent Claim
112 words
A system for processing digital signals comprising: plural independent digital signal processing means each for independently processing digital signals communicated thereto; first digital signal storing means for storing a first plurality of respective packets of digital signals; means for scheduling said first plurality of packets for processing by selected ones of said processing means and for rescheduling at least one of said first plurality of packets for processing by any selected one of said processing means other than the processing means previously scheduled to process said one packet; and means for communicating selected packets between said first storing means and the ones of said processing means scheduled to process said selected packets.
Claim 17
Independent Claim
112 words
A system for processing digital signals comprising: plural independent digital signal processing means each for independently processing digital signals communicated thereto; first digital signal storing means for storing a first plurality of respective packets of digital signals; means for scheduling said first plurality of packets for processing by selected ones of said processing means and for rescheduling at least one of said first plurality of packets for processing by any selected one of said processing means other than the processing means previously scheduled to process said one packet; and means for communicating selected packets between said first storing means and the ones of said processing means scheduled to process said selected packets.
Claim 18
Dependent Claim
75 words
A system as in claim 14 wherein said scheduling means includes: a first plurality of discrete identifier storing means for storing data identifying said first plurality of packets, each of said first plurality of identifier storing means associated with at least one of said processing means; and means for transferring data from at least a first of said first plurality of identifier storing means to any other one of said first plurality of storing means.
Claim 19
Dependent Claim
23 words
A system as in claim 15 wherein said data transferring means also selects said other one of said first plurality of storing means.
Claim 20
Dependent Claim
78 words
A system as in claim 15 wherein: each of said first plurality of packets includes a function data field representing an operation to be performed and an argument list data field representing at least one argument; and each of said processing means includes means for processing the argument represented by the argument list data field of each packet communicated thereto in accordance with the operation represented by the function data field of said packet to produce a result.
Claim 21
Dependent Claim
130 words
A system as in claim 17 wherein: said first storing means also stores a second plurality of packets each of which include a function data field representing an operation to be performed and an argument list data field identifying at least a first of said first plurality of packets; said scheduling means includes means for determining when one of said processing means has produced a result in accordance with said operation represented by the function data field and said argument represented by said argument list data field of said first packet; and said scheduling means also schedules the ones of said second plurality of packets including an argument list data field identifying said first packet for processing by a processing unit in response to the determination of said determining means.
Claim 22
Dependent Claim
26 words
A system as in claim 18 further including means for linking ones of said second plurality of packets to ones of said first plurality of packets.
Claim 23
Dependent Claim
98 words
A system as in claim 18 wherein: said first packet further includes a signal list data field identifying each of said second plurality of packets which include an argument list data field identifying said first packet; each of said processing means further includes means for transmitting a signal to each of said second plurality of packets identified by the signal list data field of the ones of said first plurality of packets communicated thereto; and said determining means comprises means for determining which of said second plurality of packets have received a signal transmitted by said transmitting means.
Claim 24
Dependent Claim
91 words
A system as in claim 20 wherein: said system further includes means for identifying portions of said first storing means available for storing new packets; each of said processing means also selectively generates new ones of said first plurality of packets; said communicating means also communicates said newly generated packets to said first storing means for storage in a portion of said first storing means identified by said available portions identifying means; and said scheduling means also schedules said newly generated packets for processing by selected ones of said processing means.
Claim 25
Dependent Claim
80 words
A system as in claim 21 wherein said available portions identifying means includes: a second plurality of discrete identifier storing means each storing data indentifying portions of said first storing means available for storing new packets, each of said second plurality of discrete storing means associated with at least one of said processing means; and means for transferring data from a first of said second plurality of storing means to any other one of said second plurality of storing means.
Claim 26
Dependent Claim
62 words
A system as in claim 22 wherein: said data identifying portions of said first storing means available for storing new packets includes a plurality of respective indicia of spaces in said first storing means each capable of storing exactly one packet; and each of the indicia of said spaces is stored in only one of said second plurality of identifier storing means.
Claim 27
Dependent Claim
55 words
A system as in claim 22 further including means for communicating data identifying the location in said first storing means of ones of said first plurality of packets not identified by the argument list data field of any of said second plurality of packets between said processing means and said second plurality of storing means.
Claim 28
Dependent Claim
20 words
A system as in claim 22 wherein each of said second plurality of discrete identifier storing means comprises a stack.
Claim 29
Dependent Claim
146 words
A system as in claim 15 wherein: said first storing means also stores a second plurality of packets the processing of each of which requires a result produced by the processing of at least one of said first plurality of packets; at least a first of said first plurality of packets further includes a signal list data field identifying the ones of said second plurality of packets the processing of which require a result produced by the processing of said first packet; each of said processing means further includes means for transmitting a signal to each of said second plurality of said packets identified by the signal list data field of the ones of said first plurality of packets communicated thereto; and said system further includes determining means for determining which of said second plurality of packets have received a signal transmitted by said transmitting means.
Claim 30
Dependent Claim
93 words
A system as in claim 26 wherein: said system further includes means for identifying portions of said first storing means available for storing new packets; each of said processing means also selectively generates new ones of said first plurality of packets; said communicating means also communicates said newly generated packets to said first storing means for storage in a portion of said first storing means identified by said available portions identifying means; and said scheduling means also schedules said newly generated packets for processing by selected ones of said plurality of processing means.
Claim 31
Dependent Claim
94 words
A system as in claim 15 wherein: each of said processing means also selectively generates new ones of said first plurality of packets; and said system further includes: a second plurality of discrete identifier storing means each storing data identifying portions of said first storing means available for storing new packets, each of said second plurality of storing means associated with at least one of said processing means, and means for transferring data from a first of said second plurality of storing means to any other one of said second plurality of storing means.
Claim 32
Dependent Claim
20 words
A system as in claim 15 wherein each of said first plurality of discrete identifier storing means comprises a stack.
Claim 33
Dependent Claim
39 words
A system as in claim 14 wherein: at least one of said plural processing means is dedicated to performing a predetermined function; and said scheduling means schedules selected ones of said packets for processing by said dedicated processing means.
Claim 34
Dependent Claim
25 words
A system as in claim 14 wherein said communicating means comprises a communications network shared by said plural processor means and said first storing means.
Claim 35
Independent Claim
116 words
A method of processing digital signals comprising the steps of: (1) storing digital signals at identifiable locations of a digital store means in the form of packets comprising both instructions and other data for processing in accordance with such instructions; (2) communicating digital signals between the digital store means and a plurality of independent digital signal processing units; (3) processing said packets independently and in parallel at said plurality of processing units; (4) storing identifiers of locations of packets which require processing at groups of locations separate from the locations of packets the identifiers identify; (5) transferring identifiers between said groups of locations; and (6) communicating identifiers between said processing units and said groups of locations.
Claim 36
Independent Claim
116 words
A method of processing digital signals comprising the steps of: (1) storing digital signals at identifiable locations of a digital store means in the form of packets comprising both instructions and other data for processing in accordance with such instructions; (2) communicating digital signals between the digital store means and a plurality of independent digital signal processing units; (3) processing said packets independently and in parallel at said plurality of processing units; (4) storing identifiers of locations of packets which require processing at groups of locations separate from the locations of packets the identifiers identify; (5) transferring identifiers between said groups of locations; and (6) communicating identifiers between said processing units and said groups of locations.
Claim 37
Dependent Claim
32 words
A method as in claim 32 further including the step of enabling an identifier stored in any location within one of said groups of locations to be transferred to any other group.
Claim 38
Dependent Claim
52 words
A method as in claim 33 wherein: each of said processing units has associated therewith at least one of said groups of locations; and said communicating step (6) comprises the step of communicating identifiers in either direction between said processing units and the groups of said locations associated with said processing units.
Claim 39
Dependent Claim
43 words
A method as in claim 33 wherein said storing step (1) includes the step of storing data in a plurality of storage segments of said digital store means, each of said processing units being associated with a predetermined one of said storage segments.
Claim 40
Dependent Claim
28 words
A method as in claim 34 wherein said transferring step (5) includes the step of equalizing the number of identifiers stored in each of the groups of locations.
Claim 41
Dependent Claim
58 words
A method as in claim 32 further including: storing identifiers of locations in said digital store means which are available to receive packets in further groups of locations separate from the locations of packets the identifiers identify; transferring identifiers between said further groups of locations; and communicating identifiers between said processing units and said further groups of locations.
Claim 42
Independent Claim
121 words
A method of processing digital signals comprising the steps of: (1) storing a first plurality of respective packets of digital signals in a first store accessible to each of a plurality independent digital signal processing units; (2) scheduling said first packets for processing by selected ones of said plurality of processing units; (3) rescheduling at least one of said first plurality of packets for processing by any selected one of said plurality of processing units other than the unit previously scheduled to process said one packet; (4) communicating selected packets between said first store and the ones of said processing units scheduled to process said selected packets; and (5) processing, independently at each of said processing units, the packets communicated thereto.
Claim 43
Independent Claim
121 words
A method of processing digital signals comprising the steps of: (1) storing a first plurality of respective packets of digital signals in a first store accessible to each of a plurality independent digital signal processing units; (2) scheduling said first packets for processing by selected ones of said plurality of processing units; (3) rescheduling at least one of said first plurality of packets for processing by any selected one of said plurality of processing units other than the unit previously scheduled to process said one packet; (4) communicating selected packets between said first store and the ones of said processing units scheduled to process said selected packets; and (5) processing, independently at each of said processing units, the packets communicated thereto.
Claim 44
Dependent Claim
82 words
A method as in claim 38 wherein: said scheduling step (2) comprises the step of storing data identifying said first plurality of packets in a first plurality of discrete identifier stores, each of said first plurality of identifier stores associated with at least one of said processing units; and said rescheduling step (3) includes the step of transferring data from at least a first of said first plurality of identifier stores to any other one of said first plurality of identifier stores.
Claim 45
Dependent Claim
26 words
A method as in claim 39 wherein said data transferring step includes the step of selecting said other one of said first plurality of identifier stores.
Claim 46
Dependent Claim
78 words
A method as in claim 39 wherein: each of said first plurality of packets includes a function data field representing an operation to be performed and an argument data field representing at least one argument; and said processing step (5) includes the step of processing the argument represented by the argument list data field of each communicated packet in accordance with the operation represented by the function data field of said each communicated packet to produce a result.
Claim 47
Dependent Claim
135 words
A method as in claim 41 wherein: said method further includes the step of storing a second plurality of packets in said first store, each of said second plurality of packets including a function data field representing an operation to be performed and an argument list data field identifying at least a first of said first plurality of packets; and said scheduling step (2) includes the steps of: determining when one of said processing units has produced a result in accordance with said operation represented by said function data field and said argument represented by said argument list data field of said first packet, and subsequently to said determining step, scheduling the ones of said second plurality of packets including an argument list data field identifying said first packet for processing by a processing unit.
Claim 48
Dependent Claim
27 words
A method as in claim 42 further including the step of linking ones of said second plurality of packets to ones of said first plurality of packets.
Claim 49
Dependent Claim
104 words
A method as in claim 42 wherein: said first packet further includes a signal list data field identifying each of said second plurality of packets which include an argument list data field identifying said first packet; said processing step (5) further includes the step of transmitting a signal from each of said processing units to each of said second plurality of packets identified by the signal list data field of the ones of said processed first plurality of packets; and said determining step comprises the step of determining which of said second plurality of packets have received a signal transmitted by said transmitting step.
Claim 50
Dependent Claim
88 words
A method as in claim 44 wherein said processing step (5) further includes the steps of: (a) selectively generating a new one of said first plurality of packets at at least a first of said plurality of processing units; (b) identifying a portion of said first store available for storing a new packet; (c) storing said new packet generated by said generating step (a) in the portion of said first store identified by said identifying step (b); and (d) performing said scheduling step (2) for said new packet.
Claim 51
Dependent Claim
91 words
A method as in claim 45 wherein: said identifying step (b) includes the step of transferring data indentifying a portion of said first store available for storing a new packet to said first processing unit from a predetermined one of a second plurality of discrete stores each containing data identifying portions of said first store available for storing new packets; and said method further includes the step (x) of transferring data from a first of said second plurality of identifier stores to any other one of said second plurality of stores.
Claim 52
Dependent Claim
25 words
A method as in claim 46 wherein said transferring step (x) includes the step of selecting said other one of said second plurality of stores.
Claim 53
Dependent Claim
61 words
A method as in claim 46 wherein: the data identifying said portions of said first store available for storing a new packet includes a plurality of respective indicia of spaces in said first store each capable of storing exactly one packet; and each of the indicia specifying a space is stored in only one of said second plurality of identifier stores.
Claim 54
Dependent Claim
61 words
A method as in claim 46 wherein said processing step (5) further includes the step of storing the data identifying the location in said first store of ones of said first plurality of packets already processed and not identified by the argument list data field of any of said second plurality of packets into one of said second plurality of stores.
Claim 55
Dependent Claim
85 words
A method as in claim 38 wherein said processing step (5) includes the steps of: (a) selectively generating a new one of said first plurality of packets at at least a first of said processing units; (b) identifying a portion of said first store available for storing a new packet; (c) storing said new packet generated by said generating step (a) in the portion of said first store identified by said identifying step (b); and (d) performing said scheduling step (2) for said new packet.
Claim 56
Dependent Claim
97 words
A method as in claim 50 wherein: said available portion identifying step (b) includes the step of transferring data indentifying a portion of said first store available for storing new packets to said first processing unit from a predetermined one of a second plurality of discrete stores, each of said second plurality of stores containing data identifying portions of said first store available for storing new packets; and said method further includes the step of transferring data from a first of said second plurality of stores to any other selected one of said second plurality of stores.
Claim 57
Dependent Claim
43 words
A method as in claim 38 wherein: at least one of said processing units is dedicated to performing a predetermined function; and said scheduling step (2) includes the step of scheduling selected ones of said packets for processing by said dedicated processing unit.
References Cited (Backward Citations)
US3648252A
Cited
US4130885A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1989-05-26 | 1989-11-25 | 1990-05-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1993-05-26 | 1993-11-25 | 1994-05-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1997-05-26 | 1997-11-25 | 1998-05-27 | $7700.00 | Window Closed / Lapsed |