PARALLEL GRAPH SEARCH · SIMULATED GPU · 5 × 5 BOARD

ห้องทดลอง Knight’s Tour
ด้วย Parallel BFS

ดู GPU core จำลอง 25 ตัวส่ง state ไปยัง core ปลายทางที่ feasible ทิ้ง dead end ทำงานพร้อมกันทีละระดับ และค้นหา complete open tours บนกระดาน 5×5 จนครบ

25-bit visited maskall-to-all interconnectlevel-synchronous inboxesfeasible core-to-core messagesdead-end pruning(mask, endpoint) deduplicationclosed tour = impossible by parity
GPU: checking…
ทำไมมีเฉพาะ open tour? Knight สลับสีช่องทุก move วงจรปิดจึงต้องมีจำนวนช่องเป็นเลขคู่ แต่ 5×5 มี 25 ช่อง ดังนั้น closed tour เป็นไปไม่ได้ทางคณิตศาสตร์ และ PBFS ชุดนี้แจกแจง complete open tours
จำนวน move0
Frontier25
สร้างลูก0
Dead ends0
Duplicates0
สำรวจสะสม0

ตัวอย่าง state ใน frontier

STATE 1 / 25Path: 1mask 0x0000001

25 board-resident GPU cores

VERTEX-CENTRIC · BULK SYNCHRONOUS
SOURCE CORE ↓ · DESTINATION CORE →0 routed messages

ประวัติแต่ละระดับ

GLOBAL BARRIER AFTER EACH ROW
DepthFrontierExpandedGeneratedDead endsDuplicates
พร้อมที่ depth 0 แต่ละช่องคือหนึ่ง core และ state เริ่มต้นอยู่ใน inbox ของ core ประจำช่องนั้น

1. Frontier parallelism

worker ไม่ได้ลองครบทั้ง 25 ช่อง แต่รับหนึ่ง state แล้วไล่เฉพาะบิตใน legal-move mask ที่ precompute ไว้ โดย core v ผูกกับช่อง v และรับ state ที่มี endpoint อยู่ช่องนั้น จากนั้นส่ง child state ตรงไปยัง core ของช่องปลายทาง

source = endpointCore
available = KNIGHT[source] & ~visited
while (available) {
  next = popLeastBit(available)
  emit(visited | bit(next), next)
}

2. Dead-end pruning

ถ้า partial path ไม่มี feasible move ก่อนเยี่ยมครบ 25 ช่อง กิ่งนั้นไม่มีทางเป็น tour จึงทิ้งได้ทันที เป็น exact pruning ไม่ใช่การเดาด้วย heuristic

if (depth < 24 && available == 0)
    discard(state)
else
    write(nextFrontier)

3. Global synchronization

PBFS ทำทุก state ที่ depth d ให้เสร็จก่อนเริ่ม depth d+1 เมื่อถึง depth 24 ระบบเก็บทุก state ที่เยี่ยมครบ 25 ช่อง แล้วคลี่ multiplicity ของ state ที่รวมกันกลับเป็น complete open tours ทุกเส้น

expand(frontier[d]) in parallel
prefix-sum child counts
barrier()
frontier[d + 1] = children