APL Machines 
Author Message
 APL Machines

Quote:
> There was an APL machine (by that name) produced by a corporation
> somewhere on the east coast of the US.  It was based on 68000
> processors,...

You're thinking of Analogic Corporation's 68000/CATscanner hybrid.  The
68000s were just control processors for the interpreter, most primitives
were microcoded on a 12-bit x 8 element Array Processor which had been
scavenged from one of Analogic's medical imaging instruments.  I believe
it's still on the market, although no plans exist to upgrade it.  The
interpreter and user interface are excellent.   The CAT scanner part is
a merciless number cruncher, so fast that you won't notice the effects
of long vector lengths until well past 1000 elements.  (i.e. it is several
hundred times faster than a 68000).  

There is a lesson in the APL Machine design, though.  The array processor
is not enough!  Despite the implementer's heavy use of the AP (e.g. linear
search on the AP always outperformed hash table lookup on the 68000),  the
68000 was a constant damper on program speed.  Memory management of small
vectors and scalars is not an especially parallelizable aspect of APL.
The uniprocessors responsible for serial sections of the interpreter, and
whatever features are used to synchronize the parallel sections are absolutely
critical elements in an APL supercomputer.

Quote:
> The "equals" primitive could be written in APL : ...[buggy code omitted]

Several interpreters have tried using "magic functions" to produce new
primitives from old.   It is never as easy as it looks, and it is NEVER fast -
it's not even tolerably slow.  

1) Your definition is wrong -- you must take absolute values before comparing
   the arguments.

2) Once the correct definition is written, you must make it work even when
   the intermediate terms exceed the number system's limits.

3) By now you've got a function that works for simple scalars. To call it
   you'll have to create two scalar APL objects, and a stack frame (that's
   invisible in the caller's ")SI").  You'll have to make a class of APL
   function capable of returning into a primitive algorithm at the correct
   place.  

This does not compare favorably with a single instruction for Tolerant Equals.

I'm not a great fan of #CT and its consequences, but it is STANDARD and heavily
relied upon, and it is one more language-specific hardware feature that APL
could really use.

Quote:
> "Dictionary APL"  NOT the "APL2" dialect.

Firstly I'd urge any APL designer to become deeply familiar with BOTH these
language definitions, and to really use BOTH systems.  The dictionary approach
("function rank") is really a wonderful perfection of the original APL array
processing ideas.  I suspect it is more efficient to implement, because it is
a little less powerful than the equivalent features in APL2.  In "Dictionary"
APL, operators are much more powerful.  If operators can really manipulate
the functions (e.g. pipelining them, carrying temporary results in registers,
etc.)  then I'd say the dictionary approach is best suited to today's
vector supercomputers.  

But "function rank" seems tied to homogeneous arrays (am I wrong here?)

There are real limits on programmers' ability to forsee what a function
expression will do.  In the APL2 approach, all the data decompositions are
explicitly written out, you can enter the subexpressions and watch what's
happening to your data.  You can also do all kinds of unorthodox decompositions
of your data, which stand no chance of being vectorizable.

And "vectorizing" is not the only hope for APL anyway!  Multiple instruction
Multiple Data parallel machines are growing in number and power, these don't
require that "one function" be in control, that "two arguments" be in memory
and that "one type" of result is expected.  I think the APL2 approach will
provide very rich ground for parallel machine designers.

Thanks in advance for any replies!


Univ. of Ill. Center for Supercomputing R&D



Wed, 17 Feb 1993 16:26:00 GMT  
 APL Machines

   There is a lesson in the APL Machine design, though.  The array
   processor is not enough!  . . . The uniprocessors responsible for
   serial sections of the interpreter, and whatever features are used
   to synchronize the parallel sections are absolutely critical
   elements in an APL supercomputer.

Anybody have any comments on how how these should be implemented (i.e.
deviations from commercial general-purpose CPU design)?  Has anyone
done any work to analyze the most common (and/or least used)
operations in the serial/scalar/small vector portions of the machine?

   > The "equals" primitive could be written in APL : ...[buggy code
   > omitted]

   Several interpreters have tried using "magic functions" to produce
   new primitives from old.  It is never as easy as it looks, and it
   is NEVER fast - it's not even tolerably slow.

The point was not to write APL in APL, but to write APL in a generic
vector language.  However, let me say that you are probably right:  it
is too easy to implement []CT at the hardware level (especially if
[]CT is limited to negative-integer-powers of two) to justify leaving
it out of a design.

   1) Your definition is wrong -- you must take absolute values before
      comparing the arguments.

I don't see that my definition was unacceptably wrong.  Deviation from
ideal is []CT squared, and for small values of []CT this is trivial.
(I am assuming that I am allowed to limit []CT to small values).  

   2) Once the correct definition is written, you must make it work
      even when the intermediate terms exceed the number system's
      limits.

Is good point.

   3) By now you've got a function that works for simple scalars. To
      call it you'll have to create two scalar APL objects, and a
      stack frame (that's invisible in the caller's ")SI").  You'll
      have to make a class of APL function capable of returning into a
      primitive algorithm at the correct place.

I'm not sure I'm not taking this level of complexity for granted in my
earlier posting.  I mean, if I do implement APL some vector language,
won't I have to deal with this complexity for most of the primitives?
Or, to rephrase:  what level of complexity should be in hardware, what
in software (feel free to elaborate on what you are expecting in
hardware).

   . . .

   The dictionary approach ("function rank") is really a wonderful
   perfection of the original APL array processing ideas.  . . . If
   operators can really manipulate the functions (e.g. pipelining
   them, carrying temporary results in registers, etc.) then I'd say
   the dictionary approach is best suited to today's vector
   supercomputers.

   But "function rank" seems tied to homogeneous arrays (am I wrong
   here?)

Function rank is tied to what the function can handle.  If the
primitive function can handle hetrogenous arrays, then function rank
is applicable to hetrogenous arrays.  Since we are talking about
APL machine architecture here, primitive means machine primitive, not
language primitive.  This leads into your idea of MIMD machines.

   There are real limits on programmers' ability to forsee what a
   function expression will do.  . . . You can also do all kinds of
   unorthodox decompositions of your data, which stand no chance of
   being vectorizable.

   And "vectorizing" is not the only hope for APL anyway!  Multiple
   instruction Multiple Data parallel machines are growing in number
   and power, these don't require that "one function" be in control,
   that "two arguments" be in memory and that "one type" of result is
   expected.

You are probably right.  I have been ignoring MIMD because I need to
think more about instruction propagation in this type of machine.
Know of any good references on the general subject?

   I think the APL2 approach will provide very rich ground for
   parallel machine designers.

Make that the APL approach, and I will be happy.  I do not consider
APL2 a complete design at this point.  (I do agree with including most
of APL2's functionality in a design, but there are a number of issues
I still have problems with.)

--
btw, does anyone know any good reference works on Heisenberg's
original approach to quantum physics?
--
Raul Rockwell                                      !

UUCP:       ...uunet!usc!raulmill                  !  55 mph = 82 nc
U.S.SNAIL:  721 E Windsor #4,  GLENDALE CA  91205  !



Wed, 17 Feb 1993 15:12:00 GMT  
 APL Machines

[most of excellent articlel by Greg Jaxon omitted]

Quote:
>> "Dictionary APL"  NOT the "APL2" dialect.

>Firstly I'd urge any APL designer to become deeply familiar with BOTH these
>language definitions, and to really use BOTH systems.  The dictionary approach
>("function rank") is really a wonderful perfection of the original APL array
>processing ideas.  I suspect it is more efficient to implement, because it is
>a little less powerful than the equivalent features in APL2.  In "Dictionary"
>APL, operators are much more powerful.  If operators can really manipulate
>the functions (e.g. pipelining them, carrying temporary results in registers,
>etc.)  then I'd say the dictionary approach is best suited to today's
>vector supercomputers.  

>But "function rank" seems tied to homogeneous arrays (am I wrong here?)

Wrong (just that last sentence, not the most insightful paragraph I couldn't
resist quoting first), but not surprisingly: Ken Iverson took a long time
to add heterogeneous arrays to the Dictionary.  The version published in
Quote Quad includes them, I think, though with little fanfare.

Moreover, we've included them in SAX (an APL interpreter and associated
programs for the Unix environment, produced by I.P. Sharp Palo Alto in
collaboration with STSC), which is to my knowledge the most complete implemente
d
subset of Dictionary APL.  (Unfortunately it's also kind of hard to get---
we try to concentrate on OEM sales, for overhead reasons).  But there's
nothing in Dictionary APL which conflicts with mixed arrays; they're just
not essential, as they are in APL2 (in Dictionary APL, it's largely a matter
of extending the domain of a few primitives like catenate ---formally, that
is, internally naturally there's a fair bit of work--- but in APL2 they're
a degenerate case of the enclosed universe, so they're essential).

Quote:
>There are real limits on programmers' ability to forsee what a function
>expression will do.  In the APL2 approach, all the data decompositions are
>explicitly written out, you can enter the subexpressions and watch what's
>happening to your data.  You can also do all kinds of unorthodox decomposition
s
>of your data, which stand no chance of being vectorizable.

I'm not entirely sure whether that paragraph is supposed to be part of
the text contrasting Dictionary APL and APL2.  If so, I should point out
that although the statement is quite true, Dictionary APL does include
the "box" and "open" primitives (similar to enclose and disclose).  We find
that it's frequently easier to write an algorithm usingn them in the first
place, while you're groping around trying to understand it; then later,
when you know what you're doing, it's often possible to dispense with box and
open and do something elegant with operators and flat arrays, instead.

[much more great stuff omitted]

Quote:
>Thanks in advance for any replies!


>Univ. of Ill. Center for Supercomputing R&D

You're most welcome---and it's very good to hear from you!  I'd lost track
of where you were...

                              /Roland Pesch

                               SAX Development Group
                               I.P. Sharp Associates
                               425 Sherman Ave., Suite 200
                               Palo Alto, CA   94306



Wed, 17 Feb 1993 21:32:00 GMT  
 APL Machines
The question of "hardware optimization" for APL machines
requires some consideration of how they will be used.  Are
we speaking here of single user or multi-user machines?
Are we looking at multiple user tasks, or single-workspace
machines with synchronous processing (single task/workspace)?
Is the machine going to run "APLish" code (data embedded
in arrays, large "logically parallel" operations); or will
it be used for "third generation language" processing style
as tends to predominate in COBOL, dBase, and Pascal application
(mixed data type stored as "records" or in structures accessed
through index operations)?

Choices in how it will be used - and who is going to be
footing the bill :-)  will largely determine design choices.
Exxon crunching seismic data will have a much different view
of the "optimal machine" than I will; probably by a few million
dollars.

I tend to discount the overheads in handling small (several
element to scalar) data structures, because it that is all
there is, then the application is unlikely to be large, and
there should be lots of spare machine cycles.  When the work
grows, if the application is well designed, so does the size
of your data entities.

Making APL hardware could involve implementing a lot of APL
as "machine instructions", but that really means microcode -
programs written in a constrained environment to squeeze as
much as possible out of very elementary operations.  Given the
raw hardware capabilities (single cycle instruction execution,
pipelineing, branch lookahead, etc.) the idea of building
what could be termed an ECISC machine (Exceedingly Complicated
Instruction Set Computing - and I do mean complicated, not
complex) flies in the face of current conventional wisdom
on performance.  Of course, this would not be the first time
that conventional wisdom could be wrong.  The structuring of
the execution environment by the APL interpreter would be an
advantage here - but it is also an advantage in generating
highly tuned object code as well - and perhaps an assembler
would be easier to work with than a micro-assembler.  As is
often the case, a middle ground may work well.  Perhaps a
more or less conventional CISC (or RISC?) machine with a few
well chosen enhancements to the instruction set to improve
fundamental APL operations would offer advantages without too
much sacrifice of development effort and system complexity.

The nature of the enhancements depend very much on what you
consider the key APL level operations to be.  My own list of
crucial favourites would include reshape, dyadic iota,
compress, reduce, and generalized inner products (or at least
and.equals).  Operations on Boolean arrays would also be very
high on the list, as would comparisons, especially those for
integer and character data.  Both base value and representation
are also important from a performance view in that they should
not be overly slow, but good system design can keep their use
far below that of the previously mentioned operations.  One
operation implicit in any APL that is crucial is the allocation
of storage for data entities.  Function calling, including the
creation of local symbols for user defined functions is another
thing that can happen very often in a well-structured system.

On the other hand, I don't really care that much how fast
the trig functions or domino run, nor that much how fast
exponentiation and the like are.  Someone who does more
"calculation" rather than "byte bashing" (commercial/logical
systems) would again have a different set of priorities.  If
I were heavily into graphics in a particular instance I might
care about floating point, but in most systems I have seen,
comparisons and data manipulation far outweigh calculation.

The most crucial item in a lot of cases is just workspace size.
An application that can get most or all of its data in a
workspace and have enough left over for transient storage for
intermediate results will be not only faster, but easier to
write and to maintain.  I have used workspaces from 32K to
several megabytes, and would not willingly go back to the
small ones.  Of course, my home system has a 750K workspace,
so most of my recent code has been very easy - I just don't
seem to have too much data in my life :-) ... of course the
data compression / storage reduction techniques learned in
those 32K workspaces still do a great job in maximizing the
capabilities of something more than twenty times larger.

Personally, I don't thing (single user machine) that you have
to provide multiple "control streams" or simultaneous processing
of user level tasks, but some parallelism in the execution of
array operations - or a high speed vector processing scheme -
could provide a major boost in performance.  In many operations
on conformal arrays, the (logical) structure of the data is
not important during the actual computation step.  If you could
generalize (should be easy) for scalar/array operations, then
you have a large part of the problem in hand.  Many other
operations could be decomposed into a number of vector, or
"quasi-vector" operations.  By quasi-vector, I mean that there
are a number of elements, regularly and repetitively spaced
through the machine's memory, with (temporarily) irrelevant
elements interspersed.

In real world terms, another major performance boost is a true
native APL file system - one that stores the components in their
internal representaion.  I did work with one system that only
stored what were essentially character representations of the
data (two dimensional? memory is mercifully weak on the details)
and a lot of time was spent converting to and from "file format".
This is probably too peripheral for your interests, as it should
be primarily a "software file server" issue, but it does touch
on (perhaps) some details of the hardware/software interface.

The idea of making APL the operating system, and giving it
complete and direct control over the system had a considerable
appeal.  The benefits could be enormous.

Speaking of Analogic, are they still around?  Do they still have
any APL products?  And, for that matter, is there a good APL for
Intel (Msdos) machines that does not cost the better part of a
thousand dollars?

Daniel Albano
Toronto, Ontario



Wed, 17 Feb 1993 15:17:00 GMT  
 APL Machines
Quick question (I hope).  Does anyone know of a reasonably systematic
(and fast) way of implementing gamma and beta function?
--


Wed, 17 Feb 1993 14:45:00 GMT  
 APL Machines

;> The question of "hardware optimization" for APL machines
;> requires some consideration of how they will be used.

Let's see.  Selecting concepts out of your original posting, I am
thinking of a multi-user machine, running "APLish code".  Let's say
something with the capacity of what currently costs around $50,000.
Price should drop for that capability by the time I am anywhere near
completion.

I haven't decided how to deal with resource locking on multi-tasking
conflicts.  (Not that I don't have ideas.  I just haven't convinced
myself that they are that good.)

The basic architechture I am trying to thrash out passes data objects
around with a checklist of what needs to happen to them.  There is a
bandwidth penalty here, but it allows for quite a bit of extensibility
(I hope).

;> . . .  I tend to discount the overheads in handling small (several
;> element to scalar) data structures, because if that is all there
;> is, then the application is unlikely to be large, and there should
;> be lots of spare machine cycles.  When the work grows, if the
;> application is well designed, so does the size of your data
;> entities.

I am not convinced that this is true for all applications.  Also there
generally needs to be several design iterations before an application
is "well designed".   It is true that MANY (probably MOST)
applications can be handled quite nicely using an APLish approach.  

;> Making APL hardware could involve implementing a lot of APL
;> as "machine instructions", but that really means microcode -
;> . . . [much deleted]

I think that you are talking about a conventional von neuman
architecture (cpu with bus leading to memory in which is stored
instructions and data).  I am being a little more "blue sky" than
that.  (I can almost afford to:  I'm a college student 8^)

;> The nature of the enhancements depend very much on what you
;> consider the key APL level operations to be.  My own list of
;> crucial favourites would include reshape, dyadic iota,
;> compress, reduce, and generalized inner products (or at least
;> and.equals).

A nice selection.

;> Operations on Boolean arrays would also be very high on the list,
;> as would comparisons, especially those for integer and character
;> data.

Given a fairly decent architecture these SHOULD be fast.  Look at the
occurance of blitters in recent personal computers.  (fast bit
manipulation does nice things to performance where applicable).

;> . . .  One operation implicit in any APL that is crucial is the
;> allocation of storage for data entities.  . . .

That is why I am trying for an architecture which is based on a
communication model.  There are penalties, but there should be big
advantages.  The question (a big one) is how to organize things.

;> On the other hand, I don't really care that much how fast
;> the trig functions or domino run, nor that much how fast
;> exponentiation and the like are.  . . .

I do.  Trancendental functions and domino do nice things to
applications which would other wise require massive looping.  Could I
get you to agree that base 2 logarithms should be fast?

;> The most crucial item in a lot of cases is just workspace size.

Considering the current state of technology, I have been assuming a
reasonably massive memory resource, though with varying levels of
caching/mass-storage.

;> Personally, I don't think (single user machine) that you have
;> to provide multiple "control streams" or simultaneous processing
;> of user level tasks, but some parallelism in the execution of
;> array operations - or a high speed vector processing scheme -
;> could provide a major boost in performance.

There are two kinds of parallelism I am considering.  (1) User-level
parallelism (coarse-grained) and (2) User-invisible (fine-grained).
(1) is more of a software issue, and (2) is more of a hardware issue.

;> In many operations on conformal arrays, the (logical) structure of
;> the data is not important during the actual computation step.

I don't quite follow you here.  What are you saying?

;> [description of practical vector operation: skipping over parts of
;> memory] . . .

;> In real world terms, another major performance boost is a true
;> native APL file system - one that stores the components in their
;> internal representation.  . . .  The idea of making APL the operating
;> system, and giving it complete and direct control over the system
;> had a considerable appeal.  The benefits could be enormous.

exactly!

I hope I am not being too foggy on details here.  If anyone feels I
should elaborate on any of the points here (assuming anyone is
interested) don't hesitate to tell me.

--
Raul
--



Wed, 17 Feb 1993 21:12:00 GMT  
 APL Machines

Quote:
> The dictionary approach ("function rank") is really a wonderful
> perfection of the original APL array processing ideas.

I missed some mechanism which allows specifying the rank of a
user-defined function.


Wed, 17 Feb 1993 15:07:00 GMT  
 
 [ 8 post ] 

 Relevant Pages 

1. APL machine (was: Re: APL CPU?)

2. apl machine architecture

3. APL Machines

4. Smallest APL machine

5. Is this the /smallest/ portable APL machine??

6. The Analogic APL Machine

7. Turing Machine in APL

8. APL for Java Virtual Machine?

9. I-APL, Vanguard APL, and APL.68000

10. OE Backup (move from machine to machine)

11. Stack machine to state machine

12. Lisp Based Machine Code (Simulators) [was Re: Lisp Machines]

 

 
Powered by phpBB® Forum Software