Optimizing Single Purpose Processor

Group Members:
Sakshyam Luitel (078BCT073)
Sijan Khadka(078BCT088)
Sudip Basnet(078BCT092)
Sujan Thapaliya(078BCT094)
 Optimizing single-purpose
processors
• Optimization is the task of making design metric
values the best possible
• Optimization opportunities
– original program
– FSMD
– datapath
– FSM

2
 Optimizing the original program

• Analyze program attributes and look for areas of

possible improvement
– number of computations
– size of variable
– time and space complexity
– operations used
• multiplication and division very expensive

3
Optimizing the original program (cont’)
original program optimized program
0: int x, y; 0: int x, y, r;
1: while (1) { 1: while (1) {
2: while (!go_i); 2: while (!go_i);
3: x = x_i; // x must be the larger number
4: y = y_i; 3: if (x_i >= y_i) {
5: while (x != y) { 4: x=x_i;
replace the subtraction
6: if (x < y) 5: y=y_i;
operation(s) with modulo
7: y = y - x; }
operation in order to speed
else 6: else {
up program
8: x = x - y; 7: x=y_i;
} 8: y=x_i;
9: d_o = x; }
} 9: while (y != 0) {
10: r = x % y;
11: x = y;
12: y = r;
}
13: d_o = x;
}
GCD(42, 8) - 9 iterations to complete the loop GCD(42,8) - 3 iterations to complete the loop
x and y values evaluated as follows : (42, 8), (43, 8), x and y values evaluated as follows: (42, 8), (8,2),
(26,8), (18,8), (10, 8), (2,8), (2,6), (2,4), (2,2). (2,0)

4
 Optimizing the FSMD

• Areas of possible improvements

– merge states
• states with constants on transitions can be eliminated,
transition taken is already known
• states with independent operations can be merged
– separate states
• states which require complex operations (a*b*c*d) can be
broken into smaller states to reduce hardware size
– scheduling

5
 Optimizing the FSMD (cont.)
int x, y; !1 optimized FSMD
original FSMD
1:
int x, y;
1 !(!go_i) eliminate state 1 – transitions have constant values 2:
2:
go_i !go_i
!go_i
2-J: x = x_i
3: y = y_i
merge state 2 and state 2J – no loop operation in
3: x = x_i between them
5:

4: y = y_i x<y x>y

merge state 3 and state 4 – assignment operations are
independent of one another 7: y = y -x 8: x = x - y
5: !(x!=y)

x!=y
9: d_o = x
6: merge state 5 and state 6 – transitions from state 6 can
x<y !(x<y) be done in state 5
y = y -x x=x-y
7: 8:
eliminate state 5J and 6J – transitions from each state
6-J: can be done from state 7 and state 8, respectively

5-J:
eliminate state 1-J – transition from state 1-J can be
d_o = x done directly from state 9
9:

1-J:

6
 Optimizing the datapath

• Sharing of functional units

– one-to-one mapping, as done previously, is not
necessary
– if same operation occurs in different states, they can
share a single functional unit
• Multi-functional units
– ALUs support a variety of operations, it can be shared
among operations occurring in different states

7
 Optimizing the FSM

• State encoding
– task of assigning a unique bit pattern to each state in
an FSM
– size of state register and combinational logic vary
– can be treated as an ordering problem
• State minimization
– task of merging equivalent states into a single state
• state equivalent if for all possible input combinations the two
states generate the same outputs and transitions to the next
same state

8
Thank You!