MIPS Hardware Multiplication ALU

Question

Can someone please point out what I am doing wrong? For every right-most bit of the multiplier, if I encounter a one, I add the multiplicand in the left side of the product. Your help is appreciated.

Answer 1

From what I can tell, this appears to be a "shift and add" multiplier.

When you right shift the multiplier, you have to left shift the multiplicand. Side note: Actual ALUs may do mux/demux rather than actual shifts but the principle is the same.

While the input regs are 4 bits, since you're dealing with signed numbers you have to [effectively] sign extend before starting. And/or when right shifting it's an arithmetic right shift [shifts in the sign bit] instead of a logical right shift [shifts in a zero bit].

The ALU may or may not need 8 bit registers internally for multiplier/multiplicand, but it makes it easier to visualize to assume they are 8 bit as the product register must be 8 bits.

Here is the sequence for such a multiplier:

step    multiplier  multiplicand    product
        4           -6
1       00000100    11111010        00000000
2       00000010    11110100        00000000
3       00000001    11101000        11101000
4       00000000    11010000        11101000
5       00000000    10100000        11101000
6       00000000    01000000        11101000
7       00000000    10000000        11101000
8       00000000    00000000        11101000

step    multiplier  multiplicand    product
        -6          4
1       11111010    00000100        00000000
2       01111101    00001000        00001000
3       00111110    00010000        00001000
4       00011111    00100000        00101000
5       00001111    01000000        01101000
6       00000111    10000000        11101000
7       00000011    00000000        11101000
8       00000001    00000000        11101000

---

Here's the demo program that I used to generate the above:

#include <stdio.h>
#include <stdlib.h>

typedef unsigned int u32;

#define CMAX    8
int cidx;
char cache[CMAX][80];

char *
binof(u32 x)
{
    char *bf;

    bf = cache[cidx++];
    if (cidx >= CMAX)
        cidx = 0;

    for (int idx = 7;  idx >= 0;  --idx, x >>= 1)
        bf[idx] = (x & 1) ? '1' : '0';

    return bf;
}

void
dostep(int step,u32 x,u32 y,u32 p)
{
    printf("%d\t\t%s\t%s\t\t%s\n",step,binof(x),binof(y),binof(p));
}

void
dotest(int x,int y)
{
    u32 xu;
    u32 yu;
    u32 p;

    xu = x;
    xu &= 0xFF;

    yu = y;
    yu &= 0xFF;

    printf("step\tmultiplier\tmultiplicand\tproduct\n");
    printf("\t\t%d\t\t\t%d\n",x,y);

    p = 0;
    for (int step = 1;  step <= 8;  ++step) {
        if (xu & 1)
            p += yu;
        dostep(step,xu,yu,p);
        xu >>= 1;
        yu <<= 1;
    }
}

// main -- main program
int
main(int argc,char **argv)
{
    char *cp;

    --argc;
    ++argv;

    for (;  argc > 0;  --argc, ++argv) {
        cp = *argv;
        if (*cp != '-')
            break;

        switch (cp[1]) {
        default:
            break;
        }
    }

#if 0
    int x = atoi(argv[0]);
    int y = atoi(argv[1]);
#else
    int x = 4;
    int y = -6;
#endif
    dotest(x,y);
    printf("\n");
    dotest(y,x);

    return 0;
}

---

UPDATE:

The above is for a simple multiplier. While keeping this model, we can refine it a bit with some observations.

If either the multiplier or the multiplicand becomes zero, there is no point to continuing the steps because the product will not change further. So, we can implement an "early escape" in the ALU control logic.

This helps a lot if the multiplier is 4: We can stop after step 3 (i.e. steps 4-8 aren't necessary).

But, this doesn't help as much if the multiplier is -6. We'd have to wait until after step 6 (i.e. steps 7-8 aren't necessary).

One way to mitigate this is to add a 4 bit comparator and swap the multiplier and multiplicand values [using a multiplexer controlled by the output of the comparator] if the multiplier is greater than the multiplicand, before sending the values into sign extension and, then, the ALU/multiplier.

All of the above can be done with a minimal amount of additional circuitry.

---

Here is the demo output for these various options:

--------------------------------------------------------------------------------
TYPE: simple

step    multiplier  multiplicand    product
        4           -6
1       00000100    11111010        00000000
2       00000010    11110100        00000000
3       00000001    11101000        11101000
4       00000000    11010000        11101000
5       00000000    10100000        11101000
6       00000000    01000000        11101000
7       00000000    10000000        11101000
8       00000000    00000000        11101000
                                    -24

step    multiplier  multiplicand    product
        -6          4
1       11111010    00000100        00000000
2       01111101    00001000        00001000
3       00111110    00010000        00001000
4       00011111    00100000        00101000
5       00001111    01000000        01101000
6       00000111    10000000        11101000
7       00000011    00000000        11101000
8       00000001    00000000        11101000
                                    -24

--------------------------------------------------------------------------------
TYPE: autoswap

step    multiplier  multiplicand    product
        4           -6
1       00000100    11111010        00000000
2       00000010    11110100        00000000
3       00000001    11101000        11101000
4       00000000    11010000        11101000
5       00000000    10100000        11101000
6       00000000    01000000        11101000
7       00000000    10000000        11101000
8       00000000    00000000        11101000
                                    -24

step    multiplier  multiplicand    product
        4           -6
1       00000100    11111010        00000000
2       00000010    11110100        00000000
3       00000001    11101000        11101000
4       00000000    11010000        11101000
5       00000000    10100000        11101000
6       00000000    01000000        11101000
7       00000000    10000000        11101000
8       00000000    00000000        11101000
                                    -24

--------------------------------------------------------------------------------
TYPE: early escape

step    multiplier  multiplicand    product
        4           -6
1       00000100    11111010        00000000
2       00000010    11110100        00000000
3       00000001    11101000        11101000
                                    -24

step    multiplier  multiplicand    product
        -6          4
1       11111010    00000100        00000000
2       01111101    00001000        00001000
3       00111110    00010000        00001000
4       00011111    00100000        00101000
5       00001111    01000000        01101000
6       00000111    10000000        11101000
7       00000011    00000000        11101000
8       00000001    00000000        11101000
                                    -24

--------------------------------------------------------------------------------
TYPE: early escape with autoswap

step    multiplier  multiplicand    product
        4           -6
1       00000100    11111010        00000000
2       00000010    11110100        00000000
3       00000001    11101000        11101000
                                    -24

step    multiplier  multiplicand    product
        4           -6
1       00000100    11111010        00000000
2       00000010    11110100        00000000
3       00000001    11101000        11101000
                                    -24

---

Here is the updated demo program:

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>

typedef unsigned int u32;

#define OPUT \
    do { \
        fputc(chr,stdout); \
        olen += 1; \
    } while (0)

#define CMAX    8
int cidx;
char cache[CMAX][80];

int opt_swap;
int opt_early;

char *
binof(u32 x)
{
    char *bf;

    bf = cache[cidx++];
    if (cidx >= CMAX)
        cidx = 0;

    for (int idx = 7;  idx >= 0;  --idx, x >>= 1)
        bf[idx] = (x & 1) ? '1' : '0';

    return bf;
}

void __attribute__((__format__(__printf__,1,2)))
outf(const char *fmt,...)
{
    va_list ap;
    int chr;
    char *bp;
    int olen;
    char ibuf[100];

    va_start(ap,fmt);
    vsprintf(ibuf,fmt,ap);
    va_end(ap);

    olen = 0;
    bp = ibuf;

    for (chr = *bp++;  chr != 0;  chr = *bp++) {
        if (chr != '\t') {
            OPUT;
            continue;
        }

        chr = ' ';
        OPUT;

        while ((olen % 4) != 0)
            OPUT;
    }
}

void
dostep(int step,u32 x,u32 y,u32 p)
{
    outf("%d\t\t%s\t%s\t\t%s\n",step,binof(x),binof(y),binof(p));
}

void
dotest(int x,int y)
{
    u32 mplier;
    u32 mcand;
    int tmp;
    u32 p;

    mplier = x;
    mplier &= 0xFF;

    mcand = y;
    mcand &= 0xFF;

    if (opt_swap && ((mplier & 0x0F) > (mcand & 0x0F))) {
        p = mplier;
        mplier = mcand;
        mcand = p;

        tmp = x;
        x = y;
        y = tmp;
    }

    outf("\n");
    outf("step\tmultiplier\tmultiplicand\tproduct\n");
    outf("\t\t%d\t\t\t%d\n",x,y);

    p = 0;
    for (int step = 1;  step <= 8;  ++step) {
        if (opt_early) {
            if (mplier == 0)
                break;
            if (mcand == 0)
                break;
        }

        if (mplier & 1)
            p += mcand;
        dostep(step,mplier,mcand,p);

        mplier >>= 1;
        mcand <<= 1;
    }

    outf("\t\t\t\t\t\t\t\t\t%d\n",(char) p);
}

// main -- main program
int
main(int argc,char **argv)
{
    char *cp;
    int x;
    int y;
    int sep;
    const char *name;

    --argc;
    ++argv;

    for (;  argc > 0;  --argc, ++argv) {
        cp = *argv;
        if (*cp != '-')
            break;

        switch (cp[1]) {
        default:
            break;
        }
    }

    switch (argc) {
    case 2:
        x = atoi(argv[0]);
        y = atoi(argv[1]);
        break;
    default:
        x = 4;
        y = -6;
        break;
    }

    sep = 0;
    for (opt_early = 0;  opt_early <= 1;  ++opt_early) {
        for (opt_swap = 0;  opt_swap <= 1;  ++opt_swap) {
            switch ((opt_early << 8) | (opt_swap << 0)) {
            case 0x0101:
                name = "early escape with autoswap";
                break;
            case 0x0100:
                name = "early escape";
                break;
            case 0x0001:
                name = "autoswap";
                break;
            default:
                name = "simple";
                break;
            }

            if (sep)
                outf("\n");
            sep = 1;

            for (int olen = 1;  olen <= 80;  ++olen)
                fputc('-',stdout);
            fputc('\n',stdout);

            outf("TYPE: %s\n",name);

            dotest(x,y);
            dotest(y,x);
        }
    }

    return 0;
}