Line data Source code
1 : /*----------------------------------------------------------------------------*/
2 : /* CP2K: A general program to perform molecular dynamics simulations */
3 : /* Copyright 2000-2026 CP2K developers group <https://cp2k.org> */
4 : /* */
5 : /* SPDX-License-Identifier: BSD-3-Clause */
6 : /*----------------------------------------------------------------------------*/
7 : #include "dbm_shard.h"
8 : #include "../offload/offload_mempool.h"
9 : #include "dbm_hyperparams.h"
10 :
11 : #include <assert.h>
12 : #include <omp.h>
13 : #include <stdbool.h>
14 : #include <stddef.h>
15 : #include <stdlib.h>
16 : #include <string.h>
17 :
18 : /*******************************************************************************
19 : * \brief Internal routine for finding a power of two greater than given number.
20 : * \author Ole Schuett
21 : ******************************************************************************/
22 10477741 : static int next_power2(const int start) {
23 10477741 : int candidate = 2;
24 36379613 : while (candidate < start) {
25 25901872 : candidate *= 2;
26 : }
27 10477741 : return candidate;
28 : }
29 :
30 : /*******************************************************************************
31 : * \brief Internal routine for finding a prime greater equal than given number.
32 : * \author Ole Schuett
33 : ******************************************************************************/
34 10477741 : static int next_prime(const int start) {
35 10477741 : int candidate = start, divisor = 0;
36 40524881 : while (divisor < candidate) {
37 567157217 : for (divisor = 2; divisor < candidate; divisor++) {
38 556679476 : if (candidate % divisor == 0) {
39 19569399 : candidate++;
40 19569399 : break;
41 : }
42 : }
43 : }
44 10477741 : return candidate;
45 : }
46 :
47 : /*******************************************************************************
48 : * \brief Internal routine for initializing a shard's hashtable.
49 : * \author Ole Schuett
50 : ******************************************************************************/
51 10477741 : static void hashtable_init(dbm_shard_t *shard) {
52 : // Choosing size as power of two allows to replace modulo with bitwise AND.
53 20955482 : shard->hashtable_size =
54 10477741 : next_power2(DBM_HASHTABLE_FACTOR * shard->nblocks_allocated);
55 10477741 : shard->hashtable_prime = next_prime(shard->hashtable_size);
56 10477741 : shard->hashtable = calloc(shard->hashtable_size, sizeof(int));
57 10477741 : assert(shard->hashtable != NULL);
58 10477741 : }
59 :
60 : /*******************************************************************************
61 : * \brief Internal routine for initializing a shard.
62 : * \author Ole Schuett
63 : ******************************************************************************/
64 2429922 : void dbm_shard_init(dbm_shard_t *shard) {
65 2429922 : shard->nblocks = 0;
66 2429922 : shard->nblocks_allocated = 0;
67 2429922 : shard->blocks = NULL;
68 2429922 : hashtable_init(shard);
69 2429922 : shard->data_size = 0;
70 2429922 : shard->data_promised = 0;
71 2429922 : shard->data_allocated = 0;
72 2429922 : shard->data = NULL;
73 2429922 : omp_init_lock(&shard->lock);
74 2429922 : }
75 :
76 : /*******************************************************************************
77 : * \brief Internal routine for copying content of shard_b into shard_a.
78 : * \author Ole Schuett
79 : ******************************************************************************/
80 619870 : void dbm_shard_copy(dbm_shard_t *shard_a, const dbm_shard_t *shard_b) {
81 619870 : assert(shard_a != NULL && shard_b != NULL);
82 :
83 619870 : if (shard_a->nblocks_allocated < shard_b->nblocks) {
84 592067 : free(shard_a->blocks);
85 592067 : shard_a->blocks = malloc(shard_b->nblocks * sizeof(dbm_block_t));
86 592067 : shard_a->nblocks_allocated = shard_b->nblocks;
87 592067 : assert(shard_a->blocks != NULL);
88 : }
89 619870 : shard_a->nblocks = shard_b->nblocks;
90 :
91 619870 : if (shard_a->hashtable_size < shard_b->hashtable_size) {
92 594886 : free(shard_a->hashtable);
93 594886 : shard_a->hashtable = malloc(shard_b->hashtable_size * sizeof(int));
94 594886 : assert(shard_a->hashtable != NULL);
95 : }
96 619870 : shard_a->hashtable_size = shard_b->hashtable_size;
97 619870 : shard_a->hashtable_prime = shard_b->hashtable_prime;
98 :
99 619870 : if (shard_a->data_allocated < shard_b->data_size) {
100 592067 : offload_mempool_host_free(shard_a->data);
101 1184134 : shard_a->data =
102 592067 : offload_mempool_host_malloc(shard_b->data_size * sizeof(double));
103 592067 : shard_a->data_allocated = shard_b->data_size;
104 592067 : assert(shard_a->data != NULL);
105 : }
106 619870 : shard_a->data_size = shard_b->data_size;
107 :
108 619870 : if (shard_b->nblocks != 0) {
109 592097 : assert(shard_a->blocks != NULL && shard_b->blocks != NULL);
110 592097 : memcpy(shard_a->blocks, shard_b->blocks,
111 592097 : shard_b->nblocks * sizeof(dbm_block_t));
112 : }
113 619870 : if (shard_b->hashtable_size != 0) {
114 619870 : assert(shard_a->hashtable != NULL && shard_b->hashtable != NULL);
115 619870 : memcpy(shard_a->hashtable, shard_b->hashtable,
116 619870 : shard_b->hashtable_size * sizeof(int));
117 : }
118 619870 : if (shard_b->data_size != 0) {
119 592097 : assert(shard_a->data != NULL && shard_b->data != NULL);
120 592097 : memcpy(shard_a->data, shard_b->data, shard_b->data_size * sizeof(double));
121 : }
122 619870 : }
123 :
124 : /*******************************************************************************
125 : * \brief Internal routine for releasing a shard.
126 : * \author Ole Schuett
127 : ******************************************************************************/
128 2429922 : void dbm_shard_release(dbm_shard_t *shard) {
129 2429922 : free(shard->blocks);
130 2429922 : free(shard->hashtable);
131 2429922 : offload_mempool_host_free(shard->data);
132 2429922 : omp_destroy_lock(&shard->lock);
133 2429922 : }
134 :
135 : /*******************************************************************************
136 : * \brief Private hash function based on Cantor pairing function.
137 : * https://en.wikipedia.org/wiki/Pairing_function#Cantor_pairing_function
138 : * Szudzik's elegant pairing proved to be too asymmetric wrt. row / col.
139 : * Using unsigned int to return a positive number even after overflow.
140 : * \author Ole Schuett
141 : ******************************************************************************/
142 276904332 : static inline unsigned int hash(const unsigned int row,
143 : const unsigned int col) {
144 276904332 : return (row + col) * (row + col + 1) / 2 + row; // Division by 2 is cheap.
145 : }
146 :
147 : /*******************************************************************************
148 : * \brief Internal routine for masking a slot in the hash-table.
149 : * \author Hans Pabst
150 : ******************************************************************************/
151 276904332 : static inline int hashtable_mask(const dbm_shard_t *shard) {
152 276904332 : return shard->hashtable_size - 1;
153 : }
154 :
155 : /*******************************************************************************
156 : * \brief Private routine for inserting a block into a shard's hashtable.
157 : * \author Ole Schuett
158 : ******************************************************************************/
159 148977365 : static void hashtable_insert(dbm_shard_t *shard, const int block_idx) {
160 148977365 : assert(0 <= block_idx && block_idx < shard->nblocks);
161 148977365 : const dbm_block_t *blk = &shard->blocks[block_idx];
162 148977365 : const unsigned int h = hash(blk->row, blk->col);
163 : // Bounded probe: at most hashtable_size steps (load factor < 1 guarantees
164 : // termination). Avoids unbounded scans when the slot variable wrapped around
165 : // via the mask but the inner iteration continued past the table end.
166 148977365 : int slot = (shard->hashtable_prime * h) & hashtable_mask(shard);
167 158620729 : for (int i = 0; i < shard->hashtable_size; ++i) { // linear probing
168 158620729 : if (shard->hashtable[slot] == 0) { // 0 means empty
169 148977365 : shard->hashtable[slot] = block_idx + 1; // 1-based
170 148977365 : return;
171 : }
172 9643364 : slot = (slot + 1) & hashtable_mask(shard);
173 : }
174 0 : assert(false);
175 : }
176 :
177 : /*******************************************************************************
178 : * \brief Internal routine for looking up a block from a shard.
179 : * \author Ole Schuett
180 : ******************************************************************************/
181 127926967 : dbm_block_t *dbm_shard_lookup(const dbm_shard_t *shard, const int row,
182 : const int col) {
183 : // Bounded probe count prevents scanning the entire table on a miss when
184 : // clusters exist (previous code could re-enter via slot wrap and re-scan).
185 127926967 : int slot = (shard->hashtable_prime * hash(row, col)) & hashtable_mask(shard);
186 136862515 : for (int i = 0; i < shard->hashtable_size; ++i) { // linear probing
187 136862515 : const int block_idx = shard->hashtable[slot];
188 136862515 : if (block_idx == 0) { // 1-based, 0 means empty
189 : return NULL; // block not found
190 : }
191 88480105 : assert(0 < block_idx && block_idx <= shard->nblocks);
192 88480105 : dbm_block_t *blk = &shard->blocks[block_idx - 1];
193 88480105 : if (blk->row == row && blk->col == col) {
194 : return blk;
195 : }
196 8935548 : slot = (slot + 1) & hashtable_mask(shard);
197 : }
198 : return NULL;
199 : }
200 :
201 : /*******************************************************************************
202 : * \brief Internal routine for allocating the metadata of a new block.
203 : * \author Ole Schuett
204 : ******************************************************************************/
205 59161141 : dbm_block_t *dbm_shard_promise_new_block(dbm_shard_t *shard, const int row,
206 : const int col, const int block_size) {
207 : // Grow blocks array if necessary.
208 59161141 : if (shard->nblocks_allocated < shard->nblocks + 1) {
209 8047819 : shard->nblocks_allocated = DBM_ALLOCATION_FACTOR * (shard->nblocks + 1);
210 8047819 : assert((shard->nblocks + 1) <= shard->nblocks_allocated);
211 8047819 : shard->blocks =
212 8047819 : realloc(shard->blocks, shard->nblocks_allocated * sizeof(dbm_block_t));
213 8047819 : assert(shard->blocks != NULL);
214 :
215 : // rebuild hashtable
216 8047819 : free(shard->hashtable);
217 8047819 : hashtable_init(shard);
218 97864043 : for (int i = 0; i < shard->nblocks; i++) {
219 89816224 : hashtable_insert(shard, i);
220 : }
221 : }
222 :
223 59161141 : const int new_block_idx = shard->nblocks;
224 59161141 : shard->nblocks++;
225 59161141 : dbm_block_t *new_block = &shard->blocks[new_block_idx];
226 59161141 : new_block->row = row;
227 59161141 : new_block->col = col;
228 59161141 : new_block->offset = shard->data_promised;
229 59161141 : shard->data_promised += block_size;
230 : // The data_size will be increased after the memory is allocated and zeroed.
231 59161141 : hashtable_insert(shard, new_block_idx);
232 59161141 : return new_block;
233 : }
234 :
235 : /*******************************************************************************
236 : * \brief Internal routine for allocating and zeroing any promised block's data.
237 : * \author Ole Schuett
238 : ******************************************************************************/
239 13131490 : void dbm_shard_allocate_promised_blocks(dbm_shard_t *shard) {
240 : // Reallocate data array if necessary.
241 13131490 : if (shard->data_allocated < shard->data_promised) {
242 2148774 : const double *data = shard->data;
243 2148774 : shard->data_allocated = DBM_ALLOCATION_FACTOR * shard->data_promised;
244 2148774 : assert(shard->data_promised <= shard->data_allocated);
245 4297548 : shard->data =
246 2148774 : offload_mempool_host_malloc(shard->data_allocated * sizeof(double));
247 2148774 : assert(shard->data != NULL);
248 2148774 : if (data != NULL) {
249 628153 : memcpy(shard->data, data, shard->data_size * sizeof(double));
250 628153 : offload_mempool_host_free(data);
251 : }
252 : }
253 :
254 : // Zero new blocks.
255 : // The following memset is usually the first touch of the memory, which leads
256 : // to frequent page faults. The executing thread determines the NUMA location
257 13131490 : if (shard->data_size < shard->data_promised) {
258 12717967 : const int tail = shard->data_promised - shard->data_size;
259 12717967 : memset(shard->data + shard->data_size, 0, tail * sizeof(double));
260 12717967 : shard->data_size = shard->data_promised;
261 : }
262 13131490 : }
263 :
264 : /*******************************************************************************
265 : * \brief Internal routine for getting block or promising a new one.
266 : * \author Ole Schuett
267 : ******************************************************************************/
268 32346169 : dbm_block_t *dbm_shard_get_or_promise_block(dbm_shard_t *shard, const int row,
269 : const int col,
270 : const int block_size) {
271 32346169 : dbm_block_t *existing_blk = dbm_shard_lookup(shard, row, col);
272 32346169 : if (existing_blk != NULL) {
273 : return existing_blk;
274 : } else {
275 30051536 : return dbm_shard_promise_new_block(shard, row, col, block_size);
276 : }
277 : }
278 :
279 : /*******************************************************************************
280 : * \brief Internal routine for getting block or allocating a new one.
281 : * \author Ole Schuett
282 : ******************************************************************************/
283 43006262 : dbm_block_t *dbm_shard_get_or_allocate_block(dbm_shard_t *shard, const int row,
284 : const int col,
285 : const int block_size) {
286 43006262 : dbm_block_t *existing_blk = dbm_shard_lookup(shard, row, col);
287 43006262 : if (existing_blk != NULL) {
288 : return existing_blk;
289 : }
290 :
291 : // Create a new block.
292 10961148 : dbm_block_t *new_blk =
293 10961148 : dbm_shard_promise_new_block(shard, row, col, block_size);
294 10961148 : dbm_shard_allocate_promised_blocks(shard);
295 :
296 10961148 : return new_blk;
297 : }
298 :
299 : // EOF
|
