An efficient algorithm for parallel integer multiplication

Benjamin Singer 1 George Saon 2
LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper we propose an efficient algorithm to implement parallel integer multiplication by a combination of parallel additions, shifts and reads from a memory-resident lookup table dedicated to squares. Such an operator called PIM (parallel integer multiplication) is in fact microprogrammed at the PROM level. Our theoretical approach is included within the framework of time and space parallel complexity theory. The mathematical relation used defines this multiplication operator in terms of a difference of two quadratic expressions, each being computed in parallel by one addition and one shift. This leads to the CPU time for any pair of numbers being constant. Our contribution is above all of practical interest on any massively parallel architecture in the field of scientific and numerical computing.
Liste complète des métadonnées
Contributeur : Yolande Belaid <>
Soumis le : jeudi 9 décembre 2010 - 15:48:43
Dernière modification le : mardi 24 avril 2018 - 13:55:24

Lien texte intégral





Consultations de la notice