# US 2004/0080512 A1 · Efficient hardware a-buffer using three-dimensional allocation of fragment memory

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2004/0080512 A1
- Document ID: US20040080512A1
- Status: Published application
- Kind: A1
- Application number: 10/280,721
- Filed: 2002-10-24
- Published: 2004-04-29
- Earliest claimed: 2002-10-24
- Assignees: Hewlett-Packard Development Company, L.P.
- Inventors: Joel James McCormack; Norman P. Jouppi; Larry Dean Seiler
- Web page: https://patentgrep.com/patent/US20040080512A1

## CPC

- G09G 5/363: {Graphics controllers}
- G06F 12/0215: {with look ahead addressing means}
- G06F 12/023: {Free address space management}
- G06T 1/60: Memory management
- G09G 5/39: Control of the bit-mapped memory
- G09G: ARRANGEMENTS OR CIRCUITS FOR CONTROL OF INDICATING DEVICES USING STATIC MEANS TO PRESENT VARIABLE INFORMATION (arrangements for transferring data between digital computers and displays G06F3/14; static indicating arrangements comprising an association of a number of separate sources or light control cells G09F9/00; static indicating arrangements comprising integral associations of a number of light sources H01J, H01K, H10H, H05B33/12; scanning, transmission or reproduction of documents or the like, e.g. facsimile transmission, details thereof H04N1/00)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

A method and apparatus for arranging fragments in a graphics memory. Each pixel of a display has a corresponding list of fragments in the graphics memory. Each fragment describes a three-dimensional surface at a plurality of sample points associated with the pixel. A predetermined number of fragments are statically allocated to each pixel. Additional space for fragment data is dynamically allocated and deallocated. Each dynamically allocated unit of memory contains fragment data for a plurality of pixels. Fragment data are arranged to exploit modem DRAM capabilities by increasing locality of reference within a single DRAM page, by putting other fragments likely to be referenced soon in pages that belong to non-conflicting banks, and by maintaining bookkeeping structures that allow the relevant DRAM precharge and row activate operations to be scheduled far in advance of access to fragment data

## Claims

### Claim 1

A method, comprising:
statically allocating a portion of a memory to store a first pre-determined number of base fragments for each of a plurality of pixels; and
dynamically allocating a portion of the memory for overflow panes of additional fragment storage, wherein the overflow panes each include storage for a second pre-determined number of fragments for each of a group of the pixels that are physically near each other in a two-dimensional coordinate system.

### Claim 2 (depends on 1)

The method of claim 1, wherein the dynamically allocating step comprises:
allocating a first overflow pane to store a plurality of overflow fragments for a first group of the pixels that are physically near each other in the two-dimensional coordinate system; and
allocating a second overflow pane to store a plurality of overflow fragments for a second group of the pixels that are physically near each other and that are physically near the first group of pixels in the two-dimensional coordinate system.

### Claim 3 (depends on 2)

The method of claim 2, wherein said statically allocating step comprises allocating a portion of a first bank of memory to store base fragments for the first group of pixels.

### Claim 4 (depends on 3)

The method of claim 3, wherein the statically allocating step comprises allocating a portion of a second bank of memory to store base fragments for the second group of pixels.

### Claim 5 (depends on 4)

The method of claim 4, wherein the first bank and the second bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 6 (depends on 4)

The method of claim 4, wherein the dynamically allocating step comprises allocating a portion of a third bank of memory to store the overflow fragments for the first group of pixels.

### Claim 7 (depends on 6)

The method of claim 6, wherein the first bank, the second bank and the third bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 8 (depends on 6)

The method of claim 6, wherein the dynamically allocating step comprises allocating a portion of a fourth bank of memory to store the overflow fragments for the second group of pixels.

### Claim 9 (depends on 8)

The method of claim 8, wherein the first bank, the second bank, the third bank and the fourth bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 10 (depends on 1)

The method of claim 1, wherein the dynamically allocating step comprises:
allocating a first overflow pane to store a first plurality of overflow fragments for a group of the pixels that are physically near each other in the two-dimensional coordinate system; and
allocating a second overflow pane to store a second plurality of overflow fragments for the group of the pixels, wherein the first plurality and the second plurality of overflow fragments include consecutive fragments for at least one of the pixels of the group.

### Claim 11 (depends on 10)

The method of claim 10, wherein the dynamically allocating step comprises:
allocating a portion of a first bank of memory to store the first plurality of overflow fragments; and
allocating a portion of a second bank of memory to store the second plurality of overflow fragments, wherein the first bank and the second bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 12 (depends on 1)

The method of claim 1, further comprising maintaining fragment bookkeeping information separately from fragment data.

### Claim 13 (depends on 12)

The method of claim 12, wherein the maintaining step comprises storing a fragment count value for each of the pixels in a two-dimensional array.

### Claim 14 (depends on 13)

The method of claim 13, wherein the two-dimensional array has entries each corresponding to one or more of the pixels.

### Claim 15 (depends on 13)

The method of claim 13, wherein the entries of the two-dimensional array are indexed by at least part of the coordinates of the pixels.

### Claim 16 (depends on 1)

The method of claim 1, further comprising maintaining address information of the overflow panes separately from fragment data.

### Claim 17 (depends on 16)

The method of claim 16, wherein the maintaining step comprises storing the address information in a plurality of two-dimensional arrays, each entry of which is associated with a group of the pixels and a group of fragments, each entry of the two-dimensional arrays storing one of the addresses or a NULL value.

### Claim 18 (depends on 17)

The method of claim 17, wherein the plurality of two-dimensional arrays are indexed by at least part of the coordinates of the pixels and by a value representative of at least part of a fragment number.

### Claim 19 (depends on 18)

The method of claim 18, wherein the value is computed as a remainder of dividing a fragment number by a predetermined integer.

### Claim 20 (depends on 16)

The method of claim 16, wherein the maintaining step comprises storing the addresses in at least one linear fragment overflow map.

### Claim 21 (depends on 20)

The method of claim 20, wherein the at least one linear fragment overflow map comprises an entry corresponding to a first memory location at which a first one of the overflow panes is stored, the entry storing a value representative of a second memory location at which a second one of the overflow panes is stored.

### Claim 22 (depends on 1)

The method of claim 1, wherein the statically allocating step comprises allocating an entire page of memory to store the first pre-determined number of base fragments for the group of the pixels, and wherein the dynamically allocating step comprises allocating a fraction of a page of memory for each of the overflow panes.

### Claim 23 (depends on 22)

The method of claim 22, wherein the dynamically allocating step comprises:
allocating a first overflow pane to store a plurality of overflow fragments for a first group of the pixels that are physically near each other in the two-dimensional coordinate system; and
allocating a second overflow pane to store a plurality of overflow fragments for a second group of the pixels that are physically near each other and that are physically near the first group of pixels in the two-dimensional coordinate system.

### Claim 24 (depends on 23)

The method of claim 23, wherein said statically allocating step comprises allocating a page of a first bank of memory to store base fragments for the first group of pixels.

### Claim 25 (depends on 24)

The method of claim 24, wherein the statically allocating step comprises allocating a page of a second bank of memory to store base fragments for the second group of pixels.

### Claim 26 (depends on 25)

The method of claim 25, wherein the first bank and the second bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 27 (depends on 25)

The method of claim 25, wherein the dynamically allocating step comprises allocating a fraction of a page of a third bank of memory to store the overflow fragments for a portion of the first group of pixels.

### Claim 28 (depends on 27)

The method of claim 27, wherein the first bank, the second bank and the third bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 29 (depends on 27)

The method of claim 27, wherein the dynamically allocating step comprises allocating a fraction of a page of a fourth bank of memory to store the overflow fragments for another portion of the first group of pixels.

### Claim 30 (depends on 29)

The method of claim 29, wherein the first bank, the second bank, the third bank and the fourth bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 31 (depends on 29)

The method of claim 29, wherein the first bank, the third bank and the fourth bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 32 (depends on 25)

The method of claim 25, wherein the dynamically allocating step comprises allocating a fraction of a page of a fourth bank of memory to store the overflow fragments for a portion of the second group of pixels, and wherein the first bank, the second bank, the third bank and the fourth bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 33 (depends on 22)

The method of claim 22, wherein the dynamically allocating step comprises:
allocating a first overflow pane to store a first plurality of overflow fragments for a group of the pixels that are physically near each other in the two-dimensional coordinate system; and
allocating a second overflow pane to store a second plurality of overflow fragments for the group of the pixels, wherein the first plurality and the second plurality of overflow fragments include consecutive fragments for at least one of the pixels of the group.

### Claim 34 (depends on 33)

The method of claim 33, wherein the dynamically allocating step comprises:
allocating a fraction of a page of a first bank of memory to store the first plurality of overflow fragments; and
allocating a fraction of a page of a second bank of memory to store the second plurality of overflow fragments, wherein the first bank and the second bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 35 (depends on 1)

The method of claim 1, wherein the statically allocating step and the dynamically allocating step comprise allocating conflicting banks of memory to store base fragments and overflow fragments for two groups of pixels provided that the two groups are physically far away from each other in the two-dimensional coordinate system.

### Claim 36 (depends on 1)

The method of claim 1, wherein the statically allocating step and the dynamically allocating step comprise allocating conflicting banks of memory to store the base fragments and overflow fragments for the first group of pixels provided that non-conflicting banks have been allocated to store portions of the base fragments and overflow fragments.

### Claim 37 (depends on 1)

The method of claim 1, wherein the statically allocating step comprises allocating a bank of memory associated with a first memory controller to a first group of the pixels and allocating a bank of memory associated with a second memory controller to a second group of the pixels.

### Claim 38 (depends on 37)

The method of claim 37, wherein the dynamically allocating step comprises allocating a bank of memory associated with the first memory controller for overflow panes of additional storage for the first group of the pixels and allocating a bank of memory associated with the second memory controller for overflow panes of additional storage for the second group of the pixels.

### Claim 39 (depends on 37)

The method of claim 37, wherein the first group of the pixels are physically contiguous to each other in the two-dimensional coordinate system.

### Claim 40 (depends on 37)

The method of claim 37, wherein the first group of pixels and the second group of pixels are dispersed across an area of the two-dimensional coordinate system.

### Claim 41 (depends on 1)

The method of claim 1, wherein the dynamically allocating step comprises: allocating an overflow pane to store a plurality of overflow fragments for a group of the pixels; and
deallocating the overflow pane when no pixel in the group requires storage for overflow fragments in the overflow pane.

### Claim 42 (depends on 41)

The method of claim 41, further comprising maintaining a fragment count value that indicates a number of fragments stored within the overflow pane.

### Claim 43 (depends on 42)

The method of claim 42, wherein the deallocating step comprises deallocating the overflow pane when the fragment count value for the overflow pane indicates that no pixel in the group requires storage for overflow fragments in the overflow pane.

### Claim 44

A computer graphics sub-system, comprising:
means for statically allocating a portion of a memory to store a first pre-determined number of base fragments for each of a plurality of pixels; and
means for dynamically allocating a portion of the memory for overflow panes of additional fragment storage, wherein the overflow panes each include storage for a second pre-determined number of fragments for each of a group of the pixels that are physically near each other in a two-dimensional coordinate system.

### Claim 45 (depends on 44)

The computer graphics sub-system of claim 44, wherein the means for dynamically allocating comprises:
means for allocating a first overflow pane to store a plurality of overflow fragments for a first group of the pixels that are physically near each other in the two-dimensional coordinate system; and
means for allocating a second overflow pane to store a plurality of overflow fragments for a second group of the pixels that are physically near each other and that are physically near the first group of pixels in the two-dimensional coordinate system.

### Claim 46 (depends on 45)

The computer graphics sub-system of claim 45, wherein the means for statically allocating allocates a portion of a first bank of memory to store base fragments for the first group of pixels.

### Claim 47 (depends on 46)

The computer graphics sub-system of claim 46, wherein the means for statically allocating allocates a portion of a second bank of memory to store base fragments for the second group of pixels.

### Claim 48 (depends on 47)

The computer graphics sub-system of claim 47, wherein the first bank and the second bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 49 (depends on 47)

The computer graphics sub-system of claim 47, wherein the means for dynamically allocating allocates a portion of a third bank of memory to store the overflow fragments for the first group of pixels.

### Claim 50 (depends on 49)

The computer graphics sub-system of claim 49, wherein the first bank, the second bank and the third bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 51 (depends on 49)

The computer graphics sub-system of claim 49, wherein the means for dynamically allocating allocates a portion of a fourth bank of memory to store the overflow fragments for the second group of pixels.

### Claim 52 (depends on 51)

The computer graphics sub-system of claim 51, wherein the first bank, the second bank, the third bank and the fourth bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 53 (depends on 44)

The computer graphics sub-system of claim 44, wherein the means for dynamically allocating comprises:
means for allocating a first overflow pane to store a first plurality of overflow fragments for a group of the pixels that are physically near each other in the two-dimensional coordinate system; and
means for allocating a second overflow pane to store a second plurality of overflow fragments for the group of the pixels, wherein the first plurality and the second plurality of overflow fragments include consecutive fragments for at least one of the pixels of the group.

### Claim 54 (depends on 53)

The computer graphics sub-system of claim 53, wherein the means for dynamically allocating comprises:
means for allocating a portion of a first bank of memory to store the first plurality of overflow fragments; and
means for allocating a portion of a second bank of memory to store the second plurality of overflow fragments, wherein the first bank and the second bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 55 (depends on 44)

The computer graphics sub-system of claim 44, further comprising means for maintaining fragment bookkeeping information separately from fragment data.

### Claim 56 (depends on 55)

The computer graphics sub-system of claim 55, wherein the means for maintaining stores a fragment count value for each of the pixels in a two-dimensional array.

### Claim 57 (depends on 56)

The computer graphics sub-system of claim 56, wherein the two-dimensional array has entries each corresponding to one or more of the pixels.

### Claim 58 (depends on 56)

The computer graphics sub-system of claim 56, wherein the entries of the two-dimensional array are indexed by at least part of the coordinates of the pixels.

### Claim 59 (depends on 44)

The computer graphics sub-system of claim 44, further comprising means for maintaining address information of the overflow panes separately from fragment data.

### Claim 60 (depends on 59)

The computer graphics sub-system of claim 59, wherein the means for maintaining stores the address information in a plurality of two-dimensional arrays, each entry of which is associated with a group of the pixels and a group of fragments, each entry of the two-dimensional arrays storing one of the addresses or a NULL value.

### Claim 61 (depends on 60)

The computer graphics sub-system of claim 60, wherein the plurality of two-dimensional arrays are indexed by at least part of the coordinates of the pixels and by a value representative of at least part of a fragment number.

### Claim 62 (depends on 61)

The computer graphics sub-system of claim 61, wherein the value is computed as a remainder of dividing a fragment number by a predetermined integer.

### Claim 63 (depends on 59)

The computer graphics sub-system of claim 59, wherein the means for maintaining stores the addresses in at least one linear fragment overflow map.

### Claim 64 (depends on 63)

The computer graphics sub-system of claim 63, wherein the at least one linear fragment overflow map comprises an entry corresponding to a first memory location at which a first one of the overflow panes is stored, the entry storing a value representative of a second memory location at which a second one of the overflow panes is stored.

### Claim 65 (depends on 44)

The computer graphics sub-system of claim 44, wherein the means for statically allocating allocates an entire page of memory to store the first pre-determined number of base fragments for the group of the pixels, and wherein the means for dynamically allocating allocates a fraction of a page of memory for each of the overflow panes.

### Claim 66 (depends on 65)

The computer graphics sub-system of claim 65, wherein the means for dynamically allocating comprises:
means for allocating a first overflow pane to store a plurality of overflow fragments for a first group of the pixels that are physically near each other in the two-dimensional coordinate system; and
means for allocating a second overflow pane to store a plurality of overflow fragments for a second group of the pixels that are physically near each other and that are physically near the first group of pixels in the two-dimensional coordinate system.

### Claim 67 (depends on 66)

The computer graphics sub-system of claim 66, wherein the means for statically allocating allocates a page of a first bank of memory to store base fragments for the first group of pixels.

### Claim 68 (depends on 67)

The computer graphics sub-system of claim 67, wherein the means for statically allocating allocates a page of a second bank of memory to store base fragments for the second group of pixels.

### Claim 69 (depends on 68)

The computer graphics sub-system of claim 68, wherein the first bank and the second bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 70 (depends on 68)

The computer graphics sub-system of claim 68, wherein the means for dynamically allocating allocates a fraction of a page of a third bank of memory to store the overflow fragments for a portion of the first group of pixels.

### Claim 71 (depends on 70)

The computer graphics sub-system of claim 70, wherein the first bank, the second bank and the third bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 72 (depends on 70)

The computer graphics sub-system of claim 70, wherein the means for dynamically allocating allocates a fraction of a page of a fourth bank of memory to store the overflow fragments for another portion of the first group of pixels.

### Claim 73 (depends on 72)

The computer graphics sub-system of claim 72, wherein the first bank, the second bank, the third bank and the fourth bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 74 (depends on 72)

The computer graphics sub-system of claim 72, wherein the first bank, the third bank and the fourth bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 75 (depends on 68)

The computer graphics sub-system of claim 68, wherein the means for dynamically allocating allocates a fraction of a page of a fourth bank of memory to store the overflow fragments for a portion of the second group of pixels, and wherein the first bank, the second bank, the third bank and the fourth bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 76 (depends on 65)

The computer graphics sub-system of claim 65, wherein the means for dynamically allocating comprises:
means for allocating a first overflow pane to store a first plurality of overflow fragments for a group of the pixels that are physically near each other in the two-dimensional coordinate system; and
means for allocating a second overflow pane to store a second plurality of overflow fragments for the group of the pixels, wherein the first plurality and the second plurality of overflow fragments include consecutive fragments for at least one of the pixels of the group.

### Claim 77 (depends on 76)

The computer graphics sub-system of claim 76, wherein the means for dynamically allocating comprises:
means for allocating a fraction of a page of a first bank of memory to store the first plurality of overflow fragments; and
means for allocating a fraction of a page of a second bank of memory to store the second plurality of overflow fragments, wherein the first bank and the second bank are non-conflicting banks so as to reduce bank conflicts.

### Claim 78 (depends on 44)

The computer graphics sub-system of claim 44, wherein the means for statically allocating and the means for dynamically allocating allocate conflicting banks of memory to store base fragments and overflow fragments for two groups of pixels provided that the two groups are physically far away from each other in the two-dimensional coordinate system.

### Claim 79 (depends on 44)

The computer graphics sub-system of claim 44, wherein the means for statically allocating and the means for dynamically allocating allocate conflicting banks of memory to store the base fragments and overflow fragments for the first group of pixels provided that non-conflicting banks have been allocated to store portions of the base fragments and overflow fragments.

### Claim 80 (depends on 44)

The computer graphics sub-system of claim 44, wherein the means for statically allocating allocates a bank of memory associated with a first memory controller to a first group of the pixels and allocates a bank of memory associated with a second memory controller to a second group of the pixels.

### Claim 81 (depends on 80)

The computer graphics sub-system of claim 80, wherein the means for dynamically allocating allocates a bank of memory associated with the first memory controller for overflow panes of additional storage for the first group of the pixels and allocates a bank of memory associated with the second memory controller for overflow panes of additional storage for the second group of the pixels.

### Claim 82 (depends on 80)

The computer graphics sub-system of claim 80, wherein the first group of the pixels are physically contiguous to each other in the two-dimensional coordinate system.

### Claim 83 (depends on 80)

The computer graphics sub-system of claim 80, wherein the first group of pixels and the second group of pixels are dispersed across an area of the two-dimensional coordinate system.

### Claim 84 (depends on 44)

means for The computer graphics sub-system of claim 44, wherein the means for dynamically allocating comprises:
means for allocating an overflow pane to store a plurality of overflow fragments for a group of the pixels; and
means for deallocating the overflow pane when no pixel in the group requires storage for overflow fragments in the overflow pane.

### Claim 85 (depends on 84)

The computer graphics sub-system of claim 84, further comprising means for maintaining a fragment count value that indicates a number of fragments stored within the overflow pane.

### Claim 86 (depends on 85)

The computer graphics sub-system of claim 85, wherein the means for deallocating deallocates the overflow pane when the fragment count value for the overflow pane indicates that no pixel in the group requires storage for overflow fragments in the overflow pane.
