Patent US4827403A successfully refreshed from Google Patents.
US4827403A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Virtual processor techniques in a SIMD multiprocessor array
Assignee: Thinking Machines Corp
•
Filing: 1986-11-24
•
Granted: 1989-05-02
•
Expires: 2006-11-24
Abstract
Abstract A virtual processor mechanism and specific techniques and instructions for utilizing such virtual processor mechanism within an SIMD computer having numerous processors, and each physical processor having dedicated memory associated therewith. Each physical processor is used to simulate multiple "virtual" processors, with each physical processor simulating the same number of virtual processors. The memory of each physical processor is divided into n regions of equal size, each such region being allocated to one virtual processor, where n is the number of virtual processors simulated by each physical processor. Whenever an instruction is processed, each physical processor is time-sliced among the virtual memory regions, performing the operation first as one virtual processor, then another, until the operation has been performed for all virtual processors. Physical processors are switched among the virtual processors in a completely regular, predictable, deterministic fashion. The virtual processor mechanism switches among virtual processors within instructions, so that at the completion of each instruction, it has been executed on behalf of all virtual processors. A number of instructions are shown for execution using these virtual processor techniques.
Inventors
- 👤 Guy L. Steele, Jr.
- 👤 W. Daniel Hillis
- 👤 Guy Blelloch
- 👤 Michael Drumbeller
- 👤 Brewster Kahle
- 👤 Clifford Lasser
- 👤 Abhiram Ranade
- 👤 James Salem
- 👤 Karl Sims
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 03:11
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/76; G06F15/80; G06F15/8007
Claims Analysis
Total Claims: 5
Claim 1
Independent Claim
294 words
In a single-instruction multiple data (SIMD) parallel processor comprising a controller and an array of physical processors controlled in parallel by instructions supplied by said controller, each processor comprising an input, an output, a processing element and an associated memory element coupled to said processing element for storing information from and supplying information to the processing element and comprising at least one memory location, the processing element operating on data provided by its input and said associated memory element, in accordance with instructions provided by said controller, to produce data at its output, a method of simulating the presence of a larger number of processors in the array than the number of said physical processors, thereby to provide a corresponding number of so-called "virtual processors" usable for executing user programs, and of utilizing said virtual processors, comprising the steps of: (a) before executing a user program, subdividing the memory elements asociated with each of a plurality of physical processing elements to form a plurality of m sub-memories associated with each processing element each of v bits in length, where m is a variable number provided before a user program is executed and m may range from 1 to at least tens of thousands; (b) providing an instruction from the controller to a set of the physical processors to cause the processing elements thereof to process data stored at a corresponding location in a first sub-memory associated with each such processing element; and (c) at a subsequent time within a time allowed for the execution of said instruction, providing said instruction from the controller to such set of physical processors to cause the processing elements thereof each to process data stored at a corresponding location in a second sub-memory associated with each such processing element.
Claim 2
Dependent Claim
294 words
In a single-instruction multiple data (SIMD) parallel processor comprising a controller and an array of physical processors controlled in parallel by instructions supplied by said controller, each processor comprising an input, an output, a processing element and an associated memory element coupled to said processing element for storing information from and supplying information to the processing element and comprising at least one memory location, the processing element operating on data provided by its input and said associated memory element, in accordance with instructions provided by said controller, to produce data at its output, a method of simulating the presence of a larger number of processors in the array than the number of said physical processors, thereby to provide a corresponding number of so-called "virtual processors" usable for executing user programs, and of utilizing said virtual processors, comprising the steps of: (a) before executing a user program, subdividing the memory elements asociated with each of a plurality of physical processing elements to form a plurality of m sub-memories associated with each processing element each of v bits in length, where m is a variable number provided before a user program is executed and m may range from 1 to at least tens of thousands; (b) providing an instruction from the controller to a set of the physical processors to cause the processing elements thereof to process data stored at a corresponding location in a first sub-memory associated with each such processing element; and (c) at a subsequent time within a time allowed for the execution of said instruction, providing said instruction from the controller to such set of physical processors to cause the processing elements thereof each to process data stored at a corresponding location in a second sub-memory associated with each such processing element.
Claim 3
Dependent Claim
120 words
The method of claim 1 wherein the instruction is an ADD instruction intended to cause the virtual processor to add together a multiplicity of numbers, and wherein a set of virtual processors having associated sub-memory in the same relative position within each memory element is termed a "VP-bank," such method comprising the additional step of: (d) for each VP-bank, (i) loading virtual carry, overflow and context flags for VP-bank k into respective hardware flag bits, (ii) conditionally adding the field at location kv+b into the field at kv+a, where a and b are operand addresses, (iii) setting hardware carry and overflow flag bits as appropriate, and (iv) storing hardware carry and overflow flags back into virtual flags for VP-bank k.
Claim 4
Dependent Claim
60 words
The method of claim 1 or claim 2 further characterized by the additional step of: (e) providing for each virtual processor a number of flag bits, f, first and second ones of said flag bits functioning as condition code bits, recording the results of operations, and a third flag bit controlling whether the results of conditional operations will be stored.
Claim 5
Dependent Claim
12 words
The method of claim 1 wherein the physical processors are functionally identical.
References Cited (Backward Citations)
US3573852A
Cited
US4101960A
Cited
US4380046A
Cited
US4481580A
Cited
US4435758A
Cited
US4591981A
Cited
US4523273A
Cited
US4621339A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-05-01 | 1992-10-31 | 1993-05-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-05-01 | 1996-10-31 | 1997-05-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-05-01 | 2000-10-31 | 2001-05-02 | $7700.00 | Window Closed / Lapsed |