3.2.5 Алгоритми за ускоряване на операция умножение

Algorithms for accelerating multiplication operation

От казаното до момента става ясно, че продължителността на операция умножение е значително по-голяма в сравнение с тази на операция събиране, ето защо съвсем естествено възниква необходимостта от разработване на алгоритми за ускоряването й. Алгоритмите за ускоряване на операция умножение се основават преди всичко на конкретни ситуации, създавани от цифрите на множителя, чиято логика предлага най-често възможността да се пропусне микрооперация събиране или да се направи изместване на повече от един разряд за такт. Тъй като тези алгоритми са разработени преди всичко чрез системен логически анализ на операция умножение, те са обединени и известни като логически алгоритми за ускоряване. Най-важната характеристика при последователната реализация на логическите алгоритми за ускоряване на операция умножение е тази, че те не гарантират предварително степента на ускоряване. Ускоряването, което следва да се разбира като икономисано време от спестени (прескочени) тактове по отношение на времетраенето на операцията, изпълнена по класическите алгоритми, е конкретно за всяка отделна операция, тъй като се отнася за конкретното съчетание на операндите. Това означава най-често, че времетраенето на операция умножение при логическите алгоритми за ускоряване е по-малко или поне равно на това при класическите алгоритми, т.е. ускорението не е абсолютна величина и то може да се оцени само в статистически смисъл, например ускорение при изпълнение на 1000 умножения. Вероятността измежду операндите на тези 1000 умножения да се срещнат такива, които ще реализират икономия на време, е много голяма и тя очевидно нараства с увеличение на този брой (или още на разглеждания времеви интервал).

Друга група алгоритми е свързана с реализация на поразрядните произведения при вземане от множителя на няколко разряда едновременно. Разглеждането на група разряди едновременно (от 2, от 3 или от 4 бита) може да се интерпретира като умножение в друга бройна система, различна от двоичната. Така например особено разпространен е алгоритъмът за умножение с 4 разряда едновременно, който, както е показано в пункт 1.1.2, може да се интерпретира като умножение в 16-ична бройна система. Не е трудно да се съобрази, че умножавайки с няколко разряда едновременно, операцията ще завърши по-бързо. Намаляването на времетраенето на операцията се дължи на намаления общ брой тактове, а те са толкова пъти по-малко, колкото е броят на едновременно взетите от множителя разряди. При умножение например с 2 разряда едновременно може да твърдим, че ускоряването на операцията е двукратно, тъй като разрядите на множителя се изчерпват за 2 пъти по-малко тактове. Такова ускорение определяме като абсолютно и предварително гарантирано, за разлика от характера на ускорението в алгоритмите, споменати по-горе.

Към настоящия момент съвременните технологични възможности са такива, че развитието на алгоритмите за умножение продължава върху тяхната апаратна реализация – към така наречените схемни (матрични) умножители. В схемните умножители изпълнението на операцията се постига в специализирана комбинационна схема. Това изпълнение може да се определи като еднотактно.

В крайна сметка алгоритмите, които довеждат до гарантирано (абсолютно) намаление на времетраенето на операция умножение, независимо от конкретността на съмножителите, се наричат апаратни алгоритми за ускоряване.

Без да имаме за задачата да изчерпим множеството от известни логически или апаратни алгоритми за ускоряване на операция умножение, тук ще бъдат разгледани едни от най-широко разпространените и от двете групи. По-задълбочени познания по тези проблеми читателят може да почерпи от специализираната и от научната литература, където освен изложените в тази книга принципи, подходи и алгоритми се разглеждат и други такива.

Следващият раздел е:

3.2.5.1 Алгоритъм на Бут (Booth) ( Algorithm of Booth )