Mux8Way for Jump?

classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

Mux8Way for Jump?

pvtjokerdavis
If I understand correctly, inside the CPU the output of the Aregister is fed to the input of the PC. Whether or not a jump actually occurs is dependent on the three j-bits of a C-instruction and the output from the ALU.
Am I on the right track by using an 8 way Mux that uses the three j-bits for sel[0..2] and the required ng and zr outputs to configure differently for the six different JMP conditions (since 000 and 111 can be set to false and true)?  
Reply | Threaded
Open this post in threaded view
|

Re: Mux8Way for Jump?

cadet1620
Administrator
pvtjokerdavis wrote
If I understand correctly, inside the CPU the output of the Aregister is fed to the input of the PC. Whether or not a jump actually occurs is dependent on the three j-bits of a C-instruction and the output from the ALU.
Am I on the right track by using an 8 way Mux that uses the three j-bits for sel[0..2] and the required ng and zr outputs to configure differently for the six different JMP conditions (since 000 and 111 can be set to false and true)?
That's one common way that people implement the jump logic. There is a way that uses less logic.

Consider making a "pos" flag from ng and zr. Then look at the bit pattern in the j-bits and look for an easy relationship to ng, zr and pos.

--Mark
Reply | Threaded
Open this post in threaded view
|

Re: Mux8Way for Jump?

pvtjokerdavis
Thank you very much. I followed your advice and finished the CPU.
Reply | Threaded
Open this post in threaded view
|

Re: Mux8Way for Jump?

ianohlander
In reply to this post by cadet1620
I have been banging my head against this for a few days. I think I have everything else in the CPU pretty much designed on paper the way I think it should work. But the JMP instructions is really giving me a hard time.

I thought of creating a pos flag. If a number is not neg and not zero it must be positive. So pos will always be ~neg*~zero. But with that logic, the output flags of the ALU can't ever match up with those of the jmp instructions. With settings like JGE or JLE or JNE, pos and zero or neg will both be 1. Since pos is calculated from the neg and zero flags and is the opposite of them, they can never both be equal, though the JMP instruction bits for neg zero and pos DO have them as sometimes matching in the JNE, JGE or JLE.

The testing method I came up with to see if the ALU outs matched the JMP instructions was to AND3(NOT3Way(J2J1J0 XOR NEGZERPOS)). If I figured correctly, that will give me a bit that tells me if the ALU outs matched the JMP instruction, which tells me whether to JMP or not. (Of course, I also have to add some conditional logic to override that test for when JMP=000 or 111 and output a 1 or 0.) From there (fingers crossed) I just need to either increment the PC or load the PC with the A register depending on that bit, which i can do with a 2 way MUX.

Obviously I am missing something. I think I may be making this too complicated.
Reply | Threaded
Open this post in threaded view
|

Re: Mux8Way for Jump?

ybakos
Just to be clear, the circuitry for the jump logic should be wired such that the PC receives a load bit of 1 if there is a jump. The PC doesn't care why it should load an instruction address, only that it should.

So, you need to craft your jump logic such that you are determining if a jump should occur in one of seven situations. Consider just JEQ and JLT. If the ALU zr output is 1 OR the ALU ng output is 1, then the PC should receive a load bit of 1. So how might you then handle JNE or JGT? Well, if you NOT the ALU zr output, that gives you JNE. And if you NOT the output of the ALU's zr output and AND it with the NOT of the ALU's ng output, what do you get? JGT.

It sounds like some of you thinking is unnecessarily reversed. But you are on the right track!
Reply | Threaded
Open this post in threaded view
|

Re: Mux8Way for Jump?

ianohlander
Ok, that helps somewhat. Thank you. My brain seems to be stuck in a rut on this and I'm trying to break out of it. So just a clarification. Would I still need test logic to make sure that the ALU outputs match the JMP instructions (obviously overriding when JMP=111 or 000) right? So when that happens, then the PC load bit is set to 1? Because I got your point on what to test for:
JGT=pos
JLE=zr+ng
JEQ=zr
JGE=zr+pos
JLT=neg
JNE=not zr

Just trying to figure out how to combine the JMP instructions with the ALU out. I see the way to do it with the mux. But not the simpler way.
Reply | Threaded
Open this post in threaded view
|

Re: Mux8Way for Jump?

cadet1620
Administrator
In reply to this post by ianohlander
ianohlander wrote
I have been banging my head against this for a few days. I think I have everything else in the CPU pretty much designed on paper the way I think it should work. But the JMP instructions is really giving me a hard time.

I thought of creating a pos flag. If a number is not neg and not zero it must be positive. So pos will always be ~neg*~zero. But with that logic, the output flags of the ALU can't ever match up with those of the jmp instructions.
You are on the right track. You do want a pos status flag. What you don't want to do is compare the status flags to the jmp field.

Think about what the bits in the jmp field mean:
    j1 j2 j3
    0  0  0         no jump
    0  0  1   JGT   jump if pos
    0  1  0   JEQ   jump if zr
    0  1  1   JGE   jump if zr or pos
    1  0  0   JLT   jump if ng
    1  0  1   JNE   jump if ng or pos
    1  1  0   JLE   jump if ng or zr
    1  1  1   JMP   jump if ng or zr or pos
Think about how to use And gates to determine if a jump should occur, one for each status bit. Then combine the outputs of those Ands to get the load signal for the PC.

--Mark
Reply | Threaded
Open this post in threaded view
|

Re: Mux8Way for Jump?

ianohlander
Thank you. Between the two of you and a nights sleep it came to me. Was stuck in a mental rut. Thanks again. This project has been really a lot of fun.
Reply | Threaded
Open this post in threaded view
|

Re: Mux8Way for Jump?

reflectionalist
In reply to this post by cadet1620
I defined the load signal as a function of five parameters, namely, ng, zr, j1, j2, and j3, by creating the truth table, ANDing the literals of lines with the load signal 1, and then ORing them.  Does this give an solution of minimal logic?
Reply | Threaded
Open this post in threaded view
|

Re: Mux8Way for Jump?

cadet1620
Administrator
reflectionalist wrote
I defined the load signal as a function of five parameters, namely, ng, zr, j1, j2, and j3, by creating the truth table, ANDing the literals of lines with the load signal 1, and then ORing them.  Does this give an solution of minimal logic?
This sounds like you are describing canonical representation (book section 1.1.1), in which case you have 12 And terms with up to 4 inputs, all Ored together. There is a much more concise solution.

You can try minimizing the canonical representation using Karnaugh maps, but that's tough with 5 inputs. For optimization, remember that all cases with 'zr' and 'ng' both true are don't-cares -- 'X' in the K-map.

See my earlier post on this thread for an idea that starts by creating a 'pos' status signal from 'zr' and 'ng'.

--Mark
Reply | Threaded
Open this post in threaded view
|

Re: Mux8Way for Jump?

reflectionalist
If I understand your post on Sep 26, 2013, the next step is to apply the canonical-representation method.  For example, in the case of JGT, it would be AND4(pos, NOT(j1), NOT(j2), j3).  Is this correct?
Reply | Threaded
Open this post in threaded view
|

Re: Mux8Way for Jump?

reflectionalist
In reply to this post by cadet1620
Thanks for the reply to further hints in email, Mark.  Problem solved.  ;)  Please allow me to answer your email here since I think my remarks may be helpful to others too.

This control unit took most of my time in building the CPU.  After seeing this thread and starting to improve my implementation, it was unclear to me why one does not need to compare the status bits with the jump bits.  The thought that the status bits together with the jump bits determine whether a jump occur is so natural.  I was led to the canonical method largely for this reason.  In a sense, I was thinking generally since the canonical method is general.  However, the concise solution you and others hint in this thread indicates that there is something special of the coding of the jump bits.  Had they be coded arbitrarily, by pigeonholing the eight possibilities (from never jump to always jump) into eight pigeonholes (marked 000 through 111), there might not be such a concise solution and one has to appeal to the canonical method followed by optimization using, say, Karnaugh maps.  So the coding of the jump bits in the book is yet another ingenious part of the design.
sk
Reply | Threaded
Open this post in threaded view
|

Re: Mux8Way for Jump?

sk
In reply to this post by cadet1620
cadet1620 wrote
ianohlander wrote
I have been banging my head against this for a few days. I think I have everything else in the CPU pretty much designed on paper the way I think it should work. But the JMP instructions is really giving me a hard time.

I thought of creating a pos flag. If a number is not neg and not zero it must be positive. So pos will always be ~neg*~zero. But with that logic, the output flags of the ALU can't ever match up with those of the jmp instructions.
You are on the right track. You do want a pos status flag. What you don't want to do is compare the status flags to the jmp field.

Think about what the bits in the jmp field mean:
    j1 j2 j3
    0  0  0         no jump
    0  0  1   JGT   jump if pos
    0  1  0   JEQ   jump if zr
    0  1  1   JGE   jump if zr or pos
    1  0  0   JLT   jump if ng
    1  0  1   JNE   jump if ng or pos
    1  1  0   JLE   jump if ng or zr
    1  1  1   JMP   jump if ng or zr or pos
Think about how to use And gates to determine if a jump should occur, one for each status bit. Then combine the outputs of those Ands to get the load signal for the PC.

--Mark
Hi Mark I am wondering , what is the best way to do it. I understood the process. Is it with a Mux8Way?

Best regards
Sajib
sk
Reply | Threaded
Open this post in threaded view
|

Re: Mux8Way for Jump?

sk
I got the simpler one ! Thanks.