Electrical computers and digital processing systems: processing – Processing architecture – Long instruction word
Reexamination Certificate
1998-12-04
2001-01-09
Treat, William M. (Department: 2783)
Electrical computers and digital processing systems: processing
Processing architecture
Long instruction word
C712S010000, C712S020000, C712S021000, C712S022000, C712S200000, C712S203000, C712S208000, C712S210000, C712S212000, C712S215000, C712S226000
Reexamination Certificate
active
06173389
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to improvements in parallel processing, and more particularly to advantageous techniques for providing dynamic very long instruction word (VLIW) sub-instruction selection for execution time parallelism in an indirect VLIW processor.
BACKGROUND OF THE INVENTION
In a VLIW processor, a typical problem is that it is difficult to make effective use of the full capabilities of the fixed length VLIWs available in the hardware. In previous designs, this design problem led to a very porous VLIW memory containing many No Operation (NOP) instructions within the VLIWs. Some machines have attempted to encode the NOPs to more fully utilize the VLIW memory space. One motivation of such attempts was to make better use of the costly VLIW memory included in these earlier processors. The encoded NOPs were typically assigned to each specific VLIW with no reuse of the VLIW possible in different areas of the program.
There are other needs to be met by a VLIW parallel data processor. For example, it is desirable to pipeline operations in order to achieve a steady state flow of data for maximum throughput. Consider the case of matrix multiplication using a VLIW architecture with four short instruction words (SIWs) per VLIW. In the example of
FIG. 1
, a 4-element vector
2
and a 4×4 matrix
4
are multiplied. Given a processor with operands stored in a register file and VLIW execution units that operate on register file source data operands and deliver result data to the register file, it can be reasonably assumed that the vector elements are stored in data registers R
20
=a
0
, R
21
=a
1
, R
22
=a
2
, and R
23
=a
3
, and the 4×4 matrix
4
is stored in a processor accessible memory.
FIG. 2
illustrates how the entire operation is handled in a typical prior art approach. Each row in table
10
represents a unique short instruction word (SIW) or VLIW instruction with the program flow beginning at the top of the table and proceeding time-wise down the page. The Load operation is an indexed load that incrementally addresses memory to fetch the data element listed and load it into the specified register R
0
or R
1
. The Add and Mpy instructions provide the function Rtarget=Rx Operation Ry, where Rtarget is the operand register closest to the function name and the source operands Rx and Ry arc the second and third register specified. Each unique VLIW memory address is identified with a number in the first column. The table
10
of
FIG. 2
shows that a minimum of seven VLIWs, each stored in a unique VLIW memory address, and three unique SIWs, are required to achieve the desired results in the prior art. It is important to note that of the seven VLIWs, three VLIWs, namely numbers
1
,
2
, and
7
, use only two SIWs per VLIW, the other four use three SIWs per VLIW. When a four instruction slot VLIW contains only two SIWs, the other two slots contain NOP instructions. When the four instruction slot VLIW contains three SIWs, the other slot contains a single NOP. With a five instruction slot VLIW as will be described in greater detail below, even poorer usage of the VLIW memory results using prior art techniques. In the vector matrix example, a five slot VLIW will use 7*5=35 VLIW memory locations with 17 NOPs assuming the fifth slot is not used for this matrix multiplication example. The prior art approach results in a very porous VLIW memory with numerous NOP instructions.
It is desirable to reduce the number of unique VLIW memory addresses to accomplish the same task since this makes more efficient use of the available hardware. It is also desirable to reduce duplicate instructions in the VLIW memory storage. This is an important consideration that allows a smaller VLIW memory to be designed into a processor thereby minimizing its cost. Further, if the same VLIW memory address could be shared by multiple sections of code and even multiple programs then the latency cost of loading the VLIW memories can be minimized, as compared to prior art approaches, and amortized over the multiple programs thereby improving overall performance. In addition, it is desirable to extend this concept into multiple Processing Elements (PEs) and to a controller Sequence Processor (SP) of a Single Instruction Multiple Data stream (SIMD) machine
SUMMARY OF THE PRESENT INVENTION
The present invention is preferably used in conjunction with the ManArray architecture various aspects of which are described in greater detail in U.S. patent application Ser. No. 08/885,310 filed Jun. 30, 1997, U.S. patent application Ser. No. 08/949,122 filed Oct. 10, 1997, U.S. patent application Ser. No. 09/169,255 filed Oct. 9, 1998, U.S. patent application Ser. No. 09/169,256 filed Oct. 9, 1998, U.S. patent application Ser. No. 09/169,072 filed Oct. 9, 1998, and U.S. patent application Ser. No. 09/187,539 filed Nov. 6, 1998, Provisional Application Ser. No. 60/068,021 entitled “Methods and Apparatus for Scalable Instruction Set Architecture” filed Dec. 18, 1997, Provisional Application Ser. No. 60/071,248 entitled “Methods and Apparatus to Dynamically Expand the Instruction Pipeline of a Very Long Instruction Word Processor” filed Jan. 12, 1998, Provisional Application Ser. No. 60/072,915 entitled “Methods and Apparatus to Support Conditional Execution in a VLIW-Based Array Processor with Subword Execution” filed Jan. 28, 1988, Provisional Application Ser. No. 60/077,766 entitled “Register File Indexing Methods and Apparatus for Providing Indirect Control of Register in a VLIW Processor” filed Mar. 12, 1998, Provisional Application Ser. No. 60/092,130 entitled “Methods and Apparatus for Instruction Addressing in Indirect VLIW Processors” filed Jul. 9, 1998, Provisional Application Ser. No. 60/103,712 entitled “Efficient Complex Multiplication and Fast Fourier Transform (FFT) Implementation on the ManArray” filed Oct. 9, 1998, and Provisional Application Ser. No. 60/106,867 entitled “Methods and Apparatus for Improved Motion Estimation for Video Encoding” filed Nov. 3, 1998, respectively, and incorporated herein in their entirety.
The present invention addresses the need to provide a compressed VLIW memory and the ability to reuse instruction components of VLIWs in a highly advantageous way. In one aspect, the present invention comprises a SIW fetch controller for reading instructions from the SIW memory (SIM), a VLIW memory (VIM) to store composed VLIWs at specified addresses, a VLIW controller for indirectly loading and reading instructions from the VIM, and instruction decode and execution units. VLIWs in the present invention are composed by loading and concatenating multiple SIWs in a VIM address prior to their execution.
In a SIMD machine, the SIW fetch controller resides in the SIMD array controller SP which dispatches the fetched 32-bit instructions to the array PEs. The SP and the PEs include a VIM, a VIM controller, and instruction and decode execution units. The concepts discussed in this disclosure apply to both the indirect VLIW (iVLIW) apparatus and mechanism located in the SP controller and each PE in a multiple PE array SIMD machine.
After at least one VLIW is loaded into VIM, it may be selected by an execute-VLIW (XV) instruction. There are two types of XV instructions described in this invention. The first one XV
1
provides sub-VLIW SIW selection across the slots at the same VIM address for execution time parallelism. The second XV
2
provides sub-VLIW SIW selection with independently selectable SIWs from the available SIWs within each of the slots VIM sections for execution time parallelism. The XV
1
instruction is described first with an example demonstrating the advantages of this approach. The XV
2
instruction description follows with an example demonstrating its inherent advantages.
The XV
1
instruction causes the stored VLIW to be read out indirectly based upon address information that is computed from a VIM base address register and an immediate Offset value that is present in the XV
1
instruction. The X
Barry Edwin F.
Pechanek Gerald G.
Revilla Juan Guillermo
Billions of Operations Per Second, Inc.
Law Offices of Peter H. Priest, PLLC
Treat William M.
LandOfFree
Methods and apparatus for dynamic very long instruction word... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for dynamic very long instruction word..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for dynamic very long instruction word... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2509372