✦ LIBER ✦

An efficient algorithm for parallel integer multiplication

✍ Scribed by Benjamin Singer; George Saon

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 67 KB
Volume: 19
Category: Article
ISSN: 1084-8045
DOI: 10.1006/jnca.1996.0029

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we propose an efficient algorithm to implement parallel integer multiplication by a combination of parallel additions, shifts and reads from a memoryresident 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.

📜 SIMILAR VOLUMES

Parallel Algorithms for Counting and Ran

Parallel Algorithms for Counting and Randomly Generating Integer Partitions

✍ Laura A. Sanchis; Matthew B. Squire 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 228 KB

This paper presents parallel algorithms for determining the number of partitions of a given integer N, where the partitions may be subject to restrictions, such as being composed of distinct parts, of a given number of parts, and/or of parts belonging to a specified set. We present a series of adapt

Performance Analysis of the Parallel Kar

Performance Analysis of the Parallel Karatsuba Multiplication Algorithm for Distributed Memory Architectures

✍ GIOVANNI CESARI; ROMAN MAEDER 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 447 KB

We present three parallel implementations of the Karatsuba algorithm for long integer multiplication on a distributed memory architecture and discuss the experimental results obtained on a Paragon computer. The first two implementations have both time complexity O(n) on n log 2 3 processors, but pre

An Efficient Parallel Algorithm for Maxi

An Efficient Parallel Algorithm for Maximum Matching for Some Classes of Graphs

✍ I. Parfenoff 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 403 KB

The P 4 -tidy graphs were introduced by I. Rusu to generalize some already known classes of graphs with few induced P 4 (cographs, P 4 -sparse graphs, P 4 -lite graphs). Here, we propose an extension of R. Lin and S. Olariu's work (1994. J. Parallel Distributed Computing 22, 26 36.) on cographs, usi

An efficient parallel algorithm for the

An efficient parallel algorithm for the calculation of canonical MP2 energies

✍ Jon Baker; Peter Pulay 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 111 KB

## Abstract We present the parallel version of a previous serial algorithm for the efficient calculation of canonical MP2 energies (Pulay, P.; Saebo, S.; Wolinski, K. Chem Phys Lett 2001, 344, 543). It is based on the Saebo–Almlöf direct‐integral transformation, coupled with an efficient prescreeni

An algorithm for concave integer minimiz

An algorithm for concave integer minimization over a polyhedron

✍ Harold P. Benson; S. Selcuk Erenguc 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 753 KB

We present an algorithm for solving the problem of globally minimizing a concave function over the integers contained in a compact polyhedron. The objective function of this problem need not be separable or even analytically defined. To our knowledge, the algorithm is the first ever proposed for thi

An Efficient Algorithm and Parallel Impl

An Efficient Algorithm and Parallel Implementations for Binary and Residue Number Systems

✍ C.N. Zhang; B. Shirazi; D.Y.Y. Yun 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 331 KB

Arithmetic units based on a Residue Number System (RNS) are fast and simple, and therefore attractive for use in digital signal processing and symbolic computation applications. However, RNS suffers from overheads of converting numbers to and from residue system. We present a new simple and uniform