Next: Inter-Procedural Dependency Analysis
Up: Generation of Prefetch Thread
Previous: Generation of Prefetch Thread
The goal of intra-procedure dependency
analysis is to identify, inside a procedure, all
the variables and statements that disk access statements depend on.
Let
of a variable be the set of
statements that are involved, directly or indirectly,
in generating the value of in a procedure.
We use a simple and conservative approach as
follows to compute
:
- All the statements that directly update the variable ,
i.e., those that define , are
included in
.
- Compute the set that contains all the variables
used in the statements in
.
Then for each variable ,
include
into
.
Note that in a block structured language like
C, special care should be taken to restrict
the computation of
in Step 1
within the scope of the declaration of the variable .
For example in the code fragment below, lines 4 and 5 should
not be included in of the variable on
line 7.
1. void main(void){
2. int i;
3. i = 5;
4. { int i;
5. i = 6;
6. }
7. lseek(fp,i,SEEK_SET);
8. }
The above algorithm for computing
is conservative
and simple to implement. However, it might
include some redundant definitions of a variable
which never reaches any disk I/O statement.
Since the generated source code will
go through a final compilation phase, we expect
that the compiler could eliminate these redundant
statements with a more detailed data flow
analysis [1].
Given this algorithm to identify related set,
we use the following algorithm
to analyze a procedure and deduce the corresponding
prefetch thread:
- Include the disk access calls in the original program that operate
on prefetchable files in , the set of statements that are I/O related.
For each variable that appears in the disk access statements,
mark it as I/O related, compute
, and include the result into .
- For each flow-control statement, e.g.,
for, while, do-while, if-then-else, case,
if there is at least one member of
inside its body, mark all the variables
used in the boolean expression of the flow-control
statement as I/O related.
For each such variable ,
compute
, and include it in .
Repeat this step until stops growing in terms of program size.
- Include into the declaration statements of all variables
that are marked as I/O related.
- Insert into the necessary synchronization
calls, add send_XXX and receive_XXX calls to
transfer data between the threads, and rename
shared global variables to avoid simultaneous updates
from both threads.
- Finally, if a procedure does not contain any I/O related
statements after the algorithm completes,
then remove its statements from .
The above algorithm executes on each procedure iteratively
until the resulting I/O-related variable
set converges.
Next: Inter-Procedural Dependency Analysis
Up: Generation of Prefetch Thread
Previous: Generation of Prefetch Thread
chuan-kai yang
2002-04-15