HammingOne

Overview

HammingOne is a high-performance tool designed to identify all pairs of long bit sequences with a Hamming distance of exactly 1.

Key Features

• GPU-Accelerated Computation: Leverages multiple CUDA threads to parallelize the computation, significantly improving performance on large datasets.
• GPU-Based Hash Map: Implements a custom hash map directly on the GPU using cuckoo hashing, optimized for efficient multi-threaded access.
• Efficient Memory Management: Utilizes CUDA's memory management for optimized data transfers between host and device.
• Fast Hash Computation: Uses precomputed powers of FNV prime for rapid hash calculations.

How It Works

1. Parallel Processing with CUDA: The program distributes the workload across multiple CUDA threads to handle large sets of bit sequences simultaneously.
2. Efficient Pair Detection: A GPU-implemented cuckoo hash map is used to efficiently manage and query bit sequences, enabling fast identification of pairs with a Hamming distance of 1.
3. Bucket Hashing: Utilizes multiple hashing functions within each bucket to ensure balanced data distribution and minimize collisions.

Usage Instructions

1. Generate Binary Vectors:

   • Use the binary vector generator located in the /generator directory.
   • This tool allows you to create sets of vectors with customizable sizes and lengths.
   • Each generated vector will have at least one corresponding pair with a Hamming distance of 1.

2. Run HammingOne:

   • The core program reads the file containing the generated vectors.
   • It processes the data to count and identify all pairs of vectors with a Hamming distance equal to 1.

Directory Structure

HammingOne/
├── generator/        # Tools for generating binary vectors
├── src/              # Source code for CUDA implementation and GPU hash map
└── README.md         # This file

System Requirements

• CUDA-compatible GPU
• NVIDIA CUDA Toolkit
• C++ compiler with CUDA support