一类图像处理算法的可重构研究
摘要
传统的冯·诺依曼体系结构的通用处理器都含有固定的硬件结构，通过顺序执行指令来实现计算任务，本质上是串行的，而专用集成电路(ASIC)将适当的功能单元以固定的方式连接起来完成计算任务，本质上是并行的。通用处理器以时间来换取处理问题的灵活性，专用处理器效率高但灵活性差，可重构计算技术(Reconfigurable Computing—RC)为传统通用处理器和专用处理器提供了一个非常有价值的发展方向。可重构计算技术处于灵活性和效率的中间位置，结合了通用和专用二者的优点，在概念上既有ASIC一样高效硬件电路实现也有类似于通用处理器的灵活性。目前大多数研究成果基本由现场可编程门阵列器件(FPGA)和通用处理器构成，由可编程器件提供对复杂运算的加速计算能力。
离散傅立叶变换(Discrete Fourier Transformation_DFT)是数字信号分析与处理如图形、语音及图像等领域的重要变换工具，是数字图像处理技术的基础，通过在时域和频域来同切换图像，对图像的信息特征进行提取和分析，简化了计算工作量，被喻为描述图像信息的第二种语言，广泛应用在图像变换。图像编码与压缩、图像分割、图像重建中。它的快速算法—快速傅立叶变换(FFT)是当前信息处理领域中广泛应用的一种重要工具，但因其计算量巨大，很大程度上限制了其在实时处理领域的应用。本文介绍了可重构技术原理，在此基础上：
1．阐述了可重构系统的特点以及研究内容，并讨论了其应用前景。
2．以快速傅立叶变换为实例算法，根据算法特点进行可重构结构设计，以可重构实验板为载体完成算法实现，FFT算法的关键在于蝶形运算(Butterfly)的设计和地址产生逻辑的设计，地址产生逻辑配合蝶形运算的流水设计以可重构方式实现不同点数的FFT运算排序功能，在提高系统性能的同时节约了物理资源。
3．对影响系统性能的浮点乘法器进行了多种设计，比较了基于FPGA结构的乘法器和基于传统并行思想的乘法器设计。本论文参考了现有的几种典型乘法器结构，提出两种乘法器结构方案，并进行比较分析，在满足性能指标的同时，还考虑了体积、功耗、等因素，在此基础上，进行了可重构技术应用的研究。
结果表明，可重构系统在数据处理能力方面比以往的系统有了很大的提高，本设计实现的FFT重构处理器可工作于60MHz下，完成一个16点FFT需要132个主时钟周期，完成32点FFT需要324个主时钟周期，而且具有一定可重构性，可以方便地将其运算点数进行扩展，或将其他的图像处理算法在实时处理系统中实现。可重构系统作为数字电路系统设计的新方法，和传统的计算系统相比，不仅节省硬件资源的开销，且自适应能力强，可靠性高，具有很高的优越性。
Though the General-purpose processor was flexible in calculation, it was lack of efficiency, and ASIC was more efficient but less in flexibility. As a resolution the reconfigurable technology provide a very valuable developing direction. Reconfigurable technology can be a new useful technology in real-time signal processing, biologic information processing, simulation of VLSI, etc. It is a focal technology of international academy and industrial field.
DFT is a common tool that is widely used in image processing and digital signal analysis. But the large scale of computation prevents it from been used in real-time system.
This dissertation introduces concepts and advantages of reconfigurable processing, on the bases of these:
1. Discusses the reconfigurable technology and its application foreground.
2. Use FFT as an example algorithm, analyze the structure of the algorithm to build the reconfigurable system and to implement the design .the pipeline thinking was used in the schema.
3. Puts forward two schemes related to float multiplier, and compares them.
The key to the FFT algorithm is the design of butterfly computation and that of the address logic. The whole schema is designed in the top-down design flow and described in the VHSIC hardware description language(VHDL), basing on these, we do our research on reconfigurable technology.
The result indicates that the data processing ability of reconfigurable system improved greatly. The system has the reconfigurable ability to implement different algorithms easily. Compared with traditional calculation system, RC system has strong adaptive computing capacity and saves hardware resources as well.
离散傅立叶变换(Discrete Fourier Transformation_DFT)是数字信号分析与处理如图形、语音及图像等领域的重要变换工具，是数字图像处理技术的基础，通过在时域和频域来同切换图像，对图像的信息特征进行提取和分析，简化了计算工作量，被喻为描述图像信息的第二种语言，广泛应用在图像变换。图像编码与压缩、图像分割、图像重建中。它的快速算法—快速傅立叶变换(FFT)是当前信息处理领域中广泛应用的一种重要工具，但因其计算量巨大，很大程度上限制了其在实时处理领域的应用。本文介绍了可重构技术原理，在此基础上：
1．阐述了可重构系统的特点以及研究内容，并讨论了其应用前景。
2．以快速傅立叶变换为实例算法，根据算法特点进行可重构结构设计，以可重构实验板为载体完成算法实现，FFT算法的关键在于蝶形运算(Butterfly)的设计和地址产生逻辑的设计，地址产生逻辑配合蝶形运算的流水设计以可重构方式实现不同点数的FFT运算排序功能，在提高系统性能的同时节约了物理资源。
3．对影响系统性能的浮点乘法器进行了多种设计，比较了基于FPGA结构的乘法器和基于传统并行思想的乘法器设计。本论文参考了现有的几种典型乘法器结构，提出两种乘法器结构方案，并进行比较分析，在满足性能指标的同时，还考虑了体积、功耗、等因素，在此基础上，进行了可重构技术应用的研究。
结果表明，可重构系统在数据处理能力方面比以往的系统有了很大的提高，本设计实现的FFT重构处理器可工作于60MHz下，完成一个16点FFT需要132个主时钟周期，完成32点FFT需要324个主时钟周期，而且具有一定可重构性，可以方便地将其运算点数进行扩展，或将其他的图像处理算法在实时处理系统中实现。可重构系统作为数字电路系统设计的新方法，和传统的计算系统相比，不仅节省硬件资源的开销，且自适应能力强，可靠性高，具有很高的优越性。
Though the General-purpose processor was flexible in calculation, it was lack of efficiency, and ASIC was more efficient but less in flexibility. As a resolution the reconfigurable technology provide a very valuable developing direction. Reconfigurable technology can be a new useful technology in real-time signal processing, biologic information processing, simulation of VLSI, etc. It is a focal technology of international academy and industrial field.
DFT is a common tool that is widely used in image processing and digital signal analysis. But the large scale of computation prevents it from been used in real-time system.
This dissertation introduces concepts and advantages of reconfigurable processing, on the bases of these:
1. Discusses the reconfigurable technology and its application foreground.
2. Use FFT as an example algorithm, analyze the structure of the algorithm to build the reconfigurable system and to implement the design .the pipeline thinking was used in the schema.
3. Puts forward two schemes related to float multiplier, and compares them.
The key to the FFT algorithm is the design of butterfly computation and that of the address logic. The whole schema is designed in the top-down design flow and described in the VHSIC hardware description language(VHDL), basing on these, we do our research on reconfigurable technology.
The result indicates that the data processing ability of reconfigurable system improved greatly. The system has the reconfigurable ability to implement different algorithms easily. Compared with traditional calculation system, RC system has strong adaptive computing capacity and saves hardware resources as well.
引文
1． 周孝宽，曹晓光等《实用微机图像处理》，北京航空航天大学出版社，1994
2． 刘政凯《微型计算机数字图像处理技术》，安徽技术出版社，1991
3． [英]R．J．奥芬《图像的并行处理技术》，科学出版社，1989
4． 毕厚杰，陈延标等《图像通信工程》，人民邮电山版社，1987
5． 江国强《现代数字逻辑电路》，电子工业出版社，2002
6． 崔屹《数字图象处理技术与应用》电子工业出版社 1997
7． [美]J．Bhasker《Verilog HDL硬件描述语言》机械工业出版社，2000
8． 邓贤照，徐英凯编写《快速傅立叶变换浅谈》／水利电力出版社 1994
9． Altera器件数据手册，2003
10． 《电子工程专辑》www.eetchina.com 2003.8.25
11. V.C. Chan and D. M. Lewis. Area-speed tradeoffs for hierarchical field-programmable gate arrays. In Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA'96:51-57, 1996
12. John F.Wakerly 《Digital Design Principles & Practices》 (Third Edition) Perason Education出版集团高等教育出版社 2001
13． 白中英《计算机组成原理》科学出版社 1994
14． 白中英 岳怡 郑岩《数字逻辑与数字系统》科学出版社 1998
15． 程佩青编《数字滤波与快速傅立叶变换》清华大学出版社 1990
16. Donald E. Thomas, Philip R. Moorby 《The Verilog Hardware Description Lanuage》 KLUWER ACADEMIC PUBLISHERS 2001
17． 李学干 苏东庄《计算机系统结构》西安电子科技大小出版社 1991
18． 高德远、马婉良译著：“Xilinx现场可编程门阵列及其应用”，西北工业大学出版社，1996年10月
19. John R. Hauser and John Wawrzynek, Garp: A MIPS Processor with a Reconfigurable Coprocessor University of California, Berkeley
20. B. Fross, D.M. Hawver, and J. P. Peterson. WILDFIRE heterogeneous adaptive parallel processing system. In Proceedings of the First Merged International Parallel Processing Symposium & Symposium on Parallel and Distributed Processing, IPPS/SPDP'98:611-615, 1998
21. C. Ebeling, D.C. Cronquist, and R Franklin. Configurable computing: The catalyst for high-performance architectures. In Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures and Processors, ASAP'97:364-372, 1997
22. R J. Bakkes and J. J. du Plessis. Mixing fixed and reconfigurable logic for array processing. In Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, FCCM'96: 118-125, 1996
23. S. Cadambi, J. Weener, S.C. Goldstein, H. Schmit, and D. E. Thomas. Managing pipeline-reconfigurable FPGAs. In Proceedings of the ACM/SIGDA International
Symposium on Field Programmable Gate Arrays, FPGA'98:55-64, 1998
24. J.A. Fernando and J. S.-N. Jean. Processor array design with FPGA area constraint. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 18(3):253--264, March 1999
25. Boschetti, M.R., Adario, A.M.S., Silva, I.S., et al. Techniques and mechanisms for dynamic reconfiguration in an image processor Proceedings 15th Symposium on Integrated Circuits and Systems Design 177-82 2002
26. paul Graham and Brent Nelson Reconfigurable Processors for High-Performance,Embedded Digital Signal Processing 459 Clyde Building, Brigham Young University,Provo UT 84602, USA
27. Doss,Christopher Cornelius Algorithm partitioning and scheduling for adaptive computers North Carolina State University Dissertation Abstracts International, Volume: 62-10 2001
28. Singh, Hartej: Lee, Ming-Hau; Lu, Guangming; Kurdahi, Fadi J.; Bagherzadeh, Nader; Chaves Filho, Eliseu M. An integrated reconfigurable system for data-parallel and computation-intensive applications IEEE Transactions on Computers, v49, n5, May, 2000, p465-481
29. Fromherz, Markus P.J.; Bobrow, Daniel G.; De Kleer, Johan Model-Based Computing for Design and Control of Reconfigurable Systems AI Magazine, v24, n4, Winter, 2003, p 120-130
30. Chin, Shu-Shin; Wu, Wei; Hong, Sangjin Rapidly reconfigurable coarse-grained FPGA architecture for digital filtering applications Midwest Symposium on Circuits and Systems, v 3, 2002, pⅢ203-Ⅲ206
31． 谷萩隆嗣编(日)《VLSI与数字信号处理》：北京-科学出版社 2003
32． 曲英杰《可重构密码协处理器的概念及其设计原理》东北大学 计算机工程与应用 2003
33． 戴明桢 周建江《TMS320C54XDSP结构、原理及应用》北京航空航天大学出版社 2001
34． 牟澄宇《单芯片可重构计算系统体系结构研究》西北工业大学 1999
35． 徐志军，徐光辉 《CPLD／FPGA的开发与应用》北京电子工业出版社 2002
36． 李丽．辛勤．杨乐平《基于FPGA的可重构系统的应用》CJFD收录期刊 微处理机2001年03期
37． 佟风辉 樊晓桠 王党辉《Karatsuba算法的应刚研究》计算机工程与应用 2002年12期
2． 刘政凯《微型计算机数字图像处理技术》，安徽技术出版社，1991
3． [英]R．J．奥芬《图像的并行处理技术》，科学出版社，1989
4． 毕厚杰，陈延标等《图像通信工程》，人民邮电山版社，1987
5． 江国强《现代数字逻辑电路》，电子工业出版社，2002
6． 崔屹《数字图象处理技术与应用》电子工业出版社 1997
7． [美]J．Bhasker《Verilog HDL硬件描述语言》机械工业出版社，2000
8． 邓贤照，徐英凯编写《快速傅立叶变换浅谈》／水利电力出版社 1994
9． Altera器件数据手册，2003
10． 《电子工程专辑》www.eetchina.com 2003.8.25
11. V.C. Chan and D. M. Lewis. Area-speed tradeoffs for hierarchical field-programmable gate arrays. In Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA'96:51-57, 1996
12. John F.Wakerly 《Digital Design Principles & Practices》 (Third Edition) Perason Education出版集团高等教育出版社 2001
13． 白中英《计算机组成原理》科学出版社 1994
14． 白中英 岳怡 郑岩《数字逻辑与数字系统》科学出版社 1998
15． 程佩青编《数字滤波与快速傅立叶变换》清华大学出版社 1990
16. Donald E. Thomas, Philip R. Moorby 《The Verilog Hardware Description Lanuage》 KLUWER ACADEMIC PUBLISHERS 2001
17． 李学干 苏东庄《计算机系统结构》西安电子科技大小出版社 1991
18． 高德远、马婉良译著：“Xilinx现场可编程门阵列及其应用”，西北工业大学出版社，1996年10月
19. John R. Hauser and John Wawrzynek, Garp: A MIPS Processor with a Reconfigurable Coprocessor University of California, Berkeley
20. B. Fross, D.M. Hawver, and J. P. Peterson. WILDFIRE heterogeneous adaptive parallel processing system. In Proceedings of the First Merged International Parallel Processing Symposium & Symposium on Parallel and Distributed Processing, IPPS/SPDP'98:611-615, 1998
21. C. Ebeling, D.C. Cronquist, and R Franklin. Configurable computing: The catalyst for high-performance architectures. In Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures and Processors, ASAP'97:364-372, 1997
22. R J. Bakkes and J. J. du Plessis. Mixing fixed and reconfigurable logic for array processing. In Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, FCCM'96: 118-125, 1996
23. S. Cadambi, J. Weener, S.C. Goldstein, H. Schmit, and D. E. Thomas. Managing pipeline-reconfigurable FPGAs. In Proceedings of the ACM/SIGDA International
Symposium on Field Programmable Gate Arrays, FPGA'98:55-64, 1998
24. J.A. Fernando and J. S.-N. Jean. Processor array design with FPGA area constraint. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 18(3):253--264, March 1999
25. Boschetti, M.R., Adario, A.M.S., Silva, I.S., et al. Techniques and mechanisms for dynamic reconfiguration in an image processor Proceedings 15th Symposium on Integrated Circuits and Systems Design 177-82 2002
26. paul Graham and Brent Nelson Reconfigurable Processors for High-Performance,Embedded Digital Signal Processing 459 Clyde Building, Brigham Young University,Provo UT 84602, USA
27. Doss,Christopher Cornelius Algorithm partitioning and scheduling for adaptive computers North Carolina State University Dissertation Abstracts International, Volume: 62-10 2001
28. Singh, Hartej: Lee, Ming-Hau; Lu, Guangming; Kurdahi, Fadi J.; Bagherzadeh, Nader; Chaves Filho, Eliseu M. An integrated reconfigurable system for data-parallel and computation-intensive applications IEEE Transactions on Computers, v49, n5, May, 2000, p465-481
29. Fromherz, Markus P.J.; Bobrow, Daniel G.; De Kleer, Johan Model-Based Computing for Design and Control of Reconfigurable Systems AI Magazine, v24, n4, Winter, 2003, p 120-130
30. Chin, Shu-Shin; Wu, Wei; Hong, Sangjin Rapidly reconfigurable coarse-grained FPGA architecture for digital filtering applications Midwest Symposium on Circuits and Systems, v 3, 2002, pⅢ203-Ⅲ206
31． 谷萩隆嗣编(日)《VLSI与数字信号处理》：北京-科学出版社 2003
32． 曲英杰《可重构密码协处理器的概念及其设计原理》东北大学 计算机工程与应用 2003
33． 戴明桢 周建江《TMS320C54XDSP结构、原理及应用》北京航空航天大学出版社 2001
34． 牟澄宇《单芯片可重构计算系统体系结构研究》西北工业大学 1999
35． 徐志军，徐光辉 《CPLD／FPGA的开发与应用》北京电子工业出版社 2002
36． 李丽．辛勤．杨乐平《基于FPGA的可重构系统的应用》CJFD收录期刊 微处理机2001年03期
37． 佟风辉 樊晓桠 王党辉《Karatsuba算法的应刚研究》计算机工程与应用 2002年12期