[Caml-list] Pointers needed for optimization problem.

[Caml-list] Pointers needed for optimization problem.

[Pal-Kristian Engstad]

Hi,

I'm interested in solving a problem I have with automatically generating 
optimal (vector) floating point code. In other words, I want to code a caml 
program that transforms the input description into assembly instructions. For 
regular floating point operations, a good compiler should be able to optimize 
the code:
	
	r := A * x * x + B * x + C

into (if multiplication is more expensive than adds):

	t := A * x
	t := t + B
	t := t * x
	t := t + B
since
	r := (A * x + B) * x + C

Now, this is fairly trivial to do, but if you have an architecture with SIMD 
vector floating point registers and opcodes, a whole range of new interesting 
optimizations can be done. With vector registers, I mean registers that have 
up to 4 floating point values. For instance, a 4-vector times a 4-by-4 matrix 
operation can be coded as:

	acc.xyzw := mtxrow[0].xyzw * vec.x
	acc.xyzw += mtxrow[1].xyzw * vec.y
	acc.xyzw += mtxrow[2].xyzw * vec.z
	res.xyzw = acc.xyzw + mtxrow[3].xyzw * vec.w

Here, each line represent one assembly instruction.

So, what I am looking for is basically pointers to literature that deal with 
issues like these, and since OCaml is a great language for language 
transformations I thought someone on this list would be able to point me in 
the right direction. I _have_ been searching on the net, but I guess I don't 
know the right keywords to search on.

PKE.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Pointers needed for optimization problem.

[Xavier Leroy]

> Now, this is fairly trivial to do, but if you have an architecture
> with SIMD vector floating point registers and opcodes, a whole range
> of new interesting optimizations can be done.
> So, what I am looking for is basically pointers to literature that deal with 
> issues like these.

What you're after is traditionally called "instruction selection".
A Google search on "SIMD instruction selection" gives some relevant
papers.  (Follow the PDF links only :-)

Other sources of potential information:
- Recent proceedings for the conferences PLDI (Prog. Lang. Design
  and Implementation) and CC (Compiler Construction).
- The comp.compilers newsgroup.

Have fun,

- Xavier Leroy
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Pointers needed for optimization problem.

[Markus Mottl]

On Fri, 23 Aug 2002, Xavier Leroy wrote:
> > Now, this is fairly trivial to do, but if you have an architecture
> > with SIMD vector floating point registers and opcodes, a whole range
> > of new interesting optimizations can be done.
> > So, what I am looking for is basically pointers to literature that deal with 
> > issues like these.
> 
> What you're after is traditionally called "instruction selection".
> A Google search on "SIMD instruction selection" gives some relevant
> papers.  (Follow the PDF links only :-)
> 
> Other sources of potential information:

For optimal instruction selection, you might want to consider ocamlburg,
which you can find here:

  http://www.cminusminus.org/tools.html

I don't know how useful it generally is for exploiting super-scalar
features, but it may be in some cases.

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

RE: [Caml-list] Pointers needed for optimization problem.

[Gurr, David (MED, self)]

[-- Attachment #1: Type: text/plain, Size: 2574 bytes --]

>From the FFTW web page <<http://www.fftw.org/download.html>>:

fftwgel
fftwgel <<http://www.complang.tuwien.ac.at/skral/fftwgel.html>> is an
experimental version of fftw with support for the SIMD instructions of
the AMD K6-2 and K7 processors as well as the Intel Pentium IV, written
by our colleague Stefan Kral at the Vienna University of Technology. We
hope to incorporate a generalization of this work into a future version
of FFTW. 

fftwgel has ocaml code for generating SIMD code for x86 machines.  Other
key words
are SWAR and Atlas.  Plus the intel and amd web pages have lots of info.
-D

> -----Original Message-----
> From: Pal-Kristian Engstad [mailto:engstad@naughtydog.com]
> Sent: Wednesday, August 21, 2002 7:33 PM
> To: caml-list@inria.fr
> Subject: [Caml-list] Pointers needed for optimization problem.
> 
> 
> Hi,
> 
> I'm interested in solving a problem I have with automatically 
> generating 
> optimal (vector) floating point code. In other words, I want 
> to code a caml 
> program that transforms the input description into assembly 
> instructions. For 
> regular floating point operations, a good compiler should be 
> able to optimize 
> the code:
> 	
> 	r := A * x * x + B * x + C
> 
> into (if multiplication is more expensive than adds):
> 
> 	t := A * x
> 	t := t + B
> 	t := t * x
> 	t := t + B
> since
> 	r := (A * x + B) * x + C
> 
> Now, this is fairly trivial to do, but if you have an 
> architecture with SIMD 
> vector floating point registers and opcodes, a whole range of 
> new interesting 
> optimizations can be done. With vector registers, I mean 
> registers that have 
> up to 4 floating point values. For instance, a 4-vector times 
> a 4-by-4 matrix 
> operation can be coded as:
> 
> 	acc.xyzw := mtxrow[0].xyzw * vec.x
> 	acc.xyzw += mtxrow[1].xyzw * vec.y
> 	acc.xyzw += mtxrow[2].xyzw * vec.z
> 	res.xyzw = acc.xyzw + mtxrow[3].xyzw * vec.w
> 
> Here, each line represent one assembly instruction.
> 
> So, what I am looking for is basically pointers to literature 
> that deal with 
> issues like these, and since OCaml is a great language for language 
> transformations I thought someone on this list would be able 
> to point me in 
> the right direction. I _have_ been searching on the net, but 
> I guess I don't 
> know the right keywords to search on.
> 
> PKE.
> -------------------
> To unsubscribe, mail caml-list-request@inria.fr Archives: 
http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ:
http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners


[-- Attachment #2: Type: text/plain, Size: 152 bytes --]

[Filename: fftwgel.url, Content-Type: application/octet-stream]
This e-Mail had an attachment that was removed in order to meet GE Security guidelines.