US4888679A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus using a cache and main memory for both vector processing and scalar processing by prefetching cache blocks including vector data elements
Assignee: Hewlett Packard Development Co LP
•
Filing: 1988-01-11
•
Granted: 1989-12-19
•
Expires: 2008-01-11
Abstract
Abstract A main memory and cache suitable for scalar processing are used in connection with a vector processor by issuing prefetch requests in response to the recognition of a vector load instruction. A respective prefetch request is issued for each block containing an element of the vector to be loaded from memory. In response to a prefetch request, the cache is checked for a "miss" and if the cache does not include the required block, a refill request is sent to the main memory. The main memory is configured into a plurality of banks and has a capability of processing multiple references. Therefore the different banks can be referenced simultaneously to prefetch multiple blocks of vector data. Preferably a cache bypass is provided to transmit data directly to the vector processor as the data from the main memory are being stored in the cache. In a preferred embodiment, a vector processor is added to a digital computing system including a scalar processor, a virtual address translation buffer, a main memory and a cache. The scalar processor includes a microcode interpreter which sends a vector load command to the vector processing unit and which also generates vector prefetch requests. The addresses for the data blocks to be prefetched are computed based upon the vector address, the length of the vector and the "stride" or spacing between the addresses of the elements of the vector.
Inventors
- 👤 Tryggve Fossum
- 👤 Ricky C. Hetherington
- 👤 David B. Fite, Jr.
- 👤 Dwight P. Manley
- 👤 Francis X. McKeen
- 👤 John E. Murray
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 10:14
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/76; G06F15/80; G06F15/8053; G06F15/8061; G06F15/8069; G06F12/00; G06F12/02; G06F12/0207; G06F12/08; G06F12/0802; G06F12/0844; G06F12/0855; G06F9/00; G06F9/06; G06F9/30; G06F9/34; G06F9/345; G06F9/3455; G06F9/38; G06F9/3824; G06F9/383
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
173 words
A method of operating a digital computer, said digital computer including a vector processor, a main memory, and a cache; said main memory including means for storing data elements at respective addresses; said cache including cache memory means for storing selected predefined blocks of said data elements, means for receiving requests to reference a specified block of said data, means for checking whether data for the specified block is stored in the cache memory means, and means operative when data for the specified block is not so stored for reading the specified block of data from said main memory and storing the block of data in the cache memory means; said method comprising the steps of: receiving an instruction to obtain a specified vector of said data elements and load said vector into said vector processor, determining the blocks of data which include at least one data element of said vector, and transmitting requests to reference the blocks of data which are determined to include at least one data element of said vector.
Claim 2
Independent Claim
173 words
A method of operating a digital computer, said digital computer including a vector processor, a main memory, and a cache; said main memory including means for storing data elements at respective addresses; said cache including cache memory means for storing selected predefined blocks of said data elements, means for receiving requests to reference a specified block of said data, means for checking whether data for the specified block is stored in the cache memory means, and means operative when data for the specified block is not so stored for reading the specified block of data from said main memory and storing the block of data in the cache memory means; said method comprising the steps of: receiving an instruction to obtain a specified vector of said data elements and load said vector into said vector processor, determining the blocks of data which include at least one data element of said vector, and transmitting requests to reference the blocks of data which are determined to include at least one data element of said vector.
Claim 3
Dependent Claim
127 words
The method as claimed in claim 1, wherein said means for receiving requests to reference a specified block of said data includes means for receiving a specified memory address, means for determining the block including the specified address, and means for obtaining the data element associated with the specified address from said memory means when the block including the specified address is stored in said memory means and otherwise obtaining the data element from the main memory, and wherein said method further comprises the steps of determining the memory address associated with each of the elements of said vector, transmitting the memory addresses so determined to the cache, and transmitting the data elements associated with the specified addresses from the means for obtaining to said vector processor.
Claim 4
Dependent Claim
19 words
The method as claimed in claim 1, wherein said step of determining is performed by executing a microcode procedure.
Claim 5
Dependent Claim
58 words
The method as claimed in claim 1, wherein said step of determining the blocks of data which include at least one data element of said vector includes the steps of sequentially computing the addresses associated with successive data elements of the vector, and testing whether each computed address is within a different block from the previously computed address.
Claim 6
Dependent Claim
64 words
The method as claimed in claim 4, wherein said addresses associated with successive data elements differ by a predetermined stride, and said step of sequentially computing the addresses associated with successive data elements of the vector computes the address of every Mth data element of the vector, where M is an integer for which different values are selected as a function of said stride.
Claim 7
Dependent Claim
37 words
The method as claimed in claim 5, wherein said blocks each have the same predetermined memory size, and said step of sequentially computing includes the step of comparing said stride to said memory size of said blocks.
Claim 8
Dependent Claim
33 words
The method as claimed in claim 5, further comprising the step of changing a count by said integer M each time said address of every Mth data element of the vector is computed.
Claim 9
Dependent Claim
43 words
The method as claimed in claim 7, further comprising the step of adjusting the address computed for the last Mth data element of the vector by a value which is selected as a function of a remainder of said count and said stride.
Claim 10
Independent Claim
157 words
A method of operating a digital computer, said digital computer including a vector processor, a main memory having multiple memory banks, and at least one data buffer interposed in a data path from said main memory to said vector processor, said memory storing predefined blocks of data elements at respective addresses; said method comprising the steps of: receiving an instruction to obtain a specified vector of data elements and load said vector into said vector processor, determining the blocks of data which include at least one data element of said vector, transmitting requests to reference the blocks of data which are determined to include at least one data element of said vector, and in response to those requests fetching the blocks from memory when the blocks are not stored in said data buffer, and obtaining from the referenced blocks said data elements of said vector and transmitting said data elements of said vector to said vector processor.
Claim 11
Independent Claim
157 words
A method of operating a digital computer, said digital computer including a vector processor, a main memory having multiple memory banks, and at least one data buffer interposed in a data path from said main memory to said vector processor, said memory storing predefined blocks of data elements at respective addresses; said method comprising the steps of: receiving an instruction to obtain a specified vector of data elements and load said vector into said vector processor, determining the blocks of data which include at least one data element of said vector, transmitting requests to reference the blocks of data which are determined to include at least one data element of said vector, and in response to those requests fetching the blocks from memory when the blocks are not stored in said data buffer, and obtaining from the referenced blocks said data elements of said vector and transmitting said data elements of said vector to said vector processor.
Claim 12
Dependent Claim
51 words
The method as claimed in claim 9, wherein said step of transmitting includes the steps of checking whether the referenced blocks of data are stored in said data buffer, and when the reference blocks of data are not found in said data buffer, transmitting respective fetch requests to said main memory.
Claim 13
Dependent Claim
39 words
The method as claimed in claim 10, wherein said method further comprises loading said fetch requests into a fetch buffer, and removing said fetch requests from said fetch buffer when their respective blocks of data are fetched from memory.
Claim 14
Dependent Claim
24 words
The method as claimed in claim 11, wherein said step of transmitting respective fetch requests is temporarily suspended when the fetch buffer becomes full.
Claim 15
Dependent Claim
52 words
The method as claimed in claim 11, wherein said step of transmitting respective fetch requests includes the step of checking whether the fetch buffer already includes the fetch request, and when the fetch buffer is found to already include the fetch request, inhibiting retransmission of the fetch request to the main memory.
Claim 16
Dependent Claim
19 words
The method as claimed in claim 11, wherein said step of determining is performed by executing a microcode procedure.
Claim 17
Dependent Claim
58 words
The method as claimed in claim 9, wherein said step of determining the blocks of data which include at least one data element of said vector includes the steps of sequentially computing the addresses associated with successive data elements of the vector, and testing whether each computed address is within a different block from the previously computed address.
Claim 18
Dependent Claim
64 words
The method as claimed in claim 15, wherein said addresses associated with successive data elements differ by a predetermined stride, and said step of sequentially computing the addresses associated with successive data elements of the vector computes the address of every Mth data element of the vector, where M is an integer for which different values are selected as a function of said stride.
Claim 19
Dependent Claim
37 words
The method as claimed in claim 16, wherein said blocks each have the same predetermined memory size, and said step of sequentially computing includes the step of comparing said stride to said memory size of said blocks.
Claim 20
Dependent Claim
33 words
The method as claimed in claim 16, further comprising the step of changing a count by said integer M each time said address of every Mth data element of the vector is computed.
Claim 21
Dependent Claim
43 words
The method as claimed in claim 18, further comprising the step of adjusting the address computed for the last Mth data element of the vector by a value which is selected as a function of a remainder of said count and said stride.
Claim 22
Independent Claim
207 words
A method of operating a digital computer having a main memory, a cache, a scalar processor, and a vector processor; said memory including means for storing data elements at respective addresses; said cache including cache memory means for storing selected predefined blocks of said data elements, means for receiving requests to reference a specified block of said data, means for checking whether data for the specified block is stored in the cache memory means, and means operative when data for the specified block is not so stored for reading the specified block of data from said main memory and storing the block of data in the cache memory means; said method comprising the steps of: receiving an instruction to obtain a specified vector of said data elements and load said vector into said vector processor; determining the blocks of data which include at least one data element of said vector, transmitting to said cache requests to reference the blocks of data which are determined to include at lest one data element of said vector, and thereafter transmitting to said cache requests to reference individually said data elements of said specified vector, and transmitting said data elements of said specified vector from said cache to said vector processor.
Claim 23
Independent Claim
207 words
A method of operating a digital computer having a main memory, a cache, a scalar processor, and a vector processor; said memory including means for storing data elements at respective addresses; said cache including cache memory means for storing selected predefined blocks of said data elements, means for receiving requests to reference a specified block of said data, means for checking whether data for the specified block is stored in the cache memory means, and means operative when data for the specified block is not so stored for reading the specified block of data from said main memory and storing the block of data in the cache memory means; said method comprising the steps of: receiving an instruction to obtain a specified vector of said data elements and load said vector into said vector processor; determining the blocks of data which include at least one data element of said vector, transmitting to said cache requests to reference the blocks of data which are determined to include at lest one data element of said vector, and thereafter transmitting to said cache requests to reference individually said data elements of said specified vector, and transmitting said data elements of said specified vector from said cache to said vector processor.
Claim 24
Dependent Claim
33 words
The method as claimed in claim 20, wherein said step of determining the blocks of data which include at least one data element of said vector is performed by a micro-sequencer executing microcode.
Claim 25
Dependent Claim
55 words
A method as claimed in claim 21, where in said micro-sequencer determines the blocks of data which include at least one data element of said vector by referencing a vector address register and sequentially computing the addresses associated with successive data elements of the vector and storing the computed address in the vector address register.
Claim 26
Dependent Claim
58 words
The method as claimed in claim 22, wherein said micro-sequencer determines the blocks of data which include at least one data element of said vector by referencing a vector length register and changing a value in said vector length register each time said micro-sequencer computes the address associated with one of said successive data elements of said vector.
Claim 27
Dependent Claim
50 words
The method as claimed in claim 22, wherein said addresses associated with successive data elements differ by a predetermined stride, and said micro-sequencer successively computes the address associated with every Mth data element of said vector, and selects M as an integer which is a predetermined function of said stride
Claim 28
Dependent Claim
41 words
The method as claimed in claim 24, wherein said data blocks have a predetermined size, and said micro-sequencer selects a value for M by comparing said stride to predetermined values, said predetermined values including said predetermined size of the data blocks.
Claim 29
Dependent Claim
242 words
A digital computer having a main memory and a cache coupled to said main memory; said main memory including means for storing data elements at respective addresses; said cache including cache memory means for storing selected predefined blocks of said data elements, means for receiving requests to reference a specified block of said data, means for checking whether data for the specified block is stored in the cache memory means, and means operative when data for the specified block is not so stored for reading the specified block of data from said main memory and storing the block of data in the cache memory means; wherein the improvement comprises: a vector processor coupled to said cache, said vector processor including means for receiving a sequence of data elements from said cache and performing vector operations on said data elements, and prefetch generator means coupled to said vector processor and said cache for prefetching the blocks of data which include the data elements of a vector specified by a vector load instruction, wherein said prefetch generator means includes means for receiving an instruction to obtain a specified vector of said data elements and load them into said vector processor, means for determining the blocks of data which include at least one data element of said vector, and means for transmitting to said cache requests to reference the blocks of data which are determined to include at least one data element of said vector.
Claim 30
Dependent Claim
242 words
A digital computer having a main memory and a cache coupled to said main memory; said main memory including means for storing data elements at respective addresses; said cache including cache memory means for storing selected predefined blocks of said data elements, means for receiving requests to reference a specified block of said data, means for checking whether data for the specified block is stored in the cache memory means, and means operative when data for the specified block is not so stored for reading the specified block of data from said main memory and storing the block of data in the cache memory means; wherein the improvement comprises: a vector processor coupled to said cache, said vector processor including means for receiving a sequence of data elements from said cache and performing vector operations on said data elements, and prefetch generator means coupled to said vector processor and said cache for prefetching the blocks of data which include the data elements of a vector specified by a vector load instruction, wherein said prefetch generator means includes means for receiving an instruction to obtain a specified vector of said data elements and load them into said vector processor, means for determining the blocks of data which include at least one data element of said vector, and means for transmitting to said cache requests to reference the blocks of data which are determined to include at least one data element of said vector.
Claim 31
Dependent Claim
34 words
The digital computer as claimed in claim 26, further comprising means coupled to said cache and said vector processor for transmitting said data elements of said vector from said cache to said vector processor.
Claim 32
Dependent Claim
43 words
The digital computer as claimed in claim 27, wherein said means for transmitting said data elements include cache memory bypass means for transmitting to said vector processor said data elements fetched from the main memory when they are being written into the cache.
Claim 33
Dependent Claim
41 words
The digital computer as claimed in claim 26, wherein said means for transmitting includes a register coupled in the data path between the main memory and the cache, and a register bypass gate connected to said register for bypassing said register.
Claim 34
Dependent Claim
58 words
The digital computer as claimed in claim 26, wherein said means for determining the blocks of data which include at least one data element of said vector includes means for sequentially computing the addresses associated with successive data elements of said vector, and testing whether each computed address is within a different block from the previously computed address.
Claim 35
Dependent Claim
68 words
The digital computer as claimed in claim 26, wherein said cache includes a fetch request buffer for buffering said requests to reference the blocks of data, said fetch request buffer providing a signal indicating when the fetch request buffer is full, and said prefetch generator means has means responsive to said buffer full signal for temporarily suspending the transmission of said requests to reference the blocks of data.
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-12-18 | 1993-06-19 | 1993-12-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-12-18 | 1997-06-19 | 1997-12-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-12-18 | 2001-06-19 | 2001-12-19 | $7700.00 | Window Closed / Lapsed |