80286: Кой е най-бързият начин за умножение по 10?

За да умножа число по което и да е кратно на 2, ще го преместя толкова пъти.

Има ли такава техника за умножаване на число по 10 за по-малко цикли?


assembly x86-16 micro-optimization
person Project Zero    schedule 04.04.2020    source източник
comment
По-конкретно на 80286, така че незабавните промени са налични, но imul reg,reg,10 е бавен и 32-битовите режими на адресиране като lea ax, [eax + eax*4] не са налични за евтини x * 5? Грижи ли ви се за производителността на кода на по-късни или по-стари процесори, в случай че нещо, което е оптимално за 286, не е оптимално другаде? Имате ли връзка за времената на инструкциите 80286?   -  person Peter Cordes    schedule 04.04.2020
comment
Shift, add, shift? 10*x = (4*x + x) * 2 = ((x << 2) + x) << 1. Това е същият начин, по който правите дълго умножение на ръка.   -  person Nate Eldredge    schedule 04.04.2020
comment
Да, стари приятелю, в момента кодирам само за 80286 (16-битов)   -  person Project Zero    schedule 04.04.2020
comment
@NateEldredge Как стойността на x ще остане постоянна, докато я добавя, след като битовете се изместят?   -  person Project Zero    schedule 04.04.2020
comment
Записвате го в друг регистър. mov bx, ax ; shl ax, 2 ; add ax, bx ; shl ax, 1.   -  person Nate Eldredge    schedule 04.04.2020
comment
@NateEldredge: Да, мисля, че сме заседнали с нещо подобно. Но дали add same,same е по-бързо или по-бавно от shl reg,1 на 286 за тази последна стъпка? Вероятно няма значение в какъв ред правите нещо; 286 не може да използва ILP в x*2 + x*8 и мисля, че имаме нужда от 1 mov. Освен ако случайно вече нямате стойността в SI|DI и BX|BP, тогава можете да lea ax, [bx + si] или нещо подобно, за да започнете с x*2   -  person Peter Cordes    schedule 04.04.2020
comment
Ще бъде ли по-ефективен от MUL?   -  person Project Zero    schedule 04.04.2020
comment
@ProjectZero: На 286, да в голяма степен. Прагът за извършване на смени/добавяне вместо mul чрез константа е поне няколко зададени бита дори на P5 Pentium; 10 има само 2 зададени бита. На модерен Nehalem или по-късно, да, по-добре от 1-операнд mul, но не по-добре от imul ax, bx, 10. (закъснение от 3 цикъла, пропускателна способност 1/такт, 1 uop)   -  person Peter Cordes    schedule 04.04.2020
comment
Може ли някой от вас да публикува отговор, за да мога да го приема?   -  person Project Zero    schedule 04.04.2020
comment
Не съм сигурен как се сравняват смените и добавянията, но можете да го направите и с четири добавяния: mov bx, ax ; add ax, ax ; add ax, ax ; add ax, bx ; add ax, ax.   -  person Nate Eldredge    schedule 04.04.2020
comment
Без да знам къде да намеря времева таблица с инструкции 286, не знам коя би била най-бързата версия, така че не знам отговора. Общият метод за разделяне на умножението на смени и добавяне/подреждане е добре известен и не би бил нов. (И BTW, споменах P5 Pentium по-рано, защото можете да видите как GCC оптимизира умноженията по константи, когато се настройва за него с gcc -O3 -march=pentium. Или дори -march=i386. godbolt.org/z/qjD-a3. О, можете да компилирате за MIPS, за да ограничите GCC само до използване на shifts и add/sub, а не x86 LEA. Или може би MPS430 като 2- операндна машина.   -  person Peter Cordes    schedule 04.04.2020

Отговори (1)


arrow_upward
4
arrow_downward

80286 нямаше цилиндър за превключване, който беше въведен с 80386. Според таблиците за синхронизиране в документацията на Microsoft Macro Assembler 5.0 (1987), SHL reg, immed8 отнема 5+n цикъла, докато SHL reg, 1 отнема 2 цикъла. ADD reg, reg отнема 2 цикъла, както и MOV reg, reg. IMUL reg16, immed отнема 21 цикъла. Следователно най-бързият начин за умножение по десет изглежда е:

           ;       // cycles
shl ax, 1  ; *2    // 2
mov bx, ax ; *2    // 4
shl ax, 1  ; *4    // 6
shl ax, 1  ; *8    // 8
add ax, bx ; *10   // 10

или алтернативно:

           ;      // cycles
mov bx, ax ; *1   // 2
shl ax, 1  ; *2   // 4
shl ax, 1  ; *4   // 6
add ax, bx ; *5   // 8
shl ax, 1  ; *10  // 10

Десет цикъла така или иначе.

person njuffa    schedule 04.04.2020