NDLI: Optimal circuits for parallel multipliers

Content Provider	IEEE Xplore Digital Library
Author	Stelling, P.F. Martel, C.U. Oklobdzija, V.G. Ravi, R.
Copyright Year	1968
Abstract	We present new design and analysis techniques for the synthesis of parallel multiplier circuits that have smaller predicted delay than the best current multipliers. V.G. Oklobdzija et al. (1996) suggested a new approach, the Three-Dimensional Method (TDM), for Partial Product Reduction Tree (PPRT) design that produces multipliers that outperform the current best designs. The goal of TDM is to produce a minimum delay PPRT using full adders. This is done by carefully modeling the relationship of the output delays to the input delays in an adder and, then, interconnecting the adders in a globally optimal way. Oklobdzija et al. suggested a good heuristic for finding the optimal PPRT, but no proofs about the performance of this heuristic were given. We provide a formal characterization of optimal PPRT circuits and prove a number of properties about them. For the problem of summing a set of input bits within the minimum delay, we present an algorithm that produces a minimum delay circuit in time linear in the size of the inputs. Our techniques allow us to prove tight lower bounds on multiplier circuit delays. These results are combined to create a program that finds optimal TDM multiplier designs. Using this program, we can show that, while the heuristic used by Oklobdzija et al. does not always find the optimal TDM circuit, it performs very well in terms of overall PPRT circuit delay. However, our search algorithms find better PPRT circuits for reducing the delay of the entire multiplier.
Sponsorship	IEEE Computer Society Technical Committee on Distributed Process IEEE Computer Society Technical Committee on VLSI IEEE Technical Committee on Computer Architecture IEEE Computer Society
Starting Page	273
Ending Page	285
Page Count	13
File Size	575312
File Format	PDF
ISSN	00189340
Volume Number	47
Issue Number	3
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1998-03-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Adders Time division multiplexing Integrated circuit interconnections Signal processing algorithms Algorithm design and analysis Compressors Circuit synthesis Delay effects Product design Added delay
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Software Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Design strategies for optimal multiplier circuits

Technology scaling effects on multipliers

High-speed Booth encoded parallel multiplier design

An efficient synthesizer for generation of fast parallel multipliers

Tight integration of timing-driven synthesis and placement of parallel multiplier circuits

Area-time optimal adder design

Analysis and design of CMOS Manchester adders with variable carry-skip

Fast parallel algorithm for ternary multiplication using multivalued I/sup 2/L technology

A universal architecture for designing efficient modulo 2/sup n/+1 multipliers

Optimal circuits for parallel multipliers

Similar Documents

Design strategies for optimal multiplier circuits

Technology scaling effects on multipliers

High-speed Booth encoded parallel multiplier design

An efficient synthesizer for generation of fast parallel multipliers

Tight integration of timing-driven synthesis and placement of parallel multiplier circuits

Area-time optimal adder design

Analysis and design of CMOS Manchester adders with variable carry-skip

Fast parallel algorithm for ternary multiplication using multivalued I/sup 2/L technology

A universal architecture for designing efficient modulo 2/sup n/+1 multipliers

Optimal circuits for parallel multipliers