How do I add a multiplier to the ALU?

[kingpinzs]

I was reading a bunch of home brew cpu sites and was wondering how I could add a hardware multiplier?
I know it can be done in software but I figure it would be faster if it is put in the hardware.

Also I read about a look ahead carry to make the adder faster. How could I get started on that?


Thanks

[cadet1620]

kingpinzs wrote

I was reading a bunch of home brew cpu sites and was wondering how I could add a hardware multiplier?
I know it can be done in software but I figure it would be faster if it is put in the hardware.

Adding a hardware multiplier to the Hack computer is a fairly big task.  You will need to use one of the "always one" bits in the I-instruction to select multiplying in the ALU.  The hardware multiplier itself basically implements the grade-school long multiplication algorithm in binary.  For 16-bit unsigned multiply the 16 partial products are generated by ANDing the multiplicand by each bit of the multiplier, and the partial products are then added using 15 16-bit adders.

That's 256 ANDs, 225 Full Adders, and 15 Half Adders!

--Mark

[cadet1620]

kingpinzs wrote

Also I read about a look ahead carry to make the adder faster. How could I get started on that?

I'd recommend using LogiSim (http://ozark.hendrix.edu/~burch/logisim/) to explore lookahead carry adders.

I was playing with lookahead carry adders in Logisim a couple month ago.  If you'd like my .circ file let me know.

--Mark

[artvanderlay]

Here's a 4 bit multiplier... simple to extend.

CHIP Mul4 {
    IN a[4], b[4];
    OUT sum[8];

    PARTS:
        Mux16(b[0..3]=a[0..3], b[4..15]=false, a[0..15]=false, sel=b[0], out=s1);
        Mux16(b[1..4]=a[0..3], b[5..15]=false, b[0]=false, a[0..15]=false, sel=b[1], out=s2);
        Mux16(b[2..5]=a[0..3], b[6..15]=false, b[0..1]=false, a[0..15]=false, sel=b[2], out=s3);
        Mux16(b[3..6]=a[0..3], b[7..15]=false, b[0..2]=false, a[0..15]=false, sel=b[3], out=s4);
        Add16(a=s1, b=s2, out=i1);
        Add16(a=s3, b=s4, out=i2);
        Add16(a=i1, b=i2, out[0..7]=sum);
}