Patent US5404469A successfully refreshed from Google Patents.
US5404469A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multi-threaded microprocessor architecture utilizing static interleaving
Assignee: Industrial Technology Research Institute
•
Filing: 1992-02-25
•
Granted: 1995-04-04
•
Expires: 2012-02-25
Abstract
Abstract A static interleaving technique solves the problem of resource contention in a very long instruction word multi-threaded microprocessor architecture. In the static interleaving technique, each function unit in the processor is allocated for the execution of an instruction from a particular thread in a fixed predetermined time slot in a repeating pattern of predetermined time slots. The fixed predetermined pattern of time slots represents the resource constraints imposed on the hardware to resolve the contention for computing resources among the instruction threads. The strategy of resource allocation is exposed to a parallel compiler which organizes a sequence of instructions into the horizontal instruction words which form each thread so as to maintain the data dependencies among the instructions and to take into account the fixed predetermined allocation of hardware resources.
Inventors
- 👤 Jin-Chin Chung
- 👤 Chuan-Lin Wu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 18:00
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3836; G06F9/3851; G06F9/3853
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
174 words
A microprocessor capable of concurrently executing a plurality of instruction threads comprising: a processor comprising a plurality of function units, a means for storing horizontal instruction words forming a plurality of instruction threads, wherein each of said function units can be shared among said plurality of threads and each horizontal instruction word contains one or more machine instructions to be executed by particular ones of said function units, means for fetching from said storing means horizontal instruction words belonging to different ones of said threads at predetermined times and in a predetermined order, and means for allocating each of said function units for the execution of a machine instruction from a particular instruction thread in a fixed predetermined time slot in a fixed predetermined repeating pattern of time slots, wherein said allocation means comprises queues for providing a fixed predetermined delay for each machine instruction in each of said horizontal instruction words in said instruction threads so that each machine instruction is applied to the appropriate function unit in the appropriate allocated time slot.
Claim 2
Dependent Claim
174 words
A microprocessor capable of concurrently executing a plurality of instruction threads comprising: a processor comprising a plurality of function units, a means for storing horizontal instruction words forming a plurality of instruction threads, wherein each of said function units can be shared among said plurality of threads and each horizontal instruction word contains one or more machine instructions to be executed by particular ones of said function units, means for fetching from said storing means horizontal instruction words belonging to different ones of said threads at predetermined times and in a predetermined order, and means for allocating each of said function units for the execution of a machine instruction from a particular instruction thread in a fixed predetermined time slot in a fixed predetermined repeating pattern of time slots, wherein said allocation means comprises queues for providing a fixed predetermined delay for each machine instruction in each of said horizontal instruction words in said instruction threads so that each machine instruction is applied to the appropriate function unit in the appropriate allocated time slot.
Claim 3
Dependent Claim
46 words
The microprocessor of claim 1 wherein specific time slots in said pattern of time slots are allocated to specific function units for the execution of machine instructions from specific ones of said threads to minimize the latency of read after write dependencies in said machine instructions.
Claim 4
Dependent Claim
21 words
The microprocessor of claim 1 wherein said fetching means fetches horizontal instruction words from said storing means in a round-robin order.
Claim 5
Dependent Claim
25 words
The microprocessor of claim 1, wherein said storing means comprises a plurality of individual caches, each individual cache associated with one of said instruction threads.
Claim 6
Dependent Claim
75 words
The microprocessor of claim 1 wherein said horizontal instruction words of each thread are compiled by a compiler which reorganizes a sequence of machine instructions into a sequence of patterns of instructions comprising a plurality of horizontal instruction words, each machine instruction having a location in a pattern depending on its data dependencies with other machine instructions and the particular time slots allocated to particular function units for the execution of instructions from particular threads.
Claim 7
Dependent Claim
32 words
The microprocessor of claim 1, wherein said allocating means comprises an allocation vector and a compiler and wherein said compiler schedules said instructions into horizontal instruction words according to said allocation vector.
Claim 8
Dependent Claim
23 words
The microprocessor of claim 6, wherein said compiler compacts said scheduled horizontal instruction words thereby reducing bus bandwidth required by said fetching means.
Claim 9
Independent Claim
238 words
A method for compiling and executing one instruction thread from a plurality of instruction threads in a multi-threaded processor system, said processor system comprising a processor including a plurality of function units comprising, allocating said function units in accordance with an allocation vector for the execution of instructions from specific ones of said threads in specific fixed predetermined time slots in a fixed predetermined repeating pattern of time slots, utilizing queues to provide a fixed predetermined delay for each instruction so that each instruction is applied to the appropriate function unit in the appropriate predetermined time slot, utilizing a sequential compiler to compile a source program into a sequence of machine instructions which can be executed by particular function units in said processor system, utilizing a parallel compiler to reorganize said sequence of machine instructions into a sequence of patterns of instructions, each instruction having a location in a pattern of instructions depending on its data dependency with a previous instruction in said sequence of instructions and depending on said allocation vector which defines the time slots in which the appropriate function unit will be available to execute the instruction, utilizing said parallel compiler to compact the instructions of each pattern of instructions into a horizontal instruction word to form said one instruction thread, storing the instructions of said one instruction thread in a cache, and executing said instructions of said one instruction thread using said function units.
Claim 10
Independent Claim
238 words
A method for compiling and executing one instruction thread from a plurality of instruction threads in a multi-threaded processor system, said processor system comprising a processor including a plurality of function units comprising, allocating said function units in accordance with an allocation vector for the execution of instructions from specific ones of said threads in specific fixed predetermined time slots in a fixed predetermined repeating pattern of time slots, utilizing queues to provide a fixed predetermined delay for each instruction so that each instruction is applied to the appropriate function unit in the appropriate predetermined time slot, utilizing a sequential compiler to compile a source program into a sequence of machine instructions which can be executed by particular function units in said processor system, utilizing a parallel compiler to reorganize said sequence of machine instructions into a sequence of patterns of instructions, each instruction having a location in a pattern of instructions depending on its data dependency with a previous instruction in said sequence of instructions and depending on said allocation vector which defines the time slots in which the appropriate function unit will be available to execute the instruction, utilizing said parallel compiler to compact the instructions of each pattern of instructions into a horizontal instruction word to form said one instruction thread, storing the instructions of said one instruction thread in a cache, and executing said instructions of said one instruction thread using said function units.
Claim 11
Independent Claim
159 words
A method for concurrently executing a plurality of instruction threads in a multi-threaded processor including a plurality of function units and a cache system for storing horizontal instruction words comprising each of said threads, each horizontal instruction word containing one or more instructions to be executed by particular ones of said function units, said method comprising the steps of fetching from said cache system horizontal instruction words belonging to different ones of said threads at predetermined times and in a predetermined order, allocating each of said function units for the execution of an instruction from a particular thread in a fioxed predetermined time slot in a fixed predetermined repeating pattern of time slots, utilizing queues to provide a fixed predetermined delay for each instruction so that each instruction is applied to the appropriate function unit in the appropriate predetermined time slot, and executing said instruction in said horizontal instruction words by said function units in said allocated time slots.
Claim 12
Independent Claim
159 words
A method for concurrently executing a plurality of instruction threads in a multi-threaded processor including a plurality of function units and a cache system for storing horizontal instruction words comprising each of said threads, each horizontal instruction word containing one or more instructions to be executed by particular ones of said function units, said method comprising the steps of fetching from said cache system horizontal instruction words belonging to different ones of said threads at predetermined times and in a predetermined order, allocating each of said function units for the execution of an instruction from a particular thread in a fioxed predetermined time slot in a fixed predetermined repeating pattern of time slots, utilizing queues to provide a fixed predetermined delay for each instruction so that each instruction is applied to the appropriate function unit in the appropriate predetermined time slot, and executing said instruction in said horizontal instruction words by said function units in said allocated time slots.
Claim 13
Dependent Claim
133 words
The method of claim 9 wherein each of said threads is compiled by the steps of: utilizing a sequential compiler to compile a source program into a sequence of machine instructions which can be executed by particular function units in said processor, utilizing a parallel compiler to reorganize said sequence of machine instructions into a sequence of patterns of instructions, each instruction having a location in a pattern of instructions depending on its data dependency with a previous instruction in said sequence of instructions and depending on an allocation vector which defines the time slots in which the appropriate function unit will be available to execute the instruction, and utilizing said parallel compiler to compact the instructions of each pattern of instructions into a horizontal instruction word to form said one instruction thread.
Claim 14
Dependent Claim
146 words
A microprocessor for executing a plurality of instruction threads comprising a plurality of function units, a plurality of instruction caches, each for storing horizontal instruction words of one thread, a plurality of instruction fetch units for fetching horizontal instruction words from corresponding ones of said caches, and an allocator for allocating each of said function units for the execution of a machine instruction from a particular instruction thread in a fixed predetermined time slot in a repeating pattern of time slots in accordance with an allocation vector which minimizes read after write latencies in machine instructions in said horizontal instruction words, wherein said allocation means comprises queues for providing a fixed predetermined delay for each machine instruction in each of said horizontal instruction words in said instruction threads so that each machine instruction is applied to the appropriate function unit in the appropriate allocated time slot.
Claim 15
Dependent Claim
146 words
A microprocessor for executing a plurality of instruction threads comprising a plurality of function units, a plurality of instruction caches, each for storing horizontal instruction words of one thread, a plurality of instruction fetch units for fetching horizontal instruction words from corresponding ones of said caches, and an allocator for allocating each of said function units for the execution of a machine instruction from a particular instruction thread in a fixed predetermined time slot in a repeating pattern of time slots in accordance with an allocation vector which minimizes read after write latencies in machine instructions in said horizontal instruction words, wherein said allocation means comprises queues for providing a fixed predetermined delay for each machine instruction in each of said horizontal instruction words in said instruction threads so that each machine instruction is applied to the appropriate function unit in the appropriate allocated time slot.
References Cited (Backward Citations)
US5226125A
Cited
EP0433864A2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-04-03 | 1998-10-03 | 1999-04-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-04-03 | 2002-10-03 | 2003-04-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-04-03 | 2006-10-03 | 2007-04-04 | $7700.00 | Window Closed / Lapsed |