1 //------------------------------------------------------------------------------ 2 // GB_AxB_saxpy3_fineHash_notM_phase: C<!M>=A*B, fine Hash, phase2 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 { 11 12 //-------------------------------------------------------------------------- 13 // phase2: fine hash task, C(:,j)<!M(:,j)>=A*B(:,j) 14 //-------------------------------------------------------------------------- 15 16 // M(:,j) is sparse/hyper and scattered into Hf 17 18 // Given Hf [hash] split into (h,f) 19 20 // h == 0 , f == 0 : unlocked and unoccupied. 21 // h == i+1, f == 1 : unlocked, occupied by M(i,j)=1. 22 // C(i,j) is ignored. 23 // h == i+1, f == 2 : unlocked, occupied by C(i,j). 24 // Hx is initialized. 25 26 // h == (anything), f == 3: locked. 27 28 // 1 -> 1 : to ignore, if M(i,j)=1 29 // 0 -> 3 : to lock, if i seen for first time 30 // 2 -> 3 : to lock, if i seen already 31 // 3 -> 2 : to unlock; now i has been seen 32 33 for ( ; pB < pB_end ; pB++) // scan B(:,j) 34 { 35 GB_GET_B_kj_INDEX ; // get index k of B(k,j) 36 GB_GET_A_k ; // get A(:,k) 37 if (aknz == 0) continue ; 38 GB_GET_B_kj ; // bkj = B(k,j) 39 40 // scan A(:,k) 41 for (int64_t pA = pA_start ; pA < pA_end ; pA++) 42 { 43 GB_GET_A_ik_INDEX ; // get index i of A(i,k) 44 GB_MULT_A_ik_B_kj ; // t = A(i,k) * B(k,j) 45 int64_t i1 = i + 1 ; // i1 = one-based index 46 int64_t i_unlocked = (i1 << 2) + 2 ; // (i+1,2) 47 int64_t i_masked = (i1 << 2) + 1 ; // (i+1,1) 48 for (GB_HASH (i)) // find i in hash table 49 { 50 int64_t hf ; 51 GB_ATOMIC_READ 52 hf = Hf [hash] ; // grab the entry 53 #if GB_HAS_ATOMIC 54 { 55 if (hf == i_unlocked) // if true, update C(i,j) 56 { 57 GB_ATOMIC_UPDATE_HX (hash, t) ;// Hx [.]+=t 58 break ; // C(i,j) has been updated 59 } 60 } 61 #endif 62 if (hf == i_masked) break ; // M(i,j)=1; ignore 63 int64_t h = (hf >> 2) ; 64 if (h == 0 || h == i1) 65 { 66 // h=0: unoccupied, h=i1: occupied by i 67 do // lock the entry 68 { 69 // do this atomically: 70 // { hf = Hf [hash] ; Hf [hash] |= 3 ; } 71 GB_ATOMIC_CAPTURE_INT64_OR (hf,Hf[hash],3) ; 72 } while ((hf & 3) == 3) ; // owner: f=0,1,2 73 if (hf == 0) // f == 0 74 { 75 // C(i,j) is a new entry in C(:,j) 76 // Hx [hash] = t 77 GB_ATOMIC_WRITE_HX (hash, t) ; 78 GB_ATOMIC_WRITE 79 Hf [hash] = i_unlocked ; // unlock entry 80 break ; 81 } 82 if (hf == i_unlocked) // f == 2 83 { 84 // C(i,j) already appears in C(:,j) 85 // Hx [hash] += t 86 GB_ATOMIC_UPDATE_HX (hash, t) ; 87 GB_ATOMIC_WRITE 88 Hf [hash] = i_unlocked ; // unlock entry 89 break ; 90 } 91 // hash table occupied, but not with i, 92 // or with i but M(i,j)=1 so C(i,j) ignored 93 GB_ATOMIC_WRITE 94 Hf [hash] = hf ; // unlock with prior value 95 } 96 } 97 } 98 } 99 } 100 101