25,161
edits
Changes
FPGA
,Created page with "'''Home * Hardware * FPGA''' [[FILE:Altera StratixIVGX FPGA.jpg|border|right|thumb| [https://en.wikipedia.org/wiki/Altera Altera] FPGA <ref>[https://en.wik..."
'''[[Main Page|Home]] * [[Hardware]] * FPGA'''
[[FILE:Altera StratixIVGX FPGA.jpg|border|right|thumb|
[https://en.wikipedia.org/wiki/Altera Altera] FPGA <ref>[https://en.wikipedia.org/wiki/Field-programmable_gate_array from Wikipedia]</ref> ]]
'''FPGA''', (Field-programmable gate array)
a [https://en.wikipedia.org/wiki/Field-programmability field-programmable] [https://en.wikipedia.org/wiki/Integrated_circuit integrated circuit] consisting of a two-dimensional [[Array|array]] of logic blocks interconnected by a hierarchy of reconfigurable routing channels. The behavior of a FPGA is defined by a schematic design or by a [https://en.wikipedia.org/wiki/Hardware_description_language hardware description language] (HDL), most notably [https://en.wikipedia.org/wiki/VHDL VHDL] and [https://en.wikipedia.org/wiki/Verilog Verilog]. FPGA cards of their main suppliers [https://en.wikipedia.org/wiki/Xilinx Xilinx] <ref>[http://www.xilinx.com/ All Programmable Technologies from Xilinx Inc.]</ref> and [https://en.wikipedia.org/wiki/Altera Altera] <ref>[http://www.altera.com/ FPGA CPLD and ASIC from Altera]</ref> can be plugged into a [[IBM PC|PC]] with communication over the [https://en.wikipedia.org/wiki/Conventional_PCI PCI] or [https://en.wikipedia.org/wiki/PCI_Express PCI Express] bus. [[IBM|IBM's]] [https://en.wikipedia.org/wiki/POWER8 POWER8] processor, introduced in August 2013, features a CAPI port (Coherent Accelerator Processor Interface) is layered on top of [https://en.wikipedia.org/wiki/PCI_Express#PCI_Express_3.x PCI Express 3.0] suited to connect custom hardware such as FPGAs <ref>[http://wccftech.com/ibm-power8-processor-architecture-detailed/ IBM Power8 Processor Detailed - Features 22nm Design With 12 Cores, 96 MB eDRAM L3 Cache and 4 GHz Clock Speed]</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=54474&start=17 Re: FPGA chess] by [[Milos Stanisavljevic]], [[CCC]], November 28, 2014</ref>.
=Architecture=
==Structure==
{|
|- style="vertical-align:top;"
| [[FILE:fpga_structure.jpg|none|border|text-bottom|320px|link=http://www.eecg.toronto.edu/~vaughn/challenge/fpga_arch.html]]
| rowspan="2" | The structure is a two-dimensional array of logic blocks and reconfigurable routing channels, which all have the same width (number of wires). I/O pads can connect to any one of the wiring segments in the channel adjacent to it <ref>[http://www.eecg.toronto.edu/~vaughn/challenge/fpga_arch.html FPGA Architecture for the Challenge]</ref>.
|-
| FPGA structure <ref>[http://www.eecg.toronto.edu/~vaughn/challenge/fpga_arch.html FPGA Architecture for the Challenge]</ref>
|}
<span id="LC"></span>
==Blocks and Cells==
{|
|- style="vertical-align:top;"
| [[FILE:Logic block2.svg|none|border|text-bottom|320px]]
| rowspan="2" | Each logic block (configurable logic block CLB, or logic array block LAB) consists of one or more logical cells (LC, adaptive logic module ALM, logic element LE, Slice etc.), each with a n-input bits (4-6) to one-output bit programmable [https://en.wikipedia.org/wiki/Lookup_table#Hardware_LUTs lookup table (LUT)] - the [[Combinatorial Logic|combinatorial logic]], and a [[Memory#FlipFlop|D-Flip-Flop]], which synchronizes and stores the output by the edge of a clock signal to implement a [[Sequential Logic|sequential logic]]. A configurable [https://en.wikipedia.org/wiki/Multiplexer multiplexer] either switches the direct or latched LUT output outwards.
|-
| Logic cell with LUT and [[Memory#FlipFlop|D-Flip-Flop]] <ref>[http://de.wikipedia.org/wiki/Field_Programmable_Gate_Array Field Programmable Gate Array from Wikipedia.de] (German)</ref>
|}
==Routing==
{|
|- style="vertical-align:top;"
| [[FILE:Switch box.svg|none|border|text-bottom|320px]]
| rowspan="2" | Inputs and outputs of a cell can connect to any one of the routing wires in the channel adjacent to it. Whenever a vertical and a horizontal channel intersect there is a switch box with programmable switches that allow it to connect to other wires in adjacent channel segments. [https://en.wikipedia.org/wiki/Virtex_%28FPGA%29#Virtex_family Xilinx Virtex] devices further provide BlockRAM, a 4096-bit synchronous memory which can be configured for single or dual port usage with variable widths of 1, 2, 4, 8 or 16 bits.
|-
| Switch box topology <ref>[https://en.wikipedia.org/wiki/Field-programmable_gate_array Field-programmable gate array from Wikipedia]</ref>
|}
=FPGA in Computer Chess=
FPGAs are suited to implement a [[Belle#Hardware|Belle]] like [[Move Generation|move generator]] in hardware. While [[Marc Boulé]] proposed a pure generation approach as used by his program [[MBChess]], [[Chrilly Donninger]], with PCI-communication overhead in mind, went some steps further in [[Brutus]] <ref>[http://en.chessbase.com/post/what-is-brutus- What is Brutus?], [[ChessBase|ChessBase News]], March 20, 2002</ref> and [[Hydra]], using a complete 3-[[Ply|ply]] [[Iterative Search|iterative search]] including [[Quiescence Search|quiescence]] and [[Evaluation|evaluation]], controlled by a [https://en.wikipedia.org/wiki/Finite-state_machine finite state machine (FSM)].
* [[MBChess]]
* [[Brutus]]
* [[Hydra]]
<span id="Boule"></span>
==Boulé==
In his Masters thesis <ref>[[Marc Boulé]] ('''2002'''). ''An FPGA Move Generator for the Game of Chess''. Masters thesis, [[McGill University]], supervisor: [[Zeljko Zilic]], co-supervisor: [[Monroe Newborn|Monty Newborn]]</ref>, [[Marc Boulé]] proposed a FPGA move generator, as used by his chess program [[MBChess]]. His approach performs a Belle like move masking method with find '''victim''' and find '''aggressor''' cycles in [[MVV-LVA]] manner. A 1-bit, 64-deep synchronous memory in each [[Squares|square]] is used to memorize masked bits. The move generator includes a PCI interface to connect it to the PC running MBChess. Communication is done via different commands, such as to instruct the move generator to [[Unmake Move|undo]] the currently stored move, generate and return the next move and [[Make Move|execute]] that move on its internal FPGA [[Board Representation|board representation]]. In total, 10,804 out of 18,816 logic cells of a Xilinx XCV800 <ref>[https://www.stmintz.com/ccc/index.php?id=292813 Re: Attention - Slater Wold] by [[Marc Boulé]], [[CCC]], April 10, 2003</ref> were used, 10,104 as LUT, 700 as RAM <ref>[https://www.stmintz.com/ccc/index.php?id=251005 Re: Thesis by Marc Boule] by [[Marc Boulé]], [[CCC]], September 08, 2002</ref>.
[[FILE:FPGAChessSquares.JPG|none|border|text-bottom]]
A block diagram of a chess square with transmitter (TX) and the receiver (RX) <ref>[[Marc Boulé]] ('''2002'''). ''An FPGA Move Generator for the Game of Chess''. Masters thesis, [[McGill University]], supervisor: [[Zeljko Zilic]], co-supervisor: [[Monroe Newborn|Monty Newborn]]</ref>
<span id="Donninger"></span>
==Donninger==
[[Brutus]] <ref>[[Chrilly Donninger]], [[Alex Kure]], [[Ulf Lorenz]] ('''2004'''). ''Parallel Brutus: The First Distributed, FPGA Accelerated Chess Program''. [http://dl.acm.org/citation.cfm?id=645610&picked=prox IPDPS’04], [http://www2.cs.uni-paderborn.de/cs/ag-monien/PERSONAL/FLULO/publications/ipdps04.pdf pdf]</ref> and its successor [[Hydra]] by [[Chrilly Donninger]] et al. <ref>[[Chrilly Donninger]], [[Ulf Lorenz]] ('''2004'''). ''[http://www.springerlink.com/content/hp9la9pwq0a1cmrp/ The Chess Monster Hydra]'' in [http://www.springerlink.com/content/8grv6pu2e8hd/?p=3037c8af6a0147319f6f5a8e133083dd&pi=0 Field Programmable Logic and Application], 14th International Conference, FPL 2004</ref> perform the last 3 plies of an n-ply search on the FPGA side, inclusively the quiescence search and evaluations. It uses 67 out of 96 BlockRAMs, 534 of 24,576 Flip-Flops, and 18,403 of 24,576 LUTs. An upper bound for the number of cycles per search node is 9. Hydra essentially contains a big piece of combinatorial logic, controlled by a finite state machine (FSM) with 54 states for the search. The move generator consists of the generate '''aggressor''' module and the generate '''victim''' module, both instantiate 64 square modules, one for each square.
The squares send piece-signals if any, respectively forwarding the signals of [[Sliding Pieces|sliding pieces]]. Each square can output the signal ’victim found’ to indicate the ’victim’ is [[Target Square|target square]] of a [[Pseudo-Legal Move|pseudo-legal move]]. The collection of all ’victim found’ signals is the input for a comparator tree, an arbiter, which selects the most attractive, not yet examined victim. The Generate Aggressor module takes the arbiter’s output as input and sends the signal of a super-piece from the target to find one or more [[Origin Square|origin squares]]. Selection criteria are the values of attacked pieces and whether or not a move is a [[Killer Move|killer move]].
=Publications=
==1997 ...==
* [[Kurt Keutzer]] ('''1997'''). ''[http://dl.acm.org/citation.cfm?id=258326 Challenges in CAD for the One Million Gate FPGA]''. [http://dblp.uni-trier.de/db/conf/fpga/fpga97.html#Keutzer97 FPGA 1997], [https://www.computer.org/csdl/proceedings/fpga/1997/2600/00/26000133.pdf pdf]
* [http://www.eecg.toronto.edu/%7Ebrown/ Stephen Brown], [[Zvonko Vranesic]] ('''1999'''). ''[http://www.mhhe.com/engcs/electrical/brownvranesic/ Fundamentals of Digital Logic with VHDL Design]''. [http://catalogs.mhhe.com/mhhe/home.do McGraw-Hill]
==2000 ...==
* [[Youhei Hori]], [[Minenobu Seki]], [[Tsutomu Maruyama]], [[Reijer Grimbergen]], [[Tsutomu Hoshino]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_20 A Shogi Processor with a Field Programmable Gate Array]''. [[CG 2000]]
* [[Valavan Manohararajah]], [https://www.linkedin.com/in/terry-borer-501847/ Terry P. Borer], [http://www.eecg.toronto.edu/%7Ebrown/ Stephen Brown], [[Zvonko Vranesic]] ('''2002'''). ''[https://www.semanticscholar.org/paper/Automatic-Partitioning-for-Improved-Placement-and-Manohararajah-Borer/d53ad046c377bedc4caa2f80dfc32339f0bc3d6d Automatic Partitioning for Improved Placement and Routing in Complex Programmable Logic Devices]''. [https://dblp.uni-trier.de/db/conf/fpl/fpl2002.html FPL 2002]
* [[Marc Boulé]] ('''2002'''). ''An FPGA Move Generator for the Game of Chess''. Masters thesis, [[McGill University]], supervisor: [[Zeljko Zilic]], co-supervisor: [[Monroe Newborn|Monty Newborn]]
* [[Marc Boulé]], [[Zeljko Zilic]] ('''2002'''). ''An FPGA Move Generator for the Game of Chess''. [[McGill University]]
* [[Marc Boulé]], [[Zeljko Zilic]] ('''2002'''). ''An FPGA Move Generator for the Game of Chess''. [[ICGA Journal#25_2|ICGA Journal, Vol. 25, No. 2]]
* [[Youhei Hori]], [[Masashi Sonoyama]], [[Tsutomu Maruyama]] ('''2002'''). ''An FPGA-Based Processor for Shogi Mating Problems''. 2002 IEEE International Conference on Field-Programmable Technology, 2002, [http://staff.aist.go.jp/hori.y/articles/hori_icfpt02.pdf pdf]
* [[Marc Boulé]], [[Zeljko Zilic]] ('''2003'''). ''FPGA Hardware Acceleration: From Chess Playing to Automated Theorem Proving''. poster presentation, Micronet Sept. 2003
* [http://www.eecg.toronto.edu/%7Ebrown/ Stephen Brown], [[Zvonko Vranesic]] ('''2003'''). ''[http://www.mhhe.com/engcs/electrical/brownvranesic/ Fundamentals of Digital Logic with Verilog Design]''. [http://catalogs.mhhe.com/mhhe/home.do McGraw-Hill]
* [[Chrilly Donninger]], [[Alex Kure]], [[Ulf Lorenz]] ('''2004'''). ''Parallel Brutus: The First Distributed, FPGA Accelerated Chess Program''. [http://dl.acm.org/citation.cfm?id=645610&picked=prox IPDPS’04]
* [[Chrilly Donninger]], [[Ulf Lorenz]] ('''2004'''). ''[http://www.springerlink.com/content/hp9la9pwq0a1cmrp/ The Chess Monster Hydra]'' in [http://www.springerlink.com/content/8grv6pu2e8hd/?p=3037c8af6a0147319f6f5a8e133083dd&pi=0 Field Programmable Logic and Application], FPL 2004
==2005 ...==
* [[Valavan Manohararajah]] ('''2005'''). ''Area Optimizations in FPGA Architecture and CAD''. Ph.D. Thesis, [http://www.valavan.net/pthesis.pdf pdf]
* [[Valavan Manohararajah]], [http://www.eecg.toronto.edu/%7Ebrown/ Stephen Brown], [[Zvonko Vranesic]] ('''2006'''). ''[https://ieeexplore.ieee.org/document/4100986/ Adaptive FPGAs: High-Level Architecture and a Synthesis Method]''. [https://dblp.uni-trier.de/db/conf/fpl/fpl2006.html FPL 2006], [http://www.eecg.toronto.edu/~brown/papers/fpl06-manohararajah.pdf pdf]
* [[Valavan Manohararajah]], [http://www.eecg.toronto.edu/%7Ebrown/ Stephen Brown], [[Zvonko Vranesic]] ('''2006'''). ''[https://ieeexplore.ieee.org/document/1715419/ Heuristics for Area Minimization in LUT-Based FPGA Technology Mapping].'' [[IEEE#TCICS|IEEE Transactions on CAD of Integrated Circuits and Systems]], Vol. 25, No. 11
* [http://www.eecg.toronto.edu/%7Ebrown/ Stephen Brown], [[Zvonko Vranesic]] ('''2007'''). ''[http://www.mhhe.com/engcs/electrical/brownvranesic/ Fundamentals of Digital Logic with Verilog Design]''. [http://catalogs.mhhe.com/mhhe/home.do McGraw-Hill], 2nd edition, [https://www.amazon.com/Fundamentals-Digital-Logic-Verilog-Design/dp/0077211642 amazon]
* [http://www.eecg.toronto.edu/%7Ebrown/ Stephen Brown], [[Zvonko Vranesic]] ('''2008'''). ''[http://www.mhhe.com/engcs/electrical/brownvranesic/ Fundamentals of Digital Logic with VHDL Design]''. [http://catalogs.mhhe.com/mhhe/home.do McGraw-Hill], 3rd edition, [https://www.amazon.com/Fundamentals-Digital-Logic-Design-CD-ROM/dp/0077221435/ref=dp_ob_title_bk amazon]
* [[Zeljko Zilic]] ('''2009'''). ''[https://www.semanticscholar.org/paper/Designing-and-Using-FPGAs-beyond-Classical-Binary-Zilic/c63e05fc673821d5dc8e471e2849105bc22526f6 Designing and Using FPGAs beyond Classical Binary Logic: Opportunities in Nano-Scale Integration Age]''. [https://dblp.uni-trier.de/db/conf/ismvl/ismvl2009.html ISMVL 2009]
==2010 ...==
* [http://www.linkedin.com/pub/james-bowman/9/511/358 James Bowman] ('''2010'''). ''J1: a small Forth CPU Core for FPGAs''. [http://www.complang.tuwien.ac.at/anton/euroforth/ef10/ EuroForth 2010], [http://www.excamera.com/files/j1.pdf pdf] <ref>[http://www.excamera.com/sphinx/fpga-j1.html The J1 Forth CPU — excamera]</ref>
* [https://dblp.uni-trier.de/pers/hd/k/Kadric:Edin Edin Kadric], [http://my.ece.queensu.ca/people/N-Manjikian/index.html Naraig Manjikian], [[Zeljko Zilic]] ('''2012'''). ''[https://www.semanticscholar.org/paper/An-FPGA-implementation-for-a-high-speed-optical-a-Kadric-Manjikian/403966143ae4ded89f519214124761d667821a11 An FPGA implementation for a high-speed optical link with a PCIe interface]''. [https://dblp.uni-trier.de/db/conf/socc/socc2012.html SoCC 2012]
==2015 ...==
* [https://dblp.uni-trier.de/pers/hd/p/Plavec:Franjo Franjo Plavec], [[Zvonko Vranesic]], [http://www.eecg.toronto.edu/%7Ebrown/ Stephen Brown] ('''2013'''). ''[https://dl.acm.org/citation.cfm?id=2535932 Exploiting Task- and Data-Level Parallelism in Streaming Applications Implemented in FPGAs]''. [https://dblp.uni-trier.de/db/journals/trets/trets6.html TRETS], Vol. 6, No. 4
=Forum Posts=
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=92614 Chip design project & another request for Belle/DT/DB info] by [[Tom Kerrigan]], [[CCC]], January 27, 2000 » [[Belle]], [[Deep Thought]], [[Deep Blue]]
* [https://www.stmintz.com/ccc/index.php?id=221124 A Response From Marc Boule] by [[Slater Wold]], [[CCC]], April 02, 2002
* [https://www.stmintz.com/ccc/index.php?id=251005 Re: Thesis by Marc Boule] by [[Marc Boulé]], [[CCC]], September 08, 2002
* [https://www.stmintz.com/ccc/index.php?id=292813 Re: Attention - Slater Wold] by [[Marc Boulé]], [[CCC]], April 10, 2003
* [https://www.stmintz.com/ccc/index.php?id=330184 Go Brutus!!] by Pete Rihaczek, [[CCC]], November 24, 2003
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=429154 fpga/mcu implementation] by Daniel Staf, [[CCC]], May 31, 2005
* [http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=1699 FPGA cards and RYBKA] by albitex, [[Computer Chess Forums|Rybka Forum]], July 11, 2007
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=54474 FPGA chess] by [[Matthew Lai]], [[CCC]], November 26, 2014
=External Links=
* [https://en.wikipedia.org/wiki/Field-programmable_gate_array Field-programmable gate array from Wikipedia]
: [https://en.wikipedia.org/wiki/Field-programmable_analog_array Field-programmable analog array from Wikipedia]
* [http://en.wikibooks.org/wiki/Programmable_Logic/FPGAs Programmable Logic/FPGAs from Wikibooks]
* [http://hamsterworks.co.nz/mediawiki/index.php/Main_Page Hamsterworks Wiki!]
* [http://www.eecg.toronto.edu/~vaughn/challenge/challenge.html The FPGA Place-and-Route Challenge] by [http://www.eecg.toronto.edu/~vaughn/ Vaughn Betz]
: [http://www.eecg.toronto.edu/~vaughn/challenge/fpga_arch.html FPGA Architecture for the Challenge]
* [http://www.excamera.com/sphinx/fpga-j1.html The J1 Forth CPU — excamera] » [[Forth]]
* [http://www.cs.ucla.edu/classes/cs151C/ UCLA Computer Science Department | Winter 2004 | CS 151C - Design of Digital Systems | VHDL Projects on XSV Board]
: [http://www.cs.ucla.edu/classes/cs151C/#checkers VHDL Checkers Implementation]
* [http://hackaday.com/2012/01/20/fpga-snake-game-uses-no-vhdl-at-all/ FPGA Snake game uses no VHDL at all - Hack a Day]
* [http://ndirty.cute.fi/~karttu/FPGA/esimes/life/HARDWARE_PHOTOS/pelikone.html The General FPGA-based board game machine, a prototype] by [http://ndirty.cute.fi/~karttu/ Antti Karttunen]
* [http://en.chessbase.com/post/what-is-brutus- What is Brutus?], [[ChessBase|ChessBase News]], March 20, 2002
* [http://en.chessbase.com/post/all-about-the-hydra-che-project All about the Hydra chess project], [[ChessBase|ChessBase News]], August 22, 2004
==Vendors==
* [http://www.altera.com/ FPGA CPLD and ASIC from Altera]
* [http://www.xilinx.com/ All Programmable Technologies from Xilinx Inc.]
* [http://www.alpha-data.com/ Alpha Data - High Performance Computing with Xilinx Virtex-7 FPGAs]
==Misc==
* [[Videos#TotoBlanke|Toto Blanke]] - PPG, [http://www.discogs.com/Toto-Blanke-Electric-Circus/release/652970 Electric Circus] (1977) feat. [https://en.wikipedia.org/wiki/Edward_Vesala Edward Vesala], [[Videos#JasperVantHof|Jasper van 't Hof]], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=mJbGKOmNXCs|alignment=left|valignment=top}}
=References=
<references />
'''[[Hardware|Up one Level]]'''
[[FILE:Altera StratixIVGX FPGA.jpg|border|right|thumb|
[https://en.wikipedia.org/wiki/Altera Altera] FPGA <ref>[https://en.wikipedia.org/wiki/Field-programmable_gate_array from Wikipedia]</ref> ]]
'''FPGA''', (Field-programmable gate array)
a [https://en.wikipedia.org/wiki/Field-programmability field-programmable] [https://en.wikipedia.org/wiki/Integrated_circuit integrated circuit] consisting of a two-dimensional [[Array|array]] of logic blocks interconnected by a hierarchy of reconfigurable routing channels. The behavior of a FPGA is defined by a schematic design or by a [https://en.wikipedia.org/wiki/Hardware_description_language hardware description language] (HDL), most notably [https://en.wikipedia.org/wiki/VHDL VHDL] and [https://en.wikipedia.org/wiki/Verilog Verilog]. FPGA cards of their main suppliers [https://en.wikipedia.org/wiki/Xilinx Xilinx] <ref>[http://www.xilinx.com/ All Programmable Technologies from Xilinx Inc.]</ref> and [https://en.wikipedia.org/wiki/Altera Altera] <ref>[http://www.altera.com/ FPGA CPLD and ASIC from Altera]</ref> can be plugged into a [[IBM PC|PC]] with communication over the [https://en.wikipedia.org/wiki/Conventional_PCI PCI] or [https://en.wikipedia.org/wiki/PCI_Express PCI Express] bus. [[IBM|IBM's]] [https://en.wikipedia.org/wiki/POWER8 POWER8] processor, introduced in August 2013, features a CAPI port (Coherent Accelerator Processor Interface) is layered on top of [https://en.wikipedia.org/wiki/PCI_Express#PCI_Express_3.x PCI Express 3.0] suited to connect custom hardware such as FPGAs <ref>[http://wccftech.com/ibm-power8-processor-architecture-detailed/ IBM Power8 Processor Detailed - Features 22nm Design With 12 Cores, 96 MB eDRAM L3 Cache and 4 GHz Clock Speed]</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=54474&start=17 Re: FPGA chess] by [[Milos Stanisavljevic]], [[CCC]], November 28, 2014</ref>.
=Architecture=
==Structure==
{|
|- style="vertical-align:top;"
| [[FILE:fpga_structure.jpg|none|border|text-bottom|320px|link=http://www.eecg.toronto.edu/~vaughn/challenge/fpga_arch.html]]
| rowspan="2" | The structure is a two-dimensional array of logic blocks and reconfigurable routing channels, which all have the same width (number of wires). I/O pads can connect to any one of the wiring segments in the channel adjacent to it <ref>[http://www.eecg.toronto.edu/~vaughn/challenge/fpga_arch.html FPGA Architecture for the Challenge]</ref>.
|-
| FPGA structure <ref>[http://www.eecg.toronto.edu/~vaughn/challenge/fpga_arch.html FPGA Architecture for the Challenge]</ref>
|}
<span id="LC"></span>
==Blocks and Cells==
{|
|- style="vertical-align:top;"
| [[FILE:Logic block2.svg|none|border|text-bottom|320px]]
| rowspan="2" | Each logic block (configurable logic block CLB, or logic array block LAB) consists of one or more logical cells (LC, adaptive logic module ALM, logic element LE, Slice etc.), each with a n-input bits (4-6) to one-output bit programmable [https://en.wikipedia.org/wiki/Lookup_table#Hardware_LUTs lookup table (LUT)] - the [[Combinatorial Logic|combinatorial logic]], and a [[Memory#FlipFlop|D-Flip-Flop]], which synchronizes and stores the output by the edge of a clock signal to implement a [[Sequential Logic|sequential logic]]. A configurable [https://en.wikipedia.org/wiki/Multiplexer multiplexer] either switches the direct or latched LUT output outwards.
|-
| Logic cell with LUT and [[Memory#FlipFlop|D-Flip-Flop]] <ref>[http://de.wikipedia.org/wiki/Field_Programmable_Gate_Array Field Programmable Gate Array from Wikipedia.de] (German)</ref>
|}
==Routing==
{|
|- style="vertical-align:top;"
| [[FILE:Switch box.svg|none|border|text-bottom|320px]]
| rowspan="2" | Inputs and outputs of a cell can connect to any one of the routing wires in the channel adjacent to it. Whenever a vertical and a horizontal channel intersect there is a switch box with programmable switches that allow it to connect to other wires in adjacent channel segments. [https://en.wikipedia.org/wiki/Virtex_%28FPGA%29#Virtex_family Xilinx Virtex] devices further provide BlockRAM, a 4096-bit synchronous memory which can be configured for single or dual port usage with variable widths of 1, 2, 4, 8 or 16 bits.
|-
| Switch box topology <ref>[https://en.wikipedia.org/wiki/Field-programmable_gate_array Field-programmable gate array from Wikipedia]</ref>
|}
=FPGA in Computer Chess=
FPGAs are suited to implement a [[Belle#Hardware|Belle]] like [[Move Generation|move generator]] in hardware. While [[Marc Boulé]] proposed a pure generation approach as used by his program [[MBChess]], [[Chrilly Donninger]], with PCI-communication overhead in mind, went some steps further in [[Brutus]] <ref>[http://en.chessbase.com/post/what-is-brutus- What is Brutus?], [[ChessBase|ChessBase News]], March 20, 2002</ref> and [[Hydra]], using a complete 3-[[Ply|ply]] [[Iterative Search|iterative search]] including [[Quiescence Search|quiescence]] and [[Evaluation|evaluation]], controlled by a [https://en.wikipedia.org/wiki/Finite-state_machine finite state machine (FSM)].
* [[MBChess]]
* [[Brutus]]
* [[Hydra]]
<span id="Boule"></span>
==Boulé==
In his Masters thesis <ref>[[Marc Boulé]] ('''2002'''). ''An FPGA Move Generator for the Game of Chess''. Masters thesis, [[McGill University]], supervisor: [[Zeljko Zilic]], co-supervisor: [[Monroe Newborn|Monty Newborn]]</ref>, [[Marc Boulé]] proposed a FPGA move generator, as used by his chess program [[MBChess]]. His approach performs a Belle like move masking method with find '''victim''' and find '''aggressor''' cycles in [[MVV-LVA]] manner. A 1-bit, 64-deep synchronous memory in each [[Squares|square]] is used to memorize masked bits. The move generator includes a PCI interface to connect it to the PC running MBChess. Communication is done via different commands, such as to instruct the move generator to [[Unmake Move|undo]] the currently stored move, generate and return the next move and [[Make Move|execute]] that move on its internal FPGA [[Board Representation|board representation]]. In total, 10,804 out of 18,816 logic cells of a Xilinx XCV800 <ref>[https://www.stmintz.com/ccc/index.php?id=292813 Re: Attention - Slater Wold] by [[Marc Boulé]], [[CCC]], April 10, 2003</ref> were used, 10,104 as LUT, 700 as RAM <ref>[https://www.stmintz.com/ccc/index.php?id=251005 Re: Thesis by Marc Boule] by [[Marc Boulé]], [[CCC]], September 08, 2002</ref>.
[[FILE:FPGAChessSquares.JPG|none|border|text-bottom]]
A block diagram of a chess square with transmitter (TX) and the receiver (RX) <ref>[[Marc Boulé]] ('''2002'''). ''An FPGA Move Generator for the Game of Chess''. Masters thesis, [[McGill University]], supervisor: [[Zeljko Zilic]], co-supervisor: [[Monroe Newborn|Monty Newborn]]</ref>
<span id="Donninger"></span>
==Donninger==
[[Brutus]] <ref>[[Chrilly Donninger]], [[Alex Kure]], [[Ulf Lorenz]] ('''2004'''). ''Parallel Brutus: The First Distributed, FPGA Accelerated Chess Program''. [http://dl.acm.org/citation.cfm?id=645610&picked=prox IPDPS’04], [http://www2.cs.uni-paderborn.de/cs/ag-monien/PERSONAL/FLULO/publications/ipdps04.pdf pdf]</ref> and its successor [[Hydra]] by [[Chrilly Donninger]] et al. <ref>[[Chrilly Donninger]], [[Ulf Lorenz]] ('''2004'''). ''[http://www.springerlink.com/content/hp9la9pwq0a1cmrp/ The Chess Monster Hydra]'' in [http://www.springerlink.com/content/8grv6pu2e8hd/?p=3037c8af6a0147319f6f5a8e133083dd&pi=0 Field Programmable Logic and Application], 14th International Conference, FPL 2004</ref> perform the last 3 plies of an n-ply search on the FPGA side, inclusively the quiescence search and evaluations. It uses 67 out of 96 BlockRAMs, 534 of 24,576 Flip-Flops, and 18,403 of 24,576 LUTs. An upper bound for the number of cycles per search node is 9. Hydra essentially contains a big piece of combinatorial logic, controlled by a finite state machine (FSM) with 54 states for the search. The move generator consists of the generate '''aggressor''' module and the generate '''victim''' module, both instantiate 64 square modules, one for each square.
The squares send piece-signals if any, respectively forwarding the signals of [[Sliding Pieces|sliding pieces]]. Each square can output the signal ’victim found’ to indicate the ’victim’ is [[Target Square|target square]] of a [[Pseudo-Legal Move|pseudo-legal move]]. The collection of all ’victim found’ signals is the input for a comparator tree, an arbiter, which selects the most attractive, not yet examined victim. The Generate Aggressor module takes the arbiter’s output as input and sends the signal of a super-piece from the target to find one or more [[Origin Square|origin squares]]. Selection criteria are the values of attacked pieces and whether or not a move is a [[Killer Move|killer move]].
=Publications=
==1997 ...==
* [[Kurt Keutzer]] ('''1997'''). ''[http://dl.acm.org/citation.cfm?id=258326 Challenges in CAD for the One Million Gate FPGA]''. [http://dblp.uni-trier.de/db/conf/fpga/fpga97.html#Keutzer97 FPGA 1997], [https://www.computer.org/csdl/proceedings/fpga/1997/2600/00/26000133.pdf pdf]
* [http://www.eecg.toronto.edu/%7Ebrown/ Stephen Brown], [[Zvonko Vranesic]] ('''1999'''). ''[http://www.mhhe.com/engcs/electrical/brownvranesic/ Fundamentals of Digital Logic with VHDL Design]''. [http://catalogs.mhhe.com/mhhe/home.do McGraw-Hill]
==2000 ...==
* [[Youhei Hori]], [[Minenobu Seki]], [[Tsutomu Maruyama]], [[Reijer Grimbergen]], [[Tsutomu Hoshino]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_20 A Shogi Processor with a Field Programmable Gate Array]''. [[CG 2000]]
* [[Valavan Manohararajah]], [https://www.linkedin.com/in/terry-borer-501847/ Terry P. Borer], [http://www.eecg.toronto.edu/%7Ebrown/ Stephen Brown], [[Zvonko Vranesic]] ('''2002'''). ''[https://www.semanticscholar.org/paper/Automatic-Partitioning-for-Improved-Placement-and-Manohararajah-Borer/d53ad046c377bedc4caa2f80dfc32339f0bc3d6d Automatic Partitioning for Improved Placement and Routing in Complex Programmable Logic Devices]''. [https://dblp.uni-trier.de/db/conf/fpl/fpl2002.html FPL 2002]
* [[Marc Boulé]] ('''2002'''). ''An FPGA Move Generator for the Game of Chess''. Masters thesis, [[McGill University]], supervisor: [[Zeljko Zilic]], co-supervisor: [[Monroe Newborn|Monty Newborn]]
* [[Marc Boulé]], [[Zeljko Zilic]] ('''2002'''). ''An FPGA Move Generator for the Game of Chess''. [[McGill University]]
* [[Marc Boulé]], [[Zeljko Zilic]] ('''2002'''). ''An FPGA Move Generator for the Game of Chess''. [[ICGA Journal#25_2|ICGA Journal, Vol. 25, No. 2]]
* [[Youhei Hori]], [[Masashi Sonoyama]], [[Tsutomu Maruyama]] ('''2002'''). ''An FPGA-Based Processor for Shogi Mating Problems''. 2002 IEEE International Conference on Field-Programmable Technology, 2002, [http://staff.aist.go.jp/hori.y/articles/hori_icfpt02.pdf pdf]
* [[Marc Boulé]], [[Zeljko Zilic]] ('''2003'''). ''FPGA Hardware Acceleration: From Chess Playing to Automated Theorem Proving''. poster presentation, Micronet Sept. 2003
* [http://www.eecg.toronto.edu/%7Ebrown/ Stephen Brown], [[Zvonko Vranesic]] ('''2003'''). ''[http://www.mhhe.com/engcs/electrical/brownvranesic/ Fundamentals of Digital Logic with Verilog Design]''. [http://catalogs.mhhe.com/mhhe/home.do McGraw-Hill]
* [[Chrilly Donninger]], [[Alex Kure]], [[Ulf Lorenz]] ('''2004'''). ''Parallel Brutus: The First Distributed, FPGA Accelerated Chess Program''. [http://dl.acm.org/citation.cfm?id=645610&picked=prox IPDPS’04]
* [[Chrilly Donninger]], [[Ulf Lorenz]] ('''2004'''). ''[http://www.springerlink.com/content/hp9la9pwq0a1cmrp/ The Chess Monster Hydra]'' in [http://www.springerlink.com/content/8grv6pu2e8hd/?p=3037c8af6a0147319f6f5a8e133083dd&pi=0 Field Programmable Logic and Application], FPL 2004
==2005 ...==
* [[Valavan Manohararajah]] ('''2005'''). ''Area Optimizations in FPGA Architecture and CAD''. Ph.D. Thesis, [http://www.valavan.net/pthesis.pdf pdf]
* [[Valavan Manohararajah]], [http://www.eecg.toronto.edu/%7Ebrown/ Stephen Brown], [[Zvonko Vranesic]] ('''2006'''). ''[https://ieeexplore.ieee.org/document/4100986/ Adaptive FPGAs: High-Level Architecture and a Synthesis Method]''. [https://dblp.uni-trier.de/db/conf/fpl/fpl2006.html FPL 2006], [http://www.eecg.toronto.edu/~brown/papers/fpl06-manohararajah.pdf pdf]
* [[Valavan Manohararajah]], [http://www.eecg.toronto.edu/%7Ebrown/ Stephen Brown], [[Zvonko Vranesic]] ('''2006'''). ''[https://ieeexplore.ieee.org/document/1715419/ Heuristics for Area Minimization in LUT-Based FPGA Technology Mapping].'' [[IEEE#TCICS|IEEE Transactions on CAD of Integrated Circuits and Systems]], Vol. 25, No. 11
* [http://www.eecg.toronto.edu/%7Ebrown/ Stephen Brown], [[Zvonko Vranesic]] ('''2007'''). ''[http://www.mhhe.com/engcs/electrical/brownvranesic/ Fundamentals of Digital Logic with Verilog Design]''. [http://catalogs.mhhe.com/mhhe/home.do McGraw-Hill], 2nd edition, [https://www.amazon.com/Fundamentals-Digital-Logic-Verilog-Design/dp/0077211642 amazon]
* [http://www.eecg.toronto.edu/%7Ebrown/ Stephen Brown], [[Zvonko Vranesic]] ('''2008'''). ''[http://www.mhhe.com/engcs/electrical/brownvranesic/ Fundamentals of Digital Logic with VHDL Design]''. [http://catalogs.mhhe.com/mhhe/home.do McGraw-Hill], 3rd edition, [https://www.amazon.com/Fundamentals-Digital-Logic-Design-CD-ROM/dp/0077221435/ref=dp_ob_title_bk amazon]
* [[Zeljko Zilic]] ('''2009'''). ''[https://www.semanticscholar.org/paper/Designing-and-Using-FPGAs-beyond-Classical-Binary-Zilic/c63e05fc673821d5dc8e471e2849105bc22526f6 Designing and Using FPGAs beyond Classical Binary Logic: Opportunities in Nano-Scale Integration Age]''. [https://dblp.uni-trier.de/db/conf/ismvl/ismvl2009.html ISMVL 2009]
==2010 ...==
* [http://www.linkedin.com/pub/james-bowman/9/511/358 James Bowman] ('''2010'''). ''J1: a small Forth CPU Core for FPGAs''. [http://www.complang.tuwien.ac.at/anton/euroforth/ef10/ EuroForth 2010], [http://www.excamera.com/files/j1.pdf pdf] <ref>[http://www.excamera.com/sphinx/fpga-j1.html The J1 Forth CPU — excamera]</ref>
* [https://dblp.uni-trier.de/pers/hd/k/Kadric:Edin Edin Kadric], [http://my.ece.queensu.ca/people/N-Manjikian/index.html Naraig Manjikian], [[Zeljko Zilic]] ('''2012'''). ''[https://www.semanticscholar.org/paper/An-FPGA-implementation-for-a-high-speed-optical-a-Kadric-Manjikian/403966143ae4ded89f519214124761d667821a11 An FPGA implementation for a high-speed optical link with a PCIe interface]''. [https://dblp.uni-trier.de/db/conf/socc/socc2012.html SoCC 2012]
==2015 ...==
* [https://dblp.uni-trier.de/pers/hd/p/Plavec:Franjo Franjo Plavec], [[Zvonko Vranesic]], [http://www.eecg.toronto.edu/%7Ebrown/ Stephen Brown] ('''2013'''). ''[https://dl.acm.org/citation.cfm?id=2535932 Exploiting Task- and Data-Level Parallelism in Streaming Applications Implemented in FPGAs]''. [https://dblp.uni-trier.de/db/journals/trets/trets6.html TRETS], Vol. 6, No. 4
=Forum Posts=
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=92614 Chip design project & another request for Belle/DT/DB info] by [[Tom Kerrigan]], [[CCC]], January 27, 2000 » [[Belle]], [[Deep Thought]], [[Deep Blue]]
* [https://www.stmintz.com/ccc/index.php?id=221124 A Response From Marc Boule] by [[Slater Wold]], [[CCC]], April 02, 2002
* [https://www.stmintz.com/ccc/index.php?id=251005 Re: Thesis by Marc Boule] by [[Marc Boulé]], [[CCC]], September 08, 2002
* [https://www.stmintz.com/ccc/index.php?id=292813 Re: Attention - Slater Wold] by [[Marc Boulé]], [[CCC]], April 10, 2003
* [https://www.stmintz.com/ccc/index.php?id=330184 Go Brutus!!] by Pete Rihaczek, [[CCC]], November 24, 2003
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=429154 fpga/mcu implementation] by Daniel Staf, [[CCC]], May 31, 2005
* [http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=1699 FPGA cards and RYBKA] by albitex, [[Computer Chess Forums|Rybka Forum]], July 11, 2007
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=54474 FPGA chess] by [[Matthew Lai]], [[CCC]], November 26, 2014
=External Links=
* [https://en.wikipedia.org/wiki/Field-programmable_gate_array Field-programmable gate array from Wikipedia]
: [https://en.wikipedia.org/wiki/Field-programmable_analog_array Field-programmable analog array from Wikipedia]
* [http://en.wikibooks.org/wiki/Programmable_Logic/FPGAs Programmable Logic/FPGAs from Wikibooks]
* [http://hamsterworks.co.nz/mediawiki/index.php/Main_Page Hamsterworks Wiki!]
* [http://www.eecg.toronto.edu/~vaughn/challenge/challenge.html The FPGA Place-and-Route Challenge] by [http://www.eecg.toronto.edu/~vaughn/ Vaughn Betz]
: [http://www.eecg.toronto.edu/~vaughn/challenge/fpga_arch.html FPGA Architecture for the Challenge]
* [http://www.excamera.com/sphinx/fpga-j1.html The J1 Forth CPU — excamera] » [[Forth]]
* [http://www.cs.ucla.edu/classes/cs151C/ UCLA Computer Science Department | Winter 2004 | CS 151C - Design of Digital Systems | VHDL Projects on XSV Board]
: [http://www.cs.ucla.edu/classes/cs151C/#checkers VHDL Checkers Implementation]
* [http://hackaday.com/2012/01/20/fpga-snake-game-uses-no-vhdl-at-all/ FPGA Snake game uses no VHDL at all - Hack a Day]
* [http://ndirty.cute.fi/~karttu/FPGA/esimes/life/HARDWARE_PHOTOS/pelikone.html The General FPGA-based board game machine, a prototype] by [http://ndirty.cute.fi/~karttu/ Antti Karttunen]
* [http://en.chessbase.com/post/what-is-brutus- What is Brutus?], [[ChessBase|ChessBase News]], March 20, 2002
* [http://en.chessbase.com/post/all-about-the-hydra-che-project All about the Hydra chess project], [[ChessBase|ChessBase News]], August 22, 2004
==Vendors==
* [http://www.altera.com/ FPGA CPLD and ASIC from Altera]
* [http://www.xilinx.com/ All Programmable Technologies from Xilinx Inc.]
* [http://www.alpha-data.com/ Alpha Data - High Performance Computing with Xilinx Virtex-7 FPGAs]
==Misc==
* [[Videos#TotoBlanke|Toto Blanke]] - PPG, [http://www.discogs.com/Toto-Blanke-Electric-Circus/release/652970 Electric Circus] (1977) feat. [https://en.wikipedia.org/wiki/Edward_Vesala Edward Vesala], [[Videos#JasperVantHof|Jasper van 't Hof]], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=mJbGKOmNXCs|alignment=left|valignment=top}}
=References=
<references />
'''[[Hardware|Up one Level]]'''
