Faster алгарытм множання 16bit для 8-бітнага MCU

Я шукаю алгарытм множання двух цэлых лікаў, якія лепш, чым ніжэй. У вас ёсць добрая ідэя пра тое, што? (БУМ - AT малалетка 84/85 ці аналагічны - дзе гэты код працуе не мае аператара мул/спраў)

uint16_t umul16_(uint16_t a, uint16_t b)
{
    uint16_t res=0;

    while (b) {
        if ( (b & 1) )
            res+=a;
        b>>=1;
        a+=a;
    }

    return res;
}

Гэты алгарытм, пры кампіляцыі для AT Малюсенькі 85/84 з выкарыстаннем AVR-GCC кампілятар, практычна ідэнтычны алгарытме __mulhi3 генеруе Арн-GCC.

Алгарытм Арн-НКУ:

00000106 <__mulhi3>:
 106:   00 24           eor r0, r0
 108:   55 27           eor r21, r21
 10a:   04 c0           rjmp    .+8         ; 0x114 <__mulhi3+0xe>
 10c:   08 0e           add r0, r24
 10e:   59 1f           adc r21, r25
 110:   88 0f           add r24, r24
 112:   99 1f           adc r25, r25
 114:   00 97           sbiw    r24, 0x00   ; 0
 116:   29 f0           breq    .+10        ; 0x122 <__mulhi3+0x1c>
 118:   76 95           lsr r23
 11a:   67 95           ror r22
 11c:   b8 f3           brcs    .-18        ; 0x10c <__mulhi3+0x6>
 11e:   71 05           cpc r23, r1
 120:   b9 f7           brne    .-18        ; 0x110 <__mulhi3+0xa>
 122:   80 2d           mov r24, r0
 124:   95 2f           mov r25, r21
 126:   08 95           ret

umul16_ алгарытм:

00000044 :
  44:   20 e0           ldi r18, 0x00   ; 0
  46:   30 e0           ldi r19, 0x00   ; 0
  48:   61 15           cp  r22, r1
  4a:   71 05           cpc r23, r1
  4c:   49 f0           breq    .+18        ; 0x60 
  4e:   60 ff           sbrs    r22, 0
  50:   02 c0           rjmp    .+4         ; 0x56 
  52:   28 0f           add r18, r24
  54:   39 1f           adc r19, r25
  56:   76 95           lsr r23
  58:   67 95           ror r22
  5a:   88 0f           add r24, r24
  5c:   99 1f           adc r25, r25
  5e:   f4 cf           rjmp    .-24        ; 0x48 
  60:   c9 01           movw    r24, r18
  62:   08 95           ret

змяніць: The instruction set is available тут.
21
Пацвердзілі вы таксама, што ён вырабляе такое ж (правільны) вынік?
дададзена аўтар Antonio, крыніца
Пацвердзілі вы таксама, што ён вырабляе такое ж (правільны) вынік?
дададзена аўтар Antonio, крыніца
Пацвердзілі вы таксама, што ён вырабляе такое ж (правільны) вынік?
дададзена аўтар Antonio, крыніца
Ідэя паспрабаваць (даволі слабы) Я мяркую, замяніўшы а + = а; з а << = 1 не мяняе нічога ў згенераваным кодзе, правільна?
дададзена аўтар Antonio, крыніца
Ідэя паспрабаваць (даволі слабы) Я мяркую, замяніўшы а + = а; з а << = 1 не мяняе нічога ў згенераваным кодзе, правільна?
дададзена аўтар Antonio, крыніца
Ідэя паспрабаваць (даволі слабы) Я мяркую, замяніўшы а + = а; з а << = 1 не мяняе нічога ў згенераваным кодзе, правільна?
дададзена аўтар Antonio, крыніца
@SergioFormiggini Адно невялікае паляпшэнне было б першым параўнаць і б, і памяняць іх месцамі, калі а <�Ь : Вы павінны выкарыстоўваць у якасці B Меншае з двух, так што вы мае мінімальная колькасць цыклаў.
дададзена аўтар Antonio, крыніца
@SergioFormiggini Адно невялікае паляпшэнне было б першым параўнаць і б, і памяняць іх месцамі, калі а <�Ь : Вы павінны выкарыстоўваць у якасці B Меншае з двух, так што вы мае мінімальная колькасць цыклаў.
дададзена аўтар Antonio, крыніца
Я да тэарэтычных 72 цыклаў, але ... Мінус я лічу, немагчыма! Дык вось 4,5 мікрасекунды. Я думаю, вы павінны дадаць больш дэталяў да вашага пытання, каб растлумачыць, чаму вы абмежаванне на 32 або 48. Можа быць, мы можам знайсці спосаб падзяліць апрацоўку ў двух выклікаў?
дададзена аўтар Antonio, крыніца
Я да тэарэтычных 72 цыклаў, але ... Мінус я лічу, немагчыма! Дык вось 4,5 мікрасекунды. Я думаю, вы павінны дадаць больш дэталяў да вашага пытання, каб растлумачыць, чаму вы абмежаванне на 32 або 48. Можа быць, мы можам знайсці спосаб падзяліць апрацоўку ў двух выклікаў?
дададзена аўтар Antonio, крыніца
Я да тэарэтычных 72 цыклаў, але ... Мінус я лічу, немагчыма! Дык вось 4,5 мікрасекунды. Я думаю, вы павінны дадаць больш дэталяў да вашага пытання, каб растлумачыць, чаму вы абмежаванне на 32 або 48. Можа быць, мы можам знайсці спосаб падзяліць апрацоўку ў двух выклікаў?
дададзена аўтар Antonio, крыніца
Я казаў, што «немагчыма»? :) Я павінен быць у стане ісці да 64 цыклаў, я дам вам ведаць.
дададзена аўтар Antonio, крыніца
Я казаў, што «немагчыма»? :) Я павінен быць у стане ісці да 64 цыклаў, я дам вам ведаць.
дададзена аўтар Antonio, крыніца
Я казаў, што «немагчыма»? :) Я павінен быць у стане ісці да 64 цыклаў, я дам вам ведаць.
дададзена аўтар Antonio, крыніца
16х16 шматзарадныя павінна прывесці ў выніку 32-бітным інакш іх верагоднасць таго, што біты высокага парадку будуць страчаныя. І.Я. 65535 * 65535 = 4294967295, які патрабуе 32 біта для прадстаўлення
дададзена аўтар user3629249, крыніца
16х16 шматзарадныя павінна прывесці ў выніку 32-бітным інакш іх верагоднасць таго, што біты высокага парадку будуць страчаныя. І.Я. 65535 * 65535 = 4294967295, які патрабуе 32 біта для прадстаўлення
дададзена аўтар user3629249, крыніца
16х16 шматзарадныя павінна прывесці ў выніку 32-бітным інакш іх верагоднасць таго, што біты высокага парадку будуць страчаныя. І.Я. 65535 * 65535 = 4294967295, які патрабуе 32 біта для прадстаўлення
дададзена аўтар user3629249, крыніца
Вы можаце напісаць uint8_t мула (uint8_t, uint8_t) і uint16_t mul_wide (uint8_t, uint8_t) , а затым апрацаваць uint16_t як multiprecision цэлы лік, якое складаецца з два 8-бітных слоў.
дададзена аўтар Hurkyl, крыніца
Вы можаце напісаць uint8_t мула (uint8_t, uint8_t) і uint16_t mul_wide (uint8_t, uint8_t) , а затым апрацаваць uint16_t як multiprecision цэлы лік, якое складаецца з два 8-бітных слоў.
дададзена аўтар Hurkyl, крыніца
@Sergio: Магчыма, самае важнае ў тым, што, так як у вас павольны алгарытм множання, Карацуба можа даць перавагу. Нават калі няма, то я не ведаю падрабязнасцяў вашай архітэктуры, але гэта можа быць магчыма, што праца з 8-бітнымі кавалкамі можа апынуцца больш эфектыўным.
дададзена аўтар Hurkyl, крыніца
@Sergio: Магчыма, самае важнае ў тым, што, так як у вас павольны алгарытм множання, Карацуба можа даць перавагу. Нават калі няма, то я не ведаю падрабязнасцяў вашай архітэктуры, але гэта можа быць магчыма, што праца з 8-бітнымі кавалкамі можа апынуцца больш эфектыўным.
дададзена аўтар Hurkyl, крыніца
@Sergio: Магчыма, самае важнае ў тым, што, так як у вас павольны алгарытм множання, Карацуба можа даць перавагу. Нават калі няма, то я не ведаю падрабязнасцяў вашай архітэктуры, але гэта можа быць магчыма, што праца з 8-бітнымі кавалкамі можа апынуцца больш эфектыўным.
дададзена аўтар Hurkyl, крыніца
Што вы маеце на ўвазе з сімвалам «^»? Я думаю, што вы маеце на ўвазе "улада"! Як я магу вылічыць Pow (х, 2); калі ў мяне няма множання?
дададзена аўтар Sir Jo Black, крыніца
Што вы маеце на ўвазе з сімвалам «^»? Я думаю, што вы маеце на ўвазе "улада"! Як я магу вылічыць Pow (х, 2); калі ў мяне няма множання?
дададзена аўтар Sir Jo Black, крыніца
Што вы маеце на ўвазе з сімвалам «^»? Я думаю, што вы маеце на ўвазе "улада"! Як я магу вылічыць Pow (х, 2); калі ў мяне няма множання?
дададзена аўтар Sir Jo Black, крыніца
@Antonio, здаецца, гэта працуе! Я выкарыстоўваю яго для тэставання!
дададзена аўтар Sir Jo Black, крыніца
@Antonio, здаецца, гэта працуе! Я выкарыстоўваю яго для тэставання!
дададзена аўтар Sir Jo Black, крыніца
@Antonio, здаецца, гэта працуе! Я выкарыстоўваю яго для тэставання!
дададзена аўтар Sir Jo Black, крыніца
Я спрабаваў, але кампілятар аддае перавагу выкарыстанне + = а !!! :) Тым не менш, на AVR Малюсенькія 85, дадаць ці LSL маюць аднолькавы час цыклу!
дададзена аўтар Sir Jo Black, крыніца
Я спрабаваў, але кампілятар аддае перавагу выкарыстанне + = а !!! :) Тым не менш, на AVR Малюсенькія 85, дадаць ці LSL маюць аднолькавы час цыклу!
дададзена аўтар Sir Jo Black, крыніца
Я спрабаваў, але кампілятар аддае перавагу выкарыстанне + = а !!! :) Тым не менш, на AVR Малюсенькія 85, дадаць ці LSL маюць аднолькавы час цыклу!
дададзена аўтар Sir Jo Black, крыніца
Я думаю, што лепшы алгарытм будзе мець іншы падыход! Але я не знаходжу! ... Мне гэта трэба для працяглага цэлалікавага вылічэнні! (Гэта таксама пытанне, каб выкарыстоўваць розум ...)
дададзена аўтар Sir Jo Black, крыніца
Я думаю, што лепшы алгарытм будзе мець іншы падыход! Але я не знаходжу! ... Мне гэта трэба для працяглага цэлалікавага вылічэнні! (Гэта таксама пытанне, каб выкарыстоўваць розум ...)
дададзена аўтар Sir Jo Black, крыніца
Я думаю, што лепшы алгарытм будзе мець іншы падыход! Але я не знаходжу! ... Мне гэта трэба для працяглага цэлалікавага вылічэнні! (Гэта таксама пытанне, каб выкарыстоўваць розум ...)
дададзена аўтар Sir Jo Black, крыніца
@Hurkyl. Я не разумею перавага!? Чым я, каб разгледзець таксама насіць з сабой!
дададзена аўтар Sir Jo Black, крыніца
@Hurkyl. Я не разумею перавага!? Чым я, каб разгледзець таксама насіць з сабой!
дададзена аўтар Sir Jo Black, крыніца
@Antonio, своп будзе добрай ідэяй! :)
дададзена аўтар Sir Jo Black, крыніца
@Antonio, своп будзе добрай ідэяй! :)
дададзена аўтар Sir Jo Black, крыніца
Я, каб праверыць, ці з'яўляецца паляпшэнне падпампоўкі павялічыць хуткасць працы алгарытму ... Я думаю, што крыху, але ён можа ўвесці іншыя comparition, якія могуць знізіць агульную хуткасць вылічэнняў.
дададзена аўтар Sir Jo Black, крыніца
Я, каб праверыць, ці з'яўляецца паляпшэнне падпампоўкі павялічыць хуткасць працы алгарытму ... Я думаю, што крыху, але ён можа ўвесці іншыя comparition, якія могуць знізіць агульную хуткасць вылічэнняў.
дададзена аўтар Sir Jo Black, крыніца
Я, каб праверыць, ці з'яўляецца паляпшэнне падпампоўкі павялічыць хуткасць працы алгарытму ... Я думаю, што крыху, але ён можа ўвесці іншыя comparition, якія могуць знізіць агульную хуткасць вылічэнняў.
дададзена аўтар Sir Jo Black, крыніца
@Hurkyl! MCU я выкарыстоўваю мае 8-бітавы слова, то алгарытм ужо кіраваныя з 8 бітнымі рэгістрамі!
дададзена аўтар Sir Jo Black, крыніца
@Hurkyl! MCU я выкарыстоўваю мае 8-бітавы слова, то алгарытм ужо кіраваныя з 8 бітнымі рэгістрамі!
дададзена аўтар Sir Jo Black, крыніца
@Hurkyl! MCU я выкарыстоўваю мае 8-бітавы слова, то алгарытм ужо кіраваныя з 8 бітнымі рэгістрамі!
дададзена аўтар Sir Jo Black, крыніца
@greybeard! Я думаю, што extenal прылады не Usefull, таму што іх час доступу! Я думаю, што лепш алгарытм вышэй! :)
дададзена аўтар Sir Jo Black, крыніца
@greybeard! Я думаю, што extenal прылады не Usefull, таму што іх час доступу! Я думаю, што лепш алгарытм вышэй! :)
дададзена аўтар Sir Jo Black, крыніца
@greybeard! Я думаю, што extenal прылады не Usefull, таму што іх час доступу! Я думаю, што лепш алгарытм вышэй! :)
дададзена аўтар Sir Jo Black, крыніца
Мікракантролер мае сваю ўнутраную памяць і адзіная шына можа выкарыстоўваць гэта I2C або SPI! Ён таксама мае ўнутраны EEPROM, але занадта мала, і доступ павольней, чым унутранае АЗП
дададзена аўтар Sir Jo Black, крыніца
Мікракантролер мае сваю ўнутраную памяць і адзіная шына можа выкарыстоўваць гэта I2C або SPI! Ён таксама мае ўнутраны EEPROM, але занадта мала, і доступ павольней, чым унутранае АЗП
дададзена аўтар Sir Jo Black, крыніца
Мікракантролер мае сваю ўнутраную памяць і адзіная шына можа выкарыстоўваць гэта I2C або SPI! Ён таксама мае ўнутраны EEPROM, але занадта мала, і доступ павольней, чым унутранае АЗП
дададзена аўтар Sir Jo Black, крыніца
Я выкарыстаў Varios выгляд хуткіх серыйных бараноў, звязаных з гэтым мікракантролеры! Спосаб выкарыстоўваць яго, каб выкарыстоўваць пратакол сувязі, які ўключае ў сябе ISR (ці выбарчыя працэдуры), каб атрымаць дадзеныя.
дададзена аўтар Sir Jo Black, крыніца
Я выкарыстаў Varios выгляд хуткіх серыйных бараноў, звязаных з гэтым мікракантролеры! Спосаб выкарыстоўваць яго, каб выкарыстоўваць пратакол сувязі, які ўключае ў сябе ISR (ці выбарчыя працэдуры), каб атрымаць дадзеныя.
дададзена аўтар Sir Jo Black, крыніца
Я выкарыстаў Varios выгляд хуткіх серыйных бараноў, звязаных з гэтым мікракантролеры! Спосаб выкарыстоўваць яго, каб выкарыстоўваць пратакол сувязі, які ўключае ў сябе ISR (ці выбарчыя працэдуры), каб атрымаць дадзеныя.
дададзена аўтар Sir Jo Black, крыніца
Я ведаю, што для вылічэнні грэх і таму лепшага боку, у многіх выпадках з'яўляецца выкарыстанне пошуку. Гэта быў лепшы спосаб у першым 8086 эпоху!
дададзена аўтар Sir Jo Black, крыніца
Я ведаю, што для вылічэнні грэх і таму лепшага боку, у многіх выпадках з'яўляецца выкарыстанне пошуку. Гэта быў лепшы спосаб у першым 8086 эпоху!
дададзена аўтар Sir Jo Black, крыніца
Я ведаю, што для вылічэнні грэх і таму лепшага боку, у многіх выпадках з'яўляецца выкарыстанне пошуку. Гэта быў лепшы спосаб у першым 8086 эпоху!
дададзена аўтар Sir Jo Black, крыніца
@ User3629249. Я ведаю, што гэты алгарытм можа быць лёгка разгледзець мадыфікаваны гэты факт! ... Версія я выкарыстоўваю маё вяртанне таксама 32 біт, але ідэя складаецца ў тым, каб палепшыць множанне Algo!
дададзена аўтар Sir Jo Black, крыніца
@ User3629249. Я ведаю, што гэты алгарытм можа быць лёгка разгледзець мадыфікаваны гэты факт! ... Версія я выкарыстоўваю маё вяртанне таксама 32 біт, але ідэя складаецца ў тым, каб палепшыць множанне Algo!
дададзена аўтар Sir Jo Black, крыніца
Вельмі добра! ... :)
дададзена аўтар Sir Jo Black, крыніца
Вельмі добра! ... :)
дададзена аўтар Sir Jo Black, крыніца
Вельмі добра! ... :)
дададзена аўтар Sir Jo Black, крыніца
Якія маштабы для якасці? Калі прастора меншае неспакой, даюць ((а + б) ^ 2 - (а-б) ^ 2)/4 паспрабаваць. Што вядома аб аперанда? Ці будзе 32-бітны вынік будзе больш прыдатным?
дададзена аўтар greybeard, крыніца
Якія маштабы для якасці? Калі прастора меншае неспакой, даюць ((а + б) ^ 2 - (а-б) ^ 2)/4 паспрабаваць. Што вядома аб аперанда? Ці будзе 32-бітны вынік будзе больш прыдатным?
дададзена аўтар greybeard, крыніца
Вы можаце вызначыць значэнне магутнасці па табліцы пошуку (любой функцыі, на самай справе). Выкананне поўнага цыкла «17 * 16» бітная табліцы ўпэўнена, выглядае даражэй, чым «9 * 16» бітаў табліца для 8 * 8-> 16 бітным множання выкарыстоўваецца з 8-бітнымі мікракантролерамі - менш турботы, выкарыстоўваючы знешнюю памяць. Тым не менш, вы можаце зрабіць 8 * 8-> 16, выкарыстоўваючы гэта, але Карацуба для 16 * 16 можа атрымаць складана без 18 бітных частковых твораў.
дададзена аўтар greybeard, крыніца
Вы можаце вызначыць значэнне магутнасці па табліцы пошуку (любой функцыі, на самай справе). Выкананне поўнага цыкла «17 * 16» бітная табліцы ўпэўнена, выглядае даражэй, чым «9 * 16» бітаў табліца для 8 * 8-> 16 бітным множання выкарыстоўваецца з 8-бітнымі мікракантролерамі - менш турботы, выкарыстоўваючы знешнюю памяць. Тым не менш, вы можаце зрабіць 8 * 8-> 16, выкарыстоўваючы гэта, але Карацуба для 16 * 16 можа атрымаць складана без 18 бітных частковых твораў.
дададзена аўтар greybeard, крыніца
Вы можаце вызначыць значэнне магутнасці па табліцы пошуку (любой функцыі, на самай справе). Выкананне поўнага цыкла «17 * 16» бітная табліцы ўпэўнена, выглядае даражэй, чым «9 * 16» бітаў табліца для 8 * 8-> 16 бітным множання выкарыстоўваецца з 8-бітнымі мікракантролерамі - менш турботы, выкарыстоўваючы знешнюю памяць. Тым не менш, вы можаце зрабіць 8 * 8-> 16, выкарыстоўваючы гэта, але Карацуба для 16 * 16 можа атрымаць складана без 18 бітных частковых твораў.
дададзена аўтар greybeard, крыніца
У залежнасці ад (паслядоўны) EEPROM/ўспышка супраць механічнага прылады.
дададзена аўтар greybeard, крыніца
У залежнасці ад (паслядоўны) EEPROM/ўспышка супраць механічнага прылады.
дададзена аўтар greybeard, крыніца
У залежнасці ад (паслядоўны) EEPROM/ўспышка супраць механічнага прылады.
дададзена аўтар greybeard, крыніца
Вы ведаеце, электратэхніка ці што?
дададзена аўтар greybeard, крыніца
Вы ведаеце, электратэхніка ці што?
дададзена аўтар greybeard, крыніца
Вы ведаеце, электратэхніка ці што?
дададзена аўтар greybeard, крыніца
Калі ласка, дадайце газаразмеркавальныя абмежаванне, згаданае ў каментары да адказу janm да пастаноўкі задачы.
дададзена аўтар greybeard, крыніца
Калі ласка, дадайце газаразмеркавальныя абмежаванне, згаданае ў каментары да адказу janm да пастаноўкі задачы.
дададзена аўтар greybeard, крыніца

11 адказы

<�Моцны> Рэзюмэ

  1. Разгледзім абмен а і б (Original прапанова)
  2. Спроба пазбегнуць умоўных пераходаў (Не паспяховая аптымізацыя)
  3. <�Літый> Змена формы ўваходнага формулы (адзнака каэфіцыента ўзмацнення 35%) </літый>
  4. Выдаленне дубляваць зруху
  5. <�Літый> отматывая цыкл: "аптымальны" вузел
  6. Пераканаць кампілятар, каб даць аптымальную зборку

1. Consider swapping a and b

One improvement would be to first compare a and b, and swap them if a: you should use as b the smaller of the two, so that you have the minimum number of cycles. Note that you can avoid swapping by duplicating the code (if (a then jump to a mirrored code section), алеI doubt it's worth.


2. Спроба пазбегнуць умоўных пераходаў (Не паспяховая аптымізацыя)

спроба:

uint16_t umul16_(uint16_t a, uint16_t b)
{
    ///Here swap if necessary
    uint16_t accum=0;

    while (b) {
        accum += ((b&1) * uint16_t(0xffff)) & a; //Hopefully this multiplication is optimized away
        b>>=1;
        a+=a;
    }

    return accum;
}

З адваротнага Сэрджыа, гэта не прынесла паляпшэння.


3. Змена формы ўваходнага формулы

Улічваючы, што мэтавая архітэктура мае ў асноўным толькі інструкцыі 8bit, калі вы падзеліце верхнюю і ніжнюю 8 біт ўваходных зменных, вы можаце напісаць:

a = a1 * 0xff + a0;
b = b1 * 0xff + b0;

a * b = a1 * b1 * 0xffff + a0 * b1 * 0xff + a1 * b0 * 0xff + a0 * b0

Цяпер, класная рэч, што мы можам выкінуць тэрмін a1 * b1 * 0xffff , паколькі 0xffff адправіць яго з рэестра .

(16bit) a * b = a0 * b1 * 0xff + a1 * b0 * 0xff + a0 * b0

Акрамя таго, А0 * b1 і а1 * b0 тэрмін можа разглядацца як 8bit множання, з-за 0xff : любая частка, якая перавышае 256 будзе выслалі з рэгістра .

So far exciting! ... But, here comes reality striking: a0 * b0 has to be treated as a 16 bit multiplication, as you'll have to keep all resulting bits. a0 will have to be kept on 16 bit to allow shift lefts. This multiplication has half of the iterations of a * b, it is in part 8bit (because of b0) алеyou still have to take into account the 2 8bit multiplications mentioned before, and the final result composition. We need further reshaping!

Так што цяпер я збіраю b0 .

(16bit) a * b = a0 * b1 * 0xff + b0 * (a0 + a1 * 0xff)

але

(a0 + a1 * 0xff) = a

Такім чынам, мы атрымліваем:

(16bit) a * b = a0 * b1 * 0xff + b0 * a

Калі N былі цыкламі зыходнага кода <> а * Ь </​​код>, цяпер першы член ўяўляе сабой 8-бітавы множанне на N/2 цыклаў, а другі 16bit * 8bit множання на N/2 цыклаў. Улічваючы M колькасць каманд за ітэрацыі ў зыходным A * B , то 8bit * 8bit ітэрацыі мае палову інструкцыі, а таксама 16bit * 8bit каля 80% M (адна каманда зруху менш для b0 у параўнанні з б). Мяркуючы разам мы Н/2 * М/2 + N/2 * М * 0.8 = Н * М * 0,65 складанасць, так што <�моцны> чаканы эканомія ~ 35% </моцны> з павагу да зыходнага кода <> N * M . Гукі абяцаюць .

Гэта код:

uint16_t umul16_(uint16_t a, uint16_t b)
{
    uint8_t res1 = 0;

    uint8_t a0 = a & 0xff; //This effectively needs to copy the data
    uint8_t b0 = b & 0xff; //This should be optimized away
    uint8_t b1 = b >>8; //This should be optimized away

    //Here a0 and b1 could be swapped (to have b1 < a0)
    while (b1) {///Maximum 8 cycles
        if ( (b1 & 1) )
            res1+=a0;
        b1>>=1;
        a0+=a0;
    }

    uint16_t res = (uint16_t) res1 * 256; //Should be optimized away, it's not even a copy!

    //Here swapping wouldn't make much sense
    while (b0) {///Maximum 8 cycles
        if ( (b0 & 1) )
            res+=a;
        b0>>=1;
        a+=a;
    }

    return res;
}

Акрамя таго, расшчапленне у 2-х цыклах павінна падвоіцца, тэарэтычна, верагоднасць пропуску некалькі цыклаў: N/2 можа быць невялікім завышаныя.

Малюсенькая далейшае ўдасканаленне складаецца ў прадухіленні апошняга, непатрэбнае зрух для а зменных. Невялікая рэмарка: калі небудзь b0 або b1 роўныя нулю, што прыводзіць да 2 дадатковыя інструкцыі. А ён таксама захоўвае першую праверку b0 і b1, які з'яўляецца самым дарагім, таму што ён не можа праверыць сцяг нуля Стан пасля аперацыі зруху для ўмоўнага пераходу з для пятля.

uint16_t umul16_(uint16_t a, uint16_t b)
{
    uint8_t res1 = 0;

    uint8_t a0 = a & 0xff; //This effectively needs to copy the data
    uint8_t b0 = b & 0xff; //This should be optimized away
    uint8_t b1 = b >>8; //This should be optimized away

    //Here a0 and b1 could be swapped (to have b1 < a0)
    if ( (b1 & 1) )
        res1+=a0;
    b1>>=1;
    while (b1) {///Maximum 7 cycles
        a0+=a0;
        if ( (b1 & 1) )
            res1+=a0;
        b1>>=1;
    }

    uint16_t res = (uint16_t) res1 * 256; //Should be optimized away, it's not even a copy!

    //Here swapping wouldn't make much sense
    if ( (b0 & 1) )
        res+=a;
    b0>>=1;
    while (b0) {///Maximum 7 cycles
        a+=a;
        if ( (b0 & 1) )
            res+=a;
        b0>>=1;
    }

    return res;
}

4. Выдаленне дубляваць зруху

Ці ёсць яшчэ месца для ўдасканалення? <�Моцны> Ды , так як байт a0 зрушваецца два разы . Так павінна быць перавага ў аб'яднанні двух завес. Гэта можа быць крыху больш складана пераканаць кампілятар рабіць менавіта тое, што мы хочам, асабліва рэгістр выніку.

Такім чынам, мы апрацоўваем ў тым жа цыкле b0 і b1 . Першае, што трэба звяртацца ў тым, што з'яўляецца ўмовай выхаду з цыкла? Да гэтага часу з дапамогай кнопак b0 / b1 чысціцца статус быў зручны тым, што дазваляе пазбегнуць выкарыстання лічыльніка. Акрамя таго, пасля зруху направа, сьцяг можа быць ужо ўстаноўлена, калі вынік аперацыі роўны нулю, і гэты сцяг можа дазволіць ўмоўны пераход без далейшых ацэнак.

Now the loop exit condition could be the failure of (b0 || b1). However this could require expensive computation. One solution is to compare b0 and b1 and jump to 2 different code sections: if b1 > b0 I test the condition on b1, else I test the condition on b0. I prefer another solution, with 2 loops, the first exit when b0 is zero, the second when b1 is zero. There will be cases in which I will do zero iterations in b1. The point is that in the second loop I know b0 is zero, so I can reduce the number of operations performed.

Цяпер, давайце забудзем пра стан выхаду і паспрабаваць злучыць 2 завесы папярэдняга раздзела.

uint16_t umul16_(uint16_t a, uint16_t b)
{
    uint16_t res = 0;

    uint8_t b0 = b & 0xff; //This should be optimized away
    uint8_t b1 = b >>8; //This should be optimized away

    //Swapping probably doesn't make much sense anymore
    if ( (b1 & 1) )
        res+=(uint16_t)((uint8_t)(a && 0xff))*256;
    //Hopefully the compiler understands it has simply to add the low 8bit register of a to the high 8bit register of res

    if ( (b0 & 1) )
        res+=a;

    b1>>=1;
    b0>>=1;
    while (b0) {///N cycles, maximum 7
        a+=a;
        if ( (b1 & 1) )
            res+=(uint16_t)((uint8_t)(a & 0xff))*256;
        if ( (b0 & 1) )
            res+=a;
        b1>>=1;
        b0>>=1; //I try to put as last the one that will leave the carry flag in the desired state
    }

    uint8_t a0 = a & 0xff; //Again, not a real copy алеa register selection

    while (b1) {///P cycles, maximum 7 - N cycles
        a0+=a0;
        if ( (b1 & 1) )
            res+=(uint16_t) a0 * 256;
        b1>>=1;
    }
    return res;
}

Thanks Sergio for providing the assembly generated (-Ofast). At first glance, considering the outrageous amount of mov in the code, it seems the compiler did not interpret as I wanted the hints I gave to him to interpret the registers.

Inputs are: r22,r23 and r24,25.
AVR Instruction Set: Quick reference, Detailed documentation

sbrs //Tests a single bit in a register and skips the next instruction if the bit is set. Skip takes 2 clocks. 
ldi//Load immediate, 1 clock
sbiw//Subtracts immediate to *word*, 2 clocks

    00000010 :
      10:    70 ff           sbrs    r23, 0
      12:    39 c0           rjmp    .+114        ; 0x86 <__SREG__+0x47>
      14:    41 e0           ldi    r20, 0x01    ; 1
      16:    00 97           sbiw    r24, 0x00    ; 0
      18:    c9 f1           breq    .+114        ; 0x8c <__SREG__+0x4d>
      1a:    34 2f           mov    r19, r20
      1c:    20 e0           ldi    r18, 0x00    ; 0
      1e:    60 ff           sbrs    r22, 0
      20:    07 c0           rjmp    .+14         ; 0x30 
      22:    28 0f           add    r18, r24
      24:    39 1f           adc    r19, r25
      26:    04 c0           rjmp    .+8          ; 0x30 
      28:    e4 2f           mov    r30, r20
      2a:    45 2f           mov    r20, r21
      2c:    2e 2f           mov    r18, r30
      2e:    34 2f           mov    r19, r20
      30:    76 95           lsr    r23
      32:    66 95           lsr    r22
      34:    b9 f0           breq    .+46         ; 0x64 <__SREG__+0x25>
      36:    88 0f           add    r24, r24
      38:    99 1f           adc    r25, r25
      3a:    58 2f           mov    r21, r24
      3c:    44 27           eor    r20, r20
      3e:    42 0f           add    r20, r18
      40:    53 1f           adc    r21, r19
      42:    70 ff           sbrs    r23, 0
      44:    02 c0           rjmp    .+4          ; 0x4a <__SREG__+0xb>
      46:    24 2f           mov    r18, r20
      48:    35 2f           mov    r19, r21
      4a:    42 2f           mov    r20, r18
      4c:    53 2f           mov    r21, r19
      4e:    48 0f           add    r20, r24
      50:    59 1f           adc    r21, r25
      52:    60 fd           sbrc    r22, 0
      54:    e9 cf           rjmp    .-46         ; 0x28 
      56:    e2 2f           mov    r30, r18
      58:    43 2f           mov    r20, r19
      5a:    e8 cf           rjmp    .-48         ; 0x2c 
      5c:    95 2f           mov    r25, r21
      5e:    24 2f           mov    r18, r20
      60:    39 2f           mov    r19, r25
      62:    76 95           lsr    r23
      64:    77 23           and    r23, r23
      66:    61 f0           breq    .+24         ; 0x80 <__SREG__+0x41>
      68:    88 0f           add    r24, r24
      6a:    48 2f           mov    r20, r24
      6c:    50 e0           ldi    r21, 0x00    ; 0
      6e:    54 2f           mov    r21, r20
      70:    44 27           eor    r20, r20
      72:    42 0f           add    r20, r18
      74:    53 1f           adc    r21, r19
      76:    70 fd           sbrc    r23, 0
      78:    f1 cf           rjmp    .-30         ; 0x5c <__SREG__+0x1d>
      7a:    42 2f           mov    r20, r18
      7c:    93 2f           mov    r25, r19
      7e:    ef cf           rjmp    .-34         ; 0x5e <__SREG__+0x1f>
      80:    82 2f           mov    r24, r18
      82:    93 2f           mov    r25, r19
      84:    08 95           ret
      86:    20 e0           ldi    r18, 0x00    ; 0
      88:    30 e0           ldi    r19, 0x00    ; 0
      8a:    c9 cf           rjmp    .-110        ; 0x1e 
      8c:    40 e0           ldi    r20, 0x00    ; 0
      8e:    c5 cf           rjmp    .-118        ; 0x1a 

5. отматывая цыкл: «аптымальныя» зборкі

З усёй гэтай інфармацыяй, давайце паспрабуем зразумець, што было б «аптымальным» рашэнне з улікам архітэктуры абмежаванняў. «Optimal» каціруецца, таму што «аптымальны» шмат у чым залежыць ад зыходных дадзеных, і тое, што мы хочам аптымізаваць. <�Моцны> Давайце выкажам здагадку, што мы хочам, каб аптымізаваць па ліку цыклаў на горшы выпадак . Калі мы ідзем у горшым выпадку, разгортванне цыклу з'яўляецца разумным выбарам: мы ведаем, што мы маем 8 цыклаў, і мы выдалім усе выпрабаванні, каб зразумець, калі мы скончылі (калі b0 і b1 роўныя нуль). Да гэтага часу мы выкарыстоўвалі трук «мы перамяшчаем, і мы правяраем сцяг нуля», каб праверыць, калі мы павінны былі выйсці з цыклу. Выдаленыя гэтае патрабаванне, мы можам выкарыстоўваць іншы прыём: мы перамяшчаем, і <�моцны> мы правяраем біт пераносу (біт мы паслалі з рэгiстра пры пераключэнні) <�моцны>, каб зразумець, ці павінен я абнавіць вынік . Улічваючы набор інструкцый, у зборцы «апісальны» код інструкцыя становіцца наступнай.

//Input: a = a1 * 256 + a0, b = b1 * 256 + b0
//Output: r = r1 * 256 + r0

Preliminary:
P0 r0 = 0 (CLR)
P1 r1 = 0 (CLR)

Main block:
0 Shift right b0 (LSR)
1 If carry is not set skip 2 instructions = jump to 4 (BRCC)
2 r0 = r0 + a0 (ADD)
3 r1 = r1 + a1 + carry from prev. (ADC)
4 Shift right b1 (LSR)
5 If carry is not set skip 1 instruction = jump to 7 (BRCC)
6 r1 = r1 + a0 (ADD)
7 a0 = a0 + a0 (ADD)  
8 a1 = a1 + a1 + carry from prev. (ADC)

[Repeat same instructions for another 7 times]

Галінаванне займае 1 каманду, калі не скакаць ня выклікаецца, 2 у адваротным выпадку. Усе астатнія інструкцыі 1 цыкл. Так Б1 дзяржава не мае ніякага ўплыву на колькасць цыклаў, у той час як мы маем 9 цыклаў, калі b0 = 1 і 8 цыклаў, калі b0 = 0. Падлік ініцыялізацыю, 8 ітэрацый і пропуск апошняга абнаўлення a0 і a1, у горшым выпадку, (b0 = 11111111b), мы маем у агульнай складанасці 8 * 9 + 2 - 2 = <�моцныя> 72 цыклаў </моцны>. Я не ведаю, рэалізацыя C ++ будзе пераканаць кампілятар генераваць яго. Можа быць:

 void iterate(uint8_t& b0,uint8_t& b1,uint16_t& a, uint16_t& r) {
     const uint8_t temp0 = b0;
     b0 >>=1;
     if (temp0 & 0x01) {//Will this convince him to use the carry flag?
         r += a;
     }
     const uint8_t temp1 = b1;
     b1 >>=1;
     if (temp1 & 0x01) {
         r+=(uint16_t)((uint8_t)(a & 0xff))*256;
     }
     a += a;
 }

 uint16_t umul16_(uint16_t a, uint16_t b) {
     uint16_t r = 0;
     uint8_t b0 = b & 0xff;
     uint8_t b1 = b >>8;

     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r); //Hopefully he understands he doesn't need the last update for variable a
     return r;
 }

Але, улічваючы папярэдні вынік, каб сапраўды атрымаць патрэбны код трэба сапраўды перайсці на зборку!


Нарэшце можна таксама разгледзець больш крайнюю інтэрпрэтацыю разгортвання завесы: sbrc інструкцыі/SBRS дазваляе тэставаць на канкрэтны біт рэгістра. Такім чынам, мы можам пазбегнуць зрушэння b0 і b1, і ў кожным цыкле праверкі іншы біт. Адзіная праблема заключаецца ў тым, што гэтыя інструкцыі толькі дазваляюць прапусціць наступную каманду, а не для карыстацкага скачка. Так, у «апавядальнай код» будзе выглядаць наступным чынам:

Main block:
0 Test Nth bit of b0 (SBRS). If set jump to 2 (+ 1cycle) otherwise continue with 1
1 Jump to 4 (RJMP)
2 r0 = r0 + a0 (ADD)
3 r1 = r1 + a1 + carry from prev. (ADC)
4 Test Nth bit of (SBRC). If cleared jump to 6 (+ 1cycle) otherwise continue with 5
5 r1 = r1 + a0 (ADD)
6 a0 = a0 + a0 (ADD)  
7 a1 = a1 + a1 + carry from prev. (ADC)

У той час як другая замена дазваляе зэканоміць 1 цыкл, няма відавочнай перавагі ў другім замяшчэнні. Тым не менш, я лічу, C ++ код можа быць лягчэй інтэрпрэтаваць для кампілятара. Улічваючы, 8 цыклаў, ініцыялізацыі і пропуск апошняга абнаўлення a0 і a1, мы цяпер маем 64 цыклаў .

C ++ код:

 template
 void iterateWithMask(const uint8_t& b0,const uint8_t& b1, uint16_t& a, uint16_t& r) {
     if (b0 & mask)
         r += a;
     if (b1 & mask)
         r+=(uint16_t)((uint8_t)(a & 0xff))*256;
     a += a;
 }

 uint16_t umul16_(uint16_t a, const uint16_t b) {
     uint16_t r = 0;
     const uint8_t b0 = b & 0xff;
     const uint8_t b1 = b >>8;

     iterateWithMask<0x01>(b0,b1,a,r);
     iterateWithMask<0x02>(b0,b1,a,r);
     iterateWithMask<0x04>(b0,b1,a,r);
     iterateWithMask<0x08>(b0,b1,a,r);
     iterateWithMask<0x10>(b0,b1,a,r);
     iterateWithMask<0x20>(b0,b1,a,r);
     iterateWithMask<0x40>(b0,b1,a,r);
     iterateWithMask<0x80>(b0,b1,a,r);

     //Hopefully he understands he doesn't need the last update for a
     return r;
 }

Note that in this implementation the 0x01, 0x02 are not a real value, алеjust a hint to the compiler to know which bit to test. Therefore, the mask cannot be obtained by shifting right: differently from all other functions seen so far, this has really no equivalent loop version.

Адна вялікая праблема заключаецца ў тым, што

r+=(uint16_t)((uint8_t)(a & 0xff))*256;

Гэта павінна быць проста сума верхняга рэгістра г з ніжнім рэгістра а . Ня трактаваліся, як хацелася б. Іншы варыянт:

r+=(uint16_t) 256 *((uint8_t)(a & 0xff));

6. Пераканаць кампілятар, каб даць аптымальную зборку

We can also keep a constant, and shift instead the result r. In this case we process b starting from the most significant bit. The complexity is equivalent, алеit might be easier for the compiler to digest. Also, this time we have to be careful to write explicitly the last loop, which must not do a further shift right for r.

 template
 void inverseIterateWithMask(const uint8_t& b0,const uint8_t& b1,const uint16_t& a, const uint8_t& a0, uint16_t& r) {
     if (b0 & mask)
         r += a;
     if (b1 & mask)
         r+=(uint16_t)256*a0; //Hopefully easier to understand for the compiler?
     r += r;
 }

 uint16_t umul16_(const uint16_t a, const uint16_t b) {
     uint16_t r = 0;
     const uint8_t b0 = b & 0xff;
     const uint8_t b1 = b >>8;
     const uint8_t a0 = a & 0xff;

     inverseIterateWithMask<0x80>(b0,b1,a,r);
     inverseIterateWithMask<0x40>(b0,b1,a,r);
     inverseIterateWithMask<0x20>(b0,b1,a,r);
     inverseIterateWithMask<0x10>(b0,b1,a,r);
     inverseIterateWithMask<0x08>(b0,b1,a,r);
     inverseIterateWithMask<0x04>(b0,b1,a,r);
     inverseIterateWithMask<0x02>(b0,b1,a,r);

     //Last iteration:
     if (b0 & 0x01)
         r += a;
     if (b1 & 0x01)
         r+=(uint16_t)256*a0;

     return r;
 }
17
дададзена
@Flexo я дадаў заключны раздзел і рэарганізаваны трохі папярэднія праўкі. Дайце мне ведаць, калі вы бачыце, прастора для далейшых паляпшэнняў.
дададзена аўтар Antonio, крыніца
@SergioFormiggini Я думаю, што вы знойдзеце тут -Ofast. Паглядзіце на гэтую версію майго answert : У мяне была копія устаўлены з вашага прапановы. Затым я выдаліў версію -OS. Таму я лічу, што тут эфектыўна -Ofast. Я думаў пра расшчапленні майго адказу, але я аддаю перавагу, каб захаваць яго як адзін з індэксам, у адваротным выпадку ён будзе выглядаць, як я хачу, каб толькі ўраджай (= збіраць) рэпутацыю, у той час як тое, што я шукаю ідэальны і поўны адказ :).
дададзена аўтар Antonio, крыніца
@SergioFormiggini Ці можаце вы ўдакладніць, калі прыярытэтам з'яўляецца атрыманне кароткага кода (таму рэалізацыю цыклу, хоць павольней, пераважней) або хуткі код (у гэтым выпадку разгортвання цыкла з'яўляецца адным з спосабаў, каб ісці)?
дададзена аўтар Antonio, крыніца
дададзена аўтар Antonio, крыніца
@greybeard Вам таксама іншай LSR перад sbrc . Заўвага: ОЦК у гэтым выпадку brcc .
дададзена аўтар Antonio, крыніца
Вы можаце напісаць свой адказ без напісання «рэдагаваць рэзюмэ» і «рэдагаваць N» калі ласка? Гэта вельмі рэзкае чытаць, значна лепш, каб напісаць яго з апісальным, які працуе для кагосьці, чытаючы гэта з нуля, і хай іншыя пасля адказу дарожкі праз рэдагаванне гісторыі/каментары па меры неабходнасці. (Падумайце пра гэта, як складанне кіраўніка ў тэксце кнігі, магчыма).
дададзена аўтар Flexo, крыніца
@Antonio код скампіляваны з -Os ня -Ofast. Я спрабаваў змяніць, але modifcation занадта мала !! :)
дададзена аўтар Sir Jo Black, крыніца
@Antonio, у мяне ёсць ідэя, што ваш адказ можа быць больш адказаў, такім чынам, усе тыя чытання могуць убачыць розныя алгарытмы і адпаведныя каментары ў канкрэтным адказе!
дададзена аўтар Sir Jo Black, крыніца
Так, мне патрэбен хуткі код. Код, які я скампіляваць павінен быць сабраны з -Os, таму што памяць AVR толькі 8 Кб флэш. Я склаў свой код у маім асяроддзі. Зараз я стараюся -Ofast, але я думаю, што розніца будзе мінімальная! Я думаю, што зрабіць, каб скампіляваць толькі гэты код і «пазашлюбны ISR» як -Ofast.
дададзена аўтар Sir Jo Black, крыніца
@Antonio, мая праблема ў тым, каб мець хуткі спосаб атрымаць множанне, а таксама для стварэння невялікага кода (як вы можаце прачытаць у маім адказ у тэст пытанне)! Як я ўжо казаў вам, я вырашала множання размяркоўваючы яго, але межжала дыскусію пра алгарытм множання, а затым я па-ранейшаму ў тэставанні!
дададзена аўтар Sir Jo Black, крыніца
Што трымае LSR ОЦК дадаць АДЦ sbrc дадаць LSL ROL ?
дададзена аўтар greybeard, крыніца

<�Моцны> Рэзюмэ

  1. Разгледзім абмен а і б (Original прапанова)
  2. Спроба пазбегнуць умоўных пераходаў (Не паспяховая аптымізацыя)
  3. <�Літый> Змена формы ўваходнага формулы (адзнака каэфіцыента ўзмацнення 35%) </літый>
  4. Выдаленне дубляваць зруху
  5. <�Літый> отматывая цыкл: "аптымальны" вузел
  6. Пераканаць кампілятар, каб даць аптымальную зборку

1. Consider swapping a and b

One improvement would be to first compare a and b, and swap them if a: you should use as b the smaller of the two, so that you have the minimum number of cycles. Note that you can avoid swapping by duplicating the code (if (a then jump to a mirrored code section), алеI doubt it's worth.


2. Спроба пазбегнуць умоўных пераходаў (Не паспяховая аптымізацыя)

спроба:

uint16_t umul16_(uint16_t a, uint16_t b)
{
    ///Here swap if necessary
    uint16_t accum=0;

    while (b) {
        accum += ((b&1) * uint16_t(0xffff)) & a; //Hopefully this multiplication is optimized away
        b>>=1;
        a+=a;
    }

    return accum;
}

З адваротнага Сэрджыа, гэта не прынесла паляпшэння.


3. Змена формы ўваходнага формулы

Улічваючы, што мэтавая архітэктура мае ў асноўным толькі інструкцыі 8bit, калі вы падзеліце верхнюю і ніжнюю 8 біт ўваходных зменных, вы можаце напісаць:

a = a1 * 0xff + a0;
b = b1 * 0xff + b0;

a * b = a1 * b1 * 0xffff + a0 * b1 * 0xff + a1 * b0 * 0xff + a0 * b0

Цяпер, класная рэч, што мы можам выкінуць тэрмін a1 * b1 * 0xffff , паколькі 0xffff адправіць яго з рэестра .

(16bit) a * b = a0 * b1 * 0xff + a1 * b0 * 0xff + a0 * b0

Акрамя таго, А0 * b1 і а1 * b0 тэрмін можа разглядацца як 8bit множання, з-за 0xff : любая частка, якая перавышае 256 будзе выслалі з рэгістра .

So far exciting! ... But, here comes reality striking: a0 * b0 has to be treated as a 16 bit multiplication, as you'll have to keep all resulting bits. a0 will have to be kept on 16 bit to allow shift lefts. This multiplication has half of the iterations of a * b, it is in part 8bit (because of b0) алеyou still have to take into account the 2 8bit multiplications mentioned before, and the final result composition. We need further reshaping!

Так што цяпер я збіраю b0 .

(16bit) a * b = a0 * b1 * 0xff + b0 * (a0 + a1 * 0xff)

але

(a0 + a1 * 0xff) = a

Такім чынам, мы атрымліваем:

(16bit) a * b = a0 * b1 * 0xff + b0 * a

Калі N былі цыкламі зыходнага кода <> а * Ь </​​код>, цяпер першы член ўяўляе сабой 8-бітавы множанне на N/2 цыклаў, а другі 16bit * 8bit множання на N/2 цыклаў. Улічваючы M колькасць каманд за ітэрацыі ў зыходным A * B , то 8bit * 8bit ітэрацыі мае палову інструкцыі, а таксама 16bit * 8bit каля 80% M (адна каманда зруху менш для b0 у параўнанні з б). Мяркуючы разам мы Н/2 * М/2 + N/2 * М * 0.8 = Н * М * 0,65 складанасць, так што <�моцны> чаканы эканомія ~ 35% </моцны> з павагу да зыходнага кода <> N * M . Гукі абяцаюць .

Гэта код:

uint16_t umul16_(uint16_t a, uint16_t b)
{
    uint8_t res1 = 0;

    uint8_t a0 = a & 0xff; //This effectively needs to copy the data
    uint8_t b0 = b & 0xff; //This should be optimized away
    uint8_t b1 = b >>8; //This should be optimized away

    //Here a0 and b1 could be swapped (to have b1 < a0)
    while (b1) {///Maximum 8 cycles
        if ( (b1 & 1) )
            res1+=a0;
        b1>>=1;
        a0+=a0;
    }

    uint16_t res = (uint16_t) res1 * 256; //Should be optimized away, it's not even a copy!

    //Here swapping wouldn't make much sense
    while (b0) {///Maximum 8 cycles
        if ( (b0 & 1) )
            res+=a;
        b0>>=1;
        a+=a;
    }

    return res;
}

Акрамя таго, расшчапленне у 2-х цыклах павінна падвоіцца, тэарэтычна, верагоднасць пропуску некалькі цыклаў: N/2 можа быць невялікім завышаныя.

Малюсенькая далейшае ўдасканаленне складаецца ў прадухіленні апошняга, непатрэбнае зрух для а зменных. Невялікая рэмарка: калі небудзь b0 або b1 роўныя нулю, што прыводзіць да 2 дадатковыя інструкцыі. А ён таксама захоўвае першую праверку b0 і b1, які з'яўляецца самым дарагім, таму што ён не можа праверыць сцяг нуля Стан пасля аперацыі зруху для ўмоўнага пераходу з для пятля.

uint16_t umul16_(uint16_t a, uint16_t b)
{
    uint8_t res1 = 0;

    uint8_t a0 = a & 0xff; //This effectively needs to copy the data
    uint8_t b0 = b & 0xff; //This should be optimized away
    uint8_t b1 = b >>8; //This should be optimized away

    //Here a0 and b1 could be swapped (to have b1 < a0)
    if ( (b1 & 1) )
        res1+=a0;
    b1>>=1;
    while (b1) {///Maximum 7 cycles
        a0+=a0;
        if ( (b1 & 1) )
            res1+=a0;
        b1>>=1;
    }

    uint16_t res = (uint16_t) res1 * 256; //Should be optimized away, it's not even a copy!

    //Here swapping wouldn't make much sense
    if ( (b0 & 1) )
        res+=a;
    b0>>=1;
    while (b0) {///Maximum 7 cycles
        a+=a;
        if ( (b0 & 1) )
            res+=a;
        b0>>=1;
    }

    return res;
}

4. Выдаленне дубляваць зруху

Ці ёсць яшчэ месца для ўдасканалення? <�Моцны> Ды , так як байт a0 зрушваецца два разы . Так павінна быць перавага ў аб'яднанні двух завес. Гэта можа быць крыху больш складана пераканаць кампілятар рабіць менавіта тое, што мы хочам, асабліва рэгістр выніку.

Такім чынам, мы апрацоўваем ў тым жа цыкле b0 і b1 . Першае, што трэба звяртацца ў тым, што з'яўляецца ўмовай выхаду з цыкла? Да гэтага часу з дапамогай кнопак b0 / b1 чысціцца статус быў зручны тым, што дазваляе пазбегнуць выкарыстання лічыльніка. Акрамя таго, пасля зруху направа, сьцяг можа быць ужо ўстаноўлена, калі вынік аперацыі роўны нулю, і гэты сцяг можа дазволіць ўмоўны пераход без далейшых ацэнак.

Now the loop exit condition could be the failure of (b0 || b1). However this could require expensive computation. One solution is to compare b0 and b1 and jump to 2 different code sections: if b1 > b0 I test the condition on b1, else I test the condition on b0. I prefer another solution, with 2 loops, the first exit when b0 is zero, the second when b1 is zero. There will be cases in which I will do zero iterations in b1. The point is that in the second loop I know b0 is zero, so I can reduce the number of operations performed.

Цяпер, давайце забудзем пра стан выхаду і паспрабаваць злучыць 2 завесы папярэдняга раздзела.

uint16_t umul16_(uint16_t a, uint16_t b)
{
    uint16_t res = 0;

    uint8_t b0 = b & 0xff; //This should be optimized away
    uint8_t b1 = b >>8; //This should be optimized away

    //Swapping probably doesn't make much sense anymore
    if ( (b1 & 1) )
        res+=(uint16_t)((uint8_t)(a && 0xff))*256;
    //Hopefully the compiler understands it has simply to add the low 8bit register of a to the high 8bit register of res

    if ( (b0 & 1) )
        res+=a;

    b1>>=1;
    b0>>=1;
    while (b0) {///N cycles, maximum 7
        a+=a;
        if ( (b1 & 1) )
            res+=(uint16_t)((uint8_t)(a & 0xff))*256;
        if ( (b0 & 1) )
            res+=a;
        b1>>=1;
        b0>>=1; //I try to put as last the one that will leave the carry flag in the desired state
    }

    uint8_t a0 = a & 0xff; //Again, not a real copy алеa register selection

    while (b1) {///P cycles, maximum 7 - N cycles
        a0+=a0;
        if ( (b1 & 1) )
            res+=(uint16_t) a0 * 256;
        b1>>=1;
    }
    return res;
}

Thanks Sergio for providing the assembly generated (-Ofast). At first glance, considering the outrageous amount of mov in the code, it seems the compiler did not interpret as I wanted the hints I gave to him to interpret the registers.

Inputs are: r22,r23 and r24,25.
AVR Instruction Set: Quick reference, Detailed documentation

sbrs //Tests a single bit in a register and skips the next instruction if the bit is set. Skip takes 2 clocks. 
ldi//Load immediate, 1 clock
sbiw//Subtracts immediate to *word*, 2 clocks

    00000010 :
      10:    70 ff           sbrs    r23, 0
      12:    39 c0           rjmp    .+114        ; 0x86 <__SREG__+0x47>
      14:    41 e0           ldi    r20, 0x01    ; 1
      16:    00 97           sbiw    r24, 0x00    ; 0
      18:    c9 f1           breq    .+114        ; 0x8c <__SREG__+0x4d>
      1a:    34 2f           mov    r19, r20
      1c:    20 e0           ldi    r18, 0x00    ; 0
      1e:    60 ff           sbrs    r22, 0
      20:    07 c0           rjmp    .+14         ; 0x30 
      22:    28 0f           add    r18, r24
      24:    39 1f           adc    r19, r25
      26:    04 c0           rjmp    .+8          ; 0x30 
      28:    e4 2f           mov    r30, r20
      2a:    45 2f           mov    r20, r21
      2c:    2e 2f           mov    r18, r30
      2e:    34 2f           mov    r19, r20
      30:    76 95           lsr    r23
      32:    66 95           lsr    r22
      34:    b9 f0           breq    .+46         ; 0x64 <__SREG__+0x25>
      36:    88 0f           add    r24, r24
      38:    99 1f           adc    r25, r25
      3a:    58 2f           mov    r21, r24
      3c:    44 27           eor    r20, r20
      3e:    42 0f           add    r20, r18
      40:    53 1f           adc    r21, r19
      42:    70 ff           sbrs    r23, 0
      44:    02 c0           rjmp    .+4          ; 0x4a <__SREG__+0xb>
      46:    24 2f           mov    r18, r20
      48:    35 2f           mov    r19, r21
      4a:    42 2f           mov    r20, r18
      4c:    53 2f           mov    r21, r19
      4e:    48 0f           add    r20, r24
      50:    59 1f           adc    r21, r25
      52:    60 fd           sbrc    r22, 0
      54:    e9 cf           rjmp    .-46         ; 0x28 
      56:    e2 2f           mov    r30, r18
      58:    43 2f           mov    r20, r19
      5a:    e8 cf           rjmp    .-48         ; 0x2c 
      5c:    95 2f           mov    r25, r21
      5e:    24 2f           mov    r18, r20
      60:    39 2f           mov    r19, r25
      62:    76 95           lsr    r23
      64:    77 23           and    r23, r23
      66:    61 f0           breq    .+24         ; 0x80 <__SREG__+0x41>
      68:    88 0f           add    r24, r24
      6a:    48 2f           mov    r20, r24
      6c:    50 e0           ldi    r21, 0x00    ; 0
      6e:    54 2f           mov    r21, r20
      70:    44 27           eor    r20, r20
      72:    42 0f           add    r20, r18
      74:    53 1f           adc    r21, r19
      76:    70 fd           sbrc    r23, 0
      78:    f1 cf           rjmp    .-30         ; 0x5c <__SREG__+0x1d>
      7a:    42 2f           mov    r20, r18
      7c:    93 2f           mov    r25, r19
      7e:    ef cf           rjmp    .-34         ; 0x5e <__SREG__+0x1f>
      80:    82 2f           mov    r24, r18
      82:    93 2f           mov    r25, r19
      84:    08 95           ret
      86:    20 e0           ldi    r18, 0x00    ; 0
      88:    30 e0           ldi    r19, 0x00    ; 0
      8a:    c9 cf           rjmp    .-110        ; 0x1e 
      8c:    40 e0           ldi    r20, 0x00    ; 0
      8e:    c5 cf           rjmp    .-118        ; 0x1a 

5. отматывая цыкл: «аптымальныя» зборкі

З усёй гэтай інфармацыяй, давайце паспрабуем зразумець, што было б «аптымальным» рашэнне з улікам архітэктуры абмежаванняў. «Optimal» каціруецца, таму што «аптымальны» шмат у чым залежыць ад зыходных дадзеных, і тое, што мы хочам аптымізаваць. <�Моцны> Давайце выкажам здагадку, што мы хочам, каб аптымізаваць па ліку цыклаў на горшы выпадак . Калі мы ідзем у горшым выпадку, разгортванне цыклу з'яўляецца разумным выбарам: мы ведаем, што мы маем 8 цыклаў, і мы выдалім усе выпрабаванні, каб зразумець, калі мы скончылі (калі b0 і b1 роўныя нуль). Да гэтага часу мы выкарыстоўвалі трук «мы перамяшчаем, і мы правяраем сцяг нуля», каб праверыць, калі мы павінны былі выйсці з цыклу. Выдаленыя гэтае патрабаванне, мы можам выкарыстоўваць іншы прыём: мы перамяшчаем, і <�моцны> мы правяраем біт пераносу (біт мы паслалі з рэгiстра пры пераключэнні) <�моцны>, каб зразумець, ці павінен я абнавіць вынік . Улічваючы набор інструкцый, у зборцы «апісальны» код інструкцыя становіцца наступнай.

//Input: a = a1 * 256 + a0, b = b1 * 256 + b0
//Output: r = r1 * 256 + r0

Preliminary:
P0 r0 = 0 (CLR)
P1 r1 = 0 (CLR)

Main block:
0 Shift right b0 (LSR)
1 If carry is not set skip 2 instructions = jump to 4 (BRCC)
2 r0 = r0 + a0 (ADD)
3 r1 = r1 + a1 + carry from prev. (ADC)
4 Shift right b1 (LSR)
5 If carry is not set skip 1 instruction = jump to 7 (BRCC)
6 r1 = r1 + a0 (ADD)
7 a0 = a0 + a0 (ADD)  
8 a1 = a1 + a1 + carry from prev. (ADC)

[Repeat same instructions for another 7 times]

Галінаванне займае 1 каманду, калі не скакаць ня выклікаецца, 2 у адваротным выпадку. Усе астатнія інструкцыі 1 цыкл. Так Б1 дзяржава не мае ніякага ўплыву на колькасць цыклаў, у той час як мы маем 9 цыклаў, калі b0 = 1 і 8 цыклаў, калі b0 = 0. Падлік ініцыялізацыю, 8 ітэрацый і пропуск апошняга абнаўлення a0 і a1, у горшым выпадку, (b0 = 11111111b), мы маем у агульнай складанасці 8 * 9 + 2 - 2 = <�моцныя> 72 цыклаў </моцны>. Я не ведаю, рэалізацыя C ++ будзе пераканаць кампілятар генераваць яго. Можа быць:

 void iterate(uint8_t& b0,uint8_t& b1,uint16_t& a, uint16_t& r) {
     const uint8_t temp0 = b0;
     b0 >>=1;
     if (temp0 & 0x01) {//Will this convince him to use the carry flag?
         r += a;
     }
     const uint8_t temp1 = b1;
     b1 >>=1;
     if (temp1 & 0x01) {
         r+=(uint16_t)((uint8_t)(a & 0xff))*256;
     }
     a += a;
 }

 uint16_t umul16_(uint16_t a, uint16_t b) {
     uint16_t r = 0;
     uint8_t b0 = b & 0xff;
     uint8_t b1 = b >>8;

     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r); //Hopefully he understands he doesn't need the last update for variable a
     return r;
 }

Але, улічваючы папярэдні вынік, каб сапраўды атрымаць патрэбны код трэба сапраўды перайсці на зборку!


Нарэшце можна таксама разгледзець больш крайнюю інтэрпрэтацыю разгортвання завесы: sbrc інструкцыі/SBRS дазваляе тэставаць на канкрэтны біт рэгістра. Такім чынам, мы можам пазбегнуць зрушэння b0 і b1, і ў кожным цыкле праверкі іншы біт. Адзіная праблема заключаецца ў тым, што гэтыя інструкцыі толькі дазваляюць прапусціць наступную каманду, а не для карыстацкага скачка. Так, у «апавядальнай код» будзе выглядаць наступным чынам:

Main block:
0 Test Nth bit of b0 (SBRS). If set jump to 2 (+ 1cycle) otherwise continue with 1
1 Jump to 4 (RJMP)
2 r0 = r0 + a0 (ADD)
3 r1 = r1 + a1 + carry from prev. (ADC)
4 Test Nth bit of (SBRC). If cleared jump to 6 (+ 1cycle) otherwise continue with 5
5 r1 = r1 + a0 (ADD)
6 a0 = a0 + a0 (ADD)  
7 a1 = a1 + a1 + carry from prev. (ADC)

У той час як другая замена дазваляе зэканоміць 1 цыкл, няма відавочнай перавагі ў другім замяшчэнні. Тым не менш, я лічу, C ++ код можа быць лягчэй інтэрпрэтаваць для кампілятара. Улічваючы, 8 цыклаў, ініцыялізацыі і пропуск апошняга абнаўлення a0 і a1, мы цяпер маем 64 цыклаў .

C ++ код:

 template
 void iterateWithMask(const uint8_t& b0,const uint8_t& b1, uint16_t& a, uint16_t& r) {
     if (b0 & mask)
         r += a;
     if (b1 & mask)
         r+=(uint16_t)((uint8_t)(a & 0xff))*256;
     a += a;
 }

 uint16_t umul16_(uint16_t a, const uint16_t b) {
     uint16_t r = 0;
     const uint8_t b0 = b & 0xff;
     const uint8_t b1 = b >>8;

     iterateWithMask<0x01>(b0,b1,a,r);
     iterateWithMask<0x02>(b0,b1,a,r);
     iterateWithMask<0x04>(b0,b1,a,r);
     iterateWithMask<0x08>(b0,b1,a,r);
     iterateWithMask<0x10>(b0,b1,a,r);
     iterateWithMask<0x20>(b0,b1,a,r);
     iterateWithMask<0x40>(b0,b1,a,r);
     iterateWithMask<0x80>(b0,b1,a,r);

     //Hopefully he understands he doesn't need the last update for a
     return r;
 }

Note that in this implementation the 0x01, 0x02 are not a real value, алеjust a hint to the compiler to know which bit to test. Therefore, the mask cannot be obtained by shifting right: differently from all other functions seen so far, this has really no equivalent loop version.

Адна вялікая праблема заключаецца ў тым, што

r+=(uint16_t)((uint8_t)(a & 0xff))*256;

Гэта павінна быць проста сума верхняга рэгістра г з ніжнім рэгістра а . Ня трактаваліся, як хацелася б. Іншы варыянт:

r+=(uint16_t) 256 *((uint8_t)(a & 0xff));

6. Пераканаць кампілятар, каб даць аптымальную зборку

We can also keep a constant, and shift instead the result r. In this case we process b starting from the most significant bit. The complexity is equivalent, алеit might be easier for the compiler to digest. Also, this time we have to be careful to write explicitly the last loop, which must not do a further shift right for r.

 template
 void inverseIterateWithMask(const uint8_t& b0,const uint8_t& b1,const uint16_t& a, const uint8_t& a0, uint16_t& r) {
     if (b0 & mask)
         r += a;
     if (b1 & mask)
         r+=(uint16_t)256*a0; //Hopefully easier to understand for the compiler?
     r += r;
 }

 uint16_t umul16_(const uint16_t a, const uint16_t b) {
     uint16_t r = 0;
     const uint8_t b0 = b & 0xff;
     const uint8_t b1 = b >>8;
     const uint8_t a0 = a & 0xff;

     inverseIterateWithMask<0x80>(b0,b1,a,r);
     inverseIterateWithMask<0x40>(b0,b1,a,r);
     inverseIterateWithMask<0x20>(b0,b1,a,r);
     inverseIterateWithMask<0x10>(b0,b1,a,r);
     inverseIterateWithMask<0x08>(b0,b1,a,r);
     inverseIterateWithMask<0x04>(b0,b1,a,r);
     inverseIterateWithMask<0x02>(b0,b1,a,r);

     //Last iteration:
     if (b0 & 0x01)
         r += a;
     if (b1 & 0x01)
         r+=(uint16_t)256*a0;

     return r;
 }
17
дададзена
@Flexo я дадаў заключны раздзел і рэарганізаваны трохі папярэднія праўкі. Дайце мне ведаць, калі вы бачыце, прастора для далейшых паляпшэнняў.
дададзена аўтар Antonio, крыніца
@SergioFormiggini Я думаю, што вы знойдзеце тут -Ofast. Паглядзіце на гэтую версію майго answert : У мяне была копія устаўлены з вашага прапановы. Затым я выдаліў версію -OS. Таму я лічу, што тут эфектыўна -Ofast. Я думаў пра расшчапленні майго адказу, але я аддаю перавагу, каб захаваць яго як адзін з індэксам, у адваротным выпадку ён будзе выглядаць, як я хачу, каб толькі ўраджай (= збіраць) рэпутацыю, у той час як тое, што я шукаю ідэальны і поўны адказ :).
дададзена аўтар Antonio, крыніца
@SergioFormiggini Ці можаце вы ўдакладніць, калі прыярытэтам з'яўляецца атрыманне кароткага кода (таму рэалізацыю цыклу, хоць павольней, пераважней) або хуткі код (у гэтым выпадку разгортвання цыкла з'яўляецца адным з спосабаў, каб ісці)?
дададзена аўтар Antonio, крыніца
дададзена аўтар Antonio, крыніца
@greybeard Вам таксама іншай LSR перад sbrc . Заўвага: ОЦК у гэтым выпадку brcc .
дададзена аўтар Antonio, крыніца
Вы можаце напісаць свой адказ без напісання «рэдагаваць рэзюмэ» і «рэдагаваць N» калі ласка? Гэта вельмі рэзкае чытаць, значна лепш, каб напісаць яго з апісальным, які працуе для кагосьці, чытаючы гэта з нуля, і хай іншыя пасля адказу дарожкі праз рэдагаванне гісторыі/каментары па меры неабходнасці. (Падумайце пра гэта, як складанне кіраўніка ў тэксце кнігі, магчыма).
дададзена аўтар Flexo, крыніца
@Antonio код скампіляваны з -Os ня -Ofast. Я спрабаваў змяніць, але modifcation занадта мала !! :)
дададзена аўтар Sir Jo Black, крыніца
@Antonio, у мяне ёсць ідэя, што ваш адказ можа быць больш адказаў, такім чынам, усе тыя чытання могуць убачыць розныя алгарытмы і адпаведныя каментары ў канкрэтным адказе!
дададзена аўтар Sir Jo Black, крыніца
Так, мне патрэбен хуткі код. Код, які я скампіляваць павінен быць сабраны з -Os, таму што памяць AVR толькі 8 Кб флэш. Я склаў свой код у маім асяроддзі. Зараз я стараюся -Ofast, але я думаю, што розніца будзе мінімальная! Я думаю, што зрабіць, каб скампіляваць толькі гэты код і «пазашлюбны ISR» як -Ofast.
дададзена аўтар Sir Jo Black, крыніца
@Antonio, мая праблема ў тым, каб мець хуткі спосаб атрымаць множанне, а таксама для стварэння невялікага кода (як вы можаце прачытаць у маім адказ у тэст пытанне)! Як я ўжо казаў вам, я вырашала множання размяркоўваючы яго, але межжала дыскусію пра алгарытм множання, а затым я па-ранейшаму ў тэставанні!
дададзена аўтар Sir Jo Black, крыніца
Што трымае LSR ОЦК дадаць АДЦ sbrc дадаць LSL ROL ?
дададзена аўтар greybeard, крыніца

<�Моцны> Рэзюмэ

  1. Разгледзім абмен а і б (Original прапанова)
  2. Спроба пазбегнуць умоўных пераходаў (Не паспяховая аптымізацыя)
  3. <�Літый> Змена формы ўваходнага формулы (адзнака каэфіцыента ўзмацнення 35%) </літый>
  4. Выдаленне дубляваць зруху
  5. <�Літый> отматывая цыкл: "аптымальны" вузел
  6. Пераканаць кампілятар, каб даць аптымальную зборку

1. Consider swapping a and b

One improvement would be to first compare a and b, and swap them if a: you should use as b the smaller of the two, so that you have the minimum number of cycles. Note that you can avoid swapping by duplicating the code (if (a then jump to a mirrored code section), алеI doubt it's worth.


2. Спроба пазбегнуць умоўных пераходаў (Не паспяховая аптымізацыя)

спроба:

uint16_t umul16_(uint16_t a, uint16_t b)
{
    ///Here swap if necessary
    uint16_t accum=0;

    while (b) {
        accum += ((b&1) * uint16_t(0xffff)) & a; //Hopefully this multiplication is optimized away
        b>>=1;
        a+=a;
    }

    return accum;
}

З адваротнага Сэрджыа, гэта не прынесла паляпшэння.


3. Змена формы ўваходнага формулы

Улічваючы, што мэтавая архітэктура мае ў асноўным толькі інструкцыі 8bit, калі вы падзеліце верхнюю і ніжнюю 8 біт ўваходных зменных, вы можаце напісаць:

a = a1 * 0xff + a0;
b = b1 * 0xff + b0;

a * b = a1 * b1 * 0xffff + a0 * b1 * 0xff + a1 * b0 * 0xff + a0 * b0

Цяпер, класная рэч, што мы можам выкінуць тэрмін a1 * b1 * 0xffff , паколькі 0xffff адправіць яго з рэестра .

(16bit) a * b = a0 * b1 * 0xff + a1 * b0 * 0xff + a0 * b0

Акрамя таго, А0 * b1 і а1 * b0 тэрмін можа разглядацца як 8bit множання, з-за 0xff : любая частка, якая перавышае 256 будзе выслалі з рэгістра .

So far exciting! ... But, here comes reality striking: a0 * b0 has to be treated as a 16 bit multiplication, as you'll have to keep all resulting bits. a0 will have to be kept on 16 bit to allow shift lefts. This multiplication has half of the iterations of a * b, it is in part 8bit (because of b0) алеyou still have to take into account the 2 8bit multiplications mentioned before, and the final result composition. We need further reshaping!

Так што цяпер я збіраю b0 .

(16bit) a * b = a0 * b1 * 0xff + b0 * (a0 + a1 * 0xff)

але

(a0 + a1 * 0xff) = a

Такім чынам, мы атрымліваем:

(16bit) a * b = a0 * b1 * 0xff + b0 * a

Калі N былі цыкламі зыходнага кода <> а * Ь </​​код>, цяпер першы член ўяўляе сабой 8-бітавы множанне на N/2 цыклаў, а другі 16bit * 8bit множання на N/2 цыклаў. Улічваючы M колькасць каманд за ітэрацыі ў зыходным A * B , то 8bit * 8bit ітэрацыі мае палову інструкцыі, а таксама 16bit * 8bit каля 80% M (адна каманда зруху менш для b0 у параўнанні з б). Мяркуючы разам мы Н/2 * М/2 + N/2 * М * 0.8 = Н * М * 0,65 складанасць, так што <�моцны> чаканы эканомія ~ 35% </моцны> з павагу да зыходнага кода <> N * M . Гукі абяцаюць .

Гэта код:

uint16_t umul16_(uint16_t a, uint16_t b)
{
    uint8_t res1 = 0;

    uint8_t a0 = a & 0xff; //This effectively needs to copy the data
    uint8_t b0 = b & 0xff; //This should be optimized away
    uint8_t b1 = b >>8; //This should be optimized away

    //Here a0 and b1 could be swapped (to have b1 < a0)
    while (b1) {///Maximum 8 cycles
        if ( (b1 & 1) )
            res1+=a0;
        b1>>=1;
        a0+=a0;
    }

    uint16_t res = (uint16_t) res1 * 256; //Should be optimized away, it's not even a copy!

    //Here swapping wouldn't make much sense
    while (b0) {///Maximum 8 cycles
        if ( (b0 & 1) )
            res+=a;
        b0>>=1;
        a+=a;
    }

    return res;
}

Акрамя таго, расшчапленне у 2-х цыклах павінна падвоіцца, тэарэтычна, верагоднасць пропуску некалькі цыклаў: N/2 можа быць невялікім завышаныя.

Малюсенькая далейшае ўдасканаленне складаецца ў прадухіленні апошняга, непатрэбнае зрух для а зменных. Невялікая рэмарка: калі небудзь b0 або b1 роўныя нулю, што прыводзіць да 2 дадатковыя інструкцыі. А ён таксама захоўвае першую праверку b0 і b1, які з'яўляецца самым дарагім, таму што ён не можа праверыць сцяг нуля Стан пасля аперацыі зруху для ўмоўнага пераходу з для пятля.

uint16_t umul16_(uint16_t a, uint16_t b)
{
    uint8_t res1 = 0;

    uint8_t a0 = a & 0xff; //This effectively needs to copy the data
    uint8_t b0 = b & 0xff; //This should be optimized away
    uint8_t b1 = b >>8; //This should be optimized away

    //Here a0 and b1 could be swapped (to have b1 < a0)
    if ( (b1 & 1) )
        res1+=a0;
    b1>>=1;
    while (b1) {///Maximum 7 cycles
        a0+=a0;
        if ( (b1 & 1) )
            res1+=a0;
        b1>>=1;
    }

    uint16_t res = (uint16_t) res1 * 256; //Should be optimized away, it's not even a copy!

    //Here swapping wouldn't make much sense
    if ( (b0 & 1) )
        res+=a;
    b0>>=1;
    while (b0) {///Maximum 7 cycles
        a+=a;
        if ( (b0 & 1) )
            res+=a;
        b0>>=1;
    }

    return res;
}

4. Выдаленне дубляваць зруху

Ці ёсць яшчэ месца для ўдасканалення? <�Моцны> Ды , так як байт a0 зрушваецца два разы . Так павінна быць перавага ў аб'яднанні двух завес. Гэта можа быць крыху больш складана пераканаць кампілятар рабіць менавіта тое, што мы хочам, асабліва рэгістр выніку.

Такім чынам, мы апрацоўваем ў тым жа цыкле b0 і b1 . Першае, што трэба звяртацца ў тым, што з'яўляецца ўмовай выхаду з цыкла? Да гэтага часу з дапамогай кнопак b0 / b1 чысціцца статус быў зручны тым, што дазваляе пазбегнуць выкарыстання лічыльніка. Акрамя таго, пасля зруху направа, сьцяг можа быць ужо ўстаноўлена, калі вынік аперацыі роўны нулю, і гэты сцяг можа дазволіць ўмоўны пераход без далейшых ацэнак.

Now the loop exit condition could be the failure of (b0 || b1). However this could require expensive computation. One solution is to compare b0 and b1 and jump to 2 different code sections: if b1 > b0 I test the condition on b1, else I test the condition on b0. I prefer another solution, with 2 loops, the first exit when b0 is zero, the second when b1 is zero. There will be cases in which I will do zero iterations in b1. The point is that in the second loop I know b0 is zero, so I can reduce the number of operations performed.

Цяпер, давайце забудзем пра стан выхаду і паспрабаваць злучыць 2 завесы папярэдняга раздзела.

uint16_t umul16_(uint16_t a, uint16_t b)
{
    uint16_t res = 0;

    uint8_t b0 = b & 0xff; //This should be optimized away
    uint8_t b1 = b >>8; //This should be optimized away

    //Swapping probably doesn't make much sense anymore
    if ( (b1 & 1) )
        res+=(uint16_t)((uint8_t)(a && 0xff))*256;
    //Hopefully the compiler understands it has simply to add the low 8bit register of a to the high 8bit register of res

    if ( (b0 & 1) )
        res+=a;

    b1>>=1;
    b0>>=1;
    while (b0) {///N cycles, maximum 7
        a+=a;
        if ( (b1 & 1) )
            res+=(uint16_t)((uint8_t)(a & 0xff))*256;
        if ( (b0 & 1) )
            res+=a;
        b1>>=1;
        b0>>=1; //I try to put as last the one that will leave the carry flag in the desired state
    }

    uint8_t a0 = a & 0xff; //Again, not a real copy алеa register selection

    while (b1) {///P cycles, maximum 7 - N cycles
        a0+=a0;
        if ( (b1 & 1) )
            res+=(uint16_t) a0 * 256;
        b1>>=1;
    }
    return res;
}

Thanks Sergio for providing the assembly generated (-Ofast). At first glance, considering the outrageous amount of mov in the code, it seems the compiler did not interpret as I wanted the hints I gave to him to interpret the registers.

Inputs are: r22,r23 and r24,25.
AVR Instruction Set: Quick reference, Detailed documentation

sbrs //Tests a single bit in a register and skips the next instruction if the bit is set. Skip takes 2 clocks. 
ldi//Load immediate, 1 clock
sbiw//Subtracts immediate to *word*, 2 clocks

    00000010 :
      10:    70 ff           sbrs    r23, 0
      12:    39 c0           rjmp    .+114        ; 0x86 <__SREG__+0x47>
      14:    41 e0           ldi    r20, 0x01    ; 1
      16:    00 97           sbiw    r24, 0x00    ; 0
      18:    c9 f1           breq    .+114        ; 0x8c <__SREG__+0x4d>
      1a:    34 2f           mov    r19, r20
      1c:    20 e0           ldi    r18, 0x00    ; 0
      1e:    60 ff           sbrs    r22, 0
      20:    07 c0           rjmp    .+14         ; 0x30 
      22:    28 0f           add    r18, r24
      24:    39 1f           adc    r19, r25
      26:    04 c0           rjmp    .+8          ; 0x30 
      28:    e4 2f           mov    r30, r20
      2a:    45 2f           mov    r20, r21
      2c:    2e 2f           mov    r18, r30
      2e:    34 2f           mov    r19, r20
      30:    76 95           lsr    r23
      32:    66 95           lsr    r22
      34:    b9 f0           breq    .+46         ; 0x64 <__SREG__+0x25>
      36:    88 0f           add    r24, r24
      38:    99 1f           adc    r25, r25
      3a:    58 2f           mov    r21, r24
      3c:    44 27           eor    r20, r20
      3e:    42 0f           add    r20, r18
      40:    53 1f           adc    r21, r19
      42:    70 ff           sbrs    r23, 0
      44:    02 c0           rjmp    .+4          ; 0x4a <__SREG__+0xb>
      46:    24 2f           mov    r18, r20
      48:    35 2f           mov    r19, r21
      4a:    42 2f           mov    r20, r18
      4c:    53 2f           mov    r21, r19
      4e:    48 0f           add    r20, r24
      50:    59 1f           adc    r21, r25
      52:    60 fd           sbrc    r22, 0
      54:    e9 cf           rjmp    .-46         ; 0x28 
      56:    e2 2f           mov    r30, r18
      58:    43 2f           mov    r20, r19
      5a:    e8 cf           rjmp    .-48         ; 0x2c 
      5c:    95 2f           mov    r25, r21
      5e:    24 2f           mov    r18, r20
      60:    39 2f           mov    r19, r25
      62:    76 95           lsr    r23
      64:    77 23           and    r23, r23
      66:    61 f0           breq    .+24         ; 0x80 <__SREG__+0x41>
      68:    88 0f           add    r24, r24
      6a:    48 2f           mov    r20, r24
      6c:    50 e0           ldi    r21, 0x00    ; 0
      6e:    54 2f           mov    r21, r20
      70:    44 27           eor    r20, r20
      72:    42 0f           add    r20, r18
      74:    53 1f           adc    r21, r19
      76:    70 fd           sbrc    r23, 0
      78:    f1 cf           rjmp    .-30         ; 0x5c <__SREG__+0x1d>
      7a:    42 2f           mov    r20, r18
      7c:    93 2f           mov    r25, r19
      7e:    ef cf           rjmp    .-34         ; 0x5e <__SREG__+0x1f>
      80:    82 2f           mov    r24, r18
      82:    93 2f           mov    r25, r19
      84:    08 95           ret
      86:    20 e0           ldi    r18, 0x00    ; 0
      88:    30 e0           ldi    r19, 0x00    ; 0
      8a:    c9 cf           rjmp    .-110        ; 0x1e 
      8c:    40 e0           ldi    r20, 0x00    ; 0
      8e:    c5 cf           rjmp    .-118        ; 0x1a 

5. отматывая цыкл: «аптымальныя» зборкі

З усёй гэтай інфармацыяй, давайце паспрабуем зразумець, што было б «аптымальным» рашэнне з улікам архітэктуры абмежаванняў. «Optimal» каціруецца, таму што «аптымальны» шмат у чым залежыць ад зыходных дадзеных, і тое, што мы хочам аптымізаваць. <�Моцны> Давайце выкажам здагадку, што мы хочам, каб аптымізаваць па ліку цыклаў на горшы выпадак . Калі мы ідзем у горшым выпадку, разгортванне цыклу з'яўляецца разумным выбарам: мы ведаем, што мы маем 8 цыклаў, і мы выдалім усе выпрабаванні, каб зразумець, калі мы скончылі (калі b0 і b1 роўныя нуль). Да гэтага часу мы выкарыстоўвалі трук «мы перамяшчаем, і мы правяраем сцяг нуля», каб праверыць, калі мы павінны былі выйсці з цыклу. Выдаленыя гэтае патрабаванне, мы можам выкарыстоўваць іншы прыём: мы перамяшчаем, і <�моцны> мы правяраем біт пераносу (біт мы паслалі з рэгiстра пры пераключэнні) <�моцны>, каб зразумець, ці павінен я абнавіць вынік . Улічваючы набор інструкцый, у зборцы «апісальны» код інструкцыя становіцца наступнай.

//Input: a = a1 * 256 + a0, b = b1 * 256 + b0
//Output: r = r1 * 256 + r0

Preliminary:
P0 r0 = 0 (CLR)
P1 r1 = 0 (CLR)

Main block:
0 Shift right b0 (LSR)
1 If carry is not set skip 2 instructions = jump to 4 (BRCC)
2 r0 = r0 + a0 (ADD)
3 r1 = r1 + a1 + carry from prev. (ADC)
4 Shift right b1 (LSR)
5 If carry is not set skip 1 instruction = jump to 7 (BRCC)
6 r1 = r1 + a0 (ADD)
7 a0 = a0 + a0 (ADD)  
8 a1 = a1 + a1 + carry from prev. (ADC)

[Repeat same instructions for another 7 times]

Галінаванне займае 1 каманду, калі не скакаць ня выклікаецца, 2 у адваротным выпадку. Усе астатнія інструкцыі 1 цыкл. Так Б1 дзяржава не мае ніякага ўплыву на колькасць цыклаў, у той час як мы маем 9 цыклаў, калі b0 = 1 і 8 цыклаў, калі b0 = 0. Падлік ініцыялізацыю, 8 ітэрацый і пропуск апошняга абнаўлення a0 і a1, у горшым выпадку, (b0 = 11111111b), мы маем у агульнай складанасці 8 * 9 + 2 - 2 = <�моцныя> 72 цыклаў </моцны>. Я не ведаю, рэалізацыя C ++ будзе пераканаць кампілятар генераваць яго. Можа быць:

 void iterate(uint8_t& b0,uint8_t& b1,uint16_t& a, uint16_t& r) {
     const uint8_t temp0 = b0;
     b0 >>=1;
     if (temp0 & 0x01) {//Will this convince him to use the carry flag?
         r += a;
     }
     const uint8_t temp1 = b1;
     b1 >>=1;
     if (temp1 & 0x01) {
         r+=(uint16_t)((uint8_t)(a & 0xff))*256;
     }
     a += a;
 }

 uint16_t umul16_(uint16_t a, uint16_t b) {
     uint16_t r = 0;
     uint8_t b0 = b & 0xff;
     uint8_t b1 = b >>8;

     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r);
     iterate(b0,b1,a,r); //Hopefully he understands he doesn't need the last update for variable a
     return r;
 }

Але, улічваючы папярэдні вынік, каб сапраўды атрымаць патрэбны код трэба сапраўды перайсці на зборку!


Нарэшце можна таксама разгледзець больш крайнюю інтэрпрэтацыю разгортвання завесы: sbrc інструкцыі/SBRS дазваляе тэставаць на канкрэтны біт рэгістра. Такім чынам, мы можам пазбегнуць зрушэння b0 і b1, і ў кожным цыкле праверкі іншы біт. Адзіная праблема заключаецца ў тым, што гэтыя інструкцыі толькі дазваляюць прапусціць наступную каманду, а не для карыстацкага скачка. Так, у «апавядальнай код» будзе выглядаць наступным чынам:

Main block:
0 Test Nth bit of b0 (SBRS). If set jump to 2 (+ 1cycle) otherwise continue with 1
1 Jump to 4 (RJMP)
2 r0 = r0 + a0 (ADD)
3 r1 = r1 + a1 + carry from prev. (ADC)
4 Test Nth bit of (SBRC). If cleared jump to 6 (+ 1cycle) otherwise continue with 5
5 r1 = r1 + a0 (ADD)
6 a0 = a0 + a0 (ADD)  
7 a1 = a1 + a1 + carry from prev. (ADC)

У той час як другая замена дазваляе зэканоміць 1 цыкл, няма відавочнай перавагі ў другім замяшчэнні. Тым не менш, я лічу, C ++ код можа быць лягчэй інтэрпрэтаваць для кампілятара. Улічваючы, 8 цыклаў, ініцыялізацыі і пропуск апошняга абнаўлення a0 і a1, мы цяпер маем 64 цыклаў .

C ++ код:

 template
 void iterateWithMask(const uint8_t& b0,const uint8_t& b1, uint16_t& a, uint16_t& r) {
     if (b0 & mask)
         r += a;
     if (b1 & mask)
         r+=(uint16_t)((uint8_t)(a & 0xff))*256;
     a += a;
 }

 uint16_t umul16_(uint16_t a, const uint16_t b) {
     uint16_t r = 0;
     const uint8_t b0 = b & 0xff;
     const uint8_t b1 = b >>8;

     iterateWithMask<0x01>(b0,b1,a,r);
     iterateWithMask<0x02>(b0,b1,a,r);
     iterateWithMask<0x04>(b0,b1,a,r);
     iterateWithMask<0x08>(b0,b1,a,r);
     iterateWithMask<0x10>(b0,b1,a,r);
     iterateWithMask<0x20>(b0,b1,a,r);
     iterateWithMask<0x40>(b0,b1,a,r);
     iterateWithMask<0x80>(b0,b1,a,r);

     //Hopefully he understands he doesn't need the last update for a
     return r;
 }

Note that in this implementation the 0x01, 0x02 are not a real value, алеjust a hint to the compiler to know which bit to test. Therefore, the mask cannot be obtained by shifting right: differently from all other functions seen so far, this has really no equivalent loop version.

Адна вялікая праблема заключаецца ў тым, што

r+=(uint16_t)((uint8_t)(a & 0xff))*256;

Гэта павінна быць проста сума верхняга рэгістра г з ніжнім рэгістра а . Ня трактаваліся, як хацелася б. Іншы варыянт:

r+=(uint16_t) 256 *((uint8_t)(a & 0xff));

6. Пераканаць кампілятар, каб даць аптымальную зборку

We can also keep a constant, and shift instead the result r. In this case we process b starting from the most significant bit. The complexity is equivalent, алеit might be easier for the compiler to digest. Also, this time we have to be careful to write explicitly the last loop, which must not do a further shift right for r.

 template
 void inverseIterateWithMask(const uint8_t& b0,const uint8_t& b1,const uint16_t& a, const uint8_t& a0, uint16_t& r) {
     if (b0 & mask)
         r += a;
     if (b1 & mask)
         r+=(uint16_t)256*a0; //Hopefully easier to understand for the compiler?
     r += r;
 }

 uint16_t umul16_(const uint16_t a, const uint16_t b) {
     uint16_t r = 0;
     const uint8_t b0 = b & 0xff;
     const uint8_t b1 = b >>8;
     const uint8_t a0 = a & 0xff;

     inverseIterateWithMask<0x80>(b0,b1,a,r);
     inverseIterateWithMask<0x40>(b0,b1,a,r);
     inverseIterateWithMask<0x20>(b0,b1,a,r);
     inverseIterateWithMask<0x10>(b0,b1,a,r);
     inverseIterateWithMask<0x08>(b0,b1,a,r);
     inverseIterateWithMask<0x04>(b0,b1,a,r);
     inverseIterateWithMask<0x02>(b0,b1,a,r);

     //Last iteration:
     if (b0 & 0x01)
         r += a;
     if (b1 & 0x01)
         r+=(uint16_t)256*a0;

     return r;
 }
17
дададзена
@Flexo я дадаў заключны раздзел і рэарганізаваны трохі папярэднія праўкі. Дайце мне ведаць, калі вы бачыце, прастора для далейшых паляпшэнняў.
дададзена аўтар Antonio, крыніца
@SergioFormiggini Я думаю, што вы знойдзеце тут -Ofast. Паглядзіце на гэтую версію майго answert : У мяне была копія устаўлены з вашага прапановы. Затым я выдаліў версію -OS. Таму я лічу, што тут эфектыўна -Ofast. Я думаў пра расшчапленні майго адказу, але я аддаю перавагу, каб захаваць яго як адзін з індэксам, у адваротным выпадку ён будзе выглядаць, як я хачу, каб толькі ўраджай (= збіраць) рэпутацыю, у той час як тое, што я шукаю ідэальны і поўны адказ :).
дададзена аўтар Antonio, крыніца
@SergioFormiggini Ці можаце вы ўдакладніць, калі прыярытэтам з'яўляецца атрыманне кароткага кода (таму рэалізацыю цыклу, хоць павольней, пераважней) або хуткі код (у гэтым выпадку разгортвання цыкла з'яўляецца адным з спосабаў, каб ісці)?
дададзена аўтар Antonio, крыніца
дададзена аўтар Antonio, крыніца
@greybeard Вам таксама іншай LSR перад sbrc . Заўвага: ОЦК у гэтым выпадку brcc .
дададзена аўтар Antonio, крыніца
Вы можаце напісаць свой адказ без напісання «рэдагаваць рэзюмэ» і «рэдагаваць N» калі ласка? Гэта вельмі рэзкае чытаць, значна лепш, каб напісаць яго з апісальным, які працуе для кагосьці, чытаючы гэта з нуля, і хай іншыя пасля адказу дарожкі праз рэдагаванне гісторыі/каментары па меры неабходнасці. (Падумайце пра гэта, як складанне кіраўніка ў тэксце кнігі, магчыма).
дададзена аўтар Flexo, крыніца
@Antonio код скампіляваны з -Os ня -Ofast. Я спрабаваў змяніць, але modifcation занадта мала !! :)
дададзена аўтар Sir Jo Black, крыніца
@Antonio, у мяне ёсць ідэя, што ваш адказ можа быць больш адказаў, такім чынам, усе тыя чытання могуць убачыць розныя алгарытмы і адпаведныя каментары ў канкрэтным адказе!
дададзена аўтар Sir Jo Black, крыніца
Так, мне патрэбен хуткі код. Код, які я скампіляваць павінен быць сабраны з -Os, таму што памяць AVR толькі 8 Кб флэш. Я склаў свой код у маім асяроддзі. Зараз я стараюся -Ofast, але я думаю, што розніца будзе мінімальная! Я думаю, што зрабіць, каб скампіляваць толькі гэты код і «пазашлюбны ISR» як -Ofast.
дададзена аўтар Sir Jo Black, крыніца
@Antonio, мая праблема ў тым, каб мець хуткі спосаб атрымаць множанне, а таксама для стварэння невялікага кода (як вы можаце прачытаць у маім адказ у тэст пытанне)! Як я ўжо казаў вам, я вырашала множання размяркоўваючы яго, але межжала дыскусію пра алгарытм множання, а затым я па-ранейшаму ў тэставанні!
дададзена аўтар Sir Jo Black, крыніца
Што трымае LSR ОЦК дадаць АДЦ sbrc дадаць LSL ROL ?
дададзена аўтар greybeard, крыніца

Кампілятар можа быць у стане вырабляць больш за кароткі код, выкарыстоўваючы патройны аператар, каб выбраць, ці варта дадаць «а» да вашага акумулятара, залежыць ад кошту тэсту і галіны, і як ваш кампілятар генеруе код.

Памяняць месцамі аргументы, каб паменшыць колькасць завес.

uint16_t umul16_(uint16_t op1, uint16_t op2)
{
    uint16_t accum=0;
    uint16_t a, b;
    a=op1; b=op2;
    if( op1>=1;
        a+=a;
    }

    return accum;
}

Шмат гадоў таму я напісаў «наперад», які спрыяў Compute, а не галіновай падыход, і што прадугледжвае камплектаванне, якое значэнне для выкарыстання,

Вы можаце выкарыстоўваць масіў, каб пазбегнуць тэсту цалкам, што ваш кампілятар, верагодна, можа выкарыстоўваць для стварэння ў якасці нагрузкі ад зрушэння. Вызначыць масіў, які змяшчае два значэння 0 і а, і абнаўляць значэнне для ў канцы цыклу,

uint16_t umul16_(uint16_t op1, uint16_t op2)
{
    uint16_t accum=0;
    uint16_t pick[2];
    uint16_t a, b;
    a=op1; b=op2;
    if( op1>=1;
        pick[1] += pick[1]; //(a+=a);
    }

    return accum;
}

Так, зло . Але я не нармальна пісаць код, як гэта.

Праўка - перагледжана, каб дадаць своп да пятлі на меншае з OP1 або OP2 (меншага колькасці праходаў). Гэта выключыла б карыснасць тэставання для аргументу = 0.

4
дададзена
@SergioFormiggini Вы павінны тэст на рэальнай сістэме. Сістэма, у якой вы тэстуеце выкарыстоўвае зусім іншы набор каманд.
дададзена аўтар Antonio, крыніца
Што тычыцца тэсту, калі адзін з аргументаў роўны нулю: калі трэба памяняць месцамі аргументы, па маёй прапанове, ўмова ітэрацыі пацерпіць няўдачу пры першай праверцы, так што практычна няма ўзмацнення, у той час як вы дадасце праверка выконваецца кожны раз, калі функцыя выкліку.
дададзена аўтар Antonio, крыніца
Межжала! ;) Я павінен праверыць ...;)
дададзена аўтар Sir Jo Black, крыніца
Я сабраў гэта ... Што з патройным аператарам трохі складаным, што з вектарам залежаць ад вялікага пралогу і эпілогу! Але код вельмі крута !!! :)
дададзена аўтар Sir Jo Black, крыніца
У двух словах, дзіўна, але гэта, здаецца, скампіляваныя лепш функцыя, якая выкарыстоўвае калі!
дададзена аўтар Sir Jo Black, крыніца
Гэта з вектарам ёсць праблема, што кампілятар не можа выкарыстоўваць рэгістры непасрэдна кіраваць зместам вектар!
дададзена аўтар Sir Jo Black, крыніца
Я напісаў вам пра скампіляваць кодзе, я не спрабаваў эфектыўную хуткасць. Цяпер я магу паспрабаваць таксама з Intel I3, але я паспрабаваць з Арн ...;)
дададзена аўтар Sir Jo Black, крыніца
Як я ўжо казаў вышэй, я бачу Арн кампілятар, калі 16 біт аперанда выкарыстоўваюцца, часта выкарыстоўваюцца дадаць пры выкарыстанні зруху налева! (Я не ведаю, што, паколькі яны выкарыстоўваюць такую ​​ж колькасць цыклаў: 1)
дададзена аўтар Sir Jo Black, крыніца
Я зрабіць некаторыя тэсты ... але на сённяшні дзень у мяне няма часу ... :)
дададзена аўтар Sir Jo Black, крыніца
Ваш Векторизованный раствор (за выключэнне LUT, што я думаю, што гэта не добра для архітэктуры AVR мікракантролераў, але я тэставаў), тым хутчэй, дадаў з прапановай @Antonio крыху хутка! Я паспрабаваў функцыі з Intel I3 і 10000000 завесы множання Randoms пары 16 разраднае цэлы лік.
дададзена аўтар Sir Jo Black, крыніца
Я разумею, што нешта з-за кэш скажоны мой тэст! Хоць працэдура, якая пачынаецца гэтым пытанне мае мала карысці замены а д б, векторизованная версія працуе лепш без падпампоўкі! (Я тэстуюць на Intel I3, Я бачыць на AVR)
дададзена аўтар Sir Jo Black, крыніца
Я ведаю @Antonio! Я праверыў, каб мець агульнае ўяўленне! Я не ведаю архітэктуру I3! Мне трэба, каб праверыць з Арн!
дададзена аўтар Sir Jo Black, крыніца
Я ведаю, я рыхтую масавы тэст, а не тэсты для кожнага асобнага размовы ... Праблема ў тым, валіднасць на тое, што не з'яўляецца аб'ектам! ... Я ведаю, што AVRs не мае кэша-памяці, няма ўнутранай аптымізацыі, ня прадказанні галінаванне і г.д., і г.д. Яны павольна, але з яе дапамогай можна ведаць istruction па istruction паводзін MCU!
дададзена аўтар Sir Jo Black, крыніца
Ваш працэсар можа можа кэшаваць падборшчык [] элементы, і ў залежнасці ад розніцы ў доступе кэша для рэгістрацыі доступу, у залежнасці ад кошту пераходу, вы можаце знайсці паляпшэнне. Але <�я> розныя .
дададзена аўтар ChuckCottrill, крыніца
А выбар [1] + = выбраць [1]; можа быць хутчэй напісана выбар [1] << = 1;
дададзена аўтар ChuckCottrill, крыніца
Аб'яднаць абодва рашэнні @Antonio і шахты для добрага рашэння.
дададзена аўтар ChuckCottrill, крыніца

Кампілятар можа быць у стане вырабляць больш за кароткі код, выкарыстоўваючы патройны аператар, каб выбраць, ці варта дадаць «а» да вашага акумулятара, залежыць ад кошту тэсту і галіны, і як ваш кампілятар генеруе код.

Памяняць месцамі аргументы, каб паменшыць колькасць завес.

uint16_t umul16_(uint16_t op1, uint16_t op2)
{
    uint16_t accum=0;
    uint16_t a, b;
    a=op1; b=op2;
    if( op1>=1;
        a+=a;
    }

    return accum;
}

Шмат гадоў таму я напісаў «наперад», які спрыяў Compute, а не галіновай падыход, і што прадугледжвае камплектаванне, якое значэнне для выкарыстання,

Вы можаце выкарыстоўваць масіў, каб пазбегнуць тэсту цалкам, што ваш кампілятар, верагодна, можа выкарыстоўваць для стварэння ў якасці нагрузкі ад зрушэння. Вызначыць масіў, які змяшчае два значэння 0 і а, і абнаўляць значэнне для ў канцы цыклу,

uint16_t umul16_(uint16_t op1, uint16_t op2)
{
    uint16_t accum=0;
    uint16_t pick[2];
    uint16_t a, b;
    a=op1; b=op2;
    if( op1>=1;
        pick[1] += pick[1]; //(a+=a);
    }

    return accum;
}

Так, зло . Але я не нармальна пісаць код, як гэта.

Праўка - перагледжана, каб дадаць своп да пятлі на меншае з OP1 або OP2 (меншага колькасці праходаў). Гэта выключыла б карыснасць тэставання для аргументу = 0.

4
дададзена
@SergioFormiggini Вы павінны тэст на рэальнай сістэме. Сістэма, у якой вы тэстуеце выкарыстоўвае зусім іншы набор каманд.
дададзена аўтар Antonio, крыніца
Што тычыцца тэсту, калі адзін з аргументаў роўны нулю: калі трэба памяняць месцамі аргументы, па маёй прапанове, ўмова ітэрацыі пацерпіць няўдачу пры першай праверцы, так што практычна няма ўзмацнення, у той час як вы дадасце праверка выконваецца кожны раз, калі функцыя выкліку.
дададзена аўтар Antonio, крыніца
Межжала! ;) Я павінен праверыць ...;)
дададзена аўтар Sir Jo Black, крыніца
Я сабраў гэта ... Што з патройным аператарам трохі складаным, што з вектарам залежаць ад вялікага пралогу і эпілогу! Але код вельмі крута !!! :)
дададзена аўтар Sir Jo Black, крыніца
У двух словах, дзіўна, але гэта, здаецца, скампіляваныя лепш функцыя, якая выкарыстоўвае калі!
дададзена аўтар Sir Jo Black, крыніца
Гэта з вектарам ёсць праблема, што кампілятар не можа выкарыстоўваць рэгістры непасрэдна кіраваць зместам вектар!
дададзена аўтар Sir Jo Black, крыніца
Я напісаў вам пра скампіляваць кодзе, я не спрабаваў эфектыўную хуткасць. Цяпер я магу паспрабаваць таксама з Intel I3, але я паспрабаваць з Арн ...;)
дададзена аўтар Sir Jo Black, крыніца
Як я ўжо казаў вышэй, я бачу Арн кампілятар, калі 16 біт аперанда выкарыстоўваюцца, часта выкарыстоўваюцца дадаць пры выкарыстанні зруху налева! (Я не ведаю, што, паколькі яны выкарыстоўваюць такую ​​ж колькасць цыклаў: 1)
дададзена аўтар Sir Jo Black, крыніца
Я зрабіць некаторыя тэсты ... але на сённяшні дзень у мяне няма часу ... :)
дададзена аўтар Sir Jo Black, крыніца
Ваш Векторизованный раствор (за выключэнне LUT, што я думаю, што гэта не добра для архітэктуры AVR мікракантролераў, але я тэставаў), тым хутчэй, дадаў з прапановай @Antonio крыху хутка! Я паспрабаваў функцыі з Intel I3 і 10000000 завесы множання Randoms пары 16 разраднае цэлы лік.
дададзена аўтар Sir Jo Black, крыніца
Я разумею, што нешта з-за кэш скажоны мой тэст! Хоць працэдура, якая пачынаецца гэтым пытанне мае мала карысці замены а д б, векторизованная версія працуе лепш без падпампоўкі! (Я тэстуюць на Intel I3, Я бачыць на AVR)
дададзена аўтар Sir Jo Black, крыніца
Я ведаю @Antonio! Я праверыў, каб мець агульнае ўяўленне! Я не ведаю архітэктуру I3! Мне трэба, каб праверыць з Арн!
дададзена аўтар Sir Jo Black, крыніца
Я ведаю, я рыхтую масавы тэст, а не тэсты для кожнага асобнага размовы ... Праблема ў тым, валіднасць на тое, што не з'яўляецца аб'ектам! ... Я ведаю, што AVRs не мае кэша-памяці, няма ўнутранай аптымізацыі, ня прадказанні галінаванне і г.д., і г.д. Яны павольна, але з яе дапамогай можна ведаць istruction па istruction паводзін MCU!
дададзена аўтар Sir Jo Black, крыніца
Ваш працэсар можа можа кэшаваць падборшчык [] элементы, і ў залежнасці ад розніцы ў доступе кэша для рэгістрацыі доступу, у залежнасці ад кошту пераходу, вы можаце знайсці паляпшэнне. Але <�я> розныя .
дададзена аўтар ChuckCottrill, крыніца
А выбар [1] + = выбраць [1]; можа быць хутчэй напісана выбар [1] << = 1;
дададзена аўтар ChuckCottrill, крыніца
Аб'яднаць абодва рашэнні @Antonio і шахты для добрага рашэння.
дададзена аўтар ChuckCottrill, крыніца

Ну, сумесь з LUT і зруху, як правіла, працуе

Нешта ўздоўж лініі, памнажаючы 8-бітныя аб'екты. Давайце разгледзім іх з двух квадрацыклаў

uint4_t u1, l1, u2, l2;
uint8_t a = 16*u1 + l1;
uint8_t b = 16*u2 + l2;

product = 256*u1*u2 + 16*u1*l2 + 16*u2*l1 + l1*l1;

inline uint4_t hi( uint8_t v ) { return v >> 4; }
inline uint4_t lo( uint8_t v ) { return v & 15; }

inline uint8_t LUT( uint4_t x, uint4_t y ) {
    static uint8_t lut[256] = ...;
    return lut[x | y << 4]
}

uint16_t multiply(uint8_t a, uint8_t b) {
    return (uint16_t)LUT(hi(a), hi(b)) << 8 +
           ((uint16_t)LUT(hi(a), lo(b)) + (uint16_t)LUT(lo(a), hi(b)) << 4 +
           (uint16_t)LUT(lo(a), lo(b));
}

проста запоўніць LUT [] з вынікамі множання. У вашым выпадку ў залежнасці ад памяці, які вы маглі б пайсці з карэ (256 LUT памеру) або з байтамі (65536 памер LUT) або што-небудзь паміж імі

3
дададзена
@SergioFormiggini Ну, 256bytes ад ўспышкі, верагодна, могуць быць выкарыстаны, множанне 16bits на аўтамабілі, больш доўгае выраз, тая ж ідэя
дададзена аўтар Severin Pappadeux, крыніца
У AVRs ёсць некалькі аператыўнай памяці (Дробка 85 толькі 512 байт), але маюць 8KByte ўспышкі і 512 байт EEPROM! ... Ёсць таксама AVRs з вялікай колькасцю памяці!
дададзена аўтар Sir Jo Black, крыніца
Я паспрабаваць! Праблема заключаецца ў тым, што доступ да флэш не з'яўляецца простым і не хутка, таму што Harvard архітэктура ў AVRs выкарыстоўваць.
дададзена аўтар Sir Jo Black, крыніца
дададзена аўтар greybeard, крыніца

Адзін падыход заключаецца ў раскачаць пятлю. У мяне няма кампілятара для платформы, якую вы выкарыстоўваеце, так што я не магу глядзець на згенераваны код, але падыход, як гэта магло б дапамагчы.

Выкананне гэтага кода менш дадзеных залежыць - вы хутчэй, у горшым выпадку, не правяраючы, калі вы ў лепшым выпадку. Памер кода трохі больш, але не памер табліцы перакадыроўкі.

(Звярніце ўвагу, код тэсціравалі, з верхняй частцы маёй галавы. Мне цікава, што згенераваны код выглядае!)

#define UMUL16_STEP(a, b, shift) \
    if ((b) & (1U << (shift))) result += ((a) << (shift)));

uint16_t umul16(uint16_t a, uint16_t b)
{
    uint16_t result = 0;

    UMUL16_STEP(a, b, 0);
    UMUL16_STEP(a, b, 1);
    UMUL16_STEP(a, b, 2);
    UMUL16_STEP(a, b, 3);
    UMUL16_STEP(a, b, 4);
    UMUL16_STEP(a, b, 5);
    UMUL16_STEP(a, b, 6);
    UMUL16_STEP(a, b, 7);
    UMUL16_STEP(a, b, 8);
    UMUL16_STEP(a, b, 9);
    UMUL16_STEP(a, b, 10);
    UMUL16_STEP(a, b, 11);
    UMUL16_STEP(a, b, 12);
    UMUL16_STEP(a, b, 13);
    UMUL16_STEP(a, b, 14);
    UMUL16_STEP(a, b, 15);

    return result;
}

абнаўленне:

У залежнасці ад таго, што робіць ваш кампілятар, то UMUL16_STEP макрас можа змяніцца. Альтэрнатывай можа быць:

#define UMUL16_STEP(a, b, shift) \
    if ((b) & (1U << (shift))) result += (a); (a) << 1;

Пры такім падыходзе кампілятар можа быць у стане выкарыстаць sbrc інструкцыі, каб пазбегнуць галін.

Мая здагадка пра тое, як асэмблер павінен выглядаць на біт, r0: r1 вынік, r2: г3 а і r4: r5 з'яўляецца б :

sbrc r4, 0
add r0, r2
sbrc r4, 0
addc r1, r3
lsl r2
rol r3

Гэта павінна выконвацца ў пастаянная час без аддзялення. Праверце біты ў r4 , а затым праверыць біты ў r5 для старэйшых васьмі бітаў. Гэта павінна выканаць множанне ў 96 цыклаў, заснаваных на маім чытанні набору інструкцый па эксплуатацыі.

2
дададзена
@janm Я думаю, што я зараз ўніз на 64 цыклаў
дададзена аўтар Antonio, крыніца
Я праверу. Але я думаю, што гэта: калі ((б) і << (зрух)) (1У) вынік + = ((а) << (1U << (зрух))); будзе: калі ((б) і (1U << (зрух))) + = вынік (а << зрух). Гэты код змяшчае шмат СПМ, але з некаторымі зменамі можа даць фіксаваны адлік часу.
дададзена аўтар Sir Jo Black, крыніца
У мяне ёсць рашэнне, якое не робяць скокі, і будзе забяспечваць пастаянны час, якое павінна быць шмат межжал. Ці магу я рэдагаваць свой пост, дадаўшы мае рашэньні і мэтавай (AVR) асэмблеры? Я праверыць, але я думаю, што гэта даволі :! #Define UMUL16_STEP (а, б, зрух) вынік + = ((0 - (((Ь & (1У << (зрух)))))) & (а < <(зрух)));
дададзена аўтар Sir Jo Black, крыніца
Так, і маё рашэнне спараджае скачок! Працэсар не мае ў istruction, які паводзіць сябе, як C- «!» паводзіць сябе!
дададзена аўтар Sir Jo Black, крыніца
У тыя дні я, каб вырашыць праблему з пратаколам НВНЕЙ, які не запускаецца, але я праверыў на маім кампутары (я ведаю, што гэта не targed). На ПК ваш адзін з хуткіх рашэнняў, тым хутчэй (на ПК) застаецца Векторизованным Рашэннем @ChuckCottrill «s. Калі я магу праверыць з Арн я думаю, каб праверыць усе з AVR!
дададзена аўтар Sir Jo Black, крыніца
Мая рэальная праблема з памнажэннем сінхранізацыя, што з'яўляецца занадта строгім, у тым парадку, што я магу выкарыстоўваць 2 макс 3 мксок з 1/16 мксками цыклу каманд, таму я павінен буду выкарыстоўваць карыстацкія значэння. Але было б межжала кропку, каб мець функцыі, якія выконваюцца ў вядомы час! :)
дададзена аўтар Sir Jo Black, крыніца
@janm! Дзякуй за вашу падтрымку! Ды я гэта зразумець! На самай справе я ўжо вядома (адлюстраваны), што! :) Але я бачу гэтае пытанне, як добры аргумент! Я думаю, што гэта, па меншай меры карысна для людзей, якія будуць чытаць нас!
дададзена аўтар Sir Jo Black, крыніца
Прывітанне @janm, я тэставанне алгарытму тут з выкарыстаннем ATmega168 і з крыху здзіўлення, я бачыў, што Althoug otpimization -Os, ваш разгорнуты алгарытм складзены з выкарыстаннем каманды MUL, замест таго, што я » ве зменены з дапамогай выніку + = (! (0 - (((б & (1U << (зрух)))))) & (а << (зрух)));
дададзена аўтар Sir Jo Black, крыніца
Так, я ўсталяваў, што памылка! Таксама абнаўляюцца з альтэрнатывай, дзе кампілятар можа быць у стане выкарыстаць тэст бітнага і прапусціць каманду, каб пазбегнуць відавочных галін.
дададзена аўтар janm, крыніца
Паглядзіце, што робіць кампілятар - Я падазраю, што вы збіраецеся занадта далёка Пазбегнуць C , калі заяву пры ўмове, што ператворыцца ў філіял. Гэта вельмі моцна залежыць ад таго, наколькі добра ваш кампілятар. Гледзячы на ​​набор інструкцый рэч, каб пазбегнуць, верагодна, а << зрух і замест зруху а па адным на кожным кроку. Глядзіце мой асэмблер для таго, як я думаю, ён павінен у канчатковым выніку глядзець. Я б, як кампілятар можа выпраменьваць, што асэмблер для другой версіі UMULT16_STEP макра я дадаў у маім рэдагавання.
дададзена аўтар janm, крыніца
Дакладна - я думаю, C, які найбольш дакладна адлюстроўвае сход з'яўляецца другі варыянт майго макраса з (а) << 1 заяву. Усё ў тым, што макра-карты ў машынныя інструкцыі і можа быць зроблена без аддзялення. Пытанне заключаецца ў тым, ці стварае кампілятар галінку або генеруе Ці два sbrc інструкцыі, як у маім асэмблеры.
дададзена аўтар janm, крыніца
3 мікрасекунды @ 1/16 часу мксек цыкла дае 48 цыклаў. Для гэтага я магу бачыць, як вы можаце атрымаць 8x16 -> 16 біт. Я думаю, што лепшае, што вы можаце зрабіць, гэта 96 цыклаў для 16 х 16 -> 16 (выдаленне апошняга LSL r2; рол r3 , таму што яны не выкарыстоўваецца, але вам патрэбныя два аперацыя XOR ініцыялізацыя выніку. ) Множанне на канстанту б змяніць становішча рэчаў, таму што вы маглі б выдаліць гэтыя тэсты.
дададзена аўтар janm, крыніца
У якасці кампрамісу, вы можаце праверыць, ці маюць адзін з аперанд нулявога старэйшых байт. Калі так, то зрабіць гэта адзін аперанд для праверкі пабітава (для астатніх васьмі). (У адваротным выпадку прадукт будзе перапаўненне, так ці інакш.) +1 для падкрэслення пропуску.
дададзена аўтар greybeard, крыніца

A non-answer, tinyARM assembler (web doc) instead of C++ or C. I modified a pretty generic multiply-by-squares-lookup for speed (< 50 cycles excluding call&return overhead) at the cost of only fitting into AVRs with no less than 1KByte of RAM, using 512 aligned bytes for a table of the lower half of squares. At 20 MHz, that would nicely meet the 2 max 3 usec time limit still not showing up in the question proper - but Sergio Formiggini wanted 16 MHz. As of 2015/04, there is just one ATtiny from Atmel with that much RAM, and that is specified up to 8 MHz … (Rolling your "own" (e.g., from OpenCores) your FPGA probably has a bunch of fast multipliers (18×18 bits seems popular), if not processor cores.)
For a stab at fast shift-and-add, have a look at shift and add, factor shifting left, unrolled 16×16→16 and/or improve on it (wiki post). (You might well create that community wiki answer begged for in the question.)

.def    a0  = r16   ; factor low byte
.def    a1  = r17
#warning two warnings about preceding definitions of
#warning  r16 and r17 are due and may as well be ignored
.def    a   = r16   ; 8-bit factor
.def    b   = r17   ; 8-bit factor ; or r18, rather?
.def    b0  = r18   ; factor low byte
.def    b1  = r19
.def    p0  = r20   ; product low byte
.def    p1  = r21

; "squares table" SqTab shall be two 512 Byte tables of
;  squares of 9-bit natural numbers, divided by 4

; Idea: exploit p = a * b = Squares[a+b] - Squares[a-b]

init:
    ldi     r16, 0x73
    ldi     r17, 0xab
    ldi     r18, 23
    ldi     r19, 1
    ldi     r20, HIGH(SRAM_SIZE)
    cpi     r20, 2
    brsh    fillSqTable ; ATtiny 1634?
    rjmp    mpy16T16
fillSqTable:
    ldi     r20, SqTabH
    subi    r20, -2
    ldi     zh, SqTabH
    clr     zl
; generate sqares by adding up odd numbers starting at 1 += -1
    ldi     r22, 1
    clr     r23
    ser     r26
    ser     r27
fillLoop:
    add     r22, r26
    adc     r23, r27
    adiw    r26, 2
    mov     r21, r23
    lsr     r21         ; get bits 9:2
    mov     r21, r22
    ror     r21
    lsr     r21
    bst     r23, 1
    bld     r21, 7
    st      z+, r21
    cp      zh, r20
    brne    fillLoop
    rjmp    mpy16F16

; assembly lines are marked up with cycle count
;  and (latest) start cycle in block.
; If first line in code block, the (latest) block start cycle
;  follows; else if last line, the (max) block cycle total

;**************************************************************
;*
;* "mpy16F16" - 16x16->16 Bit Unsigned Multiplication
;*                        using table lookup
;* Sergio Formiggini special edition
;* Multiplies  two 16-bit register values a1:a0 and b1:b0.
;* The result is placed in p1:p0.
;*
;* Number of flash words: 318 + return = 
;*                       (40 + 256(flash table) + 22(RAM init))
;* Number of cycles     : 49 + return
;* Low  registers used  : None
;* High registers used  : 7+2 (a1:a0, b1:b0, p1:p0, sq;
;*                             + Z(r31:r30))
;* RAM bytes used       : 512 (squares table)
;*
;**************************************************************
mpy16F16:
    ldi     ZH, SqTabH>>1;1 0   0   squares table>>1
    mov     ZL, a0      ; 1 1
    add     ZL, b0      ; 1 2       a0+b0
    rol     ZH          ; 1 3       9 bit offset
    ld      p0, Z       ; 2 4       a0+b0l          1
    lpm     p1, Z       ; 3 6   9   a0+b0h          2

    ldi     ZH, SqTabH  ; 1 0   9   squares table

    mov     ZL, a1      ; 1 0   10
    sub     ZL, b0      ; 1 1       a1-b0
    brcc    noNegF10    ; 1 2
    neg     ZL          ; 1 3
noNegF10:
    ld      sq, Z       ; 2 4       a1-b0l          3
    sub     p1, sq      ; 1 6   7

    mov     ZL, a0      ; 1 0   17
    sub     ZL, b1      ; 1 1       a0-b1
    brcc    noNegF01    ; 1 2
    neg     ZL          ; 1 3
noNegF01:
    ld      sq, Z       ; 2 4       a0-b1l          4
    sub     p1, sq      ; 1 6   7

    mov     ZL, a0      ; 1 0   24
    sub     ZL, b0      ; 1 1       a0-b0
    brcc    noNegF00    ; 1 2
    neg     ZL          ; 1 3
noNegF00:
    ld      sq, Z       ; 2 4       a0-b0l          5
    sub     p0, sq      ; 1 6
    lpm     sq, Z       ; 3 7       a0-b0h          6*
    sbc     p1, sq      ; 1 10  11

    ldi     ZH, SqTabH>>1;1 0   35
    mov     ZL, a1      ; 1 1
    add     ZL, b0      ; 1 2       a1+b0
    rol     ZH          ; 1 3
    ld      sq, Z       ; 2 4       a1+b0l          7
    add     p1, sq      ; 1 6   7

    ldi     ZH, SqTabH>>1;1 0   42
    mov     ZL, a0      ; 1 1
    add     ZL, b1      ; 1 2       a0+b1
    rol     ZH          ; 1 3
    ld      sq, Z       ; 2 4       a0+b1l          8
    add     p1, sq      ; 1 6   7

    ret                 ;       49

.CSEG
.org 256; words?!
SqTableH:
.db   0,   0,   0,   0,   0,   0,   0,   0,   0,   0
.db   0,   0,   0,   0,   0,   0,   0,   0,   0,   0
.db   0,   0,   0,   0,   0,   0,   0,   0,   0,   0
.db   0,   0,   1,   1,   1,   1,   1,   1,   1,   1
.db   1,   1,   1,   1,   1,   1,   2,   2,   2,   2
.db   2,   2,   2,   2,   2,   2,   3,   3,   3,   3
.db   3,   3,   3,   3,   4,   4,   4,   4,   4,   4
.db   4,   4,   5,   5,   5,   5,   5,   5,   5,   6
.db   6,   6,   6,   6,   6,   7,   7,   7,   7,   7
.db   7,   8,   8,   8,   8,   8,   9,   9,   9,   9
.db   9,   9,  10,  10,  10,  10,  10,  11,  11,  11
.db  11,  12,  12,  12,  12,  12,  13,  13,  13,  13
.db  14,  14,  14,  14,  15,  15,  15,  15,  16,  16
.db  16,  16,  17,  17,  17,  17,  18,  18,  18,  18
.db  19,  19,  19,  19,  20,  20,  20,  21,  21,  21
.db  21,  22,  22,  22,  23,  23,  23,  24,  24,  24
.db  25,  25,  25,  25,  26,  26,  26,  27,  27,  27
.db  28,  28,  28,  29,  29,  29,  30,  30,  30,  31
.db  31,  31,  32,  32,  33,  33,  33,  34,  34,  34
.db  35,  35,  36,  36,  36,  37,  37,  37,  38,  38
.db  39,  39,  39,  40,  40,  41,  41,  41,  42,  42
.db  43,  43,  43,  44,  44,  45,  45,  45,  46,  46
.db  47,  47,  48,  48,  49,  49,  49,  50,  50,  51
.db  51,  52,  52,  53,  53,  53,  54,  54,  55,  55
.db  56,  56,  57,  57,  58,  58,  59,  59,  60,  60
.db  61,  61,  62,  62,  63,  63,  64,  64,  65,  65
.db  66,  66,  67,  67,  68,  68,  69,  69,  70,  70
.db  71,  71,  72,  72,  73,  73,  74,  74,  75,  76
.db  76,  77,  77,  78,  78,  79,  79,  80,  81,  81
.db  82,  82,  83,  83,  84,  84,  85,  86,  86,  87
.db  87,  88,  89,  89,  90,  90,  91,  92,  92,  93
.db  93,  94,  95,  95,  96,  96,  97,  98,  98,  99
.db 100, 100, 101, 101, 102, 103, 103, 104, 105, 105
.db 106, 106, 107, 108, 108, 109, 110, 110, 111, 112
.db 112, 113, 114, 114, 115, 116, 116, 117, 118, 118
.db 119, 120, 121, 121, 122, 123, 123, 124, 125, 125
.db 126, 127, 127, 128, 129, 130, 130, 131, 132, 132
.db 133, 134, 135, 135, 136, 137, 138, 138, 139, 140
.db 141, 141, 142, 143, 144, 144, 145, 146, 147, 147
.db 148, 149, 150, 150, 151, 152, 153, 153, 154, 155
.db 156, 157, 157, 158, 159, 160, 160, 161, 162, 163
.db 164, 164, 165, 166, 167, 168, 169, 169, 170, 171
.db 172, 173, 173, 174, 175, 176, 177, 178, 178, 179
.db 180, 181, 182, 183, 183, 184, 185, 186, 187, 188
.db 189, 189, 190, 191, 192, 193, 194, 195, 196, 196
.db 197, 198, 199, 200, 201, 202, 203, 203, 204, 205
.db 206, 207, 208, 209, 210, 211, 212, 212, 213, 214
.db 215, 216, 217, 218, 219, 220, 221, 222, 223, 224
.db 225, 225, 226, 227, 228, 229, 230, 231, 232, 233
.db 234, 235, 236, 237, 238, 239, 240, 241, 242, 243
.db 244, 245, 246, 247, 248, 249, 250, 251, 252, 253
.db 254, 255
; word addresses, again?!
.equ SqTabH = (high(SqTableH) << 1)

.DSEG
RAMTab .BYTE 512
1
дададзена

A non-answer, tinyARM assembler (web doc) instead of C++ or C. I modified a pretty generic multiply-by-squares-lookup for speed (< 50 cycles excluding call&return overhead) at the cost of only fitting into AVRs with no less than 1KByte of RAM, using 512 aligned bytes for a table of the lower half of squares. At 20 MHz, that would nicely meet the 2 max 3 usec time limit still not showing up in the question proper - but Sergio Formiggini wanted 16 MHz. As of 2015/04, there is just one ATtiny from Atmel with that much RAM, and that is specified up to 8 MHz … (Rolling your "own" (e.g., from OpenCores) your FPGA probably has a bunch of fast multipliers (18×18 bits seems popular), if not processor cores.)
For a stab at fast shift-and-add, have a look at shift and add, factor shifting left, unrolled 16×16→16 and/or improve on it (wiki post). (You might well create that community wiki answer begged for in the question.)

.def    a0  = r16   ; factor low byte
.def    a1  = r17
#warning two warnings about preceding definitions of
#warning  r16 and r17 are due and may as well be ignored
.def    a   = r16   ; 8-bit factor
.def    b   = r17   ; 8-bit factor ; or r18, rather?
.def    b0  = r18   ; factor low byte
.def    b1  = r19
.def    p0  = r20   ; product low byte
.def    p1  = r21

; "squares table" SqTab shall be two 512 Byte tables of
;  squares of 9-bit natural numbers, divided by 4

; Idea: exploit p = a * b = Squares[a+b] - Squares[a-b]

init:
    ldi     r16, 0x73
    ldi     r17, 0xab
    ldi     r18, 23
    ldi     r19, 1
    ldi     r20, HIGH(SRAM_SIZE)
    cpi     r20, 2
    brsh    fillSqTable ; ATtiny 1634?
    rjmp    mpy16T16
fillSqTable:
    ldi     r20, SqTabH
    subi    r20, -2
    ldi     zh, SqTabH
    clr     zl
; generate sqares by adding up odd numbers starting at 1 += -1
    ldi     r22, 1
    clr     r23
    ser     r26
    ser     r27
fillLoop:
    add     r22, r26
    adc     r23, r27
    adiw    r26, 2
    mov     r21, r23
    lsr     r21         ; get bits 9:2
    mov     r21, r22
    ror     r21
    lsr     r21
    bst     r23, 1
    bld     r21, 7
    st      z+, r21
    cp      zh, r20
    brne    fillLoop
    rjmp    mpy16F16

; assembly lines are marked up with cycle count
;  and (latest) start cycle in block.
; If first line in code block, the (latest) block start cycle
;  follows; else if last line, the (max) block cycle total

;**************************************************************
;*
;* "mpy16F16" - 16x16->16 Bit Unsigned Multiplication
;*                        using table lookup
;* Sergio Formiggini special edition
;* Multiplies  two 16-bit register values a1:a0 and b1:b0.
;* The result is placed in p1:p0.
;*
;* Number of flash words: 318 + return = 
;*                       (40 + 256(flash table) + 22(RAM init))
;* Number of cycles     : 49 + return
;* Low  registers used  : None
;* High registers used  : 7+2 (a1:a0, b1:b0, p1:p0, sq;
;*                             + Z(r31:r30))
;* RAM bytes used       : 512 (squares table)
;*
;**************************************************************
mpy16F16:
    ldi     ZH, SqTabH>>1;1 0   0   squares table>>1
    mov     ZL, a0      ; 1 1
    add     ZL, b0      ; 1 2       a0+b0
    rol     ZH          ; 1 3       9 bit offset
    ld      p0, Z       ; 2 4       a0+b0l          1
    lpm     p1, Z       ; 3 6   9   a0+b0h          2

    ldi     ZH, SqTabH  ; 1 0   9   squares table

    mov     ZL, a1      ; 1 0   10
    sub     ZL, b0      ; 1 1       a1-b0
    brcc    noNegF10    ; 1 2
    neg     ZL          ; 1 3
noNegF10:
    ld      sq, Z       ; 2 4       a1-b0l          3
    sub     p1, sq      ; 1 6   7

    mov     ZL, a0      ; 1 0   17
    sub     ZL, b1      ; 1 1       a0-b1
    brcc    noNegF01    ; 1 2
    neg     ZL          ; 1 3
noNegF01:
    ld      sq, Z       ; 2 4       a0-b1l          4
    sub     p1, sq      ; 1 6   7

    mov     ZL, a0      ; 1 0   24
    sub     ZL, b0      ; 1 1       a0-b0
    brcc    noNegF00    ; 1 2
    neg     ZL          ; 1 3
noNegF00:
    ld      sq, Z       ; 2 4       a0-b0l          5
    sub     p0, sq      ; 1 6
    lpm     sq, Z       ; 3 7       a0-b0h          6*
    sbc     p1, sq      ; 1 10  11

    ldi     ZH, SqTabH>>1;1 0   35
    mov     ZL, a1      ; 1 1
    add     ZL, b0      ; 1 2       a1+b0
    rol     ZH          ; 1 3
    ld      sq, Z       ; 2 4       a1+b0l          7
    add     p1, sq      ; 1 6   7

    ldi     ZH, SqTabH>>1;1 0   42
    mov     ZL, a0      ; 1 1
    add     ZL, b1      ; 1 2       a0+b1
    rol     ZH          ; 1 3
    ld      sq, Z       ; 2 4       a0+b1l          8
    add     p1, sq      ; 1 6   7

    ret                 ;       49

.CSEG
.org 256; words?!
SqTableH:
.db   0,   0,   0,   0,   0,   0,   0,   0,   0,   0
.db   0,   0,   0,   0,   0,   0,   0,   0,   0,   0
.db   0,   0,   0,   0,   0,   0,   0,   0,   0,   0
.db   0,   0,   1,   1,   1,   1,   1,   1,   1,   1
.db   1,   1,   1,   1,   1,   1,   2,   2,   2,   2
.db   2,   2,   2,   2,   2,   2,   3,   3,   3,   3
.db   3,   3,   3,   3,   4,   4,   4,   4,   4,   4
.db   4,   4,   5,   5,   5,   5,   5,   5,   5,   6
.db   6,   6,   6,   6,   6,   7,   7,   7,   7,   7
.db   7,   8,   8,   8,   8,   8,   9,   9,   9,   9
.db   9,   9,  10,  10,  10,  10,  10,  11,  11,  11
.db  11,  12,  12,  12,  12,  12,  13,  13,  13,  13
.db  14,  14,  14,  14,  15,  15,  15,  15,  16,  16
.db  16,  16,  17,  17,  17,  17,  18,  18,  18,  18
.db  19,  19,  19,  19,  20,  20,  20,  21,  21,  21
.db  21,  22,  22,  22,  23,  23,  23,  24,  24,  24
.db  25,  25,  25,  25,  26,  26,  26,  27,  27,  27
.db  28,  28,  28,  29,  29,  29,  30,  30,  30,  31
.db  31,  31,  32,  32,  33,  33,  33,  34,  34,  34
.db  35,  35,  36,  36,  36,  37,  37,  37,  38,  38
.db  39,  39,  39,  40,  40,  41,  41,  41,  42,  42
.db  43,  43,  43,  44,  44,  45,  45,  45,  46,  46
.db  47,  47,  48,  48,  49,  49,  49,  50,  50,  51
.db  51,  52,  52,  53,  53,  53,  54,  54,  55,  55
.db  56,  56,  57,  57,  58,  58,  59,  59,  60,  60
.db  61,  61,  62,  62,  63,  63,  64,  64,  65,  65
.db  66,  66,  67,  67,  68,  68,  69,  69,  70,  70
.db  71,  71,  72,  72,  73,  73,  74,  74,  75,  76
.db  76,  77,  77,  78,  78,  79,  79,  80,  81,  81
.db  82,  82,  83,  83,  84,  84,  85,  86,  86,  87
.db  87,  88,  89,  89,  90,  90,  91,  92,  92,  93
.db  93,  94,  95,  95,  96,  96,  97,  98,  98,  99
.db 100, 100, 101, 101, 102, 103, 103, 104, 105, 105
.db 106, 106, 107, 108, 108, 109, 110, 110, 111, 112
.db 112, 113, 114, 114, 115, 116, 116, 117, 118, 118
.db 119, 120, 121, 121, 122, 123, 123, 124, 125, 125
.db 126, 127, 127, 128, 129, 130, 130, 131, 132, 132
.db 133, 134, 135, 135, 136, 137, 138, 138, 139, 140
.db 141, 141, 142, 143, 144, 144, 145, 146, 147, 147
.db 148, 149, 150, 150, 151, 152, 153, 153, 154, 155
.db 156, 157, 157, 158, 159, 160, 160, 161, 162, 163
.db 164, 164, 165, 166, 167, 168, 169, 169, 170, 171
.db 172, 173, 173, 174, 175, 176, 177, 178, 178, 179
.db 180, 181, 182, 183, 183, 184, 185, 186, 187, 188
.db 189, 189, 190, 191, 192, 193, 194, 195, 196, 196
.db 197, 198, 199, 200, 201, 202, 203, 203, 204, 205
.db 206, 207, 208, 209, 210, 211, 212, 212, 213, 214
.db 215, 216, 217, 218, 219, 220, 221, 222, 223, 224
.db 225, 225, 226, 227, 228, 229, 230, 231, 232, 233
.db 234, 235, 236, 237, 238, 239, 240, 241, 242, 243
.db 244, 245, 246, 247, 248, 249, 250, 251, 252, 253
.db 254, 255
; word addresses, again?!
.equ SqTabH = (high(SqTableH) << 1)

.DSEG
RAMTab .BYTE 512
1
дададзена

У рэшце рэшт, адказ, калі дзёрзкая адзін: я не мог (пакуль) атрымаць AVR-C-кампілятар ад GCC ўпісаць яго ў 8K код. (Для асэмблера выканання, см AVR множання: няма забароненых прыёмаў )
. Падыход, што кожны, хто выкарыстаў прылада Даф спрабаваў для другой спробы:
выкарыстоўваць перамыкач. Выкарыстанне макрасаў, зыходны код выглядае цалкам бясшкодныя, калі масажаваць:

#define low(mp)     case mp: p = a0 * (uint8_t)(mp) << 8; break
#define low4(mp)    low(mp); low(mp + 1); low(mp + 2); low(mp + 3)
#define low16(mp)   low4(mp); low4(mp + 4); low4(mp + 8); low4(mp + 12)
#define low64(mp)   low16(mp); low16(mp + 16); low16(mp + 32); low16(mp + 48)
#if preShift
# define CASE(mp)   case mp: return p + a * (mp)
#else
# define CASE(mp)   case mp: return (p0<<8) + a * (mp)
#endif
#define case4(mp)   CASE(mp); CASE(mp + 1); CASE(mp + 2); CASE(mp + 3)
#define case16(mp)  case4(mp); case4(mp + 4); case4(mp + 8); case4(mp + 12)
#define case64(mp)  case16(mp); case16(mp + 16); case16(mp + 32); case16(mp + 48)

extern "C" __attribute__ ((noinline))
 uint16_t mpy16NHB16(uint16_t a, uint16_t b)
{
    uint16_t p = 0;
    uint8_t b0 = (uint8_t)b, b1 = (uint8_t)(b>>8);
    uint8_t a0 = (uint8_t)a, p0;

    switch (b1) {
        case64(0);
        case64(64);
        case64(128);
        case64(192);
    }
#if preShift
    p = p0 << 8;
#endif
#if preliminaries
    if (0 == b0) {
        p = -a;
        if (b & 0x8000)
            p += a << 9;
        if (b & 0x4000)
            p += a << 8;
        return p;
    }
    while (b0 & 1) {
        a <<= 1;
        b0 >>= 1;
    }
#endif
    switch (b0) {
        low64(0);
        low64(64);
        low64(128);
        low64(192);
    }
    return ~0;
}
int main(int ac, char const *const av[])
{
    char buf[22];
    for (uint16_t a = 0 ; a < a+1 ; a++)
      for (uint16_t m = 0 ; m <= a ; m++)
        puts(itoa(//shift4(ac)+shift3MaskAdd((uint16_t)av[0], ac)
   //     +shift4Add(ac, (uint16_t)av[0])
   //          + mpy16NHB16(ac, (ac + 105))
                 mpy16NHB16(a, m), buf, 10));
}
0
дададзена

У рэшце рэшт, адказ, калі дзёрзкая адзін: я не мог (пакуль) атрымаць AVR-C-кампілятар ад GCC ўпісаць яго ў 8K код. (Для асэмблера выканання, см AVR множання: няма забароненых прыёмаў )
. Падыход, што кожны, хто выкарыстаў прылада Даф спрабаваў для другой спробы:
выкарыстоўваць перамыкач. Выкарыстанне макрасаў, зыходны код выглядае цалкам бясшкодныя, калі масажаваць:

#define low(mp)     case mp: p = a0 * (uint8_t)(mp) << 8; break
#define low4(mp)    low(mp); low(mp + 1); low(mp + 2); low(mp + 3)
#define low16(mp)   low4(mp); low4(mp + 4); low4(mp + 8); low4(mp + 12)
#define low64(mp)   low16(mp); low16(mp + 16); low16(mp + 32); low16(mp + 48)
#if preShift
# define CASE(mp)   case mp: return p + a * (mp)
#else
# define CASE(mp)   case mp: return (p0<<8) + a * (mp)
#endif
#define case4(mp)   CASE(mp); CASE(mp + 1); CASE(mp + 2); CASE(mp + 3)
#define case16(mp)  case4(mp); case4(mp + 4); case4(mp + 8); case4(mp + 12)
#define case64(mp)  case16(mp); case16(mp + 16); case16(mp + 32); case16(mp + 48)

extern "C" __attribute__ ((noinline))
 uint16_t mpy16NHB16(uint16_t a, uint16_t b)
{
    uint16_t p = 0;
    uint8_t b0 = (uint8_t)b, b1 = (uint8_t)(b>>8);
    uint8_t a0 = (uint8_t)a, p0;

    switch (b1) {
        case64(0);
        case64(64);
        case64(128);
        case64(192);
    }
#if preShift
    p = p0 << 8;
#endif
#if preliminaries
    if (0 == b0) {
        p = -a;
        if (b & 0x8000)
            p += a << 9;
        if (b & 0x4000)
            p += a << 8;
        return p;
    }
    while (b0 & 1) {
        a <<= 1;
        b0 >>= 1;
    }
#endif
    switch (b0) {
        low64(0);
        low64(64);
        low64(128);
        low64(192);
    }
    return ~0;
}
int main(int ac, char const *const av[])
{
    char buf[22];
    for (uint16_t a = 0 ; a < a+1 ; a++)
      for (uint16_t m = 0 ; m <= a ; m++)
        puts(itoa(//shift4(ac)+shift3MaskAdd((uint16_t)av[0], ac)
   //     +shift4Add(ac, (uint16_t)av[0])
   //          + mpy16NHB16(ac, (ac + 105))
                 mpy16NHB16(a, m), buf, 10));
}
0
дададзена