ParallelSkipTrie.cuh

Go to the documentation of this file.

 
#pragma once
 
#include <cmath> // for log2
#include <cstddef> // for size_t
#include <memory> // for smart pointers
#include <random> // for random height generation
#include <vector> // for dynamic arrays
 
#include <unordered_map>
 
#include <fstream> // for file operations
 
#include "BitString.cuh" // for string representation
#include "SkipTrie.hpp" // for Direction
 
#include "cuda_utils.cuh"
#include "msw.cuh"
 
 
template<typename CHAR_T, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>
class ParallelSkipTrie : public SkipTrie<CHAR_T, CHAR_SIZE_BITS>
{
public:
    using ST = SkipTrie<CHAR_T, CHAR_SIZE_BITS>;
 
    using KEY_T = BitString<CHAR_T, CHAR_SIZE_BITS>;
 
    ParallelSkipTrie(size_t max_size);
 
    ~ParallelSkipTrie();
 
    using ST::get_random_height;
 
    bool insert(const KEY_T* key) noexcept;
 
    bool insert(const KEY_T* key, size_t height) noexcept;
 
protected:
    size_t m_max_size;
    
    uintmax_t* d_a;
    
    uintmax_t* d_largeblock;
    
    mutable size_t m_comparison_size;
    
    mutable size_t m_max_copied;
 
    using EqualOrSuccessor = ST::EqualOrSuccessor;
 
    EqualOrSuccessor find_equal_or_successor(const KEY_T* key, const bool require_level0) const noexcept;
 
    using ResultLCP = ST::ResultLCP;
 
    ResultLCP compare(const KEY_T* key1, const KEY_T* key2, size_t lcp) const noexcept;
};
 
template<typename CHAR_T, unsigned CHAR_SIZE_BITS>
ParallelSkipTrie<CHAR_T, CHAR_SIZE_BITS>::ParallelSkipTrie(size_t max_size)
    : ST(), m_max_size(max_size)
{
    // Calculate number of words needed to store max_size characters
    // Use ceiling division (max_size / ALPHA + potential remainder)
    size_t max_size_words = (max_size + KEY_T::ALPHA - 1) / KEY_T::ALPHA;
    
    // Allocate device memory for string comparison operations
    d_a = alloc_to_device<uintmax_t>(max_size_words);
    
    // Allocate larger block for more complex parallel operations
    d_largeblock = alloc_large_block_to_device(max_size_words);
}
 
template<typename CHAR_T, unsigned CHAR_SIZE_BITS>
ParallelSkipTrie<CHAR_T, CHAR_SIZE_BITS>::~ParallelSkipTrie()
{
    // Free GPU memory allocated for string comparison
    device_free(d_a);
    
    // Free GPU memory allocated for large block operations
    device_free(d_largeblock);
}
 
template<typename CHAR_T, unsigned CHAR_SIZE_BITS>
auto ParallelSkipTrie<CHAR_T, CHAR_SIZE_BITS>::compare(const KEY_T* key1, const KEY_T* key2, size_t lcp) const noexcept -> ResultLCP
{
    // Initialize result with equality and starting LCP value
    ResultLCP result = { std::strong_ordering::equal, lcp };
 
    while (true)
    {
        // Perform parallel comparison on GPU using the current comparison size
        // This is the core GPU-accelerated operation that makes ParallelSkipTrie faster
        auto [comparison, next_lcp] = key1->par_k_compare(*key2, lcp, m_comparison_size, d_a, d_largeblock, m_max_copied);
 
        // Update the result with comparison outcome and new LCP length
        result.result = comparison;
        result.lcp = next_lcp;
 
        if (comparison == std::strong_ordering::equal)
        {
            // If both keys match completely, we're done
            if (result.lcp == key1->size() && result.lcp == key2->size())
            {
                return result;
            }
 
            // Keys match so far but are longer - double comparison size for next iteration
            // This adaptive sizing improves performance by processing more characters at once
            m_comparison_size *= 2;
            lcp = result.lcp;
        }
        else
        {
            // Found a difference between keys, exit the loop
            break;
        }
    }
 
    // Halve comparison size for future operations, but don't go below minimum
    // This adapts the comparison granularity for optimal performance
    m_comparison_size = std::max(KEY_T::MIN_PAR_COMPARE_CHAR_SIZE, m_comparison_size / 2);
 
    return result;
}
 
template<typename CHAR_T, unsigned CHAR_SIZE_BITS>
bool ParallelSkipTrie<CHAR_T, CHAR_SIZE_BITS>::insert(const KEY_T* key) noexcept
{
    // Call the height-specific insert with a random height
    // This follows skip list standard practice of randomized height assignment
    return insert(key, get_random_height());
}
 
template<typename CHAR_T, unsigned CHAR_SIZE_BITS>
bool ParallelSkipTrie<CHAR_T, CHAR_SIZE_BITS>::insert(const KEY_T* key, size_t height) noexcept
{
    // Reset the GPU comparison parameters to their initial values
    // This ensures optimal starting point for parallel comparison operations
    m_comparison_size = KEY_T::MIN_PAR_COMPARE_CHAR_SIZE;
    m_max_copied = 0;
 
    // Delegate to the parent class implementation after initializing GPU parameters
    return ST::insert(key, height);
}
 
template<typename CHAR_T, unsigned CHAR_SIZE_BITS>
typename ParallelSkipTrie<CHAR_T, CHAR_SIZE_BITS>::EqualOrSuccessor ParallelSkipTrie<CHAR_T, CHAR_SIZE_BITS>::find_equal_or_successor(const KEY_T* key, const bool require_level0) const noexcept
{
    // Reset GPU comparison parameters to their initial values
    // This ensures consistent behavior across multiple search operations
    m_comparison_size = KEY_T::MIN_PAR_COMPARE_CHAR_SIZE;
    m_max_copied = 0;
 
    // Delegate to parent class implementation after initializing GPU parameters
    // The actual comparisons will use the overridden compare() method which uses GPU acceleration
    return ST::find_equal_or_successor(key, require_level0);
}