🚀 go-pugleaf

But having additional VR's means you can overlap load and store with the
computation. Having the size and number be adjustable means you can
balance the needed overlap and reuse with the ability to use long vectors.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

kirchner@uklira.informatik.uni-kl.de (Reinhard Kirchner) writes:
>On discussing various merrits of different vector machines we came about
>the issue of the register architectures. There are on one side the cray and
>convex with 8 vector registers a 64 or 128 words, and on the other side,
>
>The Fujitsu machines with their reconfigurable register file of 32 or
>64kb, which is 4k or 8k words, being grouped from 256 register a 16/32
>words to 8 registers a 512/1024 words.
>
>Now there is the question: is such a large register file useful at all ?

        I used an Alliant FX/80 while at UCLA.  It had eight vector
registers each length 32, which could hold integer or floating point
operands.

        One time critical routine in my program was multiple precision
modular multiplication.  The assembly language loop which multiplied one
vector of length <= 32 by another such vector had enough vector registers,
but there were insufficient vector registers for another loop which
multiplied two vectors of length <= 64.  These loops also faced a shortage
of scalar integer registers (Motorola 68020 has 8 address and 8 data
registers), requiring me to use a floating point register for one loop
control variables.  I guess that 16 or 32 vector registers will be
adequate for most applications.

>But how is this on vector machines ? The register creates a speedup only
>when it can hold an entire vector, which can be used again later. This
>requires a register long enough to do so. That means vectors of e.g. a
>length of 5000 can not be held anyway, every machine must load, process,
>and store it in pieces, and only a lot of memory bandwidth helps.

        It is important to strip mine and re-use vectors.  Consider
evaluating a polynomial at 5000 points:

        do i = 1, 5000
           pvalue = p(degree)                    ! Leading coefficient
           do j = degree-1, 0, -1
              pvalue = pvalue*x(i) + p(j)        ! Horner's rule
           end do
           value(i) = pvalue
        end do

On a machine with vector length at most 64, the code can be

        do ibeg = 1, 5000, 64
            iend = MIN(i + 63, 5000)
            lng = iend - ibeg + 1
            pvalue(1:lng) = p(degree)
            do j = degree-1, 0, -1
               pvalue(1:lng) = pvalue(1:lng)*x(ibeg:iend) + p(j)
            end do
            value(ibeg:iend) = pvalue(1:lng)
        end do

If pvalue(1:lng) and x(ibeg:iend) are assigned to vector registers across
the j loop, then the only memory reference in that loop is the load of
p(j).  Loops like this (where I operate several times on one temporary
vector, here pvalue) occurred in many parts of my cose.  Alas, the
compiler installed at UCLA did not perform these optimizations.
--
Peter L. Montgomery              Internet: pmontgom@math.orst.edu
Dept. of Mathematics, Oregon State Univ, Corvallis, OR 97331-4605 USA
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

kirchner@uklira.informatik.uni-kl.de (Reinhard Kirchner) writes:
> A register has an optimizing effect only when the value in it can be used
                                      ^^^^
> several times, at least twice, to avoid loading the value again from
> memory.  We all know that this is to a great extent possible on scalar
> machines.

Vectors and scalars are not really all that different.  Unless you have
overlap between the vectors they really behave just like large scalars.
My objection to the above is the statement that multiple use is the *only*
optimizing effect.  The other (also true of scalars) is when the value is
an intermediate.  A value which was just produced as the result of an
operation, which is needed as an operand almost immediately, and that's
the last you'll ever use it will not benefit from being written to memory
and read back in again.  Of course, if you can chain your functional units
together without using intermediaries at all, you won't need registers for
this purpose.
--
J. Giles
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

In article <93-01-195@comp.compilers> jlg@cochiti.lanl.gov (J. Giles) writes:
>Vectors and scalars are not really all that different.  Unless you have
>overlap between the vectors they really behave just like large scalars.

Good point.  If you program in assembler on a Cray, you also use registers
to pre-fetch memory operands before you need 'em.  In this regard, re-use
makes things even better, but even if you only do the equivalent of i++ in
C, you can win big if you don't run out of registers.... ie, load i n
clocks before it is needed, then s1 s1+1, then store it and don't use s1
for n clocks.  the result is a three clock i++, as fast as it can be done
on a Cray.  (n varies by cpu type.... and by memory type.  can at least
span the interval 14 clocks to 24 clocks and even up to 50 clocks on some
Cray-2 processors I have used.)

Same holds true for vectors.  You don't necessarily have to have high
reuse to win, just enough registers to keep data flowing (a) from memory
(b) to memory and (c) between functional units....
--
!Robert Hyatt                    Computer and Information Sciences   !
!hyatt@cis.uab.edu               University of Alabama at Birmingham !
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

kirchner@uklira.informatik.uni-kl.de (Reinhard Kirchner) writes:
> A register has an optimizing effect only when the value in it can be used
> several times, ...

jlg@cochiti.lanl.gov (J. Giles) writes:
>...  The other [optimization] (also true of scalars) is when the value is
>an intermediate.

Actually, there's a third effect: on machines with multiple functional
units a load or store to/from a register can be done at the same time as
other operations, so that the register can act like a small programmable
cache (complete with prefetching).
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

kirchner@uklira.informatik.uni-kl.de (Reinhard Kirchner) writes:
> A register has an optimizing effect only when the value in it can be used
> several times, ...

jlg@cochiti.lanl.gov (J. Giles) writes:
>[Another effect] (also true of scalars) is when the value is
>an intermediate.

Suppose one considers a not too outlandish problem, namely, that of
producing a vector of non-uniform random variables (exponential, normal,
gamma, beta, etc.).  It is possible to vectorize the reasonably efficient
acceptance-rejection and acceptance-replacement methods available, at
least if there is a reasonable use of control vectors, and a typical such
procedure will use about a half-dozen registers.  Many of these procedures
need division, and if division has to be stepped, it will add another
register or so.

If only one vector process can be done at a time, so far so good.  But
many vector machines can parallelize the vector processes, so we have a
cause for proliferation.  Even if only load and store can be parallelized
with vector computation, we can add a few more.  So it would not surprise
me if a few dozen would not be a good idea.
--
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054
hrubin@snap.stat.purdue.edu (Internet, bitnet)
{purdue,pur-ee}!snap.stat!hrubin(UUCP)
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.