Abstract:
A data alignment logic cell properly aligns the individual data units (e.g., bytes) in a block of data that is transferred in a multiple bit bus such that the data units in the block are transferred to desired lanes of the bus. The data alignment logic cell includes a gathering unit, which aligns the data units into a fixed, justified arrangement in the bus, and a scattering unit, which receives the data units from the gathering unit and realigns them to the desired lanes. Both the gathering and scattering units contain registers for temporarily storing certain of the data units and multiplexers for transferring the data units between the lanes of the bus, the state of the multiplexers being determined by signals from control units.

Description:
FIELD OF THE INVENTION 
     This invention relates to the transfer of blocks of data through a multiple lane bus and, in particular, to a logic cell which properly aligns the transferred data. 
     BACKGROUND OF THE INVENTION 
     Blocks of data are normally transferred between a source and a destination through an interconnecting bus. If the width of the bus is greater than the units in which the data are organized, the data must normally be realigned on the bus, i.e., a unit of data (e.g., a byte) which enters the bus in lane A may need to exit the bus in lane B, where each &#34;lane&#34; represents a channel which is capable of transferring a single unit of data (byte). 
     Transfers of data from a source memory to a destination memory, for example, are often accomplished by specifying a starting source address, a starting destination address, and the number of bytes to be transferred. The computer then causes the data to be read out of the source memory, beginning with the starting address, and delivered over a bus to the destination memory. 
     Since the starting source address is not generally in a lane (or column) in the source memory which is in same as the lane (or column) of the starting destination address in the destination memory, typically the data must be realigned in conjunction with the transfer. Therefore the first byte in the block of data to be transferred must be shifted from one lane to another. 
     Data alignment is also necessary, for example, in a block data transfer from a main computer to a graphics memory card through the interface bus, and from a computer to a sound card. 
     This problem is illustrated in FIG. 1. A block of data including twelve bytes, designated 0 to 11 respectively, is to be transferred from a source, represented by a memory M1, to a destination, represented by a memory M2, over a bus W. Memory M1 is a 4X memory which has lanes A, B, C and D, and memory M2 is likewise a 4X memory with lanes a, b, c and d. The addresses of the memory locations in lanes A and a are shown, in hexadecimal units, beneath memories M1 and M2. 
     In this example, the starting address of the data in memory M1 is 0009h and the starting destination address in memory M2 is 0007h. This means that byte 0 must be shifted from lane B in memory M1 to lane d in memory M2. Similarly, byte 1 must be shifted from lane C to lane a; byte 2 must be shifted from lane D to lane b; and byte 3 must be shifted from lane A to lane C. 
     Since each vertical row is shifted out of memory M1 at the same time, there is an additional problem with timing. Bytes 0, 1 and 2 are shifted out of memory M1 simultaneously but byte 0 must be shifted into memory M2 before bytes 1 and 2. Bytes 3 and 4 are shifted out of memory M1 after bytes 1 and 2, but all four of these bytes must be shifted into memory M2 simultaneously. 
     In the example shown in FIG. 1, the starting source address may be in any one of the four lanes A-D and the starting destination address may be in any one of the four lanes a-d. Accordingly, there are sixteen different possibilities including four in which the data are not shifted into different lanes. 
     What is needed is a simple, straightforward cell that can perform data alignment rapidly and accurately. 
     SUMMARY OF THE INVENTION 
     The data alignment logic cell of this invention is connected in a multiple lane data transfer bus and includes a data gathering unit and a data scattering unit. Data units to be transferred are initially shifted into the data gathering unit where they are arranged in a single row (justified) on the bus, with the first data unit always being transferred to a first lane of the bus, the second data unit always being transferred to a second lane of the bus, etc. The data gathering unit contains registers for temporarily storing certain of the data units in order to line them up on the bus, and multiplexers for transferring the data units between lanes of the bus. 
     Next the data units are shifted into a data scattering unit where they are realigned as required. Like the data gathering unit, the data scattering unit contains registers for temporarily storing certain of the data units, and multiplexers for transferring the data units between lanes of the bus. 
     The data gathering unit is driven by a first control unit which delivers a control word determined by the bus lane in which the first unit of data appears. The data scattering unit is driven by a second control unit which delivers a control word determined by the lane to which the first unit of data is to be transferred. In the preferred embodiment, the data gathering unit and the data scattering unit have the same structure. 
     A data alignment logic cell of this invention may be used in conjunction with buses which have a number of lanes equal to a power of two (2, 4, 8, 16, 32, etc.), wherein each lane is capable of transmitting a single data unit (byte, etc.). For a bus having N lanes, for example, the data gathering unit and data scattering unit each contain N multiplexers and N-1 registers. Each register holds a single data unit, and each multiplexer has N inputs. In the preferred embodiment, the output of one of the registers is connected to the inputs of N-1 multiplexers; the output of a second register is connected to the inputs of N-2 multiplexers; and so on, with the output of the last (N-1)th register being connected to the input of a single multiplexer. 
     The control unit for each unit controls the states of the multiplexers within the unit. The control word remains constant during the transfer of the data block. 
     While the embodiment described below aligns data that is organized into 8-bit data units (bytes), this invention is applicable to data which is organized into units of any size, e.g., single-bit, 4-bits (nibble), or 16-bits (word). The term &#34;data unit&#34; as used herein refers to data units having any number of bits. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 illustrates the problem of aligning the data units when a block of data is transferred between a source and a destination. 
     FIGS. 2A and 2B illustrate a schematic diagram showing a byte alignment cell containing a byte gathering unit and a byte scattering unit interconnected in a 32-bit (4 byte) bus between a source memory and a destination memory. 
     FIG. 3 illustrates conceptually the byte paths from the source memory to the destination memory for the data transfer shown in FIGS. 1, 2A and 2B. 
     FIG. 4 illustrates conceptually the byte paths from the source memory to the destination memory for another example of a data transfer. 
     FIG. 5 illustrates an alternative embodiment of this invention designed for use with a 64-bit (8 byte) bus. 
     FIG. 6 illustrates the structure of data gathering or scattering unit usable with a bus having N lanes. 
    
    
     DESCRIPTION OF THE INVENTION 
     FIGS. 2A and 2B illustrate an embodiment of this invention which is used to align byte-sized data units. A byte alignment cell 2 includes a byte gathering unit X and a byte scattering unit Y. Byte alignment cell 2 is connected between a memories M1 and M2 via a bus W, shown in FIG. 1. As indicated above, any type of source and destination data storage units could be substituted for memories M1 and M2. 
     Byte gathering unit X and byte scattering unit Y each contain three registers, four multiplexers and a control in the preferred embodiment. Gathering unit X and scattering unit Y are identical except for the controls. 
     Referring initially to byte gathering unit X, each of registers RBX, RCX and RDX holds a byte (8-bits) of data. Register RBX is connected to the B lane of memory M1, and registers RCX and RDX are connected to the C and D lanes, respectively, of memory M1. Outputs of registers RBX-RDX are connected to inputs of multiplexers MAX, MBX, MCX and MDX as shown. In addition, lanes A-D of memory M1 are connected directly to certain of the inputs of multiplexers MAX-MDX. Each of multiplexers MAX-MDX has four inputs and one output. Control CX delivers a 2-bit word which selects one of the inputs of multiplexers MAX-MDX, respectively, and causes it to be delivered at the output of the multiplexer. 
     As noted above, the registers and multiplexers in bit scattering unit Y are identical to and are interconnected with each other in the same manner as the registers and multiplexers in bit gathering unit X. Thus registers RBY-RDY correspond to registers RBX-RDX and multiplexers MAY-MDY correspond to multiplexers MAX-MDX. Outputs of registers RBY-RDY are connected to inputs of multiplexers MAY-MDY in the same manner. 
     Byte gathering unit X and byte scattering unit Y are connected in a series arrangement such that the outputs of byte gathering unit X are connected to the inputs of byte scattering unit Y. Thus the outputs of multiplexers MBX-MDX are connected to the inputs of registers RBY-RDY, and the output of multiplexer MAX is connected directly to selected inputs of multiplexers MAY-MDY. The outputs of registers RBY-RDY are connected to selected inputs of multiplexers MAY-MDY. 
     Control CY delivers a 2-bit output which selects one of the inputs of multiplexers MAY-MDY. The outputs of multiplexers MAY-MDY form the outputs of byte scattering unit Y and are connected to lanes a-d, respectively, of memory M2. 
     The operation of byte alignment cell 2 will be described with reference to the data transfer illustrated in FIG. 1. As is customary, a system clock (not shown) provides synchronous pulses which clock data out of memory M1 and into memory M2. A vertical row of data (32 bits) is clocked out of or into a memory simultaneously. 
     Referring again to FIG. 2A, control CX delivers the control bits &#34;11&#34; to the control inputs of multiplexers MAX-MDX, and control CY delivers the control bits &#34;11&#34; to the control inputs of multiplexers MAY-MDY. In the first cycle of the clock pulse, bytes 0, 1 and 2 are clocked into registers RBX, RCX and RDX, respectively. In the second clock cycle, byte 3 will be clocked out of memory M1 and bytes 0-2 will be clocked out of registers RBX-RDX, simultaneously. Since the &#34;11&#34; inputs of multiplexers MAX-MDX are selected, byte 3 appears at the output of multiplexer MDX and bytes 0, 1 and 2 appear at the outputs of multiplexers MAX, MBX and MCX, respectively. During the second clock cycle, bytes 4-6 are also clocked into registers RBX-RDX. 
     Thus, after two clock cycles, bytes 0-3 have been delivered in a justified form at the outputs of bit gathering unit X. In a similar manner, after the third clock cycle bytes 4-7 appear in justified form at the outputs of byte gathering unit X. 
     In this situation, byte 0 is to be written into address 0007h of memory M2 and bytes 1, 2 and 3 are to be written into addresses 0008h, 0009h and 000Ah of memory M2. With the &#34;11&#34; inputs of multiplexers MAY-MDY selected, byte 0 (at the output of multiplexer MAX) is passed immediately through multiplexer MDY and into lane d of memory M2. Bytes 1-3 (at the outputs of multiplexers MBX-MDX) are read into registers RBY-RDY. Thus, after two clock cycles, byte 0 resides in address 0007h of memory M2 and bytes 1, 2 and 3 reside in registers RBY, RCY and RDY, respectively. 
     In the third clock cycle, with the &#34;11&#34; inputs of multiplexers MAY-MDY selected, bytes 1-3 are read out of registers RBY-RDY and into addresses 0008h, 0009h and 000Ah of memory M2. Byte 4, which was in register RBX at the end of the second clock cycle, is transferred through multiplexers MAX and MDY to address 00Bh of memory M2. Also, during the third clock cycle, bytes 5 and 6 are read out of registers RCX and RDX and into registers RBY and RCY. Byte 7 passes directly from memory M1 through multiplexer MDX and is read into register RDY. Thus, at the beginning of the fourth clock cycle, registers RBY-RDY hold bytes 5-7 respectively. Bytes 5-7 are written into memory locations 00Ch, 00Dh and 00Eh of memory M2, and byte 8 is read directly from register RBX through multiplexers MAX and MDY into address 000Fh of memory M2. 
     This process continues until the entire data block is transferred from memory M1 to memory M2, with bytes in lane A being switched to lane c, bytes in lane B being switched to lane d, bytes in lane C being switched to lane a, and bytes in lane D being switched to lane b. 
     As noted above, for this data transfer, controls CX and CY both delivered the control word &#34;11&#34; Tables A and B show the outputs of controls CX and CY for all possible data transfers, depending on the lane location of the first byte to be transferred. 
     
                       TABLE A______________________________________Starting Source Address           Output of Control CX______________________________________Lane A          00Lane B          11Lane C          10Lane D          01______________________________________ 
    
     
                       TABLE B______________________________________Starting Destination Address             Output of Control CY______________________________________Lane a            00Lane b            01Lane c            10Lane d            11______________________________________ 
    
     The output of control CY is simply the two least significant bits of the first destination address, while to obtain the output of control CX, the two least significant bits of the source address go through a mapping function in accordance with Table C. 
     
                       TABLE C______________________________________Least Significant BitsOf Source Address           Output of Control CX______________________________________00              0001              1110              1011              01______________________________________ 
    
     FIG. 3 illustrates conceptually the byte paths in the data transfer shown in FIGS. 1, 2A and 2B. FIG. 4 illustrates conceptually the byte paths in an alternative data transfer, with the starting source address being in lane D and the starting destination address being in lane a. In the data transfer shown in FIG. 4, control CX outputs a &#34;01&#34; and control CY outputs a &#34;00&#34;. Note further that in both FIGS. 3 and 4 the bytes are &#34;gathered&#34; into a justified form by gathering unit X and then &#34;scattered&#34; by scattering unit Y. 
     The principles of this invention are applicable to buses having widths other than 32-bits, as shown in FIGS. 1-4. For example, embodiments according to this invention may involve buses having a width of 64-bits, 128-bits or any other width so long as the total bit width is divided into a number of lanes equal to a power of 2. For example, for a 64-bit bus, each byte gathering/scattering unit will have eight 8-to-1 multiplexers and seven 8-bit registers. The multiplexers will be controlled by 3-bit words. 
     The structure of a logic cell suitable for aligning eight lanes of data is illustrated in FIG. 5. A byte gathering/scattering unit 50 contains multiplexers MA to ME and registers RB to RH. The input lines A to H receive bytes from a source memory (if unit 50 is functioning as a gathering unit) or from a byte gathering unit (if unit 50 is functioning as a byte scattering unit). The connections between the inputs, the registers and the multiplexers are described in Table D, wherein the control bits in the left hand column represent the control inputs of each of multiplexers MA to ME and the data in the other columns indicate the register or input line to which the inputs of each multiplexer are connected. 
     
                       TABLE D______________________________________Control MultiplexersBits  MA     MB      MC   MD    ME   MF    MG   MH______________________________________000   A      B       C    D     E    F     G    H001   RH     A       B    C     D    E     F    G010   RG     RH      A    B     C    D     E    F011   RF     RG      RH   A     B    C     D    E100   RE     RF      RG   RH    A    B     C    D101   RD     RE      RF   RG    RH   A     B    C110   RC     RD      RE   RF    RG   RH    A    B111   RB     RC      RD   RE    RF   RG    RH   A______________________________________ 
    
     Table E shows the mapping for the control bits to use unit 50 in the byte gathering or byte scattering mode. The 3-bit word in the lefthand column represents the least significant bits in the starting or destination address. 
     
                       TABLE E______________________________________LSB of Address         Byte Gathering                    Byte Scattering______________________________________000           000        000001           111        001010           110        010011           101        011100           100        100101           011        101110           010        110111           001        111______________________________________ 
    
     In the general case, the data alignment logic cell is connected in a bus having N lanes. The cell includes N multiplexers and N-1 registers. Each multiplexer has N inputs and one output. Since there are N lanes and N-1 registers, there are a total of N+(N-1)=2N-1 sources of data to be delivered to the inputs of the multiplexers. 
     The connections to the inputs of the multiplexers can be described as follows. The N multiplexers are designated MOXG0, MUXG1, MUXG2 . . . MUXG&lt;N-1&gt; and are associated with lanes designated L(0), L(1), L(2), . . . L(N-1), respectively. Multiplexer MUXG0 has N inputs designated MUXG0(0), MUXG0(1) . . . MUXG0(N-1); multiplexer MUXG1 has N inputs designated MUXG1(0), MUXG1(1) . . . MUXG1(N-1); and multiplexer MUXG&lt;N-1&gt; has N inputs designated MUXG&lt;N-1&gt;(0) , MUXG&lt;N-1&gt;(1) . . . MUXG&lt;N-1&gt;(N-1). The registers are designated R(1), R(2), R(3) . . . R(N-1). This structure is illustrated in FIG. 6. 
     Table F sets forth the connections to each input of the multiplexers MUXG0 through MUXG&lt;N-1&gt;. This defines a unit of the kind illustrated in FIGS. 2A and 2B, which is inherently in the &#34;scattering&#34; mode, i.e., the unit performs as a data scattering unit if the control input is the two least significant bits of the destination address. Alternatively, the unit defined by Table F can be used as a data gathering unit by changing the control input to the 2&#39;s complement of the least significant bits of the source address, as shown in Table A. The 2&#39;s complement is obtained by inverting the bits and adding one, e.g., the 2&#39;s complement of 11 is 00+01=01. 
     
                       TABLE F______________________________________  INPUTMultiplexer    N-1       N-2                1     0______________________________________MUXG0    R(1)      R(2)                R(N-1)                      L(0)                MUXG1 R(2) R(3)                      L(0) L(1)                MUXG2 R(3) R(4)                      L(1) L(2)                MUXG&lt;N-2&gt;                      R(N-1) L(0)                      L(N-3) L(N-2)                MUXG&lt;N-1&gt;                      L(0) L(1)                      L(N-2) L(N-1)______________________________________ 
    
     The connections for a unit which inherently functions as a data gathering unit are shown in Table G. This unit functions as a data gathering unit if the control input is the two least significant bits of the source address. Again, the unit defined in Table G may be converted to a data scattering unit by changing the control input to the 2&#39;s complement of the least significant bits of the destination address. 
     
                       TABLE G______________________________________   INPUTMultiplexer     N-1     N-2                1       0______________________________________MUXG0     R(N-1)  R(N-2)                R(1)    L(0)                MUXG1   L(0) R(N-1)                        R(2) L(1)                MUXG2   L(1) L(0)                        R(3) L(2)                MUXG&lt;N-2&gt;                        L(N-3) L(N-4)                        R(N-1) L(N-2)                MUXG&lt;N-1&gt;                        L(N-2) L(N-3)                        L(0) L(N-1)______________________________________ 
    
     The embodiments of this invention that have been described herein are intended to be illustrative and not limiting. Numerous alternative embodiments according to this invention will be apparent to those skilled in the art, and the broad principles of this invention are intended to cover all such alternative embodiments.