Path: utzoo!attcan!uunet!husc6!cs.utexas.edu!oakhill!wca
From: wca@oakhill.UUCP (william anderson)
Newsgroups: comp.arch
Subject: Re: m88000 benchmarks (LONG)
Keywords: m88000 benchmark fft instruction scheduling
Message-ID: <1359@claude.oakhill.UUCP>
Date: 30 Jun 88 18:58:18 GMT
Organization: Motorola Inc. Austin, Tx
Lines: 381


In messages <1941@pt.cs.cmu.edu> and <3208@ubc-cs.UUCP> Donald Lindsay
and George Pajari discussed a particular benchmark for the M88000, the
inner loop of an FFT calculation.  In this article, we examine the
output from two compilers for this code, and present the results of
instruction rescheduling on the assembly code produced by these
compilers.  We also include a hand-coded version of the code which is
nearly optimal for the given task.

INTRODUCTION

The subprogram which is considered here is a C language version of a fast
Fourier transform subroutine, to wit:

	fft(xr,xi,n,m,wr,wi)
		float xr[],xi[],wr[],wi[];
		unsigned int n,m;
	{

		unsigned int n1,n2,ia,ie,i,j,k,l;
		float c,s,xrt,xit;

		n2 = n;
		ie = 1;
		for (k=0 ; k<m ; k++)
		{
			n1 = n2;
			n2 = n2>>1;
			ia = 0;
			for (j=0 ; j<n2 ; j++)
			{
				c = wr[ia];
				s = wi[ia];
				ia = ia+ie;

				/* BEGIN INNER LOOP */

				for (i=0 ; i<n ; i+=n1)
				{
					l = i+n2;
					xrt = xr[i] - xr[l];
					xr[i] = xr[i] + xr[l];
					xit = xi[i] - xi[l];
					xi[i] = xi[i] + xi[l];
					xr[l] = c*xrt - s*xit;
					xi[l] = c*xit + s*xrt;
				}

				/* END INNER LOOP */

			}
			ie = ie<<1;
		}
	}

In particular, we will focus on the inner loop code which is bracketed by
appropriate comments in the source above.

We will examine the assembly output for this inner loop from two compilers,
a commercial C compiler (which we will designate "compiler A") and a public-
domain C compiler ("compiler B"), both of which  currently exist for the
M88000 architecture.

Finally, we will look at a hand-coded inner loop and discuss some of the
instruction timing for the M88000.

COMPILER A

The code from compiler A for the inner loop is 39 instructions and, as
scheduled by compiler A, requires 75 clocks to execute.  Although
compiler A is supposed to have a Motorola-developed instruction
scheduling strategy incorporated in it, we can filter the above code
through the Motorola instruction scheduler to get a code sequence which
executes in 64 clocks.  Both code sequences are given below:

Code scheduled by compiler A		Code scheduled by Motorola scheduler
	(75 clocks)				(64 clocks)

@L18:                                   @L18:
        mak             r5,r23,2                ld              r8,r25,0
        addu            r10,r5,r17              mak             r5,r23,2
        st              r10,r31,92              addu            r10,r5,r17
        ld              r9,r10,0                ld              r9,r10,0
        ld              r8,r25,0                st              r10,r31,92
        fsub.sss        r10,r8,r9               ld              r12,r31,92
        ld              r12,r31,92              fsub.sss        r10,r8,r9
        st              r10,r31,80              ld              r6,r12,0
        ld              r6,r12,0                st              r10,r31,80
        addu            r10,r5,r16              addu            r10,r5,r16
        fadd.sss        r7,r8,r6                st              r10,r31,88
        st              r10,r31,88              fadd.sss        r7,r8,r6
        st              r7,r25,0                st              r7,r25,0
        ld              r4,r24,0                ld              r4,r24,0
        ld              r5,r10,0                ld              r5,r10,0
        ld              r10,r31,76              ld              r10,r31,76
        ld              r3,r24,0                ld              r3,r24,0
        fsub.sss        r4,r4,r5                fsub.sss        r4,r4,r5
        fadd.sss        r3,r3,r5                fmul.dss        r7,r10,r21
        fmul.dss        r7,r10,r21              fadd.sss        r3,r3,r5
        fmul.dss        r5,r4,r20               ld              r10,r31,80
        fsub.sdd        r9,r7,r5                addu            r25,r25,r22
        st              r3,r24,0                fmul.dss        r5,r4,r20
        st              r9,r12,0                st              r3,r24,0
        ld              r10,r31,80              addu            r24,r24,r22
        fmul.dss        r2,r10,r20              fsub.sdd        r9,r7,r5
        fmul.dss        r7,r4,r21               fmul.dss        r2,r10,r20
        fadd.sdd        r4,r2,r7                fmul.dss        r7,r4,r21
        ld              r12,r31,88              st              r9,r12,0
        st              r4,r12,0                ld              r12,r31,88
        ld              r10,r31,84              ld              r10,r31,84
        ld              r12,r31,76              fadd.sdd        r4,r2,r7
        addu            r24,r24,r22             st              r4,r12,0
        addu            r25,r25,r22             ld              r12,r31,76
        addu            r23,r23,r12             addu            r23,r23,r12
        addu            r10,r10,r12             addu            r10,r10,r12
        st              r10,r31,84              st              r10,r31,84
        cmp             r10,r14,r10             cmp             r10,r14,r10
        bb1             hi,r10,@L18             bb1             hi,r10,@L18

Several comments are in order regarding the code generated by compiler A:

 1 - Compiler A generates code which clocks at 2.67 Mflops using its own
     scheduling algorithm, and which clocks at 3.13 Mflops using Motorola's
     rescheduling filter (speeds are for a 20 MHz M88000).

 2 - Compiler A fails to use the scaled index addressing mode for either
     load (ld) or store (st) instructions.  The above "mak" and "addu"
     instructions followed by a "ld" or "st" can be collapsed into a
     single scaled indexed load or store.  Interestingly, compiler A
     was written by a software company that just finished a C compiler
     for a RISC architecture which lacks indexed addressing, either
     scaled or unscaled.  Compiler A does use scaled indexed addressing,
     however, when the arrays are integers and not floats.

 3 - Even though the most aggressive optimization was called for, the code
     in the inner loop was still loading/storing values to/from the stack
     instead of promoting the temporary stack-resident variables into
     register variables.  Half of the load/store traffic in the above inner
     loop (10 of 20 loads or stores) is unnecessary if this promotion is
     done.

 4 - Note that compiler A is using mixed-mode arithmetic in its loop.
     In particular, it is keeping the intermediate products in doubles
     (which are register-resident) while doing the final add or subtract
     with a single result for the store.  This preserves the spirit of
     K&R C and does not greatly impact the loop timing since the
     mixed-mode instructions are scheduled to avoid stalls.  The mixed-
     mode arithmetic costs an additional 2 clocks per loop. 

5 - Since the final cmp instruction reuses r10 instead of another register,
    the Motorola rescheduler cannot put the the final store of the loop into
    the branch delay slot.  If another register is used for the compare
    target, we can save yet another clock from the loop.

COMPILER B

Compiler B is a public-domain C compiler which has been recently been
adapted to generate 88K code.  Compiler B generated an inner loop which
was 22 instructions in length and which required 52 clocks as
scheduled.  After scheduling with Motorola's rescheduler, the code
required 39 clocks to execute.  As above, we list the assembly code
output using the compiler's internal scheduling algorithm side by side
with the code as scheduled by Motorola's instruction rescheduler:

Code scheduled by compiler B		Code scheduled by Motorola scheduler
	(52 clocks)				(39 clocks)

@L12:                                   @L12:
        lda.b           r2,r7,r10               ld              r4,r12[r7]
        ld              r4,r12[r7]              lda.b           r2,r7,r10
        ld              r5,r12[r2]              ld              r5,r12[r2]
        fsub.sss        r3,r4,r5                fsub.sss        r3,r4,r5
        fadd.sss        r4,r4,r5                fadd.sss        r4,r4,r5
        st              r4,r12[r7]              st              r4,r12[r7]
        ld              r5,r11[r7]              ld              r5,r11[r7]
        ld              r6,r11[r2]              ld              r6,r11[r2]
        fsub.sss        r4,r5,r6                fsub.sss        r4,r5,r6
        fadd.sss        r5,r5,r6                fadd.sss        r5,r5,r6
        st              r5,r11[r7]              fmul.sss        r6,r13,r4
        fmul.sss        r5,r14,r3               fmul.sss        r4,r14,r4
        fmul.sss        r6,r13,r4               st              r5,r11[r7]
        fsub.sss        r5,r5,r6                fmul.sss        r5,r14,r3
        st              r5,r12[r2]              fmul.sss        r3,r13,r3
        fmul.sss        r4,r14,r4               lda.b           r7,r7,r18
        fmul.sss        r3,r13,r3               cmp             r25,r7,r17
        fadd.sss        r4,r4,r3                fsub.sss        r5,r5,r6
        st              r4,r11[r2]              fadd.sss        r4,r4,r3
        lda.b           r7,r7,r18               st              r5,r12[r2]
        cmp             r25,r7,r17              bb1.n           lo,r25,@L12
        bb1             lo,r25,@L12             st              r4,r11[r2]

Several comments about the code from compiler B:

 1 - Compiler B generates code which clocks at 3.85 Mflops using its own
     scheduling algorithm, and which clocks at 5.13 Mflops using Motorola's
     rescheduling filter (speeds are for a 20 MHz M88000).

 2 - Compiler B uses the scaled index addressing mode for loads and stores,
     resulting in more efficient code than compiler A.  Note also that the
     Motorola rescheduler changed the last branch-on-bit-set (bb1) instruction
     into a bb1.n and put the last store into the delay slot.

 3 - Compiler B promoted the temporary stack-resident variables into
     register variables, thus minimizing load/store traffic.

 4 - Compiler B uses only single-precision arithmetic (in the spirit of
     ANSI C).

HAND-CODED EXAMPLE

As a limit to the optimal instruction ordering for this fft inner loop
example, we include here an equivalent inner loop, hand-coded in M88000
assembler by Marvin Denman of the MC88100 Design Team.  Although the
set-up and register usage for this loop differ slightly from the compiler
examples given above, the number and selection of instructions is identical
to compiler B.  This loop of 22 instructions executes in 23 clocks.

Hand-scheduled code
   (23 clocks)

@L12:
	fsub.sss	r7,r8,r6
	fadd.sss	r6,r8,r6
	fsub.sss	r10,r9,r5
	fadd.sss	r5,r9,r5
	st		r1,r2[r16]
	st		r20,r3[r16]
	lda.b		r16,r15,r11
	ld		r8,r21[r15]
	ld		r9,r22[r15]
	st		r6,r2[r15]
	fmul.sss	r1,r13,r7
	fmul.sss	r20,r14,r7
	st		r5,r3[r15]
	fmul.sss	r17,r14,r10
	fmul.sss	r18,r13,r10
	lda.b		r15,r15,r19
	cmp		r12,r15,r25
	ld		r6,r23[r15]
	ld		r5,r24[r15]
	fsub.sss	r1,r1,r17
	bb1.n		lo,r12,@L12
	fadd.sss	r20,r18,r20

Although the last two FP instructions in the loop do not complete before
the next iteration, there are no data dependencies which cause a stall
from loop to loop.  This code loop executes at 8.70 Mflops on an M88000
system running at 20 MHz.  This corresponds to 19.1 (native) Mips.

Note that the hand-coded assembler makes an assumption that the
compilers do not make: the data arrays are assumed not to overlap.  If
the arrays do overlap, then the minimum number of clocks for the loop
is about 36 clocks, less than 10% different from the compiler B code
above.

INSTRUCTION TIMING

Since this discussion has included the results of Motorola's instruction
rescheduler for the MC88000, a short discussion of the instruction timing
for the 88K instructions mentioned in this article is in order.  First, we
present a table of the timings of several common instructions:

Instruction Latency Comments
----------- ------- ------------------------------------------------------
addu           1    add unsigned
mak            1    make bit field
lda            1    load address
st             1    store register (optional indexed, scaled-index modes);
ld             3    load register (optional indexed, scaled-index modes)
fadd.sss       5    FP add (SP)
fadd.sdd       6    FP add (DP operands, SP result)
fsub.sss       5    FP subtract (SP)
fsub.sdd       6    FP subtract (DP operands, SP result)
fmul.sss       6    FP multiply (SP)
fmul.dss       6    FP multiply (SP operands, DP result)

The M88000 has a fully-pipelined data memory unit, so that loads and
stores can be issued each cycle in an overlapped fashion.  The results
of a load, of course, cannot be used until the load completes, and the
scoreboard enforces this.  Note also that the indexed and
scaled-indexed addressing modes supported by the data unit obviate the
need to use the integer unit adder for data array access.  The
low-level concurrency provided by this feature is one reason why
compiler B's inner loop was shorter and faster than compiler A's loop.

The FP unit actually has two pipes, one for multiply and one for add, which
share the first and last stages.  Note that the latency for the mixed
precision multiply (DP result) is the same as for the SP result, since the
register file's feed-forward circuitry manages this case.  The FP unit is
pipelined to allow the FP instructions listed to be issued each cycle.

We now look at the timing diagrams for the rescheduled loop of compiler B
and the hand-coded loop, both listed above.  These diagrams give an idea of
the concurrency available at a low level in the M88000 architecture.  In
these diagrams, the instruction duration is signified with a dash ("-")
for every clock that the instruction is active.  Note that the time that
an instruction is active may not be the same as its latency (e.g. st).
Note also that the effective latency may be greater than the nominal
latency for a particular instruction due to contention for write-back
slots to the register file.

Rescheduled compiler B code (39 clocks)

               5    10   15   20   25   30   35   40
CLOCKS     ----+----+----+----+----+----+----+----+
ld         ---
lda.b       -
ld           ---
fsub.sss        -----
fadd.sss         -----
st                    --
ld                     ---
ld                      ---
fsub.sss                   -----
fadd.sss                    -----
fmul.sss                        ------
fmul.sss                         ------
st                                --
fmul.sss                           ------
fmul.sss                            ------
lda.b                                -
cmp                                   -
fsub.sss                                  -----
fadd.sss                                   -----
st                                             --
bb1.n                                           --
st                                               --


Hand-coded loop (23 clocks)

               5    10   15   20   25   30   35   40
CLOCKS     ----+----+----+----+----+----+----+----+
fsub.sss   -----
fadd.sss    -----
fsub.sss     -----
fadd.sss      -----
st             --
st              --
lda.b            -
ld                ---
ld                 ---
st                  --
fmul.sss             ------
fmul.sss              ------
st                     --
fmul.sss                ------
fmul.sss                 ------
lda.b                     -
cmp                        -
ld                          ---
ld                           ---
fsub.sss                       -----
bb1.n                           --
fadd.sss                         -----

This diagram is particularly interesting in showing the FP pipeline
performance of the M88000.  Note that in 2 places there are 5 instructions
in progress at once, 4 of which are FP instructions.  This illustrates
Frank McMahon's assertion that, for pipelined architectures, the numerical
computation rate will be directly correlated to basic code block size
(roughly, the number of instructions in the inner loop).  For an interesting
comparison of the sensitivity of overall FP performance to the number of
FP instructions per inner loop, see McMahon's "The Livermore Fortran Kernels:
A Computer Text of the Numerical Performance Range", Lawrence Livermore
National Laboratory, UCRL-53745, December 1986, pp. 8-9.

CONCLUSIONS

The M88000 assembly code output from 2 different compilers (as well as
an optimum hand-coded example) for the inner loop of an FFT routine have
been compared.  The value of instruction scheduling for a given M88000
code fragment has been shown.  Some of the M88000 instruction timings have
been given and the timing diagrams for two of the loops were given.

       /\        /\         Mitch Alsup
      //\\      //\\        Willie Anderson
     ///\\\    ///\\\       Marvin Denman
    //    \\  //    \\      Mike Paton
   /        \/        \
  /                    \    Members the of Motorola 88000 Development Team