From: Christophe Rhodes
Subject: Vectorizing compilers
Date: 
Message-ID: <sqelofrrhp.fsf@cam.ac.uk>
Is there anything out there about vectorizing lisp compilers? 

At the moment, I'm playing with SBCL, and trying (at the moment as a
purely intellectual exercise, but maybe it'll be useful anyway ;-) to
think about compiling vector operations efficiently.

But it seems to me that there are significant difficulties with
compiling vector operations. As an example, consider possibly the
purest vector operation:

(map-into result #'+ vector1 vector2)

This can be vectorized by compilers, or at least SBCL, via a source
transformation, conceptually:

(map-into (simple-array fixnum) 
          (eql #'+) 
          (simple-array fixnum) 
          (simple-array-fixnum))
=>
(fixnum/vector+ result vector1 vector2)

Where fixnum/vector+ is some kind of internal function that knows how
to do vector additions efficiently. So far so good, but now consider

(map-into result #'(lambda (x) (* x 2)) vector1)

This would take a really smart compiler(tm) to optimize, I think
(well, obviously not this specific case, but in general...) and this
isn't nearly as complicated as

(loop for x across vector 
      for i upfrom 0 
      do (setf (aref result 0) (* x 2)))

or whatever that gets macroexpanded to...

So I'm asking several things, I think; firstly, has anyone seen how
`normal' lisp code can be vectorized? Secondly, are there any dialects
from which we could borrow ideas for better vectorization?

Cheers,

Christophe
-- 
Jesus College, Cambridge, CB5 8BL                           +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/                  (defun pling-dollar 
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)

From: Stefan Kain
Subject: Re: Vectorizing compilers
Date: 
Message-ID: <3BC0F563.70B6C609@freenet.de>
Hi,

Do you talk about vectorization in the sense of
a compiler emitting assembler statements for a
vector supercomputer?

Do you have a specific machine architecture in mind?
Something like Cray T90, Cray YMP or Fujitsu VPP Series?

I have read about a Lisp implementation that ran on Cray
Supercomputers, if I recall correctly.
But I don't know anything about its
capabilities to analyse the explicit/implicit loop-structure
of the program and to emit high performance vector-assembler-
commands for the inner loops.

I have only experience with FORTRAN (Yes, I confess my sins! :-))
and C (likewise) on Vector-Computers.
It was a marvelous development environment on Cray machines.
You would get surprisingly precise information why and why not your
code was vectorized properly.

Bye!

Christophe Rhodes wrote:
> 
> Is there anything out there about vectorizing lisp compilers?
> 
> At the moment, I'm playing with SBCL, and trying (at the moment as a
> purely intellectual exercise, but maybe it'll be useful anyway ;-) to
> think about compiling vector operations efficiently.
> 
> But it seems to me that there are significant difficulties with
> compiling vector operations. As an example, consider possibly the
> purest vector operation:
> 
> (map-into result #'+ vector1 vector2)
> 
> This can be vectorized by compilers, or at least SBCL, via a source
> transformation, conceptually:
> 
> (map-into (simple-array fixnum)
>           (eql #'+)
>           (simple-array fixnum)
>           (simple-array-fixnum))
> =>
> (fixnum/vector+ result vector1 vector2)
> 
> Where fixnum/vector+ is some kind of internal function that knows how
> to do vector additions efficiently. So far so good, but now consider
> 
> (map-into result #'(lambda (x) (* x 2)) vector1)
> 
> This would take a really smart compiler(tm) to optimize, I think
> (well, obviously not this specific case, but in general...) and this
> isn't nearly as complicated as
> 
> (loop for x across vector
>       for i upfrom 0
>       do (setf (aref result 0) (* x 2)))
> 
> or whatever that gets macroexpanded to...
> 
> So I'm asking several things, I think; firstly, has anyone seen how
> `normal' lisp code can be vectorized? Secondly, are there any dialects
> from which we could borrow ideas for better vectorization?
> 
> Cheers,
> 
> Christophe
> --
> Jesus College, Cambridge, CB5 8BL                           +44 1223 510 299
> http://www-jcsu.jesus.cam.ac.uk/~csr21/                  (defun pling-dollar
> (str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
> (set-dispatch-macro-character #\! #\$ #'pling-dollar)
From: Christophe Rhodes
Subject: Re: Vectorizing compilers
Date: 
Message-ID: <sqadz2sg3x.fsf@cam.ac.uk>
Stefan Kain <···········@freenet.de> writes:

> Do you talk about vectorization in the sense of
> a compiler emitting assembler statements for a
> vector supercomputer?

For instance, but...
 
> Do you have a specific machine architecture in mind?
> Something like Cray T90, Cray YMP or Fujitsu VPP Series?

... Even the lowly x86 (with MMX or SSE extensions) can do single
instruction multiple data -- four fixnum adds in one go...

I have worked on vectorizing computers, though I don't look back on
the time with much fondness...

Cheers,

Christophe
-- 
Jesus College, Cambridge, CB5 8BL                           +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/                  (defun pling-dollar 
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)
From: Christian Lynbech
Subject: Re: Vectorizing compilers
Date: 
Message-ID: <ofzo72cybg.fsf@chl.ted.dk.eu.ericsson.se>
>>>>> "Christophe" == Christophe Rhodes <·····@cam.ac.uk> writes:

Christophe> So I'm asking several things, I think; firstly, has anyone
Christophe> seen how `normal' lisp code can be vectorized? Secondly,
Christophe> are there any dialects from which we could borrow ideas
Christophe> for better vectorization?

I believe *Lisp could be a source of inspiration:

        http://www.elwoodcorp.com/alu/table/systems.htm#think

Allthough I know very little about compilers or vectorization, I think
you should concentrate (or at least start) on coming up with new
constructs that have a clear vectorization, rather than trying to
solve the general problem of discovering vectorization in generic
code, which sounds incredible hard to me.


------------------------+-----------------------------------------------------
Christian Lynbech       | Ericsson Telebit, Skanderborgvej 232, DK-8260 Viby J
Phone: +45 8938 5244    | email: ·················@ted.ericsson.dk
Fax:   +45 8938 5101    | web:   www.ericsson.com
------------------------+-----------------------------------------------------
Hit the philistines three times over the head with the Elisp reference manual.
                                        - ·······@hal.com (Michael A. Petonic)
From: Christophe Rhodes
Subject: Re: Vectorizing compilers
Date: 
Message-ID: <sq669pryn0.fsf@cam.ac.uk>
Christian Lynbech <·················@ted.ericsson.dk> writes:

> >>>>> "Christophe" == Christophe Rhodes <·····@cam.ac.uk> writes:
> 
> Christophe> So I'm asking several things, I think; firstly, has anyone
> Christophe> seen how `normal' lisp code can be vectorized? Secondly,
> Christophe> are there any dialects from which we could borrow ideas
> Christophe> for better vectorization?
> 
> I believe *Lisp could be a source of inspiration:
> 
>         http://www.elwoodcorp.com/alu/table/systems.htm#think

Thanks.

> Allthough I know very little about compilers or vectorization, I think
> you should concentrate (or at least start) on coming up with new
> constructs that have a clear vectorization, rather than trying to
> solve the general problem of discovering vectorization in generic
> code, which sounds incredible hard to me.

Well, yeah. But I can also enviseage something like this:

(defun foo ()
  (... stuff, including declarations 
   of a and b as specialized arrays ...)
  (locally
    (declare (vectorize (access a)
                        (read b)
                        (operation (+ b (* a 2)))))
    (map-into a (lambda (x y) (+ y (* x 2))) a b))
  (... more stuff ...))

which gets us the best of both worlds, if a Reasonably Smart Compiler
can work out what the declaration means; in other words, that normal
lisp code can run efficiently quasi-unaltered (approximately the same
as with compiler directives in comments for C and FORTRAN); I was
wondering whether anything of that sort had ever been tried.

Cheers,

Christophe
-- 
Jesus College, Cambridge, CB5 8BL                           +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/                  (defun pling-dollar 
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)
From: Christopher Stacy
Subject: Re: Vectorizing compilers
Date: 
Message-ID: <uelodje92.fsf@spacy.Boston.MA.US>
You should look at the Connection Machine *LISP,
and Dick Waters SERIES package.
From: JP Massar
Subject: Re: Vectorizing compilers
Date: 
Message-ID: <3bc33021.127277195@news>
On Tue, 9 Oct 2001 10:31:53 GMT, Christopher Stacy
<······@spacy.Boston.MA.US> wrote:

>You should look at the Connection Machine *LISP,
>and Dick Waters SERIES package.

There's now been two suggestions to look at *Lisp.

Unfortunately, I don't think there exists (or, for that matter, ever
existed) reference documentation for the *Lisp language online.

In fact, I know of no paper documentation for *Lisp that still exists,
although there's probably something somewhere in somebody's basement
or logical equivalent.

If anyone knows otherwise I'd be interested to hear of it.

(I was one of the developers of *Lisp at Thinking Machines
Corporation)

On a very abstract level, *Lisp dealt with 'vectorization' by defining
'parallel variables' (pvars) instead of using arrays.

If two parallel variables were used in a standard operation, they were
assumed to be of conforming 'shape' (pretty much equivalent to the 
dimensions of an array).

The original version of *Lisp used parallel equivalents of Lisp
operations to specify 'vectorization':  e.g., +!! the analog of +,
sqrt!! the analog of sqrt.

One of the final versions of the language for the CM5 allowed one to
get rid of the '!!' suffix, simply writing the symbol '+' instead of
'+!!'.

So a 'vectorized' floating point add could have been expressed simply 
as:

(defun vadd (x y)
  (declare (type (pvar single-float) x y))
  (+ x y)
  )


The *Lisp compiler for the CM2, written by Jeff Mincy, turned out
highly optimized code for complicated parallel arithmetic expressions,
in terms of the CM2 instruction set.
From: Erik Winkels
Subject: Re: Vectorizing compilers
Date: 
Message-ID: <877ku4fspf.fsf@xs4all.nl>
······@alum.mit.edu (JP Massar) writes:
>
> There's now been two suggestions to look at *Lisp.
> 
> Unfortunately, I don't think there exists (or, for that matter, ever
> existed) reference documentation for the *Lisp language online.
[...] 
> If anyone knows otherwise I'd be interested to hear of it.

Maybe these pointers are useful:

    http://www-2.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/impl/starlisp/0.html
    (the link to think.com doesn't seem to work)

    http://www-2.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/impl/starlisp/tutorial/0.html

    ftp://ftp.csl.sri.com/pub/users/gilham/starlisp.tar.gz

The URLs lead to a Starlisp simulator (which I have _not_ tried) and
includes a tutorial, a getting started text file and some example
code.


Regards,
Erik.
-- 
The last good thing written in C was Franz Schubert's Symphony number 9.
-- Erwin Dieterich
From: JP Massar
Subject: Re: Vectorizing compilers
Date: 
Message-ID: <3bc36dce.3108202@news>
On 09 Oct 2001 22:45:32 +0200, Erik Winkels <·······@xs4all.nl> wrote:
 
>> Unfortunately, I don't think there exists (or, for that matter, ever
>> existed) reference documentation for the *Lisp language online.
>[...] 
>> If anyone knows otherwise I'd be interested to hear of it.
>
>Maybe these pointers are useful:
>
>    http://www-2.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/impl/starlisp/0.html
>    (the link to think.com doesn't seem to work)

www.think.com now points you to something having to do with ORACLE.

>
>    http://www-2.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/impl/starlisp/tutorial/0.html

Wow.  That's quite an impressive piece of work.  Thanks for the
pointer. This was not produced by/at Thinking Machines.  I wasn't even
aware that it existed.

>
>    ftp://ftp.csl.sri.com/pub/users/gilham/starlisp.tar.gz
>
>The URLs lead to a Starlisp simulator (which I have _not_ tried) and
>includes a tutorial, a getting started text file and some example
>code.
>

The simulator README files refer to a 'Getting Started in *Lisp' file
which is not included in the archive.  This, along with the
documentation referred to in the README's was produced by TMC.  None
of this documentation exists online or (any more) in paper that I am
aware of.

The *Lisp simulator was written in CLtL I.
You would have had a hard time trying it using ANSI CL.

I recently beat it into submission enough to run under Allegro, Corman
and Lispworks under Windows.

 
From: Christian Lynbech
Subject: Re: Vectorizing compilers
Date: 
Message-ID: <ofzo6zc0kj.fsf@chl.ted.dk.eu.ericsson.se>
>>>>> "JP" == JP Massar <······@alum.mit.edu> writes:

JP> The *Lisp simulator was written in CLtL I.
JP> You would have had a hard time trying it using ANSI CL.

Isn't GCL still mostly CLtL I?

JP> I recently beat it into submission enough to run under Allegro, Corman
JP> and Lispworks under Windows.

Is there patches available somewhere?


------------------------+-----------------------------------------------------
Christian Lynbech       | Ericsson Telebit, Skanderborgvej 232, DK-8260 Viby J
Phone: +45 8938 5244    | email: ·················@ted.ericsson.dk
Fax:   +45 8938 5101    | web:   www.ericsson.com
------------------------+-----------------------------------------------------
Hit the philistines three times over the head with the Elisp reference manual.
                                        - ·······@hal.com (Michael A. Petonic)
From: JP Massar
Subject: Re: Vectorizing compilers
Date: 
Message-ID: <3bc497f6.79447988@news>
On Wed, 10 Oct 2001 11:21:32 +0200, Christian Lynbech
<·················@ted.ericsson.dk> wrote:

>>>>>> "JP" == JP Massar <······@alum.mit.edu> writes:
>
>JP> The *Lisp simulator was written in CLtL I.
>JP> You would have had a hard time trying it using ANSI CL.
>
>Isn't GCL still mostly CLtL I?
>
>JP> I recently beat it into submission enough to run under Allegro, Corman
>JP> and Lispworks under Windows.
>
>Is there patches available somewhere?
>
 
No.

But I'd be happy to send anyone what I have, and, once I get a little
to time clean it up, if some archivist wants to put this latest copy
at CMU or wherever I'd be happyu to send it to them.
From: JP Massar
Subject: Re: Vectorizing compilers
Date: 
Message-ID: <3bc49437.78488687@news>
On 09 Oct 2001 22:45:32 +0200, Erik Winkels <·······@xs4all.nl> wrote:

>······@alum.mit.edu (JP Massar) writes:
>>
>> There's now been two suggestions to look at *Lisp.
>> 
>> Unfortunately, I don't think there exists (or, for that matter, ever
>> existed) reference documentation for the *Lisp language online.
>[...] 
>> If anyone knows otherwise I'd be interested to hear of it.
>
>Maybe these pointers are useful:
>
>    http://www-2.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/impl/starlisp/0.html
>    (the link to think.com doesn't seem to work)
>
>    http://www-2.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/impl/starlisp/tutorial/0.html
>
>    ftp://ftp.csl.sri.com/pub/users/gilham/starlisp.tar.gz

A clarification/retraction:

This last URL does indeed point to an archive containing TMC's
official 'Getting Started in *Lisp' document.  So it is available
online.

The *Lisp Dictionary and the *Lisp Reference Manual, referenced in the
README's found in the *Lisp Simulator distribution, as well as other
Connection Machine related documentation referenced in the 'Getting
Started in *Lisp' document, are not AFAIK available online, nor do I
know of any available paper copies of them.

From the 'Getting Started' document, and from the tutorial referenced
in the 2nd URL (produced independently of TMC), and from the example
code included with the *Lisp Simulator, it would be possible to get a
good idea of how *Lisp worked.

>
>The URLs lead to a Starlisp simulator (which I have _not_ tried) and
>includes a tutorial, a getting started text file and some example
>code.
 
From: Rahul Jain
Subject: Re: Vectorizing compilers
Date: 
Message-ID: <87u1x7f6n5.fsf@photino.sid.rice.edu>
······@alum.mit.edu (JP Massar) writes:

> On Tue, 9 Oct 2001 10:31:53 GMT, Christopher Stacy
> <······@spacy.Boston.MA.US> wrote:
> Unfortunately, I don't think there exists (or, for that matter, ever
> existed) reference documentation for the *Lisp language online.

> In fact, I know of no paper documentation for *Lisp that still exists,
> although there's probably something somewhere in somebody's basement
> or logical equivalent.

> If anyone knows otherwise I'd be interested to hear of it.

While visiting Stanford a while ago, I was wandering around the CS
building and found a box of books free for the taking outside of JMC's
office. Unfortunately, he was occupied at the time, so I didn't get to
meet him, but I did grab a few books from that box. One of them was
the ACM SIGPLAN PPEALS 1988 proceedings, which contains papers on
Qlisp and something called Curare, which tries to discover parallelism
in lisp code. Also, on RPG's site, www.dreamsongs.org , he has a paper
discussing various means of adding language-level support for
concurrency in Lisp. It was a very interesting read, and I'd love to
see an implementation of the "brand" system for CMUCL (with the
obvious need to change the syntax presented in the paper a bit).

-- 
-> -/-                       - Rahul Jain -                       -\- <-
-> -\- http://linux.rice.edu/~rahul -=- ·················@usa.net -/- <-
-> -/- "I never could get the hang of Thursdays." - HHGTTG by DNA -\- <-
|--|--------|--------------|----|-------------|------|---------|-----|-|
   Version 11.423.999.220020101.23.50110101.042
   (c)1996-2000, All rights reserved. Disclaimer available upon request.
From: ·····@rcn.com
Subject: Re: Vectorizing compilers
Date: 
Message-ID: <y9mjau43.fsf@antarres.muniversal.com>
······@alum.mit.edu (JP Massar) writes:

> On Tue, 9 Oct 2001 10:31:53 GMT, Christopher Stacy
> <······@spacy.Boston.MA.US> wrote:
> 
> >You should look at the Connection Machine *LISP,
> >and Dick Waters SERIES package.
> 
> There's now been two suggestions to look at *Lisp.
> 
> (I was one of the developers of *Lisp at Thinking Machines
> Corporation)
> 
> On a very abstract level, *Lisp dealt with 'vectorization' by defining
> 'parallel variables' (pvars) instead of using arrays.
> 
> The *Lisp compiler for the CM2, written by Jeff Mincy, turned out
> highly optimized code for complicated parallel arithmetic expressions,
> in terms of the CM2 instruction set.

I *really *hope that the *lisp compiler sources are not available online.

-jeff