Организация ЭВМ и систем. Однопроцессорные ЭВМ. Часть 1

       

Методы ускорения умножения


Рассмотренный в предыдущей теме материал показывает, что умножение – это достаточно длинная операция, состоящая из N суммирований и сдвигов, а также выделений очередных цифр множителя.

Из этого следует актуальность задачи максимального сокращения времени, затрачиваемого на операцию умножения, особенно для систем, работающих в реальном масштабе времени. В современных ЭВМ методы ускорения умножения можно разделить:

  • на аппаратные;
  • логические (алгоритмические);
  • комбинированные.
  • Аппаратные методы

    1. Распараллеливание вычислительных операций. Например, совмещение во времени суммирования и сдвига.

    2. Табличное умножение. Это довольно распространенный способ реализации различных функций. Остановимся на нем подробнее.

    Пусть X и Y – целые числа длиной в 1 байт. Надо вычислить Z=X*Y. Можно использовать 65 Кбайт памяти и занести в них значения Z для всех возможных комбинаций X и Y, а сомножители X и Y использовать в качестве адреса. Получается своеобразная таблица следующего вида:

    Алгоритмические методы

    Эти методы разнообразны. Приведем только один пример: при S=16 можно за один такт обрабатывать несколько разрядов множителя (4 разряда). Сдвиги тоже осуществляются на 4 разряда. Следует отметить, однако, что в большинстве случаев алгоритмические методы требуют определенную аппаратную поддержку.

    Комбинированные методы

    Рассмотрим пример. Пусть X и Y – 16-разрядные числа. Надо вычислить произведение вида Z=X*Y. Использовать непосредственно табличный метод не удастся, поскольку для этих целей потребуется очень большой объем памяти. Однако можно представить каждый сомножитель как сумму двух 16-разрядных слагаемых, каждое из которых представляет группы старших и младших разрядов сомножителей. В этом случае произведение примет вид

    Z  = X*Y = (x15 ... x0)*(y15 ... y0) =

        = (x15...x8000...0 + 000...0x7...x0)* (y15...y8000...0 + 000...0y7...y0) =

        = 216(x15...x8) (y15...y8) + 28(x15...x8) (y7...y0) + 28(x7...x0) (y15...y8) +

        + (x7...x0)*(y7...y0) .

    Таким образом, произведение раскладывается на простые 8-разрядные сомножители. Эти произведения 8-разрядных операндов вычисляются табличным методом, а затем следует сдвиг слагаемых сразу на 16,8,8,0 разрядов и суммирование.



    Содержание раздела