**Preliminary Analysis of vcc C/C++ Compiler for VIRAM**

Sam Williams

samw@cs.berkeley.edu

# Abstract

VIRAM is a vector machine integrating a high performance scalar core, a
vector coprocessor, and DRAM, and vcc is the vectorizing C/C++ compiler
for this machine. In this paper, I present an analysis of the quality of
the compiler based on the currently available version (3.7.5). This
analysis focuses on the compiler's ability to recognize vectorizable
loops, to produce code which is significantly faster than scalar
versions of the loop and is comparable to hand crafter versions.
Whenever possible, I try to separate the performance of the compiler and
VIRAM ISA from micro-architecture details of VIRAM-1. To this end, I
used one of the benchmarks used by Cray to test their other compilers.
The results of this analysis will be used to guide work on the compiler
to ensure that when benchmarks of real world applications are performed
on VIRAM, the compiler is not the limiting factor.

**1 - Introduction**

**1.1 - VIRAM**

VIRAM, being a SIMD coprocessor, conceptually arrays a series of virtual
processors (vp) together. Operations are performed on vp's up to the
vector length (vl). There is of course a maximum vector length (mvl),
which actually depends on the virtual processor width (vpw). For VIRAM,
vpw can vary from 1 (half words) to 3 (double words). In addition to the
registers in the scalar core, VIRAM has a vector register file of 32
entries, each 2048-bits. So for a vpw of 1, this corresponds to a mvl of
128, and with a vpw of 3, mvl is 32. Additionally, based on the
micro-architecture of January of 2000, there is a separate scalar
register file of 32 64-bit entries which can be used directly by vector
instructions. More importantly, there is a flag register file of 32
entries. The number of bits of each entry varies just like the number of
elements varies in a vector register as vpw is changed. These provide a
pair of mask registers, as well as 9 exception registers and the
remaining registers can be used to hold additional masks. These
additional flag registers and the ability to set them through a large
number of instructions should facilitate vectorization of more loops.
Finally there is a control register file which holds values like vl,
mvl, vpw, shift, and index, as well as addressing registers for base,
increment, and stride.

The instructions are actually just an extension to the MIPS instruction
set for a second coprocessor. Instructions can be vector-vector (.vv),
scalar-vector (.sv), and vector-scalar (.vs). In addition to a set of
integer and floating-point arithmetic operations, there are instructions
to permute the elements in a vector, as well as flag-processing
instructions. These can make certain loops very easy to code, where
before they could be difficult or even impossible. The big question is
since they are so much more difficult to implement in hardware, will
they be worth implementing if the compiler never can decide when to use
them? Of course routines can be hand-coded to use them, but is this
sufficient? I strongly suggest that the reader familiarize himself with
the VIRAM ISA manual. Each instruction includes a C-like functional
description, as well as a simple text description.

Memory can be written to and from the scalar core, as well as the vector
unit. This is implemented with a weak consistency model. Thus a vsync
must be inserted whenever a RAW, WAR, WAW hazard might occur between the
scalar core and the vector unit. Thus the compiler will have to keep
track of all memory dependencies, and insert syncs where appropriate.
This can become very expensive when dealing with vector spills to the
stack. This is because potentially the entire vector unit would have to
be drained to satisfy the sync.

**1.2 - vcc**

The C/C++ compiler (vcc) is currently under development for use with
VIRAM by programmers at Cray, and is thus based on the vectorizing
compilers used for Cray's own supercomputers. It is functional, yet
incomplete. Some of the features which have not been implemented include
inlining, syncs, scheduler, etc... Nevertheless, the vectorizer is
functional and I was able to use it to gauge the compiler's ability to
vectorize loops on VIRAM. It is capable of performing the necessary data
dependence analysis and creating a vectorized version of the loop if it
thinks it will be faster. However there has been no previous attempt to
examine the speedup from vectorization and compare this new level of
performance to that which could be obtained by hand-coding the functions
in question.

**2 - Vector Optimizations**

There are several optimizations which the compiler is supposed to
implement. These include strip mining, loop distribution, loop
interchange, inlining, loop unrolling, and scheduling for the specific
processor. Strip mining is required since vector machines are restricted
by mvl, and thus need the compiler to break a vector operation into many
operations on vectors of size up to mvl. Loop distribution will break a
loop up into a vectorizable section and a non-vectorizable section, e.g.
partially vectorized. Loop interchange can help memory performance,
depending on how the array is laid out in memory. Inlining is essential
in C since because it is so easy to call a function to perform some
computation in the middle of the loop. Applying a vector transformation
with this form of inlining, a computation like: A(1:N)=f(B(1:N)), can be
vectorized. Finally, scheduling instructions so that they flow smoothly
through the machine is important, and the compiler with
micro-architectural knowledge in hand can perform this optimization. For
vector machines, it is even more important to apply concepts like code
motion and value analysis, since a cost effective vector machine will
have a finite number of functional units (much less than mvl), and thus
a vector instruction will take many cycles to complete (even though the
units might be pipelined).

**3 - Dongarra Loops**

The Dongarra loops is a set of 100 loops designed to test the compilers
ability to detect potentially vectorizable code. They are not
necessarily representative of real scientific code, nevertheless they do
examine various structures and access patterns which are likely to show
up in scientific code. These includes non-unit strides, multiple loops,
many instances of potential data dependencies, conditional execution,
etc... In addition to for-loops, goto's are included for complete
language syntax testing. The loops were originally written in FORTRAN,
but have since been rewritten in C. The loops are all single precision
floating point which is actually a much better test of hardware, since
although VIRAM ISA supports double precision floating-point arithmetic,
there will not be support in hardware.

**4 - Simulation Methodology**

First, in order to isolate the performance the compiler gains by fully
exploiting the ISA, I will assume the processor has sufficient memory
bandwidth and functional units so that no stalls will occur due to
hardware limitations. Otherwise micro-architecture details would cloud
the capabilities of the ISA and the compiler. I will assume, however,
that the core is a single-issue inorder processor, which it really is.
Since there will never be a stall to micro-architectural limitations
including lack of functional units in a lane, latency, etc..., I can
bound the performance increase of vectorized code by how many
instructions are actually executed.

I used the ISA simulator (vsim-isa) for this since it does not reflect
any micro-architectural details. The performance simulator (vsim-p) has
not been maintained for the last 6 months, leading to concerns that any
numbers from it would not necessarily reflect the current
micro-architecture. Additionally, there are no plans for it to be in the
next cvs release when the final micro-architectural changes are made.
Furthermore, I was able to use tracing abilities (-verify_trace), which
I used in debugging the simulators and RTL model to get a dynamic
program trace which I could then examine. A simple write of a unique
value to a locator variable allowed me to easily automate the ability to
pick out the loops of interest from the several million instruction
trace. Compiling with vectorization turned off, and the again with it
on, allowed me to determine the speedup that vectorization could buy. I
also wrote a series of scripts to analyze things like filled branch
slots, typical vector length, etc....

The actual compiler command lines I used were:

\> vcc -hvector3 -hscalar3 -hinline3

-htask3 \*.c -o dlv

\> vcc -hvector0 -hscalar3 -hinline3

-htask3 \*.c -o dls

Here there should be (assuming they have been implemented) full scalar
optimizations, imlining, etc... There is an additional optimization
switch for the aggressiveness of the vectorizer.

-h vector \[n\]

0 no vectorization

1 conservative -- no search loops or

reductions

2 moderate -- search loops and

reductions

3 aggressive -- restructuring, alias

information is used

The second two options are meaningless, since the compiler currently
does not implement these options, which could limit the performance on
vectorized code in which functions are called inside a loop. The first
switches between vectorized and not.

**5 - Performance**

**5.1 -- Vectorization Speedup**

First I examined the ability of the compiler to recognize vectorizable
loops. Each test loop function is actually three structures: one loop to
initialize the arrays so a checksum can be computed, the main loop to
test the compiler, which is typically just adds or copies, and a final
one to ensure the checksum is correct. The final one is actually a
reduction, and as noted before, reductions had not been implemented in
the version I was using, so all of these loops required a pragma to
prevent any attempt at vectorization.

I examined the small-scale speedup by looking only at the loop structure
in question, and not the entire function, which would include overhead,
initialization, and checksum computations. Furthermore, in scientific
computing it is quite likely that many structures will have very large
arrays which will amortize the relatively small overhead of function
entry and exit. For speed of the simulation, I kept array sizes
relatively small. Even with small loops, the overall speedup for the
entire set of loops, including all overhead and checksum computations,
was a factor of 2. As seen from the following tables and graphs, many
loop structures weren't vectorized at all. A speedup of approximately 1
means that the loop was probably not run in vector mode. There could
have been a little extra vector code run before the main part of the
loop, which would tend to add a little offset to the scalar mode base.

  ---------- ------------- ---------- ------------- ---------- ------------- ---------- ------------- ---------- -------------
  **Loop**   **Speedup**   **Loop**   **Speedup**   **Loop**   **Speedup**   **Loop**   **Speedup**   **Loop**   **Speedup**

  1          15.0          21         16.7          41         10.4          61         11.0          81         6.3

  2          17.6          22         14.3          42         10.3          62         15.0          82         8.0

  3          17.9          23         14.4          43         12.4          63         14.2          83         1.0

  4          1.0           24         16.3          44         12.7          64         14.8          84         6.5

  5          0.8           25         12.0          45         20.7          65         1.0           85         7.1

  6          18.6          26         15.1          46         12.0          66         9.3           86         8.9

  7          1.1           27         21.7          47         1.0           67         1.0           87         1.0

  8          14.4          28         0.8           48         15.0          68         0.9           88         17.0

  9          8.2           29         1.0           49         1.0           69         1.0           89         17.9

  10         1.0           30         1.0           50         19.0          70         1.0           90         1.0

  11         19.4          31         1.4           51         10.0          71         1.0           91         1.0

  12         12.8          32         1.0           52         7.6           72         21.1          92         17.5

  13         1.0           33         18.0          53         22.0          73         22.4          93         9.3

  14         15.1          34         1.6           54         21.1          74         1.0           94         23.4

  15         15.4          35         12.1          55         1.0           75         1.0           95         22.1

  16         7.2           36         1.0           56         11.6          76         1.0           96         26.9

  17         1.0           37         1.7           57         11.5          77         1.0           97         12.8

  18         17.7          38         10.4          58         1.0           78         6.7           98         6.6

  19         10.1          39         22.9          59         12.0          79         13.3          99         2.6

  20         8.9           40         20.6          60         12.0          80         6.2           100        31.8
  ---------- ------------- ---------- ------------- ---------- ------------- ---------- ------------- ---------- -------------

Table 1 -- Speedup for Dongarra Loops

The theoretical speedup will be at most 64 since with a vpw of 2, there
are 64 elements per vector register. Thus any single vector instruction
can perform at most 64 operations. Furthermore, the ISA provides
additional capabilities for removing loop overhead, like
auto-incrementing a base address register. This could provide a speedup
much greater than 64. It is clear from the table that even at the best,
the compiler was only able to get a speedup of 32, and the average
speedup was slightly over 10. Nevertheless, vcc and the VIRAM ISA allows
for many more of the loops to be vectorized than the previous Cray
compilers for their vector machines.

The following graph is Table 1 sorted by speedup. It is clear from the
graph that once a loop could be vectorized, the speedup was dramatic.
Still, a significant percentage of the loops would not vectorize at all,
and thus were run in scalar mode. The question is why some loops did not
vectorize, and why, considering the ISA specifies that single precision
elements allows for a mvl of 64, the speedup was not more dramatic?
Table 2 provides the reasons (if given) by the compiler for not
vectorizing a loop. Typically it was due to a data dependence, but there
are a few more interesting cases.

![](media/image1.wmf)

Figure 1 - Loops sorted by speedup

  ---- ------------------------------- ---- -------------------------------
  5    Recurrence, but used a safe VL  70   Compiler omitted it both for
                                            scalar and vector

  28   Partially vectorized            71   Compiler omitted it both for
                                            scalar and vector

  68   Recurrence                      74   Was vectorized

  58   Conditionally vectorized        75   Was vectorized

  67   Recurrence                      76   Was vectorized

  69   Recurrence                      77   Recurrence

  10   Recurrence                      83   Recurrence

  13   Recurrence                      90   Function call

  17   Removed from test suite         91   Function call

  29   Recurrence                      87   pragma not to vectorize (no
                                            vector sin() or cos() functions
                                            yet)

  32   Recurrence                      4    Recurrence

  36   Recurrence                      30   Recurrence

  47   Recurrence                      7    Recurrence

  49   Recurrence                      31   Recurrence / unspecified /
                                            vectorized

  55   Recurrence                      34   Partially

  65   Recurrence (really a reduction) 37   Partially
  ---- ------------------------------- ---- -------------------------------

Table 2 -- Reasons Given by the compiler for not vectorizing

Although Dongarra loop #74 was vectorized, it does not run any faster
than the scalar version. It should run very fast since it is just a
vector add, however there is a bug in the code (in the benchmark!) for
this loop. The same applies to 75, 76, and 77. I am surprised this has
gone unnoticed. It is somewhat subtle, but....

int i=0;

float t, cksum=0.0;

for (i=0; i\<n; i++)

> b\[i\]=c\[i\]=1.;

BEFORE

L140: ;

if(i\>=n)goto L141;

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

i = i + 1;

goto L140;

L141: ;

AFTER(74)

The first for-loop will change the value of i, so even though it was
initialized to 0, it is n by the time the main loop starts. Thus,
although the main loop was vectorized, it is never executed, which is
why it is no faster than the scalar version (which does not run either).
It is no surprise that after correcting this, the speedups were:

074 17.86879

075 17.58333

076 10.15373

077 01.06749 (no surprise since

> the recurrence
>
> prevented
>
> vectorization)

This increased the average speedup to 10.4.

The compiler cannot currently inline a function, so any loop which calls
a function will not be vectorized. The libraries, when done, will
contain vectorized versions of the math functions, thus allowing
functions which call sin() or cos(), etc... to be vectorized, however at
this time they are not ready. This is why Dongarra loop #87 required a
pragma.

Some structures, like those in Dongarra #70 and #71, were completely
skipped by the compiler, and no warning or information was given. It
turns out that it completely eliminated the loops since the results they
produced were never used.

for (i=0; i\<n; i++) {

if(a\[i\]==0) j = i;

}

Since j was created inside the function and never used, the compiler
removed the loop completely, which might not have been the intention.

A couple of loops were conditionally vectorized, which means that at
compile time it could not be determined if the loop could be run in
vectorized form, so the compiler generates both vector and scalar
versions of the loop, as well as a runtime check, which will determine
which is appropriate. For one of these loops, the runtime check is
meaningless, since it can never happen (if n\<0 do nothing, else if n\<0
run in vector mode), yet the loop could be run in vector form. I will
discuss this one later.

For some loops, either completely or partially vectorized, the code was
so complex that it actually ran slower than the scalar version.

**5.3 - ISA Utilization**

This benchmark is primarily designed to test the compilers ability to
recognize vectorizable structures, so not every instruction is
applicable to the subset of computations performed. Nevertheless in some
cases, it would have been more appropriate to use a single more powerful
instruction than many smaller ones. Very few of the vector processing
instructions, without a doubt the most complicated in the ISA, were ever
used. Instructions like vins, vcompress, vexpand, vhalfup/dn were never
used, although the butterfly transformations vhalfup/dn are more
understandable since they were put in the ISA to facilitate FFTs.
However, the expand and compress instructions can be very useful, and in
many cases they can make certain loops very easy to implement when hand
coding them. Since it is a floating-point test, it was no surprise that
the integer instructions like saturating arithmetic and multiply-adds
were never used. However, I would have expected more than just 4 of the
16 floating-point compare predicates would have been used. Most loads
and stores were used, although as I will show later, sometimes
unnecessarily.

Given that the average vector length (after saturations) was 42, I
expected a better average speedup. However, upon closer examination it
seems that for many loops, there was a great deal of overhead, which if
they had been hand coded, would not be there.

Table 3 provides the vector instructions used by the entire program
sorted by their usage counts. The move to and from control registers in
coprocessor 2 (ctc2 / cfc2) are used far more than expected. These are
used to set registers like vl, vpw, vindex, as well as base, increment,
and stride. There is really no need to continually set vl to the same
value, nor given the fact that vector loads and stores support
auto-increment, is there typically any need to continually set the base
or increment registers. Most computations are adds, so I was expecting a
large number of vadd.vv instructions. It also appears that the compiler
is using the vector scalar registers as temporaries for the vector
control registers (vmcts / vmstc).

  ---------------------- ------------ ---------------------- ------------
  **Instruction**        **Num**      **Instruction**        **Num**

  ctc2                   21467        vfand.vv               72

  cfc2                   8229         vfnor.vv               72

  vst                    4253         vstxo                  57

  vsatvl                 3306         vdiv.vv                53

  vadd.vv                2579         viota                  53

  vfor.vv                2540         vcmp.neq.sv            46

  vld                    2456         vsub.sv                44

  mtc2                   1942         vmullo.sv              36

  vmerge.vs              1759         vcmp.lt.vv             36

  vmstc                  1651         vsqrt                  32

  vhalf                  1311         vcmp.le.sv             32

  vmcts                  1022         vsub.vv                23

  vcvt                   636          vabs                   16

  vlds                   522          vdiv.sv                12

  vfset                  513          vdiv.vs                8

  vfclr                  512          vcmp.le.vv             8

  vmerge.vv              506          vffl1                  8

  vmul.vv                378          vsub.vs                6

  vfpop                  266          vcmp.eq.sv             6

  vext.u.sv              216          vcmp.lt.vs             6

  vadd.sv                126          vext.sv                3

  vmul.sv                118          vfff1                  2

  vor.vv                 103          vfld                   2

  vldx                   101          vfst                   2

  vcmp.lt.sv             88           vsll.sv                1

  vsll.vs                84           vsra.vs                1

  vsts                   83                                  
  ---------------------- ------------ ---------------------- ------------

Table 3 -- Instruction Usage

As seen from the table, the number of control register accesses and
vector length saturations is an order of magnitude more than
computations, and five times more than memory accesses. Although vhalf's
are used to some extent, other more complex vector operations, like
extracts, are hardly ever used.

**5.4 - Quality of codegen**

In this section, I will examine in detail the code generated by the
compiler and look for major trends which could be improved upon. I will
examine only the relatively simple cases based on the logic that if the
compiler cannot generate efficient code for these there is no hope that
it will for the really complex loops.

First, I looked at:

for (i=0; i\< n; i++)

a\[i\]=1.;

which is, or is similar to, the initialize statements found in every
loop. At a high level this is just a memory fill, which can be done with
a series of vector stores. Since the VIRAM ISA supports auto-increment,
this can be done extremely efficiently. The following is the code
produced by the compiler:

*\# vpw = 2*

*\# vl = 64*

*\# \$2 and vbase0 contain the base*

*\# address of array a*

*\# \$16 is n*

*\# \$14 initially contains n*

*\# \$13 is the saturated*

*\# vector length*

\$L6:

li.s \$f0,1.00000e+00

mfc1 \$4,\$f0

mtc2 \$4,\$vs1

ctc2 \$13,vl

vmerge.vs \$vr1,\$vr1,\$vs1

li \$3,4

mul \$2,\$3,\$13

ctc2 \$2,vinc1

vst.w \$vr1,vbase0,vinc1

subu \$14,\$14,\$13

ctc2 \$14,vl

vsatvl

cfc2 \$13,vl

bgt \$14,\$0,\$L6

We can see that this is a prime candidate for optimization, yet no
optimization was performed. The first 3 instructions are essentially a
lwc2 instruction (which unfortunately neither the compiler nor the
simulators yet support). Regardless, these can be moved outside of the
loop. The next instruction sets the strip-mined vector length, and
following that it fills elements 0..vl-1 of \$vr1 with \$vs1. The merge
takes time, and could also be moved outside of the loop. The next 3
instructions will recompute the auto-increment for the store, which is
unnecessary. It stores, and auto-increments vbase0. We then decrement
the number of elements by the strip-mined vector length, and compute a
new strip-mined vector length.

In general I would propose a different method for strip-mining loops of
this nature, which should remove some of the unnecessary loop overhead.
Very simply put:

*1. Compute the strip-mined*

*vector length (vl~sm~), this*

*should be mvl*

*2. Compute the number of strip-*

*mined iterations (n / vl~sm~)*

*3. Execute the loops*

*4. Compute the residual vector*

*length (vl~res~), just (n % vl~sm~)*

*5. Execute the residual loop*

Applying these rules, some code motion, and the same initial registers:

*\# vpw = 2*

*\# vl = 64*

*\# vbase0 contains the base*

*\# address of array a*

*\# \$16 is n*

*\# \$13 is the saturated*

*\# vector length (mvl if n\>mvl)*

*\# load \$vs1 with 1.0, will*

*\# be replaced by a lwc2*

*.*

*.*

*.*

li.s \$f0,1.000000e+00

mfc1 \$4,\$f0

mtc2 \$4,\$vs1

*\# compute number of*

*\# iterations, since we*

*\# know vpw,mvl*

*\# we could just do a srl by*

*\# 6, and an andi with 0x3f*

*\# (strength reductions)*

cfc2 \$17,mvl

div \$14,\$16,\$17

mod \$15,\$16,\$17

*\# compute vinc (applied*

*\# code motion), and could*

*\# also be*

*\# replaced by a shift by 2*

*\# (strength reduction)*

li \$3,4

mul \$2,\$3,\$13

ctc2 \$2,vinc1

*\# don't execute if n\<MVL*

ble \$14,\$0,\$LRES

nop

li \$17,1

*\# more code motion*

vmerge.vs \$vr1,\$vr1,\$vs1

\$L6_SM:

vst.w \$vr1,vbase0,vinc1

subu \$14,\$14,\$17

bgt \$14,\$0,\$LSM

nop

\$L6_RES:

ctc2 \$15,vl

vst.w \$vr1,vbase0,vinc1

We can see that this loop will execute several times faster (ignoring
hardware specific limitations, e.g. ld/st unit capabilities). With the
current implementation of the VIRAM-1 micro-architecture, the store will
take 8 cycles for all 64 elements, so the loop can only be executed at
half the speed. However, this is still twice as fast as the original.

Next let us look at the main loop from Dongarra loop #3 (similarly just
replicate the first element).

for (i=1; i\<n; i++){

a\[i\] = a\[0\];

}

This is essentially the same loop as before, except instead of
replicating some constant, the first element is replicated throughout
the vector.

The loop was compiled into:

*\# vpw = 2*

*\# vl = 64*

*\# vbase0 is address of a\[1\]*

*\# \$14 initially contains*

*\# n-1*

*\# \$13 is the saturated*

*\# vector length*

\$L77:

ctc2 \$13,vl

vmerge.vs \$vr1,\$vr1,\$vs1

li \$6,4

mul \$5,\$6,\$13

cfc2 \$4,vbase0

addu \$3,\$4,\$5

vst.w \$vr1,vbase0,vinc0

move \$2,\$3

ctc2 \$2,vbase0

subu \$14,\$14,\$13

ctc2 \$14,vl

vsatvl

cfc2 \$13,vl

bgt \$14,\$0,\$L77

Clearly this loop doesn't require vbase0 to be continually recomputed,
since auto-increment could be used. And as before, the loop could be
restructured, and code could be moved out of the loop.

Next, Dongarra loop #20 has an important access pattern.

for (i=0; i\<n; i++) {

a\[i\*n\] = a\[i\*n\] + b\[i\];

}

Here, as expected, the compiler takes advantage of strided loads and
produces:

\$L726:

move \$14,\$17

\$L709:

ctc2 \$14,vl

vld.u.w \$vr2,vbase2,vinc0

vlds.u.w \$vr3,vbase1,vstride0,

vinc0

mul \$7,\$14,\$13

li \$6,4

.

.

.

ctc2 \$7,vinc1

mul \$5,\$6,\$14

vadd.s.vv \$vr1,\$vr2,\$vr3

cfc2 \$4,vbase2

addu \$3,\$4,\$5

move \$2,\$3

ctc2 \$2,vbase2

subu \$15,\$15,\$14

ctc2 \$15,vl

vsatvl

cfc2 \$17,vl

ctc2 \$14,vl

vsts.w \$vr1, vbase1, vstride0,

vinc1

bgt \$15,\$0,\$L726

From before, vbase2 does not need to be recomputed since something like
vinc2 could be used instead. As before, vinc1 does not need to be
recomputed. For simple loops like this, all that is needed in the
strip-mined iterations is a load/compute/store. The load and store can
be enabled with auto-increment to avoid any unnecessary computations.

Although superficially similar, Dongarra loop #58 was conditionally
vectorized.

for (i=0; i\<n; i++) {

a\[i\] = a\[0\];

}

This loop is virtually identical to loop #3, but the different bounds
caused problems with the vectorizer, and although it was conditionally
vectorized, it is forced to always run the scalar version. This is
because the runtime condition to run the vector version was n\<0, but
there was already a branch if n\<0 to bypass the loop. But let us
examine the vector version that was generated.

\$L2108:

dla \$8,a

l.s \$f0,0(\$8)

mfc1 \$7,\$f0

mtc2 \$7,\$vs1

ctc2 \$13,vl

vmerge.vs \$vr1,\$vr1,\$vs1

li \$6,4

mul \$5,\$6,\$13

cfc2 \$4,vbase0

addu \$3,\$4,\$5

vst.w \$vr1,vbase0,vinc0

move \$2,\$3

ctc2 \$2,vbase0

subu \$14,\$14,\$13

ctc2 \$14,vl

vsatvl

cfc2 \$13,vl

bgt \$14,\$0,\$L2108

Once again, the load of a\[0\] could be done in a single lwc2
instruction, and both it and the vmerge could be moved outside of the
loop. There is no need to continually recompute vbase0 and use it in the
computations, since vinc1 could be used instead. And once again the loop
could be broken into a strip-mined version (using mvl) and another using
residual array length. So the strip-mined part is just a store / sub /
branch.

With the power of the flag and vector processing instructions, Dongarra
loop #72 should be easy to vectorize efficiently.

for (i=0; i\<n; i++) {

if(a\[i\]\>0){

b\[j\] = a\[i\];

j++;

}

}

This loop is more complicated to compile since b\[\] is not written at
the same rate that a\[\] is read.

\# \$13 = a\[\]

\# \$16 = n

\# \$18 = saturated vl

\$L2615:

ctc2 \$13,vbase0

ctc2 \$18,vl

vld.u.w \$vr1,vbase0,vinc0

li \$2,4

vcmp.lt.sv \$vf2,\$vs0,\$vr1

mul \$19,\$2,\$18

vfpop \$vs1,\$vf2

vmstc vcat,\$vs1

cfc2 \$20,vcat

beq \$20,\$0,\$L2619

ctc2 \$18,vl

viota \$vr3,\$vf2

li \$9,2

mtc2 \$9,\$vs1

ctc2 \$20,vl

vsll.vs \$vr2,\$vr3,\$vs1

dla \$7,a

li \$5,4

mul \$8,\$5,\$14

addu \$6,\$7,\$8

ctc2 \$6,vbase1

vldx.u.w \$vr1,\$vr2,vbase1

dla \$3,b

mul \$4,\$5,\$17

addu \$2,\$3,\$4

ctc2 \$2,vbase0

addu \$17,\$17,\$20

vst.w \$vr1,vbase0,vinc0

\$L2619:

addu \$2,\$13,\$19

subu \$15,\$15,\$18

move \$13,\$2

addu \$14,\$18,\$14

ctc2 \$15,vl

vsatvl

cfc2 \$18,vl

bgt \$15,\$0,\$L2615

Basically the first section loads a strip, compares to 0 to generate a
mask, gets the number of 1's in the mask, if nonzero, continues,
generates an index from the mask and stores it in \$vr3, then \$vr2,
loads the values of a\[\] corresponding to those with an indexed load,
and stores them into b\[\]. Once again, a vinc could be used to avoid
recalculating base addresses, although unlike a\[\], the increment for
b\[\] is not fixed.

Furthermore, the vcompress instruction could be used here. (vcompress
takes a register and a mask and compresses unmasked elements). This way,
the typically slow indexed load could be avoided, as well as the
computations of the indexing vector register, i.e.

*Load strip from a\[\],*

*auto-increment vbase0*

*Compare to 0, store result in vf2*

*Compress strip using vf2*

*vinc2 = 4\*vfpop*

*store strip to b\[\], using vbase1,*

*and vinc2*

This could also reduce memory bandwidth usage by as much as 33%, since
the indexed load is unnecessary.

Next is Dongarra loop #78, which is essentially a vector copy with an
offset.

for (i=0; i\<n; i++) {

xx\[i\] = yy\[i+1\];

}

This should be no more complicated to vectorize than a simple vector
copy.

\$L2847:

move \$13,\$15

cfc2 \$12,vbase3

ctc2 \$12,vbase1

\$L2832:

li \$6,4

mul \$5,\$6,\$13

ctc2 \$5,vinc1

ctc2 \$13,vl

vld.u.w \$vr1,vbase2,vinc1

cfc2 \$4,vbase1

addu \$3,\$4,\$5

move \$2,\$3

ctc2 \$2,vbase3

subu \$14,\$14,\$13

ctc2 \$14,vl

vsatvl

cfc2 \$15,vl

ctc2 \$13,vl

vst.w \$vr1,vbase1,vinc0

bgt \$14,\$0,\$L2847

Once again, each time vinc1 is recalculated, and no increment is used
for vbase1. Here initially, vbase1 could be assigned xx\[0\], and vbase2
could be assigned yy\[1\]. Then both instructions could use vinc1, which
could be calculated outside of the loop, to auto-increment their bases,
e.g.

vld.u.w \$vr1,vbase2,vinc1

vst.w \$vr1,vbase1,vinc1

Finally, let us look at Dongarra loop #100.

for (i=0; i\<n; i++) {

a\[i\] = b\[i\] + c\[i/2\];

}

Although this loop, when vectorized, is 30 times faster than the scalar
version, it could be considerably better.

\$L3701:

move \$14,\$17

cfc2 \$12,vbase3

ctc2 \$12,vbase1

\$L3684:

li \$11,2

mtc2 \$11,\$vs3

ctc2 \$14,vl

vdiv.vs \$vr6,\$vr1,\$vs3

li \$9,4

mtc2 \$9,\$vs2

vmullo.sv \$vr5,\$vs2,\$vr6

dla \$10,c

ctc2 \$10,vbase4

vldx.u.w \$vr3,\$vr5,vbase4

mtc2 \$14,\$vs1

ctc2 \$13,vl

vadd.sv \$vr1,\$vs1,\$vr1

ctc2 \$14,vl

vld.u.w \$vr4,vbase2,vinc0

mul \$7,\$9,\$14

vadd.s.vv \$vr2,\$vr3,\$vr4

cfc2 \$8,vbase2

addu \$5,\$8,\$7

cfc2 \$6,vbase1

addu \$4,\$6,\$7

move \$3,\$5

move \$2,\$4

ctc2 \$3,vbase2

subu \$15,\$15,\$14

ctc2 \$2,vbase3

ctc2 \$15,vl

vsatvl

cfc2 \$17,vl

ctc2 \$14,vl

vst.w \$vr2,vbase1,vinc0

bgt \$15,\$0,\$L3701

Since there is nothing like a 1/n stride in the ISA, the compiler has to
approximate this. However, it does not do a great job, since it first
uses a vdiv.vs instead of a shift and then an indexed load. However, it
is easy to approximate a 1/n stride by splitting the loop into even and
odd halves.

for (i=0; i\<n/2; i++) {

a\[2\*i\] = b\[2\*i\] + c\[i\];

if((2\*i+1)\<n ){

a\[2\*i+1\] = b\[2\*i+1\] + c\[i\];

}

}

This is much easier to see how to vectorize. There are half as many
iterations, each with 3 loads (2 of which are stride 2), and 2 stride 2
stores, which is better than the 3 (including an indexed load) from the
original. The conditional can be moved out of the strip-mined loop, or
the loop could be split (requiring an extra load).

**6 - Conclusion**

Even in its incomplete state, the compiler is still capable of finding
and vectorizing code, and it gains an overall speedup of 2 and an
average small structure speedup of more than 10. It should be noted that
cases where a large loop could not be vectorized would dramatically
bring the overall speedup down.

I think there is still work to be done in cleaning up the loop overhead
inside a strip-mined loop. The compiler needs to be more consistent in
taking advantage of the features of the ISA, and the available
registers. Whenever possible, indexed loads should be avoided since they
will destroy the advantages gained with a wide memory bus, which could
be taken full advantage of with unit and small strides. The Dongarra
loops should exemplify the ISA's abilities, yet it seems the compiler is
not mature enough to show this. It would have been nice to see a set of
real world applications, but the compiler needs to generate efficient
code for the simplest and most common cases before moving to
applications where loop structures might not dominate. The Dongarra
loops probably contain a very large subset of the typical code found in
most kernels intended to benchmark VIRAM.

**7 -- Future Work**

There is of course additional work to finish the basic optimizations of
the compiler for things like inlining and scheduling. Once the
scheduler, which is highly dependent on micro-architectural details, is
written, additional analysis will be needed to examine its performance
on VIRAM-1. Unfortunately, the question of whether the performance
simulator (vsim-p) will continue to exist after the forthcoming
micro-architectural changes is still up in the air. Without it,
verifying the scheduler will be difficult, and the only other methods of
generating performance numbers is by hand or waiting for silicon to come
back. Once the compiler has matured, it will then be appropriate to
begin running benchmarks and kernels on it.

**References:**

1\. D. Martin, VIRAM ISA Manual, <http://iram.cs.berkeley.edu/isa.ps>,
2000.

2\. D. Patterson, J. Hennessey, "Computer Architecture: A Quantitative
Approach", second edition, Morgan Kaufmann, 1996.

3\. "Cray C/C++ Reference Manual", version 3.2, Silicon Graphics, 1999.

4\. "Optimizing Application Code on UNICOS System", version 3.3, Silicon
Graphics, 1999.