1 //------------------------------------------------------------------------------
2 // GB_subassign_03: C(I,J) += scalar ; using S
3 //------------------------------------------------------------------------------
4
5 // SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2021, All Rights Reserved.
6 // SPDX-License-Identifier: Apache-2.0
7
8 //------------------------------------------------------------------------------
9
10 // Method 03: C(I,J) += scalar ; using S
11
12 // M: NULL
13 // Mask_comp: false
14 // C_replace: false
15 // accum: present
16 // A: scalar
17 // S: constructed
18
19 // C is not bitmap: use GB_bitmap_assign instead
20
21 #include "GB_subassign_methods.h"
22
GB_subassign_03(GrB_Matrix C,const GrB_Index * I,const int64_t ni,const int64_t nI,const int Ikind,const int64_t Icolon[3],const GrB_Index * J,const int64_t nj,const int64_t nJ,const int Jkind,const int64_t Jcolon[3],const GrB_BinaryOp accum,const void * scalar,const GrB_Type atype,GB_Context Context)23 GrB_Info GB_subassign_03
24 (
25 GrB_Matrix C,
26 // input:
27 const GrB_Index *I,
28 const int64_t ni,
29 const int64_t nI,
30 const int Ikind,
31 const int64_t Icolon [3],
32 const GrB_Index *J,
33 const int64_t nj,
34 const int64_t nJ,
35 const int Jkind,
36 const int64_t Jcolon [3],
37 const GrB_BinaryOp accum,
38 const void *scalar,
39 const GrB_Type atype,
40 GB_Context Context
41 )
42 {
43
44 //--------------------------------------------------------------------------
45 // check inputs
46 //--------------------------------------------------------------------------
47
48 ASSERT (!GB_IS_BITMAP (C)) ;
49
50 //--------------------------------------------------------------------------
51 // S = C(I,J)
52 //--------------------------------------------------------------------------
53
54 GB_EMPTY_TASKLIST ;
55 GB_OK (GB_subassign_symbolic (S, C, I, ni, J, nj, true, Context)) ;
56
57 //--------------------------------------------------------------------------
58 // get inputs
59 //--------------------------------------------------------------------------
60
61 GB_GET_C ; // C must not be bitmap
62 const int64_t *restrict Ch = C->h ;
63 const int64_t *restrict Cp = C->p ;
64 const bool C_is_hyper = (Ch != NULL) ;
65 const int64_t Cnvec = C->nvec ;
66 GB_GET_S ;
67 GB_GET_ACCUM_SCALAR ;
68
69 //--------------------------------------------------------------------------
70 // Method 03: C(I,J) += scalar ; using S
71 //--------------------------------------------------------------------------
72
73 // Time: Optimal; must visit all IxJ, so Omega(|I|*|J|) is required.
74
75 // Entries in S are found and the corresponding entry in C replaced with
76 // the scalar.
77
78 // Method 01 and Method 03 are very similar.
79
80 //--------------------------------------------------------------------------
81 // Parallel: all IxJ (Methods 01, 03, 13, 15, 17, 19)
82 //--------------------------------------------------------------------------
83
84 GB_SUBASSIGN_IXJ_SLICE ;
85
86 //--------------------------------------------------------------------------
87 // phase 1: create zombies, update entries, and count pending tuples
88 //--------------------------------------------------------------------------
89
90 #pragma omp parallel for num_threads(nthreads) schedule(dynamic,1) \
91 reduction(+:nzombies)
92 for (taskid = 0 ; taskid < ntasks ; taskid++)
93 {
94
95 //----------------------------------------------------------------------
96 // get the task descriptor
97 //----------------------------------------------------------------------
98
99 GB_GET_IXJ_TASK_DESCRIPTOR_PHASE1 (iA_start, iA_end) ;
100
101 //----------------------------------------------------------------------
102 // compute all vectors in this task
103 //----------------------------------------------------------------------
104
105 for (int64_t j = kfirst ; j <= klast ; j++)
106 {
107
108 //------------------------------------------------------------------
109 // get jC, the corresponding vector of C
110 //------------------------------------------------------------------
111
112 int64_t jC = GB_ijlist (J, j, Jkind, Jcolon) ;
113
114 //------------------------------------------------------------------
115 // get S(iA_start:end,j)
116 //------------------------------------------------------------------
117
118 GB_GET_VECTOR_FOR_IXJ (S, iA_start) ;
119
120 //------------------------------------------------------------------
121 // C(I(iA_start,iA_end-1),jC) += scalar
122 //------------------------------------------------------------------
123
124 for (int64_t iA = iA_start ; iA < iA_end ; iA++)
125 {
126 bool found = (pS < pS_end) && (GBI (Si, pS, Svlen) == iA) ;
127 if (!found)
128 {
129 // ----[. A 1]----------------------------------------------
130 // S (i,j) is not present, the scalar is present
131 // [. A 1]: action: ( insert )
132 task_pending++ ;
133 }
134 else
135 {
136 // ----[C A 1] or [X A 1]-----------------------------------
137 // both S (i,j) and A (i,j) present
138 // [C A 1]: action: ( =C+A ): apply accum
139 // [X A 1]: action: ( undelete ): zombie lives
140 GB_C_S_LOOKUP ;
141 GB_withaccum_C_A_1_scalar ;
142 GB_NEXT (S) ;
143 }
144 }
145 }
146
147 GB_PHASE1_TASK_WRAPUP ;
148 }
149
150 //--------------------------------------------------------------------------
151 // phase 2: insert pending tuples
152 //--------------------------------------------------------------------------
153
154 GB_PENDING_CUMSUM ;
155
156 #pragma omp parallel for num_threads(nthreads) schedule(dynamic,1) \
157 reduction(&&:pending_sorted)
158 for (taskid = 0 ; taskid < ntasks ; taskid++)
159 {
160
161 //----------------------------------------------------------------------
162 // get the task descriptor
163 //----------------------------------------------------------------------
164
165 GB_GET_IXJ_TASK_DESCRIPTOR_PHASE2 (iA_start, iA_end) ;
166
167 //----------------------------------------------------------------------
168 // compute all vectors in this task
169 //----------------------------------------------------------------------
170
171 for (int64_t j = kfirst ; j <= klast ; j++)
172 {
173
174 //------------------------------------------------------------------
175 // get jC, the corresponding vector of C
176 //------------------------------------------------------------------
177
178 int64_t jC = GB_ijlist (J, j, Jkind, Jcolon) ;
179
180 //------------------------------------------------------------------
181 // get S(iA_start:end,j)
182 //------------------------------------------------------------------
183
184 GB_GET_VECTOR_FOR_IXJ (S, iA_start) ;
185
186 //------------------------------------------------------------------
187 // C(I(iA_start,iA_end-1),jC) += scalar
188 //------------------------------------------------------------------
189
190 for (int64_t iA = iA_start ; iA < iA_end ; iA++)
191 {
192 bool found = (pS < pS_end) && (GBI (Si, pS, Svlen) == iA) ;
193 if (!found)
194 {
195 // ----[. A 1]----------------------------------------------
196 // S (i,j) is not present, the scalar is present
197 // [. A 1]: action: ( insert )
198 int64_t iC = GB_ijlist (I, iA, Ikind, Icolon) ;
199 GB_PENDING_INSERT (scalar) ;
200 }
201 else
202 {
203 // both S (i,j) and A (i,j) present
204 GB_NEXT (S) ;
205 }
206 }
207 }
208
209 GB_PHASE2_TASK_WRAPUP ;
210 }
211
212 //--------------------------------------------------------------------------
213 // finalize the matrix and return result
214 //--------------------------------------------------------------------------
215
216 GB_SUBASSIGN_WRAPUP ;
217 }
218
219