From dseal@armltd.co.uk (David Seal) Fri Jan 21 09:19:21 1994 Path: doc.ic.ac.uk!warwick!zaphod.crihan.fr!jussieu.fr!univ-lyon1.fr!swidir.switch.ch!scsing.switch.ch!news.dfn.de!news.dfn.de!zib-berlin.de!zrz.TU-Berlin.DE!netmbx.de!Germany.EU.net!EU.net!howland.reston.ans.net!pipex!uknet!armltd!dseal From: dseal@armltd.co.uk (David Seal) Newsgroups: comp.sys.acorn.tech Subject: Multiply cycle counts (was Re: Constant Loading) Message-ID: <31468@armltd.uucp> Date: 20 Jan 94 14:40:43 GMT References: Sender: dseal@armltd.uucp Distribution: comp Organization: A.R.M. Ltd, Swaffham Bulbeck, Cambs, UK Lines: 65 In article mikee@dd.eng.bbc.co.uk (Mike.Ellis) writes: >Oliver Betts (olly@mantis.co.uk) wrote: >> The MUL instruction doesn't have a fixed execution time. > >According to the ARM/VLSI data sheet, the MUL and MLA instructions >are implemented using 2-bit Booth's alogrithm with early termination >and take the form :- > >MUL rd, rm, rs >MLA rd, rm, rs, rn > >Note that rd == rm is not permitted - MUL sets rd = 0, MLA set rd = anything > rd == r15 ( == pc) is not permitted > >Cycle-by-cycle analysis yields > >Cycle Action >1 rd is initialized. >2-n multiplying using 2-bit Booth's algorithm. > >n will vary between 2 and 16 depending on the multiplication to be >performed. In fact, n will vary between 2 and 17 (the instruction can take up to 1S + 16I cycles, for a total of 17 cycles) according to the value of Rs. To find out how many, look at the number of zeros at the left hand end of the value of Rs, according to the following table: Number of zeros at left Termination cycle end of Rs value (n in the above) --------------------------------------------- 0-2 17 3-4 16 5-6 15 7-8 14 9-10 13 11-12 12 13-14 11 15-16 10 17-18 9 19-20 8 21-22 7 23-24 6 25-26 5 27-28 4 29-30 3 31-32 2 So multiplication by 0 (with 32 leading zeros) or 1 (with 31 leading zeros) takes 2 cycles, multiplication by 2-7 (with 30 or 29 leading zeros) takes 3 cycles, multiplication by 8-31 takes 4 cycles, etc. Note though that there is an irregularity when you get to numbers with no leading zeros (i.e. with the top bit set): the natural progression in the above table would suggest that they would take 18 cycles, but they in fact take 17. Note also that this information applies to current ARM implementations. Future implementations may have completely different rules about the number of cycles taken by a multiply instruction. David Seal dseal@armltd.co.uk All opinions are mine only... From ee@datcon.co.uk (Eddie Edwards) Fri Jan 21 09:19:48 1994 Newsgroups: comp.sys.acorn.tech Path: doc.ic.ac.uk!mrccrc!news.dcs.warwick.ac.uk!warwick!zaphod.crihan.fr!jussieu.fr!univ-lyon1.fr!swidir.switch.ch!scsing.switch.ch!xlink.net!howland.reston.ans.net!pipex!datcon!ee From: ee@datcon.co.uk (Eddie Edwards) Subject: Re: Multiply cycle counts (was Re: Constant Loading) Message-ID: <1994Jan20.175030.3259@datcon.co.uk> Organization: Data Connection Limited X-Newsreader: TIN [version 1.2 PL0] References: <31468@armltd.uucp> Distribution: comp Date: Thu, 20 Jan 1994 17:50:30 GMT Lines: 24 David Seal (dseal@armltd.co.uk) wrote: : > : >MUL rd, rm, rs : >MLA rd, rm, rs, rn : > : So multiplication by 0 (with 32 leading zeros) or 1 (with 31 leading zeros) : takes 2 cycles, multiplication by 2-7 (with 30 or 29 leading zeros) takes 3 : cycles, multiplication by 8-31 takes 4 cycles, etc. Note though that there : is an irregularity when you get to numbers with no leading zeros (i.e. with : the top bit set): the natural progression in the above table would suggest : that they would take 18 cycles, but they in fact take 17. In fact, I think it worth pointing out that it is _rs_ which determines the speed. Therefore, you can get your code to run faster if you put the (likely) smaller operand in rs rather than rm. Eddie xxx ================================================================================ "In our song we have our banner : This .sig is brought to you with the help And the colours always shine." : of the letters D and C and the number 69. - The Green Inspiration Band :============================================== =================================: ee@datcon.co.uk - Eddie Edwards