Back to search

NJIT

Fast arithmetic operations on the hypercube using conditional sum addition and modified booth's algorithm

Abstract

dc:description.abstract

<p>Algorithms for fast arithmetic operations (i.e., addition and multiplication) on the hypercube computer are presented. The hypercube network of dimension d interconnects N = 2<sup>d</sup> processors in such a way that each processor is directly connected to d neighboring processors; m order to communicate between processors, the maximum length of the path is d. The addition algorithm is based on the conditional sum technique. The computational time using this algorithm is O(log<sub>2</sub> N+q) where q is the number of the bits per processor in the hypercube of N processors. Operands of size N*q are distributed among the hypercube processors using high-order interleaving Only two hits ate exchanged in every cycle of communication for a total of log<sub>2</sub> N communication cycles. A modified version of Booth's algorithm is adopted for fast multiplication and generates Fn/2 I partial products, where the size of the multiplier is 11 bits. These 1?n/21 partial products are half of those required by conventional multiplication. Each processor of the hypercube generates I?n/2N1 partial products, simultaneously. These partial products are distributed among the N processors using high-order interleaving. Each processor contains I (n+ni )/N I bits, where n and in are the numbers of bits in the multiplier and the multiplicand respectively. A carry-save addition (CSA) technique is used to add these multiple partial product. These multiple partial products are reduced to two operands (i.e., carry and sum) in (1n/21 - 2) iterations, which are finally added using the algorithm described earlier. The time taken by the multiplication process is O(log2 N(nq+1) + n(q+1 +1 IN) - q). These algorithm are .imulated and comparative analysis is performed for various sizes of operands and hypercube,, of various dimensions.</p>

Degree

thesis:*
Name thesis:degree_name
Master of Science in Electrical Engineering - (M.S.)
Discipline thesis:degree_discipline
Electrical and Computer Engineering

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Iftikhar, Umar Bin
Contributors dc:contributor
  • Sotirios Ziavras
  • John D. Carpinelli
  • Yun Q. Shi

Subjects

dc:subject × 4

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.njit.edu/theses/2504

Chain of custody

source
Harvested from
NJIT
Base URL
digitalcommons.njit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Iftikhar, Umar Bin. Fast arithmetic operations on the hypercube using conditional sum addition and modified booth's algorithm. https://digitalcommons.njit.edu/theses/2504