Data formatter for shifting data to correct data lanes

This application claims priority to U.S. Provisional Application Ser. No. 60/309,064, entitled DATA FORMATTER and filed on Jul. 30, 2001.

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'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.

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).

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.

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'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'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's speed and word width and the receiving FIFO's speed and word width. For minor mismatches, a shift register width of four times that of the providing RAM'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'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'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 :

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 ['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'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's current value plus the width of the providing RAM'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' 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'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'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's value, changing the pointer value to 5'h1F+4'h8=5'h07. The value wraps from 5'h1F to 5'h00 since the shift register 112 is at its highest possible value at 5'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'h07+2'h3=5'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's value to 5'h07−3'h4=5'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'h03+2'h3=5'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's value based on two factors: read and write. The pointer's value is changed to 5'h03+4'h8−3'h4=5'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'h07+2'h3=5'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's value to 5'h07−3'h4=5'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'h03+2'h3=5'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'h03−3'h4=5'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'h1F+2'h3=5'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'h02−3'h2=5'h00. No more bytes will be written into the receiving FIFO.

Note that now, pointer has a value of 5'h00. A value of 5'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'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.