Patent Publication Number: US-6711494-B2

Title: Data formatter for shifting data to correct data lanes

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims priority to U.S. Provisional Application Ser. No. 60/309,064, entitled DATA FORMATTER and filed on Jul. 30, 2001. 
    
    
     BACKGROUND 
     In computer systems, a central processing unit (CPU) may access memory by providing an address that indicates a unique location of a group of memory cells that collectively store a data element. A number of operations may be taken when performing an initial access to memory. These operations may make the initial access relatively slow. For example, certain control signals may be issued to begin the process. Next, the address may be sent to the memory. Then, the data itself may be transferred. Because of this operational overhead, or latency, the initial access to memory may take a relatively long time, e.g., four to seven clock cycles in many devices. 
     To reduce the latency of the memory, some memory devices read a block of data including four 64-bit words (256 bits or 32 bytes) from memory consecutively for each access. An advantage of this “burst access mode,” or “bursting,” is avoiding repetition of the overhead of the initial access for the subsequent three accesses. The subsequent accesses may be shortened to one to three clock cycles instead of four to seven clock cycles. 
     A memory device that supports bursting may not be byte-addressable. Instead of accessing a memory location at a specific byte address, the memory device may retrieve a multi-byte block of data elements. Some of the data elements in the block of data may not be valid for the request. 
     A data formatter may be used to take a multi-block of data from a source, such as a random access memory (RAM), and break up the multi-byte block into multiple smaller blocks. Each of the smaller blocks can then be sent to the appropriate local memory addresses. 
     A controlling program determines the size of each of the smaller blocks and their destination addresses. The smaller blocks may be broken up on any byte boundary within the larger block. The destination addresses may also be located at any byte boundary. This complicates the data formatter&#39;s responsibilities. No matter which byte lanes the data elements are in when they come from the providing RAM, the data formatter must ensure that these bytes are in the correct byte lanes for writing to a new address. 
     SUMMARY 
     A data formatter includes a shift register and a pointer manager. A providing random access memory (RAM) stores data from a multi-byte block of data, retrieved in a burst access operation to a memory, to be written to local memory addresses. The shift register receives data from the providing RAM and shifts that data in response to reading data from the providing RAM and writing data to a receiving first-in first-out (FIFO) memory. A pointer manager maintains a pointer that points to a first valid byte in a sub-block of data into the correct bytes lanes of the FIFO by moving the pointer as data is shifted into and out of the shift register. 
     The pointer manager generates indicators based on the pointer value which notify the controlling program that the shift register is full (or almost full) or empty (or almost empty). 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of a memory access system according to an embodiment. 
     FIG. 2 is a block diagram of a shift register including a pointer in a movable window of data elements to be written. 
     FIG. 3 is a flowchart describing a pointer management operation according to an embodiment. 
     FIGS. 4 to  7  are a block diagrams of the shift register of FIG. 2 including the window in different positions corresponding to different phases of an exemplary pointer management operation. 
    
    
     DETAILED DESCRIPTION 
     FIG. 1 illustrates a memory access system  100  including a data formatter  102  according to an embodiment. A memory controller  104  may read data from a memory device  106  in a “burst access” mode in which multi-byte blocks of data are retrieved from memory and loaded temporarily into another memory device, such as a random access memory (RAM), before being sent to local memory addresses. Some of the data elements in the block of data may not be valid for the request. Also, valid blocks of data and their destination addresses may be located on any byte boundary in the burst-accessed multi-byte blocks. 
     The data formatter  102  may take a block of data from a providing RAM  108  and send the data to one or more local memory addresses. The data formatter  102  is capable of breaking up the larger multi-byte block of data read from providing RAM  108  into multiple smaller blocks at the appropriate byte boundaries within the larger block. Each of the smaller blocks may be be sent to a destination address in a local memory  115 . The memory controller  104  determines the size of each of the smaller blocks and their destination addresses. 
     The data formatter  102  may include counters  110  to keep track of how many bytes from the current large block from the providing PAM  108  have been written to each of the destination addresses. The data formatter  102  shifts data to the correct byte lanes for writing to a new address regardless of which byte lanes the data elements are in when received from the providing RAM  108 . For example, in a block of four bytes, the first two bytes may need to be written to address 2, the third byte may need to be written to address 10, and the fourth byte may need to be written to address 7. If the memory bus is 4 bytes wide, as shown in FIG. 2, the first two bytes may need to be in byte lanes 2 and 3, respectively, while the third byte may need to be in byte lane 3, arid the fourth byte may need to be in byte lane 4. 
     The data formatter  102  includes a shift register  112  which shifts the data to the correct byte lanes. The data formatter may use another set of counters  111  to track and determine the correct byte lanes at any given moment. Then, based on these values, certain parameters, and its current state, the data formatter  102  shifts the data to the proper position, i.e., correct byte lanes, before allowing the data elements to be written to a receiving FIFO (First-In/First-Out) register or RAM  116 . 
     Data elements are written into the shift register from the providing RAM&#39;s data bus  114  when the RAM  108  is read. A RAM read strobe from the memory controller  104  signals to the shift register  112  that a read has occurred. When a read occurs, the data in the entire providing RAM&#39;s data bus may be copied into the lowest part of the shift register  114 , and data from lower parts of the shift register may be shifted into the higher parts of the shift register. Data at the highest parts of the shift register may be lost. 
     The width of the shift register  112  depends on the degree of mismatch between the providing RAM&#39;s speed and word width and the receiving FIFO&#39;s speed and word width. For minor mismatches, a shift register width of four times that of the providing RAM&#39;s data bus width may be sufficient. 
     A pointer manager  120  controls a window  200  of bytes in the shift register  112 , as shown in FIG.  2 . The window  200  includes a pointer which points to the lowest byte  202  of the word that will be written next to the receiving FIFO  116  and a pointer (sr_pointer) which points the highest byte  204  of the word that will be written next to the receiving FIFO  116 . The sr_pointer factors in an address offset provided by the memory controller  104  to ensure that the first byte written to the receiving FIFO  116  is in the correct byte lane. 
     The pointer manager  120  may monitor operations involving the providing RAM  108 , receiving FIFO  116 , memory controller  104 , and external memory addresses and associated byte enables in order to manage the pointers. For example, the pointer will be shifted higher by the amount of data read in from the providing RAM  108 . When data elements are written to the receiving FIFO  116 , the pointer decrements by the number of bytes that were written out. However, if data is being read in from the providing RAM  108  and being written into the receiving FIFO  116  at the same time, the pointer value will depend on how many valid bytes are being written into the receiving FIFO  116 . In this case, the value of the pointer will be decreased by the number of valid bytes being written into the receiving FIFO and will be increased by the number of bytes being read from the providing RAM  108 . The actual value is determined by the equation 
     
       
         ram1_db_width−bytes_enabled  
       
     
     where “ram1_db_width” represents to the width of the providing RAM&#39;s data bus  114  in bytes, and “bytes_enabled” represents the number of bytes that were written to the receiving FIFO  116 . 
     Bytes_enabled may be set by the memory controller  104  and is used for every write to the receiving FIFO  116  for a given external memory address. It is expected that all write operations to the receiving FIFO  116  will contain fully valid words that are the width of ram2_db_width (i.e., the width of the receiving FIFO&#39;s data bus  117  in bytes) except for possibly the first and last writes to a given external memory address. In the case of the first read from the providing RAM  108  destined to be written to a new address, if bytes_enabled is not set to the same value as ram2_db_width, less than a full word of data was written to the receiving FIFO  116 . For this case and the case of any last write to a receiving FIFO, bytes_enabled adjusts the pointer so that it represents the amount of data left in the shift register  112 . 
     FIG. 3 illustrates a flowchart describing a pointer management operation  300  according to an embodiment. The following is a Verilog language description of the operation  300 : 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 always @ (posedge clock or posedge reset) 
               
               
                   
                 begin 
               
            
           
           
               
               
            
               
                   
                 if (reset) 
               
            
           
           
               
               
            
               
                   
                 pointer[4:0] &lt;= 5′h1F; 
               
            
           
           
               
               
            
               
                   
                 else if (pointer_reset) 
               
            
           
           
               
               
            
               
                   
                 pointer[4:0] &lt;= 5′h1F; 
               
            
           
           
               
               
            
               
                   
                 else if (read_strb &amp; write_strb) 
               
            
           
           
               
               
            
               
                   
                 pointer[4:0] &lt;= pointer[4:0] + ({grave over ( )}ram1_db_width − 
               
            
           
           
               
               
            
               
                   
                 bytes_enabled[{grave over ( )}ram2_db_width:0]); 
               
            
           
           
               
               
            
               
                   
                 else if (read_strb &amp; !write_strb) 
               
            
           
           
               
               
            
               
                   
                 pointer[4:0] &lt;= pointer[4:0] + {grave over ( )}ram1_db_width; 
               
            
           
           
               
               
            
               
                   
                 else if (write_strb) 
               
            
           
           
               
               
            
               
                   
                 pointer[4:0] &lt;= pointer[4:0] − 
               
               
                   
                 bytes —enabled[{grave over ( )}ram2_db_width:0];   
               
            
           
           
               
               
            
               
                   
                 else 
               
            
           
           
               
               
            
               
                   
                 pointer[4:0] &lt;= pointer[4:0]; 
               
            
           
           
               
               
            
               
                   
                 end 
               
               
                   
                 assign sr_pointer[4:0] = pointer[4:0] + 
               
               
                   
                 address_offset[{grave over ( )}r2_log2−1:0]; 
               
               
                   
                   
               
            
           
         
       
     
     The pointer managment operation  300  executes on a clock signal (block  302 ). When a new starting address for the external memory is introduced, the pointer manager  120  changes a pointer offset value to a new value if the received bytes need to be shifted to different lanes from a default position. This new starting address is saved as the signal “address_offset”, and the sr_pointer is assigned a value described by the equation: 
     
       
           sr   —   pointer=pointer[ 4:0 ]+address   —   offset [&#39;r 2 —   log 2−1:0],  
       
     
     where r2_log2 is the base 2 logarithm of the ram2_db_width parameter, i.e., the width of the receiving FIFO&#39;s data bus in bytes. 
     The pointer manager  120  resets the pointer to a value indicating that the shift register  114  is empty whenever a block of data, as defined by the memory controller  104 , ends and another block begins (block  305 ). In this example, the empty value is hexadecimal value 1F. The pointer may also be reset to the empty value if the pointer reset signal is issued by the memory controller  104  (block  306 ). 
     The memory controller  104  indicates when data is written into the receiving FIFO  116  by sending a write strobe signal to the pointer manager  120 . The memory controller  104  indicates when data is read from the providing RAM  108  by sending a read strobe signal to the pointer manager  120 . 
     If a read strobe and a write strobe are received in the same clock cycle (block  308 ), the pointer manager  120  changes the pointer value to a value which equals the pointer&#39;s current value plus the width of the providing RAM&#39;s data bus  114  in bytes minus the bytes_enabled value (block  310 ). The bytes_enabled value will be the width of the receiving FIFO&#39; data bus  117  in bytes for any writes other than perhaps the first or last writes. 
     If a read strobe is received, but no write strobe in a clock cycle (block  312 ), the pointer manager  120  changes the value of the pointer to a value which equals its current value minus the bytes enabled value (block  314 ). 
     If the pointer manager  120  determines that neither of the last two conditions were true and a write strobe is received (block  316 ), the pointer manager  120  changes the value of the pointer to a value which equals its current value plus the width of the providing RAM&#39;s data bus  114  in bytes (block  318 ). 
     If the pointer manager determines that none of the previous conditions are true (block  320 ), the pointer manager  120  does not change the pointer value (block  322 ). 
     Consider the following example of a pointer management operation  300 . Assume the following conditions: 
     ram1_db_width=8 (bytes) 
     ram2_db_width=4 (bytes) 
     number of bytes in shift register=32 
     address_offset=3 
     In this example, fifteen bytes are to be written to an external memory address of 3. This will require two 8-byte reads from the providing RAM, and five 4-byte writes to the receiving FIFO (not four, due to the address offset). 
     The pointer begins with a value 5&#39;h1F, indicating that the shift register is empty, as shown in FIG.  4 . The address offset is set to 3 when the memory controller  104  assigns a new external memory address destination for the forthcoming data. 
     Next, a read strobe occurs, indicating to the pointer manager  120  that eight bytes of data have been placed in the shift register  112 . The pointer manager  120  adds eight to pointer&#39;s value, changing the pointer value to 5&#39;h1F+4&#39;h8=5&#39;h07. The value wraps from 5&#39;h1F to 5&#39;h00 since the shift register  112  is at its highest possible value at 5&#39;h1F. The first bytes to be written into the receiving FIFO are those ones located in bytes A,  9 ,  8 , and  7  of the shift register  112 , since the sr_pointer equals 5&#39;h07+2&#39;h3=5&#39;h0A, as shown in FIG.  5 . Bytes  7  down to 0 are the valid bytes in the shift register. Thus, byte  7  of the shift register is the first valid byte read from the providing RAM  108 . Byte  7  is “shifted” into byte lane 0 for the receiving FIFO  110 . This shift happens because of the address_offset. This same amount of shift will be in effect for all data written into the receiving FIFO  116  until the memory controller  104  issues a new external memory address. 
     After the next clock, assume that a write strobe occurs, with no read strobe. Bytes_enabled is 4, but this is a dummy value, which is the case on the first write. This allows the pointer to advance to the proper position with all possible offsets. In reality, only one byte was written to external memory. The pointer manager  120  changes the pointer&#39;s value to 5&#39;h07−3&#39;h4=5&#39;h03, as shown in FIG.  6 . The next bytes that will be written into the receiving FIFO  116  are the ones located in bytes  6 ,  5 ,  4 , and  3  of the shift register, since the sr_pointer equals 5&#39;h03+2&#39;h3=5&#39;h06. 
     After the next clock, assume that a read strobe and a write strobe occur simultaneously. Data that were in bytes  7  through  0  are moved into bytes  15  through  8 , to make room for the new data read in. Data that were in bytes  15  through  8  are moved into bytes  23  through  16 , and so on. Bytes_enabled is 4. The pointer manager  120  changes the pointer&#39;s value based on two factors: read and write. The pointer&#39;s value is changed to 5&#39;h03+4&#39;h8−3&#39;h4=5&#39;h07, as shown in FIG.  5 . The next bytes that will be written into the receiving FIFO are the ones located in bytes A,  9 ,  8 , and  7  of the shift register, since the sr_pointer equals 5&#39;h07+2&#39;h3=5&#39;h0A. 
     On the next clock, assume that only a write strobe is occurring, with no read strobe. Bytes_enabled is 4. The pointer manager  120  changes the pointer&#39;s value to 5&#39;h07−3&#39;h4=5&#39;h03, as shown in FIG.  6 . The next bytes that will be written into the receiving FIFO are the ones located in bytes  6 ,  5 ,  4 , and  3  of the shift register, since the sr_pointer equals 5&#39;h03+2&#39;h3=5&#39;h06. 
     On the next clock, again there is only a write strobe occurring, with no read strobe. Bytes_enabled has a value of 4. Pointer changes its value to 5&#39;h03−3&#39;h4=5&#39;h1F, as shown in FIG.  7 . The next bytes that will be written into the receiving FIFO are the ones located in bytes  2 ,  1 ,  0 , and  1 F of the shift register, since the sr_pointer equals 5&#39;h1F+2&#39;h3=5&#39;h02. 
     On the last clock, again assume that only a write strobe is occurring, with no read strobe. Bytes enabled has a value of 2. Pointer changes its value to 5&#39;h02−3&#39;h2=5&#39;h00. No more bytes will be written into the receiving FIFO. 
     Note that now, pointer has a value of 5&#39;h00. A value of 5&#39;h1F would indicate that the shift register is empty, but this is not the case. Instead, this value indicates that there is one more byte of possibly valid data in the shift register. This byte may or may not be written to a different external memory address. This depends on what the memory controller  104  wants to do with the byte. If this byte of data is not valid at all, pointer_reset signal will be asserted by the memory controller  104  before a new external memory address is issued. There will be no more writes to the receiving FIFO  116 , since bytes_enabled can only be less than ram2_db_width for the last write of a block of data designated for a given address. For this example, this is where the reading and writing are complete. 
     Another function of the shift register  112  may be to notify the memory controller  104  not to read from the providing RAM  108  or not to attempt to write data to the receiving FIFO  116 . These are temporary conditions that may be used to keep the memory controller  104  from performing these functions until the shift register  112  is in a condition to allow normal operation. The pointer&#39;s value indicates that the shift register  112  is almost full or almost empty and may be used to signal the temporary notification, e.g., by setting flags. For example, if the shift register  112  is almost full, it indicates this condition to the memory controller  104 . The shift register  112  may stay in this condition until a write strobe occurs, which will make room for read data without pushing unwritten data out of the shift register  112 . The actual combination of events that allow reads to continue may be different, depending on the implementation. 
     When the shift register  112  is almost empty, this status can be signaled to the memory controller  104  when the pointer is within a few bytes of being empty, depending on the implementation. The shift register  112  may stay in this condition until a read strobe occurs, indicating that there is data available to write to the receiving FIFO  116 . As before, the actual combination of events that allow writes to continue may be different, depending on the implementation. 
     A number of embodiments have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the invention. For example, blocks in the flowchart may be skipped or performed out of order and still produce desirable results. Accordingly, other embodiments are within the scope of the following claims.