logo资料库

COMPUTER ARITHMETIC Algorithms and Hardware Designs 2nd.pdf

发布时间：2022-06-14 发布人：admin 分类：说明书 资料大小：8.19M 资料格式：pdf 举报 版权申诉
第1页 / 共641页
第2页 / 共641页
第3页 / 共641页
第4页 / 共641页
第5页 / 共641页
第6页 / 共641页
第7页 / 共641页
第8页 / 共641页
资料共641页，剩余部分请下载后查看
    COMPUTER ARITHMETIC Algorithms and Hardware Designs S E C O N D E D I T I O N Behrooz Parhami Department of Electrical and Computer Engineering University of California, Santa Barbara NEW YORK OXFORD OXFORD UNIVERSITY PRESS 2010
    Oxford University Press, Inc., publishes works that further Oxford Universitiy’s objective of excellence in research, scholarship, and education. Oxford New York Auckland Cape Town Dar es Salaam Hong Kong Karachi Kuala Lumpur Madrid Melbourne Mexico City Nairobi New Delhi Shanghai Taipei Toronto with offices in Argentina Austria Brazil Chile Czech Republic France Greece Guatemala Hungary Italy Japan Poland Portugal Singapore South Korea Switzerland Thailand Turkey Ukraine Vietnam Copyright © 2010 by Oxford University Press, Inc. Published by Oxford University Press, Inc. 198 Madison Avenue, New York, New York 10016 http://www.oup.com Oxford is a registered trademark of Oxford University Press All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior permission of Oxford University Press. Library of Congress Cataloging-in-Publication Data Parhami, Behrooz. Computer arithmetic / Behrooz Parhami. – 2nd ed. p. cm. ISBN 978-0-19-532848-6 1. Computer arithmetic. 2. Computer algorithms. I. Title. QA76.9.C62P37 2009 005.1—dc22 2009034155 Printing number: 9 8 7 6 5 4 3 2 1 Printed in the United States of America on acid-free paper
    To the memory of my father, Salem Parhami (1922–1992), and to all others on whom I can count for added inspiration, multiplied joy, and divided anguish.
    PREFACE to the first edition THE CONTEXT OF COMPUTER ARITHMETIC Advances in computer architecture over the past two decades have allowed the per- formance of digital computer hardware to continue its exponential growth, despite increasing technological difficulty in speed improvement at the circuit level. This phe- nomenal rate of growth, which is expected to continue in the near future, would not have been possible without theoretical insights, experimental research, and tool- building efforts that have helped transform computer architecture from an art into one of the most quantitative branches of computer science and engineering. Better under- standing of the various forms of concurrency and the development of a reasonably efficient and user-friendly programming model have been key enablers of this success story. The downside of exponentially rising processor performance is an unprecedented increase in hardware and software complexity. The trend toward greater complexity is not only at odds with testability and certifiability but also hampers adaptability, perfor- mance tuning, and evaluation of the various trade-offs, all of which contribute to soaring development costs. A key challenge facing current and future computer designers is to reverse this trend by removing layer after layer of complexity, opting instead for clean, robust, and easily certifiable designs, while continuing to try to devise novel methods for gaining performance and ease-of-use benefits from simpler circuits that can be readily adapted to application requirements. In the computer designers’ quest for user-friendliness, compactness, simplicity, high performance, low cost, and low power, computer arithmetic plays a key role. It is one of oldest subfields of computer architecture. The bulk of hardware in early digital com- puters resided in accumulator and other arithmetic/logic circuits. Thus, first-generation computer designers were motivated to simplify and share hardware to the extent pos- sible and to carry out detailed cost–performance analyses before proposing a design. Many of the ingenious design methods that we use today have their roots in the bulky, power-hungry machines of 30–50 years ago. In fact computer arithmetic has been so successful that it has, at times, become transparent. Arithmetic circuits are no longer dominant in terms of complexity; registers, memory and memory management, instruction issue logic, and pipeline control have xix
    xx Preface become the dominant consumers of chip area in today’s processors. Correctness and high performance of arithmetic circuits are routinely expected, and episodes such as the Intel Pentium division bug of the mid 1990s are indeed rare. The preceding context is changing for several reasons. First, at very high clock rates, the interfaces between arithmetic circuits and the rest of the processor become critical. Arithmetic units can no longer be designed and verified in isolation. Rather, an integrated design optimization is required, which makes the development even more complex and costly. Second, optimizing arithmetic circuits to meet design goals by taking advantage of the strengths of new technologies, and making them tolerant to the weaknesses, requires a reexamination of existing design paradigms. Finally, incorporation of higher-level arithmetic primitives into hardware makes the design, optimization, and verification efforts highly complex and interrelated. This is why computer arithmetic is alive and well today. Designers and researchers in this area produce novel structures with amazing regularity. Carry-lookahead adders comprise a case in point. We used to think, in the not so distant past, that we knew all there was to know about carry-lookahead fast adders. Yet, new designs, improvements, and optimizations are still appearing. The IEEE 754 standard floating-point format has removed many of the concerns with compatibility and error control in floating-point computations, thus resulting in new designs and products with mass-market appeal. Given the arithmetic-intensive nature of many novel application areas (such as encryp- tion, error checking, and multimedia), computer arithmetic will continue to thrive for years to come. THE GOALS AND STRUCTURE OF THIS BOOK The field of computer arithmetic has matured to the point that a dozen or so texts and reference books have been published. Some of these books that cover computer arith- metic in general (as opposed to special aspects or advanced/unconventional methods) are listed at the end of the preface. Each of these books has its unique strengths and has contributed to the formation and fruition of the field. The current text, Computer Arith- metic: Algorithms and Hardware Designs, is an outgrowth of lecture notes the author developed and refined over many years. Here are the most important features of this text in comparison to the listed books: Division of material into lecture-size chapters. In my approach to teaching, a lecture is a more or less self-contained module with links to past lectures and pointers to what will transpire in future. Each lecture must have a theme or title and must proceed from motivation, to details, to conclusion. In designing the text, I strived to divide the material into chapters, each of which is suitable for one lecture (1–2 hours). A short lecture can cover the first few subsections, while a longer lecture can deal with variations, peripheral ideas, or more advanced material near the end of the chapter. To make the structure hierarchical, as opposed to flat or linear, lectures are grouped into seven parts, each composed of four lectures and covering one aspect of the field (Fig. P.1).
    Preface xxi Emphasis on both the underlying theory and actual hardware designs. The ability to cope with complexity requires both a deep knowledge of the theoretical underpin- nings of computer arithmetic and examples of designs that help us understand the theory. Such designs also provide building blocks for synthesis as well as reference points for cost-performance comparisons. This viewpoint is reflected in, for example, the detailed coverage of redundant number representations and associated arithmetic algorithms (Chapter 3) that later lead to a better understanding of various multiplier designs and on-line arithmetic. Another example can be found in Chapter 22, where coordinate rotation digital computer, or CORDIC, algorithms are introduced from the more intuitive geometric viewpoint. Linking computer arithmetic to other subfields of computing. Computer arithmetic is nourished by, and in turn nourishes, other subfields of computer architecture and technology. Examples of such links abound. The design of carry-lookahead adders became much more systematic once it was realized that the carry computation is a special case of parallel prefix computation that had been extensively studied by researchers in parallel computing. Arithmetic for and by neural networks is an area that is still being explored. The residue number system has provided an invaluable tool for researchers interested in complexity theory and the limits of fast arithmetic, as well as to the designers of fault-tolerant digital systems. Wide coverage of important topics. The text covers virtually all important algorith- mic and hardware design topics in computer arithmetic, thus providing a balanced and complete view of the field. Coverage of unconventional number representa- tion methods (Chapters 3 and 4), arithmetic by table lookup (Chapter 24), which is becoming increasingly important, multiplication and division by constants (Chapters 9 and 13), errors and certifiable arithmetic (Chapters 19 and 20), and the topics in Part VII (Chapters 25–28) do not all appear in other textbooks. Unified and consistent notation and terminology throughout the text. Every effort is made to use consistent notation and terminology throughout the text. For example, r always stands for the number representation radix and s for the remainder in division or square-rooting. While other authors have done this in the basic parts of their texts, many tend to cover more advanced research topics by simply borrowing the notation and terminology from the reference source. Such an approach has the advantage of making the transition between reading the text and the original reference source easier, but it is utterly confusing to the majority of the students, who rely on the text and do not consult the original references except, perhaps, to write a research paper. SUMMARY OF TOPICS The seven parts of this book, each composed of four chapters, were written with the following goals. Part I sets the stage, gives a taste of what is to come, and provides a detailed per- spective on the various ways of representing fixed-point numbers. Included are detailed discussions of signed numbers, redundant representations, and residue number systems.
    xxii Preface Part II covers addition and subtraction, which form the most basic arithmetic building blocks and are often used in implementing other arithmetic operations. Included in the discussions are addition of a constant (counting), various methods for designing fast adders, and multioperand addition. Part III deals exclusively with multiplication, beginning with the basic shift/add algorithms and moving on to high-radix, tree, array, bit-serial, modular, and a variety of other multipliers. The special case of squaring is also discussed. Part IV covers division algorithms and their hardware implementations, beginning with the basic shift/subtract algorithms and moving on to high-radix, prescaled, modular, array, and convergence dividers. Part V deals with real number arithmetic, including various methods for representing real numbers, floating-point arithmetic, errors in representation and computation, and methods for high-precision and certifiable arithmetic. Part VI covers function evaluation, beginning with the important special case of square-rooting and moving on to coordinate rotation digital computer, or CORDIC, algorithms, followed by general convergence and approximation methods, including the use of lookup tables. Part VII deals with broad design and implementation topics, including pipelining, low-power arithmetic, and fault tolerance. This part concludes by providing historical perspective and examples of arithmetic units in real computers. POINTERS ON HOW TO USE THE BOOK For classroom use, the topics in each chapter of this text can be covered in a lecture lasting 1–2 hours. In his own teaching, the author has used the chapters primarily for 1.5-hour lectures, twice a week, in a 10-week quarter, omitting or combining some chapters to fit the material into 18–20 lectures. But the modular structure of the text lends itself to other lecture formats, self-study, or review of the field by practitioners. In the latter two cases, readers can view each chapter as a study unit (for one week, say) rather than as a lecture. Ideally, all topics in each chapter should be covered before the reader moves to the next chapter. However, if fewer lecture hours are available, some of the subsections located at the end of chapters can be omitted or introduced only in terms of motivations and key results. Problems of varying complexities, from straightforward numerical examples or exer- cises to more demanding studies or miniprojects, are supplied for each chapter. These problems form an integral part of the book: they were not added as afterthoughts to make the book more attractive for use as a text. A total of 464 problems are included (15–18 per chapter). Assuming that two lectures are given per week, either weekly or biweekly homework can be assigned, with each assignment having the specific coverage of the respective half-part (two chapters) or full-part (four chapters) as its “title.” An instructor’s solutions manual is available. The author’s detailed syllabus for the course ECE 252B at UCSB is available at: http://www.ece.ucsb.edu/∼parhami/ece_252b.htm.
    Preface xxiii A simulator for numerical experimentation with various arithmetic algorithms is available at: http://www.ecs.umass.edu/ece/koren/arith/simulator/ courtesy of Professor Israel Koren. References to classical papers in computer arithmetic, key design ideas, and impor- tant state-of-the-art research contributions are listed at the end of each chapter. These references provide good starting points for in-depth studies or for term papers or projects. A large number of classical papers and important contributions in computer arithmetic have been reprinted in two volumes [Swar90]. New ideas in the field of computer arithmetic appear in papers presented at biannual conferences, known as ARITH-n, held in odd-numbered years [Arit]. Other conferences of interest include Asilomar Conference on Signals, Systems, and Computers [Asil], International Conference on Circuits and Systems [ICCS], Midwest Symposium on Cir- cuits and Systems [MSCS], and International Conference on Computer Design [ICCD]. Relevant journals include IEEE Transactions on Computers [TrCo], particularly its spe- cial issues on computer arithmetic, IEEE Transactions on Circuits and Systems [TrCS], Computers & Mathematics with Applications [CoMa], IET Circuits, Devices & Sys- tems [CDS], IET Computers & Digital Techniques [CDT], IEEE Transactions on VLSI Systems [TrVL], and Journal of VLSI Signal Processing [JVSP]. ACKNOWLEDGMENTS Computer Arithmetic: Algorithms and Hardware Designs is an outgrowth of lecture notes the author used for the graduate course “ECE 252B: Computer Arithmetic” at the University of California, Santa Barbara, and, in rudimentary forms, at several other institutions prior to 1988. The text has benefited greatly from keen observations, curios- ity, and encouragement of my many students in these courses. A sincere thanks to all of them! REFERENCES AND FURTHER READINGS Note: References appear in updated 2nd-edition form, in order to avoid the need for a separate list for the latter. [Arit] International Symposium on Computer Arithmetic, sponsored by the IEEE Computer Society. This series began with a one-day workshop in 1969 and was subsequently held in 1972, 1975, 1978, and in odd-numbered years since 1981. The 19th symposium in the series, ARITH-19, was held June 8–10, 2009, in Portland, Oregon. Asilomar Conference on Signals Systems, and Computers, sponsored annually by IEEE and held on the Asilomar Conference Grounds in Pacific Grove, California, each fall. The 43rd conference in this series was held on November 1–4, 2009. [Cava84] Cavanagh, J. J. F., Digital Computer Arithmetic: Design and Implementation, [Asil] [CDS] McGraw-Hill, 1984. IET Circuits, Devices & Systems, journal published by the Institution of Engineering and Technology, United Kingdom.
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料