（计算机科学与技术专业论文）奇异值分解算法逻辑设计的资源优化问题研究.pdf

f y 1 燃炒 r e s e a r c ho nt h er e s o u r c eo p t i m i z a t i o ni nt h e l o g i cd e s i g no fs v d a l g o r i t h m b y t a nm a n q i o n g b e ( h u n a nu n i v e r s i t y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o r t h ed e g r e eo f m a s t e ro f e n g i n e e r i n g 1 n c o m p u t e rs c i e n c ea n dt e c h n o l o g y i nt h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y p r o f e s s o rx uc h e n g m a y , 2 0 1 1 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究 所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要 贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明 的法律后果由本人承担。 作者签名： 微夸父 j 日期：纱f 年j 一月编 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容 编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和 汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 濞勃分 ，l 7 、 7 吾蝠 f 日期：劲f ，f 年期编 日期：加c ，1 年f 月诸日 奇异值分解算法逻辑设计的资源优化问题研究 摘要 三维荧光分析是一种复杂体系解析的有效方法，可广泛应用于生命、材料、 环境等领域中样品的解析。但三维荧光分析算法数据规模大、计算复杂度高，难 以在嵌入式设备中推广应用。可编程逻辑器件f p g a 具有并行性和高效性，可以 很好地解决算法在嵌入式环境下的计算要求，但三维荧光分析算法庞大的计算量 使得算法对f p g a 资源的需求相当大。考虑算法实时性要求不高的特点，本文就 如何降低算法逻辑设计的硬件资源消耗进行研究。 奇异值分解( s v d ) 是三维荧光分析的核心计算部件，其算法逻辑设计结构 直接影响三维荧光分析对硬件资源的需求。本文以降低硬件资源为目的，引入逻 辑设计中常用的“功能复用”和“并串转换”等策略，对现有s v d 处理器中基 于c o r d i c 的旋转角度计算结构和双边旋转结构进行改进。具体工作如下： 针对旋转角度计算结构中资源利用率不高的问题，本文采用“功能复用”策 略，设计了一种改进的旋转角度计算结构。该结构通过对c o r d i c 模块内部的 移位器进行功能复用，在原有结构基础上减少了2 个移位器的使用，节省了硬件 资源。 针对双边旋转结构中因数据相关造成资源空闲的问题，本文提出了两种改进 方案，分别设计了并行双边旋转结构和串行双边旋转结构。其中，并行双边旋转 结构通过解除双边旋转过程中左旋转和右旋转的数据相关性，实现了左旋转和右 旋转的并行运算，减少处理时间的同时节省了硬件资源；串行双边旋转结构通过 对2 个c o r d i c 模块进行复用，解决了因数据相关造成的空闲资源浪费问题， 从而减少了大量硬件资源。 考虑位串行结构相比于位并行结构在硬件资源以及时钟频率上的优势，本文 借助“并串转换”策略，利用c o r d i c 位串行结构以及位串行加减器、位串行 移位器等基本运算单元分别对上述改进的旋转角度计算结构、并行双边旋转结 构，以及串行双边旋转结构进行位串行的优化，进一步减少了各结构所占用的硬 件资源。 最后，本文对改进后的结构从正确性和资源优化效果两方面进行验证。首先 利用v e r i l o gh d l 语言实现了改进后的旋转角度计算结构和双边旋转结构，并在 m o d d s i m 平台上对它们进行仿真，仿真结果与理论值相符，验证了结构设计的 正确性。然后，本文实现了改进前的旋转角度计算结构和双边旋转结构，并将它 们与改进后的结构进行性能比较。对比结果显示：当数据位宽为3 2 时，改进的 旋转角度计算结构节省了17 0 1 的硬件资源；并行双边旋转结构和串行双边旋 硕：仁学位论文 转结构分别节省了3 8 1 9 和4 3 5 9 的硬件资源；该结果表明本文改进的结构达 到了很好的资源优化效果。 关键词：三维荧光分析；奇异值分解；j a c o b i 算法；s v d 处理器：c o r d i c 算 法；f p g a ； a b s t r a c t 3 一df l u o r e s c e n c ea n a l y s i st e c h n o l o g yi san e we f f e c t i v ew a yf o r a n a l y s i so f c o m p l e xs y s t e m s i th a sw i d ea p p l i c a t i o np r o s p e c t si nl i f es c i e n c e ，m a t e r i a ls c i e n c e ， e n v i r o n m e n ts c i e n c ea n ds oo n 3 一df l u o r e s c e n c ea n a l y s i sa l g o r i t h mi sb a s e do n l a r g e s c a l e m a t r i xo p e r a t i o n sa n dh a sh i g hc o m p l e x i t y s oi ti s v e r yh a r df o r p o p u l a r i z a t i o na n da p p l i c a t i o ni ne m b e d d e dd e v i c e s t h ep r o g r a m m a b l el o g i cd e v i c e f p g ah a sh i g hp a r a l l e l i s ma n dh i g hs p e e d ，c a ns o l v et h ec a l c u l a t e dr e q u i r e m e n t so f 3 一df l u o r e s c e n c ea n a l y s i sa l g o r i t h mw e l li nt h ee m b e d d e de n v i r o n m e n t ，b u tt h eh u g e c o m p u t a t i o no f3 一d f l u o r e s c e n c ea n a l y s i sa l g o r i t h ml e a d st ot h eb i gd e m a n do f f p g ar e s o u r c e s c o n s i d e rt h a t3 一df l u o r e s c e n c ea n a l y s i sd o n th a v er e a lt i m e r e q u i r e m e n t ，h o wt or e d u c et h ec o n s u m p t i o no fh a r d w a r er e s o u r c e si nl o g i c a ld e s i g n o f3 一df l u o r e s c e n c ea n a l y s i sa l g o r i t h mi ss t u d i e di nt h i sp a p e r s i n g u l a rv a l u ed e c o m p o s i t i o n ( s v d ) i st h ec o m p u t i n g i n t e n s i v ea n dt h em o s t c r i t i c a l c o m p o n e n to ft h e 3 一df l u o r e s c e n c e a n a l y s i s i t sh a r d w a r e r e s o u r c e s u t i l i z a t i o ni nt h el o g i c a ld e s i g nd i r e c t l yi n f l u e n c e st h eh a r d w a r er e s o u r c e sd e m a n d o f3 - df l u o r e s c e n c ea n a l y s i s i no r d e rt or e d u c et h ec o n s u m p t i o no fh a r d w a r e r e s o u r c e so ft h es v dp r o c e s s o r , t h ec o r d i c b a s e da n g l ec a l c u l a t i o ns t r u c t u r ea n d t h ec o r d i c b a s e dt w o - s i d er o t a t i o ns t r u c t u r ei nt h es v d p r o c e s s o ra r ei m p r o v e d w i t h “f u n c t i o n a lm o d u l e sr e u s e ”a n d “p a r a l l e lt os e r i a l c o n v e r s i o n ”s t r a t e g i e si n l o g i cd e s i g n t h ef o l l o w i n gi st h ec o n t e n t so ft h i sw o r k f i r s t ，w i t ht h eu s eo f “f u n c t i o n a lm o d u l e sr e u s e s t r a t e g y , t h ea n g l ec a l c u l a t i o n s t r u c t u r ei s i m p r o v e dt o i n c r e a s et h er e s o u r c e su t i l i z a t i o nr a t e t h ei m p r o v e d s t r u c t u r er e m o v e st w oo u t s i d es h i f t e r sa n ds a v e sr e s o u r c e st h r o u g h r e u s i n gt h e i n t e r n a ls h i f t e ro fc o r d i c t h e n ，t w oi m p r o v e ds c h e m e sa r ep r e s e n t e d ，a n dt h ep a r a l l e lt w o s i d er o t a t i o n s t r u c t r u ea n dt h es e r i a lt w o s i d er o t a t i o ns t r u c t r u ea r ed e s i g n e da c c o r d i n g l yt og e t r i do ft h ef r e er e s o u r c e sc a u s e db yt h ed a t ad e p e n d e n c eb e t w e e nt h el e f tr o t a t i o na n d t h er i g h tr o t a t i o ni nt h et w o - s i d er o t a t i o n t h ep a r a l l e lt w o - s i d er o t a t i o ns t r u c t r u e r e l i e v e st h ed a t ad e p e n d e n c ea n dr e l i z e st h ep a r a l l e lc o m p u t a t i o no ft h e m i tr e d u c e s c e r t a i na r e aa sw e l la st h ep r o c e s s i n gt i m e t h es e r i a lt w o s i d er o t a t i o ns t r u c t r u e r e m o v e st w oc o r d i cm o d u l e sb yr e u s i n gt h eo t h e rt w oc o r d i cm o d u l e s ，a n d s a v e s alo to fr e s o u r c e s i v 硕士学位论文 l 簟昌昌e 昌鼍鼍墨量量盲墨量暑暑量皇篁皇鲁皇皇詈暑毒墨量皇皇皇皇暑昌詈昌詈置皇詈詈皇皇皇墨皇= 詈詈暑詈皇詈皇皇詈篁篁暑暑暑詈皇暑詈詈詈詈詈詈詈暑詈皇皇皇皇! 巴= 皇皇= 詈詈詈詈詈墨 c o n s i d e rt h a tt h eb i t s e r i a ls t r u e t u r eh a sa d v a n t a g e so nt h eh a r d w a r er e s o u r c c a n dt h ec l o c k 疔e q u e n c yt h a nt h eb i t p a r a l l e ls t r u c t u r e ，w i t ht h eu s eo f “p a r a l l e lt o s e r i a l c o n v e r s i o n ”s t r a t e g y , t h eb i t s e r i a lo p t i m i z a t i o n sf o r t h ei m p r o v e da n g l e c a l c u l a t i o ns t r u c t u r e ，t h ep a r a l l e lt w o - s i d er o t a t i o ns t r u c t r u ea n dt h es e r i a lt w o s i d e r o t a t i o ns t r u c t r u ea r em a d eb yu s i n gt h eb i t - s e r i a l c o r d i c ，b i t s e r i a la d d e ro r s u b t r a c t o r , a n db i t s e r i a ls h i f t e r a n dt h eo p t i m i z a t i o n sc a nr e d u c eal o to fh a r d w a r e r e s o u r c e sf - u t h e r f i n a l l y , t h ec o r r e c t n e s sa n dt h eo p t i m i z a t i o ne f f e c to ft h eo p t i m i z e ds t r u c t u r e s a r ev e r i f i e d t ov e r i f yt h ec o r r e c t n e s s ，t h ev e r i l o gh d li su s e dt od e s c r i b et h e i m p r o v e ds t r u c t u r e s a n dt h e n ，t h ei m p r o v e ds t r u c t u r e sa r es i m u l a t e do nm o d e l s i m b yw r i t i n gt h et e s t b e n c h e s t ov e r i f yt h eo p t i m i z a t i o ne f f e c t ，t h eo r i g i n a ls t r u c t u r e s a r er e a l i z e dw i t ht h ee q u i v a l e n tf u n c t i o na n di nt h es a m ec o n d i t i o n s ，a n dt h e i r p e r f o r m a n c ec o m p a r i s o ns h o w s ：w h e nt h ed a t ai st h e3 2 b i t sw i d e ，t h ei m p r o v e d a n g l ec a l c u l a t i o ns t r u c t r u es a v e s17 01 r e s o u r c e s t h ep a r a l l e lt w o s i d er o t a t i o n s t r u c t r u es a v e s3 8 19 r e s o u r c e sa n dt h es e r i a lt w o s i d er o t a t i o ns t r u c t r u es a v e s 4 3 5 9 r e s o u r c e s k e yw o r d s ：3 一df l u o r e s c e n c ea n a l y s i s ；s i n g u l a rv a l u ed e c o m p o s i t i o n ；j a c o b i a l g o r i t h m ；s v dp r o c e s s o r ；c o r d i ca l g o r i t h m ；f p g a ； v 奇异值分解算法逻辑设计的资源优化问题研究 目录 学位论文原创性声明和学位论文版权使用授权书i 摘要i l a b s t r a e t 1 1 0 r 插图索引v i i i 附表索引一i x 第1 章引言1 1 1 论文工作背景1 1 1 1 课题来源1 1 1 2 研究背景及意义一1 1 1 3 研究目的2 1 2 国内外研究现状2 1 3 本文主要工作4 1 4 本文的组织结构5 1 5 小结6 第2 章奇异值分解算法逻辑设计相关研究7 2 1 引言7 2 2 逻辑设计基础与方法7 2 2 1 逻辑设计基础一7 2 2 2 硬件描述语言( h d l ) 9 2 2 3 可编程逻辑器件( f p g a ) 1 0 2 2 4 逻辑设计的性能评价指标1 1 2 3j a c o b i 奇异值分解算法一11 2 3 1 双边j a c o b i 算法1 1 2 3 2 双边j a c o b i 算法的并行处理1 4 2 4c o r d i c 算法17 2 4 1 基本原理1 8 2 4 2 工作模式2 0 2 5 小结2l 第3 章基于功能复用的资源优化2 2 3 1 引言2 2 3 2j a c o b i 奇异值分解算法的逻辑结构分析2 2 v l 硕士学位论文 3 2 1 顶层结构一2 2 3 2 2 底层结构一2 3 3 2 3 底层结构分析2 5 3 3 基于功能复用的结构优化2 6 3 3 1 旋转角度计算结构优化2 6 3 3 2 双边旋转结构优化2 7 3 4 小结3 1 第4 章基于位串行的资源优化一3 2 4 1 引言3 2 4 2c o r d i c 逻辑结构分析3 2 4 2 1 位并行结构3 2 4 2 2 位串行结构3 3 4 2 3 两种结构的分析比较3 4 4 3 基于位串行的结构优化3 6 4 3 1 基本运算单元的位串行设计3 6 4 3 2 旋转角度计算结构的位串行优化3 7 4 3 3 双边旋转结构的位串行优化3 8 4 4 小结4 2 第5 章设计验证一4 3 5 1 验证平台与方法：4 3 5 2 改进结构的仿真验证4 4 5 2 1 旋转角度计算结构仿真4 4 5 2 2 双边旋转结构仿真4 5 5 2 3 整体结构仿真4 6 5 2 4 仿真结果分析4 8 5 3 性能比较4 8 5 4 小结4 9 总结与展望5 0 参考文献5 2 致谢5 6 附录a 攻读学位期间所发表的论文与书籍一5 7 附录b 攻读学位期间所参与的课题与项目5 8 v i l 奇异值分解算法逻辑设计的资源优化问题研究 插图索引 2 18 x 8 矩阵的b l v 阵列结构l5 2 2s v d 处理器对角化的输入输出1 6 2 3b l v 阵列数据交换实例1 7 2 4 向量在二维平面的旋转1 8 2 5c o r d i c 旋转模式2 0 3 18 x 8 矩阵的b l v 阵列2 3 3 2 基于c o r d i c 的旋转角度计算结构一2 4 3 3 基于c o r d i c 的双边旋转结构2 5 3 4 改进的旋转角度计算结构一2 6 3 5 并行双边旋转结构2 8 3 6 并行双边旋转结构中的因子扩展模块一2 9 3 7 串行双边旋转结构3 0 3 8 串行双边旋转结构中的因子扩展模块3 0 4 1c o r d i c 位并行结构一3 3 4 2c o r d i c 位串行结构3 3 4 3 串行加减器3 6 4 4 串行移位寄存器3 7 4 5 改进的c o r d i c 位串行结构z 部分3 8 4 6 旋转角度计算结构的位串行优化一3 8 4 7 并行双边旋转中左右旋转模块的位串行优化3 9 4 8 并行双边旋转中因子扩展模块的位串行优化4 0 4 9 串行双边旋转中左右旋转模块的位串行优化一4 0 4 1 0 串行双边旋转中因子扩展模块的位串行优化4 l 5 1 实验平台4 3 5 2 数据组织结构一4 4 5 3 旋转角度计算结构仿真波形一4 5 5 4 并行双边旋转结构仿真波形4 5 5 5 串行双边旋转结构仿真波形4 6 5 6b l v 阵列仿真波形( 1 ) 一4 7 5 7b l v 阵列仿真波形( 2 ) 一4 7 图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图 硕+ 学位论文 附表索引 2 1 扩展因子k n 与迭代次数n 的关系2 0 4 1c o r d i c 位并行结构性能3 5 4 2c o r d i c 位串行结构性能3 5 4 3 两种结构性能比较( 位串行：位并行) 一3 5 4 4 两种双边旋转结构的比较4 l 5 1b l v 阵列仿真结果与理论值的比较( 1 ) 4 7 5 2b l v 阵列仿真结果与理论值的比较( 2 ) 一4 7 5 3 改进前各个结构的性能4 8 5 4 改进后各个结构的性能4 8 5 5 硬件资源比较( 改进后：改进前) 4 8 l x 表表表表表表表表表表 硕士学位论文 第1 章引言 1 1 论文工作背景 1 1 1 课题来源 对于复杂体系解析三维荧光分析技术的研究，湖南大学化学生物传感与计量 学国家重点实验室走在世界前列。多年来，实验室无论在荧光分析理论，还是应 用研究方面都做了大量的工作，并取得了一系列瞩目的成果。该实验室联合湖南 大学信息科学与工程学院嵌入式系统及网络实验室，倡导并力行以“数学分离” 代替或增强化学或物理分离，并为研发基于“数学分离”的系列新型分析仪器提 供了新的设计依据和创新性思路。 本课题得到湖南省科研条件创新专项“三维荧光光谱分析仪高性能数学分离 关键部件研制”的资助。 1 1 2 研究背景及意义 在分析科学领域，荧光分析技术因其高灵敏度己成为该领域的研究热点并得 到了广泛的应用。在荧光分析技术中，三维荧光分析是最近几十年才发展起来 的一门重要技术，用于复杂体系( 未知干扰物共存下) 解析，在生命科学、材料 科学、环境科学和石油化工等方面极有应用价值1 2 】。 现有三维荧光分析仪因缺乏专用计算平台，必须依赖桌面计算机，借助 m a t l a b 平台对仪器采集的数据进行二次分析和处理。仪器、p c 等的不便携性， 以及m a t l a b 知识产权的限制，阻碍了三维荧光分析技术的进一步推广。因此， 研制面向三维荧光分析，且具有携带方便、低功耗、易操作等特点高性能嵌入式 专用计算设备对推动三维荧光分析技术的应用和普及具有重要作用。 在嵌入式领域，算法的实现可大致分为软件和硬件两大类。软件实现灵活性 高，且具有很强的通用性和可移植性，但是它需要比较庞大的操作系统支持，因 而速度较慢。而硬件实现则具有低功耗、高速度等特点，但是对开发人员的要求 比较高。一般来说，硬件实现较多地应用于嵌入式专用计算设备和具有特殊要求 的高性能计算设备中。 目前一些主流的硬件计算平台包括基于d s p ( d i g i t a ls i g n a lp r o c e s s o r ，数字 信号处理器) 的计算平台以及基于f p g a ( f i e l dp r o g r a m m a b l eg a t aa r r a y ，现场 可编程门阵列) 的计算平台。d s p 是一种精简指令集计算机的范例，可以在一 个时钟周期内完成定点数的乘加运算。对于需要定期系数更新、决策控制任务或 奇异值分解算法逻辑设计的资源优化问题研究 高速串行数学运算这类任务来说，d s p 体现了良好的适应性。但对于多通道、 海量并行数据处理应用来说，基于d s p 的计算平台因受制于时钟速率和串行指 令流的限制，难以在资源、成本或功耗上取得令人满意的平衡。f p g a 相比于 d s p 具有在计算结构上的细粒度可编程优势，且在大带宽的海量并行数据处理 方面性能优越，兼具有高速、灵活、低功耗、可重构等特点，在高性能嵌入式计 算领域越来越受青睐。 随着微电子学的发展和集成电路生产工艺的进步，大规模和超大规模集成电 路的生产制作技术日趋成熟，f p g a 芯片的集成度也越来越高，且速度，功耗等 性能都在提升。研制以f p g a 为平台，面向三维荧光分析的高性能嵌入式专用计 算设备成为可能。然而，三维荧光分析算法需要处理大规模矩阵运算，计算复杂 度高，如果将算法完全映射到f p g a 上，需要消耗大量的f p g a 资源，使得系统 的成本和功耗都会比较高。因此，在三维荧光分析算法的f p g a 实现过程中，如 何降低算法对硬件资源的消耗仍然是一项极具挑战，且亟待解决的任务。 周等【3 】对三维荧光分析算法进行了运行时分析，得出矩阵的奇异值分解是三 维荧光分析的基础关键部件。奇异值分解算法逻辑设计的效率和硬件资源利用率 将直接影响三维荧光分析的性能以及对硬件资源的需求。由于三维荧光分析对数 据的处理并没有实时性要求，因此，在奇异值分解算法逻辑设计过程中，利用算 法的并行性，充分发挥f p g a 并行处理结构的优势，提高奇异值分解效率的同时， 更重要的是节省硬件资源，提高资源利用率，减少算法对f p g a 资源的需求，必 要的时候，甚至可以牺牲一定的计算速度来换取硬件资源，使得同样面积的 f p g a 可以实现更大规模矩阵的奇异值分解。这样不但可以降低系统功耗，也可 以减少系统成本，符合三维荧光分析仪嵌入式专用计算设备产业化发展的方向， 有助于三维荧光分析技术的应用推广，也可以促进嵌入式计算技术在分析科学领 域的应用。 1 1 3 研究目的 本文主要对奇异值分解算法的逻辑设计进行资源优化研究。针对现有奇异值 分解逻辑设计因追求速度而造成的资源消耗极大的问题，本文采用相应的“功能 复用“或者“并串转换”等资源优化策略，对现有结构进行改进，使其占用更少 的硬件资源，为实现三维荧光分析中大规模矩阵奇异值分解奠定基础。 1 2 国内外研究现状 奇异值分解是线性代数中一个重要的矩阵分解，作为矩阵计算、矩阵分析的 强大工具之一，它在光谱分析，主成分分析，信号和图像处理等领域都有很广泛 的应用1 4 5 ”s 2 6 l 。 2 硕上学位论文 关于奇异值分解算法的研究最早可以追溯到1 8 7 3 年b e l t r a m i 所做的工作， 但是直到1 9 6 5 年g o l u b 和k a h a n 才在奇异值分解的数值计算领域取得突破性进 展【，】，并且于l9 6 9 给出了比较稳定的算法u o ，即传统q r 迭代算法，它的中心思 想是利用正交变换将原矩阵转化为双对角线矩阵，然后再对双对角线矩阵迭代进 行q r 分解。 六十年代，k a h a n 证明了双对角线矩阵的奇异值可以精确地计算，具有和原 矩阵元素一样的精确度。到九十年代初期，k a h a n 和d c m m e l 给出了一种零位移 q r 算法，这种算法计算双对角矩阵的奇异值具有很高的相对精度 i l l 。f e m a n d o 和p a r l c t t 在19 9 4 年提出了一种全新的比零位移q r 算法更加精确和快速的奇异 值分解算法f 1 2 1 3 l 。 而d e m m c l 和v c s c l i c 在文献【1 4 】中则说明了用j a c o b i 方法【j 5 l 与其它方法相 比计算所得到的奇异值和奇异向量具有更高的精度，但比零位移q r 算法速度要 慢的多；文献 1 6 中j a c o b i 方法进行了改进使得其在速度上几乎和零位移q r 算法相当。 上述奇异值分解算法中，传统q r 迭代算法比较成熟，但是在性能和精确度 上都不够理想。零位移q r 算法从传统q r 迭代算法发展而来，从中继承了很多 成熟的技巧，所以也相对的完善，并且具有较高的效率和良好的精确度，所以是 一种比较适中的方法。j a c o b i 算法是唯一一种不需要先对角化的方法，这保证 了它的精确度是所有算法中最高的，且文献【1 6 】对它进行了各种改进，使得它的 效率可以和其它方法相当，成为一种值得选用的方法。 j a c o b i 算法现在已经发展成为一种应用最为广泛的奇异值分解算法。由于 j a c o b i 算法存在高度的潜在并行性，目前j a c o b i 算法的研究主要集中在利用 f p g a 等并行处理结构实现所有元素的并行计算。二十世纪八十年代初，b r e n t 、 l u k 以及v a nl o a n 首先提出了一种由o ( n 2 ) 个奇异值分解处理器( s v d 处理器) 组成的二维s y s t o l i c 阵列结构( b l v 阵列) ，用来解决nxn 实对称矩阵的奇异值 分解问题【”1 ；随后又提出了一种由o ( n ) 个s v d 处理器组成的一维s y s t o l i c 阵列， 用来解决m r l 矩阵的奇异值分解问题 1 8 j ；为进一步减少奇异值分解所消耗的时 间，考虑利用o ( n 2 ) 个s v d 处理器组成的二维s y s t o l i c 阵列，用来解决m n 矩 阵的奇异值分解问题【”】。b r e n t 等人所提出的阵列结构都充分利用了j a c o b i 算 法的并行性，很大程度地提高了奇异值分解的效率。b r e n t 等人【 js - ，s 0 的工作成 为了研究j a c o b i 算法并行计算及其f p g a 实现的重要基础。 b r e n t 等提出的b l v 阵列的基本组成单元是s v d 处理器，j rc a v a l l a r o 以 及f t l u k wj 最早提出利用c o r d i c 算法来设计b l v 阵列中的s v d 处理器，并 做了相关的理论研究，分析了s v d 处理器的时间和空间复杂度，后续相关研究 1 2 2 , 2 又2 4 2 5 ，2 6 ，2 7 1 都在该文献基础之上。其中，c o r d i c 算法f 2 8 l 是一种仅仅通过加法和 3 奇异值分解算法逻辑设计的资源优化问题研究 移位操作就能实现的硬件算法，特别适用于实现奇异值分解。r a ya n d r a k a t 2 9 】讨 论了c o r d i c 算法在f p g a 上的实现结构，包括位并行结构、位串行结构等， 并对各个结构进行了详细的分析比较。文献 2 2 】结合c o r d i c 算法，提出了一种 j a c o b i 算法在f p g a 上的实现结构，并对结构的性能进行了详细的分析和评估。 为了减少j a c o b i 算法的计算量，文献 2 3 】提出了一种基于c o r d i c 的近似 j a c o b i 算法。文献【2 4 研究了基于c o r d i c 的s v d 处理器的v l s i 的实现。文 献【2 5 对s v d 处理器进行了改进，在每个s v d 处理器上增加一个存储控制模 块，以实现更大规模矩阵的奇异值分解而不增加资源消耗。文献 2 6 和文献 2 7 】 分别设计了具有不同性能的s v d 处理器应用于特征子空间雷达目标识别中。 国内外对于b l v 阵列结构以及阵列中s v d 处理器的研究，主要以提高奇异 值分解效率，满足应用系统的实时要求为目标，借助逻辑设计中“流水操作”以 及“串并转换”等策略，对现有结构进行改进，以更多的硬件资源换取更高的速 度。而这样的结构并不适用于三维荧光分析，因此，本文的研究工作将主要提高 现有结构的资源利用率，减少其所占用的硬件资源。 1 3 本文主要工作 三维荧光分析高性能嵌入式专用计算设备研制对推动三维荧光分析技术的 应用和普及起着重要作用。然而三维荧光分析算法以大规模矩阵运算为基础，数 据量和计算量惊人，在算法移植过程中，如何降低算法或算法中的关键部件对硬 件资源的需求，成为研制高性能嵌入式专用设备亟待解决的首要问题。 奇异值分解作为三维荧光分析的核心计算部件，它的执行效率以及对硬件资 源的利用率直接影响三维荧光分析的性能及资源的消耗。本文依托湖南省科研条 件创新专项“三维荧光光谱分析仪高性能数学分离关键部件研制 为背景，以减 少三维荧光分析中奇异值分解所占用的硬件资源为目标，围绕奇异值分解算法逻 辑设计的资源优化问题展开研究。具体来说，本文的主要工作如下： 1 对奇异值分解算法逻辑设计的相关问题进行了分析，讨论与总结，为后 文奇异值分解算法逻辑设计的资源优化问题的研究提供理论基础和依据。具体问 题包括： ( 1 ) 逻辑设计基础与方法，包括一些相关概念，后文中涉及的基本逻辑电 路，以及逻辑设计的性能评价指标等。 ( 2 ) 经典的双边j a c o b i 奇异值分解算法，算法的并行调度规则，f p g a 实现算法的逻辑结构一一b l v 阵列结构，以及阵列中s v d 处理器的工作原理。 ( 3 ) 与s v d 处理器的旋转角度计算和双边旋转都相关的c o r d i c 算法的 基本原理和工作模式。 2 利用逻辑设计中常用的“功能复用”以及“并串转换”策略对b l v 阵列 4 硕上学位论文 中s v d 处理器的基本组成单元一一旋转角度计算结构和双边旋转结构一一进行 资源优化，具体方法如下： ( 1 ) 针对旋转角度计算结构，对c o r d i c 内部的移位器进行功能复用，在 原有结构基础上减少了2 个移位器的使用，节省一定硬件资源。 ( 2 ) 针对双边旋转结构，对其中2 个c o r d i c 模块进行功能复用，并给出 了两种改进方案，都在原有结构基础上减少了2 个c o r d i c 模块的使用。节省 大量的硬件资源。 ( 3 ) 利用c o r d i c 位串行结构以及位串行加减器、位串行移位器等基本运 算单元分别完成了旋转角度计算结构和双边旋转结构的位串行优化，进一步减少 硬