1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
|
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The mask, accumulator, and replace option} %%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:maskaccum}
After a GraphBLAS operation computes a result ${\bf T}$, (for example, ${\bf
T=AB}$ for \verb'GrB_mxm'), the results are assigned to an output matrix ${\bf
C}$ via the mask/ accumulator phase, written as ${\bf C \langle M \rangle = C
\odot T}$. This phase is affected by the \verb'GrB_REPLACE' option in the
descriptor, the presence of an optional binary accumulator operator ($\odot$),
the presence of the optional mask matrix ${\bf M}$, and the status of the mask
descriptor. The interplay of these options is summarized in
Table~\ref{tab:maskaccum}.
The mask ${\bf M}$ may be present, or not. It may be structural or valued, and
it may be complemented, or not. These options may be combined, for a total of
8 cases, although the structural/valued option as no effect if ${\bf M}$ is not
present. If ${\bf M}$ is not present and not complemented, then $m_{ij}$ is
implicitly true. If not present yet complemented, then all $m_{ij}$ entries are
implicitly zero; in this case, ${\bf T}$ need not be computed at all. Either
${\bf C}$ is not modified, or all its entries are cleared if the replace option
is enabled. If ${\bf M}$ is present, and the structural option is used, then
$m_{ij}$ is treated as true if it is an entry in the matrix (its value is
ignored). Otherwise, the value of $m_{ij}$ is used. In both cases, entries
not present are implicitly zero. These values are negated if the mask is
complemented. All of these various cases are combined to give a single
effective value of the mask at position ${ij}$.
The combination of all these options are presented in the
Table~\ref{tab:maskaccum}. The first column is the \verb'GrB_REPLACE' option.
The second column lists whether or not the accumulator operator is present.
The third column lists whether or not $c_{ij}$ exists on input to the
mask/accumulator phase (a dash means that it does not exist). The fourth
column lists whether or not the entry $t_{ij}$ is present in the result matrix
${\bf T}$. The mask column is the final effective value of $m_{ij}$, after
accounting for the presence of ${\bf M}$ and the mask options. Finally, the
last column states the result of the mask/accum step; if no action is listed in
this column, then $c_{ij}$ is not modified.
Several important observations can be made from this table. First,
if no mask is present (and the mask-complement descriptor option is not used),
then only the first half of the table is used. In this case, the \verb'GrB_REPLACE'
option has no effect. The entire matrix ${\bf C}$ is modified.
Consider the cases when $c_{ij}$ is present but $t_{ij}$ is not, and there is no
mask or the effective value of the mask is true for this ${ij}$ position. With
no accumulator operator, $c_{ij}$ is deleted. If the accumulator operator is
present and the replace option is not used, $c_{ij}$ remains unchanged.
\begin{table}
{\small
\begin{tabular}{lllll|l}
\hline
repl & accum & ${\bf C}$ & ${\bf T}$ & mask & action taken by ${\bf C \langle M \rangle = C \odot T}$ \\
\hline
- &- & $c_{ij}$ & $t_{ij}$ & 1 & $c_{ij} = t_{ij}$, update \\
- &- & - & $t_{ij}$ & 1 & $c_{ij} = t_{ij}$, insert \\
- &- & $c_{ij}$ & - & 1 & delete $c_{ij}$ because $t_{ij}$ not present \\
- &- & - & - & 1 & \\
- &- & $c_{ij}$ & $t_{ij}$ & 0 & \\
- &- & - & $t_{ij}$ & 0 & \\
- &- & $c_{ij}$ & - & 0 & \\
- &- & - & - & 0 & \\
\hline
yes&- & $c_{ij}$ & $t_{ij}$ & 1 & $c_{ij} = t_{ij}$, update \\
yes&- & - & $t_{ij}$ & 1 & $c_{ij} = t_{ij}$, insert \\
yes&- & $c_{ij}$ & - & 1 & delete $c_{ij}$ because $t_{ij}$ not present \\
yes&- & - & - & 1 & \\
yes&- & $c_{ij}$ & $t_{ij}$ & 0 & delete $c_{ij}$ (because of \verb'GrB_REPLACE') \\
yes&- & - & $t_{ij}$ & 0 & \\
yes&- & $c_{ij}$ & - & 0 & delete $c_{ij}$ (because of \verb'GrB_REPLACE') \\
yes&- & - & - & 0 & \\
\hline
- &yes & $c_{ij}$ & $t_{ij}$ & 1 & $c_{ij} = c_{ij} \odot t_{ij}$, apply accumulator \\
- &yes & - & $t_{ij}$ & 1 & $c_{ij} = t_{ij}$, insert \\
- &yes & $c_{ij}$ & - & 1 & \\
- &yes & - & - & 1 & \\
- &yes & $c_{ij}$ & $t_{ij}$ & 0 & \\
- &yes & - & $t_{ij}$ & 0 & \\
- &yes & $c_{ij}$ & - & 0 & \\
- &yes & - & - & 0 & \\
\hline
yes&yes & $c_{ij}$ & $t_{ij}$ & 1 & $c_{ij} = c_{ij} \odot t_{ij}$, apply accumulator \\
yes&yes & - & $t_{ij}$ & 1 & $c_{ij} = t_{ij}$, insert \\
yes&yes & $c_{ij}$ & - & 1 & \\
yes&yes & - & - & 1 & \\
yes&yes & $c_{ij}$ & $t_{ij}$ & 0 & delete $c_{ij}$ (because of \verb'GrB_REPLACE') \\
yes&yes & - & $t_{ij}$ & 0 & \\
yes&yes & $c_{ij}$ & - & 0 & delete $c_{ij}$ (because of \verb'GrB_REPLACE') \\
yes&yes & - & - & 0 & \\
\hline
\end{tabular}
}
\caption{Results of the mask/accumulator phase. \label{tab:maskaccum}}
\end{table}
When there is no mask and the mask \verb'GrB_COMP' option is not selected, the
table simplifies (Table~\ref{tab:maskaccum_nomask}). The \verb'GrB_REPLACE'
option no longer has any effect. The \verb'GrB_SECOND_T' binary operator when
used as the accumulator unifies the first cases, shown in
Table~\ref{tab:maskaccum_nomask_2nd}. The only difference now is the behavior
when $c_{ij}$ is present but $t_{ij}$ is not. Finally, the effect of
\verb'GrB_FIRST_T' as the accumulator is shown in
Table~\ref{tab:maskaccum_nomask_1st}.
\begin{table}[h]
\begin{center}
{\small
\begin{tabular}{lll|l}
\hline
accum & ${\bf C}$ & ${\bf T}$ & action taken by ${\bf C = C \odot T}$ \\
\hline
- & $c_{ij}$ & $t_{ij}$ & $c_{ij} = t_{ij}$, update \\
- & - & $t_{ij}$ & $c_{ij} = t_{ij}$, insert \\
- & $c_{ij}$ & - & delete $c_{ij}$ because $t_{ij}$ not present \\
- & - & - & \\
\hline
yes & $c_{ij}$ & $t_{ij}$ & $c_{ij} = c_{ij} \odot t_{ij}$, apply accumulator \\
yes & - & $t_{ij}$ & $c_{ij} = t_{ij}$, insert \\
yes & $c_{ij}$ & - & \\
yes & - & - & \\
\hline
\end{tabular}
}
\caption{When no mask is present (and not complemented).
\label{tab:maskaccum_nomask}}
\end{center}
\end{table}
\begin{table}[h]
\begin{center}
{\small
\begin{tabular}{lll|l}
\hline
accum & ${\bf C}$ & ${\bf T}$ & action taken by ${\bf C = C \odot T}$ \\
\hline
yes & $c_{ij}$ & $t_{ij}$ & $c_{ij} = t_{ij}$, apply \verb'GrB_SECOND' accumulator \\
yes & - & $t_{ij}$ & $c_{ij} = t_{ij}$, insert \\
yes & $c_{ij}$ & - & \\
yes & - & - & \\
\hline
\end{tabular}
}
\caption{No mask, with the SECOND operator as the accumulator.
\label{tab:maskaccum_nomask_2nd}}
\end{center}
\end{table}
\begin{table}[h]
\begin{center}
{\small
\begin{tabular}{lll|l}
\hline
accum & ${\bf C}$ & ${\bf T}$ & action taken by ${\bf C = C \odot T}$ \\
\hline
yes & $c_{ij}$ & $t_{ij}$ & \\
yes & - & $t_{ij}$ & $c_{ij} = t_{ij}$, insert \\
yes & $c_{ij}$ & - & \\
yes & - & - & \\
\hline
\end{tabular}
}
\caption{No Mask, with the FIRST operator as the accumulator.
\label{tab:maskaccum_nomask_1st}}
\end{center}
\end{table}
|
