Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #15504 > unrolled thread

The container abstraction and parallel programming

Back to article view | Back to comp.lang.c

Contents

  The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-07 00:02 +0100
    Re: The container abstraction and parallel programming blp@cs.stanford.edu (Ben Pfaff) - 2012-01-06 15:08 -0800
      Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-07 00:27 +0100
        Re: The container abstraction and parallel programming blp@cs.stanford.edu (Ben Pfaff) - 2012-01-06 15:30 -0800
          Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-07 00:41 +0100
    Re: The container abstraction and parallel programming Kaz Kylheku <kaz@kylheku.com> - 2012-01-07 00:04 +0000
      Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-07 09:06 +0100
      Re: The container abstraction and parallel programming Nick Keighley <nick_keighley_nospam@hotmail.com> - 2012-01-08 03:42 -0800
    Re: The container abstraction and parallel programming Ian Collins <ian-news@hotmail.com> - 2012-01-07 13:50 +1300
      Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-07 09:31 +0100
        Re: The container abstraction and parallel programming Ian Collins <ian-news@hotmail.com> - 2012-01-07 22:03 +1300
        Re: The container abstraction and parallel programming Stephen Sprunk <stephen@sprunk.org> - 2012-01-07 07:39 -0600
          Re: The container abstraction and parallel programming Gene <gene.ressler@gmail.com> - 2012-01-07 09:27 -0800
            Re: The container abstraction and parallel programming Stephen Sprunk <stephen@sprunk.org> - 2012-01-08 11:37 -0600
              Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-08 18:42 +0100
          Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-08 11:48 +0100
            Re: The container abstraction and parallel programming ec429 <ec429@cam.ac.uk> - 2012-01-08 11:16 +0000
            Re: The container abstraction and parallel programming Stephen Sprunk <stephen@sprunk.org> - 2012-01-08 11:52 -0600
              Re: The container abstraction and parallel programming Keith Thompson <kst-u@mib.org> - 2012-01-08 14:17 -0800
                Re: The container abstraction and parallel programming pete <pfiland@mindspring.com> - 2012-01-08 22:08 -0500
                Re: The container abstraction and parallel programming Stephen Sprunk <stephen@sprunk.org> - 2012-01-09 11:07 -0600
                  Re: The container abstraction and parallel programming Keith Thompson <kst-u@mib.org> - 2012-01-09 14:55 -0800
              Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-09 00:22 +0100
            Re: The container abstraction and parallel programming Nobody <nobody@nowhere.com> - 2012-01-09 14:19 +0000
              Re: The container abstraction and parallel programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-09 16:40 +0000
              Re: The container abstraction and parallel programming Kaz Kylheku <kaz@kylheku.com> - 2012-01-09 17:53 +0000
              Re: The container abstraction and parallel programming Gene <gene.ressler@gmail.com> - 2012-01-10 16:58 -0800
    Re: The container abstraction and parallel programming Robert Wessel <robertwessel2@yahoo.com> - 2012-01-07 01:28 -0600
    Re: The container abstraction and parallel programming Jens Gustedt <jens.gustedt@loria.fr> - 2012-01-07 09:39 +0100
      Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-07 09:54 +0100
        Re: The container abstraction and parallel programming Jens Gustedt <jens.gustedt@loria.fr> - 2012-01-07 11:36 +0100
    Re: The container abstraction and parallel programming Gareth Owen <gwowen@gmail.com> - 2012-01-08 08:08 +0000
      Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-08 11:41 +0100
        Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-08 11:53 +0100
        Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-08 11:59 +0100
        Re: The container abstraction and parallel programming ec429 <ec429@cam.ac.uk> - 2012-01-08 11:05 +0000
          Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-08 12:29 +0100
            Re: The container abstraction and parallel programming ec429 <ec429@cam.ac.uk> - 2012-01-08 13:35 +0000
        Re: The container abstraction and parallel programming gwowen <gwowen@gmail.com> - 2012-01-09 01:09 -0800
        Re: The container abstraction and parallel programming Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-26 09:23 -0800
          Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-26 23:41 +0100
            Re: The container abstraction and parallel programming Tim Rentsch <txr@alumni.caltech.edu> - 2012-03-07 16:18 -0800

Page 1 of 3  [1] 2 3  Next page →

#15504 — The container abstraction and parallel programming

Today, more than 10 years tafter Intel introduced the first SIMD 
instructions it is still not possible to use those instructions to do 
SIMD programming when you use C and two mainstream compilers like gcc or 
MSVC.

 From the C side there is absolutely no support for this type of 
programming, even though plain arrays could do the trick obviously.


The container abstraction, specifically the valarray container, could be 
used to *mean* SIMD using operator overloading.

The use case could be

ValArray operator+(ValArray left,ValArray right);

This would allow an operation like adding two arrays element-wise
to be performed using SIMD instructions.


Obviously, the usual "optimizations" can be added to those
basic operations so that
	
         ValArray a,b,c,d;

	a = b+c+d;

doesn't have to produce an intermediate array but can be "compiled"
by an overloaded assignment operator to generate

	a[i] = b[i]+c[i]+d[i];

as is done in C++. Each overloaded operator returns a token operator
containing information about its arguments, and the overloaded 
assignment operator compiles correct element-wise code by reparsing
the generated tree.

To prepare for this, the C Containers library proposes the ValArray
container, for each of the basic types (char, short, int, long long and 
size_t).

In the sample implementation there is a generic module that
allows to generate code for ANY type, also those being left out like
long (since it is always either equal to int or equal to long long in
all implementations I know of). The type size_t was added to be able
to correctly index any sequantial container with a ValArray of size_t's.

The code proposed NOW is plain serial code, but can (and should) be
replaced in more sophisticated implementations than the sample 
implementation to do SIMD programming, one of the most basic forms
of parallelism, already available in plain hardware since already 10 
years...

Obviously the four basic operations should be there, but other kinds of 
array operations could be interesting like

o REDUCE Apply binary operation to each element and the running total:
	REDUCE + 1 2 3 4 5  --> 1+2+3+4+5 = 15

         You apply operator + to the identity element for "+" and to the
         first element: 0+1 --> 1
         You apply the operator + to the second element and the result
         of the last operation: 1+2-->3
	ETC until the last element is reached.

o EXPAND Apply binary operation producing a ValArray of same length
         containing the intermediate results:
         EXPAND + 1 2 3 4 5 --> 1 3 6 10 15


o SELECT  Apply boolean vector to ValArray selecting all elements that
           correspond to 1 and eliminate those with zeros.

	SELECT 1 1 0 1 0 0 / 10 20 30 40 50 60 --> 10 20 40

o EXTEND Apply boolean vector to ValArray leaving all elements with 1
          and introducing the zero or blank (for character arrays) at the
          zero positions:

          EXTEND 1 1 0 1 0 0 / 10 20 40 --> 10 20 0 40 0 0

The idea is to select a set of operations that makes it easy to work 
with arrays as objects of operations instead of working with scalar data.

What new operations should be in the set?
How could those operations be incoporated into mainstream C?


jacob

[toc] | [next] | [standalone]

#15506

jacob navia <jacob@spamsink.net> writes:

> Today, more than 10 years tafter Intel introduced the first SIMD
> instructions it is still not possible to use those instructions to do
> SIMD programming when you use C and two mainstream compilers like gcc
> or MSVC.
>
> From the C side there is absolutely no support for this type of
> programming, even though plain arrays could do the trick obviously.

"absolutely no support"?  You exaggerate:
http://gcc.gnu.org/onlinedocs/gcc-4.6.2/gcc/X86-Built_002din-Functions.html#X86-Built_002din-Functions
-- 
"For those who want to translate C to Pascal, it may be that a lobotomy
 serves your needs better." --M. Ambuhl

"Here are the steps to create a C-to-Turbo-Pascal translator..." --H. Schildt

[toc] | [prev] | [next] | [standalone]

#15508

Le 07/01/12 00:08, Ben Pfaff a écrit :
> jacob navia<jacob@spamsink.net>  writes:
>
>> Today, more than 10 years tafter Intel introduced the first SIMD
>> instructions it is still not possible to use those instructions to do
>> SIMD programming when you use C and two mainstream compilers like gcc
>> or MSVC.
>>
>>  From the C side there is absolutely no support for this type of
>> programming, even though plain arrays could do the trick obviously.
>
> "absolutely no support"?  You exaggerate:
> http://gcc.gnu.org/onlinedocs/gcc-4.6.2/gcc/X86-Built_002din-Functions.html#X86-Built_002din-Functions

Hi Ben

Look, those functions exist of curse but that is not standard C, those
functions have no links to the rest  of the language.

Besides, they are tied to the Intel architecture (what
is not wrong of course) but the idea behind my post is to try to
abstract a bit from a single architecture to a more *general* SIMD
programming. Note that the notions of container and operations
are NOT tied to Intel, IBM or Motorola vector proposals but could
be used with all three.

Even me with my limited ressources have some intrinsics for some 
operations but that is really not *language* support Ben.

[toc] | [prev] | [next] | [standalone]

#15509

jacob navia <jacob@spamsink.net> writes:

> Le 07/01/12 00:08, Ben Pfaff a écrit :
>> jacob navia<jacob@spamsink.net>  writes:
>>
>>> Today, more than 10 years tafter Intel introduced the first SIMD
>>> instructions it is still not possible to use those instructions to do
>>> SIMD programming when you use C and two mainstream compilers like gcc
>>> or MSVC.
>>>
>>>  From the C side there is absolutely no support for this type of
>>> programming, even though plain arrays could do the trick obviously.
>>
>> "absolutely no support"?  You exaggerate:
>> http://gcc.gnu.org/onlinedocs/gcc-4.6.2/gcc/X86-Built_002din-Functions.html#X86-Built_002din-Functions
>
> Look, those functions exist of curse but that is not standard C, those
> functions have no links to the rest  of the language.

If that's your purpose then I don't know why you started out by
saying that you can't do it with "mainstream compilers like GCC".
-- 
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.\
 \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

[toc] | [prev] | [next] | [standalone]

#15510

Le 07/01/12 00:30, Ben Pfaff a écrit :
> jacob navia<jacob@spamsink.net>  writes:
>
>> Le 07/01/12 00:08, Ben Pfaff a écrit :
>>> jacob navia<jacob@spamsink.net>   writes:
>>>
>>>> Today, more than 10 years tafter Intel introduced the first SIMD
>>>> instructions it is still not possible to use those instructions to do
>>>> SIMD programming when you use C and two mainstream compilers like gcc
>>>> or MSVC.
>>>>
>>>>   From the C side there is absolutely no support for this type of
>>>> programming, even though plain arrays could do the trick obviously.
>>>
>>> "absolutely no support"?  You exaggerate:
>>> http://gcc.gnu.org/onlinedocs/gcc-4.6.2/gcc/X86-Built_002din-Functions.html#X86-Built_002din-Functions
>>
>> Look, those functions exist of curse but that is not standard C, those
>> functions have no links to the rest  of the language.
>
> If that's your purpose then I don't know why you started out by
> saying that you can't do it with "mainstream compilers like GCC".

... and MSVC, and ANY compiler now. It wasn't directed against gcc
specifically.


Because all those compilers propose
the same thing as gcc/Intel compilers do: a series of machine dependent
intrinsics that make your code not portable at all, and maybe because of
that are not accepted by a large user base.

What I wanted to propose is a more abstract and portable way of doing 
SIMD than just using pseudo functions that map to one instructions of 
the Intel instruction set.

Obviously the problem is there since all that those intrinsics propose
is very low level operations (what amounts to more or less returning to
àssembly language in C since all the intrinsics map to specific
Intel/AMD instructions).

What my aim is is to start a discussion about what kind of constructs 
could be used to abstract from those operations into more general concepts.

[toc] | [prev] | [next] | [standalone]

#15514

On 2012-01-06, jacob navia <jacob@spamsink.net> wrote:
> Today, more than 10 years tafter Intel introduced the first SIMD 
> instructions it is still not possible to use those instructions to do 
> SIMD programming when you use C and two mainstream compilers like gcc or 
> MSVC.

If anything, that may be an indicator that maybe nobody cares that much about
Intel's SIMD instructions.  It's not hard to see why.

SIMD instructions do not translate to a tangible benefit for the average
consumer of Intel chips. (Marketing 101: features need to connect with
benefits!)

There was a time when games and video playback stretched the ability of the CPU
to the core, and hardware for accelerating them was next to nonexistent.  The
processing-intensive tasks in those kinds of applications are handled by
dedicated hardware these days.

SIMD will not fix the major, user-visible performance issues in a Wintel PC,
like long boot times, or browsers becoming unresponsive for seconds at a time.

[toc] | [prev] | [next] | [standalone]

#15525

Le 07/01/12 01:04, Kaz Kylheku a écrit :
> On 2012-01-06, jacob navia<jacob@spamsink.net>  wrote:
>> Today, more than 10 years tafter Intel introduced the first SIMD
>> instructions it is still not possible to use those instructions to do
>> SIMD programming when you use C and two mainstream compilers like gcc or
>> MSVC.
>
> If anything, that may be an indicator that maybe nobody cares that much about
> Intel's SIMD instructions.  It's not hard to see why.
>
> SIMD instructions do not translate to a tangible benefit for the average
> consumer of Intel chips. (Marketing 101: features need to connect with
> benefits!)
>

But... how could those benefits be *USED* unless you program in assembly?

That is the whole point of my post. You can't say that users do not
want those features if there are no high level constructs that they
can use to make that happen!


> There was a time when games and video playback stretched the ability of the CPU
> to the core, and hardware for accelerating them was next to nonexistent.  The
> processing-intensive tasks in those kinds of applications are handled by
> dedicated hardware these days.
>

But the problem *remains* since you can't address that dedicated 
hardware from a high level language anyway!


> SIMD will not fix the major, user-visible performance issues in a Wintel PC,
> like long boot times, or browsers becoming unresponsive for seconds at a time.

SIMD needs a special kind of programming that is badly supported in
current serial languages like C or C++. Many parallel languages have
been proposed but they are of too limited scope to catch. What is needed
is a way to address SIMD programming from within a known general purpose
programming *context*.

[toc] | [prev] | [next] | [standalone]

#15580

On Jan 7, 12:04 am, Kaz Kylheku <k...@kylheku.com> wrote:
> On 2012-01-06, jacob navia <ja...@spamsink.net> wrote:
>
> > Today, more than 10 years tafter Intel introduced the first SIMD
> > instructions it is still not possible to use those instructions to do
> > SIMD programming when you use C and two mainstream compilers like gcc or
> > MSVC.
>
> If anything, that may be an indicator that maybe nobody cares that much about
> Intel's SIMD instructions.  It's not hard to see why.
>
> SIMD instructions do not translate to a tangible benefit for the average
> consumer of Intel chips. (Marketing 101: features need to connect with
> benefits!)

but there's an awful lot of Intel chips sold. Even 0.1% of that market
is huge. Just because the average desk top user doesn't need SIMD
doesn't mean its market is negligable.

> There was a time when games and video playback stretched the ability of the CPU
> to the core, and hardware for accelerating them was next to nonexistent.  The
> processing-intensive tasks in those kinds of applications are handled by
> dedicated hardware these days.
>
> SIMD will not fix the major, user-visible performance issues in a Wintel PC,
> like long boot times, or browsers becoming unresponsive for seconds at a time.

yes but there are people who need heavy number crunching. CAD for one,
I'd think.

[toc] | [prev] | [next] | [standalone]

#15517

On 01/ 7/12 12:02 PM, jacob navia wrote:
> Today, more than 10 years tafter Intel introduced the first SIMD
> instructions it is still not possible to use those instructions to do
> SIMD programming when you use C and two mainstream compilers like gcc or
> MSVC.
>
>   From the C side there is absolutely no support for this type of
> programming, even though plain arrays could do the trick obviously.

That may be the case for those compilers, but not for others.  For 
example the Sun Studio compilers (I'd expect Intel to offer something as 
well) have a number of vector processing optimisations which include simd.

I think this class of optimisation is best left as a compiler 
implementation detail.  The range of vector processing support 
(including the likes of OpenMP) is simply too large (from nothing to a 
GPU) to be considered for standardisation. If the demand is there, the 
vendor will deliver.

> The container abstraction, specifically the valarray container, could be
> used to *mean* SIMD using operator overloading.

A similar approach has been used by some compilers for many years, 
typically implemented as some form of "performance library" for vector 
type operations.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#15527

Le 07/01/12 01:50, Ian Collins a écrit :
> On 01/ 7/12 12:02 PM, jacob navia wrote:
>> Today, more than 10 years tafter Intel introduced the first SIMD
>> instructions it is still not possible to use those instructions to do
>> SIMD programming when you use C and two mainstream compilers like gcc or
>> MSVC.
>>
>> From the C side there is absolutely no support for this type of
>> programming, even though plain arrays could do the trick obviously.
>
> That may be the case for those compilers, but not for others. For
> example the Sun Studio compilers (I'd expect Intel to offer something as
> well) have a number of vector processing optimisations which include simd.
>

Yes, Intel and Sun, as hardware vendors, have a real interest in making 
people use the features of their hardware and will try to propose
either automatically SIMD deduction or inline assembly that supports
their features directly.

Problem is, even after dozens of years and millions and millions of
dollars in research, automatic SIMD parallelization remains VERY 
difficult for the genral case. The problem, basically, is as follows:

Automatic parallelization must PROVE that no dependencies exist
between the array members, no unforeseen side effects can possibly
occur and ONLY THEN the constructs in question can be parallelized.

All this needs extensive program analysis, what is made even more 
difficult with the model of separate module compilation...

High level constructs designed to allow the programmer assert that
he/she wants parallel programming FOR THIS OBJECT simplify the
task of the compiler, allowing for simpler compilers and more
widespread use.

> I think this class of optimisation is best left as a compiler
> implementation detail. The range of vector processing support (including
> the likes of OpenMP) is simply too large (from nothing to a GPU) to be
> considered for standardisation. If the demand is there, the vendor will
> deliver.
>

Well, SIMD processing is basically the same, only the SCALE changes from
an Intel SSE4 and a GPU with some thousand nodes. Using a higher level 
construct you LEAVE the details to the compiler obviously, assuming a
compiler for Intel will make use of SSE4 and a compiler for a GPU will
use the GPU. What you do NOT leave to the compiler is the ANALYSIS as to
which constructs can be used with SIMD, allowing the compiler to 
specialize in code generation without burdening it with a complete
analysis of all the possible data paths that could interfere with the
SIMD optimization.


>> The container abstraction, specifically the valarray container, could be
>> used to *mean* SIMD using operator overloading.
>
> A similar approach has been used by some compilers for many years,
> typically implemented as some form of "performance library" for vector
> type operations.
>

Yes, I just wanted to propose that idea not for a single compiler but 
for the language in general.

[toc] | [prev] | [next] | [standalone]

#15530

On 01/ 7/12 09:31 PM, jacob navia wrote:
> Le 07/01/12 01:50, Ian Collins a écrit :
>> On 01/ 7/12 12:02 PM, jacob navia wrote:
>>> Today, more than 10 years tafter Intel introduced the first SIMD
>>> instructions it is still not possible to use those instructions to do
>>> SIMD programming when you use C and two mainstream compilers like gcc or
>>> MSVC.
>>>
>>>  From the C side there is absolutely no support for this type of
>>> programming, even though plain arrays could do the trick obviously.
>>
>> That may be the case for those compilers, but not for others. For
>> example the Sun Studio compilers (I'd expect Intel to offer something as
>> well) have a number of vector processing optimisations which include simd.
>>
>
> Yes, Intel and Sun, as hardware vendors, have a real interest in making
> people use the features of their hardware and will try to propose
> either automatically SIMD deduction or inline assembly that supports
> their features directly.
>
> Problem is, even after dozens of years and millions and millions of
> dollars in research, automatic SIMD parallelization remains VERY
> difficult for the genral case. The problem, basically, is as follows:
>
> Automatic parallelization must PROVE that no dependencies exist
> between the array members, no unforeseen side effects can possibly
> occur and ONLY THEN the constructs in question can be parallelized.
>
> All this needs extensive program analysis, what is made even more
> difficult with the model of separate module compilation...

> High level constructs designed to allow the programmer assert that
> he/she wants parallel programming FOR THIS OBJECT simplify the
> task of the compiler, allowing for simpler compilers and more
> widespread use.

I guess pragmas are another option, as used for OpenMP.  We already have 
the restrict keyword to simplify analysis with pointer parameters, maybe 
something similar for parallelisation?

>>> The container abstraction, specifically the valarray container, could be
>>> used to *mean* SIMD using operator overloading.
>>
>> A similar approach has been used by some compilers for many years,
>> typically implemented as some form of "performance library" for vector
>> type operations.
>>
>
> Yes, I just wanted to propose that idea not for a single compiler but
> for the language in general.

I do see your point, but there are many CPU/OS specific tricks used to 
get the optimum performance on a particular platform, which is way 
vendor's compilers generally squeeze the best performance from a system. 
  Would this on its own do enough to justify its inclusion in the language?

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#15541

On 07-Jan-12 02:31, jacob navia wrote:
> Le 07/01/12 01:50, Ian Collins a écrit :
>> On 01/ 7/12 12:02 PM, jacob navia wrote:
>>> Today, more than 10 years tafter Intel introduced the first SIMD
>>> instructions it is still not possible to use those instructions to do
>>> SIMD programming when you use C and two mainstream compilers like gcc or
>>> MSVC.
>>>
>>> From the C side there is absolutely no support for this type of
>>> programming, even though plain arrays could do the trick obviously.
>>
>> That may be the case for those compilers, but not for others. For
>> example the Sun Studio compilers (I'd expect Intel to offer something as
>> well) have a number of vector processing optimisations which include
>> simd.
> 
> Yes, Intel and Sun, as hardware vendors, have a real interest in making
> people use the features of their hardware and will try to propose
> either automatically SIMD deduction or inline assembly that supports
> their features directly.
> 
> Problem is, even after dozens of years and millions and millions of
> dollars in research, automatic SIMD parallelization remains VERY
> difficult for the genral case. The problem, basically, is as follows:
> 
> Automatic parallelization must PROVE that no dependencies exist
> between the array members, no unforeseen side effects can possibly
> occur and ONLY THEN the constructs in question can be parallelized.
> 
> All this needs extensive program analysis, what is made even more
> difficult with the model of separate module compilation...

There are no "dependencies" between array members.  There is a possible
aliasing problem when dealing with pointers rather than arrays, but that
is easily enough solved with "restrict" qualifiers.

I don't understand what you think the problem is.

S

-- 
Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

[toc] | [prev] | [next] | [standalone]

#15547

On Jan 7, 2:39 pm, Stephen Sprunk <step...@sprunk.org> wrote:
> On 07-Jan-12 02:31, jacob navia wrote:
>
>
>
>
>
> > Le 07/01/12 01:50, Ian Collins a écrit :
> >> On 01/ 7/12 12:02 PM, jacob navia wrote:
> >>> Today, more than 10 years tafter Intel introduced the first SIMD
> >>> instructions it is still not possible to use those instructions to do
> >>> SIMD programming when you use C and two mainstream compilers like gcc or
> >>> MSVC.
>
> >>> From the C side there is absolutely no support for this type of
> >>> programming, even though plain arrays could do the trick obviously.
>
> >> That may be the case for those compilers, but not for others. For
> >> example the Sun Studio compilers (I'd expect Intel to offer something as
> >> well) have a number of vector processing optimisations which include
> >> simd.
>
> > Yes, Intel and Sun, as hardware vendors, have a real interest in making
> > people use the features of their hardware and will try to propose
> > either automatically SIMD deduction or inline assembly that supports
> > their features directly.
>
> > Problem is, even after dozens of years and millions and millions of
> > dollars in research, automatic SIMD parallelization remains VERY
> > difficult for the genral case. The problem, basically, is as follows:
>
> > Automatic parallelization must PROVE that no dependencies exist
> > between the array members, no unforeseen side effects can possibly
> > occur and ONLY THEN the constructs in question can be parallelized.
>
> > All this needs extensive program analysis, what is made even more
> > difficult with the model of separate module compilation...
>
> There are no "dependencies" between array members.  There is a possible
> aliasing problem when dealing with pointers rather than arrays, but that
> is easily enough solved with "restrict" qualifiers.
>
> I don't understand what you think the problem is.
>
> S
>
> --
> Stephen Sprunk         "God does not play dice."  --Albert Einstein
> CCIE #3723         "God is an inveterate gambler, and He throws the
> K5SSS        dice at every possible opportunity." --Stephen Hawking- Hide quoted text -

He has to be referring to loop dependencies as in

for (i = 0; i < n; i++) a[i] = a[i-3] + 2;

The main reason I'm writing is to point out that late version C
compilers including gcc, Intel, and I believe though am not sure,
Microsoft all will emit vector instructions for loops coded with
commonsense idioms.  I have a signal processing code that speeds up by
a factor of 3 with gcc when this opimization is turned on.

Cheers.

[toc] | [prev] | [next] | [standalone]

#15588

On 07-Jan-12 11:27, Gene wrote:
> On Jan 7, 2:39 pm, Stephen Sprunk <step...@sprunk.org> wrote:
>> On 07-Jan-12 02:31, jacob navia wrote:
>>> Automatic parallelization must PROVE that no dependencies exist
>>> between the array members, no unforeseen side effects can possibly
>>> occur and ONLY THEN the constructs in question can be parallelized.
>>
>>> All this needs extensive program analysis, what is made even more
>>> difficult with the model of separate module compilation...
>>
>> There are no "dependencies" between array members.  There is a possible
>> aliasing problem when dealing with pointers rather than arrays, but that
>> is easily enough solved with "restrict" qualifiers.
>>
>> I don't understand what you think the problem is.
> 
> He has to be referring to loop dependencies as in
> 
> for (i = 0; i < n; i++) a[i] = a[i-3] + 2;
> 
> The main reason I'm writing is to point out that late version C
> compilers including gcc, Intel, and I believe though am not sure,
> Microsoft all will emit vector instructions for loops coded with
> commonsense idioms.  I have a signal processing code that speeds up by
> a factor of 3 with gcc when this opimization is turned on.

Right.  Unfortunately, GCC seems to only recognize "commonsense idioms"
and misses opportunities to vectorize code that doesn't fit those
idioms, even when doing so would be provably safe.  So, you have to know
what idioms it understands and modify your code to comply; that is not
ideal, but it's hardly a new concept--and presumably the set of idioms
will expand over time as folks complain or contribute patches.

I have no idea if ICC (or MSVC?) has the same limitation.

S

-- 
Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

[toc] | [prev] | [next] | [standalone]

#15589

Le 08/01/12 18:37, Stephen Sprunk a écrit :
>
> Right.  Unfortunately, GCC seems to only recognize "commonsense idioms"
> and misses opportunities to vectorize code that doesn't fit those
> idioms, even when doing so would be provably safe.  So, you have to know
> what idioms it understands and modify your code to comply; that is not
> ideal, but it's hardly a new concept--and presumably the set of idioms
> will expand over time as folks complain or contribute patches.
>
> I have no idea if ICC (or MSVC?) has the same limitation.

Not the same but SIMILAR limitations. Then, for each compiler:
do {
	learnLimitations();
	ModifyCode();
} while (ItsnotInStandardC());

:-)

That is the reason for my proposal. There is no standard way of doing 
SIMD even if most modern CPUs have SIMD extensions.

[toc] | [prev] | [next] | [standalone]

#15574

Le 07/01/12 14:39, Stephen Sprunk a écrit :
>
> There are no "dependencies" between array members.  There is a possible
> aliasing problem when dealing with pointers rather than arrays, but that
> is easily enough solved with "restrict" qualifiers.
>
> I don't understand what you think the problem is.
>
> S
>

The problem, Stephen, is as follows:

gcc will vectorize this:

void doADD(double *L, double *R, double *result,size_t n)
{
      for(size_t i=0; i<n;i++) result[i]=L[i]+R[i];
}

but will NOT vectorize this:

void doADD(double *L, double *R, double *result,size_t n)
{
      for(size_t i=0; i<n;i++) result[n-i]=L[n-i]+R[n-i];
}

Why?

As you (correctly) say:

 > There are no "dependencies" between array members.

All this huge machinery for automatic vectorizing has never worked
correctly for dozens of years since requires an incredible
amount of program analysis. My proposition is:

Why make complicated something that you can do in a simple way?

Let the programmer declare the data that should be handled in an SIMD
way.

If I write:

	c = (a+b)/2;
	if (c&1) fn(1);

You could deduce that c must be of integer type isn't it?
LET THE COMPILER DO THAT. Let's eliminate declarations for
integer and let the compiler deduce from the program text
the type of each variable.

Looks ridiculous isn't it?

Well, for SIMD the problem is the same.

[toc] | [prev] | [next] | [standalone]

#15578

On 08/01/12 10:48, jacob navia wrote:
> You could deduce that c must be of integer type isn't it?
> LET THE COMPILER DO THAT. Let's eliminate declarations for
> integer and let the compiler deduce from the program text
> the type of each variable.
>
> Looks ridiculous isn't it?
No, actually.  There are several programming languages which have 
strong, static typing, and yet have a complete system of type inference. 
  I believe ML is one such language.
Such a thing is not appropriate for C, because in C's model types are 
/promises/ one makes to the compiler.  This is C's optimisation 
paradigm: you promise the compiler you won't use a value as anything but 
an integer, by declaring it 'int'.  You promise the compiler you won't 
write through a pointer, by qualifying it 'const'.  You promise the 
compiler the pointer you gave it has no aliases, by qualifying it 
'restrict'.
If you want code that makes more use of hardware features like SIMD, 
don't add primitives that map to hardware instructions - add new ways of 
promising things to the compiler.  Then suggest them in comp.std.c and 
don't bash other compilers for not supporting them unless and until they 
get incorporated into the Standard.
-e
-- 
'sane', adj.: see 'unimaginative'
   on the web - http://jttlov.no-ip.org

[toc] | [prev] | [next] | [standalone]

#15590

On 08-Jan-12 04:48, jacob navia wrote:
> Le 07/01/12 14:39, Stephen Sprunk a écrit :
>> I don't understand what you think the problem is.
> 
> The problem, Stephen, is as follows:
> 
> gcc will vectorize this:
> 
> void doADD(double *L, double *R, double *result,size_t n)
> {
>      for(size_t i=0; i<n;i++) result[i]=L[i]+R[i];
> }
> 
> but will NOT vectorize this:
> 
> void doADD(double *L, double *R, double *result,size_t n)
> {
>      for(size_t i=0; i<n;i++) result[n-i]=L[n-i]+R[n-i];
> }
> 
> Why?

GCC doesn't understand that loop because it's not idiomatic.  When I
crank up the verbosity, it tells me that loop has a "complicated access
pattern".

> All this huge machinery for automatic vectorizing has never worked
> correctly for dozens of years since requires an incredible amount
> of program analysis.

It works correctly if you write idiomatic code, and the amount of work
required to recognize a handful of idioms is not "incredible".

> My proposition is:
> 
> Why make complicated something that you can do in a simple way?
> 
> Let the programmer declare the data that should be handled in an SIMD
> way.

GCC has vector data types for that, eg. v2df, if you want them.  IMHO,
it's simpler (and more portable) to just write code that can be
auto-vectorized according to whatever hardware is available on the
particular target of the day.

(I have a different perspective on this, perhaps, because my employer's
code base has to run on over a dozen different CPUs; portability trumps
maximum performance on one particular CPU.)

> If I write:
> 
>     c = (a+b)/2;
>     if (c&1) fn(1);
> 
> You could deduce that c must be of integer type isn't it?

Um, no.  It could be any arithmetic type.

> Well, for SIMD the problem is the same.

Not really.  A vector is just an array of some other type--it's not a
new type itself.

S

-- 
Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

[toc] | [prev] | [next] | [standalone]

#15595

Stephen Sprunk <stephen@sprunk.org> writes:
> On 08-Jan-12 04:48, jacob navia wrote:
[...]
>> If I write:
>> 
>>     c = (a+b)/2;
>>     if (c&1) fn(1);
>> 
>> You could deduce that c must be of integer type isn't it?
>
> Um, no.  It could be any arithmetic type.

"c&1" is valid only if c is of some integer type.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#15601

Keith Thompson wrote:
> 
> Stephen Sprunk <stephen@sprunk.org> writes:
> > On 08-Jan-12 04:48, jacob navia wrote:
> [...]
> >> If I write:
> >>
> >>     c = (a+b)/2;
> >>     if (c&1) fn(1);
> >>
> >> You could deduce that c must be of integer type isn't it?
> >
> > Um, no.  It could be any arithmetic type.
> 
> "c&1" is valid only if c is of some integer type.

Otherwise, it is a constraint violation.

I have a copy of one of the old C standards.

ISO/IEC 9899: 1990

6.3.10 Bitwise AND operator

Syntax
    AND-expression:
        equality-expression
        AND-expression & equality-expression

Constraints
   Each of the operands shall have integral type.

-- 
pete

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web