JP3652909B2 - Pseudo multi-port memory device - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a multi-port memory device, and is particularly used in motion vector search for inter-frame image encoding processing of moving images, and writes a plurality of data to a continuous address at a time and a plurality of data from unrelated addresses. The present invention relates to a multi-port memory device that can be read simultaneously.
[0002]
[Prior art]
In a vector search used in an inter-frame image encoding process of a moving image, a block matching method is usually used as a motion vector detection method.
In this block matching method, the screen is divided into small rectangular areas (blocks), and motion is detected for each block.
Generally, the block size includes 8 horizontal pixels × 8 vertical pixels, 16 horizontal pixels × 16 vertical pixels, and the like.
[0003]
Next, among the conventional motion vector search methods, the simplest and high image quality full search method will be described.
FIG. 3 is an explanatory diagram showing a conventional full search method, schematically showing a template 1 that is a target for obtaining a motion vector and a search region 2 that is a search range of a motion vector.
[0004]
Template 1 shows a pixel block in a certain image, and search area 2 is a pixel block in another image larger than template 1.
Further, Δ3 (triangle mark) is a pixel constituting the template 1, and ○ 4 (circle mark) is a pixel constituting the search area 2.
In FIG. 3, the template 1 is shown overlaid on the search area 2, and the pixel ◯ 4 in the search area of the overlapping portion is not displayed.
[0005]
Hereinafter, the unit of the number of pixels in the horizontal direction is referred to as a pixel, and the unit of the number of pixels in the vertical direction is referred to as a line.
According to this, the template shown in FIG. 3 is expressed as 4 pixels × 4 lines, and the search area 2 is expressed as 11 pixels × 11 lines.
[0006]
In this full search method, an area of 4 pixels × 4 lines having the same size as the template 1 (hereinafter, this area is referred to as a block) is sequentially cut out from the search area 2, the pixel value of each pixel of the cut out block, the template An absolute difference value, a square difference value, and the like are obtained sequentially from the pixel value of one corresponding pixel.
And the sum total about each pixel value of the calculated | required value is calculated for every cut-out block.
[0007]
That is, in the search area 2, if the block is shifted by one pixel or one line from the upper left to the lower right, the search area 2 is 11 pixels × 11 lines, so that a total of 8 × 8 = 64 blocks Are cut out, and this is a target for calculation (calculation for obtaining a sum of absolute differences, a sum of squared differences, etc.) with the template 1. Then, the motion vector is obtained from the block having the smallest calculation result as the template 1 has moved.
[0008]
In FIG. 3, when the motion vector of the pixel block at the position corresponding to the template 1 is (0, 0), the range of values that the motion vector can take is “−4 to +3” in both the horizontal direction and the vertical direction.
This is because, as shown in FIG. 3, the template 1 in the horizontal and vertical directions is equivalent to 4 pixels (or 4 lines) on either side and 3 pixels (or 3 lines) on the other side. Because it can move each minute.
[0009]
For example, when the calculated value of the block 5 (difference absolute value sum, difference square value sum, etc.) is the minimum, the motion vector is (−2, −2).
The above is the principle explanation for obtaining the motion vector.
As a motion vector search method for obtaining a motion vector, a case where a sum of absolute differences is used will be described below, but an evaluation formula such as a sum of squared differences may be used as another arithmetic formula.
[0010]
This full search method makes it easy to parallelize computing units (hereinafter referred to as PE) that calculate the sum of absolute differences.
Normally, the pixels in the search area are stored in the memory, but by using the overlap between adjacent blocks, the pixel transfer amount between the parallelized PE (hereinafter referred to as PE array) and the memory Can be reduced.
[0011]
FIG. 4 is an explanatory diagram showing the operation of the PE array.
Here, the number of pixels beside the search area 6 is
(Number of pixels next to template) × 2-1
= 4 × 2-1 = 7
4 PEs are provided corresponding to the blocks 7 to 10.
These four blocks overlap each other by 4 pixels × 3 lines.
[0012]
Therefore, only one pixel is read out from the memory, sent to the PE array, and the PEs corresponding to the blocks 7 to 10 are activated by delaying each cycle one cycle at a time in this order.
In addition, since the block 7 and the block 11 are overlapped by 4 pixels × 3 lines, the PE corresponding to the block 11 is provided, and the pixels in the second line of the search area 6 are sent to the PE array, so that Parallel processing can be performed even with PEs corresponding to 11.
[0013]
That is, the pixels in the search area 6 are stored in consecutive addresses from the upper left corner pixel to the lower right corner pixel of the area, read out one by one from the memory in that order, and sent to the PE array. The parallel operation can be realized.
By this method, it is possible to parallelize PEs up to the number of pixels of the template.
However, if only one pixel is read from the memory, an invalid cycle occurs in the PE at the right end of the search area 6.
[0014]
FIG. 5 is an explanatory diagram showing the generation mechanism of the invalid cycle.
In the figure, among the pixels in the search area 6, the pixel 12 is used for the calculation of the blocks 8 to 10, but is not used for the calculation of the blocks 7 and 11.
Therefore, when the pixel 12 is read from the memory and sent to the PE array, it cannot be calculated by the PE corresponding to the calculation of the block 7 and the block 11, and an invalid cycle occurs.
In order to avoid this, it is necessary to read the pixel 13 from the memory simultaneously with the pixel 12 and send it to the PE array.
[0015]
Further, the number of horizontal pixels in the search area 2 shown in FIG. 3 is larger than that in the search area 6 shown in FIGS.
(Number of pixels next to template) × 3-1
= 4 × 3-1 = 11
It is.
[0016]
In this case, as shown in FIG. 6, the search area 2 is divided into a left search area 14 and a right search area 15 and is searched twice, so that all blocks cut out from the search area 2 can be evaluated. it can.
FIG. 6 is an explanatory diagram showing a parallel calculation technique.
For example, “Toshihiro Minami, Toshio Kondo, Kazuhito Murashita, Ryota Kasai,“ Proposal of a one-dimensional systolic array-type full search motion vector detector ”, Science theory (D-1), vol. J78-D-1, no.12, pp.913-925, Dec.1995 ".
[0017]
In the same document, the calculation method of the computing unit (PE) for calculating the sum of absolute differences is based on whether the motion vector or the template is associated with the PE, and the pixels in the search region are shifted. Alternatively, four basic configurations are shown based on two criteria of whether to broadcast.
In the following, referring to FIG. 7, as an example of the configuration of the PE used in FIG. 4 described above, “MMSB (Motion-vector Mapping method with Search-area-pixel Broadcasting) operation” The principle will be described.
[0018]
FIG. 7 is an explanatory diagram showing a motion vector correspondence / search area pixel broadcasting system, where (a) shows a block diagram of PE and (b) shows a calculation process.
Note that the image is actually two-dimensional, but for the sake of simplicity, FIG. 7 shows a case where the image is assumed to be one-dimensional.
In MMSB, the pixels X in the search area are broadcast to every PE pixel by pixel, and the pixels a in the template are shifted between the PEs for each clock CK.
[0019]
In each PE, the difference absolute value a @ X is calculated for each CK between the pixel a and the pixel X, and accumulated in each PE by a latch and an adder.
Then, by selecting the output from each PE by the selector according to CK, the difference absolute value sum S is sequentially calculated as shown in FIG. 7B. For example, in the clock “3CK”,
S₀ = A₀@X₀+ A₁@X₁+ A₂@X₂+ A_Three@X_Three
Is calculated.
[0020]
Also, with reference to FIGS. 8 and 9, the operation principle of the search region division method of the above-described improved MMSB method will be described as a configuration example of the PE used in FIG.
FIG. 8 is an explanatory diagram showing a search area dividing method, where (a) is a pixel arrangement example and (b) is a block diagram of PE.
FIG. 9 is an explanatory diagram showing a calculation process of MMSB for a two-dimensional image.
[0021]
In FIG. 5 described above, the difference absolute value calculation process when the pixel 12 is read and the pixel 13 is not read simultaneously is as shown in FIG.
In the MMSB extended to support two-dimensional images, the sum of absolute differences S_0,0, S_0,1, S_0,2In the PE that calculates_0,3It can be seen that the calculation of the second line cannot be started until the calculation of the first line is completed, and an invalid cycle (broken line area in the figure) occurs.
[0022]
The invalid cycle can be avoided by supplementing the pixels in the second row as shown in FIG.
In this case, pixel X_0,4Is the sum of absolute differences S_0,1, S_0,2, S_0,3Used to calculate X_1,0Is S_0,0Used to calculate
Therefore, as shown in FIG. 8B, these two pixels X_0,4, X_1,0Broadcast simultaneously.
[0023]
And S_0,0X in the leftmost PE when calculating_1,0And select X for other PEs._0,4Select with the selector.
This allows the calculation to continue in all four PEs.
In other words, the invalid cycle that occurs when the number of horizontal motion vectors to be searched at once matches the number of horizontal pixels of the template and moves from the right end to the left end of the search area is obtained by supplementing the pixels in the next row. You can delete it.
[0024]
Further, due to the same cause as the invalid cycle described above, an invalid cycle occurs in the PE array even at the lower end of the search area.
In order to prevent this, it is only necessary to simultaneously read out four pixels from the memory and send them to the PE array.
For example, as shown in FIG. 6, an invalid cycle occurs at the lower end of the search area by sending the pixels 16 and 17 in the search area 14 and the pixels 18 and 19 in the search area 15 to the PE array. Can be avoided.
[0025]
Regarding this technology, for example, `` M. mizumo, Y. Ooi, N. Hayashi, J. Goto, M. Hozumi, K. Furuta, A. Shibayama, Y. Nakazawa, O. Ohnishi, S. Zhu, Y. Yokoyama , Y.Katayama, H.Tanaka, N.Miki, Y.Senda, I.Tamitani, M.Yamashina; "A 1.5-WSingle-Chip MPEG-2 MP @ ML Video Encoder with Low Power Motion Estimation and Clocking" IEEE J .Solid-State Circuits, vol. 32, no. 11, pp. 1807-1816, Nov. 1997 ”.
[0026]
In order to avoid the generation of invalid cycles by such a method, it is necessary to simultaneously read out four pixels (data) from unrelated addresses.
Therefore, it is conceivable to use a 4-port memory, but the 4-port memory is large and slow.
[0027]
Therefore, it is conceivable to use a plurality of 1-port memories as shown in FIG.
FIG. 10 is an explanatory diagram showing a full search method (first prior art) using a plurality of memories.
As described above, by simultaneously storing the pixels to be read out in the four separate memories 20 to 23, it becomes possible to simultaneously read out the four pixels.
[0028]
As can be seen from the above description, when the full search method is adopted, the structure of the memory and the PE array becomes simple, but an enormous amount of calculation is required as the block size and the search area size increase.
Therefore, a telescopic search method has been proposed to reduce the amount of calculation.
[0029]
In general, a moving image is composed of a plurality of images that are temporally continuous. In particular, in an image encoding process, there are cases where motion vectors of a plurality of previous images are obtained in addition to the previous image in time.
In such a case, a motion vector is obtained in a narrow area in an adjacent image, and it is used as an initial value to obtain a motion vector in a narrow area in the next adjacent image. The motion vector at is obtained.
[0030]
This telescopic search method will be described with reference to FIG.
FIG. 11 is an explanatory diagram showing a telescopic search method (second prior art).
In the figure, images 25 to 28 are four images that are temporally continuous, image 28 is the current image, and images 25, 26, and 27 are three screens ago, two screens ago, and one screen respectively. It is the previous image.
The rectangular block 24 moves from the image 25 to the image 26 with the motion vector mv1, and similarly moves from the image 26 to the image 27 and from the image 27 to the image 28 with the motion vectors mv2 and mv3, respectively.
[0031]
Therefore, the movement of the rectangular block 24 from the image 28 to the image 25 is “mv1 + mv2 + mv3”.
In the telescopic search method, in order to obtain a motion vector from the image 28 to the image 25, first, the region 31 in the image 27 is searched by using the rectangular block 24 in the image 28 as a template to detect the motion vector mv3.
In this case, the motion vector at the center of the region 31 is (0, 0).
[0032]
Next, the area 30 in the image 26 is searched to detect the motion vector mv2.
When the motion vector from the image 28 to the image 27 regarding the rectangular block 24 is considered, the motion vector at the center of the region 30 is mv3.
Finally, when the motion vector into the image 25 is also considered, the motion vector at the center of the region 29 is “mv3 + mv2”.
[0033]
As another technique for reducing the amount of calculation, a technique for evaluating a motion on a reduced image obtained by sampling and performing a search only in a narrow range using the obtained motion vector as an initial value is also proposed. ing.
A method combining this sampling method and the above-described telescopic tank method is, for example, `` K. Suguri, T. Minami, H. Matuda, R. Kusaba, T. Kondo, R. Kasai, T. Watanabe, H. Sato, N. Shibata, Y. Tashiro, T. Izuoka, A. Shimiz, H. Kotera, "A real-time motion estimation and compensation LSI with wide search range for MPEG2 video encoding" IEEE J. Solid-State Circuits, vol. 31 , no. 11, pp.1733-1741, Nov. 1996 ”.
[0034]
[Problems to be solved by the invention]
However, when such a plurality of general one-port memories are used as memory devices for storing search target pixels in each motion vector search described above, there are the following problems.
First, in a full search method (first prior art: see FIG. 10) in which pixels read simultaneously are stored in separate memories, when a plurality of small-capacity memories are used, compared to a case where a single large-capacity memory is used. As a result, there is a problem that division loss occurs and the chip area increases.
[0035]
In the telescopic search method (second prior art: see FIG. 11), the search position of the next field is adaptively determined based on the search result of the previous field. For this reason, there is a problem in that the address of the search target pixel in the search area memory cannot be determined in advance, and pixels that are read simultaneously cannot be stored in different memories.
The present invention is to solve such a problem, and provides a pseudo multi-port memory device that can read a plurality of data from unrelated addresses using one or two large-capacity memories. The purpose is that.
[0036]
[Means for Solving the Problems]
  In order to achieve such an object, the pseudo multi-port memory device according to the present invention has an input / output bit width capable of reading and writing a plurality of data constituting a data group at a time.Two1-port memory,Data rearrangement means for selecting and rearranging arbitrary data from each data constituting each data group read from the one-port memory, and outputting as a new data group;thisData sorting meansA shift register group consisting of a plurality of shift registers each having a predetermined number of shift stages arranged in parallel to each other is provided.Data sorting meansThe corresponding data groups sequentially read from each of the shift registers are sequentially held in each shift register, and a plurality of data constituting each data group are sequentially shifted out from each shift register one by one, so that each shift register can obtain a desired data group. Data is output in parallel at the same time.
[0038]
DETAILED DESCRIPTION OF THE INVENTION
Next, the present invention will be described with reference to the drawings.
FIG. 1 is a block diagram of a pseudo multi-port memory device according to a first embodiment of the present invention.
In this embodiment, one memory 32 having an input / output bit width that can read or write simultaneously four pixels (4 data) constituting one pixel group (data group) is used, and all pixels in the search region are used. Is stored in the memory 32.
[0039]
Here, in order to facilitate understanding of the concept of the search area, the memory 32 is represented in two dimensions, but in reality it is a one-dimensional memory, and four pixels (four data) are stored at one address.
For example, addresses of address 0, address 1, and address 2 are assigned to the left, middle, and right four pixels in the first line in the memory 32, respectively.
In addition, the addresses of 3 addresses, 4 addresses, and 5 addresses are assigned to each of the left, middle, and right 4 pixels in the second line, and continuous addresses are assigned from the left to the right on the same line. Are allocated in order from top to bottom.
[0040]
Note that the crosses in the memory 32 indicate invalid data.
Since the search area 2 in FIG. 3 described above has 11 pixels in the horizontal direction, the total number of pixels in one line is not divisible by 4.
In such a case, invalid data is added so that the four pixels to be read and written at a time are always only pixels on the same line.
[0041]
Four pixels are simultaneously read from the memory 32 in synchronization with CK (clock), and each CK is transferred to each shift register 37 to 40 of the shift register group arranged in parallel in the order of “39 → 40 → 37 → 38”. Set to
The four arrows 44a to 44d correspond to the respective pixels in order from the leftmost pixel of the pixel group read from the memory 32, and a path (path) in which the four pixels read from the memory 32 are set in the shift register. Represents.
[0042]
The shift registers 37 to 40 shift one pixel to the right every 1 CK.
The number of shift stages of the shift registers 39, 40, 37, and 38 is 7, 5, 5, and 3, respectively.
Thus, the reason why the difference in the number of shift stages of the shift register is to read out the four pixel groups that should be read out simultaneously for every CK over 4 CKs.
[0043]
Here, since the pixel group 34 and the pixel group 36 are three pixels and one pixel is invalid, the number of shift stages of the shift register 40 and the shift register 38 is five and three.
Note that the pixel group 34 is included in the left search area 14 shown in FIG.
In applications where all 4 pixels are valid, 6 and 4 respectively.
Hereinafter, the operation of each shift register will be described.
First, the pixel group 35 including the pixel 18 is read with the first CK and set in the shift register 39.
[0044]
Then, the subsequent CK sequentially shifts, and the pixel 18 is output to the PE array 45 by the fifth CK.
In the second CK, the pixel group 36 including the pixel 19 is read and set in the shift register 40, and the pixel 19 is output to the PE array 45 in the fifth CK.
[0045]
In the third CK, the pixel group 33 including the pixel 16 is read and set in the shift register 37, and the pixel 16 is output to the PE array 45 in the fifth CK.
In the fourth CK, the pixel group 34 including the pixels 17 is read and set in the shift register 38, and the pixels 17 are output to the PE array 45 in the fifth CK.
[0046]
Therefore, it can be seen that the pixels 16 to 19 are simultaneously output in parallel to the PE array 45 at the fifth CK.
Therefore, according to this embodiment, division loss does not occur as in the case where a plurality of small-capacity memories shown in FIG. 10 are used, and a plurality of pixels (data) are obtained using one memory. A multi-port memory device capable of simultaneously reading from unrelated addresses can be configured, and an increase in chip area can be suppressed.
[0047]
In the present embodiment, the number of pixels that are read and written at a time in the memory 32 is four pixels, and only the case of matching the number of pixels in the horizontal direction of the template is shown. However, the present invention is not limited to this.
In other words, the present embodiment is characterized in that a plurality of pixels are read at a time and are sequentially set in corresponding shift registers, and desired pixels are output in parallel while being shifted by each shift register. Therefore, it is not always necessary to match the number of pixels read from the memory at once with the number of pixels in the horizontal direction of the template.
[0048]
In the above description, the case where four pixels are simultaneously read from the memory 32 and set in the shift registers 37 to 40 every 1 CK is shown.
However, for example, the number of shift stages of the shift register is doubled as described above, and 8 pixels are simultaneously read out from the memory 32 every 2 CK. It may be set every time, so that four pixels can be simultaneously sent to the PE array 45.
Further, the number of memories is theoretically only one, and even if there are a plurality of memories, continuous addresses only need to be allocated.
[0049]
Next, a second embodiment of the present invention will be described with reference to FIG.
FIG. 2 is a block diagram showing a pseudo multi-port memory device according to the second embodiment of the present invention.
In the present embodiment, a case will be described in which two memories 41 and 42 that can simultaneously read and write four pixels are operated as a unit and read at eight pixels.
[0050]
In FIG. 2, pixels of numbers 00 to 03, numbers 08 to 11, numbers 16 to 19, and numbers 24 to 27 are stored at addresses 0, 1, 2, and 3, respectively.
In addition, pixels of numbers 04 to 07, numbers 12 to 15, numbers 20 to 23, and numbers 28 to 31 are stored in addresses 0, 1, 2, and 3 of the memory 42, respectively.
[0051]
Here, when setting the pixels 22 to 25 across the memories 41 and 42 to any one of the shift registers 37 to 40, the pixels 24 to 27 are first read from the address 3 of the memory 41, Pixels 20 to 23 are read from address 2 of the memory 42 at a time.
Next, these 8 pixels are rearranged by the pixel rearrangement circuit 43, and the pixels of numbers 22 to 25 are selected.
[0052]
That is, among the 8 pixels to be read, when a lower-numbered pixel is stored in the memory 41, the data group is read from the same address in the memories 41 and 42.
On the other hand, when a pixel with a lower number among the 8 pixels to be read is stored in the memory 42, the address of the memory 41 is set to the address +1 of the memory 42.
[0053]
As a result, it is possible to read out four pixels having consecutive numbers starting from a pixel having an arbitrary number.
Then, the desired four pixels are output in parallel to the PE array 45 by a shift register configuration similar to that of the first embodiment described above.
[0054]
Therefore, according to the present embodiment, division loss does not occur as in the case where a plurality of small-capacity memories shown in FIG. 10 are used, and a plurality of pixels (data) are obtained using two memories. A multi-port memory device capable of simultaneously reading from unrelated addresses can be configured, and an increase in chip area of the memory device itself can be suppressed.
Also, the top of the four pixels that are read simultaneously can be set to an arbitrary number, and can be applied to the telescopic search method shown in FIG.
[0055]
In the present embodiment, the case where two memories are used has been described, but the present invention is not limited to this.
That is, in this embodiment, a pixel larger than the number of pixels set in the shift register is read out using a plurality of memories, and a pixel rearrangement circuit cuts out a pixel with an arbitrary number as a head and sets it in the shift register. The point of output is essential.
[0056]
Therefore, it is not always necessary to limit the number of memories to two.
Further, it is not necessary to match the number of pixels read from each memory at the same time with the number of pixels in the horizontal direction of the template.
[0057]
【The invention's effect】
  As described above, the present invention has an input / output bit width capable of reading / writing a plurality of data constituting a data group at a time.Two1-port memory,Data rearrangement means for selecting and rearranging arbitrary data from each data constituting each data group read from the one-port memory, and outputting as a new data group;thisData sorting meansA shift register group consisting of a plurality of shift registers each having a predetermined number of shift stages arranged in parallel to each other is provided.Data sorting meansThe corresponding data groups sequentially read from each of the shift registers are sequentially held in each shift register, and a plurality of data constituting each data group are sequentially shifted out from each shift register one by one, so that each shift register can obtain a desired data group. Data is output in parallel at the same time.
  Therefore, by applying the pseudo multi-port memory device of the present invention to the full search method of motion vector search, division loss does not occur as in the case of using a plurality of conventional small-capacity memories.,A plurality of data (pixels) can be read simultaneously from unrelated addresses, and an increase in the chip area of the memory device itself can be suppressed.At the same time, pixels that are read out simultaneously can be stored in different memories, and can be applied to a telescopic search method..
[Brief description of the drawings]
FIG. 1 is a block diagram of a pseudo multi-port memory device according to a first embodiment of the present invention.
FIG. 2 is a block diagram of a pseudo multi-port memory device according to a second embodiment of the present invention.
FIG. 3 is an explanatory diagram showing a conventional full search method.
FIG. 4 is an explanatory diagram showing the operation of a PE array.
FIG. 5 is an explanatory diagram showing an invalid cycle generation mechanism.
FIG. 6 is an explanatory diagram showing a search area dividing method and a parallel operation technique in the method.
FIG. 7 is an explanatory diagram showing a motion vector correspondence / search area pixel broadcasting system;
FIG. 8 is an explanatory diagram illustrating a method for avoiding generation of invalid cycles in a two-dimensional image.
FIG. 9 is an explanatory diagram showing a MMSB calculation process for a two-dimensional image;
FIG. 10 is an explanatory diagram showing a full search method (first prior art) using a plurality of memories.
FIG. 11 is an explanatory diagram showing a telescopic search method (second prior art).
[Explanation of symbols]
16-19 ... Pixel, 32 ... Memory, 33-36 ... Pixel group, 37-40 ... Shift register, 41, 42 ... Memory, 43 ... Pixel rearrangement circuit, 44a-44d ... Path (arrow), 45 ... PE array .

Claims (1)

In a multi-port memory device capable of writing a data group consisting of a plurality of data at a time to a continuous address and reading the data group simultaneously from unrelated addresses,
Two one- port memories having an input / output bit width that can read and write a plurality of data constituting a data group at one time ;
Data rearrangement means for selecting and rearranging arbitrary data from each data constituting each data group read from the one-port memory, and outputting as a new data group;
The respectively arranged parallel to the data rearranging unit comprises a plurality of shift registers having a predetermined number of shift stages, holds the data group corresponding sequentially outputted from the data rearranging unit in order in each shift register, each of the data A pseudo multi-port comprising: a shift register group that simultaneously outputs desired data from each shift register in parallel by sequentially shifting out a plurality of data constituting the group from each shift register one by one Memory device.

Images