Tile-based graphics

CROSS-REFERENCE TO RELATED APPLICATION(S)

0001This application claims priority from Great Britain Application No. 1305921.7, filed on Apr. 2, 2013, the contents of which is incorporated in its entirety herein.

BACKGROUND

0002A tile-based graphics system renders 2D or 3D computer graphics images using tile based rendering. As part of a tile-based rendering technique a rendering space is sub-divided into a plurality of regions called tiles or blocks (herein referred to as “tiles”), which each comprise a plurality of pixels. Tiles are often rectangular, but they may be other shapes such as triangular or hexagonal. The rendering space may correspond to an image for display on a screen, but other render targets, such as texture data in memory, are also possible. Tiles can be various sizes, for example tiles may be 16×16 pixels. In one example of a screen resolution, there are 1280×1024 pixels. At such a resolution, there would 5120 tiles, each comprising 16×16 pixels.

0003As a matter of terminology, “pixels” are individual image points which are displayed in a final image, whereas “fragments” are individual image points which are processed in order to generate the pixels for display in a final image. Some implementations may provide multiple fragments overlapping one pixel. Primitives are often polygons, typically triangles, but may have other forms such as points, lines or patches.

0004A display list is derived, for each tile, indicating primitives located either partially or wholly within the tile. Each tile is rendered using its display list. The objects are rasterized to determine which objects are present in each of the fragments of the tile.

SUMMARY

0005This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

0006A tile-based graphics system has a rendering space sub-divided into a plurality of tiles which are to be processed. Graphics data items, such as parameters or texels, are fetched into a cache for use in processing one of the tiles. Indicators are determined for the graphics data items, whereby the indicator for a graphics data item indicates the number of tiles with which that graphics data item is associated. The graphics data items are evicted from the cache in accordance with the indicators of the graphics data items. For example, the indicator for a graphics data item may be a count of the number of tiles with which that graphics data item is associated, whereby the graphics data item(s) with the lowest count(s) is (are) evicted from the cache.

0007In particular, there is provided a method of processing data in a tile-based graphics system having a rendering space sub-divided into a plurality of tiles with which graphics data items are associated, the method comprising: fetching, from a graphics data memory into a cache, graphics data items which are to be used in processing one of the tiles; and reading the graphics data items from the cache for use in processing said one of the tiles, wherein the method further comprises: determining indicators for the graphics data items, wherein, for each of the graphics data items, the indicator for that graphics data item is indicative of the number of tiles with which that graphics data item is associated; determining which of the graphics data items in the cache to evict based on the determined indicators; and evicting the determined graphics data items from the cache.

0008The graphics data items may be stored in graphics data sets in the graphics data memory with each of the graphics data sets comprising one or more of the graphics data items. As an example, a particular graphics data item may be associated with a particular tile if a graphics data item in the graphics data set comprising the particular graphics data item is to be used to process the particular tile, and for each of the graphics data items, the indicator for that graphics data item may be indicative of the number of tiles which are processed using a graphics data item in the graphics data set comprising that graphics data item. As another example, a particular graphics data item may be associated with a particular tile if the particular graphics data item is to be used to process the particular tile, and for each of the graphics data items, the indicator for that graphics data item may be indicative of the number of tiles which are processed using that graphics data item.

0009The method may further comprise determining bounding regions for the graphics data items wherein a particular graphics data item may be associated with a particular tile if the bounding region for that graphics data item at least partially overlaps the particular tile, and for each of the graphics data items, the indicator for that graphics data item may be indicative of the number of tiles which at least partially overlap the bounding region for that graphics data item. For each of the graphics data items, the bounding region for that graphics data item may contain all of the graphics data items in the graphics data set of that graphics data item.

0010For each of the graphics data items, the number of tiles with which that graphics data item is associated may be determined during a step of determining which of the graphics data items are present in each of the tiles. Furthermore, the method may further comprise determining an order in which tiles are to be processed based on the indicators of the graphics data items in the cache and based on the step of determining which of the graphics data items are present in each of the tiles.

0011The graphics data items may be parameters defining geometry for inclusion in the tiles. For example, the graphics data sets may be parameter blocks and the graphics data memory may be a parameter buffer.

0012The graphics data items may be texels of textures for inclusion in the tiles. For example, the graphics data sets may be textures and the graphics data memory may be a texture memory.

0013For each of the graphics data items, the indicator may be a count of the number of tiles with which that graphics data item is associated. The method may further comprise decrementing the count for a particular graphics data item when a tile with which the particular graphics data item is associated has been processed. The step of determining which of the graphics data items in the cache to evict may comprise determining which of the graphics data items in the cache has the lowest count. Furthermore, the step of determining which of the graphics data items in the cache to evict may comprise determining whether any of the graphics data items have a count equal to zero. Furthermore, if the count of the particular graphics data item is one when a tile with which the particular graphics data item is associated has been processed then the method may comprise invalidating the cache entry corresponding to the particular graphics data item. The count may be limited, such that for each of the graphics data items, if the number of tiles with which that graphics data item is associated is greater than a predetermined maximum, the count may be determined to be equal to the predetermined maximum. It may be the case that the count is decremented only if the count is less than the predetermined maximum.

0014In an example, for each of the graphics data items, the indicator for that graphics data item indicates one of two conditions, the two conditions being: (i) that the number of tiles with which that graphics data item is associated is equal to one, and (ii) that the number of tiles with which that graphics data item is associated is greater than one.

0015In another example, for each of the graphics data items, the indicator for that graphics data item indicates one of four conditions, the four conditions being: (i) that the number of tiles with which that graphics data item is associated is equal to one, (ii) that the number of tiles with which that graphics data item is associated is equal to two, (iii) that the number of tiles with which that graphics data item is associated is equal to three or four, and (iv) that the number of tiles with that graphics data item is associated is greater than four.

0016The method may further comprise determining that further graphics data items are to be fetched into the cache, and determining that there is insufficient space in the cache to store the further graphics data items without evicting some graphics data items from the cache, wherein said determining which of the graphics data items in the cache to evict and said evicting the determined graphics data items from the cache may be performed responsive to said determining that there is insufficient space in the cache to store the further graphics data items.

0017If the determined indicators are the same for a plurality of the graphics data items, the step of determining which of the graphics data items in the cache to evict may be further based on respective times that the graphics data items in the cache were last used.

0018The indicators for the graphics data items may be stored in the cache and may also be stored in the graphics data memory. Alternatively, the indicators for the graphics data items may be stored in the graphics data memory and may be accessed by references stored in the cache referencing the indicators stored in the graphics data memory. In a simple example, a reference could be a pointer to the parameter block. The cache may store a pointer to the parameter block simply as the address (or “tag”) of the data (or a trivial function of it).

0019There is also provided a tile-based graphics system having a rendering space sub-divided into a plurality of tiles with which graphics data items are associated, the tile-based graphics system comprising a processing unit configured to: fetch, from a graphics data memory into a cache, graphics data items which are to be used in processing one of the tiles; read the graphics data items from the cache for use in processing said one of the tiles; determine indicators for the graphics data items, wherein, for each of the graphics data items, the indicator for that graphics data item is indicative of the number of tiles with which that graphics data item is associated; determine which of the graphics data items in the cache to evict based on the determined indicators; and evict the determined graphics data items from the cache.

0020The above features may be combined as appropriate, as would be apparent to a skilled person, and may be combined with any of the aspects of the examples.

BRIEF DESCRIPTION OF THE DRAWINGS

Examples will now be described in detail by way of reference to the accompanying drawings in which:

<figref idref="DRAWINGS">FIG. 1</figref> shows a tile-based graphics system;

<figref idref="DRAWINGS">FIG. 2</figref> represents objects included in a rendering space of a tile-based graphics system;

<figref idref="DRAWINGS">FIG. 3<i>a </i></figref>shows a first parameter block;

<figref idref="DRAWINGS">FIG. 3<i>b </i></figref>shows a second parameter block;

<figref idref="DRAWINGS">FIG. 4</figref> is a flow chart for a method of processing data in a tile-based graphics system;

<figref idref="DRAWINGS">FIG. 5</figref> shows a parameter cache;

<figref idref="DRAWINGS">FIG. 6</figref> represents another object included in a rendering space of a tile-based graphics system; and

<figref idref="DRAWINGS">FIG. 7</figref> represents further objects included in a rendering space of a tile-based graphics system.

0030Common reference numerals are used throughout the figures to indicate similar features.

DETAILED DESCRIPTION

0031Tile-based renderers may store primitive data (or “parameters”) representing geometrical objects or other geometry in blocks of memory called parameter blocks. Each parameter block contains parameters describing one or more primitives which may be located in multiple tiles. The parameters of the parameter block represent the location of the primitives (e.g. the location of vertices forming the primitives for example in screen space coordinates). The parameters of the parameter block may also indicate other features (or “attributes”) of the objects or geometry such as colour and texture.

0032Parameter blocks for a scene can be stored in a parameter buffer in a memory. The parameters are analysed to determine which of the parameters will be needed to process each of the tiles. In particular, a display list can be derived for each tile, which indicates parameters, if any, describing primitives located either partially or wholly within the tile. In this way, a display list for a tile identifies each of the parameters needed to process the tile. For example, the display list may include references to the relevant parameter data stored in the parameter buffer.

0033Each tile is rendered using its display list. The objects are rasterized to determine which objects are present in each of the fragments of the tile. During rasterization of the objects in a tile, the parameters indicated in the display list for that tile are fetched from their respective parameter blocks from the parameter buffer into a smaller local memory (which is, for example, on-chip memory) known as a parameter cache. The parameter cache is usually smaller than that required to store the parameters of all of the parameter blocks that are needed in order to render all of the tiles in a scene. Therefore, when a tile has been processed, and new parameters are fetched into the parameter cache for processing a new tile, some of the parameters stored in the parameter cache are evicted from the parameter cache.

0034In order to determine which of the parameters in the parameter cache are evicted, a Least Recently Used (LRU) eviction policy could be used. According to the LRU eviction policy, the least recently used items (i.e. parameters) are the first to be discarded from the parameter cache

0035Embodiments will now be described by way of example only.

0036<figref idref="DRAWINGS">FIG. 1</figref> is a schematic diagram showing a tile-based graphics system <b>100</b>. The system <b>100</b> may be implemented on a device, such as a smart phone, tablet, laptop, Personal Computer (PC), television, or any other appropriate device in which graphics data is to be processed. The tile-based graphics system <b>100</b> is configured to receive data, e.g. from an application, process the data and provide an output of processed data. The system <b>100</b> comprises a processing unit <b>102</b> which is configured to process the data. The processing unit <b>102</b> may be implemented in hardware or software, or a combination thereof. For example, some portions of processing unit <b>102</b> may be implemented in fixed-function hardware elements comprising circuits configured to process data accordingly as described herein. These fixed-function hardware elements can couple with programmable processing elements.

0037For example, processing unit <b>102</b> may include a physical realization of a Graphics Processing Unit (GPU) that includes some fixed function circuit elements, some programmable elements and some configurable elements, or some combination thereof. The different elements of this physical realization may be configured, organized and in some cases, reorganized, in order to implement different functional elements of a graphics rendering process. Many different graphics rendering processes can be conceptualized as a pipeline of different constituent operations. These constituent operations can be implemented on different elements in a GPU, on elements that can be simultaneously configured to perform multiple such operations, or on elements that were reconfigured to perform each such operation. Also, processing unit <b>102</b> can be modelled as implementing a rendering pipeline according to a particular logical flow, although actual operations being performed by processing unit <b>102</b> may differ, in some respects, from the logical flow. Implementations of processing unit <b>102</b> may include machine executable code configuring a programmable processor. When machine executable code to perform a specific function is used to configure a programmable processor, that programmable processor effectively both becomes and includes circuitry for performing that specific function (even as it also may simultaneously be and include circuitry for performing other functions).

0038The processing unit <b>102</b> comprises a plurality of functional blocks for processing data, wherein some (but, for clarity, not all) of the functional blocks of the processing unit <b>102</b> are shown in <figref idref="DRAWINGS">FIG. 1</figref>. In particular, the processing unit <b>102</b> comprises a tiling unit <b>106</b>, an image synthesis processor (ISP) block <b>108</b> and a texture and shading processor (TSP) block <b>110</b>. Examples of other functional elements of a graphics processing pipeline include aspects of geometry shading, tessellation, clipping, culling, and stencil. The system <b>100</b> comprises a memory <b>112</b> which is arranged to communicate with the processing unit <b>102</b> and blocks therein. The memory <b>112</b> comprises a parameter buffer <b>114</b> and a texture memory <b>116</b>. Memory <b>112</b> can have different physical manifestations; for example, texture memory <b>116</b> may include one or more levels of cache hierarchy, which are physically separate or shared with other kinds of data and memory <b>112</b> may support separate physical memories for parameter buffer <b>114</b> and for texture memory <b>116</b>. Memory <b>112</b> may have different numbers of physical ports in different implementations. As such, memory <b>112</b> represents a range of implementations, the details of which can be determined in accordance with objectives of that implementation, in accordance with the disclosure. The processing unit <b>102</b> also comprises a first parameter cache <b>118</b>, a second parameter cache <b>120</b> and a texture cache <b>122</b>; considerations relating to memory <b>112</b> apply also to caches <b>120</b> and <b>122</b>.

0039An input of the tiling unit <b>106</b> is arranged to receive graphics data. An output of the tiling unit <b>106</b> is coupled to an input of the parameter buffer <b>114</b>. A first output of the parameter buffer <b>114</b> is coupled to a first input of the ISP block <b>108</b>. An output of the ISP block <b>108</b> is coupled to a first input of the TSP block <b>110</b>. A second output of the parameter buffer <b>114</b> is coupled to an input of the first parameter cache <b>118</b> and to an input of the second parameter cache <b>120</b>. An output of the first parameter cache <b>118</b> is coupled to a second input of the ISP block <b>108</b>. An output of the second parameter cache <b>120</b> is coupled to a second input of the TSP block <b>110</b>. An output of the texture memory <b>116</b> is coupled to an input of the texture cache <b>122</b>. An output of the texture cache <b>122</b> is coupled to a third input of the TSP cache <b>110</b>.

0040In operation, the processing unit <b>102</b> is arranged to receive graphics data, e.g. coming from an application which is currently running on the device on which the system <b>100</b> is implemented. The graphics data comprises geometry data that defines objects for display. The tiling unit <b>106</b> includes logic for implementing a number of functions in the processing unit <b>102</b>. In one example, the tiling unit <b>106</b> receives the geometry data and derives a plurality of primitives from the geometry data. Some processing to the geometry data may, or may not, be performed by the processing unit <b>102</b> (in functional blocks which are not illustrated in <figref idref="DRAWINGS">FIG. 1</figref>) before the tiling unit <b>106</b> receives the geometry data. In another example, tiling unit <b>106</b> also can receive definitions of primitives defined from received geometry data. The primitives may form surfaces of objects represent geometrical objects or other geometry.

0041Parameters describing the primitives are stored in the parameter buffer <b>114</b> in blocks of memory called parameter blocks. Each parameter block contains parameters describing multiple primitives which may be located in multiple tiles. The primitives are often polygons, such as triangles, but may have other forms, such as lines, points or patches. The parameters of a parameter block represent the location of the primitives (e.g. the location of vertices forming the primitives for example in screen space coordinates). The parameters of the parameter block may also indicate other features of the objects or geometry such as colour and texture.

0042The tiling unit <b>106</b> divides a rendering space into a plurality of tiles, or uses a divided rendering space, each of which may comprise a plurality of fragments. The tiles may be rectangular (including square), but they could be other shapes such as triangular or hexagonal. The rendering space may correspond to an image for display on a screen, but other render targets, such as texture data in memory, are also possible.

0043For each tile, the tiling unit <b>106</b> determines whether each of the primitives is located at least partially within that tile. That is, the tiling unit <b>106</b> determines whether at least part of the primitive is located within a viewable region of the tile. This can be done using a number of well-known techniques. As an example, tiling unit <b>106</b> can transform 3-D geometry into “screen space” according to a transformation, such transformation can be defined based on a viewpoint. Such transformation can be performed by a programmable element configured accordingly, or by a circuit that can be configured with supplied parameters, for example.

0044In this way, the tiling unit <b>106</b> derives a display list, for each tile, comprising identifiers which identify the parameters (e.g. any of location, colour, and texture of the primitives), if any, which describe primitives which are located either partially or wholly within the tile. That is, the display list for a tile includes a set of references to the parameter blocks which contain geometry at least partially overlapping with the tile. Each of the references may be associated with a mask indicating the subset of parameters from that parameter block that represent primitives that are present in or pertain to primitives in the tile. In such implementations, the display list for a tile identifies each of the parameters needed to process the tile by providing references to relevant parameters stored in the parameter buffer <b>114</b>. In some cases, the display list may reference position parameters for the primitives, but does not need to reference all parameters available for each primitive (e.g., texture references).

0045The display lists can be provided from the tiling unit <b>106</b> to the parameter buffer <b>114</b> for storage therein. ISP block <b>108</b> can begin processing a tile by retrieving or otherwise accessing the display list for the tile. Such retrieving or accessing can proceed over time, such as by incrementally processing parts of the display list. When the ISP block <b>108</b> processes the tiles, it can, for example, implement Hidden Surface Removal (HSR). In order to implement HSR for a tile, the ISP block <b>108</b> processes the parameters indicated in the tile's display list to determine which primitives are visible and which are hidden at each fragment position within the tile. So that the ISP block <b>108</b> can process the parameters within a tile, the parameters included in the tile's display list are fetched from the parameter buffer <b>114</b> into the parameter cache <b>118</b>. The ISP block <b>108</b> then reads the parameters from the parameter cache <b>118</b> for use in processing the tile, e.g. for implementing the HSR. ISP block <b>108</b> can remove parameters which will not affect the rendered image before the TSP block <b>110</b> processes the tiles, or otherwise indicate which of the primitives are visible at which of the fragments for processing by TSP block <b>110</b>. ISP block <b>108</b> can operate in parallel on multiple fragments of a tile, on multiple tiles, or both.

0046Some implementations of ISP block <b>108</b> also may generate per-fragment parameter data for the parameters of each primitive; for example, per fragment texture references can be produced by ISP block <b>108</b>.

0047The TSP block <b>110</b> processes the tiles to apply texturing and shading to the objects that are present within the tile. An output from the ISP block <b>108</b> is provided to the TSP block <b>110</b> which indicates which of the parameters the TSP block <b>110</b> will need in order to process the tiles. So that the TSP block <b>110</b> can process the parameters within a tile, the parameters indicated in the output from the ISP block <b>108</b> can be fetched from the parameter buffer <b>114</b> into the parameter cache <b>120</b>. Some or all of the parameters used by the TSP block <b>110</b> for processing a tile may be different to those used by the ISP block <b>108</b> for processing the same tile. For example, the parameters used by the ISP block <b>108</b> may relate to the location of primitives, whereas the parameters used by the TSP block <b>110</b> may, additionally or alternatively, relate to texture and shading data to be applied to primitives. The TSP block <b>110</b> then reads the parameters from the parameter cache <b>120</b> for use in processing the tile, e.g. for implementing the texturing and shading. The parameters may include indications of textures (or specific texels from textures) that are to be applied to objects by the TSP block <b>110</b>. The indicated textures (or texels) are fetched from the texture memory <b>116</b> into the texture cache <b>122</b> for use by the TSP block <b>110</b> in processing the tile, e.g. for implementing the texturing and shading.

0048The output from the TSP block <b>110</b> may be passed to further processing blocks (not shown in <figref idref="DRAWINGS">FIG. 1</figref>) within the processing unit <b>102</b> before being output from the processing unit <b>102</b>, e.g. to a display buffer for display on a screen of the device on which the system <b>100</b> is implemented.

0049In the example shown in <figref idref="DRAWINGS">FIG. 1</figref>, the cache memories (<b>118</b>, <b>120</b> and <b>122</b>) are on-chip memories which are smaller than the corresponding parameter buffer <b>114</b> and texture memory <b>116</b> stored in the memory <b>112</b>, which may for example be a system memory. In other examples, at least one of the cache memories (<b>118</b>, <b>120</b> and/or <b>122</b>) may not be implemented as an on-chip memory, i.e. may not be implemented on the same chip as the processing unit <b>102</b>. The parameter caches <b>118</b> and <b>120</b> are usually smaller than that required to store all of the parameter blocks stored in the parameter buffer <b>114</b> that are needed in order to render all of the tiles in a scene (although the parameter caches <b>118</b> and <b>120</b> are usually large enough to store all of the parameters that are needed in order to render one of the tiles, but this may depend upon the quantity and complexity of the objects included in the tile). Similarly, the texture cache <b>122</b> is usually smaller than that required to store all of the textures stored in the texture memory <b>116</b> that are needed in order to render all of the tiles in a scene. So that the ISP block <b>108</b> can process all of the tiles, at least some of the parameters in the parameter cache <b>118</b> are evicted as further parameters are fetched into the parameter cache <b>118</b> from the parameter buffer <b>114</b>. Similarly, at least some of the parameters in the parameter cache <b>120</b> and at least some of the texels in the texture cache <b>122</b> are evicted as further parameters/texels are fetched into the respective caches so that the TSP block <b>110</b> can process all of the tiles.

0050There are described herein eviction policies which may perform better than the LRU eviction policy described above. The performance of the eviction policies may be indicated by the proportion of cache read requests that result in cache hits, i.e. the hit ratio of the cache. The eviction policies are described in detail below with reference to the parameters in the parameter cache <b>118</b>, but the same principles can be applied to the parameters in the parameter cache <b>120</b> and to the texels in the texture cache <b>122</b>. Furthermore, the same principles of the eviction policies described herein can be applied to any suitable graphics data items which are stored in a cache for use in processing the tiles.

0051<figref idref="DRAWINGS">FIG. 2</figref> is a simplified representation of a rendering space <b>202</b> of a tile-based graphics system comprising twenty tiles, arranged in a 5×4 array. Within the rendering space <b>202</b> are shown two objects <b>204</b> and <b>206</b>. A first of the two objects comprises four primitives labelled <b>204</b>₁, <b>204</b>₂, <b>204</b>₃and <b>204</b>₄. It can be seen that the first object overlaps with six of the tiles of the rendering space <b>202</b>. These six tiles are in the middle of the 5×4 array of the rendering space <b>202</b> and are indicated as tiles A to F in <figref idref="DRAWINGS">FIG. 2</figref>. Where it is not explicitly stated, the term “overlap” used herein is to be understood to mean “at least partially overlap”. It can be understood from <figref idref="DRAWINGS">FIG. 2</figref> that the primitive <b>204</b>₁overlaps with three tiles (tiles A, D and E), the primitive <b>204</b>₂overlaps with four tiles (tiles A, B, D and E), the primitive <b>204</b>₃overlaps with two tiles (tiles B and E) and the primitive <b>204</b>₄overlaps with four tiles (tiles B, C, E and F). A second of the two objects comprises two primitives labelled <b>206</b>₁and <b>206</b>₂. It can be seen that the second object overlaps with just one of the tiles of the rendering space <b>202</b>. In particular, it can be understood from <figref idref="DRAWINGS">FIG. 2</figref> that both of the primitives <b>206</b>₁and <b>206</b>₂overlap with only one tile, that being tile A. There will usually be other objects in the scene, likely comprising more primitives than the objects shown in <figref idref="DRAWINGS">FIG. 2</figref>, but these are not shown in <figref idref="DRAWINGS">FIG. 2</figref> for clarity.

0052As described above, each object is stored in one or more parameter blocks in the parameter buffer <b>114</b>. Each of the parameter blocks includes parameters describing the primitives of at least one of the objects. <figref idref="DRAWINGS">FIG. 3<i>a </i></figref>is a simplified diagram of a first parameter block (“Parameter Block <b>1</b>”) which comprises parameters describing the primitives of the first object <b>204</b>. In particular, in the example shown in <figref idref="DRAWINGS">FIG. 3<i>a</i></figref>, parameter block <b>1</b> stores: the parameter, PB<b>1</b>₁, which describes the primitive <b>204</b>₁; the parameter, PB<b>1</b>₂, which describes the primitive <b>204</b>₂; the parameter, PB<b>1</b>₃, which describes the primitive <b>204</b>₃; and the parameter, PB<b>1</b>₄, which describes the primitive <b>204</b>₄.

0053Similarly, <figref idref="DRAWINGS">FIG. 3<i>b </i></figref>is a simplified diagram of a second parameter block (“Parameter Block <b>2</b>”) which comprises parameters describing the primitives of the second object <b>206</b>. In particular, in the example shown in <figref idref="DRAWINGS">FIG. 3<i>b</i></figref>, parameter block <b>2</b> stores: the parameter, PB<b>2</b>₁, which describes the primitive <b>206</b>₁; and the parameter, PB<b>2</b>₂, which describes the primitive <b>206</b>₂.

0054The precise form of the parameters stored in the parameter buffer <b>114</b> may vary and may be more complicated than that shown in <figref idref="DRAWINGS">FIGS. 3<i>a </i>and 3<i>b</i></figref>. For example, the parameter blocks may store vertex data for the different vertices within an object, whereby the parameters for a primitive include data of a group of the vertices (e.g. three vertices forming a triangle) to thereby describe the location of the primitive. In that case the parameter for a primitive is actually a group of parameters which may include data relating to a group of vertices. The parameter blocks may further store data other than the location data of the primitives (e.g. colour or texture data) as separate data items to the location data, such that the parameters for a primitive may include sets of location data combined with the other data for the primitive. It should therefore be appreciated that where <figref idref="DRAWINGS">FIGS. 3<i>a </i>and 3<i>b </i></figref>show a parameter (e.g. PB<b>1</b>₁) relating to a primitive, the parameter may in fact include multiple data items from the parameter block which can be combined to describe the primitive. Furthermore, as shown in <figref idref="DRAWINGS">FIGS. 3<i>a </i>and 3<i>b </i></figref>each of the parameter blocks includes a miscellaneous data field which comprises data relating to that parameter block. The data in the miscellaneous data field may include state data to indicate how the data in the parameter block should be interpreted.

0055<figref idref="DRAWINGS">FIG. 4</figref> shows a flow chart for a method of processing data in a tile-based graphics system, implementing a new eviction policy for evicting parameters from the parameter cache <b>118</b>.

0056In step S<b>402</b>, for each of the parameter blocks, a count is determined of the number of tiles that overlap with at least one parameter of the parameter block. These counts therefore provide an indication of the number of tiles with which the parameters of a parameter block are associated. In other words, the count for a parameter block indicates how many of the tiles will be processed using at least one parameter from the parameter block. For example, the count for the Parameter Block <b>1</b> will be six because, as shown in <figref idref="DRAWINGS">FIG. 2</figref>, six tiles (tiles A to F) overlap with at least one primitive described by the parameters of Parameter Block <b>1</b> (i.e. primitives <b>204</b>₁, <b>204</b>₂, <b>204</b>₃and <b>204</b>₄). Similarly, the count for the Parameter Block <b>2</b> will be one because, as shown in <figref idref="DRAWINGS">FIG. 2</figref>, only one tile (tile A) overlaps with at least one primitive described by the parameters of Parameter Block <b>2</b> (i.e. primitives <b>206</b>₁and <b>206</b>₂).

0057In one example, tiling unit <b>106</b> determines the counts for the parameter blocks in step S<b>402</b>. This may be performed as part of the tiling process in which the display lists are derived for the tiles. The display list for a tile indicates the parameters which are to be used to process the tile. Alternatively, in step S<b>402</b> the information in the display lists of the tiles may be used to determine, for each of the parameter blocks, the count of the number of tiles that overlap with at least one primitive described by the parameters of the parameter block. For each of the parameter blocks, the count that is determined in step S<b>402</b> is stored in the miscellaneous data field of that parameter block in the parameter buffer <b>110</b>. Two examples of how the counts may be determined from the tiling process are: (i) setting a flag corresponding to each tile position every time any primitive in a parameter block is found in that tile and then summing the number of flags at the end of the tiling process; or (ii) parsing the display lists for each tile and incrementing the parameter block counter whenever the parameter block is referenced.

0058In step S<b>404</b>, the ISP block <b>108</b> fetches parameters from the parameter buffer <b>114</b> into the parameter cache <b>118</b>, as described above. The parameters that are fetched into the parameter cache <b>118</b> are those that are indicated in the display list of a current tile as being needed to process the current tile that the ISP block <b>108</b> is processing. As described above, the display list provides references to the parameter blocks in the parameter buffer <b>114</b> with masks to indicate the subset of parameters which are needed from the parameter blocks.

0059For example, <figref idref="DRAWINGS">FIG. 5</figref> shows parameters which are fetched into the parameter cache <b>118</b> by the ISP block <b>108</b> in order to process tile A shown in <figref idref="DRAWINGS">FIG. 2</figref>. Tile A overlaps with primitives <b>204</b>₁and <b>204</b>₂which are described by parameters PB<b>1</b>₁and PB<b>1</b>₂of Parameter Block <b>1</b> stored in the parameter buffer <b>114</b>. Tile A also overlaps with primitives <b>206</b>₁and <b>206</b>₂which are described by parameters PB<b>2</b>₁and PB<b>2</b>₂of Parameter Block <b>2</b> stored in the parameter buffer <b>114</b>. Therefore, in order for the ISP block <b>108</b> to process tile A, these four parameters (PB<b>1</b>₁, PB<b>1</b>₂, PB<b>2</b>₁and PB<b>2</b>₂) are fetched from the parameter buffer <b>114</b> into the parameter cache <b>118</b> in step S<b>404</b>. The parameter cache <b>118</b> may include other parameters than those shown in <figref idref="DRAWINGS">FIG. 5</figref>. For example, the parameter cache <b>118</b> may include parameters that have been previously fetched for the processing of previous tiles by the ISP block <b>108</b>.

0060When a parameter is fetched into the parameter cache <b>118</b>, an indication of the count for the parameter's parameter block is also stored in the parameter cache <b>118</b>. This is shown in <figref idref="DRAWINGS">FIG. 5</figref> whereby the counts for the parameters in the parameter cache <b>118</b> are stored. As described above, the counts for the parameters PB<b>1</b>₁and PB<b>1</b>₂from Parameter Block <b>1</b> are six and the counts for the parameters PB<b>2</b>₁and PB<b>2</b>₂from Parameter Block <b>2</b> are one.

0061In step S<b>406</b> the ISP block <b>108</b> reads the parameters from the parameter cache <b>118</b> that are indicated in the display list for tile A.

0062In step S<b>408</b> the ISP block <b>108</b> processes tile A using the parameters indicated in the display list for tile A. Therefore, in the example shown in <figref idref="DRAWINGS">FIG. 2</figref>, the parameters PB<b>1</b>₁, PB<b>1</b>₂, PB<b>2</b>₁and PB<b>2</b>₂will be used by the ISP block <b>108</b> to process tile A. As described above the ISP block <b>108</b> may implement Hidden Surface Removal (HSR) by determining which of the primitives are visible at each fragment position and then removing parameters from the image which will not affect the rendered image. The tiles processed by the ISP block <b>108</b> are output for further processing in the processing unit <b>102</b>, e.g. by the TSP block <b>110</b>. Different tiles from the same rendering space may be processed in parallel (i.e. simultaneously) in different processing blocks (e.g. the ISP block <b>108</b> and the TSP block <b>110</b>) in the processing unit <b>102</b>.

0063When the ISP block <b>108</b> has processed tile A, then in step S<b>410</b> the counts for the parameter blocks which have at least one parameter describing a primitive which overlaps with tile A may be decremented. Therefore, once the ISP block <b>108</b> has processed tile A, the count for Parameter Block <b>1</b> (stored in the miscellaneous data field of Parameter Block <b>1</b>) is decremented from six to five and the count for Parameter Block <b>2</b> (stored in the miscellaneous data field of Parameter Block <b>2</b>) is decremented from one to zero. Furthermore, the counts are also decremented for any of the parameters in the parameter cache <b>118</b> which are included in parameter blocks whose count is decremented. Therefore, when the ISP block <b>108</b> has processed tile A, the counts stored in the parameter cache <b>118</b> for the parameters from Parameter Blocks <b>1</b> and <b>2</b> will be decremented such that the count for parameters PB<b>1</b>₁and PB<b>1</b>₂in the parameter cache <b>118</b> will be decremented from six to five and the counts for the parameters PB<b>2</b>₁and PB<b>2</b>₂in the parameter cache <b>118</b> will be decremented from one to zero. Decrementing is an example and any self-consistent approach to setting an initial value and updating that value is acceptable.

0064Therefore, the counts for parameters of a parameter block are indicative of the number of tiles, that are still to be processed, that overlap with at least one parameter of the parameter block.

0065In step S<b>412</b> it is determined (e.g. by the ISP block <b>108</b>) whether there is another tile for the ISP block <b>108</b> to process. If there is not another tile for the ISP block <b>108</b> to process then the ISP block <b>108</b> has finished processing the tiles in the rendering space as indicated by reference S<b>414</b> in <figref idref="DRAWINGS">FIG. 4</figref>. In this case the processing of the tiles will continue in subsequent processing blocks (e.g. the TSP block <b>110</b>) in the processing unit <b>102</b>.

0066However, if the ISP block <b>108</b> does have another tile to process then the method passes from step S<b>412</b> to step S<b>416</b>. For example, when the ISP block <b>108</b> has processed tile A, it may then determine that tile B is to be processed. The ISP block <b>108</b> needs to read some parameters in order to process the next tile (e.g. tile B). The ISP block <b>108</b> will attempt to read the parameters from the parameter cache <b>118</b>. In step S<b>416</b> it is determined (e.g. by control logic of the parameter cache <b>118</b>) whether the parameter cache <b>118</b> has the parameters that are needed for the ISP block <b>108</b> to process the next tile. That is, it is determined whether any further parameters are needed to be fetched into the parameter cache <b>118</b> for the ISP block <b>108</b> to process the next tile.

0067If it is determined in step S<b>416</b> that the parameter cache <b>118</b> has all of the parameters required to process the next tile (i.e. that no further parameters are required to be fetched from the parameter buffer <b>114</b> into the parameter cache <b>118</b>) then the method passes from step S<b>416</b> back to step S<b>406</b>, wherein the ISP block <b>108</b> reads the appropriate parameters from the parameter cache <b>118</b> and in step S<b>408</b> processes the next tile, in a similar manner to that described above in relation to tile A.

0068However, if it is determined that further parameters are needed in the parameter cache <b>118</b> in order for the ISP block <b>108</b> to process the next tile (e.g. tile B) then the method passes from step S<b>416</b> to step S<b>418</b>. In the example that the next tile to be processed by the ISP block <b>108</b> is tile B then, as can be appreciated from <figref idref="DRAWINGS">FIG. 2</figref>, the ISP block <b>108</b> will need to use parameters PB<b>1</b>₂, PB<b>1</b>₃and PB<b>1</b>₄to process the tile. Parameter PB<b>1</b>₂is already in the parameter cache <b>118</b> due to the processing of tile A, but parameters PB<b>1</b>₃and PB<b>1</b>₄are further parameters which are not in the parameter cache <b>118</b> and will need to be fetched from the parameter buffer <b>114</b>. In step S<b>418</b> it is determined (e.g. by control logic of the parameter cache <b>118</b>) whether there is sufficient space in the parameter cache <b>118</b> to store the further parameters. If it is determined that there is sufficient space in the parameter cache <b>118</b> to store the further parameters then the method passes back to step S<b>404</b> and the further parameters are fetched from the parameter buffer <b>114</b> into the parameter cache <b>118</b>. The further parameters are then read by the ISP block <b>108</b> from the parameter buffer <b>118</b> in step S<b>406</b> and the next tile (e.g. tile B) is processed in step S<b>408</b>, in a similar manner to that described above in relation to tile A.

0069However, if it is determined in step S<b>418</b> that there is not sufficient space in the parameter cache <b>118</b> to store the further parameters (e.g. parameters PB<b>1</b>₃and PB<b>1</b>₄for processing tile B) then one or more of the parameters that are present in the parameter cache <b>118</b> will need to be evicted from the parameter cache <b>118</b> when the further parameters are fetched into the parameter cache <b>118</b>. In this case, the method passes to step S<b>420</b> in which it is determined (e.g. by control logic of the parameter cache <b>118</b>) which of the parameters should be evicted from the parameter cache <b>118</b>. The determination as to which of the parameters to evict from the parameter cache <b>118</b> is based on the counts of the parameters in the parameter cache <b>118</b>. For example, it may be determined that the parameter(s) with the lowest count(s) in the parameter cache <b>118</b> are to be evicted from the parameter cache <b>118</b>.

0070As described above the counts for parameters of a parameter block are indicative of the number of tiles that overlap with at least one primitive described by parameters of the parameter block. Furthermore, due to the decrementing of the counts as the tiles are processed, the counts for parameters of a parameter block are indicative of the number of tiles, that are still to be processed, that overlap with at least one primitive described by parameters of the parameter block. Therefore the count of a parameter in the parameter cache <b>118</b> provides an indication of the likelihood of that parameter being used in the next tile that is processed. Therefore, evicting the parameter(s) with the lowest count(s) is a useful eviction policy because parameters in the parameter cache <b>118</b> which are less likely to be used for processing the next tile (i.e. parameters which have lower counts) are evicted before parameters in the parameter cache <b>118</b> which are more likely to be used for processing the next tile (i.e. parameters which have higher counts).

0071In step S<b>422</b> the parameters which were determined in step S<b>420</b> to be suitable for eviction from the parameter cache <b>118</b> (e.g. those in the parameter cache <b>118</b> which have the lowest counts) are evicted from the parameter cache <b>118</b>. The method then passes back to step S<b>404</b> and the further parameters are fetched from the parameter buffer <b>114</b> into the parameter cache <b>118</b>. The eviction in step S<b>420</b> may be performed by fetching new parameters to replace the evicted parameters. Alternatively, an active eviction step may be carried out whereby parameters are evicted (e.g. by setting a flag to be “invalid” for the relevant cache line in the parameter cache <b>118</b>) before the step of fetching new parameters to replace the evicted parameters. The further parameters are then read by the ISP block <b>108</b> from the parameter buffer <b>118</b> in step S<b>406</b> and the next tile (e.g. tile B) is processed in step S<b>408</b>, in a similar manner to that described above in relation to tile A.

0072In the example shown in <figref idref="DRAWINGS">FIGS. 2 and 5</figref>, when tile A has been processed the parameters PB<b>1</b>₁, PB<b>1</b>₂, PB<b>2</b>₁and PB<b>2</b>₂are in the parameter cache <b>118</b>. The counts of PB<b>2</b>₁and PB<b>2</b>₂are lower than the counts of PB<b>1</b>₁and PB<b>1</b>₂, so the parameters PB<b>2</b>₁and PB<b>2</b>₂are evicted from the parameter cache <b>118</b>. This makes space in the parameter cache <b>118</b> for further parameters. If tile B is the next tile to be processed then the parameters PB<b>1</b>₃and PB<b>1</b>₄are fetched into the parameter cache <b>118</b> from the parameter buffer <b>114</b>, such that the parameter cache <b>118</b> will include the four parameters PB<b>1</b>₁, PB<b>1</b>₂, PB<b>1</b>₃and PB<b>1</b>₄from parameter block <b>1</b>. It can be seen from <figref idref="DRAWINGS">FIG. 2</figref> that parameters PB<b>1</b>₂, PB<b>1</b>₃and PB<b>1</b>₄are needed by the ISP block <b>108</b> to process tile B. It was a good decision to evict parameters PB<b>2</b>₁and PB<b>2</b>₂from the parameter cache <b>118</b> because those parameters are not needed to process tile B. It was also a good decision not to evict parameter PB<b>1</b>₂from the parameter cache <b>118</b> because that parameter is needed to process tile B.

0073The eviction policies based on the counts of the parameters as described herein may perform better than a LRU eviction policy in the example shown in <figref idref="DRAWINGS">FIGS. 2 and 5</figref>. If the parameters are used by the ISP block <b>108</b> to process tile A in the order that they are shown in <figref idref="DRAWINGS">FIG. 5</figref> in the parameter cache <b>118</b>, then using a LRU eviction policy may result in parameters PB<b>1</b>₁and PB<b>1</b>₂being evicted from the parameter cache <b>118</b> when tile A has been processed whereas parameters PB<b>2</b>₁and PB<b>2</b>₂may not be evicted from the cache <b>118</b> at that point. It can be appreciated from <figref idref="DRAWINGS">FIG. 2</figref> that parameters PB<b>2</b>₁and PB<b>2</b>₂(describing primitives <b>206</b>₁and <b>206</b>₂) will not be needed again to process any tile other than tile A and therefore it is not useful to keep these parameters in the parameter cache <b>118</b>. In contrast, parameters PB<b>1</b>₁, PB<b>1</b>₂, PB<b>1</b>₃and PB<b>1</b>₄(describing primitives <b>204</b>₁, <b>204</b>₂, <b>204</b>₃and <b>204</b>₄) will be needed again to process other tiles and therefore it may be useful to keep these parameters in the parameter cache <b>118</b>. Eviction policies described herein weight the eviction of parameters from the parameter cache <b>118</b> based on tile coverage. As can be seen in the examples given above, these eviction policies may result in a higher cache hit rate compared to a LRU eviction policy. This means that fewer calls to the parameter buffer <b>114</b> in memory <b>112</b> are needed to fetch parameters into the parameter cache <b>118</b>. Accessing memory <b>112</b> may be a slow process compared to other processes carried out by the processing unit <b>102</b> so reducing the number of memory accesses allows for faster processing by the processing unit <b>102</b>.

0074The example of Parameter Block <b>2</b> given above is a good example of where the eviction policies described herein perform better than a LRU eviction policy. Every member primitive of Parameter Block <b>2</b> is entirely located within one tile (tile A). Once that tile has been processed there is no reason to keep the parameters PB<b>2</b>₁and PB<b>2</b>₂of Parameter Block <b>2</b> in the parameter cache <b>118</b>. Under an LRU policy however the parameters of Parameter Block <b>2</b> will typically reside in the parameter cache <b>118</b> for a prolonged period, reducing the efficiency of the parameter cache <b>118</b>. As scene complexity increases, geometry gets smaller and the situation in which every member primitive of a parameter block is entirely located within one tile becomes increasingly common.

0075Eviction policies described herein consider how many tiles a parameter block overlaps with. Parameters from a parameter block containing primitives which overlap with only one or a small number of tiles are less likely to be required again to process another tile than parameters from a parameter block which contains primitives that overlap with many tiles. This realisation leads to the eviction policies which weight the eviction of parameters of parameter blocks from the parameter cache <b>118</b> based on tile coverage.

0076As described above, a count is maintained for each of the parameter blocks of the number of tiles overlapped by the primitives in that parameter block. When an eviction from the parameter cache is required, a parameter from the parameter block with the lowest counter is chosen for eviction. If multiple parameters are present in the parameter cache <b>118</b> with the same count value, then a conventional eviction policy (such as LRU) may be used to determine which of those parameters is to be evicted. Due to the locality of the input data, parameters (e.g. defining objects) found in one tile are likely to be used again in an adjacent tile, such that when tiles are processed in sequential order, the LRU eviction policy is a good default choice for determining which parameters to evict from the parameter cache in the event that multiple parameters are present in the parameter cache <b>118</b> with the same count value.

0077In the examples described above, the count is decremented for a parameter of a parameter block if any of the parameters within that parameter block are used to process a tile. Therefore, the counts for parameters in the parameter cache <b>118</b> may reach zero, which indicates that those parameters will not be used again to process further tiles in the rendering space <b>202</b>. As such those parameters will not be needed in the parameter cache <b>118</b>. Therefore if the count for a parameter in the parameter cache <b>118</b> reaches zero then that parameter may be evicted from the parameter cache <b>118</b>. Evicting parameters with count values of zero helps to maximise the parameter cache usage, thereby reducing the number of calls to the memory <b>112</b> that are needed.

0078As described above, the number of tiles overlapped by primitives in a parameter block can be determined in several ways known to those skilled in the art. For example, a list of the overlapping tiles may be stored in the parameter block during the tiling of the primitives by the tiling unit <b>106</b>.

0079In another example, as illustrated in <figref idref="DRAWINGS">FIG. 6</figref>, a conservative bounding box <b>606</b> may be constructed in a rendering space <b>602</b> for a parameter block. In the simple example shown in <figref idref="DRAWINGS">FIG. 6</figref>, parameters of three primitives <b>604</b>₁, <b>604</b>₂and <b>604</b>₃are included in a parameter block, and the bounding box <b>606</b> is the smallest rectangular array of tiles (labelled G to P in <figref idref="DRAWINGS">FIG. 6</figref>) which comprises all of the tiles which overlap with at least one of the primitives of the parameter block. As illustrated in <figref idref="DRAWINGS">FIG. 6</figref>, primitive <b>604</b>₁overlaps tiles L and M; primitive <b>604</b>₂overlaps tile M; and primitive <b>604</b>₃overlaps tiles I, J, K, M, N and O. The number of tiles included in the bounding box <b>606</b> can be used as the count for the parameters of the parameter block. It can readily be seen that none of the primitives shown in <figref idref="DRAWINGS">FIG. 6</figref> overlap tiles G, H or P, but that tiles G, H and P are included in the bounding box <b>606</b>. Therefore, if the bounding box method is used to determine the counts for the parameters in the parameter block shown in <figref idref="DRAWINGS">FIG. 6</figref> then the counts will be determined to be ten even though only seven of the tiles (tiles I, J, K, L, M, N and O) actually overlap with at least one of the primitives of the parameter block. The count for a parameter of a parameter block is therefore not necessarily strictly equal to the number of tiles that overlap at least one primitive described by parameters of the parameter block.

0080In the examples given herein, rectangular bounding boxes are used which are simple to implement and well matched to rectangular tiles. However, a rectangular bounding box is just one example of a bounding region which may be used. Other bounding regions may be used. For example, tighter bounds such as spheres and polynomials may be used in a similar manner as that described herein for the rectangular bounding boxes. Methods also exist for optimizing the rectangular bounding box. In the example of <figref idref="DRAWINGS">FIG. 6</figref>, such a method may exclude non-overlapped tiles G, H, and P to produce the minimal set of seven tiles overlapped by the primitives of the parameter block for use as the bounding region.

0081In general, the count for a parameter can be considered to be an indicator of the number of tiles with which the parameter is associated. Any suitable indicator may be used. The count is used as a weighting to be used to determine which parameters are to be evicted from the parameter cache <b>118</b>. As such, the count is not required to be exactly correct in specifying the number of tiles with which a parameter is associated, provided that it gives an approximate indication of the number of tiles with which a parameter is associated. In this way, the counts allow the number of tiles with which a first parameter is associated to be compared (approximately, even if not exactly) to the number of tiles with which a second parameter is associated to determine which of the parameters is associated is fewer tiles, and is therefore a suitable candidate for eviction from the parameter cache <b>118</b>. A particular parameter may be considered to be associated with a particular tile if a parameter in the parameter block comprising the particular parameter is to be used to process the particular tile (i.e. one of the primitives of the parameter block overlaps the particular tile). When the bounding box method is used, a particular parameter may be considered to be associated with a particular tile if the bounding box including the particular parameter overlaps the particular tile.

0082In the examples described above, each parameter block has its own count. However, in other examples, the granularity of the counts may be different. For example, each parameter may have its own count, which may be different to the counts of other parameters of the same parameter block, and which is indicative of the number of tiles associated with that parameter, e.g. the number of tiles which are to be processed using the parameter. Determining the number of tiles associated with a parameter may include using the display lists generated by the tiling unit <b>106</b> during tiling of the primitives in the scene. Alternatively, each parameter may have its own conservative bounding box which is used to determine the number of tiles associated with that parameter. As another example, each block of data (e.g. comprising multiple parameters) that can be loaded into a cache line of the parameter cache <b>118</b> may have its own count, which is indicative of the number of tiles which are to be processed using at least one parameter in the block of data. In all of these examples, irrespective of the granularity of the counts, a count is determined for each of the parameters. For example, when the counts are at the granularity of the parameter blocks, the step of determining a count for a parameter block will determine the counts for each of the parameters of that parameter block, i.e. each of the parameters in the parameter block have a count equal to that which has been determined for the parameter block.

0083When a tile is processed and the counts are decremented, it should be the case that the count for every parameter that is associated with the processed tile is decremented. The determination as to which of the parameters are associated with a processed tile for the purpose of decrementing the counts should match the determination as to the number of tiles with which the parameters are associated when determining the counts. For example, if the bounding box method is used to determine the counts (e.g. such that all of the parameters shown in <figref idref="DRAWINGS">FIG. 6</figref> are determined to be associated with all ten of the tiles G to P, thereby setting the counts for the parameters to be ten) then when any of the tiles in the bounding box is processed the counts for the parameters within the bounding box should be decremented. This is true even for processing tiles in the bounding box which do not overlap with any of the primitives in the parameter block, e.g. for processing tiles G, H and P.

0084In the examples given above, the counts for parameters are decremented as tiles associated with the parameters are processed. However, in other examples, the counts are not decremented, i.e. step S<b>410</b> is omitted from the method in the examples described with reference to <figref idref="DRAWINGS">FIG. 4</figref>. In examples in which the counts are not decremented the counts for parameters of a parameter block are indicative of the number of tiles in the rendering space <b>202</b> that overlap with at least one parameter of the parameter block, irrespective of whether the tiles have already been processed. An eviction policy such as this, in which the counts are not decremented, may still perform better than a LRU eviction policy (in terms of a cache hit ratio), although it may not perform as well as the eviction policies described herein which do implement the decrementing counters (in terms of a cache hit ratio). However, the cost of including the processing required to implement the decrementing counters may, in some scenarios, outweigh the benefits obtained by decrementing counters, such that in some scenarios implementing an eviction policy which does not decrement the counters may be beneficial.

0085In the examples above, it is not described that there is an upper limit to the values of the counts. However, in practical systems, it is likely that the number of bits allocated to be used for the counts is limited. For example, N bits could be used to represent each of the counts, with the possible values of the counts, denoted C, being an integer in the range: 0≤C≤2^N−1. Therefore there is a predetermined maximum value that the count can take, C_max, which is given by 2^N−1. For example, three bits may be used to represent each of the counts, such that the value of C_maxis 7. Therefore, in this example, the values of the counts, C, can be in the range: 0≤C≤7. It is useful to limit the number of bits used to represent each of the counts so that the amount of memory used to store the counts is limited. This is particularly true when the counts are stored in two places, e.g. in the miscellaneous field in a parameter block in the parameter buffer <b>114</b> and in the parameter cache <b>118</b> as shown in <figref idref="DRAWINGS">FIG. 5</figref>. The memory of the parameter cache <b>118</b> is in high demand, so placing a limit on the number of bits that are used for the counts may be useful because the counts are stored in the parameter cache <b>118</b>.

0086When the number of tiles with which a parameter is associated is determined, as described above, if the number of tiles with which a parameter is associated is greater than the predetermined maximum (C_max), then the value of the count is set to be equal to the predetermined maximum (C_max). In other words, if the value of the count for a parameter is set at C_maxthis indicates that the number of tiles with which that parameter is associated is greater than or equal to C_max. When there is a limit to the value of the count, then for all count values less than the maximum (i.e. for C&lt;C_max) then the count values may be decremented in the same way as described above as the tiles are processed. However, when the count value is set to the maximum value (i.e. for C=C_max) then the count values are not decremented as the tiles are processed. In other words, the count value is decremented only if the count is less than the predetermined maximum (C_max). This is because a count value of C_maxfor a parameter does not uniquely indicate the number of tiles associated with that parameter. A count value of C_maxindicates that the number of tiles associated with that parameter is greater than or equal to C_max. Therefore, decrementing the count value may not be useful when the count value is set to be C_max.

0087However, in some examples a count value of C_maxmay be decremented. This may be beneficial by reducing the likelihood of parameters with count values of C_maxfrom remaining in the parameter cache <b>118</b> after they are needed by the ISP block <b>108</b> for processing tiles. In some examples, where the count value for a parameter is stored in the parameter cache <b>118</b> and in the parameter buffer <b>114</b>, as in examples described above, a count value of a parameter of C_maxin the parameter cache <b>118</b> may be decremented but the corresponding count value of the parameter (e.g. of the parameter block) in the parameter buffer <b>114</b> may not be decremented. In this way, the parameter may be evicted from the parameter cache <b>118</b> as the count value is decremented, but if the parameter is subsequently re-loaded into the parameter cache <b>118</b> it will be re-loaded with a count value of C_max. In some other examples, a decision may be made as to whether to decrement the count value of a parameter with a count value of C_max, based on a condition, such as the occupancy of the parameter cache <b>118</b>, or the number of other parameters in the parameter cache <b>118</b> which have count values of C_max.

0088It is described above that the count value, denoted C, is an integer in the range: 0≤C≤2^N−1. However, the count values may instead be in the range 1≤C≤2^N, thereby allowing an extra count value to be represented, at the expense of not being able to represent a count value of zero. However, it may not be necessary to be able to represent a count value of zero. For example, rather than decrementing a count value of one to a count value of zero, the count value may remain at one and the cache entry corresponding to the parameter may be invalidated. A cache entry may be invalidated by setting a flag in the parameter cache <b>118</b> to indicate that the parameter is invalid. Alternatively, a cache entry may be invalidated by setting a tag or address to a predefined value, e.g. all bits set to zero or all bits set to one. It is known to invalidate cache entries in caches to indicate data in a cache that can be overwritten when new data is fetched into the cache. Therefore, the count value of zero is not needed and the maximum count value (C_max) that can be represented can be increased by one without increasing the number of bits used to represent the count values. It is noted that an “invalid” state (indicated for example with an “invalid flag” or by setting a tag or address to a predefined value, e.g. all bits set to zero or all bits set to one) is implemented in most caches to indicate whether lines of the cache are empty or whether they hold genuine data. Therefore, the process of invalidating a cache entry (e.g. by setting an invalid flag, or by setting a tag or address to a predefined value), as described above to extend the range of count values that can be represented, may not involve using any extra bits that would not already be used by the cache. This is because the cache may already implement a method for invalidating cache entries (e.g. using an “invalid flag” or setting a tag or address to a predefined value, e.g. all bits set to zero or all bits set to one).

0089In one example use case, just one bit is used to represent each of the counts. In relation to the example given above, this can be thought of as setting N to be one, such that 1≤C≤C_max, where C_maxis equal to two. The count in this example is therefore a one-bit flag, which can take either a first value or a second value. The value of the count for a parameter can therefore be used to indicate one of two conditions. If the count for a parameter has the first value (which is denoted C₁herein) this indicates that the number of tiles with which that parameter is associated is equal to one. If the count has the second value (which is denoted C_>1herein) this indicates that the number of tiles with which that parameter is associated is greater than one.

0090This use case has some particular benefits. Since only one bit is used for the count values, the data required to store the counts and transmit the counts between the processing unit <b>102</b> and the system memory <b>112</b> is small compared to examples where more than one bit is used for the count values. Furthermore, it has been observed that parameter blocks may have parameters which are associated with only one tile. Furthermore, as scene complexity increases, geometry gets smaller and it gets more likely that a parameter block for a piece of geometry (e.g. an object) has parameters which are associated with only one tile.

0091In an example in which just one bit is used for the counts, the count values are not decremented as the tiles are processed. Instead, the eviction policy condenses down to determining which of the parameters in the parameter cache have counts which have the first value C₁indicating that the parameters are only present in one tile, whereby these parameters are good candidates for eviction from the parameter cache <b>118</b>. Parameters which have counts having the value C_>1are not good candidates for eviction from the parameter cache <b>118</b> and are weighted to reduce the likelihood of eviction from the parameter cache <b>118</b> relative to the likelihood of parameters with counts of C₁being evicted from the parameter cache <b>118</b>. As described above, if we need to discriminate between parameters to determine which parameter to evict from the cache when the counts for the parameters have the same value, then another eviction policy such as a LRU eviction policy may be used. It should be appreciated that, any parameter in the parameter cache <b>118</b> which has been used to process a tile and which has a count value of C₁(indicating that the parameters are associated with only one tile) will not be used again to process another tile and therefore can be evicted from the parameter cache <b>118</b>.

0092In another example use case, two bits are used to represent each of the counts. The count in this example is therefore a two-bit flag, which can take one of four possible values. The value of the count for a parameter can therefore be used to indicate one of four conditions. If the count for a parameter has a first value (which is denoted C₁herein) this indicates that the number of tiles with which that parameter is associated is equal to one. If the count has a second value (which is denoted C₂herein) this indicates that the number of tiles with which that parameter is associated is equal to two. If the count has a third value (which is denoted C₃₄herein) this indicates that the number of tiles with which that parameter is associated is equal to three or four. If the count has a fourth value (which is denoted C_>4herein) this indicates that the number of tiles with which that parameter is associated is greater than four.

0093This use case is useful because while small objects may contain primitives that fit within a single tile it is common for those objects to be intersected by tile boundaries. The common case of small objects intersected by a single tile edge will result in parameter blocks located in only two tiles. Similarly, objects may be intersected by both the horizontal and vertical tile edges resulting in parameter blocks located in either three or four tiles. Therefore, it is not unusual for a parameter block relating to an object to have parameters which are associated with one, two, three or four tiles, and it may be useful to be able to distinguish between these situations when determining which parameters to evict from the parameter cache <b>118</b> as well as distinguishing these cases from parameter blocks which have parameters associated with more than four tiles. <figref idref="DRAWINGS">FIG. 7</figref> shows four tiles (denoted Q, R, S and T) of a rendering space <b>702</b>. Three objects (denoted <b>704</b>, <b>706</b> and <b>708</b>) are shown in the rendering space <b>702</b>. It can be seen that object <b>704</b> overlaps with just one of the tiles (tile Q); object <b>706</b> overlaps with two of the tiles (tiles R and T); and object <b>708</b> overlaps with all four of the tiles (tiles Q, R, S and T). The difference in the number of overlapping tiles of the objects is due to the difference in alignment of the objects to the tiling of the rendering space <b>702</b>. According to the example use case being described, the parameters in the parameter block for object <b>704</b> will have counts with the value C₁because object <b>704</b> overlaps only one tile; the parameters in the parameter block for object <b>706</b> will have counts with the value C₂because object <b>706</b> overlaps two tiles; and the parameters in the parameter block for object <b>708</b> will have counts with the value C₃₄because object <b>708</b> overlaps four tiles. The parameters in a parameter block for an object that covers more than four of the tiles are given count values of C_>4.

0094The parameters are evicted from the parameter cache <b>118</b> based on their count values. In particular, parameters with count values of C₁will be evicted from the parameter cache <b>118</b> preferentially ahead of parameters with count values of C₂which themselves will be evicted from the parameter cache <b>118</b> preferentially ahead of parameters with count values of C₃₄, which themselves will be evicted from the parameter cache <b>118</b> preferentially ahead of parameters with count values of C_>4. It can be appreciated that when tile Q has been processed the parameters relating to object <b>704</b> are not needed for processing any of the other tiles, and due to the count value of those parameters being C₁those parameters will be evicted from the parameter cache <b>118</b> ahead of the parameters relating to object <b>708</b> which have count values of C₃₄and which are needed for processing the other tiles (tiles R, S and T) shown in <figref idref="DRAWINGS">FIG. 7</figref>.

0095Using two bits for the count values is particularly useful because it distinguishes between four common scenarios, and therefore will provide a significant improvement in the cache hit ratio compared to a LRU eviction policy. Furthermore, this is achieved whilst requiring only 2 bits of data for each count value. This is advantageous in terms of storing the count values and transmitting the count values between the parameter buffer <b>114</b> on the memory <b>112</b> and the parameter cache <b>118</b> on the processing unit <b>102</b>.

0096When two bits are used for the counts, the count values of C₁, C₃₄and C_>4may not be decremented as the tiles are processed. The count value of C₁has no lower value to be decremented to. The count values of C₃₄and C_>4do not uniquely define the number of tiles that are associated with a parameter and as such are not decremented as the tiles are processed. However, a count value of C₂does indicate that a parameter is associated with two tiles and the count value of C₂may be decremented to the count value C₁. Therefore, the count value of a parameter with a count of C₂may, or may not, be decremented to be a count of C₁when a tile associated with that parameter is processed. In other examples, a count value of C_>4may be decremented to a count value of C₃₄. Furthermore, a count value of C₃₄may be decremented to a count value of C₂. As described above in relation to the decrementing of count values of C_max, the count values C₃₄and C_>4may be decremented in the parameter cache <b>118</b>, whist not being decremented in the parameter buffer <b>114</b>. Furthermore, rather than decrementing a count value of C₁, when a tile is processed with which a parameter is associated which has a count value of C₁, the count value of the parameter may remain as C₁but a cache invalid flag may be set for the parameter to indicate that the parameter may be overwritten in (i.e. evicted from) the parameter cache <b>118</b> when further parameters are fetched into the parameter cache <b>118</b>.

0097In the examples described above, the counts are stored in the parameter cache <b>118</b> and in the parameter buffer <b>114</b>. However, in other examples, the counts may be stored only in the parameter buffer <b>114</b> and for each of the parameters in the parameter cache <b>118</b> there is stored in the parameter cache <b>118</b> a reference for referencing the counts for the parameters from the parameter buffer <b>114</b>. In that case, when determining which of the parameters to evict from the parameter cache <b>118</b>, the references of the parameters in the parameter cache <b>118</b> are used to determine the counts for the parameters in the parameter cache <b>118</b> by referencing the counts stored in the parameter buffer <b>114</b>, and then the counts are used to determine which parameter to evict (e.g. the parameter(s) with the lowest count value(s)). This example may save some memory space in the parameter cache <b>118</b> because the count values are not needed to be stored in the parameter cache <b>118</b>. The references are stored in the parameter cache <b>118</b> which may use fewer bits of memory than storing the counts themselves in the parameter cache <b>118</b>. This may be useful because the memory space in the parameter cache <b>118</b> is limited. However, delay may be added to the processing of the tiles to allow time for the counts to be retrieved from the parameter buffer <b>114</b> in order to determine which parameters to evict from the parameter cache <b>118</b>.

0098The examples described above relate to the eviction of parameters from the parameter cache <b>118</b>. The same principles of the eviction policies can be applied to other caches in the processing unit <b>102</b>. That is, for any graphics data items which are used to process tiles and which are fetched from an graphics data memory in the memory <b>112</b> into a cache on the processing unit <b>102</b>, indicators may be determined for the graphics data items such that for each of the graphics data items, the indicator for that graphics data item is indicative of the number of tiles with which that graphics data item is associated. The indicators can then be used to determine which of the graphics data items to evict from the cache, such that the eviction policy is based on the tile coverage of the graphics data items. The graphics data items may for example be parameters or texels, which may be stored in graphics data sets such as parameter blocks or textures in the memory <b>112</b>.

0099For example, the parameter cache <b>120</b> which is used by the TSP block <b>110</b> may use an eviction policy corresponding to those described above in relation to the parameter cache <b>118</b> used by the ISP block <b>108</b>. That is, each of the parameters may be fetched into the parameter cache <b>120</b> with an associated count. The count used in the parameter cache <b>118</b> is separate to the count used in the parameter cache <b>120</b>. As described above, the counts used by the ISP block <b>108</b> (and stored in parameter cache <b>118</b>) are determined from the tiling performed by the tiling unit <b>106</b>. Those same count values may be used by the TSP block <b>110</b> (and stored in parameter cache <b>120</b>), or different counts may be used by the TSP block <b>110</b> (and stored in parameter cache <b>120</b>) which may, for example, be determined based on the results of the Hidden Surface Removal (HSR) performed by the ISP block <b>108</b> (e.g. such that the counts for the TSP block <b>110</b> may be lower than the counts for the ISP block <b>108</b>). Similar to in the examples described above in relation to the counts used by the ISP block <b>108</b>, in some examples, each parameter block has a separate count (for use by the TSP block <b>110</b>) of the number tiles with which at least one of the parameters of that parameter block is associated. The count for the TSP block <b>110</b> is used in the same way as described above in relation to the count for the ISP block <b>108</b>, in order to determine which parameters to evict from the parameter cache <b>120</b>, and may be decremented in the same way.

0100In the examples described above, there are two separate parameter caches: parameter cache <b>118</b> used by the ISP block <b>108</b> and parameter cache <b>120</b> used by the TSP block <b>110</b>. In other examples there may be a single (“unified”) parameter cache which could be used by both the ISP block <b>108</b> and the TSP block <b>110</b>. Even when a single cache is used, separate counts would be used for the ISP block <b>108</b> and the TSP block <b>110</b>. However, when a single parameter cache is used one of the processing blocks (ISP block <b>108</b> or TSP block <b>110</b>) may evict parameters required by the other one of the processing blocks (TSP block <b>110</b> or ISP block <b>108</b>) and vice versa. This would result in “thrashing” of the parameter cache. Therefore, using a single parameter cache for use by both the ISP block <b>108</b> and the TSP block <b>110</b> may reduce the effectiveness of the caching of the parameters in the processing unit <b>102</b>. However, it is possible that it could be beneficial to use a single parameter cache.

0101As another example, the texture cache <b>120</b> which is used by the TSP block <b>110</b> may use an eviction policy corresponding to those described above in relation to the parameter caches <b>118</b> and <b>120</b>. The texture memory <b>116</b> resides in the memory <b>112</b> and stores textures. Each texture includes one or more texels which can be applied to primitives of an object. The parameters of an object may indicate a portion of a texture which is to be applied to the primitives of the object when processing a tile in the TSP block <b>110</b>. When the TSP block <b>110</b> processes a tile, the appropriate texels from the indicated texture are fetched from the texture memory <b>116</b> into the texture cache <b>122</b>. In the same ways that counts can be determined for the parameters as described above, counts can be determined for the texels to indicate the number of tiles with which the texels are associated. For example, the counts may be determined on the granularity of the textures (in the same way that counts are determined on the granularity of the parameter blocks as described above), whereby each texel within a texture is given the same count value, which indicates the number of tiles with which texels from that texture are associated. When texels are required to be evicted from the texture cache <b>122</b>, the counts for the texels in the texture cache <b>122</b> can be used to determine which texels to evict from the texture cache <b>122</b>. That is, the eviction of texels from the texture cache <b>122</b> is weighted based on the number of tiles with which the texels are associated.

0102The order in which tiles within a rendering space are processed may be determined. Many factors may contribute to determining the order in which tiles are to be processed. For example, simple ordering schemes include raster scanning, where tiles are processed one row of tiles at a time, from top to bottom, and within each row of tiles the ordering is left to right. Other ordering schemes such as Boustrophedon ordering and Morton ordering are common. Processing of the tiles may be implemented in a multithreaded manner, and it may, or may not, be beneficial to group together the tiles that are to be processed in one thread. As another example, a load balancing technique may be used to determine the order in which tiles are processed, the details of such techniques are beyond the scope of this description.

0103The examples described above relate to implementing an eviction policy for evicting graphics data items (e.g. parameters or texels) from a cache. As part of the implementation of this eviction policy, indicators (or “counts”) are included in the cache for the graphics data items to indicate the number of tiles with which each of the graphics data items is associated. These indicators may be used in the determination of the order in which the tiles are to be processed. The influence of the indicators on the determination of the order in which the tiles are to be processed may be smaller than other factors which are considered in the determination, but with other factors being equal, the indicators in the cache may determine the order in which tiles are processed. It may be beneficial to process tiles which are to be processed using graphics data items which are already in the cache, rather than needing to fetch graphics data items into the cache. In examples in which the indicators are decrementing counts as described above then it may be beneficial to preferentially drive counts towards zero for graphics data items with relatively low count values such that they will be evicted from the cache (thereby freeing up space in the cache for other graphics data items), and will not be needed for processing other tiles. This can be done by choosing to process tiles which are associated with those graphics data items. The display lists for the tiles can be used to determine which of the tiles are associated with which of the graphics data items. It could be that in other scenarios, tiles are chosen to be processed to thereby reduce the counts of graphics data items with relatively high count values in the cache.

0104Generally, any of the functions, methods, techniques or components described above can be implemented hardware (e.g., fixed logic or function circuitry), hardware configured by firmware or software, or any combination of these implementations. in order to clarify aspects of the disclosure, descriptions of some portions systems that implement these aspects are grouped, and referred to as “modules”, “components”, “blocks” or “units” for performing one or more specified functions or sets of functions, where such functions may themselves have constituent functions or other operations. The implementation of such modules, components and units may vary and can include fixed logic or function circuitry), hardware configured by firmware or software, or any combination of these implementations. Similarly, a ‘processor’ or a ‘computer’ refers to any device, or portion thereof, that includes such modules, components, or units, or which can be configured to implement same.

0105For example, the term “unit” can describe a collection of circuits, such as one or more of fixed function circuits, and circuits formed by configuring a programmable processor, to perform a stated function or collection of functions that logically relate to each other. For example, a “tiling unit” describes circuitry that implements a tiling function, while an “image synthesis processing unit” describes circuitry for synthesizing image data, and which uses inputs from a “tiling unit”. The scope of these various terms depends on a context in which they are used. For example, some implementations may characterize vertex shading and viewpoint transformation as being implemented in a geometry processing unit or phase that precedes a tiling unit or phase, while other implementations may characterize these functions as being implemented in tiling unit and part of a tiling phase. As such, a processor may both include and be a tiling unit, an image synthesis processor, a texture and shading processor, and so on.

0106In the case of a software implementation, the module, functionality, component or logic represents program code that performs specified tasks when executed on a processor (e.g. one or more CPUs). In one example, the methods described may be performed by a computer configured with software in machine readable form stored on a computer-readable medium. One such configuration of a computer-readable medium is signal bearing medium and thus is configured to transmit the instructions (e.g. as a carrier wave) to the computing device, such as via a network. The computer-readable medium may also be configured as a computer-readable storage medium and thus is not a signal bearing medium. Examples of a non-transitory machine or computer readable storage medium include a random-access memory (RAM), read-only memory (ROM), an optical disc, flash memory, hard disk memory, and other memory devices that may use magnetic, optical, and other techniques to store instructions or other data and that can be accessed by a machine.

0107The software may be in the form of a computer program comprising computer program code for configuring a computer to perform the constituent portions of described methods or in the form of a computer program comprising computer program code means adapted to perform all the steps of any of the methods described herein when the program is run on a computer and where the computer program may be embodied on a computer readable medium. The program code can be stored in one or more computer readable media. The features of the techniques described herein are platform-independent, meaning that the techniques may be implemented on a variety of computing platforms having a variety of processors.

0108Those skilled in the art will also realize that all, or a portion of the functionality, techniques or methods may be carried out by a dedicated circuit, an application-specific integrated circuit, a programmable logic array, a field-programmable gate array, or the like. For example, the module, functionality, component or logic may comprise hardware in the form of circuitry. Such circuitry may include transistors and/or other hardware elements available in a manufacturing process. Such transistors and/or other elements may be used to form circuitry or structures that implement and/or contain memory, such as registers, flip flops, or latches, logical operators, such as Boolean operations, mathematical operators, such as adders, multipliers, or shifters, and interconnects, by way of example. Such elements may be provided as custom circuits or standard cell libraries, macros, or at other levels of abstraction. Such elements may be interconnected in a specific arrangement. The module, functionality, component or logic may include circuitry that is fixed function and circuitry that can be programmed to perform a function or functions; such programming may be provided from a firmware or software update or control mechanism. In an example, hardware logic has circuitry that implements a fixed function operation, state machine or process.

0109It is also intended to encompass software which “describes” or defines the configuration of hardware that implements a module, functionality, component or logic described above, such as HDL (hardware description language) software, as is used for designing integrated circuits, or for configuring programmable chips, to carry out desired functions. That is, there may be provided a computer readable storage medium having encoded thereon computer readable program code for generating a processing unit configured to perform any of the methods described herein, or for generating a processing unit comprising any apparatus described herein.

0110Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims. It will be understood that the benefits and advantages described above may relate to one example or may relate to several examples.

0111Any range or value given herein may be extended or altered without losing the effect sought, as will be apparent to the skilled person. The steps of the methods described herein may be carried out in any suitable order, or simultaneously where appropriate. Aspects of any of the examples described above may be combined with aspects of any of the other examples described to form further examples without losing the effect sought.