10.6 NODE PROJECTION OPERATION
In Section 10.5, we discussed how we can associate a time step value to each point in the computation domain 
. In this section, we discuss how we can assign a processor or a thread to each point in the DAG. The combination of node scheduling and node projection will result in determination of the work done by each task at any given time step. The choice of the projection operation will impact the interthread or interprocessor communication, which is a very crucial factor in determining the speed of the execution of the algorithm.
The projection operation transforms our DAG in 
to a projected DAG in an integer space of reduced dimensionality 
where k < n. We label the new projected acyclic graph 
. Central to the projection operation is the projection matrix P and the projection direction d.
A subtle point to be noticed in the projection operation is that it controls the amount of workload assigned to each software thread for a multithreaded implementation or the workload assigned to each PE for a systolic array implementation. Just like affine scheduling, affine projection affords us little control over the workload assigned to a thread or a PE. However, nonlinear projection operations will give us very good control over the workload assigned to each thread or PE.
Definition 10.4
A projection matrix P is a k × n matrix of rank k that provides a many-to-one projection of points in 
to points in 
(10.41)
For our case, the DAG lies in the 2-D integer space 
. The projection matrix becomes a row vector
(10.42)
and a point p = [i j]t will map to the point
Definition 10.5
A projection direction d is a nullvector of the projection matrix P.
Proof of the above definition is found in Chapter 11. For our case, the nullvector associated with the projection matrix is given by
(10.43)
Conversely, if we start by selecting a certain projection direction d = [d1 d2]t, the associated projection matrix becomes P = [d2 –d1].
Points or nodes lying along the projection direction will be mapped onto the same point in the new projected DAG (
). A restriction on the projection direction d is that two points that lie on an equitemporal plane should not map to the same point in 
. This can be expressed as
(10.44)
The projection direction should not be orthogonal to the scheduling vector since this is contradictory to the requirements of parallelism—namely, all nodes executing simultaneously are assigned to the same thread or PE.
As a result of the above equation, choosing a particular scheduling vector restricts our options for valid projection directions. Let us work with our choice for the scheduling vector of s = [1 –1]. Therefore, we have three possible choices for projection directions:
(10.45)
(10.46)
(10.47)
All these projection directions are not orthogonal to our scheduling vector.