Difference: CS455Team4 (14 vs. 15)

Revision 152008-04-11 - YiChu

Line: 1 to 1
 

Team 4 (Team Foo) Page

New results after optimization

Changed:
<
<
Benchmarks Starting Point P1:Adding Print Consolidation P2: Adding Copy Propagation P3: Adding loop unrolling
automaton 114 112 (-2) 97 (-15) 97
binrep 77 76 (-1) 72 (-4) 72
fibonacci 1098 1098 862 (-236) 730 (-132)
jacobi 10201117 10201117 10201117 8171485 (-2029632)
mandel 6477411 6477411 6477411 6477411
movingedge 1355 1355 1244 (-111) 902 (-342)
multiply 156 156 152 (-4) 24 (-128)
sort 10971 10971 8372 (-1699) 8100 (-272)
sort_insertion 2943 2943 2318 (-625) 2256 (-62)
tax 172 153 (-19) 117 (-36) 117
trivia 47 47 41 (-6) 40 (-1)
>
>
Benchmarks Starting Point P1:Adding Print Consolidation P2: Adding Copy Propagation P3: Adding loop unrolling Final optimization
automaton 114 112 (-2) 97 (-15) 97 90
binrep 77 76 (-1) 72 (-4) 72 72
fibonacci 1098 1098 862 (-236) 730 (-132) 730
jacobi 10201117 10201117 10201117 8171485 (-2029632) 8171485
mandel 6477411 6477411 6477411 6477411 6474447
movingedge 1355 1355 1244 (-111) 902 (-342) 901
multiply 156 156 152 (-4) 24 (-128) 11
sort 10971 10971 8372 (-1699) 8100 (-272) 7569
sort_insertion 2943 2943 2318 (-625) 2256 (-62) 2002
tax 172 153 (-19) 117 (-36) 117 104
trivia 47 47 41 (-6) 40 (-1) 40
 
  • The number in the bracket indicates the number of reduced statements compared to the previous phase.
Added:
>
>

Somthing to say...

  • we are kind of proud of our latest result. Thanks to everyone in our team, especially to our leader Bin ; ), and also thanks to our TA, Xiaoming who updates our ranking everyday, and last but definetely not least, many thanks to our professor Chen, who gave us such a nice opportunity to understand how much potentiality there lies to optimize our code and how much potentiality there lies in us to really do something about it. ^_^

Report on final optimization (2008-04-10)

  • Further improve value numbering to extended basic blocks, which has nice effect on reducing the number of statements for sort.c and sort_insertion.c. This optimization is really basic and effective, but it didn't strike us at first. : )

  • Copy propagation for returned values of function calls

We found that gcc uses a temporary variable to store the return value of a function call. For instance,

a.0 = foo();
a = a.0;
c = a + b;

By replacing a.0 with a, we can get rid of one copy statement and leave only a=foo(). This helps in cases when the program calls subroutine functions with returned values very often.

  • Empty Basic Blocks Merging

After dead code elimination, we are actually left with some empty basic blocks and this discovery provides us another chance for further optimization. For instance, in the tax.c the gimple code generated after dead code elimination is like this:

if (a<b) goto L2 else goto L3;

L2: //empty BB
   goto L4;

L3: //empty BB

L4:
   a = a+c;
   ...

It seems clear that block L2 and L3 are actually dummy blocks and serves only to increase useless statements. By merging these these empty blocks, we are improving our result.

 

Progress Report (2008-04-08)

  • Loop unrolling
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback