Electrical computers and digital processing systems: memory – Address formation – Combining two or more values to create address
Reexamination Certificate
1998-03-23
2001-02-27
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Address formation
Combining two or more values to create address
C711S217000, C711S218000, C711S219000
Reexamination Certificate
active
06195737
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to a system for non-linear memory access and in particular for accessing data stored in tiled, or block, formats.
BACKGROUND OF THE INVENTION
Many computer and data base applications involve data having a multi-dimensional nature. For example, data in a spreadsheet is referenced with regard to the particular row and column in which the data appears. The same is applicable to video image data, physical object data, and hierarchical data base elements. Video image data is referenced with regard to the particular x and y coordinate location at which the image data is displayed. Physical object data is referenced with regard to x, y, z coordinates, often termed the real-world coordinates of the object. Hierarchical data base elements are referenced by their path in a multidimensional tree structure. Traditionally, the coordinates associated with the representation of the data are termed object coordinates, or virtual coordinates.
Conventional memory devices are structured with a unidimensional addressing scheme. That is, each data element within the memory is referenced by a unique, single dimensioned, address. Storing multi-dimensional data in a unidimensional memory requires a mapping from each multidimensional object coordinate to a corresponding unidimensional memory address. One such mapping of a multidimensional representation to a unidimensional address is a linear mapping, as shown in FIG.
1
. The object space
100
comprises data elements, or picture elements (pixels), arranged in a two-dimensional address space. Each pixel is represented by its location in these two dimensions, as shown by P(
0
,
0
), P(
1
,
0
), etc. in FIG.
1
. In the linear mapping shown in
FIG. 1
, each of the pixels in the first row, or line, of pixels is stored sequentially in the memory
110
. The pixels of the second line, P(
0
,
1
), P(
1
,
1
), etc. are stored sequentially after the first line of pixels. In a linear mapping, a linear equation is applied to compute the memory address corresponding to each object coordinate. For example, in the mapping shown in
FIG. 1
, the memory address, A, is equal to x+1024*y, where x is the first pixel coordinate, and y is the second pixel coordinate. In a three dimensional, (x, y, z), system, the memory address is computed as A=z*K
2
+y*K
1
+x, where K
1
is the range of x, and K
2
is the product of the range of x times the range of y.
When a linear mapping scheme is utilized, the address corresponding to an object coordinate can be calculated relative to a previously computed address. For example, in the mapping of
FIG. 1
, where A=x+1024*y, the address of a pixel to the right of another is offset by 1 from the address of the other; the address of a pixel below another is offset by 1024 from the address of the other. Utilizing this linear address relationship, memory access techniques can be optimized to process this data. For example, to process pixels lying along a vertical line, each entity can be accessed by adding 1024 to the prior address, rather than computing the address of each entity directly, using the x+1024*y formula. In this manner, a single addition (+1024) is used to compute the next address, rather than a multiplication (1024* y) and an addition (+x). In a similar manner, data at any periodic interval can be quickly accessed.
Although the linear addressing scheme offers considerable computational advantages for determining a coordinate's associated memory address, it does have disadvantages. In a linear mapping scheme, there is a fixed “distance” in memory
110
between data elements that are “adjacent” to each other in the object space
100
. That is, for example, each pixel separated by one line in the object space
100
is separated by M locations in the memory
110
, where M is the length of the line. In
FIG. 1
, P(
0
,
1
) is at memory address 1024, whereas it's vertically adjacent element P(
0
,
0
) is at memory address
0
, a separation of 1024 locations in memory. In the three-dimensional case discussed above, a distance of K
2
separates data elements in adjacent z coordinates in memory. In many systems, the “cost”, in terms of access time or access difficulty, is directly related to the distance between data items in memory. Often, a “block” of memory is accessed in a single memory access operation. If the “successive” data element, in the object coordinate space, is not within the block of memory accessed, a subsequent access is required. For example, in
FIG. 1
, the processing of data elements in a left to right fashion will be efficient, because each accessed block will contain a multitude of the data elements desired, thereby reducing the number of accesses required. Conversely, the processing of data elements of
FIG. 1
in a top to bottom fashion will be inefficient, because each accessed block will typically contain only one of the desired data elements, the next desired data element being located a substantial distance (1024 memory locations) away from the prior vertically adjacent data element.
The inefficiencies of linear memory access for multidimensional data structures can be particularly problematic. Multi-dimensional applications often process data in an “area” or “regional” scheme. For example, in image processing, individual data elements are often smoothed, wherein a data element's value is modified by the values of data elements adjacent, in the object space, to this data element. Such area dependent processing will be efficient for processing data elements in one dimension, but inefficient in the other dimension, if a linear addressing scheme is utilized. To optimize performance in area or regional processing schemes, a non-linear mapping of multidimensional data is utilized to allocate contiguous blocks of memory to areas or regions of the object space, as shown in FIG.
2
. The object space is partitioned into sub-areas, or tiles, and the elements of each tile are stored in a contiguous block of memory.
In
FIG. 2
, the object space is partitioned into tiles
101
,
102
, etc. of 12 pixels, arranged in a 4×3 manner. The first tile
101
comprises the data elements within the bounds between P(
0
,
0
) and P(
3
,
2
); the second tile
102
comprises the data elements within the bounds between P(
4
,
0
) and P(
7
,
2
); etc. As shown, the mapping of the first tile
101
is as follows: the first four pixels (P(
0
,
0
)-P(
3
,
0
)) are stored in the first four memory locations (memory address
0
-
3
); the four pixels from the line below (P(
0
,
1
)-P(
3
,
1
)) are stored in the next four memory locations (memory address
4
-
7
); the four pixels from the next line below (P(
0
,
2
)-P(
3
,
2
)) are stored in the next four memory locations (
8
-
11
). Thus, the first
12
memory locations contain the data elements of the first 4×3 tile
101
. The second tile
102
is mapped in the next
12
memory locations in the same manner: pixels P(
4
,
0
)-P(
7
,
0
) are stored in the next four memory locations (
12
-
15
); pixels P(
4
,
1
)-P(
7
,
1
) are stored next (
16
-
19
); etc. In this non-linear addressing scheme, pixels that are in proximity to each other in either dimension in the object space are generally close to each other in memory space, as compared to a linear addressing scheme.
A disadvantage of tiling, however, is that the non-linear mapping does not provide for the relative memory access technique discussed above. Because the mapping is non-linear, the relationship between the addresses of the data elements is not merely additive, as in the linear mapping scheme. That is, for example, the determination of an address corresponding to a data element adjacent to another data element is not merely effected by the addition of a constant, as in a linear addressing scheme, discussed above. Conventional memory access techniques for non-linear mappings require the direct computation of each memory address from the object coordinates. In
FIG. 2
, for example, P(
0
,
2
) is
4
memory
Feldstein Robert
Hollister Brad
ATI Technologies Inc.
Kim Matthew
Mackison & Reckamp, P.C.
Tzeng Fred F.
LandOfFree
Method and apparatus for relative addressing of tiled data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for relative addressing of tiled data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for relative addressing of tiled data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2606426