llvm dev - Sep 2011 - [LLVMdev] Proposal: floating point accuracy metadata (OpenCL related)

Hi,

This is my proposal to add floating point accuracy support to LLVM.
The intention is that the frontend may provide metadata to signal to
the backend that it may select a less accurate (i.e. more efficient)
instruction to perform a given operation.  This is primarily a
requirement of OpenCL, which specifies that certain floating point
operations may be computed inaccurately.

Comments appreciated.

------------------------------------------------------------------------

Specification
-------------

The metadata attribute is named "fpaccuracy", and contains a single
integer parameter which specifies the maximum relative error of the
operation to which it is attached, in ULPs.  For the definition of
ULPs we follow the definition given in the OpenCL 1.1 specification
(section 7.4):

	If x is a real number that lies between two finite
	consecutive floating-point numbers a and b, without being
	equal to one of them, then ulp(x) = |b - a|, otherwise
	ulp(x) is the distance between the two non-equal finite
	floating-point numbers nearest x. Moreover, ulp(NaN) is
	NaN.

Implementation
--------------

As a start, I am attaching a Clang patch which adds this metadata
to single precision floating point division instructions in OpenCL
(which are accurate to 2.5ulp, per OpenCL 1.1 s7.4).  I would imagine
that in the future we may want to allow the user to control the level
of accuracy (one idea is that we can provide a __builtin_fpaccuracy
function, which could be used like this):

__builtin_fpaccuracy(x/y, 2) // compute x/y with a maximum error of 2ulp

The backend is not my area of expertise, so I won't venture to say
how difficult it would be to recognise and act on the attribute there.

Alternatives
------------

I am proposing metadata here, since it may be removed without
negatively affecting accuracy.

We could add fpaccuracy as a core LLVM attribute (a la nsw and nuw).
But this would be relatively intrusive (only a few clients care about
accuracy) and it would need to be added to a variety of unrelated
instruction types (most floating point operations, as well as
intrinsic calls).

We could also introduce a set of intrinsics for inaccurate FP
operations.  The main disadvantage is that we would need to add an
intrinsic for each FP operation, which could add up to a lot of work.
Furthermore, the new intrinsics would not necessarily be recognised
by the existing optimisers.

------------------------------------------------------------------------

Thanks,
-- 
Peter
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Annotate-imprecise-FP-division-with-fpaccuracy-metad.patch
Type: text/x-diff
Size: 3929 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110907/1961cf40/attachment.patch>

Hi Peter,

This sounds like I really good idea. One thing that did occur to me
though from an OpenCL point of view is that ULP accuracy requirements
can differ for embedded and full profile so that may need to be handled
somehow.

Thanks,
Rob 

On Wed, 2011-09-07 at 21:55 +0100, Peter Collingbourne
wrote:
> Hi,
> 
> This is my proposal to add floating point accuracy support to LLVM.
> The intention is that the frontend may provide metadata to signal to
> the backend that it may select a less accurate (i.e. more efficient)
> instruction to perform a given operation.  This is primarily a
> requirement of OpenCL, which specifies that certain floating point
> operations may be computed inaccurately.
> 
> Comments appreciated.
> 
> ------------------------------------------------------------------------
> 
> Specification
> -------------
> 
> The metadata attribute is named "fpaccuracy", and contains a
single
> integer parameter which specifies the maximum relative error of the
> operation to which it is attached, in ULPs.  For the definition of
> ULPs we follow the definition given in the OpenCL 1.1 specification
> (section 7.4):
> 
> 	If x is a real number that lies between two finite
> 	consecutive floating-point numbers a and b, without being
> 	equal to one of them, then ulp(x) = |b - a|, otherwise
> 	ulp(x) is the distance between the two non-equal finite
> 	floating-point numbers nearest x. Moreover, ulp(NaN) is
> 	NaN.
> 
> Implementation
> --------------
> 
> As a start, I am attaching a Clang patch which adds this metadata
> to single precision floating point division instructions in OpenCL
> (which are accurate to 2.5ulp, per OpenCL 1.1 s7.4).  I would imagine
> that in the future we may want to allow the user to control the level
> of accuracy (one idea is that we can provide a __builtin_fpaccuracy
> function, which could be used like this):
> 
> __builtin_fpaccuracy(x/y, 2) // compute x/y with a maximum error of 2ulp
> 
> The backend is not my area of expertise, so I won't venture to say
> how difficult it would be to recognise and act on the attribute there.
> 
> Alternatives
> ------------
> 
> I am proposing metadata here, since it may be removed without
> negatively affecting accuracy.
> 
> We could add fpaccuracy as a core LLVM attribute (a la nsw and nuw).
> But this would be relatively intrusive (only a few clients care about
> accuracy) and it would need to be added to a variety of unrelated
> instruction types (most floating point operations, as well as
> intrinsic calls).
> 
> We could also introduce a set of intrinsics for inaccurate FP
> operations.  The main disadvantage is that we would need to add an
> intrinsic for each FP operation, which could add up to a lot of work.
> Furthermore, the new intrinsics would not necessarily be recognised
> by the existing optimisers.
> 
> ------------------------------------------------------------------------
> 
> Thanks,
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev

Peter,
 Is there a way to make this flag globally available? Metadata can be fairly
expensive to handle at each node when in many cases it is a global flag and not
a per operation flag.
> -----Original Message-----
> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
cs.uiuc.edu]
> On Behalf Of Robert Quill
> Sent: Thursday, September 08, 2011 3:24 AM
> To: Peter Collingbourne
> Cc: anton.lokhmotov at arm.com; cfe-dev at cs.uiuc.edu; llvmdev at
cs.uiuc.edu
> Subject: Re: [LLVMdev] [cfe-dev] Proposal: floating point accuracy
> metadata (OpenCL related)
> 
> Hi Peter,
> 
> This sounds like I really good idea. One thing that did occur to me
> though from an OpenCL point of view is that ULP accuracy requirements
> can differ for embedded and full profile so that may need to be handled
> somehow.
> 
> Thanks,
> Rob
> 
> On Wed, 2011-09-07 at 21:55 +0100, Peter Collingbourne wrote:
> > Hi,
> >
> > This is my proposal to add floating point accuracy support to LLVM.
> > The intention is that the frontend may provide metadata to signal to
> > the backend that it may select a less accurate (i.e. more efficient)
> > instruction to perform a given operation.  This is primarily a
> > requirement of OpenCL, which specifies that certain floating point
> > operations may be computed inaccurately.
> >
> > Comments appreciated.
> >
> > ---------------------------------------------------------------------
> ---
> >
> > Specification
> > -------------
> >
> > The metadata attribute is named "fpaccuracy", and contains a
single
> > integer parameter which specifies the maximum relative error of the
> > operation to which it is attached, in ULPs.  For the definition of
> > ULPs we follow the definition given in the OpenCL 1.1 specification
> > (section 7.4):
> >
> > 	If x is a real number that lies between two finite
> > 	consecutive floating-point numbers a and b, without being
> > 	equal to one of them, then ulp(x) = |b - a|, otherwise
> > 	ulp(x) is the distance between the two non-equal finite
> > 	floating-point numbers nearest x. Moreover, ulp(NaN) is
> > 	NaN.
> >
> > Implementation
> > --------------
> >
> > As a start, I am attaching a Clang patch which adds this metadata
> > to single precision floating point division instructions in OpenCL
> > (which are accurate to 2.5ulp, per OpenCL 1.1 s7.4).  I would imagine
> > that in the future we may want to allow the user to control the level
> > of accuracy (one idea is that we can provide a __builtin_fpaccuracy
> > function, which could be used like this):
> >
> > __builtin_fpaccuracy(x/y, 2) // compute x/y with a maximum error of
> 2ulp
> >
> > The backend is not my area of expertise, so I won't venture to say
> > how difficult it would be to recognise and act on the attribute
> there.
> >
> > Alternatives
> > ------------
> >
> > I am proposing metadata here, since it may be removed without
> > negatively affecting accuracy.
> >
> > We could add fpaccuracy as a core LLVM attribute (a la nsw and nuw).
> > But this would be relatively intrusive (only a few clients care about
> > accuracy) and it would need to be added to a variety of unrelated
> > instruction types (most floating point operations, as well as
> > intrinsic calls).
> >
> > We could also introduce a set of intrinsics for inaccurate FP
> > operations.  The main disadvantage is that we would need to add an
> > intrinsic for each FP operation, which could add up to a lot of work.
> > Furthermore, the new intrinsics would not necessarily be recognised
> > by the existing optimisers.
> >
> > ---------------------------------------------------------------------
> ---
> >
> > Thanks,
> > _______________________________________________
> > cfe-dev mailing list
> > cfe-dev at cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
> 
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Hi Peter,
> This is my proposal to add floating point accuracy support to LLVM.
> The intention is that the frontend may provide metadata to signal to
> the backend that it may select a less accurate (i.e. more efficient)
> instruction to perform a given operation.
I'm a bit worried that accuracy metadata may be dropped or modified before
it reaches the backend.  Currently, an OpenCL backend can safely assume that
the division operation is the same as specified in the OpenCL standard (i.e.
with the maximum relative error of 2.5 ulps), and map it, say, to the native
division instruction.  If "no accuracy metadata" would mean "use
correct
rounding", you are correct in that accuracy metadata could be dropped
without negatively affecting accuracy.  Dropping accuracy metadata could,
however, negatively affect performance, if the backend would have to go for
a slow software implementation instead of a fast hardware implementation.
If would be better if "no accuracy metadata" would mean "use the
default
language accuracy", so only allowing for relaxing accuracy further.  But
then LLVM-IR would remain language-dependent.
> We could also introduce a set of intrinsics for inaccurate FP
> operations.  The main disadvantage is that we would need to add an
> intrinsic for each FP operation, which could add up to a lot of work.
> Furthermore, the new intrinsics would not necessarily be recognised
> by the existing optimisers.
The existing optimisers would need to be extended to recognise relaxed
accuracy requirements.  Otherwise, they could over-tighten them for safety
(again negatively affecting performance).

I suggest we discuss this on Friday at the LLVM developers' meeting in
London.

Best, Anton.