Creating page coherency and improved bank sequencing in a memory access command stream

• US 6,628,292 B1
• Filed: 07/31/1999
• Issued: 09/30/2003
• Est. Priority Date: 07/31/1999
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Prouty, Bryan G., Ashburn, Jon L
• Primary Examiner(s): Chauhan, Ulka J.
• Application Number:
  US09/364,973
• Time in Patent Office: 1,522 Days
• Field of Search: 345/503, 345/506, 345/520, 345/522, 345/531, 345/533, 345/535, 345/537, 345/545, 345/565, 345/570, 345/571, 710/33, 710/35, 710/39, 710/54, 710/52, 710/55, 710/56, 710/310
• US Class Current: 345/565
• CPC Class Codes: G09G 5/39 Control of the bit-mapped memory

Abstract

A buffer facilitates reordering of incoming memory access commands so that the memory access commands may be associated automatically according to their row/bank addresses. The storage capacity in the buffer may be dynamically allocated among groups as needed. When the buffer is flushed, groups of memory access commands are selected for flushing whose row/bank addresses are associated, thereby creating page coherency in the flushed memory access commands. Batches of commands may be flushed from the buffer according to a sequence designed to minimize same-bank page changes in frame buffer memory devices. Good candidate groups for flushing may be chosen according to criteria based on the binary bank address for the group, the size of the group, and the age of the group. Groups may be partially flushed. If so, a subsequent flush operation may resume flushing a partially-flushed group when to do so would be more beneficial than flushing a different group chosen solely based on its bank address. The first and last commands flushed in any batch are accompanied by flags indicating that they are the first and last commands in the batch, respectively.

Claims

1. Circuitry for storing pixel commands to facilitate reordering of the pixel commands, each pixel command comprising pixel data and pixel row/bank and column addresses to facilitate reordering of the pixel commands, comprising:

a bus for receiving a pixel commands from a pipeline, each pixel command accompanied by pixel data, a pixel row/bank address and a pixel column address;

a row/bank address storage array for storing each received pixel command'"'"'s row/bank address in a row/bank address entry when the received pixel command'"'"'s row/bank address is not currently stored in the row/bank address storage array;

a multi-line column address storage array for storing in an available line of the column address storage array the MSBs of the pixel command'"'"'s column addresses when such MSBs are not currently stored in a line of the column address storage array that is currently associated with the row/bank address entry matching the command'"'"'s row/bank address;

a line-in-use bit array having columns associated with columns of the row/bank address storage array and rows associated with lines of the column address storage array, wherein cells of the line-in-use bit array associate the row/bank address entry matching the command'"'"'s row/bank address with the line of the column address storage array in which the pixel'"'"'s column address MSBs are stored when such an association has not been made for a previously-received command; and

a multi-line pixel data storage array, having lines of pixel entry locations which are associated with the lines of the column address storage array, for storing the pixel command'"'"'s pixel data within a line of pixel entries in the pixel data storage array which is associated with the line of the column address storage array in which the command'"'"'s column address MSBs are stored.

2. A method for storing memory access commands each comprising pixel data and pixel row/bank and column addresses to facilitate reordering of the memory access commands, wherein for each received memory access command, the method comprises:

storing the received command'"'"'s row/bank address in a row/bank address entry of a row/bank address storage array when the row/bank address is not currently stored in the row/bank address storage array;

storing the MSBs of the command'"'"'s column addresses in an available line of a multi-line column address storage array when such MSBs are not currently stored in a line of the column address storage array that is currently associated with the row/bank address entry matching the command'"'"'s row/bank address;

firstly associating the row/bank address entry matching the command'"'"'s row/bank address with the line of the column address storage array in which the pixel'"'"'s column address MSBs are stored when such first association has not been made for a previously-received command;

secondly associating a line of pixel entries in a multi-line pixel data storage array with the line of the column address storage array in which the command'"'"'s column address MSBs are stored when such second association has not been made for a previously-received memory access command; and

storing the command'"'"'s pixel data within the associated line of the pixel entries.

3. The method of claim 2, further comprising:

selecting for batch flushing a group of pixel data entries which are associated with a same row/bank address.

4. The method of claim 3, further comprising:

flushing the selected group of currently-stored pixel data when the group meets at least one of the following conditions;

condition 1;

[Did a previous flush operation leave the group partially unflushed?] AND [Is the group'"'"'s age older than a threshold age? OR Is the group'"'"'s size larger than a threshold size?];

condition 2;

[Is the group'"'"'s binary bank address unequal to the binary bank address of the last-flushed group?] AND [Is the group'"'"'s binary bank address unequal to the bank address of the z buffer that is attached to the last-flushed group AND Does the group'"'"'s size exceed a threshold size?];

condition 3;

[Is the group'"'"'s binary bank address unequal to the binary bank address of the last-flushed group?] AND [Is the group'"'"'s binary bank address unequal to the binary bank address of the z buffer that is attached to the last-flushed group?] AND [Does the group'"'"'s age exceed a threshold age?].

5. The method of claim 2, further comprising:

flushing at least a portion of the stored pixel data.

6. The method of claim 2, further comprising:

selecting a group of pixel data entries which are associated with a same row/bank address;

selecting a flushing mode from one of the following three flushing modes;

(1) must flush all stored pixel data from storage, (2) must flush at least all stored pixel data in the selected group, or (3) may flush only a portion of all stored pixel data in the selected group; and

flushing the stored pixel data according to the selected flushing mode.

7. The method of claim 6, wherein, when the selected flushing mode is mode (3), the method further comprises:

after each line of stored pixel entries belonging to the selected group is flushed and while more lines of pixel entries belonging to the selected group remain in storage, determining condition 1;

[Is the group not older than a threshold age? AND Is the size of the group remaining to be flushed not larger than a threshold size?]; and

if condition 1 is true, discontinuing the flush even though the group has only been partially flushed.

8. The method of claim 7, further comprising:

if condition 1 is false, determining condition 2;

[Is room available in the output buffer for the smaller of a maximum batch size or the remainder of this group?]; and

if condition 2 is true, continuing to flush the group.

9. The method of claim 2, further comprising:

flushing at least a portion of the stored pixel data when a timeout has occurred during which no new memory access commands have been received.

10. The method of claim 2, further comprising:

flushing at least a portion of the stored pixel data when a pixel collision occurs.

11. The method of claim 2, further comprising:

flushing at least a portion of the stored pixel data when the received command'"'"'s row/bank address is not and cannot be stored in a row/bank address entry of a row/bank address storage array.

12. The method of claim 2, further comprising:

flushing at least a portion of the stored pixel data when the MSBs of a received memory access command'"'"'s column addresses is not and cannot be stored in the column address storage array.

13. The method of claim 2, further comprising:

flushing at least a portion of the stored pixel data when a timeout has occurred during which an output buffer has been idle.

14. The method of claim 2, further comprising:

selecting for batch flushing an optimal group of pixel data entries which are associated with a same row/bank address based on at least one best-group criterion; and

flushing the selected group of pixel data entries.

15. The method of claim 14, wherein the at least one best-group criterion comprises:

[Was the last-flushed group only partially flushed?] AND [Is the last-flushed group older than a threshold age? OR Is the last-flushed group larger than a threshold size?].

16. The method of claim 14, wherein the at least one best-group criterion comprises:

[If there are no currently-stored “

bank mesh”

groups whose binary bank addresses are neither equal to the binary bank address of the last-flushed group nor equal to the binary bank address of the z buffer that is attached to the last-flushed group, then select the largest of the currently-stored groups].

17. The method of claim 14, wherein the at least one best-group criterion comprises:

[If there are any currently-stored “

large bank mesh”

groups whose binary bank addresses are neither equal to the binary bank address of the last-flushed group nor equal to the binary bank address of the z buffer that is attached to the last-flushed group, AND at least one of the bank mesh groups is larger than a threshold size, then select the largest of the large bank mesh groups].

18. The method of claim 14, wherein the at least one best-group criterion comprises:

[If there are any currently-stored “

old bank mesh”

groups whose binary bank addresses are neither equal to the binary bank address of the last-flushed group nor equal to the binary bank address of the z buffer that is attached to the last-flushed group, AND at least one of the bank mesh groups is older than a threshold age, then select-the largest of the old bank mesh groups].

19. The method of claim 14, wherein the at least one best-group criterion comprises:

[If there are any currently-stored “

bank mesh”

groups whose binary bank addresses are neither equal to the binary bank address of the last-flushed group nor equal to the binary bank address of the z buffer that is attached to the last-flushed group, BUT none of the bank mesh groups is larger than a threshold size or older than a threshold age, then select the largest of the bank mesh groups].

20. The method of claim 14, further comprising:

flushing pixel data that share a common row/bank address by sending at least first pixel data and last pixel data to an output buffer;

accompanying the first pixel with a flag indicating that it is the first pixel data in the batch; and

accompanying the last pixel data with a flag indicating that it is the last pixel data in the batch.

21. The method of claim 2, wherein the memory access commands are pixel commands.