X hits on this document

Powerpoint document

Chapter 2: Custom single-purpose processors - page 24 / 29

88 views

0 shares

0 downloads

0 comments

24 / 29

24

Embedded Systems Design: A Unified Hardware/Software Introduction, (c) 2000 Vahid/Givargis

Optimizing the original program (cont’)

0: int  x, y;

1: while (1) {

2:   while (!go_i);

3:   x = x_i;

4:   y = y_i;

5:   while  (x != y)  {

6:       if  (x < y)    

7:          y = y - x;

         else             

8:          x = x - y;

      }

9:    d_o = x;

   }

 0: int  x, y, r;

 1: while (1) {

 2:    while (!go_i);

        // x must be the larger number

 3:    if (x_i >= y_i)  {

 4:       x=x_i;

 5:       y=y_i;

        }

 6:    else {

 7:       x=y_i;

 8:       y=x_i;

        }

 9:    while  (y != 0)  {

10:       r = x % y;

11:       x = y;

12:       y = r;

        }

13:    d_o = x;

     }

original program

optimized program

replace the subtraction operation(s) with modulo operation in order to speed up program

GCD(42, 8) - 9 iterations to complete the loop

x and y values evaluated as follows : (42, 8), (43, 8), (26,8), (18,8), (10, 8), (2,8), (2,6), (2,4), (2,2).

GCD(42,8) - 3 iterations to complete the loop

x and y values evaluated as follows: (42, 8), (8,2), (2,0)

Document info
Document views88
Page views88
Page last viewedFri Dec 09 04:30:27 UTC 2016
Pages29
Paragraphs1664
Words3162

Comments