cugar::cuda::SyncFreeHashMap< KeyT, HashT, INVALID_KEY > Struct Template Reference

Detailed description

template<typename KeyT, typename HashT, KeyT INVALID_KEY = 0xFFFFFFFF>
struct cugar::cuda::SyncFreeHashMap< KeyT, HashT, INVALID_KEY >

This class implements a device-side Hash Map, allowing arbitrary threads from potentially different CTAs of a cuda kernel to add new entries at the same time.

The constructor of the class accepts pointers to the arrays representing the underlying data structure:

• an array of hashed keys
• an array of unique set entries
• an array of slots keeping track of the unique position where each inserted key has been mapped
• a pointer to a counter, keeping track of the number of set entries

Before starting to use the SynchronousHashMap, the array of hash slots has to be initialized to INVALID_KEY.

The difference between this class and the HashMap is that this class allows to call both insert() and find() at the same time, without interposing a global synchronization between them: the price is higher overhead (due to the need to use volatile writes and add memory fences).

#include <hash.h>

Public Methods
CUGAR_HOST_DEVICE	SyncFreeHashMap ()
CUGAR_HOST_DEVICE	SyncFreeHashMap (const uint32 _table_size, KeyT *_hash, KeyT *_unique, uint32 *_slots, uint32 *_count)
CUGAR_DEVICE bool	try_insert (const KeyT key, const HashT hash_code, const uint32 n)
CUGAR_DEVICE void	insert (const KeyT key, const HashT hash_code)
CUGAR_DEVICE bool	insert (const KeyT key, const HashT hash_code, uint32 *pos)
CUGAR_DEVICE uint32	find (const KeyT key, const HashT hash_code)
uint32	size () const
KeyT	get_unique (const uint32 i) const

Public Members
KeyT *	hash
KeyT *	unique
uint32 *	slots
uint32 *	count
uint32	table_size

Static Public Members
static const uint32	BUCKET_SIZE = 8

Constructor & Destructor Documentation

SyncFreeHashMap() [1/2]

template<typename KeyT, typename HashT, KeyT INVALID_KEY = 0xFFFFFFFF>

CUGAR_HOST_DEVICE cugar::cuda::SyncFreeHashMap< KeyT, HashT, INVALID_KEY >::SyncFreeHashMap ( )

inline

constructor

SyncFreeHashMap() [2/2]

template<typename KeyT, typename HashT, KeyT INVALID_KEY = 0xFFFFFFFF>

CUGAR_HOST_DEVICE cugar::cuda::SyncFreeHashMap< KeyT, HashT, INVALID_KEY >::SyncFreeHashMap ( const uint32  _table_size, KeyT *  _hash, KeyT *  _unique, uint32 *  _slots, uint32 *  _count  )

inline

constructor

Parameters

_table_size	the size of the hash table (needs to be a power of 2)
_hash	a pointer to the array of _table_size hashing slots - needs to be initialized to INVALID_KEY before first use
_unique	a pointer to the array where inserted entries will be stored - needs to be appropriately sized to contain all unique entries
_slots	a pointer to an array of _table_size entries keeping track of the unique position where each inserted key has been mapped
_count	a pointer to a single counter, used to keep track of how many unique entries have been inserted

Member Function Documentation

find()

template<typename KeyT, typename HashT, KeyT INVALID_KEY = 0xFFFFFFFF>

CUGAR_DEVICE uint32 cugar::cuda::SyncFreeHashMap< KeyT, HashT, INVALID_KEY >::find ( const KeyT  key, const HashT  hash_code  )

inline

find the unique slot associated to an inserted key

get_unique()

template<typename KeyT, typename HashT, KeyT INVALID_KEY = 0xFFFFFFFF>

KeyT cugar::cuda::SyncFreeHashMap< KeyT, HashT, INVALID_KEY >::get_unique ( const uint32  i ) const

inline

return the i-th unique element in the set

insert() [1/2]

template<typename KeyT, typename HashT, KeyT INVALID_KEY = 0xFFFFFFFF>

CUGAR_DEVICE void cugar::cuda::SyncFreeHashMap< KeyT, HashT, INVALID_KEY >::insert ( const KeyT  key, const HashT  hash_code  )

inline

insert an element with its hashing value

Parameters

key	the element to insert
hash_code	the hashing value

insert() [2/2]

template<typename KeyT, typename HashT, KeyT INVALID_KEY = 0xFFFFFFFF>

CUGAR_DEVICE bool cugar::cuda::SyncFreeHashMap< KeyT, HashT, INVALID_KEY >::insert ( const KeyT  key, const HashT  hash_code, uint32 *  pos  )

inline

insert an element with its hashing value and immediately get the unique slot where it's been inserted

Parameters

key	the element to insert
hash_code	the hashing value

size()

template<typename KeyT, typename HashT, KeyT INVALID_KEY = 0xFFFFFFFF>

uint32 cugar::cuda::SyncFreeHashMap< KeyT, HashT, INVALID_KEY >::size ( ) const

inline

return the size of the hash set

try_insert()

template<typename KeyT, typename HashT, KeyT INVALID_KEY = 0xFFFFFFFF>

CUGAR_DEVICE bool cugar::cuda::SyncFreeHashMap< KeyT, HashT, INVALID_KEY >::try_insert ( const KeyT  key, const HashT  hash_code, const uint32  n  )

inline

insert an element with its hashing value

Parameters

key	the element to insert
hash_code	the hashing value

---

The documentation for this struct was generated from the following file:

• C:/p4research/research/jpantaleoni/Fermat-Public/contrib/cugar/basic/cuda/hash.h