BC/NW 2008, №1 (12): 3.1

 

 

 

 

АЛГОРИТМ УВЕЛИЧЕНИЯ БЫСТРОДЕЙСТВИЯ АППАРАТНОГО УМНОЖИТЕЛЯ

 

С.В.Гусев, А.А.Алексеев

 

(Москва, Московский энергетический институт(технический университет), Россия)

 

 

 

 

 В настоящее время широкое распространения получили процессоры цифровой обработки сигналов, в которых используются встроенные блоки умножителей-накопителей.  Увеличение быстродействия этих блоков ведет к увеличению быстродействия всего процессора, т.к. блоки накопителей-умножителей требуют наибольшее время для выполнения команд адресованных им. Наибольшее распространение получили параллельные алгоритмы умножение, в частности алгоритм Уоллеса. 

Рассмотрим частный случай 16 битного модуля накопителя-умножителя. При умножении двух 16 разрядных чисел получим матрицу частных произведений, содержащую 16 строк. Так как количества шагов свертывание зависит от количества строк,  имеет смысл использовать алгоритм Бута, с помощью которого можно сократить количество строк вдвое. Т.е. для нашего случая получим 10 строк. В случае если мы строим блок умножителя-накопителя, а не простого умножителя так же имеет смысл рассматривать накопленную сумму как частное произведение. Т.е. добавить  к суммам частных произведений в качестве 11й строки. Далее при примени алгоритма Уоллеса получим, что для свертывания данного массива нам потребуется  7 шагов. Заметим что при использовании алгоритма Уоллеса количество строк в матрице на j-й ступени оценивается по следующей формуле: w0 = n; wj+1 = 2[wj3] + (wj mod 3); Т.е полусумматоры используются только если в столбце осталось 2 бита.

Следующий алгоритм позволяет сократить количество ступеней  за счет формирования переноса на

более ранних стадиях.  Суть алгоритма состоит в следующем:

1)При проектировании дерева рассчитать полное количество бит с учетом всех переносов на каждом столбце.

2)Далее, если общее количество бит на данном столбце получается четным, то полусумматоры для данного столбца использовать нельзя, так как это приведет к лишним битам переноса.  На тех столбцах где общее количество бит получилось нечетным можно использовать один полусумматор на любом шаге сжатия.

Разберем конкретный пример модуля шестнадцатиразрядного умножителя-накопителя. Преобразовав

множители по алгоритму Бута, получим два восьмибитных сомножителя. Составим матрицу частных произведений. Добавим накопленную ранее сумму в качестве одной из строк, расширив при этом знак каждой строки и начиная с первого столбца через один добавим соответствующий бит знакового вектора(полученного при преобразовании сомножителей по Буту).  Получаем следующую разрядность столбцов(по порядку, начиная с крайнего правого, т.е нулевого): {3, 2, 4, 3, 5, 4, 6, 5, 7, 6, 8, 7, 9, 8, 10, 9, 11 ,10} и далее все столбцы будут иметь разрядность 10.  Нулевой столбец не имеет переносов справа, следовательно, в нем может быть только три бита. В столбце 1 содержится два бита, так же на каком то этапе к нему добавиться перенос от первого столбца, т.е получим общее количество бит 1го столбца равно 3.

Рассчитаем  количество бит для каждого столбца по формуле: N = Nначальноеj + Nпереносj-1.

Получаем что общее (но не максимальное, т.к. возможны различные конфигурации сжатия) количество бит для каждого столбца будет следующим (начиная с нулевого): {3,3,5,5,7,7,9,9,11,11,13,13,15,15,17,17,19}. И далее до 31го общее количество бит на столбцах будет рано 19. Т.е пользуясь правилом приведенным в данном алгоритме получим, что на каждом столбце мы можем однократно, на любом шаге  использовать полусумматор. Таким образом, алгоритм позволяет сжать эту матрицу  до двух строк на четвертом шаге. В то время как с использованием алгоритма Уоллеса данная матрица сжимается за 5 шагов. В зависимости от библиотеки при аппаратной реализации это позволит сэкономить от 0.5 до 1 ns.