An efficient algorithm for parallel integer multiplication

Benjamin Singer 1 George Saon 2
2 READ - READ
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

https://hal.inria.fr/inria-00545095
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

Identifiants

Collections

Partager

Métriques

Consultations de la notice

124