A Model for Recursive Algorithm - Type-DAG
Consider matrix multiply, for example C+=AB. Consider the simplest recursive algorithm you can think of, where the matrixes are logically composed of four quadrants:
|C0 C1 | |A0 A1 | |B0 B1 |
C = |C2 C3 | A = |A2 A3 | B = |B2 B3 |
We may write the algorithms as follows:
C += AB /* < m,n,p > */ :
if (m<=1 or n<=1 or p<=1)
c += a*b;
else {
C0 += A0*B0; /* < m/2+m%2,n/2+n%2,p/2+p%2 > */
C0 += A1*B2;
C1 += A0*B1;
C1 += A1*B3;
C2 += A2*B0;
C2 += A3*B2;
C3 += A2*B1;
C3 += A3*B3; /* < m/2,n/2,p/2 >*/
}
We indicate the size of the problem using
the notation <m,n,p> where m is the number of
rows of matrix A, n is the number of rows of B
and p is the number of columns of B.
We may wonder how many different problems we need to divide or to solve for a matrix multiply of size <17,17,17>. Or stated differently, we may wonder whether or not there are function calls that solve the same problem but on different data. We know that there are no more than 2*17^3 problems, but in practice there are only 34 different problems!
By showing the unfolding of the recursion calls, and presenting only one node per unique problem, it should be clear why there are only 34 different problems (for a problem <n,n,n>, we have proven that there are O(8log n) different problems).
For square matrices of size n x n, the data structure can be built in O(8logn) steps. This is the Type-DAG of the computation.
Type-DAG
A call graph is a static description of the relation among function calls in an application. Using the call graph, we can determine whether or not we may reach from a function f() a function g() at run time. If there is a path from f() to g(), the execution of the application may reach g() if, at any time, it reaches f(). (If there is no path, the execution that reaches f() it will not reach g().) The call graph is used for inter-procedural - data dependency - analysis. It is an extremely powerful abstraction.
Type-DAG is a data structure that captures the information of the unfolding of the call graph - which is the information about function calls available at run-time. The Type-DAG represents the control flow of an application using a Direct Acyclic Graph (DAG). Each node on the DAG represents a family of function calls having a particular type.
In fact, the Type-DAG is the result of a hybrid approach. Our approach requires a - very - partial execution of the application, like a profiler, but it is based on a static analysis reducing to a minimum the run-time information required.