(git:27c966b)
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-2026 CP2K developers group <https://cp2k.org> */
4/* */
5/* SPDX-License-Identifier: BSD-3-Clause */
6/*----------------------------------------------------------------------------*/
7#include "dbm_shard.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 ******************************************************************************/
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;
36 // Divisors up to the square root suffice (division avoids an overflow).
37 for (int divisor = 2; divisor <= candidate / divisor; divisor++) {
38 if (candidate % divisor == 0) { // try the next candidate
39 ++candidate;
40 divisor = 1;
41 }
42 }
43 return candidate;
44}
45
46/*******************************************************************************
47 * \brief Internal routine for initializing a shard's hashtable.
48 * \author Ole Schuett
49 ******************************************************************************/
50static void hashtable_init(dbm_shard_t *shard) {
51 // Choosing size as power of two allows to replace modulo with bitwise AND.
52 shard->hashtable_size =
55 shard->hashtable = calloc(shard->hashtable_size, sizeof(int));
56 assert(shard->hashtable != NULL);
57}
58
59/*******************************************************************************
60 * \brief Internal routine for initializing a shard.
61 * \author Ole Schuett
62 ******************************************************************************/
64 shard->nblocks = 0;
65 shard->nblocks_allocated = 0;
66 shard->blocks = NULL;
67 hashtable_init(shard);
68 shard->data_size = 0;
69 shard->data_promised = 0;
70 shard->data_allocated = 0;
71 shard->data = NULL;
72 omp_init_lock(&shard->lock);
73}
74
75/*******************************************************************************
76 * \brief Internal routine for copying content of shard_b into shard_a.
77 * \author Ole Schuett
78 ******************************************************************************/
79void dbm_shard_copy(dbm_shard_t *shard_a, const dbm_shard_t *shard_b) {
80 assert(shard_a != NULL && shard_b != NULL);
81
82 if (shard_a->nblocks_allocated < shard_b->nblocks) {
83 free(shard_a->blocks);
84 shard_a->blocks = malloc(shard_b->nblocks * sizeof(dbm_block_t));
85 shard_a->nblocks_allocated = shard_b->nblocks;
86 assert(shard_a->blocks != NULL);
87 }
88 shard_a->nblocks = shard_b->nblocks;
89
90 if (shard_a->hashtable_size < shard_b->hashtable_size) {
91 free(shard_a->hashtable);
92 shard_a->hashtable = malloc(shard_b->hashtable_size * sizeof(int));
93 assert(shard_a->hashtable != NULL);
94 }
95 shard_a->hashtable_size = shard_b->hashtable_size;
96 shard_a->hashtable_prime = shard_b->hashtable_prime;
97
98 if (shard_a->data_allocated < shard_b->data_size) {
100 shard_a->data =
101 offload_mempool_host_malloc(shard_b->data_size * sizeof(double));
102 shard_a->data_allocated = shard_b->data_size;
103 assert(shard_a->data != NULL);
104 }
105 shard_a->data_size = shard_b->data_size;
106 shard_a->data_promised = 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 routine for inserting a block into a shard's hashtable.
137 * \author Ole Schuett
138 ******************************************************************************/
139static void hashtable_insert(dbm_shard_t *shard, const int block_idx) {
140 assert(0 <= block_idx && block_idx < shard->nblocks);
141 const dbm_block_t *blk = &shard->blocks[block_idx];
142 // Bounded probe: at most hashtable_size steps (load factor < 1 guarantees
143 // termination). Avoids unbounded scans when the slot variable wrapped around
144 // via the mask but the inner iteration continued past the table end.
145 int slot = dbm_shard_slot(shard, blk->row, blk->col);
146 for (int i = 0; i < shard->hashtable_size; ++i) { // linear probing
147 if (shard->hashtable[slot] == 0) { // 0 means empty
148 shard->hashtable[slot] = block_idx + 1; // 1-based
149 return;
150 }
151 slot = dbm_shard_nextslot(shard, slot);
152 }
153 assert(false);
154}
155
156/*******************************************************************************
157 * \brief Internal routine for looking up a block from a shard.
158 * \author Ole Schuett
159 ******************************************************************************/
160dbm_block_t *dbm_shard_lookup(const dbm_shard_t *shard, const int row,
161 const int col) {
162 // Bounded probe count prevents scanning the entire table on a miss when
163 // clusters exist (previous code could re-enter via slot wrap and re-scan).
164 int slot = dbm_shard_slot(shard, row, col);
165 for (int i = 0; i < shard->hashtable_size; ++i) { // linear probing
166 const int block_idx = shard->hashtable[slot];
167 if (block_idx == 0) { // 1-based, 0 means empty
168 return NULL; // block not found
169 }
170 assert(0 < block_idx && block_idx <= shard->nblocks);
171 dbm_block_t *blk = &shard->blocks[block_idx - 1];
172 if (blk->row == row && blk->col == col) {
173 return blk;
174 }
175 slot = dbm_shard_nextslot(shard, slot);
176 }
177 return NULL;
178}
179
180/*******************************************************************************
181 * \brief Internal routine for growing the block metadata of a shard such that
182 * it holds nblocks blocks in total without growing again.
183 * \author Ole Schuett and Hans Pabst
184 ******************************************************************************/
185void dbm_shard_reserve(dbm_shard_t *shard, const int nblocks) {
186 // Grow blocks array if necessary.
187 if (shard->nblocks_allocated < nblocks) {
188 shard->nblocks_allocated = DBM_ALLOCATION_FACTOR * nblocks;
189 assert(nblocks <= shard->nblocks_allocated);
190 shard->blocks =
191 realloc(shard->blocks, shard->nblocks_allocated * sizeof(dbm_block_t));
192 assert(shard->blocks != NULL);
193 }
194
195 // A copied hash table can hold fewer blocks than the block array.
196 if (shard->hashtable_size < DBM_HASHTABLE_FACTOR * nblocks) {
197 free(shard->hashtable);
198 hashtable_init(shard);
199 for (int i = 0; i < shard->nblocks; i++) {
200 hashtable_insert(shard, i);
201 }
202 }
203}
204
205/*******************************************************************************
206 * \brief Internal routine for allocating the metadata of a new block.
207 * \author Ole Schuett
208 ******************************************************************************/
210 const int col, const int block_size) {
211 dbm_shard_reserve(shard, shard->nblocks + 1);
212
213 const int new_block_idx = shard->nblocks;
214 shard->nblocks++;
215 dbm_block_t *new_block = &shard->blocks[new_block_idx];
216 new_block->row = row;
217 new_block->col = col;
218 new_block->offset = shard->data_promised;
219 shard->data_promised += block_size;
220 // The data_size will be increased after the memory is allocated and zeroed.
221 hashtable_insert(shard, new_block_idx);
222 return new_block;
223}
224
225/*******************************************************************************
226 * \brief Internal routine for allocating and zeroing any promised block's data.
227 * \author Ole Schuett
228 ******************************************************************************/
230 // Reallocate data array if necessary.
231 if (shard->data_allocated < shard->data_promised) {
232 const double *data = shard->data;
234 assert(shard->data_promised <= shard->data_allocated);
235 shard->data =
236 offload_mempool_host_malloc(shard->data_allocated * sizeof(double));
237 assert(shard->data != NULL);
238 if (data != NULL) {
239 memcpy(shard->data, data, shard->data_size * sizeof(double));
241 }
242 }
243
244 // Zero new blocks.
245 // The following memset is usually the first touch of the memory, which leads
246 // to frequent page faults. The executing thread determines the NUMA location
247 if (shard->data_size < shard->data_promised) {
248 const int tail = shard->data_promised - shard->data_size;
249 memset(shard->data + shard->data_size, 0, tail * sizeof(double));
250 shard->data_size = shard->data_promised;
251 }
252}
253
254/*******************************************************************************
255 * \brief Internal routine for getting block or promising a new one.
256 * \author Ole Schuett
257 ******************************************************************************/
259 const int col,
260 const int block_size) {
261 dbm_block_t *existing_blk = dbm_shard_lookup(shard, row, col);
262 if (existing_blk != NULL) {
263 return existing_blk;
264 } else {
265 return dbm_shard_promise_new_block(shard, row, col, block_size);
266 }
267}
268
269/*******************************************************************************
270 * \brief Internal routine for getting block or allocating a new one.
271 * \author Ole Schuett
272 ******************************************************************************/
274 const int col,
275 const int block_size) {
276 dbm_block_t *existing_blk = dbm_shard_lookup(shard, row, col);
277 if (existing_blk != NULL) {
278 return existing_blk;
279 }
280
281 // Create a new block.
282 dbm_block_t *new_blk =
283 dbm_shard_promise_new_block(shard, row, col, block_size);
285
286 return new_blk;
287}
288
289// EOF
#define DBM_ALLOCATION_FACTOR
#define DBM_HASHTABLE_FACTOR
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:139
static void hashtable_init(dbm_shard_t *shard)
Internal routine for initializing a shard's hashtable.
Definition dbm_shard.c:50
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:273
static int next_power2(const int start)
Internal routine for finding a power of two greater than given number.
Definition dbm_shard.c:22
void dbm_shard_reserve(dbm_shard_t *shard, const int nblocks)
Internal routine for growing the block metadata of a shard such that it holds nblocks blocks in total...
Definition dbm_shard.c:185
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:209
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:160
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:229
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:258
void dbm_shard_init(dbm_shard_t *shard)
Internal routine for initializing a shard.
Definition dbm_shard.c:63
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:79
static int dbm_shard_slot(const dbm_shard_t *shard, const int row, const int col)
Internal routine for the slot of a block in the shard's hashtable.
Definition dbm_shard.h:81
static int dbm_shard_nextslot(const dbm_shard_t *shard, const int slot)
Internal routine for the slot following the given one (probing).
Definition dbm_shard.h:91
static void const int const int i
void offload_mempool_host_free(const void *memory)
Internal routine for releasing memory back to the pool.
void * offload_mempool_host_malloc(const size_t size)
Internal routine for allocating host memory from the pool.
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:42
int * hashtable
Definition dbm_shard.h:37
omp_lock_t lock
Definition dbm_shard.h:44
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:40
int data_size
Definition dbm_shard.h:41
int hashtable_size
Definition dbm_shard.h:35
int data_promised
Definition dbm_shard.h:39