Abstract:
A method and system for virtual memory translation of data represented in a multidimensional coordinate system when the physical memory may be located in more than one physical memory location. The translation of one or more virtual addresses into one or more accesses to one or more physical memories is achieved by representing each address of each element of a memory of the one or more physical memories as a point in a Cartesian coordinate system wherein consecutive points in the Cartesian coordinate system represent virtual memory addresses corresponding to elements from different physical memories of the one or more physical memories. Points in the Cartesian coordinate system are translated into one or more corresponding physical memory addresses, and read or write operations may be performed relative to these physical memory addresses. Multiple read or write operations may be performed during a single clock cycle through the use of parallel accesses of the one or more physical memories. Alternatively, multiple read or write operations may be performed in a pipelined architecture.

Description:
TECHNICAL FIELD  
         [0001]    This invention relates generally to the field of multidimensional digital data processing, and more specifically to the use of memory translation devices when multiple memory modules are present.  
         BACKGROUND OF THE INVENTION  
         [0002]    In hardware for performing multimedia signal processing, there may be multiple memory modules that contain the data required for multimedia signal processing operations. Because the data may be stored in more than one memory module, there are programmatic issues related to retrieving the data in a fast and efficient manner. The data required for a multimedia application may be located in more than one memory module because of the requirements for the data storage, or because of bandwidth limitations of the multimedia signal processing system.  
           [0003]    Referring to FIG. 1, a general multimedia signal processing architecture  100  is shown, according to the prior art. An input/output module  110  forwards data to multimedia processor  120 , and also receives processed data from multimedia processor  120 . Multimedia processor  120  performs signal processing operations on input data and stores the results in one or more memory modules  150 . The input data to multimedia processor  120  may originate from input/output module  110  or from the one or more memory modules  150 . A processor/memory interface  130  handles the interactions between the one or more memory modules  150  and the multimedia processor  120 . The functionality of processor/memory interface  130  can become complicated when multimedia processor  120  requires data that is stored in more than one memory module (for example memory module  135  and memory module  140 ). Accessing data stored in more than one memory module can increase the coding required in processor/memory interface  130 , and can increase application complexity.  
           [0004]    An example of a system that stores data in multiple memory modules due to bandwidth limitations is a motion estimating unit in a video encoding application. In this application, pixel data have to be stored in multiple memory modules in order to increase the bandwidth of the data transferred to the motion estimation unit. In this example, as well as other applications, it is desirable to achieve multiple memory accesses per clock cycle. This design consideration impacts the design of the interface between the multimedia processing and the memory modules since coding efficiency is related to the number of parallel memory fetches that can occur within a single clock cycle.  
           [0005]    A programmatic approach that abstracts the interface to a plurality of memory modules so that multiple memory modules which may contain heterogeneous data could be accessed by reusing the same section of code would be advantageous. It would also be advantageous if this section of code could be executed within a single clock cycle, and would further remove the physical addresses of the plurality of memory modules from the multimedia processor. A common approach to abstracting the plurality of physical addresses is to use a virtual address translation application that is part of the processor/memory interface. Virtual address translation allows the multimedia processor to represent the plurality of memory modules using a convenient representation which is translated to the physical addresses of the data contained in memory as necessary.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0006]    The features of the invention believed to be novel are set forth with particularity in the appended claims. The invention itself however, both as to organization and method of operation, together with objects and advantages thereof, may be best understood by reference to the following detailed description of the invention, which describes certain exemplary embodiments of the invention, taken in conjunction with the accompanying drawings in which:  
         [0007]    [0007]FIG. 1 is a general multimedia signal processing system, according to the prior art.  
         [0008]    [0008]FIG. 2 is a diagram of an exemplary memory interface, according to a certain embodiment of the present invention.  
         [0009]    [0009]FIG. 3 is a high level block diagram of the VMTU integration with a plurality of memory modules, according to a certain embodiment of the present invention.  
         [0010]    [0010]FIG. 4 is a more detailed block diagram of the VMTU integration with a plurality of memory modules, according to a certain embodiment of the present invention.  
         [0011]    [0011]FIG. 5 is a diagram of,the address generator logic for a single port, according to a certain aspect of the present invention.  
         [0012]    [0012]FIG. 6 is a schematic diagram of the input logic coupled to the plurality of memory modules, according to a certain embodiment of the present invention.  
         [0013]    [0013]FIG. 7 is a schematic diagram of the output logic coupled to the plurality of memory modules, according to a certain embodiment of the present invention.  
         [0014]    [0014]FIG. 8 is a flow diagram of a VMTU read operation, according to a certain embodiment of the present invention.  
         [0015]    [0015]FIG. 9 is a flow diagram of a VMTU write operation, according to a certain embodiment of the present invention.  
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0016]    While this invention is susceptible of embodiment in many different forms, there is shown in the drawings and will herein be described in detail specific embodiments, with the understanding that the present disclosure is to be considered as an example of the principles of the invention and not intended to limit the invention to the specific embodiments shown and described. In the description below, like reference numerals are used to describe the same, similar or corresponding parts in the several views of the drawings.  
         [0017]    Referring now to FIG. 2, a diagram of an exemplary memory interface  200  is shown, according to a certain embodiment of the present invention. A two dimensional array of macroblocks  260  is shown, where a representative macroblock  250  of the two dimensional array of macroblocks  260  further comprises a repeating pattern of memory element of memory module A  210 , memory element of memory module B  220 , memory element of memory module C  230 , and memory element of memory module D  240 . The four memory modules are oriented within a macroblock so that contiguous memory modules represent distinct memory elements. So, in the exemplary embodiment of FIG. 2, an element of memory module A  210  is not adjacent to any other element of memory module A  210 . It is noted that the memory orientation shown in FIG. 2 is exemplary, and other memory arrangements are possible without departing from the spirit and scope of the present invention. For example, more than four memory modules could be used while still maintaining a separation between elements of a same memory module. It is also possible that the memory modules can be represented within a macroblock of the two dimensional array of macroblocks without using a repeating pattern of memory elements within the macroblock. It is also possible that the array of macroblocks have a dimensionality greater than two without departing from the spirit and scope of the present invention.  
         [0018]    A user interfacing with the two dimensional array of macroblocks  260  may specify the two dimensional coordinates of an element within the two dimensional array of macroblocks  260 . This coordinate specification is simpler than requiring the programmer to directly specify a physical memory address of the memory location represented by the element within the two dimensional array of macroblocks  260 . An additional benefit of using a Cartesian coordinate representation of memory elements within one or more memory modules is that multiple memory elements from multiple memory modules may be concurrently returned to the user after the user requests a single memory element. The concurrent return of multiple memory elements from multiple memory modules increases a processing bandwidth of a system incorporating the two dimensional array of macroblocks  260 , since multiple memory requests may be performed on a single clock cycle. As an example, referring again to FIG. 2, a user may select the lower left D memory element from macroblock  260  and one or more memory elements can then be selected and returned to the user. These one or more memory elements need not be in the same macroblock of the two dimensional array of macroblocks  260 . In a preferred embodiment of the present invention, a single two dimensional coordinate selection results in a quad group, the top two memory elements within a quad group, or the bottom two elements within a quad group being selected, where a quad group represents a single contiguous memory element from each memory module (an example is the ABCD macroblock  250  of FIG. 2).  
         [0019]    Referring now to FIG. 3 a high-level block diagram  300  of a Virtual Memory Translation Unit (VMTU) integration with a plurality of memory modules is shown, according to a certain embodiment of the present invention. Memory requests are received on a plurality of input ports  330  by VMTU  320 . VMTU  320  processes these memory requests to produce a plurality of memory addresses, and communicates the plurality of memory addresses with a corresponding plurality of memory modules  310 . The plurality of memory modules  310  returns a plurality of data requested by VMTU  320  corresponding to the plurality of memory addresses. VMTU  320  then routs the plurality of data onto a plurality of output ports  340 . In a preferred embodiment of the present invention, memory requests received by the plurality of input ports  330  may be in linear mode (direct memory addresses), or in xy coordinate mode without departing from the spirit and scope of the present invention. If a memory request is in linear mode, then VMTU  320  passes this memory request directly to a memory module of the plurality of memory modules. If a memory request is in xy coordinate mode, then VMTU  320  first translates the memory request to an address readable by a memory module of the plurality of memory modules. One of skill in the art will recognize that while xy coordinates are discussed, the present invention may be implemented in three or more dimensions without departing from the spirit and scope of the present invention.  
         [0020]    Referring now to FIG. 4 a more detailed block diagram  400  of the VMTU integration with a plurality of memory modules is shown, according to a certain embodiment of the present invention. Input ports  330 , comprising input port  405 , input port  410 , and input port  415 , are coupled to an xy to linear address generator block  420 . xy to linear address generator block  420  further comprises a plurality of xy to linear address generators, where each xy to linear address generator of the plurality of xy to linear address generators is coupled to a corresponding input port. Each xy to linear address generator of the plurality of xy to linear address generators receives as input an xy address, a control signal indicating which memory macroblock the xy address corresponds to, and a flag indicating the number of associated memory elements that are to be accessed in addition to the specified xy address. The outputs of xy to linear address generator block  420  are coupled to a multiplexer block  425 . Multiplexer block  425  determines which memory module of the plurality of memory modules  310  a particular xy address corresponds to. The plurality of memory modules  310  output the data corresponding to the plurality of memory addresses and a plurality of control signals received from multiplexer block  425 . The data output from the plurality of memory modules  310  is coupled to a multiplexer block  430 . Multiplexer block  430  uses the plurality of control signals to couple the data to the plurality of output ports  340 . In a preferred embodiment of the present invention, xy to linear address generator block  240 , multiplexer block  425 , and multiplexer block  430  are contained within VMTU  320 .  
         [0021]    Referring now to FIG. 5, a diagram of the address generator logic  500  for a single port is shown, according to a certain aspect of the present invention. An xy address is received by this port via input port  405 . Split adjust block  510  receives the xy address from input port  405 . Split adjust block  510  processes the xy address and outputs xy addresses corresponding to a top-left pixel. In a preferred embodiment of the present invention split adjust block  510  contains two incrementors to perform the split adjust. The top left pixel is then coupled to an xy to linear converter  515 , a top-right pixel which is then coupled to an xy to linear converter  520 , a bottom left pixel which is then coupled to an xy to linear converter  525 , and a bottom right pixel which is then coupled to an xy to linear converter  530 . Each of the xy to linear converters ( 515 ,  520 ,  525 ,  530 ) rearrange bits to generate linear addresses from the input xy address. xy to linear converters  515 ,  520 ,  525 , and  530  are coupled to a address/chip enable generator  535 . Address/chip enable generator  535  takes linear addresses as input and outputs corresponding physical memory addresses  545  and a plurality of chip enable signals  550  for the corresponding plurality of memory modules  310 . In a preferred embodiment of the present invention, address/chip enable generator  535  and address/chip enable generator  540  determine physical memory addresses by rearranging the bits of the output of xy to linear converters  515 ,  520 ,  525 ,  520 .  
         [0022]    It should be noted that one of skill in the art will recognize that although split adjust block  510  outputs four xy address for a given input xy address, any number of xy addresses could be determined relative to a given xy address without departing from the spirit and scope of the present invention. It is also noted that the output xy addresses of split adjust block  510  can be non-contiguous without departing from the spirit and scope of the present invention.  
         [0023]    Referring now to FIG. 6, a schematic diagram of the input logic  600  coupled to the plurality of memory modules  310  is shown, according to a certain embodiment of the present invention. Memory module  660  of the plurality of memory modules  310  is coupled to a multiplexer  650 . Multiplexer  650  receives as input one or more linear addresses  620  coupled at multiplexer  640 , as well as one or more generated addresses  610  coupled at multiplexer  635 . Memory module  660  also receives one or more chip select or enable signals  630  that are combined in an OR block  645 . In a preferred embodiment of the present invention, each memory module of the plurality of memory modules  310  is coupled to one or more translated addresses similar in form to the one or more translated addresses  610  and one or more linear addresses similar in form to the one or more linear addresses  630 . In a preferred embodiment of the present invention, multiplexer  640  and multiplexer  650  are coupled to the one or more chip enable signals  630 . When a chip enable signal of the one or more chip enable signals  630  is active, the corresponding address is passed to memory module  660 . Memory module  660  also receives the chip enable signal via OR block  645 .  
         [0024]    Referring now to FIG. 7, a schematic diagram of the output logic  700  coupled to the plurality of memory modules  310  is shown, according to a certain embodiment of the present invention. A plurality of output data  710  is transmitted from the plurality of memory modules  310  to multiplexer  725 . Linear data  720  is then coupled to the output of multiplexer  725  at multiplexer  730 . It is noted that one of skill in the art will realize that the number of inputs to multiplexer  725  and multiplexer  730  is exemplary, and a different number of output data from the plurality of memory modules  310  could be used without departing from the spirit and scope of the present invention. It is further noted that linear data  720  is coupled to multiplexer  730  since certain embodiments of the present invention allow the programmer or user to bypass the VMTU and use the linear addresses.  
         [0025]    The output of multiplexer  730  is then coupled to output port  740  of one or more output ports. In accordance with certain embodiments of the present invention, each output port of the one or more output ports may operate in linear or VMTU mode. In a preferred embodiment of the present invention, each port of the one or more output ports determines linear mode or VMTU mode independent of the remaining one or more output ports. It should also be noted that the output of one or more of multiplexer  725  and multiplexer  730  is determined by the value of one or more corresponding enable signals. It is also noted that one of skill in the art will recognize that different output ports of the one or more output ports may be operable to output different parts of the plurality of memory modules  310  without departing from the spirit and scope of the present invention.  
         [0026]    Referring now to FIG. 8, a flow diagram of a VMTU read operation  800  is shown, according to a certain embodiment of the present invention. As in block  810 , a programmer or agent external to the VMTU passes an xy address to the VMTU. The xy address is split into multiple xy addresses (block  820 ), and each of the split xy addresses are translated into a linear address plus an enable, or chip select signal (block  830 ). The plurality of enable signals are used to determine the correct memory location within the plurality of memory modules  310  where the read operation is to occur. At each memory module of the plurality of memory modules  310 , the plurality of enable signals are used to select between one or more linear addresses corresponding to physical memory locations within each memory module of the plurality of memory modules  310  (block  840 ). The plurality of enable signals are then used to select the correct memory module for each output port (block  850 ). The read data is then returned on the plurality of output ports (block  860 ).  
         [0027]    Referring now to FIG. 9, a flow diagram of a VMTU write operation  900  is shown, according to a certain embodiment of the present invention. As in block  910 , a programmer or agent external to the VMTU sends an xy address as well as one or more data to the VMTU. The xy address is split into multiple xy addresses (block  920 ), and each of the split xy addresses are translated into a linear address plus an enable, or chip select signal (block  930 ). The plurality of enable signals are used to determine the correct memory location where the write operation is to occur. At each memory module of plurality of memory modules  310 , the plurality of enable signals are used to select between one or more linear addresses corresponding to physical memory locations within each memory module of the plurality of memory modules  310  (block  940 ). The plurality of enable signals are then used to select the correct memory module for each input data (block  950 ). Each of the one or more write data is then written to the appropriate memory location (block  860 ).  
         [0028]    It is noted that a pipelined instruction architecture could also be used to provide the translation of one or more virtual addresses into accesses of one or more physical memories without departing from the spirit and scope of the present invention. The use of a pipeline allows the concurrent execution of one or more steps in the translation of the one or more virtual addresses into one or more physical addresses. In a certain embodiment of the present invention, the pipeline is divided into three stages. During a first stage, an xy address is split into one or more xy addresses, each of the xy addresses are converted to a linear address, and if a write cycle is occurring then one or more write data corresponding to the xy addresses are routed to the correct memory locations. During a second stage, the physical memory locations are accessed to perform a plurality of write operations during a write cycle and a plurality of read operations during a read cycle. It is noted that in a preferred embodiment of the present invention, the plurality of read operations and the plurality of write operations do not overlap in time. During a third stage, a plurality of read data corresponding to the plurality of read operations are routed to a corresponding plurality of output ports. It is further noted that one of skill in the art will recognize that a different number of stages could be used and the functionality to perform the translation of the one or more virtual addresses into accesses of one or more physical memories could be separated into the stages in a different manner than just described without departing from the spirit and scope of the present invention.  
         [0029]    Those skilled in the art will appreciate that the program steps and associated data used to implement the embodiments described above can be implemented using disc storage as well as other forms of storage such as for example Read Only Memory (ROM) devices, Random Access Memory (RAM) devices; optical storage elements, magnetic storage elements, magneto-optical storage elements, flash memory and/or other equivalent storage technologies without departing from the present invention. Such alternative storage devices should be considered equivalents.  
         [0030]    The present invention, as described in embodiments herein, is implemented using a programmed processor executing programming instructions that are broadly described above in flow chart form that can be stored on any suitable electronic storage medium or transmitted over any suitable electronic communication medium. However, those skilled in the art will appreciate that the processes described above can be implemented in any number of variations and in many suitable programming languages without departing from the present invention. For example, the order of certain operations carried out can often be varied, additional operations can be added or operations can be deleted without departing from the invention. Error trapping can be added and/or enhanced and variations can be made in user interface and information presentation without departing from the present invention. Such variations are contemplated and considered equivalent.  
         [0031]    While the invention has been described in conjunction with specific embodiments, it is evident that many alternatives, modifications, permutations and variations will become apparent to those of ordinary skill in the art in light of the foregoing description. Accordingly, it is intended that the present invention embrace all such alternatives, modifications and variations as fall within the scope of the appended claims.