Algorithms and Parallel Computing

17.6 DAG NODE PROJECTION

The projection operation is a many-to-one function that maps several nodes of the DAG onto a single node, which constitutes the resulting . Thus, several operations in the DAG are mapped to a single thread. The projection operation allows thread or hardware economy by multiplexing several operations in the DAG on a single node in . Chapters 10 and 11 explained how to perform the projection operation using a projection matrix P. To obtain the projection matrix, we need to define a desired projection direction d. The vector d belongs to the null- space of P. Since we are dealing with a 2-D DAG, matrix P is a row vector and d is a column vector. A valid projection direction d must satisfy the inequality

(17.27)

There are many projection vectors that satisfy Eq. 17.27 for the scheduling function s₁. For simplicity, we choose three of them:

(17.28)

(17.29)

(17.30)

The corresponding projection matrices are given by

(17.31)

(17.32)

(17.33) ...