arm "neon"

[Niels Möller]

nisse at lysator.liu.se (Niels Möller) writes:

> With neon, if we put
>
>   d0: v0, v1
>   d1: u0, u0
>   d2: c0, c1
>   d3: c0', r1
>
> we could do
>
>   vmull.u32	q3, d0, d1	; Form products
>   vaddl.u32	q4, d2, d3	; Add and extend carry inputs
>   vadd.i64	q1, q3, q4

I've implemented a neon addmul_2, see below.

Unfortunately, it's not very fast. My first working version took almost
10 cycles per limb product. One iteration through the loop is 9
instructions, and it takes 19 cycles, so there's definitely something
slowing execution down. Then I moved the multiplications earlier, which
got us down to 7 cycles per limb product (14 cycles per iteration through
the loop).

And I don't really know how far it can be sped up, but there is
definitely some potential for software pipelining (the multiplies can be
moved even further in advance), and with some unrolling we could do
loads and stores of two (or more) limbs at a time. The recurrency seems
to be a chain

  vaddl, vadd, vshr, vld1

which with some tricks could be turned into

  vaddl, vadd, vext

What latency can one expect? If we have only a single cycle latency for
each those operations, performance will be limited by instruction
decoding. One could hope to get down to two cycles / limb product, but
it looks quite difficult.

Maybe it would be interesting to try the code also on cortex-a15?

Ah, and one interface question: What's the smallest n which mpn_addmul_2
must support?

Regards,
/Niels

dnl  ARM neon mpn_addmul_2.

dnl  Contributed to the GNU project by Niels Möller

dnl  Copyright 2013 Free Software Foundation, Inc.

dnl  This file is part of the GNU MP Library.

dnl  The GNU MP Library is free software; you can redistribute it and/or modify
dnl  it under the terms of the GNU Lesser General Public License as published
dnl  by the Free Software Foundation; either version 3 of the License, or (at
dnl  your option) any later version.

dnl  The GNU MP Library is distributed in the hope that it will be useful, but
dnl  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
dnl  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
dnl  License for more details.

dnl  You should have received a copy of the GNU Lesser General Public License
dnl  along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.

include(`../config.m4')

	.cpu	cortex-a9
	.fpu	neon
	.arm
	.arch	armv7-a

C	     cycles/limb
	
define(`rp',`r0')
define(`up',`r1')
define(`n', `r2')
define(`vp',`r3')

define(`v01', `d0')
define(`u00', `d1')
define(`l01', `d2')
define(`c01', `d3')

C
C	      c1 c0
C	      r1 c0'
C	      u0*v0
C	   u0*v1
C	------------
C	   c1 c0 r0
C	      c0'
	
ASM_START()
PROLOGUE(mpn_addmul_2)
	vldr		v01, [vp]
	veor		c01, c01, c01
	C Load via vp, store via rp
	mov		vp, rp
	vld1.64		{l01}, [vp]!
	vld1.32		{u00[]}, [up]!
	vmull.u32	q3, u00, v01
	sub		n, #1
	b		.Lentry
	
.Loop:
	vld1.32		l01[1], [vp]!
.Lentry:
	vaddl.u32	q2, l01, c01
	vld1.32		{u00[]}, [up]!
	subs		n, #1
	vadd.i64	q1, q2, q3 
	vmull.u32	q3, u00, v01

	C q1 overlaps d2, d3, so at this point,
	C l01 = d2 = u0*v0 + c0 + l0
	C c01 = d3 = u0*v1 + c1 + l1
	C We need to store low part of l01, shift it, and load high part

	vst1.32		l01[0], [rp]!
	vshr.u64	l01, l01, #32
	bne		.Loop

	vaddl.u32	q2, l01, c01
	subs		n, #1
	vadd.i64	q1, q2, q3 

	vst1.32		l01[0], [rp]!
	vshr.u64	l01, l01, #32
	
	vadd.i64	c01, c01, l01
	vst1.32		c01[0], [rp]
	vmov.32		r0, c01[1]
	
	bx		lr
EPILOGUE()



-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.