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 битого компаратора и поменять множитель и множимого значения [с помощью мультиплексора, управляемого с выходом компаратора] , еслиУмножитель больше, чем multipicand, перед отправкой значений в расширение знака, а затем 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; 
}