(git:858b7a1)
Loading...
Searching...
No Matches
dbm_shard.c
Go to the documentation of this file.
1/*----------------------------------------------------------------------------*/
2/* CP2K: A general program to perform molecular dynamics simulations */
3/* Copyright 2000-2025 CP2K developers group <https://cp2k.org> */
4/* */
5/* SPDX-License-Identifier: BSD-3-Clause */
6/*----------------------------------------------------------------------------*/
7#include <assert.h>
8#include <omp.h>
9#include <stdbool.h>
10#include <stddef.h>
11#include <stdlib.h>
12#include <string.h>
13
14#include "dbm_hyperparams.h"
15#include "dbm_mempool.h"
16#include "dbm_shard.h"
17
18/*******************************************************************************
19 * \brief Internal routine for finding a power of two greater than given number.
20 * \author Ole Schuett
21 ******************************************************************************/
22static int next_power2(const int start) {
23 int candidate = 2;
24 while (candidate < start) {
25 candidate *= 2;
26 }
27 return candidate;
28}
29
30/*******************************************************************************
31 * \brief Internal routine for finding a prime greater equal than given number.
32 * \author Ole Schuett
33 ******************************************************************************/
34static int next_prime(const int start) {
35 int candidate = start, divisor = 0;
36 while (divisor < candidate) {
37 for (divisor = 2; divisor < candidate; divisor++) {
38 if (candidate % divisor == 0) {
39 candidate++;
40 break;
41 }
42 }
43 }
44 return candidate;
45}
46
47/*******************************************************************************
48 * \brief Internal routine for initializing a shard's hashtable.
49 * \author Ole Schuett
50 ******************************************************************************/
51static void hashtable_init(dbm_shard_t *shard) {
52 // Choosing size as power of two allows to replace modulo with bitwise AND.
53 shard->hashtable_size =
56 shard->hashtable = calloc(shard->hashtable_size, sizeof(int));
57 assert(shard->hashtable != NULL);
58}
59
60/*******************************************************************************
61 * \brief Internal routine for initializing a shard.
62 * \author Ole Schuett
63 ******************************************************************************/
65 shard->nblocks = 0;
66 shard->nblocks_allocated = 0;
67 shard->blocks = NULL;
68 hashtable_init(shard);
69 shard->data_size = 0;
70 shard->data_promised = 0;
71 shard->data_allocated = 0;
72 shard->data = NULL;
73 omp_init_lock(&shard->lock);
74}
75
76/*******************************************************************************
77 * \brief Internal routine for copying content of shard_b into shard_a.
78 * \author Ole Schuett
79 ******************************************************************************/
80void dbm_shard_copy(dbm_shard_t *shard_a, const dbm_shard_t *shard_b) {
81 assert(shard_a != NULL && shard_b != NULL);
82
83 if (shard_a->nblocks_allocated < shard_b->nblocks) {
84 free(shard_a->blocks);
85 shard_a->blocks = malloc(shard_b->nblocks * sizeof(dbm_block_t));
86 shard_a->nblocks_allocated = shard_b->nblocks;
87 assert(shard_a->blocks != NULL);
88 }
89 shard_a->nblocks = shard_b->nblocks;
90
91 if (shard_a->hashtable_size < shard_b->hashtable_size) {
92 free(shard_a->hashtable);
93 shard_a->hashtable = malloc(shard_b->hashtable_size * sizeof(int));
94 assert(shard_a->hashtable != NULL);
95 }
96 shard_a->hashtable_size = shard_b->hashtable_size;
97 shard_a->hashtable_prime = shard_b->hashtable_prime;
98
99 if (shard_a->data_allocated < shard_b->data_size) {
100 dbm_mempool_host_free(shard_a->data);
101 shard_a->data =
102 dbm_mempool_host_malloc(shard_b->data_size * sizeof(double));
103 shard_a->data_allocated = shard_b->data_size;
104 assert(shard_a->data != NULL);
105 }
106 shard_a->data_size = shard_b->data_size;
107
108 if (shard_b->nblocks != 0) {
109 assert(shard_a->blocks != NULL && shard_b->blocks != NULL);
110 memcpy(shard_a->blocks, shard_b->blocks,
111 shard_b->nblocks * sizeof(dbm_block_t));
112 }
113 if (shard_b->hashtable_size != 0) {
114 assert(shard_a->hashtable != NULL && shard_b->hashtable != NULL);
115 memcpy(shard_a->hashtable, shard_b->hashtable,
116 shard_b->hashtable_size * sizeof(int));
117 }
118 if (shard_b->data_size != 0) {
119 assert(shard_a->data != NULL && shard_b->data != NULL);
120 memcpy(shard_a->data, shard_b->data, shard_b->data_size * sizeof(double));
121 }
122}
123
124/*******************************************************************************
125 * \brief Internal routine for releasing a shard.
126 * \author Ole Schuett
127 ******************************************************************************/
129 free(shard->blocks);
130 free(shard->hashtable);
132 omp_destroy_lock(&shard->lock);
133}
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 ******************************************************************************/
142static inline unsigned int hash(const unsigned int row,
143 const unsigned int col) {
144 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 ******************************************************************************/
151static inline int hashtable_mask(const dbm_shard_t *shard) {
152 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 ******************************************************************************/
159static void hashtable_insert(dbm_shard_t *shard, const int block_idx) {
160 assert(0 <= block_idx && block_idx < shard->nblocks);
161 const dbm_block_t *blk = &shard->blocks[block_idx];
162 const unsigned int h = hash(blk->row, blk->col);
163 int slot = (shard->hashtable_prime * h) & hashtable_mask(shard);
164 for (;; slot = (slot + 1) & hashtable_mask(shard)) { // linear probing
165 for (int i = slot; i < shard->hashtable_size; ++i) {
166 if (shard->hashtable[i] == 0) { // 0 means empty
167 shard->hashtable[i] = block_idx + 1; // 1-based
168 return;
169 }
170 }
171 }
172}
173
174/*******************************************************************************
175 * \brief Internal routine for looking up a block from a shard.
176 * \author Ole Schuett
177 ******************************************************************************/
178dbm_block_t *dbm_shard_lookup(const dbm_shard_t *shard, const int row,
179 const int col) {
180 int slot = (shard->hashtable_prime * hash(row, col)) & hashtable_mask(shard);
181 for (;; slot = (slot + 1) & hashtable_mask(shard)) { // linear probing
182 for (int i = slot; i < shard->hashtable_size; ++i) {
183 const int block_idx = shard->hashtable[i];
184 if (block_idx == 0) { // 1-based, 0 means empty
185 return NULL; // block not found
186 }
187 assert(0 < block_idx && block_idx <= shard->nblocks);
188 dbm_block_t *blk = &shard->blocks[block_idx - 1];
189 if (blk->row == row && blk->col == col) {
190 return blk;
191 }
192 }
193 }
194}
195
196/*******************************************************************************
197 * \brief Internal routine for allocating the metadata of a new block.
198 * \author Ole Schuett
199 ******************************************************************************/
201 const int col, const int block_size) {
202 // Grow blocks array if necessary.
203 if (shard->nblocks_allocated < shard->nblocks + 1) {
204 shard->nblocks_allocated = DBM_OVERCOMMIT_HOST * (shard->nblocks + 1);
205 assert((shard->nblocks + 1) <= shard->nblocks_allocated);
206 shard->blocks =
207 realloc(shard->blocks, shard->nblocks_allocated * sizeof(dbm_block_t));
208 assert(shard->blocks != NULL);
209
210 // rebuild hashtable
211 free(shard->hashtable);
212 hashtable_init(shard);
213 for (int i = 0; i < shard->nblocks; i++) {
214 hashtable_insert(shard, i);
215 }
216 }
217
218 const int new_block_idx = shard->nblocks;
219 shard->nblocks++;
220 dbm_block_t *new_block = &shard->blocks[new_block_idx];
221 new_block->row = row;
222 new_block->col = col;
223 new_block->offset = shard->data_promised;
224 shard->data_promised += block_size;
225 // The data_size will be increased after the memory is allocated and zeroed.
226 hashtable_insert(shard, new_block_idx);
227 return new_block;
228}
229
230/*******************************************************************************
231 * \brief Internal routine for allocating and zeroing any promised block's data.
232 * \author Ole Schuett
233 ******************************************************************************/
235
236 // Reallocate data array if necessary.
237 if (shard->data_promised > shard->data_allocated) {
238 const double *data = shard->data;
240 assert(shard->data_promised <= shard->data_allocated);
241 shard->data =
242 dbm_mempool_host_malloc(shard->data_allocated * sizeof(double));
243 assert(shard->data != NULL);
244 if (data != NULL) {
245 memcpy(shard->data, data, shard->data_size * sizeof(double));
247 }
248 }
249
250 // Zero new blocks.
251 // The following memset is usually the first touch of the memory, which leads
252 // to frequent page faults. The executing thread determines the NUMA location
253 if (shard->data_promised > shard->data_size) {
254 const int tail = shard->data_promised - shard->data_size;
255 memset(shard->data + shard->data_size, 0, tail * sizeof(double));
256 shard->data_size = shard->data_promised;
257 }
258}
259
260/*******************************************************************************
261 * \brief Internal routine for getting block or promising a new one.
262 * \author Ole Schuett
263 ******************************************************************************/
265 const int col,
266 const int block_size) {
267 dbm_block_t *existing_blk = dbm_shard_lookup(shard, row, col);
268 if (existing_blk != NULL) {
269 return existing_blk;
270 } else {
271 return dbm_shard_promise_new_block(shard, row, col, block_size);
272 }
273}
274
275/*******************************************************************************
276 * \brief Internal routine for getting block or allocating a new one.
277 * \author Ole Schuett
278 ******************************************************************************/
280 const int col,
281 const int block_size) {
282 dbm_block_t *existing_blk = dbm_shard_lookup(shard, row, col);
283 if (existing_blk != NULL) {
284 return existing_blk;
285 }
286
287 // Create a new block.
288 dbm_block_t *new_blk =
289 dbm_shard_promise_new_block(shard, row, col, block_size);
291
292 return new_blk;
293}
294
295// EOF
#define DBM_HASHTABLE_FACTOR
#define DBM_OVERCOMMIT_HOST
void dbm_mempool_host_free(const void *memory)
Private routine for releasing memory back to the pool.
void * dbm_mempool_host_malloc(size_t size)
Private routine for allocating host or device memory from the pool.
static void hashtable_insert(dbm_shard_t *shard, const int block_idx)
Private routine for inserting a block into a shard's hashtable.
Definition dbm_shard.c:159
static void hashtable_init(dbm_shard_t *shard)
Internal routine for initializing a shard's hashtable.
Definition dbm_shard.c:51
static int hashtable_mask(const dbm_shard_t *shard)
Internal routine for masking a slot in the hash-table.
Definition dbm_shard.c:151
void dbm_shard_release(dbm_shard_t *shard)
Internal routine for releasing a shard.
Definition dbm_shard.c:128
static int next_prime(const int start)
Internal routine for finding a prime greater equal than given number.
Definition dbm_shard.c:34
dbm_block_t * dbm_shard_get_or_allocate_block(dbm_shard_t *shard, const int row, const int col, const int block_size)
Internal routine for getting block or allocating a new one.
Definition dbm_shard.c:279
static int next_power2(const int start)
Internal routine for finding a power of two greater than given number.
Definition dbm_shard.c:22
dbm_block_t * dbm_shard_promise_new_block(dbm_shard_t *shard, const int row, const int col, const int block_size)
Internal routine for allocating the metadata of a new block.
Definition dbm_shard.c:200
dbm_block_t * dbm_shard_lookup(const dbm_shard_t *shard, const int row, const int col)
Internal routine for looking up a block from a shard.
Definition dbm_shard.c:178
void dbm_shard_allocate_promised_blocks(dbm_shard_t *shard)
Internal routine for allocating and zeroing any promised block's data.
Definition dbm_shard.c:234
static unsigned int hash(const unsigned int row, const unsigned int col)
Private hash function based on Cantor pairing function. https://en.wikipedia.org/wiki/Pairing_functio...
Definition dbm_shard.c:142
dbm_block_t * dbm_shard_get_or_promise_block(dbm_shard_t *shard, const int row, const int col, const int block_size)
Internal routine for getting block or promising a new one.
Definition dbm_shard.c:264
void dbm_shard_init(dbm_shard_t *shard)
Internal routine for initializing a shard.
Definition dbm_shard.c:64
void dbm_shard_copy(dbm_shard_t *shard_a, const dbm_shard_t *shard_b)
Internal routine for copying content of shard_b into shard_a.
Definition dbm_shard.c:80
static void const int const int i
Internal struct for storing a block's metadata.
Definition dbm_shard.h:20
Internal struct for storing a matrix shard.
Definition dbm_shard.h:30
double * data
Definition dbm_shard.h:43
int * hashtable
Definition dbm_shard.h:37
omp_lock_t lock
Definition dbm_shard.h:45
int nblocks_allocated
Definition dbm_shard.h:32
dbm_block_t * blocks
Definition dbm_shard.h:33
int hashtable_prime
Definition dbm_shard.h:36
int data_allocated
Definition dbm_shard.h:41
int data_size
Definition dbm_shard.h:42
int hashtable_size
Definition dbm_shard.h:35
int data_promised
Definition dbm_shard.h:39