Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd

5星(超过95%的资源)
所需积分/C币:50 2016-06-08 11:55:15 8.14MB PDF
159
收藏 收藏
举报

Ideal for graduate and senior undergraduate courses in computer arithmetic and advanced digital design, Computer Arithmetic: Algorithms and Hardware Designs, Second Edition, provides a balanced, comprehensive treatment of computer arithmetic. It covers topics in arithmetic unit design and circuit implementation that complement the architectural and algorithmic speedup techniques used in high-performance computer architecture and parallel processing. Using a unified and consistent framework, the text begins with number representation and proceeds through basic arithmetic operations, floating-point arithmetic, and function evaluation methods. Later chapters cover broad design and implementation topics-including techniques for high-throughput, low-power, fault-tolerant, and reconfigurable arithmetic. An appendix provides a historical view of the field and speculates on its future. An indispensable resource for instruction, professional development, and research, Computer Arithmetic: Algorithms and Hardware Designs, Second Edition, combines broad coverage of the underlying theories of computer arithmetic with numerous examples of practical designs, worked-out examples, and a large collection of meaningful problems. This second edition includes a new chapter on reconfigurable arithmetic, in order to address the fact that arithmetic functions are increasingly being implemented on field-programmable gate arrays (FPGAs) and FPGA-like configurable devices. Updated and thoroughly revised, the book offers new and expanded coverage of saturating adders and multipliers, truncated multipliers, fused multiply-add units, overlapped quotient digit selection, bipartite and multipartite tables, reversible logic, dot notation, modular arithmetic, Montgomery modular reduction, division by constants, IEEE floating-point standard formats, and interval arithmetic. Features: * Divided into 28 lecture-size chapters * Emphasizes both the underlying theories of computer arithmetic and actua
Copyrighted Materials Copyright@2010OxfordUniversityPressRetrievedfromwww.knovel.com 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 Copyrighted Materials Copyright@2010OxfordUniversityPressRetrievedfromwww.knovel.com 3 PREFACE to the first edition THE CONTEXT OF COMPUTER ARITHMETIC A dvances 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 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 Preface b e the dominant consumers of chip area in todays 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 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) 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 VIl( 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 gorithms, 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 HOWTO USE THE BOOK For classroom use, the topics in each chapter of this text can be covered in a lecture lastin 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 An instructors 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/ece252b.htm Preface XX A simulator for numerical experimentation with various arithmetic algorithms 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 [Swar901 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 Cil cuits and Systems [MSCSl, 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 [Trvll, and Journal of vlsi signal processing [jvsPi 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 subsequentl 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 4rd conference in this series was held on november 1-4. 2009 [Cava84] Cavanagh, J.J. F, Digital Computer Arithmetic: Design and implementation McGraw-Hill. 1984 [CDS] IET Circuits, Devices Systems, journal published by the Institution of Engineerin and Technology, United Kingdom XXIV [CDT] IET Computers Digital Techniques, journal published by the Institution of Engineering and Technology, United Kingdom CoMa] Computers Mathematics with Applications, journal published by Pergamon Press [ Desc06 Deschamps, J.-P, G.J. A. Bioul, and G. D. Sutter, Synthesis of arithmetic Circuits FPGA, ASIC and Embedded systems, Wiley-Interscience, 2006 [Erce04 Ercegovac, M. D, and T Lang, Digital Arithmetic, Morgan Kaufmann, 2004 Flor63] Flores, I, The Logic of Computer Arithmetic, Prentice-Hall, 1963 [Gosl80 Gosling, J B, Design of Arithmetic Units for Digital Computers, Macmillan, 1980 [Hwan79] Hwang, K, Computer Arithmetic: Principles, Architecture, and Design, Wiley 1979. ICCD] International Conference on Computer Design, sponsored annually by the ieee Computer Society. ICCD-2009 was held on October 4-7, in Lake Tahoe, California [CCS] International Conference on Circuits and Systems, sponsored annually by the ieee Circuits and Systems society The latest in this series was held on May 24-27, 2009 in Taipei, Taiwan [VSPI J. VLSI Signal Processing, published by Kluwer Academic Publishers [Knut97 Knuth, D. E, The Art of Computer Programming, Vol 2: Seminumerical algorithms, 3rd ed, Addison-Wesley, 1997. (The widely used second edition, published in 1981 is cited in Parts V and vI) [Kore02] Koren, I, Computer Arithmetic AlgorithmS, 2nd ed, A K Peters, 2002 [Kuli&1 Kulisch, U.W., and w. L Miranker, Computer Arithmetic in Theory and Practice, Academic Press. 1981 Lu04 Lu, M, Arithmetic and Logic in Computer Systems, Wiley, 2004 [MSCS] Midwest Symposium on Circuits and Systems, sponsored annually by the ieee Circuits and systems societ [Omon94] Omondi, A.R., Computer Arithmetic SystemS: AlgorithmS, Architecture and Implementations, Prentice-Hall, 1994 [Rich55] Richards, R. K, Arithmetic Operations in Digital Computers, Van Nostrand, 1955 [Scot85] Scott, N.R., Computer Number Systems and Arithmetic, Prentice-Hall, 1985 IStei71 Stein, M. L, and W. D Munro, Introduction to Machine arithmetic, Addison-Wesley, 1971 [Stin04 Stine, J.E., Digital Computer Arithmetic Datapath Design Using Verilog hdl Kluwer. 2004 [Swar90] Swartzlander, E.E., Jr, Computer Arithmetic, Vols. I and Il, IEEE Computer Society Press. 1990 [TrCo] IEEE Trans. Computers, journal published by the IEEE Computer Society Occasionally entire special issues or sections are devoted to computer arithmetic (e. g, Vol. 19, No 8, August 1970; Vol. 22, No. 6, June 1973; Vol. 26, No. 7, July 1977; Vol 32, No 4, April 1983; Vol. 39, No 8, August 1990; Vol. 41, No. 8, August 1992, Vol 43, No 8, August 1994; Vol 47, No. 7, July 1998; Vol 49, No. 7, July 2000; VoL 54, No 3, March 2005; Vol 58, No. 2, February 2009) ITrCs IEEE Trans. Circuits and Systems, Parts /&ll, journals published by Ieee. The two parts have been distinguished differently over the years. Currently, Part I publishes regular papers, while Part II is devoted to"express briefs Preface XXV [TrVL] IEEE Trans. Very Large scale Integration(VLSn) Systems, journal published jointly by the ieee Circuits and systems Society, Computer Society, and Solid-State Circuits council [Wase82] Waser,S, and M.J. Flynn, Introduction to Arithmetic for Digital Systems Designers, Holt. Rinehart winston. 1982 TWino80 Winograd, S, Arithmetic Complexity of Computations, SIAM, 1980

...展开详情
试读 127P Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
hubeigaokao 最近正在学习,很好的资料
2017-12-26
回复
weixin_38578580 很好,文字版
2017-10-27
回复
YT_SEU 不是影印版本 但是目录全是乱码
2017-05-16
回复
MinnieCCMM 第二版和第一版稍有不同,很清晰的版本,终于找到了~
2017-04-22
回复
jiayou0909 很好,文字清晰。
2017-01-04
回复
rustnail 好书,感谢分享!
2017-01-03
回复
fighter001 很好的一本书,对理解计算机编码和运算很有帮助
2016-10-15
回复
eggcar 质量很高,但是目录标签全是乱码。。。
2016-10-14
回复
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

关注 私信
上传资源赚钱or赚积分
最新推荐
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd 50积分/C币 立即下载
1/127
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第1页
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第2页
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第3页
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第4页
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第5页
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第6页
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第7页
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第8页
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第9页
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第10页
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第11页
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第12页
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第13页
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第14页
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第15页
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第16页
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第17页
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第18页
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第19页
Computer.Arithmetic.Algorithms.and.Hardware.Designs.2nd第20页

试读结束, 可继续阅读

50积分/C币 立即下载 >