Abstract:
The present invention is directed to a method and apparatus for mapping a customer memory onto a plurality of physical memories. The apparatus may include: (a) a plurality of physical memories onto which a customer memory may be mapped, each of physical memories having a data width of m blocks, the customer memory having a data width of k blocks, and k and m being integers; (b) an address controller, communicatively coupled to a plurality of physical memories, for receiving first address information of the customer memory, for outputting second address information to a plurality of physical memories, and for outputting index information; (c) a data input controller, communicatively coupled to the address controller and a plurality of physical memories, for receiving data of the customer memory and the index information, and for outputting data with a data width of m blocks to a plurality of physical memories; and (d) a data output controller, communicatively coupled to a plurality of physical memories and to the address controller though a delay unit, for receiving the index information, for receiving output, with a width of said m blocks, of a plurality of physical memories, and for outputting the customer memory with a width of said k blocks.

Description:
FIELD OF THE INVENTION 
   The present invention generally relates to integrated circuits, and particularly to an apparatus and method for synthesizing a controller that automatically maps a customer&#39;s logic memories to given physical memories. 
   BACKGROUND OF THE INVENTION 
   Integrated circuit (IC) design on a chip, e.g., LSI Logic Corporation&#39;s RapidSlice™, and the like, usually contains physical memories with fixed capacities and fixed data widths. However, a customer&#39;s IC design may contain logic memories with different capacities and data widths. Conventionally, mapping customer&#39;s logic memories to given physical memories is done manually, which is a very tedious and time-consuming process. Therefore, it would be advantageous to provide a controller for automatically mapping a customer&#39;s arbitrary logic memory into physical memories on a chip. 
   SUMMARY OF THE INVENTION 
   Accordingly, the present invention is directed to an apparatus and method for synthesizing a controller that automatically maps customer&#39;s logic memories to given physical memories. In an exemplary aspect of the present invention, a method for mapping a customer memory onto a plurality of physical memories may include the following steps: (a) dividing input of a customer memory into k input blocks, where k is an integer; (b) converting k input blocks into m input blocks, where m is an integer; and (c) combining m input blocks into input to a plurality of physical memories, each physical memory having a data width of m blocks. 
   In an additional exemplary aspect of the present invention, an apparatus for mapping a customer memory onto a plurality of physical memories may include: (a) a plurality of physical memories onto which a customer memory may be mapped, each of physical memories having a data width of m blocks, the customer memory having a data width of k blocks, and k and m being integers; (b) an address controller, communicatively coupled to a plurality of physical memories, for receiving first address information of the customer memory, for outputting second address information to a plurality of physical memories, and for outputting index information; (c) a data input controller, communicatively coupled to the address controller and a plurality of physical memories, for receiving data of the customer memory and the index information, and for outputting data with a data width of m blocks to a plurality of physical memories; and (d) a data output controller, communicatively coupled to a plurality of physical memories and to the address controller though a delay unit, for receiving the index information, for receiving output, with a width of said m blocks, of a plurality of physical memories, and for outputting the customer memory with a width of said k blocks. 
   It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention as claimed. The accompanying drawings, which are incorporated in and constitute a part of the specification, illustrate an embodiment of the invention and together with the general description, serve to explain the principles of the invention. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The numerous advantages of the present invention may be better understood by those skilled in the art by reference to the accompanying figures in which: 
       FIG. 1  shows an exemplary snake algorithm for k=3 and m=4 in accordance with an exemplary embodiment of the present invention; 
       FIG. 2  shows an exemplary snake algorithm for k=5 and m=8 in accordance with an exemplary embodiment of the present invention; 
       FIG. 3  shows exemplary snake packing for k=7 and m=8 in accordance with an exemplary embodiment of the present invention; 
       FIG. 4  shows an exemplary circuit for realizing a snake algorithm in accordance with an exemplary embodiment of the present invention; 
       FIG. 5  shows an exemplary circuit for realizing x[i] for k=3 and m=4 in accordance with an exemplary embodiment of the present invention; 
       FIG. 6  shows an exemplary embodiment of the data input controller shown in  FIG. 4  in accordance with an exemplary embodiment of the present invention; 
       FIG. 7  shows an exemplary embodiment of the data output controller shown in  FIG. 4  in accordance with an exemplary embodiment of the present invention; and 
       FIG. 8  is a flow chart of an exemplary method for mapping a logic memory onto a plurality of physical memories with different data width in accordance with an exemplary embodiment of the present invention. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   Reference will now be made in detail to the presently preferred embodiments of the invention, examples of which are illustrated in the accompanying drawings. 
   Referring generally now to  FIGS. 1 through 7 , exemplary embodiments of the present invention are shown. One purpose of the present invention may be to synthesize a controller that automatically maps customer&#39;s logic memories into given physical memories. In one embodiment, an algorithm (and corresponding architecture) is constructed to map a given logic memory into a plurality of physical memories with a larger number of bits. 
   I. “Snake” Algorithm for Memory Packing 
   Suppose there is a customer&#39;s logic memory with a capacity cap and data width w, and two physical memories, each with a capacity tcap and data width tw, where
 
 w&lt;tw&lt; 2* w,    (1)
 
also suppose
 
 w=k *block_width,   (2-1)
 
and
 
 tw=m *block_width,   (2-2)
 
i.e., customer&#39;s logic memory data and physical memory data may be divided into blocks of the width block_width, where k and m are both integers, then the following may be assumed:
 
 m= 2^ t    (3)
 
for some t.
 
   From (1), the following may be obtained:
 
 k&lt;m&lt; 2 *k    (4)
 
According to (4), if m=4, then k=3; if m=8, then k=5 or k=7.
 
   For k=6, block_width may be increased to twice wide, and m and k may be decreased to half according to formulas (2-1) and (2-2). Thus, for the case k=6, m=4 and k=3 may still be obtained. 
   The algorithm of the present invention goes through data blocks (cells) of an original logic memory like a snake and packs the data to a wider memory consecutively. After all the data of the original logic memory are packed into the wider memory, the wider memory may be divided into two physical memories in the following way: all the cells with even addresses of the wider memory may be consecutively put into the first memory named Memory-1, and all the cells with odd addresses of the wider memory may be consecutively put into the second memory named Memory-2. 
     FIG. 1  shows an exemplary snake algorithm for k=3 and m=4 in accordance with an exemplary embodiment of the present invention. As shown, an original logic memory  102  is 3 block_width wide (k=3), and a wider memory  104  is 4 block_width wide (m=4). The snake algorithm of the present invention packs blocks of data from the memory  102  into data blocks of the memory  104  as follows. For address A=0, the 2nd (uppermost), the 1st, and the zero (0, lowest) blocks of data from the memory  102  are packed into the 3rd (uppermost), the 2nd, and the 1st blocks of the memory  104  with address=0, respectively. For address A=1, the 2nd (uppermost), the 1st, and the zero (0, lowest) blocks of data from the memory  102  are packed into the zero (0) block of the memory  104  with address=0, the 3rd block of the memory  104  with address=1, and the 2nd block of the memory  104  with address=1, respectively. Thus, the algorithm of the present invention goes through blocks from the original logic memory  102  like a snake and packs the data to the wider memory  104  consecutively. 
   As shown in  FIG. 1 , after all the blocks of data from the original logic memory  102  are packed into the wider memory  104 , the wider memory may be divided into two physical memories in the following way: all the cells with even addresses from the wider memory  104  may be consecutively put into a first memory  106  named Memory-1, and all the cells with odd addresses from the wider memory  104  may be consecutively put into a second memory  108  named Memory-2. For example, for address A=5, the uppermost (2nd) block of data from the original memory  102  may be put into the lowest (zero) block of the memory  108  with address A2=1, and the 1st and zero (0) blocks of data from the original memory  102  may be put into the 3rd (uppermost) and 2nd blocks of the memory  106  with address A1=2, respectively. 
   Similarly, for k=5 and m=8, an exemplary snake algorithm in accordance with an exemplary embodiment of the present invention is shown in  FIG. 2 , and for k=7 and m=8, exemplary snake packing in accordance with an exemplary embodiment of the present invention is shown in  FIG. 3 . 
   Obviously,
 
 A 1=( A+ 1)* k /(2* m ),   (5-1)
 
and
 
 A 2= A*k /(2* m ),   (5-2)
 
where A, A1, and A2 are all integers.
 
   Take into account formula (3), the following may be obtained:
 
 A 1=(( A+ 1)* k )&gt;&gt;( t+ 1),   (5a-1)
 
and
 
 A 2=( A*k )&gt;&gt;( t+ 1)   (5a-2)
 
where the symbol “&gt;&gt;” represents a Bitwise Right-Shift. Operation a&gt;&gt;b means a right shift of all digits of integer a by b times, and returns the value of a divided by 2 to the power of b, i.e., (a/2^b). For example, suppose a=25=(00011001) and b=3, then a&gt;&gt;b=3=(00000011). If a=(a 0 , a 1 , . . . , a k ), then a&gt;&gt;b=(0, . . . , 0, a 0 , a 1 , . . . ,a (k-b) ).
 
II. Circuit for Snake Algorithm Realization
 
   The process of packing is periodic with a period (2*m) because k is odd. For a cell of the original logic memory with address A=(i+2m), the packing actions may be repeated as for the cell with address A=i. For a cell with address A=(i+m), the packing actions may be repeated as for the cell with address A=i, with one change (the memories are permuted because k is odd). 
   For example, in  FIG. 1 , for address A=5=1+m the same packing actions may be performed as for A=1 (but memories are permuted), and for address A=9=1+2*m the same packing actions may be performed as for A=1 (without memory permutation). 
   The index of the address in the period may be denoted by index. Obviously,
 
index= A (mod(2* m ))   (6)
 
and from formula (3) the following may be obtained:
 
index= A &gt;&gt;( t+ 1)  (6a)
 
Thus, when A&lt;2*m, index=A.
 
   (1) Circuit 
     FIG. 4  shows an exemplary circuit  400  for realizing a snake algorithm in accordance with an exemplary embodiment of the present invention. As shown, the circuit may include an address controller  402 , a data input controller  404 , a write-enable controller  406 , a physical Memory-1  408 , a physical Memory-2  410 , a data output controller  412 , and a delay unit  414  such as a flip-flop, or the like. 
   The address controller  402  may receive an address A of an original logic memory as input. The address controller  402  may then output an address A1 of the physical Memory-1  408  based on formula (5a-1), an address A2 of the physical Memory-2  410  based on formula (5a-2), and an index based on formula (6a). 
   The data input controller  404  may receive DI (Data In) and the index as input. The DI may be a customer&#39;s arbitrary memory with a width of k block_width. The data input controller  404  may output DI 1  and DI 2 , both with a width of m block_width. Thus, the data input controller  404  converts the customer&#39;s memory with a width of k block_width into memories with a width of m block_width. The data input controller  404  will be described in detail below. 
   The physical Memory-1  408  and the physical Memory-2  410  may receive DI 1  and DI 2  as input and output DO 1  and DO 2 , respectively. Both DO 1  and DO 2  have a width of m block_width. 
   The data output controller  412  may receive a delayed index (Dindex obtained through the delay unit  414 ), DO 1  and DO 2  as input and may output DO, which has a width of k block_width. Thus, the data output controller  412  converts memories with a width of m block_width back into a memory with a width of k block_width. The data output controller  412  will be described in detail below. 
   The write-enable controller  406  is the same as the data input controller  404  except wires WE, WE 1  and WE 2  are used instead of DI, DI 1  and DI 2 , respectively. 
   Thus, the circuit  400  automatically maps a customer&#39;s logic memory with a data width of k block_width to a plurality of physical memories, each with a data width of m block_width. From the customer&#39;s perspective, however, the customer may only see DI and DO, both have a data width of k block_width. The customer may not realize that the logic memory has been mapped to physical memories with a different data width. 
   (2) Data Input Controller 
     FIG. 6  shows an exemplary embodiment of the data input controller  404  shown in  FIG. 4  in accordance with an exemplary embodiment of the present invention. 
   The i-th block of the input data (i.e., DI in  FIG. 4 ) to the data input controller  404  may be denoted by block[i], where 0≦i&lt;k Thus, block[k−1] represents the uppermost block of the input, and block[0] represents the lowest block of the input. 
   The content of i-th block of the Memory-1 for index=j may be denoted by mem1_data[i][j], and the content of i-th block of the Memory-2 for index=j may be denoted by mem2_data[i][j], where 0≦j&lt;2*m and 0≦i&lt;m. 
   For the semi-period m, the following may be obtained:
 
mem1_data[ i][j+m ]=mem2_data[ i][j] 
 
and
 
mem2_data[ i][j+m ]=mem1_data[ i][j] 
 
When 0≦j&lt;m, because the snake subsequence is periodic the memories may be permuted.
 
   For the full period 2*m, the following may be obtained
 
mem1_data[ i][j+ 2* m ]=mem1_data[ i][j] 
 
and
 
mem2_data[ i][j+ 2* m ]=mem2_data[ i][j]. 
 
   For example, for m=4 and k=3, the following may be obtained:
 
mem1_data[0][0]=0,
 
mem1_data[1][0]=block[0],
 
mem1_data[2][0]=block[1],
 
mem1_data[3][0]=block[2],
 
and
 
mem2_data[ i][ 0]=0 for any i,
 
because all blocks with the address 0 belongs to Memory-1 (see, e.g.,  FIG. 1 ).
 
   In addition, for m=4 and k=3, the following may be obtained:
 
mem1_data[0][2]=0,
 
mem1_data[1][2]=0,
 
mem1_data[2][2]=0,
 
mem1_data[3][2]=block[0]
 
mem2_data[0][2]=block[1],
 
mem2_data[1][2]=block[2],
 
mem2_data[2][2]=0,
 
and
 
mem2_data[3][2]=0.
 
   As shown in  FIG. 6 , the output of the decoder for index may be denoted by ind[2*m−1], . . . , ind[0]. The decoder realizes the system of all the conjunctions with (t+1) variables where t is the same as in the formula (3). For example, for index=4, ind[4]=1 and ind[i]=0 for other i. 
   The content of i-th input block for Memory-1 may be denoted by x[i], and the content of i-th input block for Memory-2 may be denoted by y[i], where 0≦i&lt;m. Thus,
 
x[i]=((mem1_data[i][0] &amp; ind[0])            (mem1_data[i][1] &amp; ind[1]          . . .          (mem1_data[i][m−1] &amp; ind[m−1]))         ((mem2_data[i][0] &amp; ind[m])         (mem2_data[i][1] &amp; ind[m+1]) . . .          (mem2_data[i][m−1] &amp; ind[2m−1])),
 
and
 
y[i]=((mem2_data[i][0] &amp; ind[0])          (mem2_data[i][1] &amp; ind [1])          . . .          (mem2_data[i][m−1] &amp; ind[m−1]))         ((mem1_data[i][0] &amp; ind[m])          (mem1_data[i][1] &amp; ind[m+1]) . . .          (mem1_data[i][m−1] &amp; ind[2m−1])),
 
where “&amp;” represents a logical conjunction, and “         ” represents a logic disjunction.

   Note, based on the above two formulas, a tree of disjunctions with a minimal depth to realize x[i] and y[i] may be constructed. For example,  FIG. 5  shows an exemplary circuit for realizing x[i] for k=3 and m=4 in accordance with an exemplary embodiment of the present invention. Note in  FIG. 5 , every bus has a width of block_width. 
   Referring back to  FIG. 6 , the output x is the result of the concatenation of x[m−1], x[k−2], . . . , x[1], x[0], and the output y is the result of the concatenation of y[m−1], y[k−2], . . . , y[1], y[0]. It is noted that the output x and y in  FIG. 6  are equivalent to the output DI 1  and DI 2  of the data input controller  404  in  FIG. 4 , respectively. 
   (3) Data Output Controller 
     FIG. 7  shows an exemplary embodiment of the data output controller  412  shown in  FIG. 4  in accordance with an exemplary embodiment of the present invention. 
   As described previously, the i-th block of the original input data (i.e., DI in  FIG. 4 ) is denoted by block[i], where 0≦i&lt;k. The content of the i-th block of the original memory for index=j may be denoted by memdata[i][j], where 0≦j&lt;2*m and 0≦i&lt;k. For example, in  FIG. 1 , for m=4 and k=3, the following may be obtained:
 
memdata[0][1]=mem2_block[2],
 
memdata[1][1]=mem2_block[3],
 
memdata[2][1]=mem1_block[0],
 
where mem1_block[i] represents the i-th block from the Memory-1  106  and mem2_block[i] represents the i-th block from the Memory-2  108 .
 
   Referring to  FIG. 7 , the output of the decoder for index may be denoted by ind[2*m−1], . . . , ind[0], as previously described. The content of the i-th output block from the data output controller  412  may be denoted by z[i], where 0≦i&lt;k. Thus,
 
 z[i ]=(memdata[ i ][0] &amp; ind[0])           (memdata[ i ][1] &amp; ind[1])          . . .          (memdata[i][2m−1] &amp; ind[2m−1]).
 
Note, based on this formula, a tree of disjunctions with a minimal depth to realize z[i] may be constructed, similar to that shown in  FIG. 5 .

   The output z in  FIG. 7  is the result of the concatenation of z[k−1], z[k−2], . . . , z[1], z[0]. 
     FIG. 8  is a flow chart of an exemplary process  800  for mapping a logic memory onto a plurality of physical memories with different data width in accordance with an exemplary embodiment of the present invention. The process may start with step  802  in which input of a customer&#39;s (logic) memory is divided into k blocks. The k input blocks may then be converted into m input blocks  804 . The m input blocks may be combined into input to a plurality of physical memories, each physical memory having a data width of m blocks  806 . Preferably, a plurality of physical memories are two physical memories. Output of a plurality of physical memories may be read for given input  808 . Output of each physical memory may be divided into m output blocks  810 . The m output blocks may be converted into k output blocks  812 . The k output blocks may then be combined into output of the customer&#39;s memory  814 . 
   The process  800  shown in  FIG. 8  may be implemented in the circuit  400  shown in  FIG. 4 . Specifically, the steps  802 ,  804 , and  806  may be implemented by the data input controller  404 , and the steps  810 ,  812 , and  814  may be implemented by the data output controller  412 . It is understood that the process  800  shown in  FIG. 8  may be implemented in other circuits as may be contemplated by a person of ordinary skill in the art without departing from the scope and spirit of the present invention. 
   It is to be noted that the above described embodiments according to the present invention may be conveniently implemented using conventional general purpose digital computers programmed according to the teachings of the present specification, as will be apparent to those skilled in the computer art. Appropriate software coding may readily be prepared by skilled programmers based on the teachings of the present disclosure, as will be apparent to those skilled in the software art. 
   It is to be understood that the present invention may be conveniently implemented in forms of software package. Such a software package may be a computer program product which employs a storage medium including stored computer code which is used to program a computer to perform the disclosed function and process of the present invention. The storage medium may include, but is not limited to, any type of conventional floppy disks, optical disks, CD-ROMs, magneto-optical disks, ROMs, RAMs, EPROMs, EEPROMs, magnetic or optical cards, or any other suitable media for storing electronic instructions. 
   It is understood that the specific order or hierarchy of steps in the processes disclosed is an example of exemplary approaches. Based upon design preferences, it is understood that the specific order or hierarchy of steps in the processes may be rearranged while remaining within the scope of the present invention. The accompanying method claims present elements of the various steps in a sample order, and are not meant to be limited to the specific order or hierarchy presented. 
   It is believed that the present invention and many of its attendant advantages will be understood by the foregoing description. It is also believed that it will be apparent that various changes may be made in the form, construction and arrangement of the components thereof without departing from the scope and spirit of the invention or without sacrificing all of its material advantages. The form herein before described being merely an explanatory embodiment thereof, it is the intention of the following claims to encompass and include such changes.