[bug]: In Project 5: CPU, the order of the chips matters.

[Arcadonauts]

Tool

Hardware Simulator

Interface

Website (https://nand2tetris.github.io/web-ide)

Contact Details

No response

What happened?

If I put the registers above the ALU, I fail the test at time 19. If I put the ALU above the registers, I pass the test.

Additional Comments

This one might actually be an issue with my understanding, not with the Web IDE. If this is desired behavior, and I don't understand how HDL works, then please accept my apologies.

Do you want to try to fix this bug?

• [ ] I want to try to add this feature!

Code of Conduct

• [X] I agree to follow this project's Code of Conduct

[DavidSouther]

This looks like a duplicate of #337. Please re-verify with the most recent version (which you should get by refreshing the page), and if it is not fixed, please re-open this issue and include your code that is failing.

[Arcadonauts]

I refreshed, but maybe there's some sort of cache issue? (Firefox)

If the registers at Point A are moved down to Point C, it passes every test, but as it is here, it fails only at time=19.

CHIP CPU {

    IN  inM[16],         // M value input  (M = contents of RAM[A])
        instruction[16], // Instruction for execution
        reset;           // Signals whether to re-start the current
                         // program (reset==1) or continue executing
                         // the current program (reset==0).

    OUT outM[16],        // M value output
        writeM,          // Write to M? 
        addressM[15],    // Address in data memory (of M)
        pc[15];          // address of next instruction

    PARTS:

        PC(
            in = regAOut, reset = reset,
            load = jump, inc = true, out[0..14] = pc
        );  

        // Point A

        Register(
            in = muxAOut, load = loadA, 
            out = regAOut, out[0..14] = addressM
        );

        Register(
            in = aluOut, load = loadD, 
            out = regDOut, out = xValue
        );

        // Point B

        ALU(
            y = yValue, 
            x = xValue,
            zx = instruction[11], // zero the x input?
            nx = instruction[10], // negate the x input?
            zy = instruction[9], // zero the y input?
            ny = instruction[8], // negate the y input?
            f = instruction[7],  // compute (out = x + y) or (out = x & y)?
            no = instruction[6], // negate the out output?
            out = aluOut, // 16-bit output
            out = outM,
            zr = eq,      // if (out == 0) equals 1, else 0
            ng = neg      // if (out < 0)  equals 1, else 0
        );

        // Point C

        And(a = canJump, b = isCInstruction, out = jump);

        Or8Way(
            in[0] = jumpPos, in[1] = jumpZero, 
            in[2] = jumpNeg, out = canJump
        );

        And(a = instruction[0], b = pos, out = jumpPos);
        And(a = instruction[1], b = eq, out = jumpZero);
        And(a = instruction[2], b = neg, out = jumpNeg);

        And(a = nonNeg, b = nonZero, out = pos);
        Not(in = eq, out = nonZero);
        Not(in = neg, out = nonNeg);

        And(
            a = instruction[3], b = instruction[15], 
            out = writeM
        );

        Mux16(
            a = regAOut, b = inM, 
            sel = instruction[12], out = yValue
        );

        Mux16(
            a = aluOut, b = instruction,
            sel = isAInstruction, out = muxAOut
        );

        And(
            a = isCInstruction, b = instruction[5],
            out = storeA
        );

        Or(
            a = isAInstruction, b = storeA,
            out = loadA,
        );

        And(
            a = isCInstruction, b = instruction[4],
            out = loadD
        );

        Not(in = instruction[15], out = isAInstruction);
        Not(in = isAInstruction, out = isCInstruction);

}```

[netalondon]

This is indeed not fixed yet, reopening.

[netalondon]

@DavidSouther maybe I'm missing something but I just don't think that the insertion sort approach is equivalent to a proper topological sort here.

Changing to a topological sort fixes this issue. (I added that in #381 without pulling in an entire graph class, just using this.insToPart and this.partsToOut if that's any better).

Again, I could be missing something, let me know what you think.

[DavidSouther]

It seems that I'm the one who's missing something - empirically, your topological sort works and the insertion sort isn't sufficient.

I'll take a closer look at #381- if I can find the difference, I'll be pleased, but we'll go with what you've got that is working.

[DavidSouther]

It sounds like in #376 we're not sure whether it's the sort or the clock order based on the internal CPU implementation?

[netalondon]

It sounds like in #376 we're not sure whether it's the sort or the clock order based on the internal CPU implementation?

Looks like a sorting issue after all.