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
|
//------------------------------------------------------------------------------
// GB_AxB_saxpy3_fineHash_notM_phase2: C<!M>=A*B, fine Hash, phase2
//------------------------------------------------------------------------------
// SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2022, All Rights Reserved.
// SPDX-License-Identifier: Apache-2.0
//------------------------------------------------------------------------------
{
//--------------------------------------------------------------------------
// phase2: fine hash task, C(:,j)<!M(:,j)>=A*B(:,j)
//--------------------------------------------------------------------------
// M(:,j) is sparse/hyper and scattered into Hf
// Given Hf [hash] split into (h,f)
// h == 0 , f == 0 : unlocked and unoccupied.
// h == i+1, f == 1 : unlocked, occupied by M(i,j)=1.
// C(i,j) is ignored.
// h == i+1, f == 2 : unlocked, occupied by C(i,j).
// Hx is initialized.
// h == (anything), f == 3: locked.
// 1 -> 1 : to ignore, if M(i,j)=1
// 0 -> 3 : to lock, if i seen for first time
// 2 -> 3 : to lock, if i seen already
// 3 -> 2 : to unlock; now i has been seen
for ( ; pB < pB_end ; pB++) // scan B(:,j)
{
GB_GET_B_kj_INDEX ; // get index k of B(k,j)
GB_GET_A_k ; // get A(:,k)
if (aknz == 0) continue ;
GB_GET_B_kj ; // bkj = B(k,j)
// scan A(:,k)
for (int64_t pA = pA_start ; pA < pA_end ; pA++)
{
GB_GET_A_ik_INDEX ; // get index i of A(i,k)
GB_MULT_A_ik_B_kj ; // t = A(i,k) * B(k,j)
int64_t i1 = i + 1 ; // i1 = one-based index
int64_t i_unlocked = (i1 << 2) + 2 ; // (i+1,2)
int64_t i_masked = (i1 << 2) + 1 ; // (i+1,1)
for (GB_HASH (i)) // find i in hash table
{
int64_t hf ;
GB_ATOMIC_READ
hf = Hf [hash] ; // grab the entry
#if GB_HAS_ATOMIC
{
if (hf == i_unlocked) // if true, update C(i,j)
{
GB_ATOMIC_UPDATE_HX (hash, t) ;// Hx [.]+=t
break ; // C(i,j) has been updated
}
}
#endif
if (hf == i_masked) break ; // M(i,j)=1; ignore
int64_t h = (hf >> 2) ;
if (h == 0 || h == i1)
{
// h=0: unoccupied, h=i1: occupied by i
do // lock the entry
{
// do this atomically:
// { hf = Hf [hash] ; Hf [hash] |= 3 ; }
GB_ATOMIC_CAPTURE_INT64_OR (hf,Hf[hash],3) ;
} while ((hf & 3) == 3) ; // owner: f=0,1,2
if (hf == 0) // f == 0
{
// C(i,j) is a new entry in C(:,j)
// Hx [hash] = t
GB_ATOMIC_WRITE_HX (hash, t) ;
GB_ATOMIC_WRITE
Hf [hash] = i_unlocked ; // unlock entry
break ;
}
if (hf == i_unlocked) // f == 2
{
// C(i,j) already appears in C(:,j)
// Hx [hash] += t
GB_ATOMIC_UPDATE_HX (hash, t) ;
GB_ATOMIC_WRITE
Hf [hash] = i_unlocked ; // unlock entry
break ;
}
// hash table occupied, but not with i,
// or with i but M(i,j)=1 so C(i,j) ignored
GB_ATOMIC_WRITE
Hf [hash] = hf ; // unlock with prior value
}
}
}
}
}
|
