// examples/cuda-checklist/histogram.cu // Two histogram kernels, checked bin by bin against a CPU histogram. // Checks correct output only. Nothing here is timed. #include #include #include #include #define CHECK(call) \ do { \ cudaError_t err_ = (call); \ if (err_ != cudaSuccess) { \ fprintf(stderr, "%s:%d: %s\n", __FILE__, __LINE__, \ cudaGetErrorString(err_)); \ exit(2); \ } \ } while (0) // region: basic-histogram // One thread per value. Every thread updates the one global histogram. __global__ void histogram_basic(const unsigned int *bin_of, unsigned int n, unsigned int *hist) { unsigned int i = blockIdx.x * blockDim.x + threadIdx.x; if (i < n) { atomicAdd(&hist[bin_of[i]], 1u); } } // endregion: basic-histogram // region: privatized-histogram // Each block counts its slice into a private copy in shared memory, // then adds the whole copy to the global histogram once. __global__ void histogram_privatized(const unsigned int *bin_of, unsigned int n, unsigned int bins, unsigned int *hist) { extern __shared__ unsigned int copy[]; // Zero the block's copy, with threads striding over the bins. for (unsigned int b = threadIdx.x; b < bins; b += blockDim.x) { copy[b] = 0; } __syncthreads(); // This block's contiguous slice of the input. gridDim.x must divide n, // or the n % gridDim.x leftover values would be skipped. unsigned int slice = n / gridDim.x; unsigned int start = blockIdx.x * slice; for (unsigned int i = threadIdx.x; i < slice; i += blockDim.x) { atomicAdd(©[bin_of[start + i]], 1u); } __syncthreads(); // Merge: every bin of the copy, empty ones included. for (unsigned int b = threadIdx.x; b < bins; b += blockDim.x) { atomicAdd(&hist[b], copy[b]); } } // endregion: privatized-histogram // Same rule as binOf in privatizationModel.mjs. static unsigned int bin_for(unsigned int i, unsigned int bins, bool skewed) { if (skewed) return (i % 2 == 0) ? 0u : ((i - 1) / 2) % bins; return i % bins; } int main() { const unsigned int n = 1u << 20; const unsigned int threads = 256; const unsigned int bin_choices[] = {7, 256}; const unsigned int block_choices[] = {64, 256, 1024, 4096}; unsigned int max_bins = 0; for (unsigned int b : bin_choices) max_bins = b > max_bins ? b : max_bins; const char *input_names[] = {"even", "skewed"}; int failures = 0; for (unsigned int blocks : block_choices) { if (n % blocks != 0) { fprintf(stderr, "blocks=%u does not divide n=%u\n", blocks, n); return 1; } } unsigned int *d_bin_of = nullptr; unsigned int *d_hist = nullptr; CHECK(cudaMalloc(&d_bin_of, n * sizeof(unsigned int))); CHECK(cudaMalloc(&d_hist, max_bins * sizeof(unsigned int))); for (unsigned int bins : bin_choices) { for (int s = 0; s < 2; ++s) { bool skewed = (s == 1); std::vector bin_of(n); std::vector expected(bins, 0); for (unsigned int i = 0; i < n; ++i) { bin_of[i] = bin_for(i, bins, skewed); expected[bin_of[i]]++; } unsigned int longest = 0; for (unsigned int c : expected) longest = c > longest ? c : longest; CHECK(cudaMemcpy(d_bin_of, bin_of.data(), n * sizeof(unsigned int), cudaMemcpyHostToDevice)); std::vector got(bins); // The basic kernel does not depend on the block count: run it once. CHECK(cudaMemset(d_hist, 0, bins * sizeof(unsigned int))); histogram_basic<<<(n + threads - 1) / threads, threads>>>( d_bin_of, n, d_hist); CHECK(cudaGetLastError()); CHECK(cudaDeviceSynchronize()); CHECK(cudaMemcpy(got.data(), d_hist, bins * sizeof(unsigned int), cudaMemcpyDeviceToHost)); bool basic_ok = (got == expected); printf("bins=%u input=%s basic=%s\n", bins, input_names[s], basic_ok ? "ok" : "FAIL"); if (!basic_ok) ++failures; for (unsigned int blocks : block_choices) { CHECK(cudaMemset(d_hist, 0, bins * sizeof(unsigned int))); histogram_privatized<<>>( d_bin_of, n, bins, d_hist); CHECK(cudaGetLastError()); CHECK(cudaDeviceSynchronize()); CHECK(cudaMemcpy(got.data(), d_hist, bins * sizeof(unsigned int), cudaMemcpyDeviceToHost)); bool privatized_ok = (got == expected); printf("bins=%u input=%s blocks=%u longest=%u privatized=%s\n", bins, input_names[s], blocks, longest, privatized_ok ? "ok" : "FAIL"); if (!privatized_ok) ++failures; } } } CHECK(cudaFree(d_bin_of)); CHECK(cudaFree(d_hist)); return failures ? 1 : 0; }