Other Applications of Dependence

67 slides
0.3 MB
317 views

Similar Presentations

Presentation Transcript

1

Dependence in C and Hardware DesignAllen and Kennedy, Chapter 12 Presented by Tali Shragai

2

Today’s lecture…

3

IntroductionSo far, we’ve discussed dependence analysis in Fortran Dependence analysis applies to any language and translation context where arrays and loops are useful Application to C and C++ Modern features (pointers, structures…) Application to hardware design Language based approach

4

Outline Optimizing C Overview The challenges HW design Overview HW Description Languages (HDL) Optimizing simulation Synthesis optimization methods Summary

5

Problems of CC\C++ focuses on simplified software development, at the expense of optimizability Optimization may not be desired: Polling a keyboard example - while (!(t=*p)); Optimizer would move p outside the loop… Use of C\C++ has expanded into areas where optimization is required…

6

Problems of C - Examplevoid vadd(double *a, double *b, double *c, int n){ while(n--) *a++ = *b++ + *c++; } Would be easily vectorized & optimized in Fortran, but not in C: Pointers Memory locations accessed by pointers is not clear (unlike for arrays…) Aliasing C does not guarantee that arrays passed into subroutine do not overlap

7

Problems of C – Example (cont.)void vadd(double *a, double *b, double *c, int n){ while(n--) *a++ = *b++ + *c++; } Side-effect operators Pre\post increment operators conceal the index calculations for addressing arrays Optimizer focuses extra effort on transformations (induction-variable substitution…) Loops Fortran loops provides values and restrictions to simplify optimizations

8

Outline Optimizing C Overview The challenges HW design Overview HW Description Languages (HDL) Optimizing simulation Synthesis optimization methods Summary

9

PointersC optimizers’ most difficult challenge is unrestricted pointers: Hard to resolve indirect pointer access: pointer variable can point to different memory locations during its use Aliasing memory locations: memory location can be accessed by more than one pointer variable at any given time Resulting in a much more difficult and expensive dependence testing

10

Pointers dependence testingCompiler can replace pointers indirections like *p by subscripted array references n[e], for dependence testing. But another pointer q might access the same place  need to be replaced with the pseudo array n too… In the worst case, must assume that each pair of references is dependent!

11

Dependence testing strategiesSafety Assertions: Use compiler options / pragmas to indicate “disciplined” code Safe parameters All pointer parameters point to independent storage Safe pointers All pointer variables (parameter, local, global) point to independent storage Whole-Program Analysis: Without separate compilation, analyzing dependency in the entire program is solvable, but still unsatisfactory

12

Naming and StructuresIn Fortran, unlike C, a block of storage can be uniquely identified by a single name  simplify dependence analysis Dependence analysis requires a single name for all references to the same location C’s constructs complicate this: p; *p; **p; *(p+4); *(&p+4); p[1]*p**p&p

13

Naming and Structures (cont.)Troublesome structures Naming problem What is the name of ‘a.b’ ? Unions Allow different sized objects to overlap same storage Need to reduce references to the same common unit of smallest storage possible

14

LoopsLack of constraints in C Jumping into loop body is permitted Induction variable (if there’s any) can be modified in the body of the loop Loop increment value may also be changed Conditions controlling the initiation, increment, and termination of the loop have no constraints on their form Might be hard to identify a loop variable with start and end values

15

Loops (cont.)Rewrite while as a DO loop The induction variable: Only one! Must be initialized with the same value on all paths into the loop Must have one and only one increment in the loop The increment must be executed on every iteration The termination condition must match No jumps from outside of the loop body

16

Scoping and StaticsScoping rules might create extra aliasing Handled by creating unique symbols for variables with same name but different scopes Static variables File-static variable can only be modified by procedures that see its declaration. Access to the variable can be determined from scope information in the symbol table. Storing an address parameter in a static variable makes it accessible from any other procedures.

17

Problematic C DialectsSome of C code might look “tidy”, as in Fortran. “Messy” style conventions: Use of pointers instead of arrays Use of address and dereference operators Use of side effect operators Previously mapped to machine instructions Complicate the work of optimizers

18

Problematic C Dialects (cont.)Titan C Compiler: remove side effect operators! But, requires enhancements in some transformations Constant propagation Treat address operators as constants and propagate them where possible Replace generic pointer in a dereference with the actual address Expression simplification and recognition Need stronger recognition within expression where variable is actually the ‘base variable’

19

Problematic C Dialects (cont.)Conversion of pointers into array references Simplifies dependence testing Induction variable substitution need to enhanced Deal with indirect access to array references through pointers Recognize and remove usage of side-effect operators

20

C MiscellaneousVolatile variables Functions with these variables are best left without optimization Volatile code usually isn’t targeted for optimization (example: vector unit initialization) Setjmp and Longjmp Commonly used for error handling: Calling setjmp saves current context in a buffer. longjmp can then be called and bypass section of the calling chain Storing and loading current state of computation is complex when optimization is performed and variables are allocated to registers  No optimization used!

21

C Miscellaneous (cont.)Varags and stdargs Variable number of arguments printf(…) Implemented by a complier directive: Save all register parameters to the stack Access using pointer manipulation over the stack Pointer variable is an alias for many parameters in the program  No optimization

22

Outline Optimizing C Overview The challenges HW design Overview HW Description Languages (HDL) Optimizing simulation Synthesis optimization methods Summary

23

Hardware Design: OverviewIn the past, HW design was done at gate\transistor level Today, HW design is language-based, similarly to SW development Level of abstraction may vary Current trend is high level behavioral specification Key factor: compiler’s efficiency

24

Abstraction levels for HW DesignCircuit / Physical level Diagrams of electronic components Logic level Boolean equations Register transfer level (RTL) Control state transitions and data transfers Synthesis: convert RTL to gates and flip-flops System level Behavior expressed by variables, no timing Behavioral synthesis: select arithmetic units, impose timingMost Common!

25

Hardware DesignBehavior Synthesis is really a compilation problem Two fundamental tasks Verification (Simulation) Implementation (Synthesis) Optimization is essential for both: HW Simulation is inherently very slow Efficient synthesis raises the device’s value

26

Outline Optimizing C Overview The challenges HW design Overview HW Description Languages (HDL) Optimizing simulation Synthesis optimization methods Summary

Browse More Presentations

Last Updated: 8th March 2018

Recommended PPTs