Computer graphics processing and selective visual display system – Computer graphics display memory system – Addressing
Reexamination Certificate
2002-01-11
2004-11-16
Tung, Kee M. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics display memory system
Addressing
C345S520000, C345S531000, C345S572000, C711S202000
Reexamination Certificate
active
06819326
ABSTRACT:
The invention relates to a memory address translation unit designed to generate a mapping to translate a logical address of a data element of a data-block, to a physical address of a data cell of a data-unit, being part of a memory device, comprising an analyzer for analyzing properties of the memory device and properties of data-blocks, and a mapping generator for generating the mapping based on output of the analyzer.
The invention further relates to an image processing apparatus comprising such a memory address translation unit.
The invention further relates to a method to generate a mapping to translate a logical address of a data element of a data-block, to a physical address of a data cell of a data-unit, being part of a memory device, comprising a first step to analyze properties of the memory device and properties of data-blocks, and a second step to generate the mapping based on results of the first step.
One type of prior art memory address translation unit is disclosed in the article Array Address Translation for SDRAM-based Video Processing Application, in Visual Communications and Image Processing 2000, Proceedings of SPIE- The International Society for Optical Engineering, Vol. 4067, part two, Year 2000, pages 922.931.
As the resolution of video processing applications becomes high, video signal processors have to deal with a large amount of data within a tightly bounded time. To obtain high memory bandwidth, some memory devices, e.g. SDRAM, use an important feature: the burst access mode. The burst access mode makes it possible to access a number of consecutive data words by giving one read or write command. Because the reading of dynamic memory cells is destructive, the content in a row of cells in the memory bank is copied into a row of static memory cells, the page registers. Subsequently, access to this row is provided. Similarly, when another row has to be accessed, first the content in the row of static memory cells has to be copied back into the original, destructed, dynamic cells. These actions, referred to as row-activations and respectively pre-charges, consume valuable time in which the array of memory cells, i.e. a bank, cannot be accessed. To optimize the utilization of the memory-bus bandwidth, data should only be accessed at the grain size of a data burst, e.g. eight words. These data bursts represent non-overlapping data-units in the memory device which can only be accessed as a whole. Because a request for data may concern only a few bytes, i.e. the data-units are larger than the requested data blocks and a request for data can involve more than one data-unit in the memory device, the amount of transfer overhead may be significant. To minimize this overhead a good mapping from logical addresses to physical addresses is important. To illustrate this the following example is provided. A video processing algorithm processes two-dimensional arrays of 8×8 pixels. Such two-dimensional arrays are represented as data-blocks. If the addresses of the various pixels are linearly mapped to physical addresses, accessing such a data-block causes seven row-changes. However if the pixels of such 8×8 data-block are kept in one data-unit of the memory device, accessing such a 8×8 data-block does not induce any row-changes.
From the article Array Address Translation for SDRAM-based Video Processing Application, in Visual Communications and Image Processing 2000, Proceedings of SPE- The International Society for Optical Engineering, Vol. 4067, part two, Year 2000, pages 922-931, is known a memory address translation unit for reducing the number of memory cycles in multi-dimensional video processing applications. In this article an algorithm is described that searches for a suitable window size considering the memory access patterns and memory parameters. A logical array, e.g. a video frame, is partitioned into a set of rectangles called windows. The window size determines how pixels from e.g. a video frame are divided into a number of groups of related pixels. In other words, a video frame is split in a number of regions, wherein the spatial dimensions of such a region correspond to the dimensions of a window. All pixels from such a region belong to one group of related pixels. Each group of related pixels is stored in a row of the memory device. The length of a window corresponds with the number of pixels in horizontal direction. The height of a window corresponds with the number of pixels in vertical direction. Address translation means determination of a physical address for a logical address. To store a data element into a memory device, a physical address of a data-cell, being a part of a data-unit, has to be calculated for the logical address of the data element. Each pixel has a logical address. This address might be the set of co-ordinates of the pixel within the video frame. If it is required that a group of related pixels has to be stored in one data-unit, then this determines the calculation of the physical addresses related to the pixels to be stored. The pixels from a group of related pixels should be mapped to consecutive physical addresses. In the article a mapping of video data into memory is proposed related to analyzing the application software.
The consequences of estimating the window size by analyzing the application software only, is that the estimated window size is not optimal. This results in a mapping of logical to physical addresses that is not optimal. The effect is that a group of related pixels is not stored in one data-unit but spread over several data-units. One data-block request, to access such a group of related pixels has a significant memory transfer overhead. The memory device is invoked several times, instead of performing one burst access.
Besides the consequence of estimating the window size by analyzing the application software only, without considering data dependencies, it is not always possible to analyze the application software, because the code might not be available. That may be an issue if the code, or parts of it, has been developed by a third party.
It is a first object of the invention to provide a memory address translation unit of the kind described in the opening paragraph with an improved mapping to translate a logical address of a data element of a data-block to a physical address of a data cell of a data-unit.
It is a second object of the invention to provide an image processing apparatus comprising such a memory address translation unit.
It is a third object of the invention to provide a method of the kind described in the opening paragraph with improved mapping to translate a logical address of a data element of a data-block to a physical address of a data cell of a data-unit.
The first object of the invention is achieved in that the analyzer analyzes values of properties of actual data-blocks that are actually stored to or retrieved from the memory device during a predetermined period of time. Values of properties of data-blocks that are actually stored or retrieved runtime, can differ from values of properties of data-blocks from which it is assumed, based on analysis of the application software only, that they will be stored or retrieved. Furthermore the probability of occurrence of the data-blocks is impossible to derive by analyzing the application software, without considering data dependencies. Most application programs contain a number of loops and conditional tests. The consequence of these conditional tests is that the program has a number of parallel paths. The input data of the program determines which paths are actually taken. In other words the input data to be processed by an application program strongly influences the internal variables of the program and thus the memory accesses. This happens for example in an MPEG decoder. It strongly depends on the strategy taken by the encoder what type of data-blocks the MPEG decoder will have as its operands.
An embodiment of the memory address translation unit according to the invention is described in claim
2
. An important prop
Koninklijke Philips Electronics , N.V.
Tung Kee M.
Ure Michael J.
LandOfFree
Memory address translation for image processing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory address translation for image processing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory address translation for image processing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3300390