That's how i ROL (a case study in circuit efficiency)

[Arnadath]

"And you're gonna hear me ROR".

So. In my last thread, i provided you with a first finished version of the ALU for the CPU i'm designing. And everything is fine, except for the bit shifter. Although it's working, it isn't yet up to par with my goals about the timing constraints in the circuit. Since then, i've been working on the registers, and partially on the efficiency of the ALU. 

I can tell you, this bit shifter and especially the left shifting/rotating has been a real migrain, but i did the smart thing. I left it aside for a while. Played the piano, argued with idiots on facebook about the coronavirus etc... Then, one day later i came back and i designed it anew. Came up with this version and i want you to note some lines i drew. I'll go into the specifics in a minute

This tangled mess that took me almost 3 hours to come up with, is a circuit that shifts/rotates right. Simply explained, you assign a 3 bit value in a ribbon to the far right, and based on that, the circuit will shift the 8-bit value it gets on the bottom left-most and right-most ribbons by 0 up to (and including) 7. Also the bottom middle-most (is that even a thing?) ribbon, simply let's us choose between plainly shifting the value, or rolling it. Therefore, let's assume we have a value of '01101001' and we shift it right by 2, then the value will become '00011010'. Essentially we performed an integer division by 4, but in the world of binary mathematics. If we now translate it to our worlds mathematics, namely decimal numbers, we took a value of 105 and divided it by 4 (keeping only the integral part) which equals to 26. 

Now the time constraints i have put to this thing i'm making, is that i want every function of the ALU to be performed in the least steps possible, and definately less than 9. The above circuit, complies with this. It will perform it's most 'time-consuming' task' in at most 8 steps which is the Red line. The design was also compact enough to my likings. so i kept it.

And then i thought i would be smart, if i did this for the left shifting/rotating function by just swaping all the input bits, doing the right shift, and then reswaping them in the end, essentially left shifting/rotating. And it worked, but...

Now it consumed more time. in face, in the edge case, it consumed 50% more time. And it exceeded the quota that i had set. So again i put it aside. Played the piano, argued on facebook and came back to the drawing board, two days later. And almost immediately i changed my approach 180^o and within ten minutes, i came up with this.

Spoiler

This does a left shift/rotate, takes even less time than the right shift/rotating shown above, is even more compact and makes me and Murphy (the guy that came up with the famous law) happy. Also unlocks the potential to make the ROR/SHR thingy less time consuming and more compact. But this will be your homework if you wanna get into these things. Let's be creative. Post your own version of efficient bitshifting and let's evaluate them in the end. Winner get's a cookie.

 

So, lessons learned in the end:

1. Give your brain some rest. Tomorrow is a new (not just another) day

2. Murphy is almost always right. Make him proud

3.Get into lot's of stuff. You'll be suprised at what  you can draw inspiration from.

[Yoma_Nosme]

I like it. Although I only see red/green spaghetti at the moment. Here's a cookie for the effort and for explaining it so thoroughly. I can follow your explanation and understand basically what it does and why but I'm lost on the how...looking forward for more

[Maxposting]

On 19. 3. 2020 at 7:42 AM, Yoma_Nosme said:

I like it. Although I only see red/green spaghetti at the moment. Here's a cookie for the effort and for explaining it so thoroughly. I can follow your explanation and understand basically what it does and why but I'm lost on the how...looking forward for more

Yeah, people are making games/literal cpus and in the meanwhile I'm just vibing with basic automation