Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2006-01-12
2010-12-14
Ngo, Chuong D (Department: 2193)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
07853637
ABSTRACT:
Aggressive pipelining allows Field Programmable Gate Arrays (FPGAs) to achieve high throughput on many Digital Signal Processing applications. However, cyclic data dependencies in the computation can limit pipelining and reduce the efficiency and speed of an FPGA implementation. Saturated accumulation is an important example where such a cycle limits the throughput of signal processing applications. A reformulation of saturated addition as an associative operation permits a parallel-prefix calculation to be used to perform saturated accumulation at any data rate supported by the device. The method may be extended to other operations containing loops with one or more loop-carried dependencies.
REFERENCES:
patent: 6330660 (2001-12-01), Ganapathy et al.
patent: 6842845 (2005-01-01), Ganapathy et al.
Balzola, P.I., et al., “Design Alternatives for Parallel Saturating Multioperand Adders,”Proceedings of the International Conference on Computer Design, pp. 172-177 (Sep. 2001).
Lee, C., et al., “MediaBench: A Tool for Evaluating and Synthesizing Multimedia and Communications Systems,”International Symposium on Microarchitecture, pp. 330-335 (1997).
Papadantonakis, K., et al., “Pipelining Saturated Accumulation,” IEEEInternational Conference on Field Programmable Technology(Dec. 11-14, 2005).
Barua, et al., “Maps: A compiler-managed memory system for raw machines”, Saman Amarasinghe, Anant Agarwal, cag-www.lc.mit.edu/raw, 1998.
Brent, et al., “A regular layout for parallel adders”, IEEE Transaction on Computers, vol. C-31, 1982.
DeHon, et al., “Design Patterns for Reconfigurable Computing”, IEEE Symposium on Field-Programmable Custom Computing Machines, 2004.
DeHon, et al., “The density advantage of configurable computing”, IEEE Configurable Computing, 2000.
Hillis, et al., “Data parallel algorithms”, Communications of the ACM, vol. 29, No. 12, 1986.
Luo, et al., “Accelerating pipelined integer and floating-point accumulations in configurable hardware with delayed addition techniques”, IEE Transactions on Computers, vol. 49, No. 3, 2000.
Singh, et al., “The case for registered routing switches in field programmable gate arrays”, ACM, 2001.
Tsu, et al., “HSRA: High-Speed, Hierarchical Synchronous Reconfigurable Array” ,ACM, 1999.
Von Herzen, “Signal processing at 250 MHz using high-performance FPGA's”, ACM, 1997.
Weaver, et al., Post-placement C-slow retiming for the xilinx virtex, FPGA, 2003.
Weaver, et al., “The SFRA: A corner-Turn FPGA Architechture”, FPGA, 2004.
Winograd, “On time required to perform addition”, Journal of the Association for computing machine, vol. 12, No. 2, 1965.
Xilinx, Inc., 2100 Logic Drive, San Jose, CA 95124,RocketlO X Transceiver User Guide, r2002.
Chan Stephanie
DeHon André M.
Papadantonakis Karl
California Institute of Technology
Ngo Chuong D
Steinfl & Bruno LLP
LandOfFree
Method and system for pipelining saturated accumulation and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for pipelining saturated accumulation and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for pipelining saturated accumulation and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4236695