2024年4月21日发(作者：永久免费qq机器人手机版)

ICCD’96,InternationalConferenceonComputerDesign,October7–9,1996,Austin,Texas,USA

,

example,wecanusetheNewtonmethodon

toderivetheiterationequation

,where

isanapproximatevalueof

canbe

eginning,aseedobtainedbymultiplying

()isgeneratedbyhardwarecircuitry,aROMtablefor

iteration,multiplicationsandadditionsor

subtractionsareneeded.

Inordertospeedupthemultiplication,itisusualtouse

afastparallelmultipliertogetapartialproductionandthen

ethemultiplier

requiresaratherlargenumberofgatecounts,itisimpracti-

caltoplaceasmanymultipliersasrequiredtorealizefully

pipelinedoperationfordivision(div)andsquareroot(sqrt)

esignofmostcommercialRISCpro-

cessors,amultiplierisusedforalliterationsofdivorsqrt

ansthattheprocessorsarenotcapable

ofacceptinganewdivorsqrtinstructionforeachclock

cycle.

However,manyapplicationsrequireafastpipelined

purposeoffastvectornormal-

ization,lpresentedadesigntechniqueforpipelined

operationthatusessubtractorsandmultiplexors[2].

Inthispaper,wedescribeanewnon-restoringsquareroot

algorithmthatrequiresneithermultipliersnormultiplexors.

Comparedwithpreviousnon-restoringalgorithms,oural-

gorithmisveryeffi-

eratesthecorrectresultingvalueateachiterationanddoes

operationateachiterationissimple:additionorsubtraction

remainderoftheadditionorsubtractionisfedviaregisters

ast

iteration,iftheremainderisnon-negative,itisaprecisere-

ise,wecanobtainapreciseremainderby

anadditionoperation.

Thisalgorithmhasbeenimplementedinamultithreaded

processordesignwhichhasbeendevelopedatUniversity

ofAizuusingToshibaTC180C/E/TC183C/EGateArray

Library[7].Wealsoimplementedandverifiedthealgorithm

lementationsaresimple

andmorearea-timeefficientthanmanyexistingdesigns.

n2describes

n3

-

tion4and5introducetwoVLSIimplementationsforthe

538

fullypipelinedimplementationand

lowingsec-

tioninvestigatestheperformanceandcostcomparedwith

finalsectionpresents

conclusions.

D = 01,11,11,11

Q = 1000

D - Q x Q

+ 0100

Q = 1100

D - Q x Q

- 0010

Q = 1010D - Q x Q

+ 0001

Q = 1011D - Q x Q

=

00,11,11,11is nonnegtive

=

11,10,11,11is negtive

=

00,01,10,11is nonnegtive

=

00,00,01,10

usNon-RestoringSquareRootAlgo-

rithm

Assumethatanoperandisdenotedbya32-bitunsigned

number:.Thevalueofthe

operandis

.Foreverypairofbitsoftheoperand,the

integerpartofsquareroothasonebit(seeFig.1).Thusthe

integerpartofsquarerootfora32-bitoperandhas16bits:

.

pleofpreviousnon-

restoringsquarerootalgorithm

Non-RestoringSquareRootAlgo-

rithm

Thefocusofthepreviousrestoringandnon-restoringal-

gorithmsisoneachbitofthesquarerootwitheachiteration.

Inthissection,wedescribeanewnon-restoringsquareroot

usofthenewalgorithmisonthepar-

orithmgenerates

acorrectresultingbitineachiterationincludingthelast

rationduringeachiterationisverysim-

ple:additionorsubtractionbasedonthesignoftheresult

tialremaindergeneratedin

eachiterationisusedinthenextiterationevenitisnegative

(thisiswhatnon-restoringmeansinournewalgorithm).At

thefinaliteration,ifthepartialremainderisnotnegative,

itbecomesthefiise,wecan

getthefinalpreciseremainderbyanadditiontothepartial

remainder.

Thefollowingisthenewnon-restoringsquarerootalgo-

rithmwrittenintheClanguage.

OPERAND

SQUARE

ROOT

D

31

D

30

D

29

D

28

D

27

D

26

Q

15

Q

14

Q

13

...

...

D

1

Q

0

D

0

ofoperandandsquareroot

andtheniteratefromto

Atfirst,wereset

,andsubtract

iteration,weset

esultisnegative,thensettingmadetoo

big,sowereset

.Thisalgorithmmodifieseachbit

of

calledarestoringsquarerootalgorithm.

Animplementationexamplecanbefoundin[5].

Anon-restoringsquarerootalgorithmmodifieseachbit

nswithaninitialguess

of

(partialroot)and

iteration,istheniteratesfrom

subtractedbythesquaredpartialroot:.Based

onthesignoftheresult,thealgorithmaddsorsubtractsa1

8-bitexampleofthealgorithmisshown

in

entationexamplescanbefoundin[3]and

[4].

Wecanseethatthealgorithmhasfollowingdisad-

,itrequiresanaddition/subtraction(in-

crease/decrease)-

ond,thealgorithmmayproduceanerrorinthelastbitposi-

,itrequiresanoperationof

iterationwiththeresultnotbeingusedforthenextiteration.

canbereplacedbyAlthoughthemultiplicationof

substitutevariable,thecircuitryrequiredisstillcomplex.

539