Блог

Главная - Вопросы по программированию - Модуль аппаратного умножения MIPS

Модуль аппаратного умножения MIPS

#assembly #mips #multiplication #alu

#сборка #mips #умножение #alu

Вопрос:

введите описание изображения здесь

Может кто-нибудь, пожалуйста, указать, что я делаю неправильно? Для каждого самого правого бита множителя, если я сталкиваюсь с единицей, я добавляю множитель в левой части произведения. Мы ценим вашу помощь.

Ответ №1:

Из того, что я могу сказать, это, по-видимому, множитель «сдвига и добавления».

Когда вы сдвигаете множитель вправо, вы должны сдвинуть множитель влево. Примечание: фактические ALU могут выполнять мультиплексирование / демультиплексирование, а не фактические сдвиги, но принцип тот же.

Хотя входные правила равны 4 битам, поскольку вы имеете дело с числами со знаком, вы должны [эффективно] подписать extend перед запуском. И / или при сдвиге вправо это арифметический сдвиг вправо [сдвиги в знаковом бите] вместо логического сдвига вправо [сдвиги в нулевом бите].

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 amp; 1) ? '1' : '0';

    return bf;
}

void
dostep(int step,u32 x,u32 y,u32 p)
{
    printf("%dtt%st%stt%sn",step,binof(x),binof(y),binof(p));
}

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

    xu = x;
    xu amp;= 0xFF;

    yu = y;
    yu amp;= 0xFF;

    printf("steptmultipliertmultiplicandtproductn");
    printf("tt%dttt%dn",x,y);

    p = 0;
    for (int step = 1;  step <= 8;    step) {
        if (xu amp; 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;
}

Обновить:

Выше приведено для простого множителя. Сохраняя эту модель, мы можем немного усовершенствовать ее с помощью некоторых наблюдений.

Если множитель или множимая становятся равными нулю, нет смысла продолжать шаги, потому что продукт больше не изменится. Итак, мы можем реализовать «ранний выход» в логике управления ALU.

Это очень помогает, если множитель равен 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 amp; 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("%dtt%st%stt%sn",step,binof(x),binof(y),binof(p));
}

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

    mplier = x;
    mplier amp;= 0xFF;

    mcand = y;
    mcand amp;= 0xFF;

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

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

    outf("n");
    outf("steptmultipliertmultiplicandtproductn");
    outf("tt%dttt%dn",x,y);

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

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

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

    outf("ttttttttt%dn",(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: %sn",name);

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

    return 0;
}

Комментарии:

1. вы используете более старый алгоритм, который намного медленнее обрабатывает умножение.

2. Да, без сомнения. Shift-and-add является базовым, но медленным. «Реальный» множитель использовал бы больше схем для выполнения этого за один или два цикла. На диаграмме недостаточно информации [например, что делает блок control-test, что находится в путях обратной связи или комбинаторной логике в блоке ALU и т. Д.]. Эта информация подразумевается на основе модели, которую вы изучали (например, деревья Уоллеса и т. Д.).Итак, основываясь на том, что я мог видеть, и на том, что у вас было в таблице, я должен был догадаться.