11.6 NULLSPACE OF DEPENDENCE MATRIX: THE BROADCAST SUBDOMAIN B
We will see in this section that the nullvector of the dependence matrix A of some variable v describes a subdomain B ⊂ 
. We will prove that all points in B contain the same instance of v.
11.6.1 The Nullspace of A
If the dependence matrix A is rank deficient, then the number of independent nullvectors associated with A is given by
(11.22)
where n is the number of indices of the algorithm. These nullvectors define the nullspace of matrix A.
Now assume a specific instance for the variable v(c). The following theorem identifies the points in that use that variable.
Theorem 11.1
Consider a particular nullvector e associated with a variable v. If two distinct points p1 and p2 use the same instance v(c), then the vector connecting the two points is a nullvector of A.
Proof:
Assume the two points use the same instance v(c). Substitute the two points into Eq. 11.21 to get
(11.23)
(11.24)
Subtracting the two equations, we get
(11.25)
We can write above equation as
(11.26)
where α ≠ 0. Therefore, the vector connecting the two points is a nullvector of A. Now assume the two points lie along the nullvector e. We can write
where α ≠ 0 since the two points are distinct. We can write
Thus, the vector connecting the two points is a nullvector.
Now assume that p1 is associated with the variable instance v(c1) and p2 is associated with the variable instance v(c2), but the vector connecting the two points is a nullvector of A. We can use Eq. 11.21 to get
(11.29)
(11.30)
Subtracting the above two equations, we get
From Eqs. 11.28 and 11.31, we have
(11.32)
This implies that c1 = c2. This proves the theorem.
We conclude from the above theorem that if the rank of the dependence matrix A associated with variable v is less than n, then there is a set of nullvectors of A associated with the variable v. This set defines a subdomain B. An instance of v is defined over a subdomain B ⊂ , which we call the broadcast subdomain. Every point in B sees the same instance of v.
Every variable v of the algorithm, indexed by the pair [A, a], is associated with a broadcast subdomain B whose basis vectors are the nullspace of A. The basis vectors will prove useful to pipeline the variable v and eliminate broadcasting.
The dimension of the broadcast subdomain B is given by [85]
(11.33)
where n is the dimension of the computation domain .
From Eq. 11.1, the index dependence of the input variable M1(i, j) is given by
(11.34)
The rank of A1 is two. This implies that its nullspace basis vector space is only one-dimensional (1-D), corresponding to one vector only. That nullspace basis vector could be given by
We note that the broadcast domain for M1(i, j) is 1-D and coincides with the k-axis. Figure 11.2a shows the broadcast domain B1 for the output variable instance M1(c1, c2). This output is calculated using all the points in whose indices are (c1 c2 k), where 0 ≤ k < K.
Figure 11.2 The broadcast subdomain for input and output variables. (a) Subdomain B1 for variable M1(c1, c2). (b) Subdomain B2 for variable M2(c1, c2). (c) Subdomain B3 for variable M3(c1, c2).
From Eq. 11.1, the index dependence of the input variable M2(i, k) is given by
(11.36)
The rank of A2 is two. This implies that its nullspace basis vectors space is only 1-D, corresponding to one vector only. That basis vector of its nullspace could be given by
Figure 11.2b shows the broadcast domain B2 for the input variable instance M2(c1, c2). This input is supplied to all the points in whose indices are (c1 j c2), where 0 ≤ j < J.
From Eq. 11.1, the index dependence of the input variables M3(k, j) is given by
(11.38)
The rank of A3 is two. This implies that its nullspace basis vectors space is only 1-D, corresponding to one vector only. That basis vector of its nullspace could be given by
(11.39)
Figure 11.2c shows the broadcast domain B3 for the input variable instance M3(c1, c2). This input is supplied to all the points in whose indices are (i c2 c1), where 0 ≤ i < I. Note that for this variable in particular, the first index c1 maps to the k-axis and the second index c2 maps to the j-axis. This stems from the fact that we indexed this input variable using the notation M3(k, j) in our original algorithm in Eq. 11.1.