The GPU page ends at a wall: an
Eternity II backtracker is not compute-bound, it is a chain of tiny dependent
memory lookups, and Mike Field's 2011 analysis showed both GPU branches
(cooperate or work alone) ending at the external memory bus
(message 9003). An FPGA is the
one piece of silicon that seems to answer that exact complaint. There is no
cache hierarchy to miss: the lookup tables live in on-chip block RAM, one
clock cycle away, in dozens of independent little memories that can all be
read in the same cycle. The bit-shifts and masks that cost instructions on
a CPU come free as wiring. And instead of one big fast core you lay down many
small slow ones, each a complete backtracker with its own tables.
The community saw this road early and mapped it thoroughly. One member
designed the solver, published the datapath, projected five billion
placements per second per chip, and ran a prototype on real hardware. Then,
and this page exists to say it plainly, nobody ever drove the road to the
end. No full-Eternity-II FPGA run was ever reported, in nineteen years of
archive. The interesting part is that the reasons are on the record too, in
the designer's own words.
Recall the fork from Field's analysis (told in full on the
GPU page): parallel searchers either
share information, needing synchronization bandwidth the fabric doesn't have,
or work independently, needing per-worker state that outgrows the ~8 KB of
fast memory a GPU lane gets, spilling everything to one shared external bus.
His 2011 post applied the same argument to FPGAs in the same breath: "either
need to store too much information, pass too much information around or it
choke[s] on memory bandwidth"
(message 9003).
But the FPGA version of the argument has an escape hatch the GPU version
doesn't. On a GPU the fast-memory budget per worker is fixed by the vendor.
On an FPGA you draw the memory map: if you can shrink one backtracker's
entire world (candidate tables, board state, used-piece set) small enough,
you can instantiate it entirely in block RAM, replicate it fifty times, and
no worker ever touches external memory at all. The bandwidth wall isn't
climbed; it's deleted. The whole FPGA story of this archive is the pursuit of
that "if": making the solver's state small and uniform enough to become
hardware. It took one member six years of background thought to get there,
and the answer required changing the problem.
FPGAs enter the archive within weeks of the puzzle itself. In August 2007
psykowally, swearing off yet another software brute-forcer, mused about doing
it "in FPGA or something" while guessing it would only "take off a few
factors" (message 2022), a
guess the next seven years would keep confirming. In September, Dieter Gehrke
asked whether anyone had considered exact cover in hardware, pointing at an
academic FPGA implementation
(message 2623). Nobody had.
The November 2007 poll thread ("purpose built electronics" got exactly one
vote, its lone voter noted) produced the first real engineering talk. Bob
Cousins had already bought an Altera evaluation kit for Eternity I, planned
an FPGA accelerator for a software backtracker, and abandoned it: even at 10
million positions per second in hardware, the bottleneck was communication
with the PC (message 3259).
Glen Dudley put his finger on why backtracking wastes silicon: place 200
pieces, backtrack five, and 195 cells' worth of dedicated hardware sit idle
that cycle (message 3260).
Another member announced he'd "just started" a VHDL design and sought
collaborators (message 3266),
and was never heard from on the subject again. A third ran the sobering
numbers: trading a PC core's clock for FPGA parallelism costs 10–1000x up
front, and you'd be "better off... just using multiple computers"
(message 3268). SAT-in-hardware
got the same triage in 2008: millions of clause terms won't fit the largest
FPGA's logic (message 4723).
One person actually wrote HDL. In May 2008 Mike Pringle described an
edge-swapping local searcher whose fitness function (count the valid, unique
pieces the current edge assignment implies) was designed to swap and score
in a single clock. "I have the VHDL done for this but I ran out of FPGA
resources on the evaluation board I have for anything over 8×8"
(message 5493). First HDL in
the record, first resource wall in the record, same message.
Then came the protagonist. In October 2010 Michael Field, the engineer whose
26-cycles-per-placement budget anchors the
solver-engineering page,
opened a thread titled "E2 in hardware...", having started playing with
Digilent FPGA boards. His first sober estimate: a hardware backtracker would
run "roughly as fast as a PC's cpu core"; the real prize would be massively
parallel constraint checking, arc consistency evaluated at every step
(message 8063). Martin
(capiman)'s cost/benefit reply held up: one hardware backtracker merely
matches one of the four cores already in your PC, so only the parallel-logic
uses are interesting, and the ~2,816 bits of board state a full
arc-consistency fabric needs might not fit the biggest FPGA on the market
(message 8064). Field sketched
a 256-cell fabric with 18 pattern bits per side and a piece-request bus, and
signed off with the sentence that could caption this whole page: "no matter
what it won't be a silver bullet"
(message 8065). By 2012 he had
concluded FPGAs were "next to useless for implementing an E2 back-tracker":
the feedback loop between board and bag is too tight, so "the clock speed of
a CPU wins", and wondered instead about using the fabric to generate
rotation sets for a CPU to check
(message 9069).
On 7 February 2014, Field posted "Solving Eternity II in FPGA hardware": the
problem had "been sitting in my subconscious, slowly chewing over it for
about 6 years. Last night I had a bit of an eureka moment"
(message 9226). His old
record-class software solver couldn't become hardware for two reasons he
named precisely: it needed a ~6 MB lookup table (17x17x17x17x15 32-bit
entries) with truly random access, and the place-check-backtrack loop has
almost no fine-grained parallelism. The eureka was to relax the problem
until the datapath became uniform:
- Backtrack only the top-left 15×15 (never the right column or bottom
row), and use no hint pieces.
- Fill top-left to bottom-right, so every cell's candidate lookup is
indexed the same way: by its top and left edge colours. No corner cases, no
per-cell tables, one identical circuit, everywhere.
That uniformity collapsed the memory problem. The whole lookup structure fit
in about 4,096 bytes of ROM plus ~1 KB of state per solver
(message 9226): a 1024-entry,
18-bit-wide tile table (tile number, right pattern, bottom pattern, sorted by
top/left patterns) plus a 324-entry index giving each colour-pair's start and
count (message 9228). In
hardware, he noted, the shifts and masks are free wiring, the two tables sit
in different BRAMs so both lookups happen in parallel, and block RAM's
same-cycle read-write gives an atomic test-and-set on the used-piece bit:
the inner loop's entire memory traffic, one cycle away. Compare that 4 KB
against the GPU page's fatal ">8 KB
per thread": this is what deleting the bandwidth wall looks like.
The projection: about 50 solver instances on a Zynq 7020 at ~200 MHz,
each place/unplace averaging ~2 cycles, "up to 5 billion tile placements per
second per chip"
(message 9226). For scale, the
era's best CPU cores did 70–115 million.
The next month is the best-documented hardware bring-up in the archive, and
every step is worth recording because each one traded away a little of the
projection.
- Feb 20. Simulation places its first tiles; synthesis says >109 MHz on
a Spartan-6 LX9 using ~10% of its logic; near 50M placements/s per instance
early in a puzzle, degrading as more pieces are in use and cycles are spent
skipping them (message 9231).
- Feb 25. The first casualty on the record: the design
"didn't pan out, I had memory bandwidth issues during a 'tile lift'"
(unplacing needs two writes
at once, and a BRAM port is a BRAM port). The fix is elegant: a four-stage
hyper-pipeline, four independent backtrackers time-sharing one datapath
so each stage's memory access happens in its own cycle. Timing: 132.363
MHz; per-core cost 96 registers and 334 LUTs; an estimated 10 cores on the
small LX9 or 50 on an LX45, "around 5,000M 'actions' per second"
(message 9232).
- Mar 1: real silicon. Arnaud Carré had supplied a 16×16, 29-colour
benchmark his tuned CPU solver walks completely in 34.75 s at 114.5M
recursions/s on one i7-3770K core
(message 9234). Field loaded
it into actual hardware at 200 MHz, output limited, for now, to a single
LED that lights while any thread runs. The LED went out after 1 min 21 s;
his back-of-envelope put each thread at roughly a third of an i7 thread,
and a four-core, sixteen-thread build on his USB-powered board at ~800M
checks/s. He published the design on his site
(message 9236). Two days later
he found the flaw in that comparison and revised the figure down to 1/8;
the corrected number is below.
- Mar 3: the symmetry bug. Comparing counts with Arnaud revealed Field's
fixed top-left tile was doing a quarter of the benchmark's work. Corrected,
one hardware thread walks the entire tree in 199 seconds,
"about an 1/8th of the speed of Arnaud's i7 solver running on one core",
but 24 threads
fit on a sub-$100 board, and an 8-stage pipeline should allow 48. The
hardware found and printed all four solutions, timestamps and boards in the
post (message 9237).
And that is where the record stops. The 8-stage pipeline, the 48 threads, the
Zynq port, the full-puzzle run: none of them ever appears in the archive.
mulisak asked how to get started and Field answered with toolchain links and
his own free FPGA book
(message 9245); on April 1
mulisak proposed "e2coin", a cryptocurrency whose proof-of-work would be
edge-matching, arguing E2 is "CPU friendly - GPU unfriendly - but...
FPGA friendly" (message 9260);
the thread drifted into CPU benchmarks, and the hardware went quiet.
Nothing shipped, and the designer said why. In January 2022, Jef Bucas
asked whether anyone had access to an IEEE paper on FPGAs and Eternity II,
and Field's reply is the retrospective this page is built on: "The E2 problem
is correctly sized to make an FPGA solver hard :)". Because of the tight
feedback between board and bag he "couldn't get faster than a single core on
a low-end PC (~75M tiles per sec)", and the lookup-table memory "is high
enough that you quickly exhaust on-chip RAM if you are trying multiple
instances. It was a fun deadend for me"
(message 10649). Read that
against the projection: the 5G/s figure assumed fifty instances, and the very
BRAM that made one instance fast is what capped how many instances fit. The
prototype's own synthesis reports had foreshadowed it: one benchmark-sized
core already claimed 23 of the LX9's 64 RAM blocks
(message 9236).
The economics never closed either. The one member who tried both worlds,
valy, remembered Field's board fondly ("he was crunching 15 Mn/s on an FPGA
platform. Perf/W maybe unbeatable",
message 9588), and then
described the cost: FPGA work is "soooo slow to compile... code... debug...
You need to be an expert or have plenty of spare time and motivation. I've
tried once, that was my hardest programming experience"
(message 9590). Months of HDL
bring-up bought what the
solver-engineering ledger
gets from a compiler flag. That asymmetry, not any single technical wall,
is why every FPGA thread in the archive ends in silence: a 2021 member's
promised "FPGA custom engine in 2022"
(message 10581) is the last of
the line, and it too never resurfaced.
The one completed attempt was academic, and it underperformed software.
The paper Bucas asked for, "Exploitation of Parallel Search Space
Evaluation with FPGAs in Combinatorial Problems: The Eternity II Case"
(ReConFig 2011, ieeexplore 6044826),
is the only finished, published FPGA Eternity II system anywhere in the
record. Its bottom line, as the list read it: "After three months, the best
available solution contained 187/196 center pieces"
(message 10651), far below
what contemporary software heuristics produced. Bucas's verdict was the
community's: "a bit disappointed by the results in term of speed... I would
expect more from a 'dedicated' HW"
(message 10655).
| Who | When | What happened | Msg |
|---|
| psykowally | 2007 | First FPGA mention; guesses "a few factors" of speedup | 2022 |
| Dieter Gehrke | 2007 | Proposes exact cover in FPGA hardware; no taker | 2623 |
| Bob Cousins | 2007 | E1-era Altera accelerator plan, abandoned on PC-comms bottleneck; hybrid idea | 3259 |
| jp_yahoo | 2007 | Starts a VHDL design, seeks collaborators; never heard again | 3266 |
| Mike Pringle | 2008 | Edge-swap local search, VHDL written; out of resources beyond 8x8 | 5493 |
| Field & Martin | 2010 | Feasibility exchange: one hardware backtracker merely matches a CPU core | 8063, 8064 |
| Mike Field | 2011–12 | Memory analysis "carries over to FPGAs"; verdict "next to useless" for backtracking | 9003, 9069 |
| Mike Field | 2014 | The design: uniform 15x15, 4 KB tables, 50 instances @ 200 MHz, 5G/s/chip projected | 9226, 9228 |
| Mike Field | 2014 | Built and measured: hyper-pipelined prototype walks a 16×16 benchmark on silicon; 1 thread ≈ 1/8 i7 core (his own correction of an initial 1/3) | 9237 |
| mulisak | 2014 | e2coin: E2 as FPGA-friendly proof-of-work; posted April 1, no uptake | 9260 |
| academic team | 2011 | Only completed FPGA system; 3 months → 187/196 centre pieces | 10651 |
| Brahim Hamadicharef | 2021 | Announces "FPGA custom engine in 2022"; never mentioned again | 10581 |
| Mike Field | 2022 | The retrospective: "a fun deadend", BRAM exhaustion caps instances | 10649 |
Grant the projection everything it asked for. Say the 50-core, 200 MHz chip
had shipped at its full 5×10⁹ placements/s, and say you filled a rack
with two thousand of them: 10¹³ placements per second, more than the
whole community's combined fleet has ever fielded. A year is ~3×10⁷ seconds,
so the rack walks ~3×10²⁰ nodes a year. The full puzzle's search tree is,
at its plateau, on the order of 10⁴⁵ partial boards wide
(complex theory does this measurement
properly). The division: about 10²⁴ rack-years. Every order of magnitude
the hardware gains moves that exponent by one, and twenty-four of them are
missing.
This is the same sentence the GPU page ends on, because it is the same
mathematics: hardware is a constant divisor, and E2's wall is exponential.
Why a faster computer doesn't help does the
general argument; the FPGA chapter is simply its cleanest case study, because
here even the projected numbers (never mind the measured ones) concede
the point before the division starts.
The map is still on the table, and parts of it have aged well. Field's own
2022 caveat cuts the other way now: "cheaper FPGAs are now much larger"
(message 10649): a modern
mid-range part carries megabytes of block RAM where his Spartan-6 had
kilobytes, so the instance-count ceiling that killed the 2014 projection has
genuinely lifted. But the target list that survives scrutiny is the same one the
GPU page arrives at:
- Not search. A record attempt needs heuristics, restarts, and the
freedom to change fill order mid-campaign, everything Field traded away to
make the datapath uniform. The 15×15 relaxation that made the hardware
possible is exactly what a record hunter can't accept.
- Enumeration and verification. Fixed-shape exhaustive sweeps (census
re-verification, row and block counting, bounded sub-puzzles) are uniform
by construction: the property Field had to buy, these workloads get free.
His prototype already demonstrated the essential act, walking a complete
16×16 benchmark tree on silicon and finding exactly its four solutions
(message 9237).
- Placements per watt. The niche nobody disputed: valy's "perf/W maybe
unbeatable" (message 9588)
still stands for anyone running a years-long background census where the
electricity bill, not the placement rate, is the budget.
The road, in other words, leads somewhere, just not to 480. It was mapped by
someone who knew both the software and the silicon better than anyone else on
the list, driven one exit down, and carefully signposted on the way back: a
fun dead end, correctly sized to be one.