US5442797A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Latency tolerant risc-based multiple processor with event driven locality managers resulting from variable tagging
Assignee: University of Iowa Research Foundation
•
Filing: 1991-12-04
•
Granted: 1995-08-15
•
Expires: 2011-12-04
Abstract
Abstract A method and an apparatus for reconciling communication and locality by enabling a user/programmer to write programs in an extended procedural language which explicitly manipulate locality. The multiprocessor includes a plurality of processing elements connected to each other each processing element having a unique address and including a central processing unit for executing local CPU code and reading and writing local data and a locality manager for controlling data movement between processing elements which are cooperating on a single task by executing local locality manager code which indicates when shared data can be released and when non-local data is requested.
Inventors
- 👤 Thomas L. Casavant
- 👤 Samuel A. Fineberg
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 22:50
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3877; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17356; G06F15/17368; G06F15/17381; G06F15/76; G06F15/80; G06F15/8007
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
203 words
A parallel multiprocessor for executing code resulting from a program which has been compiled, said code including locality manager code and cpu code, comprising: a plurality of processing elements connected to each other and arranged in an interconnection structure, each processing element having a unique address within said interconnection structure, each processing element comprising: central processing means for processing data by executing local cpu code which is a part of said cpu code that is local to said central processing means; and locality manager processor for controlling data movement between processing elements which are cooperating on a single task by executing, upon the occurrence of specified events resulting from execution of said local cpu code, local locality manager code which is a part of said locality manager code that is local to said locality manager processor, said local locality manager code indicating when data shared among two or more of said processing elements can be released for movement between processing elements and when non-local data from another processing element is requested, wherein said central processing means and said locality manager processor are separately programmable and operate independently of each other as specified in said local locality manager code and said local cpu code.
Claim 2
Dependent Claim
203 words
A parallel multiprocessor for executing code resulting from a program which has been compiled, said code including locality manager code and cpu code, comprising: a plurality of processing elements connected to each other and arranged in an interconnection structure, each processing element having a unique address within said interconnection structure, each processing element comprising: central processing means for processing data by executing local cpu code which is a part of said cpu code that is local to said central processing means; and locality manager processor for controlling data movement between processing elements which are cooperating on a single task by executing, upon the occurrence of specified events resulting from execution of said local cpu code, local locality manager code which is a part of said locality manager code that is local to said locality manager processor, said local locality manager code indicating when data shared among two or more of said processing elements can be released for movement between processing elements and when non-local data from another processing element is requested, wherein said central processing means and said locality manager processor are separately programmable and operate independently of each other as specified in said local locality manager code and said local cpu code.
Claim 3
Dependent Claim
33 words
The parallel multiprocessor claimed in claim 1, wherein each processing element further comprises a processing element main memory connected to said central processing means for storing local data and the local cpu code.
Claim 4
Dependent Claim
52 words
The parallel multiprocessor claimed in claim 2, wherein each processing element further comprises cache memory in said central processing means for storing the local data; and main memory updating means for updating local data stored in said processing element main memory in accordance with the local data stored in said cache memory.
Claim 5
Dependent Claim
20 words
The parallel multiprocessor claimed in claim 3, further comprising a locality manager memory for storing the local locality manager code.
Claim 6
Dependent Claim
44 words
The parallel multiprocessor claimed in claim 3, further comprising routing logic means having direct access to said locality manager memory and to said processing element main memory and connected to said locality manager processor for routing data in accordance with said locality manager processor.
Claim 7
Dependent Claim
18 words
The parallel multiprocessor claimed in claim 1, wherein said central processing means is a reduced instruction set computer.
Claim 8
Dependent Claim
160 words
A method of controlling data and control flow in the parallel multiprocessor of claim 1 as specified in said program, comprising the steps of: declaring a variable to be a taggable variable in the program; tagging the taggable variable in the program yielding a tagged variable to indicate to the processing elements in the multiprocessor that data associated with the tagged variable at one processing element may be moved to or from one or more of said plurality of processing elements; requesting data as specified in the program associated with said tagged variable by one or more of said plurality of processing elements other than said one processing element whenever the data is required at said one or more processing elements; and releasing said data to permit by specifying in the program a predetermined number of said requesting steps from said one or more processing elements received by said one processing element to receive the data in non-local tagged variables.
Claim 9
Dependent Claim
73 words
The method claimed in claim 7 further comprising the step of controlling data movement between processing elements which are cooperating on a single task by executing local locality manager code using the locality manager processor, wherein the local locality manager code indicates when data shared among two or more processing elements can be released for movement between processing elements and when non-local data which is data local to another processing element is requested.
Claim 10
Dependent Claim
27 words
The method claimed in claim 7 further comprising the step of storing portions of said cpu code as local cpu code in respective processing element main memories.
Claim 11
Dependent Claim
25 words
The method claimed in claim 9 further comprising the step of executing said local cpu code using the central processing means in respective processing elements.
Claim 12
Dependent Claim
26 words
The method claimed in claim 7 further comprising the step of storing local locality manager code, local data and non-local data in respective locality manager memories.
Claim 13
Dependent Claim
56 words
The method claimed in claim 7 further comprising the step of specifying tasks to be performed by said locality manager processor in ordered triples each ordered triple including a variable reference, a tag and local locality manager instructions corresponding to each task, said local locality manager instructions comprising a portion of said local locality manager code.
Claim 14
Dependent Claim
185 words
A parallel multiprocessor comprising: a plurality of processing elements connected to each other in an interconnection structure, each processing element having a unique address within said structure and comprising: a processing element main memory for storing local cpu code; a central processing unit having a cache memory with an instruction portion and a data portion, for executing the local cpu code, and for reading from and writing to said processing element main memory; a locality manager memory for storing local locality manager code and data; a locality manager processor for controlling data movement between processing elements which are cooperating on a single task by executing local locality manager code which indicates when shared data can be released and when non-local data is requested; main memory updating means for updating data stored in said processing element main memory in accordance with data in said data portion of the cache memory; and routing logic means having direct access to said locality manager memory and said processing element main memory and connected to said locality manager processor for routing data as specified in said local locality manager code.
Claim 15
Dependent Claim
185 words
A parallel multiprocessor comprising: a plurality of processing elements connected to each other in an interconnection structure, each processing element having a unique address within said structure and comprising: a processing element main memory for storing local cpu code; a central processing unit having a cache memory with an instruction portion and a data portion, for executing the local cpu code, and for reading from and writing to said processing element main memory; a locality manager memory for storing local locality manager code and data; a locality manager processor for controlling data movement between processing elements which are cooperating on a single task by executing local locality manager code which indicates when shared data can be released and when non-local data is requested; main memory updating means for updating data stored in said processing element main memory in accordance with data in said data portion of the cache memory; and routing logic means having direct access to said locality manager memory and said processing element main memory and connected to said locality manager processor for routing data as specified in said local locality manager code.
Claim 16
Dependent Claim
52 words
The parallel multiprocessor claimed in claim 13, further comprising a CPU bus and a bus interface logic unit connected to said central processing unit and said CPU bus for detecting cpu events by monitoring tag bits coupled to said local locality manager code and passing memory accesses to said processing element bus.
Claim 17
Dependent Claim
44 words
The parallel multiprocessor claimed in claim 14, further comprising a cpu-lm fifo connected to said bus interface logic unit, said bus interface logic unit placing address bits and tag bits into said cpu-lm fifo whenever said bus interface logic unit detects a cpu event.
Claim 18
Dependent Claim
59 words
The parallel multiprocessor claimed in claim 15, further comprising a block logic unit connected to said bus interface logic for storing synchronization bits for data stored in said processing element main memory, the synchronization bits indicating whether data may be written over or read, said bus interface logic unit checking said block logic unit whenever a reference is taggable.
Claim 19
Dependent Claim
31 words
The parallel multiprocessor claimed in claim 14, further comprising block logic means connected to said bus interface logic unit for controlling synchronization of taggable data that has been requested or released.
Claim 20
Dependent Claim
39 words
The parallel multiprocessor claimed in claim 17, wherein said block logic means for controlling comprises means for preventing a reading of a taggable variable that has been requested until after data associated with the taggable variable has been received.
Claim 21
Dependent Claim
42 words
The parallel multiprocessor claimed in claim 17, wherein said block logic means for controlling comprises means for preventing over-writing of taggable variables that have been released until after data associated with the taggable variable has been sent a predetermined number of times.
Claim 22
Dependent Claim
40 words
The parallel multiprocessor claimed in claim 17, wherein said block logic means for controlling comprises means for preventing reading from and preventing writing to taggable variables after the data associated with the taggable variable has been requested and released, respectively.
Claim 23
Independent Claim
149 words
A method for making a parallel multiprocessor which can execute code resulting from a program which has been compiled, said code including locality manager code and cpu code, comprising the steps of: arranging a first processor to serve as a central processing unit for executing local cpu code; coupling a second processor to the first processor to serve as a locality manager unit for executing local locality manager code; coupling a routing logic unit to the second processor, whereby the first processor, the second processor and the routing logic unit comprise a processing element; repeating said arranging and both of said coupling steps yielding a plurality of processing elements; and interconnecting the plurality of processing elements by interconnecting the plurality of routing logic units, wherein the second processors control movement of data between processing elements independently of the first processors and the first and second processors are separately programmable.
Claim 24
Independent Claim
149 words
A method for making a parallel multiprocessor which can execute code resulting from a program which has been compiled, said code including locality manager code and cpu code, comprising the steps of: arranging a first processor to serve as a central processing unit for executing local cpu code; coupling a second processor to the first processor to serve as a locality manager unit for executing local locality manager code; coupling a routing logic unit to the second processor, whereby the first processor, the second processor and the routing logic unit comprise a processing element; repeating said arranging and both of said coupling steps yielding a plurality of processing elements; and interconnecting the plurality of processing elements by interconnecting the plurality of routing logic units, wherein the second processors control movement of data between processing elements independently of the first processors and the first and second processors are separately programmable.
References Cited (Backward Citations)
US4079327A
Cited
US5008815A
Cited
US4598400A
Cited
US4814973A
Cited
US4805091A
Cited
US5047917A
Cited
US4773038A
Cited
WO1988001772A1
Cited
US4791641A
Cited
US4827403A
Cited
US5050069A
Cited
US4984235A
Cited
US5201040A
Cited
US4830376A
Cited
WO1989007299A1
Cited
US4969088A
Cited
US4984237A
Cited
US5113514A
Cited
US5083265A
Cited
US5175733A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-08-14 | 1999-02-13 | 1999-08-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-08-14 | 2003-02-13 | 2003-08-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-08-14 | 2007-02-13 | 2007-08-15 | $7700.00 | Window Closed / Lapsed |