PREFACE

The field-programmable gate array (FPGA) is a relatively new type of component for the construction of electronic systems, particularly those using digital, or more correctly logical, circuit principles. It consists of an array of functional blocks along with an interconnection network, and as the name implies, its configuration can be determined in the field, that is, at the point of application. The specific function of each block and the connections between blocks are prescribed by the user. For the most part we will be concerned with reprogrammable FPGAs in this text, since they offer more flexibility than fuse-programmable devices. This choice is not a matter of taste. Already the FPGA market has a wide range of architectures and alternative ways of controlling configurations. We do not dismiss fuse-programmable architectures, which clearly already provide fast, economical, and compact implementations for logic designs. But it is almost like comparing a ROM-based computer with the more-general RAM-based one. Moreover, this field is at such an early stage of development that no one yet knows the most appropriate design methodologies and run-time environments. The FPGA takes its place in the continuing evolution of very-large-scale integrated (VLSI) circuit technology toward denser and faster circuits. It already provides, for many applications, an adequate number of transistors in a single chip package for the functional blocks, switches for the routing network, and the memory capacity to control both. The prospects for further increases in both circuit density and speed of operation are excellent, since VLSI circuit density continues to double every 2 to 3 years or so. Indeed, billion-transistor (10⁹) chips are anticipated by the turn of the century.

Clearly, the ability to reconfigure an electronic component, either to correct an error, or to change an application, has economic benefits, but we suggest that the impact of the FPGA concept is much more profound, in that a logic system may be dynamically reconfigured to match changing circumstances. This is a new computing paradigm whose potential is far-reaching. Although present-day FPGA components have only a few thousand or tens of thousands of gates, future ones will have hundreds of thousands or eventually millions of gates. We may expect to see the development of pipelined and parallel processing in which the system configuration changes dynamically. For example, a graphic processing operation might use three processors for three-dimensional calculations and switch to two processors for screen-related calculations. An image processing system could divide computations into parallel tasks for a large number of processors realized within the same FPGA chip. While such schemes may seem futuristic, they suggest that the FPGA should not be thought of as just a VLSI component that replaces others, but as a concept with distinctive new possibilities.

Returning to present-day realizations, the FPGA has significant advantages for the development of prototype systems and their early introduction to the market. The benefits are similar to those associated with the introduction of the microprocessor in the late 1970s, such as programmability and adaptability, but with additional advantages in speed, compactness, and design protection. From an educational viewpoint, designing with FPGAs requires computer assistance at almost every stage of design, including detailed specification, simulation, placement, and routing, and calls for an overall systematic design methodology. We consider this to be an important aspect in the education of future engineers, which should improve both the performance and the quality of the systems they produce. At the same time, the increase in designer productivity makes it possible to consider alternative implementations at a higher level than previously, and should not cramp the creativity of a system designer.

ABOUT THE BOOK

The book is intended to serve the needs of several constituencies:

• As a text to accompany an undergraduate course in which students are introduced to FPGAs for the first time, and in which laboratory work is a likely accompaniment.
• As a graduate-level text, with introductory aspects as well as more advanced applications and interest in the underlying VLSI structures of FPGAs, computer-aided design (CAD) algorithms for functional and physical layout.
• For the professional engineer who wishes to obtain an appreciation of FPGA principles and prospects.

In all cases, we assume a familiarity with the basic principles of logic circuits and their realization as digital systems with commonly available components. We have paid more attention than is customary to the nature of the emerging industry and business aspects, since we believe that these should be of interest to all of the preceding categories of reader. VLSI technology has been an exciting business to be in during its formative years, and technical considerations cannot be divorced from financial and marketing aspects.

Chapter 1 discusses the alternative ways in which a logic system can be realized, and the variety of technologies available for the purpose. It considers the design process itself as worthy of study, and highlights various design methodologies that have emerged. Chapter 2 is mostly a review of logical and electrical aspects of digital systems with which the reader should already be familiar, with additional material on implementing state machines so as to take advantage of common FPGA properties. Chapter 3 reviews the architecture of FPGAs, along with the options and trade-offs for different approaches. While the industry is still in its formative years, radically different directions have been taken in setting up the underlying structures, and new architectures will continue to emerge. The chapter concludes with a discussion of appropriate benchmarks for FPGA comparison. Chapter 4 is concerned with CAD for FPGA applications, and attempts to give a comprehensive, manufacturer-independent view of the place of CAD tools, as well as some elementary and specific examples for two particular systems. In Chapter 5 there are a number of case studies of small-and modest-scale designs implemented on different FPGA architectures, along with a substantial example of a parallel controller that stretched the limits of an FPGA architecture and its supporting CAD software. Chapter 6 is concerned with advanced applications of FPGAs, including several large-scale examples in which the FPGA is used as a novel computing structure. The term “custom computing machine” has been coined to describe such systems, and a number of illustrations already exist to show the enormous potential of arrays of FPGA chips for some of the present-day “Grand Challenge” problems, such as high-speed string comparison for the Human Genome Project. Business issues are the focus of Chapter 7, and include a perspective on the start-up and growth of new companies in this field, as well as the relevance of market factors to FPGA applications in the context of other ways of implementing digital systems. The chapter concludes with a short review of intellectual property aspects—how to protect one’s own or one’s company’s ideas in a highly competitive environment. The FPGA has interesting new possibilities for design protection, and can be made extraordinarily secure compared with other VLSI technologies. Chapter 8 was added to the text as late as possible and reviews some recent developments. Much of this chapter has been contributed by the manufacturers concerned, and we appreciate their cooperation. There is a Glossary containing explanations of the technical terms, particularly acronyms, used in the field.

Readers should be aware that we have not included full details of FPGA technical data, nor specific information on particular CAD support software. This decision is based on the fact that well-written technical handbooks are available from the FPGA manufacturers and CAD software vendors, and also recognizes that the publication cycle of a text is long, compared with ever-changing computer software and the intervals between announcements of new FPGA families and devices. For the most part our examples are from Xilinx Inc. and Algotronix Ltd., and readers should contact their nearest distributor for technical information.

A few months before the manuscript was completed, Algotronix Ltd. was acquired by Xilinx Inc., and in the new circumstances two of the original authors, John Gray and Tom Kean, had to withdraw. We believe that the pioneering work they carried out on fine-grain FPGA structures will be recognized as a valuable and complementary alternative to more widely accepted methods used in the industry.

BACKGROUND AND APPLICABILITY

As mentioned earlier, we assume that the reader is already familiar with logic circuits, including the concepts of state machines and their realization. A university-level introductory course should be adequate, and even better if supplemented by laboratory experience, for example, with a logic breadboarding system. Chapter 2 provides relevant review material. In considering using this book as a text, it is worth giving thought to the long-term impact of this technology on both undergraduate and graduate education, since FPGAs could be relevant to a sequence of classes related to digital design and computer architecture.

This book could be used as a text for an introductory undergraduate- or graduate-level class on field-programmable logic arrays and their applications. This might be offered in electrical engineering, computer engineering, or computer science. It should be combined with exposure to a practical FPGA system, including supporting CAD hardware and software. It is planned to produce an Instructor’s Manual which will include suggestions and advice, as well as worked examples, suggestions for projects, and solutions. This manual will also suggest useful sources of information. The previously listed classes could focus on one particular FPGA architecture, but should include comparisons with other architectures, if at all possible. We recommend that the broader aspects, including design methodologies and business issues, be included in such courses.

The material in the text can be usefully linked to an introductory VLSI design class. Often such courses emphasize full-custom design, and already include most of the basic elements found in an FPGA. While the underlying architecture is highly proprietary, many of the issues in full-custom design, such as global and local communication, memory, input/output pads, general-purpose logic blocks, are particularly relevant. The FPGA also allows much faster turnaround than for full-custom design, and exposure to this material gives students a more balanced perspective on digital system implementation.

The book could be used in conjunction with a project-oriented class, particularly for computer engineering or computer science students. Assuming that adequate CAD support is available, FPGAs should contribute to a considerable increase in student productivity, compared with traditional digital breadboard systems. An added advantage is the emphasis on a systematic approach to engineering design, and the high-quality design documentation that is readily produced from the CAD system. This is highly relevant to the emphasis placed on design by the U.S. Accreditation Board for Engineering and Technology (ABET), which defines “engineering design” as [ABET90]:

. . . the process of devising a system, component, or process to meet desired needs.... Among the fundamental elements of the design process are the establishment of objectives and criteria, synthesis, analysis, construction, testing, and evaluation. The engineering component of a curriculum must include at least some of the following features: development of student creativity, use of open-ended problems, development and use of design methodology, formulation of design problem statements, consideration of alternative solutions, feasibility considerations, and detailed system descriptions. Further, it is essential to include a variety of realistic constraints such as economic factors, safety, reliability, aesthetics, ethics, and social impact.

We submit that FPGAs can provide an outstanding design environment for engineering education.

Computer architecture courses are often accompanied by the use of a simulator for trying out proposed architectures. The FPGA and its CAD simulators should be very attractive for such courses, with the added advantage of implementation at speeds much nearer to those of a real system than the slowness of a software simulator. For some of the less-complex FPGA architectures, it is possible to independently develop CAD software, including simulators, and much exploration can be done without the actual hardware parts. The demise of Algotronix as a source of parts should not discourage exploration of this and other novel architectures by simulation. We have already found such a simulator useful for debugging purposes, and they are easy to develop for fine-grain architectures.

At the graduate-level, FPGAs can provide useful target architectures for classes in CAD for digital systems. These include physical design issues such as partitioning, placement, and routing, along with logic simplification and simulation. Clearly, simpler architectures are to be preferred to more complex ones, and it may be necessary to approach the manufacturer for details of CAD file formats, and so forth. Even outside the classroom context, students should be encouraged to develop software aids for FPGAs. These goals would be easier to attain if FPGA vendors actively encouraged more open design systems for their products.

A superficial pass through the book may detect more emphasis on wiring management and layout issues than might be expected for a component that, in an ideal world, would be designed and configured totally automatically. There is a close parallel with full-custom VLSI design and much scope for designer ingenuity by exploiting the inherent massive parallelism, particularly by pipelining.

In summary, the FPGA can provide a realistic implementation vehicle for complex digital systems that are beyond the limits of conventional breadboard logic, and where there is insufficient time for full-custom, standard-cell, or even mask-programmable gate array implementation.

ERRORS AND OMISSIONS

Despite the best efforts of the author team, errors will get through to the printed version. We would appreciate being informed of any such errors, and will endeavor to see that they are identified and corrected in subsequent printings.

ACKNOWLEDGMENTS

First we wish to express our sincere gratitude to our former coauthors John Gray and Tom Kean. Without their enthusiasm, experience, and cooperation the book would never have been started. The authors wish to thank a number of individuals who have contributed to the development of this book. Erik Dagless, Jonathan M. Saul, and Tomasz Kozlowski of the University of Bristol provided the material on parallel state machines in Chapter 2, and the two former authors provided the video controller example given in Chapter 5. Christopher Kappler of Syracuse University contributed the sorter design given in the same chapter, and, along with Kang Shen, developed the self-timed approach to genetic string matching described in Chapter 6. Roberto Melo provided the multiplier examples in Chapter 5 as part of a wider study that included standard-cell designs. Fred Furtek kindly agreed to the insertion of his original and thought-provoking approach to motion estimation that is reprinted, with permission, at the end of Chapter 6. Ted Hagelin of the Syracuse University College of Law provided much of the background on intellectual property issues in the latter half of Chapter 7, and Harold Burstyn made some important corrections to one of the author’s interpretations. Amr Mohsen, Wayne Luk, Steven Sillich, and Steven Trimberger were very helpful in commenting on draft versions of the text. Ed Sibert of Syracuse University devoted countless late hours in the production of the final manuscript in Latex. Mary Haas-Wendel became involved in the development of the manuscript at a late stage. She made significant contributions to the business issues chapter based on her experience in the corporate world as well as providing much editorial help. Finally, there are a host of persons in both academia and industry who have encouraged the authors directly and indirectly, through papers and discussions.

The authors are of course solely responsible for the views expressed in this book.

BIBLIOGRAPHY