Field-Programmable
`Gate Arrays
`
`Intel Exhibit 1011
`Intel v. Iida
`
`

`

`THE KLUWER INTERNATIONAL SERIES
`IN ENGINEERING AND COMPUTER SCIENCE
`
`VLSI, COMPUTER ARCIllTECfURE AND
`DIGITAL SIGNAL PROCESSING
`Consulting Editor
`Jonathan Allen
`
`Latest Titles
`Microwave Semiconductor Devices, S. Yngvesson
`ISBN: 0-7923-9156-X
`A Survey of High-Level Synthesis Systems, R. A. Walker, R. Camposano
`ISBN: 0-7923-9158-6
`Symbolic Analysis for Automated Design of Analog Integrated Circuits,
`G. Gielen, W. Sansen,
`ISBN: 0-7923-9161-6
`High-Level VLSI Synthesis, R. Camposano, W. Wolf,
`ISBN: 0-7923-9159-4
`Integrating Functional and Temporal Domains in Logic Design: The False Path
`Problem and its Implications, P. C. McGeer, R. K. Brayton,
`ISBN: 0-7923-9163-2
`Neural Models and Algorithmsfor Digital Testing, S. T. Chakradhar,
`V. D. Agrawal, M. L. Bushnell,
`ISBN: 0-7923-9165-9
`Monte Carlo Device Simulation: Full Band and Beyond, Karl Hess, editor
`ISBN: 0-7923-9172-1
`The Design of Communicating Systems: A Sygem Engineering Approach,
`C.J. Koomen
`ISBN: 0-7923-9203-5
`Parallel Algorithms and Architectures for DSP Applications,
`M. A. Bayoumi, editor
`ISBN: 0-7923-9209-4
`Digital Speech Processing: Speech Coding, Synthesis and Recognition
`A. Nejat Ince, editor
`ISBN: 0-7923-9220-5
`Sequential Logic Synthesis, P. Ashar, S. Devadas, A. R. Newton
`ISBN: 0-7923-9187-X
`Sequential Logic Testing and Verification, A. Ghosh, S. Devadas, A. R. Newton
`ISBN: 0-7923-9188-8
`Introduction to the Design of Transconductor-Capacitor Filters,
`J. E. Kardontchik
`ISBN: 0-7923-9195-0
`The SynthesisApproach to Digital SygemDesign, P. Michel, U. Lauther, P. Duzy
`ISBN: 0-7923-9199-3
`Fault Covering Problems in Reconfigurable VLSI Systems, R.Libeskind-Hadas,
`N. Hassan, J. Cong, P. McKinley, C. L. Liu
`ISBN: 0-7923-9231-0
`High Level Synthesis of ASICs Under Timing and SynchronizPtion Congraints
`D.C. Ku, G. De Micheli
`ISBN: 0-7923-9244-2
`The SECD Microprocessor, A Verification Case Study, B.T. Graham
`ISBN: 0-7923-9245-0
`
`

`

`
`Field-Programmable Field-Programmable
`
`Gate Arrays Gate Arrays
`
`
`Stephen D. Brown Stephen D. Brown
`
`University о/ Toronto University о/ Toronto
`
`
`Robert J. Francis Robert J. Francis
`
`University o/Toronto University o/Toronto
`
`
`Jonathan Rose Jonathan Rose
`
`University o/Toronto University o/Toronto
`
`
`Zvonko G. Vranesic Zvonko G. Vranesic
`
`University ofToronto University ofToronto
`
`
`
`Springer Science+Business Media, LLC Springer Science+Business Media, LLC
`
`
`
`~. " ~. "
`
`

`

`Library оС Congress Cataloging-in-Publication Data
`
`Field-рrоgrаmmаbIе gate arrays / Stephen D. Brown ... [et al.].
`ст. -- (Кluwer international series in engineering and
`р.
`computer science ; SECS 180)
`Includes bibIiographical references and index.
`ISBN 978-1-4613-6587-7
`ISBN 978-1-4615-3572-0 (eBook)
`DOI 10.1007/978-1-4615-3572-0
`1. ProgrammabIe logic devices. 2. Gate array circuits.
`1. Brown, Stephen D.
`11. Series.
`ТК7872.L64F54 1992
`621.З9'5--dс20
`
`92-13785
`CIP
`
`Copyright © 1992 Ьу Springer Science+Business Media New York
`Originally published Ьу Кluwer Academic PubIishers in 1992
`Softcover reprint ofthe hardcover 1st edition 1992
`АН rights reserved. No part of this pubIication тау Ье reproduced, stored in а retrieval
`system or transmitted in апу form orby any means, mechanical, photo-copying, recording,
`or otherwise, without the prior written permission of the pubIisher,
`Springer Science+Business Media, LLC.
`
`Printed оп acid-free paper.
`
`

`

`To Susan,
`Ming,
`Barbara, Jessica, Hannah,
`and Anne
`
`

`

`Contents
`
`Preface ......................................................................................... xi
`
`Glossary ........................................................................................ xiii
`
`1
`1.1
`1.2
`1.2.1
`1.2.2
`1.3
`1.4
`1.5
`1.6
`
`Introduction to FPGAs ............................................................. .
`Evolution of Programmable Devices .......................................... .
`What is an FPGA? ...................................................................... ..
`Logic Blocks
`............................................................................... .
`Interconnection Resources
`.......................................................... .
`Economics of FPGAs .................................................................. .
`............................................................... .
`Applications of FPGAs
`Implementation Process
`.............................................................. .
`Concluding Remarks .................................................................. ..
`
`1
`2
`4
`5
`6
`6
`8
`9
`11
`
`Commercially Available FPGAs ............................................... 13
`2
`Programming Technologies ......................................................... 14
`2.1
`2.1.1 Static RAM Programming Technology.......................................
`15
`2.1.2 Anti-fuse Programming Technology............................................ 16
`2.1.3 EPROM and EEPROM Programming Technology..................... 18
`2.1.4 Summary of Programming Technologies
`..................... ............... 20
`2.2
`Commercially Available FPGAs .................................................. 20
`
`

`

`viii
`
`Field-Programmable Gate Arrays
`
`2.2.1 Xilinx FPGAs ............................................................................... 21
`2.2.2 Actel FPGAs
`................................................................................ 27
`2.2.3 Altera FPGAs ............................................................................... 30
`2.2.4 Plessey FPGA .............. ... ........ ... .... ... .... .... ... ........... ...................... 34
`2.2.5 Plus Logic FPGA ......................................................................... 34
`2.2.6 Advanced Micro Devices (AMD) FPGA ..................................... 35
`2.2.7 QuickLogic FPGA ........................................................................ 36
`2.2.8 Algotronix FPGA ......................................................................... 37
`.............................................................. 38
`2.2.9 Concurrent Logic FPGA
`2.2.lO Crosspoint Solutions FPGA .......... ... .... .............. .... .... ........... ....... 39
`2.3
`FPGA Design Flow Example ....................................................... 40
`Initial Design Entry ...................................................................... 41
`2.3.1
`2.3.2 Translation to XNF Format .......................................................... 41
`2.3.3 Partition ........................................................................................ 41
`2.3.4 Place and Route ............................................................................ 43
`2.3.5 Performance Calculation and Design Verification......................... 43
`2.4
`Concluding Remarks .............. ....... ... ........ .......... .... ...................... 43
`
`Technology Mapping for FPGAs .............................................. 45
`3
`Logic Synthesis ............................................................................ 46
`3.1
`3.1.1 Logic Optimization ...................................................................... 47
`3.1.2 Technology Mapping ................................................................... 48
`3.2
`Lookup Table Technology Mapping ............................................ 51
`3.2.1 The Chortle-crf Technology Mapper ........................................... 52
`3.2.2 The Chortle-d Technology Mapper .............................................. 69
`3.2.3 Lookup Table Technology Mapping in mis-pga .......................... 71
`3.2.4 Lookup Table Technology Mapping in Asyl ............................... 72
`3.2.5 The Hydra Technology Mapper ................................................... 72
`3.2.6 The Xmap Technology Mapper ................................................... 73
`3.2.7 The VISMAP Technology Mapper .............................................. 73
`3.3 Multiplexer Technology Mapping
`............................................... 74
`3.3.1 The Proserpine Technology Mapper ............................................ 75
`3.3.2 Multiplexer Technology Mapping in mis-pga ............................. 85
`3.3.3 The Amap and XAmap Technology Mappers
`............................. 85
`3.4
`Final Remarks
`.............................................................................. 86
`
`Logic Block Architecture ........................................................... 87
`4
`Logic Block Functionality versus Area-Efficiency...................... 88
`4.1
`4.1.1 Logic Block Selection . ... ............... ... ........... ....... ........ ... .... ........... 90
`4.1.2 Experimental Procedure ............................................................... 92
`4.1.3 Logic Block Area and Routing Model......................................... 93
`4.1.4 Experimental Results and Conclusions .... ... ........... ....... ....... .... .... 96
`
`

`

`Contents
`
`ix
`
`Impact of Logic Block Functionality on FPGA Perfonnance ..... 103
`4.2
`4.2.1 Logic Block Selection .................................................................. 104
`4.2.2 Logic Synthesis Procedure ................................................ ........... 106
`4.2.3 Model for Measuring Delay ......................................................... 107
`................................................................... 107
`4.2.4 Experimental Results
`4.3
`Final Remarks and Future Issues
`................................................. 115
`
`Routing for FPGAs ..................................................................... 117
`5
`Routing Tenninology ................................................................... 118
`5.1
`General Strategy for Routing in FPGAs
`...................................... 119
`5.2
`Routing for Row-Based FPGAs ................................................... 120
`5.3
`Introduction to Segmented Channel Routing ............................... 121
`5.3.1
`5.3.2 Definitions for Segmented Channel Routing
`............................... 124
`5.3.3 An Algorithm for I-Segment Routing
`......................................... 124
`........................................ 125
`5.3.4 An Algorithm for K-Segment Routing
`5.3.5 Results for Segmented Channel Routing
`..................................... 128
`5.3.6 Final Remarks for Row-Based FPGAs
`........................................ 129
`5.4
`Routing for Symmetrical FPGAs ................................................. 130
`5.4.1 Example of Routing in a Symmetrical FPGA .............................. 131
`5.4.2 General Approach to Routing in Symmetrical FPGAs ................ 132
`5.4.3 The CGE Detailed Router Algorithm
`.......................................... 133
`5.4.4 Final Remarks for Symmetrical FPGAs
`...................................... 145
`
`Flexibility of FPGA Routing Architectures ............................. 147
`6
`FPGA Architectural Assumptions .............. ........ .......................... 148
`6.1
`6.1.1 The Logic Block ............................ ................................ ............... 149
`6.1.2 The Connection Block .................................................................. 151
`6.1.3 The Switch Block ......................................................................... 153
`6.2
`Experimental Procedure ............................................................... 155
`6.3
`Limitations of the Study............................................................... 156
`................................................................... 157
`6.4
`Expenmental Results
`6.4.1 Effect of Connection Block Flexibility on Routability ................ 157
`6.4.2 Effect of Switch Block Flexibility on Routability ....................... 161
`6.4.3 Tradeoffs in the Flexibilities of the S and C Blocks .................... 162
`6.4.4 Track Count Requirements
`.......................................................... 164
`6.4.5 Architectural Choices .. ................................................................. 165
`6.5
`Conclusions.................................................................................. 166
`
`A Theoretical Model for FPGA Routing .................................. 169
`7
`Architectural Assumptions for the FPGA .................................... 170
`7.1
`Overview of the Stochastic Model................................ ............... 171
`7.2
`7.2.1 Model of Global Routing and Detailed Routing .......................... 172
`
`

`

`x
`
`Field-Programmable Gate Arrays
`
`Previous Research for Predicting Channel Densities . .................. 172
`7.3
`7.3.1 Predicting Channel Densities in FPGAs ...................................... 173
`7.4
`The Probability of Successfully Routing a Connection ............... 174
`7.4.1 The Logic Block to C Block Event .............................................. 176
`7.4.2 The S Block Events ...................................................................... 178
`7.4.3 The C Block to Logic Block Event .............................................. 182
`...........••....•..•..........•.......................•.......... 184
`7.4.4 The Probability of Rei
`7.5
`Using the Stochastic Model to Predict Routability ...................... 184
`7.5.1 Routability Predictions ................................................................. 186
`.. .... ... .... .................. ... .... .............. ........ ... ....... ........ 189
`7.6
`Final Remarks
`
`References ................................................................................... 191
`
`Index ............................................................................................ 203
`
`

`

`Preface
`
`This book deals with Field-Programmable Gate Arrays (FPGAs). which have
`emerged as an attractive means of implementing logic circuits. providing
`instant manufacturing turnaround and negligible prototype costs. They hold
`the promise of replacing much of the VLSI market now held by Mask(cid:173)
`Programmed Gate Arrays. FPGAs offer an affordable solution for custom(cid:173)
`ized VLSI. over a wide variety of applications and have also opened up new
`possibilities in designing reconfigurable digital systems.
`The book discusses the most important aspects of FPGAs in a textbook
`manner. It is not an edited collection of papers. It gives the reader a focused
`view of the key issues. using a consistent notation and style of presentation.
`It provides detailed descriptions of commercially available FPGAs and an
`in-depth treatment of the FPGA architecture and CAD issues that are the sub(cid:173)
`jects of current research.
`The material presented will be of interest to a variety of readers. In
`particular. it should appeal to:
`1.
`Readers who are not familiar with FPGA technology. but wish to be
`introduced to it. They will find an extensive survey that includes pro(cid:173)
`ducts from ten FPGA manufacturers. and a discussion of the most per(cid:173)
`tinent issues in the design of FPGA architectures. as well as the CAD
`tools needed to make effective use of them.
`
`

`

`xii
`
`Field-Programmable Gate Arrays
`
`2.
`
`Readers who already have an understanding of FPGAs, but who are
`interested in learning about the research directions that are of current
`interest.
`Chapter 1 introduces FPGA technology. It defines an FPGA to be a user(cid:173)
`programmable integrated circuit, consisting of a set of logic blocks that can
`be interconnected by general routing resources. A survey of commercial
`FPGA devices is provided in Chapter 2. This includes descriptions of the
`chip architectures and the basic technologies that are needed to to achieve the
`programmability. Chapter 3 deals with the Computer-Aided Design (CAD)
`task known as "technology mapping," which determines how a given logic
`circuit can be implemented using the logic blocks available in a particular
`FPGA. Included are examples of technology mapping algorithms for two
`types of FPGA. Chapter 4 considers the design of the logic block and its
`effect on the speed and logic density of FPGA circuits. It gives the results of
`several recent studies on this topic. The next chapter focuses on the CAD
`routing problem in FPGAs, where the interconnections between the logic
`blocks are realized. Examples of algorithms are presented for two different
`types of FPGA. Chapter 6 investigates the question of how the richness of
`the routing resources affects the FPGA's ability to implement circuits. It
`shows the results of a recent experimental study. The final Chapter also con(cid:173)
`siders the the routing resources, but uses a mathematical modelling tech(cid:173)
`nique. This provides an example of how FPGAs can be studied and
`improved through theoretical research.
`The authors wish to acknowledge the encouragement and help of Carl
`Harris, of Kluwer Academic Publishers, who has ensured that this book was
`produced in optimum time. We would also like to express our appreciation
`to the many members of the FPGA research project at the University of
`Toronto, whose efforts have contributed both to the information presented in
`this book and to the general understanding of the many complex issues in the
`design and use of FPGAs. These include Professors Paul Chow and David
`Lewis, as well as Kevin Chung, Bahram Fallah, Keith Farkas, Alan Huang,
`Carl Mizuyabu, Gerard Paez, Immanuel Rahardja, Soon Ong Seo, Satwant
`Singh, Benjamin Tseng, and Jean-Michel Vuillamy. Professor Mart Molle
`provided valuable comments on the stochastic modelling chapter. Jack
`Kouloheris and Abbas EI Gamal of Stanford University generously provided
`several figures and engaging discussions. The authors gratefully ack(cid:173)
`nowledge enlightening conversations with many people in the FPGA indus(cid:173)
`try and environs. In particular Steve Trimberger, Bill Carter and Erich Goet(cid:173)
`ting from Xilinx, Jonathan Greene and Andy Haines at Actel, Stan Kopec
`and Clive McCarthy from Altera, Dwight Hill from AT&T Bell Labs, and
`David Marple from Crosspoint.
`
`

`

`Glossary
`
`Anti-Fuse
`a programming element switch which is normally open, and which
`closes when a high voltage is placed across its terminals.
`
`Area-efficiency (of an FPGA architecture)
`the amount of area required by the architecture to implement a given
`amount of logic circuitry.
`
`Binary Decision Diagram (BDD)
`a method of representing Boolean logic expressions using a selector
`element and Shannon decomposition ..
`
`Channel
`the rectangular area that lies between two rows or two columns of logic
`blocks. A routing channel contains a number of tracks.
`
`Channel Density
`the maximum number of connections in parallel anywhere in a channel.
`
`

`

`xiv
`
`Field-Programmable Gate Arrays
`
`Channel Segment
`a section of the routing channel.
`
`Connection Block
`a structure in the routing architecture of an FPGA that provides connec(cid:173)
`tions between the pins of the logic block and the routing channels.
`
`EEPROM
`Electrically Erasable Programmable Read Only Memory.
`
`EPROM
`Erasable Programmable Read Only Memory.
`
`Field-Programmable Device
`a device that can be configured by the user with simple electrical equip(cid:173)
`ment.
`
`Flexibility (of routing architecture)
`the number of choices offered by a routing architecture in making a set
`of connections.
`
`FPGA Architecture
`the logic block, routing and I/O block structure of an FPGA.
`
`Fe
`
`a parameter specifying connection block flexibility.
`
`Fs
`
`a parameter specifying switch block flexibility.
`
`Global Router
`a CAD tool that determines which set of channels each connection trav(cid:173)
`els through.
`
`Logic Block
`the basic unit of the FPGA that performs the combinational and
`sequential logic functions.
`
`Logic Block Architecture
`the choice of combinational and sequential functiolls of the logic block,
`
`

`

`Glossary
`
`xv
`
`and their interconnection within that block.
`
`Logic Block Functionality
`the number of different combinational functions that a logic block can
`implement.
`
`Logic Density (of an FPGA)
`the amount of logic capability per unit area that an FPGA achieves.
`
`Lookup Table (LUT)
`a digital memory with K address lines that can implement any function
`of K inputs by placing the truth table into the memory.
`
`Mask-Programed Gate Array (MPGA)
`an IC with uncommitted arrays of transistors that are personalized by
`two or more layers of metal connections.
`
`PAL Programmable Array Logic.
`
`Pass Transistor
`a transistor used as a switch to make a connection between two points.
`
`Placement
`the CAD task of assignment of logic blocks to physical locations.
`
`PLD Programmable Logic Device.
`
`Programmable Inversion
`a feature of a logic block which allows that inputs or outputs can be
`programmed in true or complemented form.
`
`Programming Technology
`the fundamental method of customization in an FPGA that provides the
`user-programmability. Examples are SRAM, anti-fuse, EPROM and
`EEPROM.
`
`Programmable Switch
`a switch in an FPGA that is used to connect two wire segments, and can
`
`

`

`xvi
`
`Field-Programmable Gate Arrays
`
`be programmably opened or closed using the programming technology.
`
`Routability
`the percentage of required connections successfully completed after
`routing.
`
`Routing Architecture
`the distribution and length of wire segments, and the manner in which
`the wire segments and programmable switches are placed in the routing
`channels.
`
`Segmented Channel
`a routing channel where tracks contain wire segments of varying
`lengths.
`
`Switch Block
`a structure in the routing architecture which connects one routing chan(cid:173)
`nel to another.
`
`Technology Mapping
`the CAD task of converting boolean expressions into a network that
`consists of only logic blocks.
`
`Track (routing)
`a straight section of wire that spans the entire width or length of a rout(cid:173)
`ing channel. A track can be composed of a number of wire segments of
`various lengths.
`
`Wire Segment
`a length of metal wire that has programmable switches on either end,
`and possibly switches connected to the middle of the wire. It cannot be
`broken by a programmable switch, or else it would be two wire seg(cid:173)
`ments.
`
`

`

`Field-Programmable
`Gate Arrays
`
`

`

`CHAPTER
`1
`Introduction
`to FPGAs
`
`Very Large Scale Integration (VLSI) technology has opened the door to
`the implementation of powerful digital circuits at low cost. It has become
`possible to build chips with more than a million transistors, as exemplified
`by state-of-the-art microprocessors. Such chips are realized using the full(cid:173)
`custom approach, where all parts of a VLSI circuit are carefully tailored to
`meet a set of specific requirements. Semi-custom approaches such as Stan(cid:173)
`dard Cells and Mask-Programmed Gate Arrays (MPGAs) have provided an
`easier way of designing and manufacturing Application-Specific Integrated
`Circuits (ASICs).
`Each of these techniques, however, requires extensive manufacturing
`effort, taking several months from beginning to end. This results in a high
`cost for each unit unless large volumes are produced, because the overhead to
`begin production of such chips ranges from $20,000 to $200,000.
`In the electronics industry it is vital to reach the market with new pro(cid:173)
`ducts in the shortest possible time, and so reduced development and produc(cid:173)
`tion time is essential. Furthermore, it is important that the financial risk
`incurred in the development of a new product be limited so that more new
`ideas can be prototyped. Field-Programmable Gate Arrays (FPGAs) have
`emerged as the ultimate solution to these time-to-market and risk problems
`because they provide instant manufacturing and very low-cost prototypes.
`An FPGA can be manufactured in only minutes, and prototype costs are on
`the order of $100. A field-programmable device is a device in which the final
`
`

`

`2
`
`Field-Programmable Gate Arrays
`
`logic structure can be directly configured by the end user, without the use of
`an integrated circuit fabrication facility.
`The last three years have seen FPGAs grow from a tiny market niche
`into a $200 million business. It is expected that almost one billion dollars
`worth of FPGAs will be sold every year by 1996, representing a significant
`proportion of the IC market.
`This book is concerned with many aspects of FPGA architecture and
`the Computer-Aided Design Tools needed in their use. This chapter begins
`by describing the evolution of programmable devices and gives a brief intro(cid:173)
`duction to FPGAs, their economics and their use. It also provides an indica(cid:173)
`tion of the material presented in subsequent chapters.
`
`1.1 Evolution of Programmable Devices
`Programmable devices have long played a key role in the design of
`digital hardware. They are general-purpose chips that can be configured for a
`wide variety of applications. The first type of programmable device to
`the Programmable Read-Only Memory
`achieve widespread use was
`(PROM). A PROM is a one-time programmable device that consists of an
`array of read-only cells. A logic circuit can be implemented by using the
`PROM's address lines as the circuit's inputs, and the circuit's outputs are
`then defined by the stored bits. With this strategy, any truth-table function
`can be implemented.
`Two basic versions of PROMs are available, those that can be pro(cid:173)
`grammed only by the manufacturer, and those that can be programmed by
`the end-user. The first type is called mask-programmable and the second is
`field-programmable. In the context of implementing logic circuits, superior
`speed-performance can be obtained with a mask-programmable chip because
`connections within the device can be hardwired during manufacture. In con(cid:173)
`trast, field-programmable connections always involve some sort of pro(cid:173)
`grammable switch (such as a fuse) that is inherently slower than a hardwired
`connection. However, a field-programmable device offers advantages that
`often outweigh its speed-performance shortcomings:
`•
`Field-programmable chips are less expensive at low volumes than
`mask-programmable devices because they are standard off-the-shelf
`parts. An IC manufacturing facility must be "tooled" to begin produc(cid:173)
`tion of a mask-programmed device which incurs a large overhead cost.
`Field-programmable chips can be programmed
`immediately,
`in
`minutes, whereas mask-programmable devices must be manufactured
`by a foundry over a period of weeks or months.
`
`•
`
`

`

`Introduction to FPGAs
`
`3
`
`Two field-programmable variants of the PROM, the Erasable Pro(cid:173)
`grammable Read-Only Memory (EPROM) and the Electrically Erasable
`Programmable Read-Only Memory (EEPROM) offer an additional advan(cid:173)
`tage; both can be erased and re-programmed many times. In some applica(cid:173)
`tions, and particularly during the early stages of a logic circuit's design, re(cid:173)
`programmability is an attractive feature.
`While PROMs are a viable alternative for realizing simple logic cir(cid:173)
`cuits, it is clear that the structure of a PROM is best suited for the implemen(cid:173)
`tation of computer memories. Another type of programmable device,
`designed specifically for implementing logic circuits, is the Programmable
`Logic Device (PLD). A PLD typically comprises an array of AND gates con(cid:173)
`nected to an array of OR gates. A logic circuit to be implemented in a PLD
`is thus represented in sum-of-products form. The most basic version of a
`PLD is the Programmable Array Logic (PAL). A PAL consists of a pro(cid:173)
`grammable AND-plane followed by a fixed OR-plane. The outputs of the
`OR gates can be optionally registered by a flip-flop in most chips. PALs also
`offer the advantages of field-programmability, which is obtained using one of
`fuse, EPROM or EEPROM technology.
`A more flexible version of the PAL is the Programmable Logic Array
`(PLA). PLAs also comprise an AND-plane followed by an OR-plane, but in
`this case connections to both planes are programmable. They are available in
`both mask-programmable and field-programmable versions.
`With their simple two-level structure, both types of PLDs described
`above allow high speed-performance implementations of logic circuits.
`However, the simple structure also leads to their main drawback. They can
`only implement small logic circuits that can be represented with a modest
`number of product terms, because their interconnection structure would grow
`impractically large if the number of product terms were increased.
`The most general type of programmable devices consists of an array of
`uncommitted elements that can be interconnected according to a user's
`specifications. Such is the class of devices known as Mask-Programmable
`Gate Arrays (MPGAs). The most popular MPGAs consist of rows of transis(cid:173)
`tors that can be interconnected to implement a desired logic circuit. User(cid:173)
`specified connections are available both within the rows (to implement basic
`logic gates) and between the rows (to connect the basic gates together). In
`addition to the rows of transistors, some circuitry is provided that handles
`input and output to the external pins of the Ie package. In an MPGA, all the
`mask layers that define the circuitry of the chip are pre-defined by the
`manufacturer, except those that specify the final metal layers. These metal
`layers are customized to connect the transistors in the array, thereby
`
`

`

`4
`
`Field-Programmable Gate Arrays
`
`implementing the desired circuit. MPGAs have a large non-recurring
`engineering (NRE) cost because of the need to generate the metal mask layer
`and manufacture the chip. However, the unit cost decreases significantly
`when large volumes (more than 1000 chips) are required.
`The main advantage of MPGAs over PLDs is that they provide a gen(cid:173)
`eral structure that allows the implementation of much larger circuits. This is
`primarily due to their interconnection structure, which scales proportionally
`with the amount of logic. On the other hand, since MPGAs are mask(cid:173)
`programmable, they require significant manufacturing time and incur high
`initial costs. A Field-Programmable Gate Array combines the programma(cid:173)
`bility of a PLD and the scalable interconnection structure of an MPGA. This
`results in programmable devices with much higher logic density.
`
`1.2 What is an FPGA?
`Like an MPGA, an FPGA consists of an array of uncommitted ele(cid:173)
`ments that can be interconnected in a general way. Like a PAL, the intercon(cid:173)
`nections between the elements are user-programmable. FPGAs were intro(cid:173)
`duced in 1985 by the Xilinx Company. Since then, many different FPGAs
`have been developed by a number of companies: Actel, Altera, Plessey, Plus,
`Advanced Micro Devices (AMD), QuickLogic, Algotronix, Concurrent
`Logic, and Crosspoint Solutions, among others. Chapter 2 describes the
`FPGAs produced by each of these ten companies.
`Figure 1.1 shows a conceptual diagram of a typical FPGA. As dep(cid:173)
`icted, it consists of a two-dimensional array of logic blocks that can be con(cid:173)
`nected by general interconnection resources. The interconnect comprises
`segments of wire, where the segments may be of various lengths. Present in
`the interconnect are programmable switches that serve to connect the logic
`blocks to the wire segments, or one wire segment to another. Logic circuits
`are implemented in the FPGA by partitioning the logic into individual logic
`blocks and then interconnecting the blocks as required via the switches.
`To facilitate the implementation of a wide variety of circuits, it is
`important that an FPGA be as versatile as possible. This means that the
`design of the logic blocks, coupled with that of the interconnection resources,
`should facilitate the implementation of a large number of digital logic cir(cid:173)
`cuits. There are many ways to design an FPGA, involving tradeoffs in the
`complexity and flexibility of both the logic blocks and the interconnection
`resources. This book will address most of the relevant issues involved.
`
`

`

`Introduction to FPGAs
`
`5
`
`Interconnection
`Resources
`
`Logic Block
`
`Figure 1.1 - A Conceptual FPGA.
`
`1.2.1 Logic Blocks
`The structure and content of a logic block are called its architecture.
`Logic block architectures can be designed in many different ways. As shown
`by the examples in Chapter 2, some FPGA logic blocks are as simple as 2-
`input NAND gates. Other blocks have more complex structure, such as mul(cid:173)
`tiplexers or lookup tables. In some FPGAs, a logic block corresponds t