硬件与软件设计的算术优化技巧指南

需积分: 9 113 浏览量更新于2024-07-17 收藏 2.1MB PDF 举报

《算术优化技术在硬件与软件设计中的应用》是一本针对嵌入式平台上的数字信号处理算法设计的专业书籍。该书旨在帮助读者提升系统性能、降低能耗，并避免手动编写的复杂算术函数，通过自动优化技术实现高效的设计。书中深入探讨了高级编译器优化和高速架构在实施有限 impulse response (FIR) 过滤器的应用，这些技术在通信、信号处理、计算机图形学和密码学等领域都能显著提高性能。作者Ryan Kastner是加州大学圣地亚哥分校计算机科学与工程系的副教授，他为读者提供了清晰易懂的算法和实例，使学习者能够轻松理解和应用这些技术。书中还涵盖了算术表达式合成和计算机算术的基础知识，使得对于该主题的新手也能顺利入门。这本书尤其适合研究者、专业人士以及在系统级设计、自动化、编译器和非常大规模集成电路（VLSI）CAD等领域工作的研究生。本书的核心内容包括但不限于以下几点： 1. **自动算术优化技术**：介绍如何通过自动化工具和技术来优化硬件和软件中的算术运算，提升执行效率。 2. **FIR滤波器实现**：详细讲解如何利用高效率的编译器优化策略和架构设计，以优化FIR滤波器的硬件实现，这对于信号处理系统的性能至关重要。 3. **跨领域应用**：涉及通信、图像处理、图形渲染和安全领域的算术操作优化，展示实际应用的广泛性。 4. **基础理论**：提供算术表达式合成和计算机算术基础知识，为理解优化算法提供坚实的数学和理论基础。 5. **实践指导**：通过丰富的算法步骤和案例分析，帮助读者掌握算术优化的实际操作和软件开发过程。 6. **适用人群**：无论你是初学者还是经验丰富的从业者，都可以从这本书中获得有价值的信息，提升在系统设计和自动化领域的专业能力。《算术优化技术在硬件与软件设计中的应用》是一本实用且全面的参考书籍，不仅适用于学术研究，也是工程师日常工作中不可或缺的工具。通过阅读这本书，读者将能深入了解如何在嵌入式环境中高效利用算术优化技术，推动项目的成功实施。

to fixed point representation. Though floating point representation provides

greater dynamic range and precision than fixed point, it is far more expensive to

compute. Most embedded system applications tolerate a certain degree of inaccur-

acy and use the much simpler fixed point notation to increase throughput and

decrease area, delay, and energy. The conversion of floating point to fixed point

produces some errors [1]. These errors should be carefully analyzed to see if they

reside within tolerable limits [2, 3].

At this point, the application is roughly divided between hardware and soft-

ware. The designer, perhaps with the help of automated tools, determ ines the

parts of the system specification that should be mapped onto hardware compon-

ents and the parts that should be mapped to software. For real-time applications

with tight timing constraints, the computation intensive kernels are often imple-

mented in hardware, while the parts of the specification with looser timing

constraints are implemented in software. After this decision, the architecture of

the system and the memory hierarchy are decided. The custom hardware por-

tions of the system are then designed by means of a behavioral description of the

algorithm using a hardw are description language (HDL). Hardware synthes is

tools transform these hardware descriptions into a register transfer level (RTL)

language description by means of powerful hardware synthesis tools. These

synthesis tools mainly perform scheduling, resource allocation, and binding of

the various operations obtained from an intermediate representation of the

System

specification

Logic

synthesis

Architectural

synthesis

Physical

synthesis

description

Hardware design flow

Algorithmic

optimization

Error

analysis

Fixed to floating

point conversion

Hardware/Software

partitioning

Computational analysis

Compiler backend:

analysis,

optimization,

code generation

Compiler frontend:

lexical analysis,

syntactic analysis,

semantic checking

Embedded system

Software design flow

Figure 1.1 Embedded system design flow.

4 Introduction

behavior represented in the HDL [4]. In addition the tools perform optimizations

such as redundancy elimination (common subexpression elimination (CSE) and

value numbering) and critical path minimiza tion. The constant multiplications in

the linear systems and polynomials can be decomposed into shifts and additions

and the resulting complexity can be further reduced by eliminating common

subexpressions [5–8]. Furthermore, there are some numeric transformations of

the constant coefficients that can be applied to linear transforms to reduce the

strength of the operations [9, 10]. This book provides an in-depth discussion of

such transforms. The order and priorities of the various optimizations and

transformations are largely ap plication dependent and are the subject of current

research. In most cases, this is done by evaluating a number of transformations

and selecting the one that best meet s the constraints [11]. The RTL description is

then synthesized into a gate level netlist, which is subsequently placed and routed

using standard physical design tools.

For the software portion of the design, custom instructions tuned to the

particular application may be added [12–14]. Certain computation intensive

kernels of the application may require platform dependent software in order to

achieve the best performance on the available architecture. This is often done

manually by selecting the relevant functions from optimized software libraries.

For some domains, including signal processing applications, automatic library

generators are available [11]. The software is then compiled using various trans-

formations and optimization techniques [15]. Unfortunately, these compiler

optimizations perform limited transformations for reducing the complexity of

polynomial expressions and linear systems. For some applications, the gen erated

assembly code is optimized (mostly manually) to improve performance, though it

is not practical for large and complex programs. An assembler and a linker are

then used to generate the executable co de.

Opportunities for optimizing polynomial expressions and linear systems exist

for both the hardware and the software implementations. These optimizations

have the potential for huge impact on the performance and power consumption

of the embedded systems. This book presents techniques and algorithms for

performing such optimizations during both the hardware design flow and the

software compilation.

1.2 Salient features of this book

The unique feature of this book is its treatment of the hardware synthesis and

software compilation of arithmetic expressions. It is the first book to discuss

automated optimization techniques for arithmetic expressions. The previous

literature on this topic, e.g., [16] and [17], deals only with the details of implement-

ing arithmetic intensive functions, but stops short of discussing techniques to

optimize them for different target architectures. The book gives a detailed intro-

duction to the kind of arithmetic expressions that occur in real-life applications,

51.2 Salient features of this book

such as signal processing and computer graphics. It shows the reader the import-

ance of optimizing arithmetic express ions to meet performance and resource

constraints and improve the quality of silicon. The book describes in detail the

different techniques for performing hardware and software optimizations. It also

describes how these techniques can be tuned to improve different parameters such

as the performance, power consumption, and area of the synthesized hardware.

Though most of the algorithms described in it are heuristics, the book also shows

how optimal solutions to these problems can be modeled using integer linear

programming (ILP). The usefulness of these techniques is then verified by applying

them on real benchmarks.

In short, this book gives a comprehensive overview of an important problem

in the design and optimization of arithmetic intensive embedded systems.

It describes in detail the state of the art techniques that have been developed to

solve this problem. This book does not go into detai l about the mathematics

behind the arithmetic expressions. It assumes that system designers hav e per-

formed an analysis of the system and have come up with a set of polynomial

equations that describe the functionality of the system, within an acceptable error.

Furthermore, it assumes that the system designer has decided what is the best

architecture (software, ASIC or FPGA or a combination of them) to implement

the arithmetic function. The book does not talk about techniques to verify the

precision of the optimized arithmetic expressions. Techniques such as those dis-

cussed in [2] and [18] can be used to verify if the expressions produce errors within

acceptable limits.

1.3 Organization



Chapter 2 illustrates the different applications that require arithmetic computa-

tion. It shows how polynomial expressions and linear computations reside in a

number of applications that drive embedded systems and high-performance

computing market s. The chapter discusses how polynomials are employed in

computer graphics applications and describes the use of linear systems in DSP,

cryptography, and address calculation.



Chapter 3 presents an overview of the software compilation process an d shows

opportunities to optimize linear systems and polynomial expressions.



Chapter 4 provides a high-level description of the hardware synthes is design

flow. It explains the major steps in this design flow including input specification,

algorithm optimization, scheduling, binding, and resource allocation. The chapter

illustrates these concepts with a case study of an FIR filter.



Chapter 5 gives a brief introduction to the concepts in digital arithmetic.

It explains number representations including fixed and floating point represen-

tations. Also, it presents different architectures to perform two-operand and

multiple-operand additio n. These concepts are impor tant in order to gain an

understanding of the optimizations described in Chapters 6 and 7.

6 Introduction



Chapter 6 presents algebraic optimization techniques for polynomial expres-

sions. It describes representations of polyn omial expressions as well as various

algorithms to optimize polynomials for both hardware and software implemen-

tation. The chapter concludes with experimental results showing the relative

benefits of the various optimization techniques.



Chapter 7 describes algebraic techniques for the optimization of linear arithmetic

computations such as FIR filters and other linear transforms. Algorithms to

optimize multiple-operand addition are also presented. Finally, the chapter pre-

sents experimental results where the usefulness of these techniques is demonstrated

using real-life examples.

1.4 Target audience

When writing this book we had several audiences in mind. Much of the material

is targeted towards specialists, whether they be researchers in academia or

industry, who are designing both software and hardware for polynomial expres-

sions and/or linear systems. The book also provides substantial background of

the state of the art algorithms for the implementation of these systems, and

serves as a reference for researchers in these areas. This book is designed to

accommodate readers with different backgrounds, and the book includes some

basic introductory material on several topics including computer arithmetic,

software compilation, and hardware synthesis. These introductory chapters give

just enough background to demonstrate basic ideas and provide references to

gain more in-depth information . Most of the book can be understood by anyone

with a basic grounding in computer engineering. The book is suitab le for

graduate students, either as a reference or as textbook for a specialized class

on the topics of hardware synthesis and software compilation for linear syst ems

and polynomial express ions. It is also suitable for an advanced topics class for

undergraduate students.

References

[1] C. Shi and R.W. Brodersen, An automated floating-point to fixed-point conversion

methodology, IEEE International Conference on Acoustics, Speech, and Signal Processing,

2003. Washington, DC: IEEE Computer Society, 2003.

[2] C.F. Fang, R.A. Rutenbar, and T. Chen, Fast, accurate static analysis for fixed-

point finite-precision effects in DSP designs, International Conference on Computer Aided

Design (ICCAD), San Jose, 2003. Washington, DC: IEEE Computer Society, 2003.

[3] D. Menard and O. Sentieys, Automatic evaluation of the accuracy of fixed-point

algorithms, Design, Automation and Test in Europe Conference and Exhibition, 2002.

Washington, DC: IEEE Computer Society, 2002.

71.4 Target audience

[4] G.D. Micheli, Synthesis and optimization of digital circuits, New York, NY:

McGraw-Hill, 1994.

[5] M. Potkonjak, M.B. Srivastava, and A.P. Chandrakasan, Multiple constant

multiplications: efficient and versatile framework and algorithms for exploring

common subexpression elimination, IEEE Transactions on Computer Aided Design

of Integrated Circuits and Systems, 15(2), 151–65, 1996.

[6] R. Pasko, P. Schaumont, V. Derudder, V. Vernalde, and D. Durackova, A new

algorithm for elimination of common subexpressions, IEEE Transactions on Computer

Aided Design of Integrated Circuits and Systems, 18(1), 58–68, 1999.

[7] R. Pasko, P. Schaumont, V. Derudder, and D. Durackova, Optimization method for

broadband modem FIR filter design using common subexpression elimination,

International Symposium on System Synthesis, 1997. Washington, DC: IEEE Computer

Society, 1997.

[8] A. Hosangadi, F. Fallah, and R. Kastner, Common subexpression elimination

involving multiple variables for linear DSP synthesis, IEEE International Conference on

Application-Specific Architectures and Processors, 2004. Washington, DC: IEEE

Computer Society, 2004.

[9] A. Chatterjee, R.K. Roy, and M.A. D’Abreu, Greedy hardware optimization

for linear digital circuits using number splitting and refactorization, IEEE Transactions

on Very Large Scale Integration (VLSI) Systems , 1(4), 423–31, 1993.

[10] H.T. Nguyen and A. Chatterjee, Number-splitting with shift-and-add decomposition

for power and hardware optimization in linear DSP synthesis, IEEE Transactions on

Very Large Scale Integration (VLSI) Systems, 8, 419–24, 2000.

[11] M. Puschel, B. Singer, J. Xiong, et al., SPIRAL: a generator for platform-adapted

libraries of signal processing algorithms, Journal of High Performance Computing and

Applications, 18, 21–45, 2004.

[12] R. Kastner, S. Ogrenci-Memik, E. Bozorgzadeh, and M. Sarrafzadeh, Instruction

generation for hybrid reconfigurable systems, International Conference on Computer

Aided Design. New York, NY: ACM, 2001.

[13] A. Peymandoust, L. Pozzi, P. Ienne, and G. De Micheli, Automatic instruction set

extension and utilization for embedded processors, IEEE International Conference on

Application-Specific Systems, Architectures, and Processors, 2003. Washington, DC:

IEEE Computer Society, 2003.

[14] Tensilica Inc., http://www.tensilica.com.

[15] S.S. Muchnick, Advanced Compiler Design and Implementation, San Francisco, CA:

Morgan Kaufmann Publishers, 1997.

[16] J.P. Deschamps, G.J.A. Bioul, and G.D. Sutter, Synthesis of Arithmetic Circuits:

FPGA, ASIC and Embedded Systems, New York, NY: Wiley-Interscience (2006).

[17] U. Meyer-Baese, Digital Signal Processing with Field Programmable Gate Arrays,

third edition. Springer, 2007.

[18] C. Fang Fang, R.A. Rutenbar, M. Puschel, and T. Chen, Toward efficient static

analysis of Finite-Precision effects in DSP applications via affine arithmetic modeling,

Design Automation Conference. New York, NY: ACM, 2003.

8 Introduction

剩余198页未读，继续阅读

cfy_ardai

粉丝: 0
资源: 2

硬件与软件设计的算术优化技巧指南

算术优化算法(Arithmetic Optimization Algorithm)源代码解读

"基于AT89C51单片机的简易计算器设计及实现

"第二版计算机算术：经典算法与硬件设计

Computer Arithmetic:Algorithm and Hardware Design

A Proposal for Hardware Assisted Arithmetic Overflow Detection for Array and Bitfield Operations (LazyOverflowDetect_Final)-计算机科学

Arithmetic Optimization Algorithm (AOA) Java 代码：Arithmetic Optimization Algorithm 是一种新的元启发式求解优化问题的方法-matlab开发

computer arithmetic - algorithms and hardware designs

Computer Arithmetic - Algorithms and Hardware Designs - Parhami

算术优化算法(Arithmetic Optimization Algorithm, AOA)源代码

Arithmetic coding anddecode for Text Compression:Arithmetic coding anddecode for Text Compression-matlab开发

最新资源