JPH03292575A - Address generating device - Google Patents

Abstract

PURPOSE:To give access to a memory from a cache memory at a high speed by converting the coordinates of a pixel designated based on the values of the 1st and 2nd registers which hold the X and Y coordinates of the graphics data into an address of the memory. CONSTITUTION:A conversion means 150 converts the coordinates of a pixel designated based on the values of the 1st and 2nd registers 110 and 120 which hold the X and Y coordinates of the graphics data into an address of a memory 140. Thus, the memory 140 shows the pixels adjacent to each other in the direc tion Y in the continuous addresses, and the means 150 produces the address of the memory 140 based on the (X, Y) coordinates held by the registers 110 and 120. As a result, the continuity of the address produced between the pixels of the graphics data can be increased. As a result, an access is given to a memory at a high speed.

Description

DETAILED DESCRIPTION OF THE INVENTION Field of the Invention The present invention relates to an address generation device that generates an address for a memory that holds graphics data in an information processing system that generates graphics data such as characters and figures. It is something.

Prior Art An example of a conventional address generator (for example, Nikkei Data Pro Microcomputer, MCl-164-002, June 1986)
(Nikkei McGraw-Hill, Inc.) is shown in Figure 4.

FIG. 4 is a configuration diagram showing the relationship between pixels of graphics data in a two-dimensional space and addresses on the memory. In FIG. 420 is a memory that holds the graphics data 410, 421 to 423 are addresses on the memory 420, where n is the number of bits constituting one word of the memory 420, and the graphics data 410 is For example, groups of n pixels 411, 412, 413,...
are held at addresses 421, 422, 423, etc., respectively. The address in memory is A, the bit position in the word indicated by that address is BP, the X coordinate in two-dimensional space is X, and the Y coordinate is Y. , the number of space width words is WDT
, let the origin address be ORG, then the pixel coordinates (X
, Y), address AR and bit position BP can be found using the following formula: AR=ORG+WDTxY+ [X/n] - (1)B
P=mod (X, n) −
(2) where L [a] is the largest integer not exceeding a, m
0d (a, b) is the remainder of a / b 4 Problems to be solved by the invention The execution speed of processors has been increasing significantly year by year, but the access speed of memory has not kept up with it (~ Therefore, when designing an information processing system, the key point is how fast the memory can be accessed.For this reason, it is important to install cache memory between external memory and fill the gap in access speed. Even if this is generally done, if the data to be accessed is not in the cache memory (if the data is exchanged between the cache memory and external memory), the effect of cache memory is that if the data to be accessed is local. is large, and the effect is small in the global picture.When generating graphics data such as characters and figures, for example when generating a straight line, the pixel coordinates may change to around 8. An example of a coordinate change on the area graphics data 510 is shown.In the example of FIG. 5, if the current pixel addresses are TA and R,
When the coordinates change in the positive and negative directions (1) and (5),
The address of the pixel after the change is also TAR.When changing in the other six directions (2) to (4) and (6) to (8), the address of the pixel after the change is TAR from equation (1).
AR-WDT, TAR+WDT, and the address is WDT away from TAR. Now, suppose that the probabilities of change in each of the 8 neighboring directions are equal. If the address changes to one of the adjacent addresses TAR-1, TAR, or TAR+1. For example, if the number of bits that make up one word is n = 16, there are 8 ways for each pixel to change, so there are 16 x 8 = 128 ways for one word. Because each pixel has only two ways of X coordinate, positive and negative, there are 16x2 = 32 ways for one word. Therefore, the probability (y32/128 = 0.25), and the continuity of the address is small l,% When other graphics data is generated, the L coordinate Gt may change to around 8, and the continuity of addresses is generally considered to be low.Therefore, the locality of graphics data is low, and the effect of cache memory is small. Namusara C2 In recent years, the resolution of graphics data has been increasing.The resolution of current CRTs is about 100 dpi (100 pixels per inch), and the resolution of printers is about 100 dpi (I00 pixels per inch). It is approximately 300 to 400 dpi.

In particular, as graphical user interfaces for improving man-machine interfaces become widespread,
CRTs are now required to have the same resolution as printers.4 Unlike printers, CRTs require real-time performance, and high-speed generation of graphics data is essential. However, since the size of the shape itself of the graphics data generated is the same regardless of whether the resolution is low or high, the higher the resolution, the greater the number of pixels composing the graphics data and the longer the processing time.

For example, when generating a shape 610 as shown in FIG. 6, low-resolution graphics data 620 is composed of 4 pixels, and high-resolution graphics data 630 with twice the resolution in both the X and Y directions is 16 pixels required 4 Address 62 for low resolution
The ability to access four addresses from 1 to 624 (
At high resolution, eight addresses from 631 to 638 must be accessed (°C) As the resolution increases, the shape of the generated graphics data becomes wider in area.The number of addresses to be accessed increases. As explained earlier, accessing memory is slow. If the number of accesses to memory increases significantly, the overall processing time increases significantly.

As mentioned above, an address generator with the configuration shown in Figure 4 is a good choice.Since there is little continuity of addresses between pixels of generated graphics data, it is difficult to demonstrate the effect of cache memory, and it is difficult to use high-resolution graphics. For data, the number of accesses to memory increases significantly, increasing processing time.

In view of this point, the present invention as claimed in claim 1 provides an address generation device that can increase the continuity of addresses between pixels of generated graphics data. In view of the above, it is an object of the present invention to provide an address generator capable of reducing the number of accesses to a memory at high resolution. In order to-
, a first register that holds the X coordinate of graphics data, a second register that holds the Y coordinate of graphics data, and a register that holds the graphics data as a set of pixels in a two-dimensional space that are adjacent in the Y direction. an address generator comprising: a memory for representing pixels to be stored as consecutive addresses; and a conversion means for converting the coordinates of the pixel specified by the value of the first register and the value of the second register into an address on the memory. The present invention of claim 2 (above) is an apparatus for solving the above problems.
A first register that holds the X coordinate of graphics data, a second register that holds the Y coordinate of graphics data, and a register that holds the graphics data as a set of pixels in a two-dimensional space and divides the two-dimensional space into one. A memory that is divided into tiles in a rectangular area with sides of 2 pixels or more and represents pixels in each rectangular area with the same address, and a pixel specified by the value of the first register and the value of the second register. The address generating device is provided with a conversion means for converting the coordinates of , into an address on the memory.

Operation The present invention according to claim 1 has the above-described configuration, so that the memory for holding graphics data represents pixels adjacent in the Y direction by consecutive addresses, and the data is stored in a register (
Since the conversion means generates an address to the memory from the (X, Y) coordinates, it is possible to increase the continuity of addresses between pixels of generated graphics data. The memory that holds graphics data stores pixels within a rectangular area as 1
represented by two addresses and held in a register (X,
Y) Since the conversion means generates addresses to the memory from the coordinates, the number of addresses occupied by pixels of graphics data generated at high resolution is reduced, and the number of accesses to the memory can be reduced. FIG. 1 is a block diagram showing an embodiment of the address generation device of the present invention. In Figure 1, 110
holds the X coordinate (X) Regis Ku 120 holds the Y coordinate 1 (
130 is a graphics data storage in two-dimensional space. 131 to 133 are pixel captures of graphics data 130. 140 is a memory that holds graphics data 130. 141 to 143 are addresses on memory 140 150 converts the (X, Y) coordinates indicated by the values of the register 110 and the register 120 into an address on the memory 140. The conversion half 151 holds the address (AR). The register 152 stores the space high word number (HGT). ) is the value '1
155 is an adder/subtractor that adds and subtracts the value of register 151 and the output of selector 154. 156 is a register that holds the bit position (BP) in a word. 157 is an incrementer/decrementer that increases the value of the register 156 by ±1. 158 is a register that holds the origin address (ORG) of the graphics data 130 and the number of bits (n) that constitute one word of the memory 140. 159 is an operation. The operation of the address generating device of this embodiment configured as described above will be explained below. Each pixel is stored in the memory 140 in order of increasing Y coordinate.
31, 132, 133, ... are each address 14
1, 142, 143, etc. When calculating the address AR and bit position BP from the pixel coordinates (X, Y), use registers 110 and 120.
, 152 and the value of the register group 158.
59, perform the following calculation (store in registers 151 and 156) AR=○RG+Y+HGTX [X/n] ・(3)B
P=mod (X, n) ・=(4
) or [a] is the largest integer not exceeding a, m0d(
a, b) is the remainder of a/b and the pixel coordinates are X
When the coordinates change in the positive/negative direction, the following operations are performed: First, the value in the register 156 is incremented by ±1 by the incrementer/decrementer 157, and then stored in the register 156 again.At this time, overflow/underflow occurs. When this occurs, the value of the register 151 and the value of the register 152 selected by the selector 154 are added and subtracted by the adder/subtractor 155 (AR±HGT).
This operation occurs when the coordinate change crosses the left and right word boundaries, but when the pixel coordinate changes in the positive/negative direction of the Y coordinate (
Friend: Even if the following operation is performed, the value of the register 151 and the value of the register 153 selected by the selector 154 are added/subtracted (AR±1) by the adder/subtractor 155 and stored in the register 151 again, but the pixel coordinates are different from the above. When Ct changes in four diagonal directions, the following operation is performed. First, the value of the register 151 and the value of the register 153 selected by the selector 154 are added and subtracted by the adder/subtractor 155 - (AR±1
) and stored in register 151 again, the value in register 156 is stored in incrementer/decrementer 15 at the same time.
7 and stored in register 156 again.
If an overflow/underflow occurs at this time, the value of the register 151 and the value of the register 152 selected by the selector 154 are added/subtracted again by the adder/subtractor 155 ((AR±1)±HGT) and stored in the register 151 again. Similarly to the conventional example > Assuming that the probability that the coordinates of a pixel changes in each of the eight neighboring directions is equal, calculate the probability that the coordinates of a pixel change to an adjacent address α.

For example, when the number of bits composing l word is n = 16
Since each pixel can change in 8 ways, there are 16×8=128 ways in one word.

That board, there are 5 ways to change the address to the adjacent address for the left and right pixels and 8 ways for the other pixels, so
In one word, there are 2X5+14X8=122 ways.
Therefore, the probability is 122/128=0. 95..., which makes it impossible to increase the continuity of addresses compared to the probability of 0.25 in the conventional example. A similar effect can be obtained even if the pixels of the graphics data are expressed using multiple bits.Also, in this example, the pixels of the graphics data are divided into areas of every n columns, and the Y coordinate increases every n pieces in one row of each area. A similar effect can be obtained by allocating the addresses of pixels adjacent in the LY force direction using another method, but FIG. 2 is a block diagram showing an embodiment of the address generator of the present invention. In FIG. 2, 210
220 holds the X coordinate (X), and the Regis 220 holds the Y coordinate (Y
) 230 is a graphics data register in two-dimensional space 231 to 233 are pixel lines of graphics data 23-0 240 is a memory that holds graphics data 230 241 to 243 are addresses on memory 240 250 is a conversion that converts the (X, Y) coordinates indicated by the values of the register 210 and the register 220 into an address on the memory 240. 251 is a conversion that holds an address (AR). A register 252 is the number of space width words (WDT). ) holds the value 1
255 is an adder/subtractor that adds or subtracts the value of register 251 and the output of selector 254. 256 is the X-direction bit position (XBP) in the word.
The register 257 that holds the value of the register 256
The incrementer/decrement register 258 that increments 1 is a register register that holds the Y-direction bit position (YBP) within a word.
59 is an incrementer that increases the value of register 258 by ±1.
260 is the origin address (ORG) of the graphics data 230 and the graphics data 230
The register 261 that holds the number of pixels (u) in the X direction of the rectangular area into which the graphics data 230 is divided and the number (V) of pixels in the Y direction of the rectangular area into which the graphics data 230 is divided is an arithmetic unit. The operation of the address generator of this embodiment, which is configured as follows, where n is the number of bits constituting the image data 230, will be described below. Even if it is divided into tiles, it is just UAu, v is u
Let x be an integer of 2 or more that satisfies v=n. The n pixels included in this rectangular area are sequentially stored in the memory 240, for example, pixel groups 231, 232, 233, .
...are addresses 241, 242, 243, etc., respectively.
・Holded to . Bit position 4 within the pixel word
& Expressed by the bit position in the X direction and the bit position in the Y direction.

What if you want to find the address AR, X-direction bit position XBP, and Y-direction bit position YBP from the pixel coordinates (X, Y)? The following calculation is performed by the arithmetic unit 261 between the values of the L registers 210 and 220.252 and the values of the register group 260 in line 1. % Store in registers 251, 256, 258 a AR=ORG+WDTX[Y/v]+[X/u...
・(5) XBP=mod (X, u) −(
6) YBP=mod (Y, v)
-(7) Just L [a] is the largest integer not exceeding a, m.

d(a,b) is the remainder of a/b.When the coordinate of a pixel changes in the positive/negative direction of the X coordinate, the following operation is performed.First, the value of the register 256 is changed to The signal is changed to ±1 and stored in the register 256 again. If an overflow/underflow occurs at this time, the value of the register 251 and the value of the register 253 selected by the selector 254 are added/subtracted (AR±1) by the adder/subtractor 255 and stored in the register 251 again. Occurs when a coordinate change crosses a left or right word boundary.

When the coordinates of a pixel change in the positive and negative directions of the Y coordinate, the following operations are performed. First, the value of the register 258 is incremented by ±1 by the incrementer/decrementer 259 and stored in the register 258 again. If an overflow/underflow occurs at this time, the value of the register 251 and the value of the register 252 selected by the selector 254 are added or subtracted by the adder/subtractor 255 (AR±
WDT) and stored in the register 251 again.This operation (L) occurs when the coordinate change crosses the upper and lower word boundaries, but when the pixel coordinate changes in the other four diagonal directions, the following operation occurs. The values in the register 256 are first incremented by ±1 by the incrementer/decrementer 257 and stored in the register 256 again. At the same time, the value in the register 258 is incremented by ±1 by the incrementer/decrementer 259 and stored in the register 258 again. When an overflow/underflow occurs in the incrementer/decrementer 257, the value of the register 251 and the value of the register 253 selected by the selector 254 are added/subtracted by the adder/subtractor 255 (AR
±1) is stored in the register 251 again, but when an overflow/underflow occurs in the incrementer/decrementer 259, the value of the register 251 and the value of the register 252 selected by the selector 254 are added/subtracted by the adder/subtractor 255 (AR±WDT ) and stored in register 251 again.If overflow/underflow occurs in both incrementer/decrementer 257 and 259, the value of register 251 and selector 2
The value of the register 253 selected by 54 is added to the adder/subtractor 2
55 is added and subtracted (AR±1) and stored in the register 251. The value of the device register 251 and the selector 254 are
The value of the register 252 selected by the adder/subtractor 255
They are added and subtracted ((AR±1)±WDT) and stored in the register 251 again.
Figure 3 shows graphics data 310 in this embodiment that has the same resolution as the high-resolution graphics data 630 of the conventional example shown in Figure 6. Constituent bit number n = 1
6. In this example, the number of pixels in the X direction of the rectangular area is u = 4, and the number of pixels in the Y direction of the rectangular area is v = 4. In the graphics data 310, the shape 610 shown in FIG.
The force consists of the same 16 pixels as the graphics data 630 shown in the figure (only the two addresses 311 and 312 need to be accessed (-therefore, the conventional 8
Compared to addresses, it is not possible to reduce the number of accesses to the memory. In this example, the number of bits to represent one pixel is set to one bit. Also, the shape of the rectangular area is described as a 4 x 4 pixel square.Other than this, the same effect can be obtained if the rectangular area is 2 pixels or more on a side and is close to a square, but the effect is more than the effect of the invention. According to the invention No. 1, adjacent pixels in the Y direction of graphics data are represented by consecutive addresses on the memory, and the pixel's ('X, Y
) Although the conversion means from coordinates generates addresses to memory at high speed, the continuity of addresses between pixels of the generated graphics data increases. To effectively speed up memory access using cache memory. According to the present invention as claimed in claim 2, the pixels of graphics data are represented by the same address on the memory in units of rectangular areas close to squares, and the practical effect is thick (~). Y) The conversion means from coordinates generates addresses to memory at high speed. Therefore, by reducing the number of addresses occupied by pixels of graphics data generated at high resolution and reducing the number of accesses to memory, processing speed is increased. can be carried out, and its practical effects are significant.

[Brief explanation of the drawing]

FIG. 1 shows a block diagram of an address generator according to an embodiment of the invention according to claim 1. FIG. 2 shows a block diagram of an address generator according to an embodiment according to the invention according to claim 2. FIG. 4 is an explanatory diagram showing an example of a conventional address generation device; FIG. 5 is an explanatory diagram showing the operation of the conventional example; FIG. 6 is an explanatory diagram showing the operation of the conventional example.

Claims (2)

[Claims] (1) A first register that holds the X coordinate of graphics data, a second register that holds the Y coordinate of graphics data, and a register that holds the graphics data as a set of pixels in a two-dimensional space in the Y direction. , a memory for representing pixels adjacent to each other as consecutive addresses, and a conversion means for converting the coordinates of the pixel specified by the value of the first register and the value of the second register into an address on the memory. An address generator characterized by the following. (2) A first register that holds the X coordinate of graphics data, a second register that holds the Y coordinate of graphics data, and a two-dimensional register that holds the graphics data as a set of pixels in a two-dimensional space. 1 side of space is 2
A memory that is divided into tiles in a rectangular area larger than pixels and represents pixels in each rectangular area with the same address, and a memory that stores the coordinates of the pixel specified by the value of the first register and the value of the second register. An address generation device characterized by comprising conversion means for converting into an address on the memory.