MIPS 硬件乘法 ALU

Question

有人可以指出我做错了什么吗？对于乘数的每个最右边的位，如果我遇到一个，我会在乘积的左侧添加被乘数。感谢您的帮助。

Answer 1

据我所知，这似乎是一个 "shift and add" 乘数。

当你右移乘数时，你必须左移被乘数。 旁注：实际 ALU 可能会 mux/demux 而不是实际移位，但原理是相同的。

虽然输入寄存器是 4 位，但由于您处理的是 有符号 数字，因此您必须在开始前 [有效] 对扩展进行签名。 And/or 右移时是算术右移 [移入符号位] 而不是逻辑右移 [移入零位]。

对于 multiplier/multiplicand，ALU 内部可能需要也可能不需要 8 位寄存器，但是假设它们是 8 位更容易想象，因为乘积寄存器必须是 8 位。

下面是这种乘法器的序列：

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

这是我用来生成以上内容的演示程序：

#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;
}

更新：

以上是一个简单的乘法器。在保留这个模型的同时，我们可以通过一些观察来改进它。

如果乘数或 被乘数 变为零，则继续这些步骤没有意义，因为 product 不会进一步改变。所以，我们可以在ALU控制逻辑中实现一个"early escape"

如果乘数为 4，这将有很大帮助：我们可以在第 3 步后停止（即不需要第 4-8 步）。

但是，如果乘数为 -6，这并没有多大帮助。我们必须等到第 6 步之后（即不需要第 7-8 步）。

缓解这种情况的一种方法是添加一个 4 位比较器并交换乘数和 被乘数 值 [使用由比较器的输出] 如果乘数大于被乘数，然后将值发送到符号扩展名，然后是 ALU/multiplier.

以上所有都可以用最少的附加电路来完成。

以下是这些不同选项的演示输出：

--------------------------------------------------------------------------------
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

这是更新后的演示程序：

#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;
}

MIPS 硬件乘法 ALU

MIPS Hardware Multiplication ALU

assembly

mips

multiplication

alu