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 : #ifndef DBM_SHARD_H
8 : #define DBM_SHARD_H
9 :
10 : #include <omp.h>
11 :
12 : #ifdef __cplusplus
13 : extern "C" {
14 : #endif
15 :
16 : /*******************************************************************************
17 : * \brief Internal struct for storing a block's metadata.
18 : * \author Ole Schuett
19 : ******************************************************************************/
20 : typedef struct {
21 : int row;
22 : int col;
23 : int offset;
24 : } dbm_block_t;
25 :
26 : /*******************************************************************************
27 : * \brief Internal struct for storing a matrix shard.
28 : * \author Ole Schuett
29 : ******************************************************************************/
30 : typedef struct {
31 : int nblocks;
32 : int nblocks_allocated;
33 : dbm_block_t *blocks;
34 :
35 : int hashtable_size; // should be a power of two
36 : int hashtable_prime; // should be a coprime of hashtable_size
37 : int *hashtable; // maps row/col to block numbers
38 :
39 : int data_promised; // ref'd by dbm_block_t.offset (not yet allocated)
40 : int data_allocated; // actually allocated (capacity of data buffer)
41 : int data_size; // actually allocated and initialized
42 : double *data; // potentially over-allocated (to amortize resizing)
43 :
44 : omp_lock_t lock; // used by dbm_put_block
45 : } dbm_shard_t;
46 :
47 : /*******************************************************************************
48 : * \brief Internal routine for initializing a shard.
49 : * \author Ole Schuett
50 : ******************************************************************************/
51 : void dbm_shard_init(dbm_shard_t *shard);
52 :
53 : /*******************************************************************************
54 : * \brief Internal routine for copying content of shard_b into shard_a.
55 : * \author Ole Schuett
56 : ******************************************************************************/
57 : void dbm_shard_copy(dbm_shard_t *shard_a, const dbm_shard_t *shard_b);
58 :
59 : /*******************************************************************************
60 : * \brief Internal routine for releasing a shard.
61 : * \author Ole Schuett
62 : ******************************************************************************/
63 : void dbm_shard_release(dbm_shard_t *shard);
64 :
65 : /*******************************************************************************
66 : * \brief Internal hash function based on Cantor pairing function.
67 : * https://en.wikipedia.org/wiki/Pairing_function#Cantor_pairing_function
68 : * Szudzik's elegant pairing proved to be too asymmetric wrt. row / col.
69 : * Using unsigned int to return a positive number even after overflow.
70 : * \author Ole Schuett
71 : ******************************************************************************/
72 247631271 : static inline unsigned int dbm_shard_hash(const unsigned int row,
73 : const unsigned int col) {
74 247631271 : return (row + col) * (row + col + 1) / 2 + row; // Division by 2 is cheap.
75 : }
76 :
77 : /*******************************************************************************
78 : * \brief Internal routine for the slot of a block in the shard's hashtable.
79 : * \author Hans Pabst
80 : ******************************************************************************/
81 247631271 : static inline int dbm_shard_slot(const dbm_shard_t *shard, const int row,
82 : const int col) {
83 247631271 : return (shard->hashtable_prime * dbm_shard_hash(row, col)) &
84 247631271 : (shard->hashtable_size - 1);
85 : }
86 :
87 : /*******************************************************************************
88 : * \brief Internal routine for the slot following the given one (probing).
89 : * \author Hans Pabst
90 : ******************************************************************************/
91 8960606 : static inline int dbm_shard_nextslot(const dbm_shard_t *shard, const int slot) {
92 8960606 : return (slot + 1) & (shard->hashtable_size - 1);
93 : }
94 :
95 : /*******************************************************************************
96 : * \brief Internal routines for prefetching an upcoming lookup in two stages:
97 : * the hashtable slot first, then (once cached) the block it refers to.
98 : * A lookup otherwise waits for two dependent cache misses.
99 : * \author Hans Pabst
100 : ******************************************************************************/
101 17171355 : static inline void dbm_shard_prefetch_slot(const dbm_shard_t *shard,
102 : const int row, const int col) {
103 17171355 : __builtin_prefetch(&shard->hashtable[dbm_shard_slot(shard, row, col)]);
104 17171355 : }
105 23900902 : static inline void dbm_shard_prefetch_block(const dbm_shard_t *shard,
106 : const int row, const int col) {
107 23900902 : const int block_idx = shard->hashtable[dbm_shard_slot(shard, row, col)];
108 23900902 : if (0 < block_idx) { // first probe only, 1-based, 0 means empty
109 19395732 : __builtin_prefetch(&shard->blocks[block_idx - 1]);
110 : }
111 23900902 : }
112 :
113 : /*******************************************************************************
114 : * \brief Internal routine for looking up a block from a shard.
115 : * \author Ole Schuett
116 : ******************************************************************************/
117 : dbm_block_t *dbm_shard_lookup(const dbm_shard_t *shard, const int row,
118 : const int col);
119 :
120 : /*******************************************************************************
121 : * \brief Internal routine for growing the block metadata of a shard such that
122 : * it holds nblocks blocks in total without growing again.
123 : * \author Ole Schuett and Hans Pabst
124 : ******************************************************************************/
125 : void dbm_shard_reserve(dbm_shard_t *shard, int nblocks);
126 :
127 : /*******************************************************************************
128 : * \brief Internal routine for allocating the metadata of a new block.
129 : * \author Ole Schuett
130 : ******************************************************************************/
131 : dbm_block_t *dbm_shard_promise_new_block(dbm_shard_t *shard, const int row,
132 : const int col, const int block_size);
133 :
134 : /*******************************************************************************
135 : * \brief Internal routine for allocating and zeroing any promised block's data.
136 : * \author Ole Schuett
137 : ******************************************************************************/
138 : void dbm_shard_allocate_promised_blocks(dbm_shard_t *shard);
139 :
140 : /*******************************************************************************
141 : * \brief Internal routine for getting block or promising a new one.
142 : * \author Ole Schuett
143 : ******************************************************************************/
144 : dbm_block_t *dbm_shard_get_or_promise_block(dbm_shard_t *shard, const int row,
145 : const int col,
146 : const int block_size);
147 :
148 : /*******************************************************************************
149 : * \brief Internal routine for getting block or allocating a new one.
150 : * \author Ole Schuett
151 : ******************************************************************************/
152 : dbm_block_t *dbm_shard_get_or_allocate_block(dbm_shard_t *shard, const int row,
153 : const int col,
154 : const int block_size);
155 :
156 : #ifdef __cplusplus
157 : }
158 : #endif
159 :
160 : #endif
161 :
162 : // EOF
|
