This repository has been archived by the owner on May 16, 2021. It is now read-only.
forked from nkallima/sim-universal-construction
-
Notifications
You must be signed in to change notification settings - Fork 0
/
tvec.h
190 lines (146 loc) · 4.75 KB
/
tvec.h
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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include "primitives.h"
#ifndef _TVEC_H_
#define _TVEC_H_
#ifdef sparc
# define bitword_t uint32_t
# define _TVEC_DIVISION_SHIFT_BITS_ 5
# define _TVEC_MODULO_BITS_ 31
# define _TVEC_BIWORD_SIZE_ 32
#else
# define bitword_t uint64_t
# define _TVEC_DIVISION_SHIFT_BITS_ 6
# define _TVEC_MODULO_BITS_ 63
# define _TVEC_BIWORD_SIZE_ 64
#endif
/* automatic partial unrolling*/
#if N_THREADS <= 0
# error Unacceptable N_THREADS size
#elif N_THREADS <= _TVEC_BIWORD_SIZE_
# define _TVEC_CELLS_ 1
# define LOOP(EXPR, I) {I=0;EXPR;}
#elif N_THREADS <= 2 * _TVEC_BIWORD_SIZE_
# define _TVEC_CELLS_ 2
# define LOOP(EXPR, I) {I=0;EXPR; I++; EXPR;}
#elif N_THREADS <= 3 * _TVEC_BIWORD_SIZE_
# define _TVEC_CELLS_ 3
# define LOOP(EXPR, I) {I=0;EXPR; I++; EXPR; I++; EXPR;}
#else
# define _TVEC_CELLS_ ((N_THREADS >> _TVEC_DIVISION_SHIFT_BITS_) + 1)
# define LOOP(EXPR, I) {for (I = 0; I < _TVEC_CELLS_; I++) {EXPR;}}
#endif
typedef struct ToggleVector {
bitword_t cell[_TVEC_CELLS_];
} ToggleVector;
// Operations that handle banks of bits and no the whole vectors
// -------------------------------------------------------------
static inline int TVEC_GET_BANK_OF_BIT(int bit) {
#if N_THREADS > _TVEC_BIWORD_SIZE_
return bit >> _TVEC_DIVISION_SHIFT_BITS_;
#else
return 0;
#endif
}
static inline void TVEC_ATOMIC_COPY_BANKS(volatile ToggleVector *tv1, volatile ToggleVector *tv2, int bank) {
tv1->cell[bank] = tv2->cell[bank];
}
static inline void TVEC_ATOMIC_ADD_BANK(volatile ToggleVector *tv1, ToggleVector *tv2, int bank) {
#if _TVEC_BIWORD_SIZE_ == 32
FAA32(&tv1->cell[bank], tv2->cell[bank]);
#else
FAA64(&tv1->cell[bank], tv2->cell[bank]);
#endif
}
static inline void TVEC_NEGATIVE_BANK(ToggleVector *tv1, ToggleVector *tv2, int bank) {
tv1->cell[bank] = -tv2->cell[bank];
}
static inline void TVEC_XOR_BANKS(ToggleVector *res, ToggleVector *tv1, ToggleVector *tv2, int bank) {
res->cell[bank] = tv1->cell[bank] ^ tv2->cell[bank];
}
static inline void TVEC_AND_BANKS(ToggleVector *res, ToggleVector *tv1, ToggleVector *tv2, int bank) {
res->cell[bank] = tv1->cell[bank] & tv2->cell[bank];
}
// Operations that handle whole vectors of bits
// --------------------------------------------
static inline ToggleVector TVEC_NEGATIVE(ToggleVector tv) {
int i = 0;
ToggleVector res;
LOOP(res.cell[i] = -tv.cell[i], i);
return res;
}
static inline void TVEC_REVERSE_BIT(ToggleVector *tv1, int bit) {
#if N_THREADS > _TVEC_BIWORD_SIZE_
int i, offset;
i = bit >> _TVEC_DIVISION_SHIFT_BITS_;
offset = bit & _TVEC_MODULO_BITS_;
tv1->cell[i] ^= 1L << offset;
#else
tv1->cell[0] ^= 1L << bit;
#endif
}
static inline void TVEC_SET_BIT(ToggleVector *tv1, int bit) {
#if N_THREADS > _TVEC_BIWORD_SIZE_
int i, offset;
i = bit >> _TVEC_DIVISION_SHIFT_BITS_;
offset = bit & _TVEC_MODULO_BITS_;
tv1->cell[i] |= 1L << offset;
#else
tv1->cell[0] |= 1L << bit;
#endif
}
static inline void TVEC_SET_ZERO(ToggleVector *tv1) {
int i;
LOOP(tv1->cell[i] = 0L, i);
}
static inline bool TVEC_IS_SET(ToggleVector tv1, int pid) {
#if N_THREADS > _TVEC_BIWORD_SIZE_
int i, offset;
i = pid >> _TVEC_DIVISION_SHIFT_BITS_;
offset = pid & _TVEC_MODULO_BITS_;
// Commented code is optimized to avoid branches
// if ( (tv1.cell[i] & (1L << offset)) == 0) return false;
// else return true;
return (tv1.cell[i] >> offset) & 1;
#else
// Commented code is optimized to avoid branches
// if ( (tv1.cell[i] & (1L << offset)) == 0) return false;
// else return true;
return (tv1.cell[0] >> pid) & 1;
#endif
}
static inline ToggleVector TVEC_OR(ToggleVector tv1, ToggleVector tv2) {
int i;
ToggleVector res;
LOOP(res.cell[i] = tv1.cell[i] | tv2.cell[i], i);
return res;
}
static inline ToggleVector TVEC_AND(ToggleVector tv1, ToggleVector tv2) {
int i;
ToggleVector res;
LOOP(res.cell[i] = tv1.cell[i] & tv2.cell[i], i);
return res;
}
static inline ToggleVector TVEC_XOR(ToggleVector tv1, ToggleVector tv2) {
int i;
ToggleVector res;
LOOP(res.cell[i] = tv1.cell[i] ^ tv2.cell[i], i);
return res;
}
static inline int TVEC_COUNT_BITS(ToggleVector tv) {
int i, count;
count = 0;
LOOP(count += nonZeroBits(tv.cell[i]), i);
return count;
}
// pthread_mutex_t lock;
static void binprintf(int v)
{
// pthread_mutex_lock(&lock);
unsigned int mask = 1 << sizeof (int) * CHAR_BIT - 1;
while(mask) {
sync_printf("%d", (v&mask ? 1 : 0));
mask >>= 1;
}
sync_printf("%s\n","");
// pthread_mutex_unlock(&lock);
}
#endif