1、Block Floating Point Interval ALU for Digital Signal Processing,Sandeep Hattangady, William Edmonson, Winser Alexander,September 30, 2008,HiPer DSP Lab, North Carolina State University,Outline,IntroductionBackgroundArchitectureResultsConclusions and Future WorkReferences,Outline,IntroductionBackgrou
2、ndArchitectureResultsConclusion s and Future WorkReferences,Problem Statement,To provide reliable arithmetic for embedded systems. Low power Small footprint Real-time computing Applications Digital signal processing & Control Fuzzy systems Adaptive filtering Decision systems,Introduction,Problem Sta
3、tement,Introduction,Twos complement formatQ7.8 input dataQ15.0 output data,Upper Bound,Lower Bound,Upper Bound,Lower Bound,Overflow leads to unreliable interval arithmetic!,Overflow in an interval Summation,Build a fixed point interval ALU whose arithmetic stays reliable even in the presence of over
4、flow.,Fixed point implementations face overflow due to small dynamic range,Problem Solution,Use Block Floating Point (BFP) arithmetic to achieve higher dynamic range over that of conventional fixed point architecturesHandle overflows using Conditional Block Floating-point Scaling (CBFS) scheme,Intro
5、duction,Outline,IntroductionBackgroundArchitectureResultsConclusions and Future WorkReferences,Previous Work,Dedicated fixed point interval ALU Ruchir2006The only fixed point interval ALU implementation.No scheme in place to handle overflow.Block Floating Point arithmetic Digital filters Oppenheim19
6、70 Fast Fourier Transform (FFT) processors Bidet1995 Fast Hartley Transform (FHT) processors Erickson1992 Commercial Fixed point DSPs with BFP support,Previous Work,* ADSP-21xx * TMS320C54x * Oak DSP Core * TMS320C64x * Lucent DSP16xx * NEC uPD7701x * SGS Thomson D950-Core,Criteria for Reliable IA,C
7、orrectness : Van Emden2001An interval operation is correct when the output interval contains results of all point-wise evaluations based on values from the argument intervals. For ex: 1,2 + 3,4 = 4,6 Totality : A total interval operation is one that is defined for all possible input arguments. For e
8、x : We provide only division by powers of 2 eliminating divide-by-0 error. Closedness : A closed interval operation indicates that the output interval is obtained on the same space as that of the input intervals. For example, interval operations on intervals defined on the real space R always yields
9、 an output interval on the space R. Optimality : An optimal interval operation does not perform any overestimation and its bounds are the most optimized ones for the type of representation chosen. Efficiency : The term efficiency is defined with respect to the implementation of interval arithmetic i
10、n hardware.,Background,Thought Process,Fixed point implementations Lower design complexity Small dynamic range,Floating Point implementationsHigher design complexity Large dynamic range,Block Floating Point representation,Associate a group of fixed point values with a common exponent term,Background
11、,Block Floating Point Arithmetic,BFP implementations on DSPs rely on memory for data storage. Divide data into blocks.Scale data to common exponent pre-operation. Perform fixed point operations to process that block.,BLOCK NORMALIZATION,Background,Upper Endpoint envelope,Lower Endpoint envelope,Math
12、ematical Formulation of Block Floating Point for Intervals,0.0000100, 0.00110001.1110011, 0.0000001,Data Samples,Normalized Data,0.0010000, 0.11000001.1001100, 0.0000100,M = 0.0011000 0.1875= -2,Exponent detection Finding,Normalization Shifting all data left by,New block exponent (Old block exponent
13、 + ), can also be evaluated as negated minimum count of leading number of sign bits in binary,Block Exponent,0.03125 , 0. 1875-0.1015625, 0.0078125,0.125 , 0. 75-0.40625, 0.03125,Comments,Handling Fixed Point Overflows,Conditional Block Floating-point Scaling (CBFS) Overflow mainly associated with A
14、ddition operation CBFS based on correcting errorsProcedure: Perform operation Check if overflow occurred If it did, scale down the result by a factor of 2Increment output block exponent If it didnt overflow, retain resultOutput block exponent is same as input block exponent,Design Specifications,Rou
15、nding,Outward Rounding Output interval must meet correctness Retain the rounding scheme from IALU Ruchir2006 Truncate lower endpoint by discarding higher precision bits Add the OR-ed result of the discarded bits to round the result to +.Rounding to + can cause overflow.Example of Rounding 32-bit to
16、+ to yield 16-bit: 7FFF XXXX (hex) where XXXX is not 0000 (hex) Rounding to +yields 7FFF + 1 = 8000 (hex)Correct by sending out 4000 (hex), increment output block exponent. Referred to as Special case of Rounding.,Design Specifications,Outline,IntroductionBackgroundArchitectureResultsConclusions and
17、 Future WorkReferences,Top Level Hardware Architecture,Hardware Architecture,Slide 17/35,Flag Generator,1. Identify case of Multiplication using flag-combinations,2. Distributing Commands toLower and Upper Bound modules,3. Generating Disjoint Signal,Compare (XL with YU) ; (XU with YL)Set disjoint hi
18、gh if (YUXL) or (XUYL),Hardware Architecture,Slide 18/35,Lower Bound Module,Hardware Architecture,Generates the Lower endpoint of the output intervalMultiplexed data pathsSets OVFL_L, a one bit signal, high to indicate overflow to the Scale Synchronizer,Slide 19/35,Upper Bound Module,Generates the U
19、pper endpoint of the output interval.Same structure as Lower Bound module.Generates 1-bit signal OVFL_U to indicate overflow in the Upper Bound to the Scale Synchronizer module.,Hardware Architecture,Slide 20/35,BFP Operations,EXPONENT DETECTION,Identify the redundant sign bits by XOR of successive
20、data bits.Obtain the count of the redundant bits using a priority encoder.,LEFT SHIFTING,The integer output from the Priority Encoder is the value of Single cycle Normalize : Select normalized value from shifted versions of the input using as the select line,Hardware Architecture,Slide 21/35,Main fu
21、nctionsRounding 32-bit outputs of Lower and Upper Bound modules appropriately to 16-bitsSynchronizing the output endpoints and updating the increment in output block exponents appropriately (updt_L, updt_U)Storing the minimum exponent detected during Exponent Detection for a block,Hardware Architect
22、ure,Scale Synchronizer,Slide 22/35,Scale Synchronizer,Hardware Architecture,Interval operations Outward Rounding Synchronization Overflow flags from the Lower and Upper Bound modules Special case rounding for Upper Bound result Updating Block exponent increment (updt_L and updt_U) Whether overflow o
23、ccurred or not in either output endpointWhether special case rounding occurred or not Whether the operations are iterative or notPoint-wise operations Rounding scheme could be Truncation or Rounding to + No synchronization needed Updating Block Exponent increment Whether overflow occurred or not Whe
24、ther special case rounding occurred or not Whether the operations are iterative or not,Slide 23/35,Scaling Modules,Hardware Architecture,For each overflow, the output block exponent is incremented (updt_L, updt_U)For iterative operations, the input that point forward should be scaled down by this fa
25、ctor.Selection logic is used with the select signal being updt_L and updt_U for the Scale_L and Scale_U modules respectively.,Outline,IntroductionBackgroundArchitectureResultsConclusions and Future WorkReferences,Module Execution Rates,Design Clock Frequency = 96.8MHzPower Dissipation measured using
26、 Synopsys Prime Power 0.04918W for 1000 input vectors,0.18um CMOSX Library,Results,Evaluating Hardware Performance,Throughput (R) = Number of output samples processed per secondFor interval block of size N, (N) cycles needed each for Exponent Detection and Left-shifting to Normalize3 cycle penalty p
27、er overflow associated with flushing the MAC feedback path, reloading the new block exponent and resuming operations.Let t =design Timing; p =number of overflowsProbability of nth overflow Probability of (n-1)th overflow. In the limiting case of , R = 32.2M samples/second,Results,Future Work,Pipelin
28、e the ArchitectureAdding Saturation for point-wise evaluationsExploring the BFPIALU as a coprocessorDeveloping a Superscalar or VLIW-based interval processor around the ALU,Conclusions and Future Work,Conclusion,Developed a competitive hardware solution for reliable interval arithmetic on fixed poin
29、t architecturesIntroduced BFP arithmetic for intervals with CBFS for overflow handlingEnhanced the utility of the architecture by expanding the command set. incorporating the ability to perform point-wise arithmetic.,Conclusions and Future Work,Outline,IntroductionBackgroundArchitectureResultsConclu
30、sions and Future WorkReferences,Ruchir2006 R. Gupte, W. Edmonson, Gianchandani, J, S. Ocloo, and W. Alexander, “Pipelined ALU for signal processing to implement interval arithmetic,“ Signal Processing Systems Design and Implementation IEEE, pp. 95-100, 2006. Amaricai2007 Alexandru Amaricai, Mircea V
31、ladutiu, Lucian Prodan, Mihai Udrescu, Boncalo, Oana,” Design of Addition and Multiplication Units for High Performance Interval Arithmetic Processor”, Design and Diagnostics of Electronic Circuits and Systems, 2007. DDECS 07. IEEE, April 2007 Schultz2000 M. J. Schultz and E. E. Swartzlander, “A fam
32、ily of variable-precision interval arithmetic processors,“ IEEE Transactions on Computers, vol. 49, May 2000. Stine1998 J. E. Stine and M. J. Schulte, “A combined interval and floating-point multiplier,“ 8th Great Lakes Symposium on VLSI, pp. 208-213, Feb 1998. Stine1998a J. E. Stine and M. J. Schul
33、te, “A combined interval and floating-point divider,“ IEEE Conference Record on Signals, Systems and Computers, 1998 Akkas2002 A. Akkas, “A combined interval and Floating-point comparator/selector,“ Application-Specific Systems, Architectures and Processors, pp. 208-217, July 2002. Oppenheim1970 A.
34、Oppenheim, Realization of digital filters using block-floating-point arithmetic,“ IEEE Transactions on Audio and Electroaccoustics, vol. 18, pp. 130-136, Jun 1970. Erickson1992 A. C. Erickson and B. S. Fagin, Calculating the FHT in hardware,“ IEEE Transactions on Signal Processing, vol. 40, June 199
35、2.,References,Bidet1995 Bidet E., Castelain D., Joanblanq C. and Senn, P.,”A fast single-chip implementation of 8192 complex point FFT”, IEEE Journal of Solid-State Circuits, vol. 30, No.3, pp. 300-305, Mar 1995 Van Emden2001 M. Van Emden, T. Hickey, and Q. Ju, “Interval arithmetic: From principles
36、to implementation,“ Massachusetts Journal of the ACM, vol. 48, pp. 1038-1068, September 2001. Liang2000 Q. Liang and J. M. Mendel, “Overcoming time-varying co-channel interference using Type-2 fuzzy adaptive filters,“ IEEE Transactions on Circuits and Systems - II, vol. 47, Dec 2000. Chhabra1999 Chh
37、abra and R. Iyer, “A block floating point implementation on the TMS320C54x DSP,“ Tech. Rep., Texas Instruments, December 1999. Application report SPRA610. Kalliojarvi1996 K. Kalliojarvi and J. Astola, Roundoff errors in block-floating-point systems,“ IEEE Transactions on Acoustics, Speech, and Signa
38、l Processing, vol. 44, pp. 783-790, April 1996. Deschamps2006 J.-P. Deschamps, G. J. A. Bioul, and G. D. Sutter, Synthesis of Arithmetic Circuits. John Wiley & Sons, 2006. Cragon1996 H. G. Cragon, Memory Systems and Pipelined Processors. Sudbury, Massachusetts: Jones and Barlett Publishers, 1996. Hansen2004 E. Hansen and G. W. Walster, “Global optimization using interval analysis”, Marcel Dekker, Inc. and Sun Microsystems, Inc., 2004. intervalhomepage http:/www.cs.utep.edu/interval-comp/intsoft.html.,References,Slide 32/35,Thank You !,
