How to Shift 32 Bit Numbers on a 16 Bit Datapath
This is a computer architecture question.
My datapath is only 16 bit wide, meaning my ALU can only process 16 bit operands at a time. My registers are 32 bits wide and are addressable in lower and upper 16 bit portions.
Every time I read the lower half of a register I also read an extra bit telling me weather the upper half contains any 1s at all (ref 1).
So far I implemented the shift left logical. (sll rd, rs1, rs2)
- Read the lower half of the rs1 register, and shift it by the amount specified in the lower rs2 register
- The bits that I shifted out of these 16 bits, are being stored in a temporary 16 bit register inside the alu
- The shifted value will be written back to the lower rd register and the status bit is set (see ref 1)
Now if there is no data written in the higher rs1 register (see ref 1) and the bits that are in the temp alu register are all 0, then my shift operation is done.
Otherwise a second cycle for the upper half is needed
- Read the high rs1 register and shift it by the amount stored in the lower rs2 register
- But now fill the rs1 with the values stored in the alu temp register (not with 0 as in the first cycle)
- Bits shifted out of the 16bit space will be dropped
- The result is written back to the higher rd register, and the rd status bit is set (see ref 1)
Example 1: Lets say rs1 is 0x00001234 and rs2 is 0x00000002 (Perform a left shift by 2)
- First I read the lower 16bits of rs1 and rs2, presenting 0x1234 and 0x0002. But by reading that I do also get the status bits of both registers, in this case being 0 for rs1 and 0 for rs2 since the upper 16 bits of both registers are all 0. With the data given I can perform a left shift by 2. Resulting in 0x48D0. Since no 1s were shifted out of the sll I can store the result in lower rd and set its status bit to 0. (This is all done in one cycle)
Example 2: Lets say rs1 is 0x0000D234 and rs2 is 0x00000005 (Perform a left shift by 5)
- First I read the lower 16bits of rs1 and rs2, presenting 0xD234 and 0x0005. But by reading that I do also get the status bits of both registers, in this case being 0 for rs1 and 0 for rs2 since the upper 16 bits of both registers are all 0. With the data given I can perform a left shift by 5. Resulting in 0x4680. But now I shifted 11010 (0x1A) out of the 16 bit space. This value is stored in the Alu temp register and since it contains 1s I have to perform another cycle.
- In the second cycle I read the upper rs1 and lower rs2, presenting 0x0000 and 0x0005. I perform another shift left by 5, but now the Alu temp register is used to fill up the shifted values. 0x0000 -> 0x00__ -> 0x001A. This result is then written back to the upper rd. Therefore finishing my 32 bit sll in two 16 bit cycles.
Example 3: Lets say rs1 is 0x01231234 and rs2 is 0x00000002 (Perform a left shift by 2)
- First I read the lower 16bits of rs1 and rs2, presenting 0x1234 and 0x0002. But by reading that I do also get the status bits of both registers, in this case being 1 for rs1 and 0 for rs2 since the upper 16 bits of rs1 are non-zero. Since the status bit of rs1 was non-zero I have to preform a second cycle even if no 1s are shifted out of the lower 16 bits (See Example 2). From now on it follows Example 2, by writing back to rd and preforming a second cycle for the upper bits.
I hope these examples gave a better insight.
Now I want to implement a right shift operation (arithmetical and logical). But how to do that in at most 2 cycles and if I have to read the lower rs1 register first (including the status bit)?
Thanks for reading; this is my first question here, so please don't go to harsh on me :D
Start by reading the higher part. The first cycle you will read the high part. Do the right shift, the shifted out bits will be present in the high part of the tmp register and the result of the shift will be written back. The second cycle , you read the low part , you do a shift and an or with the result present in the tmp register. then the result of this part will be written back.