Chapter 12

Chapter 12

Software Optimisation

Software Optimisation

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 2

Software Optimisation Chapter

Software Optimisation Chapter

This chapter consists of three parts:

This chapter consists of three parts:

Part 1:

Part 1:

Optimisation Methods.

Optimisation Methods.

Part 2:

Part 2:

Software Pipelining.

Software Pipelining.

Part 3:

Part 3:

Multi-cycle Loop Pipelining.

Multi-cycle Loop Pipelining.

Chapter 12

Chapter 12

Software Optimisation

Software Optimisation

Part 1 - Optimisation 

Part 1 - Optimisation 

Methods

Methods

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 4

Objectives

Objectives



Introduction to optimisation and optimisation procedure.

Introduction to optimisation and optimisation procedure.



Optimisation of C code using the code generation tools.

Optimisation of C code using the code generation tools.



Optimisation of assembly code.

Optimisation of assembly code.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 5

Introduction

Introduction



Software optimisation is the process of manipulating software code to achieve two main goals:

Software optimisation is the process of manipulating software code to achieve two main goals:



Faster execution time.

Faster execution time.



Small code size.

Small code size.

Note: It will be shown that in general there 

Note: It will be shown that in general there 

is a trade off between faster 

is a trade off between faster 

execution type and smaller code size.

execution type and smaller code size.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 6

Introduction

Introduction



To implement efficient software, the programmer must be familiar with:

To implement efficient software, the programmer must be familiar with:



Processor architecture.

Processor architecture.



Programming language (C, assembly or linear assembly).

Programming language (C, assembly or linear assembly).



The code generation tools (compiler, assembler and linker).

The code generation tools (compiler, assembler and linker).

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 7

Code Optimisation Procedure

Code Optimisation Procedure

O p t im i s e   A l g o r i t h m

P r o g r a m   i n   'C '

a n d   c o m p il e   w i t h o u t

a n y   o p ti m i s a t i o n

C o d e

F u n c t io n in g ?

M a k e   t h e

n e c e s s a r y

c o r r e c t i o n ( s )

P r o fi l e   C o d e

R e s u l t

S a t i s f a c t o r y ?

U s e   in t r in s i c s

P r o fi l e   C o d e

R e s u l t

S a t i s f a c t o r y ?

S e t   n = 0   ( - O n )

C o m p i l e   c o d e   w i t h

- O n   o p t io n

C o d e

F u n c t io n in g ?

M a k e   t h e

n e c e s s a r y

c o r r e c t i o n ( s )

P r o fi l e   C o d e

R e s u l t

S a t i s f a c t o r y ?

N < 3 ?

N

N

N

Y

N

N

N

N o   f u r t h e r

o p t i m i s a t i o n   i s

r e q u ir e d

Y

N o   f u r t h e r

o p t i m i s a t i o n   i s

r e q u ir e d

Y

P a s s   t o   n e x t

s t e p   o f

o p t i m i s a i o n

( N = N + 1 )

y

N o   f u r t h e r

o p t i m i s a t i o n   i s

r e q u ir e d

I d e n t i f y   C o d e

F u n c t i o n s   t o   b e   f u r t h e r

o p ti m is e d   f r o m

P r o fi l i n g   R e s u l t

C o n v e r t   c o d e   n e e d i n g

o p t i m is a ti o n   t o   l in e a r

a s s e m b l y

C o d e

F u n c t i o n i n g ?

M a k e   t h e

n e c e s s a r y

c o r r e c t i o n ( s )

R e s u lt

S a t i s f a c t o r y ?

N o   f u r t h e r

o p t im is a ti o n   i s

r e q u i r e d

W r i t e   c o d e   i n   h a n d

a s s e m b l y

Y

N

Y

N

Y

Y

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 8

Code Optimisation Procedure

Code Optimisation Procedure

C   s o u r c e

fi le

C o d e

g e n e r a to r

O p tim is e r

P a r s e r

. c

. o p t

. a s m

. if

O p tim is in g   C o m p ile r

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 9

Optimising C Compiler Options

Optimising C Compiler Options



The ‘C6x optimising C compiler uses

The ‘C6x optimising C compiler uses 

the ANSI C source code and can perform optimisation currently up-to about 80% compared with a hand-scheduled assembly. 

the ANSI C source code and can perform optimisation currently up-to about 80% compared with a hand-scheduled assembly. 



However, to achieve this level of optimisation, knowledge of different levels of optimisation is essential. Optimisation is performed at different stages and levels

However, to achieve this level of optimisation, knowledge of different levels of optimisation is essential. Optimisation is performed at different stages and levels .

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 10

Assembly Optimisation

Assembly Optimisation



To develop an appreciation of how to optimise code, let us optimise an 

To develop an appreciation of how to optimise code, let us optimise an 

FIR filter:

FIR filter:



For simplicity we write:

For simplicity we write:

 

  















1

0

N

k

k

n

x

k

h

n

y

 

   











1

0

N

i

i

x

i

h

n

y

[1]

[1]

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 11

Assembly Optimisation

Assembly Optimisation



To implement Equation 1, we need to perform the following steps:

To implement Equation 1, we need to perform the following steps:

(1)

(1)

Load the sample x[i].

Load the sample x[i].

(2)

(2)

Load the coefficients h[i].

Load the coefficients h[i].

(3)

(3)

Multiply x[i] and h[i].

Multiply x[i] and h[i].

(4)

(4)

Add (x[i] * h[i]) to the content of an accumulator.

Add (x[i] * h[i]) to the content of an accumulator.

(5)

(5)

Repeat steps 1 to 4 N-1 times.

Repeat steps 1 to 4 N-1 times.

(6)

(6)

Store the value in the accumulator to y.

Store the value in the accumulator to y.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 12

Assembly Optimisation

Assembly Optimisation



Steps 1 to 6 can be translated into the following ‘C6x assembly code:

Steps 1 to 6 can be translated into the following ‘C6x assembly code:

MVK

.S1

0,B0

; Initialise the loop counter

MVK

.S1

0,A5

; Initialise the accumulator

loop

LDH

.D1

*A8++,A2

; Load the samples x[i]

LDH

.D1

*A9++,A3

; Load the coefficients h[i]

NOP

4

; Add “nop 4” because the LDH has a latency of 5.

MPY

.M1

A2,A3,A4

; Multiply x[i] and h[i]

NOP

; Multiply has a latency of 2 cycles

ADD

.L1

A4,A5,A5

; Add “x [i]. h[i]” to the accumulator

[B0]

SUB

.L2

B0,1,B0

;  

[B0]

B

.S1

loop

;   loop overhead

NOP

5

;   The branch has a latency of 6 cycles

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 13

Assembly Optimisation

Assembly Optimisation



In order to optimise the code, we need to:

In order to optimise the code, we need to:

(1)

(1)

Use instructions in parallel.

Use instructions in parallel.

(2)

(2)

Remove the NOPs.

Remove the NOPs.

(3)

(3)

Remove the loop overhead (remove SUB and B: loop unrolling).

Remove the loop overhead (remove SUB and B: loop unrolling).

(4)

(4)

Use word access or double-word access instead of byte or half-word access.

Use word access or double-word access instead of byte or half-word access.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 14

.M1

.M1

.M2

.M2

.L1

.L1

.L2

.L2

.S1

.S1

.S2

.S2

.D1

.D1

.D2

.D2

Cycle

Cycle

.D1

.D1

.D2

.D2

1

1

2

2

3

3

4

4

5

5

6

6

7

7

8

8

9

9

10

10

11

11

12

12

13

13

14

14

15

15

16

16

NOP

NOP

Step 1 - Using Parallel 

Step 1 - Using Parallel 

Instructions

Instructions

ldh

ldh

mpy

mpy

ldh

ldh

b

b

nop

nop

nop

nop

nop

nop

nop

nop

nop

nop

nop

nop

nop

nop

nop

nop

nop

nop

add

add

sub

sub

nop

nop

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 15

.M1

.M1

.M2

.M2

.L1

.L1

.L2

.L2

.S1

.S1

.S2

.S2

.D1

.D1

.D2

.D2

Cycle

Cycle

.D1

.D1

.D2

.D2

1

1

2

2

3

3

4

4

5

5

6

6

7

7

8

8

9

9

10

10

11

11

12

12

13

13

14

14

15

15

16

16

NOP

NOP

Step 1 - Using Parallel 

Step 1 - Using Parallel 

Instructions

Instructions

ldh

ldh

mpy

mpy

ldh

ldh

b

b

nop

nop

nop

nop

nop

nop

nop

nop

nop

nop

nop

nop

nop

nop

nop

nop

nop

nop

add

add

sub

sub

nop

nop

Note: Not all instructions can be put in 

Note: Not all instructions can be put in 

parallel since the result of one unit is 

parallel since the result of one unit is 

used as an input to the following unit.

used as an input to the following unit.

Note: Not all instructions can be put in 

Note: Not all instructions can be put in 

parallel since the result of one unit is 

parallel since the result of one unit is 

used as an input to the following unit.

used as an input to the following unit.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 16

.M1

.M1

.M2

.M2

.L1

.L1

.L2

.L2

.S1

.S1

.S2

.S2

.D1

.D1

.D2

.D2

Cycle

Cycle

.D1

.D1

.D2

.D2

1

1

2

2

3

3

4

4

5

5

6

6

7

7

8

8

9

9

10

10

11

11

12

12

13

13

14

14

15

15

16

16

NOP

NOP

Step 2 - Removing the NOPs

Step 2 - Removing the NOPs

ldh

ldh

mpy

mpy

ldh

ldh

b

b

nop

nop

nop

nop

add

add

sub

sub

nop

nop

loop LDH

.D1 *A8++,A2

LDH

.D1 *A9++,A3

[B0] SUB

.L2 B0,1,B0

[B0] B

.S1 loop

NOP

2

MPY

.M1 A2,B3,A4

NOP
ADD

.L1 A4,A5,A5

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 17

Step 3 - Loop Unrolling

Step 3 - Loop Unrolling



The SUB and B instructions consume at least two extra cycles per 

The SUB and B instructions consume at least two extra cycles per 

iteration (this is known as branch overhead).

iteration (this is known as branch overhead).

loop

LDH

.D1

*A8++,A2

LDH

.D1

*A9++,A3

[B0]

SUB

.L2

B0,1,B0

[B0]

B

.S1

loop

NOP

2

MPY

.M1

A2,A3,A4

NOP
ADD

.L1

A4,A5,A5

LDH

.D1

*A8++,A2

;Start of iteration 1

||

LDH

.D2

*B9++,B3

NOP

4

MPY

.M1X

A2,B3,A4

;Use  of  cross  path

NOP
ADD

.L1

A4,A5,A5

LDH

.D1

*A8++,A2

;Start of iteration 2

||

LDH

.D2

*B9++,B3

NOP

4

MPY

.M1

A2,B3,A4

NOP
ADD

.L1

A4,A5,A5

;

:

;

:

;

:

LDH

.D1

*A8++,A2

; Start of iteration n

||

LDH

.D2

*B9++,B3

NOP

 4

MPY

.M1

A2,B3,A4

NOP
ADD

.L1

A4,A5,A5

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 18

Step 4 - Word or Double Word 

Step 4 - Word or Double Word 

Access

Access



The ‘C6711 has two 64-bit data buses for data memory access and therefore up to two 64-bit can be loaded into the registers at any time (see Chapter 2).

The ‘C6711 has two 64-bit data buses for data memory access and therefore up to two 64-bit can be loaded into the registers at any time (see Chapter 2).



In addition the ‘C6711 devices have variants of the multiplication instruction to support different operation (see Chapter 2).

In addition the ‘C6711 devices have variants of the multiplication instruction to support different operation (see Chapter 2).

Note: Store can only be up to 32-bit.

Note: Store can only be up to 32-bit.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 19

loop

LDW

.D1

*A9++,A3 ; 32-bit word is loaded in a single cycle 

||

LDW

.D2

*B6++,B1

NOP

4

[B0]

SUB

.L2

[B0]

B

.S1

loop

NOP

2

MPY

.M1

A3,B1,A4

||

MPYH

.M2

A3,B1,B3

NOP
ADD

.L1

A4,B3,A5

Step 4 - Word or Double Word 

Step 4 - Word or Double Word 

Access

Access



Using word access, MPY and MPYH the previous code can be written as:

Using word access, MPY and MPYH the previous code can be written as:



Note: By loading words and using MPY and MPYH instructions the execution time has 

Note: By loading words and using MPY and MPYH instructions the execution time has 

been halved since in each iteration two 16x16-bit multiplications are performed.

been halved since in each iteration two 16x16-bit multiplications are performed.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 20

Optimisation Summary

Optimisation Summary



It has been shown that there are four complementary methods for code optimisation:

It has been shown that there are four complementary methods for code optimisation:



Using instructions in parallel.

Using instructions in parallel.



Filling the delay slots with useful code.

Filling the delay slots with useful code.



Using word or double word load.

Using word or double word load.



Loop unrolling.

Loop unrolling.

These 

These 

increase performance

increase performance

 and 

 and 

reduce code size.

reduce code size.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 21

Optimisation Summary

Optimisation Summary

This 

This 

increases performance

increases performance

 but 

 but 

increases code size.

increases code size.



It has been shown that there are four complementary methods for code optimisation:

It has been shown that there are four complementary methods for code optimisation:



Using instructions in parallel.

Using instructions in parallel.



Filling the delay slots with useful code.

Filling the delay slots with useful code.



Using word or double word load.

Using word or double word load.



Loop unrolling.

Loop unrolling.

Chapter 12

Chapter 12

Software Optimisation

Software Optimisation

Part 2 - Software 

Part 2 - Software 

Pipelining

Pipelining

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 23

Objectives

Objectives



Why using Software 

Why using Software 

Pipelining, SP?

Pipelining, SP?



Understand software 

Understand software 

pipelining concepts.

pipelining concepts.



Use software pipelining 

Use software pipelining 

procedure.

procedure.



Code the word-wide software 

Code the word-wide software 

pipelined dot-product routine.

pipelined dot-product routine.



Determine if your pipelined 

Determine if your pipelined 

code is more efficient with or 

code is more efficient with or 

without prolog and epilog.

without prolog and epilog.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 24

Why using Software Pipelining, 

Why using Software Pipelining, 

SP?

SP?



SP creates highly optimized loop-

SP creates highly optimized loop-

code by:

code by:



Putting several instructions in 

Putting several instructions in 

parallel.

parallel.



Filling delay slots with useful code.

Filling delay slots with useful code.



Maximizes functional units.

Maximizes functional units.



SP is implemented by simply using 

SP is implemented by simply using 

the tools:

the tools:



Compiler options -o2 or -o3.

Compiler options -o2 or -o3.



Assembly Optimizer if .sa file.

Assembly Optimizer if .sa file.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 25

Software Pipeline concept

Software Pipeline concept

     

     

LDH

LDH

 

 

||  LDH

||  LDH

     

     

MPY

MPY

     

     

ADD

ADD

            

            

How many cycles would

How many cycles would

it take to perform this

it take to perform this

loop 5 times?

loop 5 times?

(Disregard delay-slots).

(Disregard delay-slots).

______________ cycles

______________ cycles

To explain the concept of software 

To explain the concept of software 

pipelining, we 

pipelining, we 

will assume

will assume

 that all 

 that all 

instructions execute in one cycle.

instructions execute in one cycle.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 26

Software Pipeline Example

Software Pipeline Example

     

     

LDH

LDH

 

 

||  LDH

||  LDH

     

     

MPY

MPY

     

     

ADD

ADD

            

            

How many cycles would

How many cycles would

it take to perform this

it take to perform this

loop 5 times?

loop 5 times?

(Disregard delay-slots).

(Disregard delay-slots).

______________ cycles

______________ cycles

5 x 3 = 15

5 x 3 = 15

Let’s examine hardware

Let’s examine hardware

 (functional units) usage ... 

 (functional units) usage ... 

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 27

Non-Pipelined Code

Non-Pipelined Code

.M1

.M1

.M2

.M2

.L1

.L1

.L2

.L2

.S1

.S1

.S2

.S2

.D1

.D1

.D2

.D2

1

1

Cycle

Cycle

ldh

ldh

ldh

ldh

2

2

mpy

mpy

3

3

add

add

4

4

ldh

ldh

ldh

ldh

5

5

mpy

mpy

6

6

add

add

7

7

ldh

ldh

ldh

ldh

8

8

mpy

mpy

9

9

add

add

.

.

D1

D1

.

.

D2

D2

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 28

Pipelining Code

Pipelining Code

.M1

.M1

.M2

.M2

.L1

.L1

.L2

.L2

.S1

.S1

.S2

.S2

.D1

.D1

.D2

.D2

1

1

Cycle

Cycle

ldh

ldh

ldh

ldh

2

2

mpy

mpy

ldh

ldh

ldh

ldh

3

3

add

add

mpy

mpy

ldh

ldh

ldh

ldh

4

4

add

add

mpy

mpy

ldh

ldh

ldh

ldh

5

5

add

add

mpy

mpy

ldh

ldh

ldh

ldh

6

6

add

add

mpy

mpy

7

7

add

add

Pipelining these instructions took 1/2 the cycles!

Pipelining these instructions took 1/2 the cycles!

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 29

Pipelining Code

Pipelining Code

.M1

.M1

.M2

.M2

.L1

.L1

.L2

.L2

.S1

.S1

.S2

.S2

.D1

.D1

.D2

.D2

1

1

Cycle

Cycle

ldh

ldh

ldh

ldh

2

2

mpy

mpy

ldh

ldh

ldh

ldh

3

3

add

add

mpy

mpy

ldh

ldh

ldh

ldh

4

4

add

add

mpy

mpy

ldh

ldh

ldh

ldh

5

5

add

add

mpy

mpy

ldh

ldh

ldh

ldh

6

6

add

add

mpy

mpy

7

7

add

add

Pipelining these instructions takes only 7 cycles!

Pipelining these instructions takes only 7 cycles!

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 30

Loop Kernel

Loop Kernel

Single-cycle “loop”

Single-cycle “loop”

iterated three times.

iterated three times.

Pipelining Code

Pipelining Code

.M1

.M1

.L1

.L1

.D1

.D1

.D2

.D2

ldh

ldh

ldh

ldh

1

1

mpy

mpy

2

2

ldh

ldh

ldh

ldh

add

add

3

3

mpy

mpy

ldh

ldh

ldh

ldh

mpy

mpy

add

add

ldh

ldh

ldh

ldh

4

4

add

add

mpy

mpy

5

5

ldh

ldh

ldh

ldh

add

add

6

6

mpy

mpy

7

7

add

add

Prolog

Prolog

Staging for loop.

Staging for loop.

Epilog

Epilog

Completing final

Completing final

operations.

operations.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 31

Pipelined Code

Pipelined Code

prolog:

prolog:

LDH

LDH

; load 1

; load 1

||

||

LDH

LDH

MPY

MPY

; mpy  1

; mpy  1

||

||

LDH

LDH

; load 2

; load 2

||

||

LDH

LDH

loop:

loop:

ADD

ADD

; add  1

; add  1

||

||

MPY

MPY

; mpy

; mpy

 2

 2

||

||

LDH

LDH

; load 3

; load 3

||

||

LDH

LDH

ADD

ADD

; add  2

; add  2

||

||

MPY

MPY

; mpy

; mpy

 3

 3

||

||

LDH

LDH

; load 4

; load 4

||

||

LDH

LDH

.

.

.

.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 32

Software Pipelining Procedure

Software Pipelining Procedure

   

   

1.

1.

Write algorithm in C code & verify.

Write algorithm in C code & verify.

   

   

2.

2.

Write ‘C6x Linear Assembly code.

Write ‘C6x Linear Assembly code.

   

   

3.

3.

Create dependency graph.

Create dependency graph.

   

   

4.

4.

Allocate registers.

Allocate registers.

   

   

5.

5.

Create scheduling table.

Create scheduling table.

   

   

6.

6.

Translate scheduling table to ‘C6x code.

Translate scheduling table to ‘C6x code.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 33

short DotP(short *m, short *n, short count)

short DotP(short *m, short *n, short count)

{ int i;

{ int i;

  

  

short product;

short product;

  

  

short sum = 0;

short sum = 0;

  

  

for (i=0; i < count; i++)

for (i=0; i < count; i++)

  

  

{

{

    

    

product = m[i] * n[i];

product = m[i] * n[i];

    

    

sum += product;

sum += product;

  

  

}

}

  

  

return(sum);

return(sum);

}

}

Software Pipelining Example (Step 

Software Pipelining Example (Step 

1)

1)

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 34

Software Pipelining Procedure

Software Pipelining Procedure

   

   

1.

1.

Write algorithm in C code & verify.

Write algorithm in C code & verify.

   

   

2.

2.

Write ‘C6x Linear Assembly code.

Write ‘C6x Linear Assembly code.

   

   

3.

3.

Create dependency graph.

Create dependency graph.

   

   

4.

4.

Allocate registers.

Allocate registers.

   

   

5.

5.

Create scheduling table.

Create scheduling table.

   

   

6.

6.

Translate scheduling table to ‘C6x code.

Translate scheduling table to ‘C6x code.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 35

; for (i=0; i < count; i++)

; for (i=0; i < count; i++)

; prod = m[i] * n[i];

; prod = m[i] * n[i];

; sum += prod;

; sum += prod;

loop:

loop:

ldh

ldh

*p_m++, m

*p_m++, m

ldh

ldh

*p_n++, n

*p_n++, n

mpy

mpy

m, n, prod

m, n, prod

add

add

prod, sum, sum

prod, sum, sum

   

   

[count]

[count]

sub

sub

count, 1, count

count, 1, count

   

   

[count] 

[count] 

b

b

loop

loop

1.

1.

No NOP’s required.

No NOP’s required.

2.

2.

No parallel instructions required.

No parallel instructions required.

3.

3.

You don’t have to specify:

You don’t have to specify:



Functional units, or

Functional units, or



Registers.

Registers.

Write code in Linear Assembly 

Write code in Linear Assembly 

(Step 2)

(Step 2)

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 36

Software Pipelining Procedure

Software Pipelining Procedure

   

   

1.

1.

Write algorithm in C code & verify.

Write algorithm in C code & verify.

   

   

2.

2.

Write ‘C6x Linear Assembly code.

Write ‘C6x Linear Assembly code.

   

   

3.

3.

Create a dependency graph (4 steps).

Create a dependency graph (4 steps).

   

   

4.

4.

Allocate registers.

Allocate registers.

   

   

5.

5.

Create scheduling table.

Create scheduling table.

   

   

6.

6.

Translate scheduling table to ‘C6x code.

Translate scheduling table to ‘C6x code.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 37

Dependency Graph Terminology

Dependency Graph Terminology

a

a

b

b

na

na

Child Node

Child Node

Parent Node

Parent Node

Path

Path

5

5

.L

.L

.D

.D

.D

.D

LDH

LDH

LDH

LDH

5

5

NOT

NOT

Conditional Path

Conditional Path

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 38

Dependency Graph Steps

Dependency Graph Steps

(a)

(a)

Draw the algorithm nodes 

Draw the algorithm nodes 

and paths.

and paths.

(b)

(b)

Write the number of cycles it 

Write the number of cycles it 

takes for each instruction to 

takes for each instruction to 

complete execution.

complete execution.

(c)

(c)

Assign “required” function 

Assign “required” function 

units to each node.

units to each node.

(d)

(d)

Partition the nodes to A and 

Partition the nodes to A and 

B sides and assign sides to all 

B sides and assign sides to all 

functional units.

functional units.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 39

Dependency Graph (Step a)

Dependency Graph (Step a)



In this step each instruction is 

In this step each instruction is 

represented by a node.

represented by a node.



The node is represented by a 

The node is represented by a 

circle, where:

circle, where:



Outside: write instruction.

Outside: write instruction.



Inside: register where result is 

Inside: register where result is 

written.

written.



Nodes are then connected by 

Nodes are then connected by 

paths showing the data flow.

paths showing the data flow.

Note: Conditional paths are 

Note: Conditional paths are 

represented by 

represented by 

dashed

dashed

 lines.

 lines.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 40

Dependency Graph (Step a)

Dependency Graph (Step a)

m

m

LDH

LDH

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 41

Dependency Graph (Step a)

Dependency Graph (Step a)

m

m

LDH

LDH

n

n

LDH

LDH

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 42

Dependency Graph (Step a)

Dependency Graph (Step a)

m

m

LDH

LDH

n

n

LDH

LDH

prod

prod

MPY

MPY

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 43

Dependency Graph (Step a)

Dependency Graph (Step a)

m

m

LDH

LDH

n

n

LDH

LDH

prod

prod

MPY

MPY

sum

sum

ADD

ADD

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 44

Dependency Graph (Step a)

Dependency Graph (Step a)

m

m

LDH

LDH

n

n

LDH

LDH

prod

prod

MPY

MPY

sum

sum

ADD

ADD

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 45

Dependency Graph (Step a)

Dependency Graph (Step a)

m

m

LDH

LDH

n

n

LDH

LDH

prod

prod

MPY

MPY

sum

sum

ADD

ADD

count

count

SUB

SUB

loop

loop

B    

B    

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 46

Dependency Graph (Step b)

Dependency Graph (Step b)



In this step the number of 

In this step the number of 

cycles it takes for each 

cycles it takes for each 

instruction to complete 

instruction to complete 

execution is added to the 

execution is added to the 

dependency graph.

dependency graph.



It is written along the 

It is written along the 

associated data path.

associated data path.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 47

Dependency Graph (Step b)

Dependency Graph (Step b)

m

m

LDH

LDH

n

n

LDH

LDH

prod

prod

MPY

MPY

sum

sum

ADD

ADD

5

5

5

5

2

2

1

1

count

count

SUB

SUB

loop

loop

B    

B    

1

1

1

1

6

6

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 48

Dependency Graph (Step c)

Dependency Graph (Step c)



In this step functional units are 

In this step functional units are 

assigned to each node.

assigned to each node.



It is advantageous to start 

It is advantageous to start 

allocating units to instructions 

allocating units to instructions 

which require a specific unit:

which require a specific unit:



Load/Store.

Load/Store.



Branch.

Branch.



We do not need to be concerned 

We do not need to be concerned 

with multiply as this is the only 

with multiply as this is the only 

operation that the .M unit 

operation that the .M unit 

performs.

performs.

Note: The side is not allocated at 

Note: The side is not allocated at 

this stage.

this stage.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 49

Dependency Graph (Step c)

Dependency Graph (Step c)

m

m

LDH

LDH

n

n

LDH

LDH

prod

prod

MPY

MPY

sum

sum

ADD

ADD

.D

.D

.D

.D

5

5

5

5

2

2

1

1

count

count

SUB

SUB

loop

loop

B    

B    

1

1

1

1

.M

.M

.S

.S

6

6

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 50

Dependency Graph (Step d)

Dependency Graph (Step d)



The data path is partitioned into 

The data path is partitioned into 

side A and B at this stage.

side A and B at this stage.



To optimise code we need to 

To optimise code we need to 

ensure that a maximum number 

ensure that a maximum number 

of units are used with a 

of units are used with a 

minimum number of cross 

minimum number of cross 

paths.

paths.



To make the partition visible on 

To make the partition visible on 

the dependency graph a line is 

the dependency graph a line is 

used.

used.



The side can then be added to 

The side can then be added to 

the functional units associated 

the functional units associated 

with each instruction or node.

with each instruction or node.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 51

Dependency Graph (Step d)

Dependency Graph (Step d)

A

A

Side

Side

B

B

Side

Side

m

m

LDH

LDH

n

n

LDH

LDH

prod

prod

MPY

MPY

sum

sum

ADD

ADD

.D

.D

.D

.D

5

5

5

5

2

2

1

1

count

count

SUB

SUB

loop

loop

B    

B    

1

1

1

1

.M

.M

.S

.S

6

6

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 52

Dependency Graph (Step d)

Dependency Graph (Step d)

m

m

LDH

LDH

n

n

LDH

LDH

prod

prod

MPY

MPY

sum

sum

ADD

ADD

A

A

Side

Side

.D

.D

1

1

.D

.D

2

2

5

5

5

5

2

2

1

1

count

count

SUB

SUB

loop

loop

B    

B    

1

1

1

1

.M

.M

1x

1x

.L

.L

1

1

.L

.L

2

2

.S

.S

2

2

B

B

Side

Side

6

6

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 53

Software Pipelining Procedure

Software Pipelining Procedure

   

   

1.

1.

Write algorithm in C code & verify.

Write algorithm in C code & verify.

   

   

2.

2.

Write ‘C6x Linear Assembly code.

Write ‘C6x Linear Assembly code.

   

   

3.

3.

Create a dependency graph (4 steps).

Create a dependency graph (4 steps).

   

   

4.

4.

Allocate registers.

Allocate registers.

   

   

5.

5.

Create scheduling table.

Create scheduling table.

   

   

6.

6.

Translate scheduling table to ‘C6x code.

Translate scheduling table to ‘C6x code.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 54

Step 4 - Allocate Functional Units

Step 4 - Allocate Functional Units



 

 



 

 



 

 



 

 



 

 



 

 

Do we have enough 

Do we have enough 

functional units to 

functional units to 

code this algorithm in 

code this algorithm in 

a 

a 

single-cycle

single-cycle

 loop?

 loop?

.L1

.L1

.M1

.M1

.D1

.D1

.S1

.S1

x1

x1

.L2

.L2

.M2

.M2

.D2

.D2

.S2

.S2

x2

x2

sum

sum

prod

prod

m

m

.M1x

.M1x

count

count

n

n

loop

loop



 

 

m

m

LDH

LDH

n

n

LDH

LDH

prod

prod

MPY

MPY

sum

sum

ADD

ADD

A

A

Side

Side

.D1

.D1

.

.

D2

D2

5

5

5

5

2

2

1

1

count

count

SUB

SUB

loop

loop

B    

B    

1

1

1

1

.M1x

.M1x

.L1

.L1

.

.

L2

L2

.S2

.S2

B

B

Side

Side

6

6

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 55

Step 4 - Allocate Registers

Step 4 - Allocate Registers

Content of Register File A

Content of Register File A

&a

&a

a

a

prod

prod

sum

sum

Reg. A

Reg. A

Reg. B

Reg. B

A0

A0

B0

B0

A1

A1

B1

B1

A2

A2

B2

B2

A3

A3

B3

B3

A4

A4

B4

B4

...

...

...

...

A15

A15

B15

B15

Content of Register File B

Content of Register File B

count

count

&b

&b

b

b

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 56

Software Pipelining Procedure

Software Pipelining Procedure

   

   

1.

1.

Write algorithm in C code & verify.

Write algorithm in C code & verify.

   

   

2.

2.

Write ‘C6x Linear Assembly code.

Write ‘C6x Linear Assembly code.

   

   

3.

3.

Create a dependency graph (4 steps).

Create a dependency graph (4 steps).

   

   

4.

4.

Allocate registers.

Allocate registers.

   

   

5.

5.

Create scheduling table.

Create scheduling table.

   

   

6.

6.

Translate scheduling table to ‘C6x code.

Translate scheduling table to ‘C6x code.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 57

.L1

.L1

.L2

.L2

.S1

.S1

.S2

.S2

.M1

.M1

.M2

.M2

.D1

.D1

.D2

.D2

Step 5 - Create Scheduling Table

Step 5 - Create Scheduling Table

How do we know the loop ends up in cycle 8?

How do we know the loop ends up in cycle 8?

LOOP

LOOP

PROLOG

PROLOG

8

8

7

7

6

6

5

5

4

4

3

3

2

2

1

1

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 58

Length of Prolog

Length of Prolog

Answer:



Count up the 

length of 

longest path,  in 

this case we 

have:
5 + 2 + 1 = 8 

cycles

m

m

LDH

LDH

prod

prod

MPY

MPY

sum

sum

ADD

ADD

5

5

2

2

1

1

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 59

.L1

.L1

.L2

.L2

.S1

.S1

.S2

.S2

.M1

.M1

.M2

.M2

.D1

.D1

.D2

.D2

Scheduling Table

Scheduling Table

LOOP

LOOP

PROLOG

PROLOG

8

8

7

7

6

6

5

5

4

4

3

3

2

2

1

1

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 60

Scheduling Table

Scheduling Table

8

8

 

 

.L1

.L1

.L2

.L2

.S1

.S1

.S2

.S2

.M1

.M1

.M2

.M2

.D1

.D1

.D2

.D2

7

7

6

6

5

5

4

4

3

3

2

2

1

1

LOOP

LOOP

PROLOG

PROLOG

 

 

*

*

*

*

*

*

*

*

*

*

*

*

*

*

ldh m

ldh m

*

*

*

*

*

*

*

*

*

*

*

*

*

*

ldh n

ldh n

*

*

*

*

mpy

mpy

add

add

*

*

*

*

*

*

*

*

*

*

B

B

Where do we want to branch?

Where do we want to branch?

Branch here

Branch here

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 61

Scheduling Table

Scheduling Table

.L1

.L1

.L2

.L2

.S1

.S1

.S2

.S2

.M1

.M1

.M2

.M2

.D1

.D1

.D2

.D2

add

add

*

*

*

*

mpy

mpy

*

*

*

*

*

*

*

*

*

*

B

B

8

8

7

7

6

6

5

5

4

4

3

3

2

2

1

1

*

*

*

*

*

*

*

*

*

*

*

*

*

*

ldh m

ldh m

*

*

*

*

*

*

*

*

*

*

*

*

*

*

ldh n

ldh n

*

*

*

*

*

*

*

*

*

*

*

*

sub

sub

LOOP

LOOP

PROLOG

PROLOG

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 62

Software Pipelining Procedure

Software Pipelining Procedure

   

   

1.

1.

Write algorithm in C code & verify.

Write algorithm in C code & verify.

   

   

2.

2.

Write ‘C6x Linear Assembly code.

Write ‘C6x Linear Assembly code.

   

   

3.

3.

Create a dependency graph (4 steps).

Create a dependency graph (4 steps).

   

   

4.

4.

Allocate registers.

Allocate registers.

   

   

5.

5.

Create scheduling table.

Create scheduling table.

   

   

6.

6.

Translate scheduling table to ‘C6x code.

Translate scheduling table to ‘C6x code.

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 63

Translate Scheduling Table to ‘C6x 

Translate Scheduling Table to ‘C6x 

Code

Code

.L1

.L1

.L2

.L2

.S1

.S1

.S2

.S2

.M1

.M1

.M2

.M2

.D1

.D1

.D2

.D2

add

add

*

*

*

*

mpy

mpy

*

*

*

*

*

*

*

*

*

*

B

B

7

7

6

6

5

5

4

4

3

3

2

2

1

1

1

1

*

*

*

*

*

*

*

*

*

*

*

*

*

*

ldh m

ldh m

*

*

*

*

*

*

*

*

*

*

*

*

*

*

ldh n

ldh n

*

*

*

*

*

*

*

*

*

*

*

*

sub

sub

LOOP

LOOP

PROLOG

PROLOG

C1       ldh .D1  *A1++,A2

C1       ldh .D1  *A1++,A2

 

 

||      ldh .D2  *B1++,B2

||      ldh .D2  *B1++,B2

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 64

Translate Scheduling Table to ‘C6x 

Translate Scheduling Table to ‘C6x 

Code

Code

.L1

.L1

.L2

.L2

.S1

.S1

.S2

.S2

.M1

.M1

.M2

.M2

.D1

.D1

.D2

.D2

add

add

*

*

*

*

mpy

mpy

*

*

*

*

*

*

*

*

*

*

B

B

7

7

6

6

5

5

4

4

3

3

2

2

2

2

1

1

*

*

*

*

*

*

*

*

*

*

*

*

*

*

ldh m

ldh m

*

*

*

*

*

*

*

*

*

*

*

*

*

*

ldh n

ldh n

*

*

*

*

*

*

*

*

*

*

*

*

sub

sub

LOOP

LOOP

PROLOG

PROLOG

C1       ldh .D1  *A1++,A2

C1       ldh .D1  *A1++,A2

 

 

||      ldh .D2  *B1++,B2

||      ldh .D2  *B1++,B2

C2       ldh .D1  *A1++,A2

C2       ldh .D1  *A1++,A2

 

 

||      ldh .D2  *B1++,B2

||      ldh .D2  *B1++,B2

 

 

|| [B0] sub .L2  B0,1,B0

|| [B0] sub .L2  B0,1,B0

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 65

Translate Scheduling Table to ‘C6x 

Translate Scheduling Table to ‘C6x 

Code

Code

.L1

.L1

.L2

.L2

.S1

.S1

.S2

.S2

.M1

.M1

.M2

.M2

.D1

.D1

.D2

.D2

add

add

*

*

*

*

mpy

mpy

*

*

*

*

*

*

*

*

*

*

B

B

7

7

6

6

5

5

4

4

3

3

3

3

2

2

1

1

*

*

*

*

*

*

*

*

*

*

*

*

*

*

ldh m

ldh m

*

*

*

*

*

*

*

*

*

*

*

*

*

*

ldh n

ldh n

*

*

*

*

*

*

*

*

*

*

*

*

sub

sub

LOOP

LOOP

PROLOG

PROLOG

C1       ldh .D1  *A1++,A2

C1       ldh .D1  *A1++,A2

 

 

||      ldh .D2  *B1++,B2

||      ldh .D2  *B1++,B2

C2       ldh .D1  *A1++,A2

C2       ldh .D1  *A1++,A2

 

 

||      ldh .D2  *B1++,B2

||      ldh .D2  *B1++,B2

 

 

|| [B0] sub .L2  B0,1,B0

|| [B0] sub .L2  B0,1,B0

C3       ldh .D1  *A1++,A2

C3       ldh .D1  *A1++,A2

 

 

||      ldh .D2  *B1++,B2

||      ldh .D2  *B1++,B2

 

 

|| [B0] sub .L2  B0,1,B0

|| [B0] sub .L2  B0,1,B0

 

 

|| [B0] B   .S2  loop

|| [B0] B   .S2  loop

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 66

Translate Scheduling Table to ‘C6x 

Translate Scheduling Table to ‘C6x 

Code

Code

.L1

.L1

.L2

.L2

.S1

.S1

.S2

.S2

.M1

.M1

.M2

.M2

.D1

.D1

.D2

.D2

add

add

*

*

*

*

mpy

mpy

*

*

*

*

*

*

*

*

*

*

B

B

7

7

6

6

5

5

4

4

4

4

3

3

2

2

1

1

*

*

*

*

*

*

*

*

*

*

*

*

*

*

ldh m

ldh m

*

*

*

*

*

*

*

*

*

*

*

*

*

*

ldh n

ldh n

*

*

*

*

*

*

*

*

*

*

*

*

sub

sub

LOOP

LOOP

C1       ldh .D1  *A1++,A2

C1       ldh .D1  *A1++,A2

 

 

||      ldh .D2  *B1++,B2

||      ldh .D2  *B1++,B2

C2       ldh .D1  *A1++,A2

C2       ldh .D1  *A1++,A2

 

 

||      ldh .D2  *B1++,B2

||      ldh .D2  *B1++,B2

 

 

|| [B0] sub .L2  B0,1,B0

|| [B0] sub .L2  B0,1,B0

C3       ldh .D1  *A1++,A2

C3       ldh .D1  *A1++,A2

 

 

||      ldh .D2  *B1++,B2

||      ldh .D2  *B1++,B2

 

 

|| [B0] sub .L2  B0,1,B0

|| [B0] sub .L2  B0,1,B0

 

 

|| [B0] B   .S2  loop

|| [B0] B   .S2  loop

C4       ldh .D1  *A1++,A2

C4       ldh .D1  *A1++,A2

 

 

||      ldh .D2  *B1++,B2

||      ldh .D2  *B1++,B2

 

 

|| [B0] sub .L2  B0,1,B0

|| [B0] sub .L2  B0,1,B0

 

 

|| [B0] B   .S2  loop

|| [B0] B   .S2  loop

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 67

Translate Scheduling Table to ‘C6x 

Translate Scheduling Table to ‘C6x 

Code

Code

.L1

.L1

.L2

.L2

.S1

.S1

.S2

.S2

.M1

.M1

.M2

.M2

.D1

.D1

.D2

.D2

add

add

*

*

*

*

mpy

mpy

*

*

*

*

*

*

B

B

*

*

B

B

8

8

7

7

6

6

5

5

4

4

3

3

2

2

1

1

*

*

*

*

*

*

ldh

ldh

*

*

*

*

*

*

ldh m

ldh m

*

*

*

*

*

*

ldh

ldh

*

*

*

*

*

*

ldh n

ldh n

*

*

*

*

*

*

sub

sub

*

*

*

*

sub

sub

LOOP

LOOP

C1       ldh .D1  *A1++,A2

C1       ldh .D1  *A1++,A2

 

 

||      ldh .D2  *B1++,B2

||      ldh .D2  *B1++,B2

C2       ldh .D1  *A1++,A2

C2       ldh .D1  *A1++,A2

 

 

||      ldh .D2  *B1++,B2

||      ldh .D2  *B1++,B2

 

 

|| [B0] sub .L2  B0,1,B0

|| [B0] sub .L2  B0,1,B0

C3       ldh .D1  *A1++,A2

C3       ldh .D1  *A1++,A2

 

 

||      ldh .D2  *B1++,B2

||      ldh .D2  *B1++,B2

 

 

|| [B0] sub .L2  B0,1,B0

|| [B0] sub .L2  B0,1,B0

 

 

|| [B0] B   .S2  loop

|| [B0] B   .S2  loop

C4       ldh .D1  *A1++,A2

C4       ldh .D1  *A1++,A2

 

 

||      ldh .D2  *B1++,B2

||      ldh .D2  *B1++,B2

 

 

|| [B0] sub .L2  B0,1,B0

|| [B0] sub .L2  B0,1,B0

 

 

|| [B0] B   .S2  loop

|| [B0] B   .S2  loop

C5       ldh .D1  *A1++,A2

C5       ldh .D1  *A1++,A2

 

 

||      ldh .D2  *B1++,B2

||      ldh .D2  *B1++,B2

 

 

|| [B0] sub .L2  B0,1,B0

|| [B0] sub .L2  B0,1,B0

 

 

|| [B0] B   .S2  loop

|| [B0] B   .S2  loop

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 68

Translate Scheduling Table to ‘C6x 

Translate Scheduling Table to ‘C6x 

Code

Code

.L1

.L1

.L2

.L2

.S1

.S1

.S2

.S2

.M1

.M1

.M2

.M2

.D1

.D1

.D2

.D2

add

add

*

*

*

*

mpy

mpy

*

*

*

*

B

B

*

*

*

*

B

B

8

8

7

7

6

6

4

4

4

4

3

3

2

2

1

1

*

*

*

*

ldh

ldh

*

*

*

*

*

*

*

*

ldh m

ldh m

*

*

*

*

ldh

ldh

*

*

*

*

*

*

*

*

ldh n

ldh n

*

*

*

*

sub

sub

*

*

*

*

*

*

sub

sub

LOOP

LOOP

PROLOG

PROLOG

C6

C6

   ldh .D1  *A1++,A2

   ldh .D1  *A1++,A2

 ||

 ||

   ldh .D2  *B1++,B2

   ldh .D2  *B1++,B2

 || [B0] sub .L2  B0,1,B0

 || [B0] sub .L2  B0,1,B0

 || [B0] B

 || [B0] B

 .S2  loop

 .S2  loop

 ||      mpy .M1x A2,B2,A3

 ||      mpy .M1x A2,B2,A3

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 69

Translate Scheduling Table to ‘C6x 

Translate Scheduling Table to ‘C6x 

Code

Code

.L1

.L1

.L2

.L2

.S1

.S1

.S2

.S2

.M1

.M1

.M2

.M2

.D1

.D1

.D2

.D2

add

add

*

*

*

*

mpy

mpy

*

*

*

*

B

B

*

*

*

*

B

B

8

8

7

7

6

6

4

4

4

4

3

3

2

2

1

1

*

*

*

*

ldh

ldh

*

*

*

*

*

*

*

*

ldh m

ldh m

*

*

*

*

ldh

ldh

*

*

*

*

*

*

*

*

ldh n

ldh n

*

*

*

*

sub

sub

*

*

*

*

*

*

sub

sub

LOOP

LOOP

PROLOG

PROLOG

C7

C7

   ldh .D1  *A1++,A2

   ldh .D1  *A1++,A2

 ||

 ||

   ldh .D2  *B1++,B2

   ldh .D2  *B1++,B2

 || [B0] sub .L2  B0,1,B0

 || [B0] sub .L2  B0,1,B0

 || [B0] B

 || [B0] B

 .S2  loop

 .S2  loop

 ||      mpy .M1x A2,B2,A3

 ||      mpy .M1x A2,B2,A3

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 70

Translate Scheduling Table to ‘C6x 

Translate Scheduling Table to ‘C6x 

Code

Code

.L1

.L1

.L2

.L2

.S1

.S1

.S2

.S2

.M1

.M1

.M2

.M2

.D1

.D1

.D2

.D2

add

add

*

*

*

*

mpy

mpy

*

*

*

*

B

B

*

*

*

*

B

B

8

8

7

7

6

6

4

4

4

4

3

3

2

2

1

1

*

*

*

*

ldh

ldh

*

*

*

*

*

*

*

*

ldh m

ldh m

*

*

*

*

ldh

ldh

*

*

*

*

*

*

*

*

ldh n

ldh n

*

*

*

*

sub

sub

*

*

*

*

*

*

sub

sub

LOOP

PROLOG

PROLOG

*  Single-Cycle Loop

*  Single-Cycle Loop

loop:

loop:

   ldh .D1  *A1++,A2

   ldh .D1  *A1++,A2

 ||

 ||

   ldh .D2  *B1++,B2

   ldh .D2  *B1++,B2

 || [B0] sub .L2  B0,1,B0

 || [B0] sub .L2  B0,1,B0

 || [B0] B

 || [B0] B

 .S2  loop

 .S2  loop

 ||      mpy .M1x A2,B2,A3

 ||      mpy .M1x A2,B2,A3

 ||      add .L1  A4,A3,A4

 ||      add .L1  A4,A3,A4

 

 

See Chapter 14 for practical examples

Dr. Naim 
Dahnoun, 
Bristol U
niversity
,  (c) Te
xas Instr
uments 20
04

Chapter 12, Slide 71



With this method we have only created 

With this method we have only created 

the 

the 

prolog

prolog

 and the 

 and the 

loop

loop

.

.



Therefore if the filter has 100 taps, then 

Therefore if the filter has 100 taps, then 

we need to repeat the loop 100 times as 

we need to repeat the loop 100 times as 

we need 100 adds. 

we need 100 adds. 



This means that we are performing 107 

This means that we are performing 107 

loads.  These 

loads.  These 

7 extra loads

7 extra loads

 may lead to 

 may lead to 

some illegal memory acesses

some illegal memory acesses

.

.

Translate Scheduling Table to ‘C6x 

Translate Scheduling Table to ‘C6x 

Code

Code

.L1

.L1

.L2

.L2

.S1

.S1

.S2

.S2

.M1

.M1

.M2

.M2

.D1

.D1

.D2

.D2

add

add

mpy

mpy

mpy

mpy

mpy

mpy

B

B

B

B

B

B

B

B

B

B

B

B

8

8

7

7

6

6

5

5

4

4

3

3

2

2

1

1

ldh m

ldh m

ldh m

ldh m

ldh m

ldh m

ldh m

ldh m

ldh m

ldh m

ldh m

ldh m

ldh m

ldh m

ldh m

ldh m

ldh n

ldh n

ldh n

ldh n

ldh n

ldh n

ldh n

ldh n

ldh n

ldh n

ldh n

ldh n

ldh n

ldh n

ldh n

ldh n

sub

sub

sub

sub

sub

sub

sub

sub

sub

sub

sub

sub

sub

sub

LOOP

LOOP

PROLOG

PROLOG