MIPS硬件乘法ALU

Question

有人能指出我做错了什么吗？ 对于乘数的每个最右边位，如果遇到一个乘数，我在乘积的左边添加被乘数。 您的帮助表示赞赏。

Answer 1

从我所知道的情况来看，这似乎是一个“移位和增加”乘数。

右移乘数时，必须左移被乘数。 附注：实际的ALU可能会执行复用/解复用而不是实际的移位，但原理是相同的。

虽然输入寄存器为4位，但由于您正在处理有符号的数字，您必须在启动之前[有效]签名扩展。和/或右移时，它是一个算术右移[符号位移位]而不是逻辑右移[移入零位]。

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

---

UPDATE：

以上是一个简单的乘数。在保持这个模型的同时，我们可以通过一些观察来对其进行细化。

如果两个乘数或被乘数变为零，不存在指向继续步骤，因为产品不会进一步改变。所以，我们可以在ALU控制逻辑中实现“早期逃脱”。

如果乘数为4，我们可以停下来：我们可以在步骤3后停止（即不需要步骤4-8）。

但是，如果乘数是-6，这并没有太大的帮助。我们必须等到步骤6之后（即步骤7-8不需要）。减轻这种

的一种方式是，可以添加4位比较器和交换乘法器和被乘数值[使用由比较器的输出控制的多路转换器] 如果的乘数比大于被乘数，然后将值发送到符号扩展中，然后发送ALU /乘数。

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

---

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

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