Patent US4825360A successfully refreshed from Google Patents.
US4825360A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for parallel processing with mostly functional languages
Assignee: Symbolics Inc
•
Filing: 1986-07-30
•
Granted: 1989-04-25
•
Expires: 2006-07-30
Abstract
Abstract A parallel processing system is receptive of a program and has at least two processors connected in parallel to a shared main memory. Each processor executes instructions of the program which includes side-effecting instructions which modify the contents of a location in main memory and functional instructions which reference locations in main memory. The program is compiled into a series of independent instruction blocks each of which includes predominantly functional instructions and terminates in a side-effecting instruction and the processors execute the blocks in parallel.
Inventors
- 👤 Thomas F. Knight, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 14:30
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0806; G06F12/0815; G06F12/0831; G06F12/0833; G06F8/00; G06F8/40; G06F8/41; G06F8/45
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
170 words
In a parallel processing system receptive of a program and having at least two processors connected in parallel to a shared main memory, wherein each processor executes instructions of a program which includes side effecting instructions which modify the contents of a location in main memory and functional instructions which reference locations in main memory or operate only on internal processor registers, the improvement comprising: means for compiling a program into a series of independent instruction blocks including predominantly functional instructions and terminating in a side effecting instruction; means for applying compiled blocks to the at least two processors for executing the blocks in parallel; and means for validating data to be stored in a location of main memory from each parallel processed block relative to locations referenced during execution by the other of the at least two processors, wherein the validating means comprises, for each processor, means for maintaining a dependency list of all locations in main memory which have been referenced during the execution of a block therein.
Claim 2
Dependent Claim
170 words
In a parallel processing system receptive of a program and having at least two processors connected in parallel to a shared main memory, wherein each processor executes instructions of a program which includes side effecting instructions which modify the contents of a location in main memory and functional instructions which reference locations in main memory or operate only on internal processor registers, the improvement comprising: means for compiling a program into a series of independent instruction blocks including predominantly functional instructions and terminating in a side effecting instruction; means for applying compiled blocks to the at least two processors for executing the blocks in parallel; and means for validating data to be stored in a location of main memory from each parallel processed block relative to locations referenced during execution by the other of the at least two processors, wherein the validating means comprises, for each processor, means for maintaining a dependency list of all locations in main memory which have been referenced during the execution of a block therein.
Claim 3
Dependent Claim
115 words
The system according to claim 1, wherein the validating means comprises first cache means associated with each processor for temporarily storing the location and contents of each location in main memory to be side effected by the execution of the block therein and means for confirming each block in the order of the blocks as specified in the program wherein the validity of the contents of the first cache means are approved comprising means for comparing the dependency list of the block to be confirmed with the locations side effected by already confirmed blocks to detect a match and means for aborting the execution of the block to be confirmed if there is a match.
Claim 4
Dependent Claim
29 words
The system according to claim 2, wherein the confirming means comprises a block counter and means for incrementing the block counter to indicate the next block to be confirmed.
Claim 5
Dependent Claim
82 words
The system according to claim 2, wherein the means for maintaining a dependency list comprises second cache means associated with each processor for temporarily storing each location and contents of main memory referenced by a block being executed in the processor and wherein the confirming means comprises means for updating the contents of the second cache means upon the aborting of a block and for effecting the reexecution of an aborted block with the side effected location from an already confirmed block.
Claim 6
Dependent Claim
21 words
The system according to claim 4, wherein the first and second cache means each comprises a fully associative content addressable memory.
Claim 7
Dependent Claim
54 words
The system according to claim 4, wherein the second cache means comprises an addressable random access memory for storing dependency information of main memory locations and hash table means receptive of said addresses of the main memory locations for hashing them into a reduced member of address bits for addressing the random access memory.
Claim 8
Dependent Claim
30 words
The system according to claim 1, wherein the means for maintaining a dependency list includes means for selectively referencing locations in main memory without adding same to the dependency list.
Claim 9
Dependent Claim
138 words
In a method for executing a program in at least two processors connected in parallel to a shared main memory, wherein the program includes side effecting instructions which modify the contents of a location in main memory and functional instructions which reference locations in main memory, the improvement comprising: compiling the program into a series of independent instruction blocks including predominantly functional instructions and terminating in a side effecting instruction, applying compiled blocks to the processors, executing the blocks in parallel and validating data to be stored in a location of main memory from each parallel processed block relative to locations referenced during execution by the other of the at least two processors by maintaining a dependency list for each processor of all locations in main memory which have been referenced during the execution of a block therein.
Claim 10
Dependent Claim
138 words
In a method for executing a program in at least two processors connected in parallel to a shared main memory, wherein the program includes side effecting instructions which modify the contents of a location in main memory and functional instructions which reference locations in main memory, the improvement comprising: compiling the program into a series of independent instruction blocks including predominantly functional instructions and terminating in a side effecting instruction, applying compiled blocks to the processors, executing the blocks in parallel and validating data to be stored in a location of main memory from each parallel processed block relative to locations referenced during execution by the other of the at least two processors by maintaining a dependency list for each processor of all locations in main memory which have been referenced during the execution of a block therein.
Claim 11
Dependent Claim
90 words
The method according to claim 8, wherein the step of validating further comprises for each processor temporarily storing the location and contents of each location in main memory to be side effected by the execution of the block therein and confirming each block in the order of the blocks as specified in the program to approve the validity of the stored contents by comparing the dependency list of the block to be confirmed with the locations which have been side effected by the already confirmed blocks to detect a match.
Claim 12
Dependent Claim
24 words
The method according to claim 9, wherein the step of validating further comprises aborting the execution of a block when there is a match.
Claim 13
Dependent Claim
56 words
The method according to claim 10, wherein the step of maintaining a dependency list comprises temporarily storing for each processor each location and contents of main memory referenced by the block being executed therein and wherein the step of validating further comprises reexecuting an aborted block with the side effected location from an already confirmed block.
Claim 14
Dependent Claim
44 words
The method according to claim 11, wherein the step of temporarily storing the referenced locations comprises hashing each location address into a hashed address having a reduced number of address bits and storing dependency information at the hashed address in a random access memory.
Claim 15
Dependent Claim
24 words
The method according to claim 8, where in the step of maintaining a dependency list includes selectively omitting referenced locations from the dependency list.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-04-24 | 1992-10-24 | 1993-04-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-04-24 | 1996-10-24 | 1997-04-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-04-24 | 2000-10-24 | 2001-04-25 | $7700.00 | Window Closed / Lapsed |