（微电子学与固体电子学专业论文）lut结构工艺映射算法的研究.pdf

目录 4 1 s a m a p 算法概述2 9 4 2 模拟退火算法2 9 4 3 映射问题模型3 0 4 4s a m a p 算法3 2 4 4 1 状态初始化3 2 4 4 2 目标函数定义3 4 4 4 3 新状态产生3 5 4 4 4 状态接受判断3 6 4 4 5 温度控制3 7 4 4 6 结束退火条件3 8 4 5 映射方案生成3 8 4 6l u t 单元编程信息生成j 4 0 4 7 实验结果4 2 第五章总结与展望4 4 5 1 总结4 4 5 2 展望4 4 参考文献。4 6 致谢5 0 摘要 摘要 s o c ( s y s t e mo i lc h i p ) 把整个电路系统集成在一块芯片上，提高了系统的 性能。但单纯的s o c 缺乏灵活性，一旦需求有所变化就得重新设计芯片，这极 大的增加了开发成本，延长了产品上市时间。在s o c 中嵌入可编程的i p 核可以 给s o c 提供一定的重新配置能力，从而可以改善s o c 灵活性太差的缺点。但 s o c 提供给i p 核的面积资源是十分有限的，这就让可编程i p 核配套的软件系统 更需要考虑如何充分利用这有限的面积资源。 工艺映射是可编程逻辑配套软件系统中的一个重要模块，它用可编程逻辑 中特殊单元替代用户设计的电路逻辑单元，实现等效的逻辑功能，因此工艺映 射建立在可编程逻辑单元结构的基础上。l u t ( l o o ku pt a b l e ) 是可编程逻辑 中使用最广泛的结构之一，针对l u t 结构的工艺映射很有研究意义。工艺映射 都有一定的优化目标，比如面积，延迟，功耗等。嵌入s o c 中i p 核的有限面积 使得面积优化相对其它优化目标来说更加重要。 本文提出了利用模拟退火从全局范围对l u t 结构进行工艺映射的方法，目 的是为了减少等效实现用户设计的电路逻辑所用的l u t 单元个数。实现逻辑所 用l u t 单元个数的减少意味着实现逻辑所用的芯片面积的减少，另外逻辑单元 数目的减少也会在一定程度上减少单元连接之间的接口数目，从而可以缓减可 编程布线资源的压力。 本文所作的贡献在于： 1 提出了一种利用图的深度优先搜索在可编程逻辑器件中处理组合反馈电路的 方法。 2 相对现有的工艺映射算法只从各个局部优化进行映射，本文提出了一种新的 利用模拟退火过程从全局范围考虑问题的方案，实验结果表明这个方法可以 取得更好的优化。 3 提出了一种与映射方案之间建立对应关系的以图论边值为基础的参数模型。 4 提出y $ 1 j 用高级语言的位逻辑运算来进行l u t 单元配置信息生成的方法。 关键词：可编程逻辑工艺映射l u t 模拟退火 一 a b s t r a c t a bs t r a c t s o c ( s y s t e mo nc h i p ) c a ni m p r o v et h ep e r f o r m a n c eo ft h ec i r c u i ts y s t e mb y p u t t i n gt h ew h o l es y s t e mi n t oo n ec h i p b u tp u r es o cd e s i g nl a c k sf l e x i b i l i t y ，e v e na v e r ys m a l lc h a n g eo ft h er e q u i r e m e n tw i l ll e a dt ot h er e d e s i g no ft h ew h o l es y s t e m ， w h i c hi n c r e a s e st h ec o s to ft h ed e v e l o p m e n ta n dp r o l o n g st h et i m et om a r k e t t h e f l e x i b i l i t yo fs o cc a nb ei m p r o v e db ye m b e d d i n gp r o g r a m m a b l ei pc o r ei n t ot h es o c c h i p h o w e v e r ，t h ea r e ap r o v i d e dt ot h ei pc o r ei nt h ew h o l ec h i pi sv e r yl i m i t e d ， w h i c hm a k e sa r e ao p t i m i z a t i o nb e c o m ev e r yi m p o r t a n ti nt h ec o r r e s p o n d i n gs o f t w a r e s y s t e m t e c h n o l o g ym a p p i n gi s a ni m p o r t a n tm o d u l ei nt h e c o r r e s p o n d i n gs o f t w a r e s y s t e m i tu s e st h es p e c i a lp r o g r a m m a b l el o g i cu n i t st or e p l a c et h ec i r c u i t sl o g i c e l e m e n t st or e a l i z et h ee q u i v a l e n tl o g i cf u n c t i o n ，s oi ti sb a s e do i lt h es t r u c t u r eo ft h e p r o g r a m m a b l el o g i cu n i t s i n c el u t ( l o o ku pt a b l e ) i s av e r y p o p u l a r p r o g r a m m a b l el o g i cu n i t ，i ti sv e r yi n s t r u c t i v et os t u d yt e c h n o l o g ym a p p i n ga l g o r i t h m o ft h i ss t r u c t u r e t e c h n o l o g ym a p p i n gh a si t so p t i m i z a t i o no b je c t i v e ss u c ha sa r e a ， d e l a ya n dp o w e re t c l i m i t e da r e ai n t h e p r o g r a m m a b l e i pc o r em a k e sa r e a o p t i m i z a t i o nm o r ei m p o r t a n tt h a no t h e ro p t i m i z a t i o n si n t h et e c h n o l o g ym a p p i n g p r o c e s s o t h e rt h a n c o n s i d e r i n gt e c h n o l o g ym a p p i n gp r o b l e ml o c a l l y a s p r e v i o u s h e u r i s t i ca l g o r i t h md i d ，t h i st h e s i sc o n s i d e r st h ep r o b l e mg l o b a l l yb yu s i n gs i m u l a t e d a n n e a l i n gp r o c e s sa n dp r e s e n t sat e c h n o l o g ym a p p i n ga l g o r i t h ms a - m a pt o w a r d l u ts t r u c t u r ew i t ht h eo b j e c t i v eo fa r e ao p t i m i z a t i o n a r e ao p t i m i z a t i o nw i l lr e d u c e t h en u m b e ro fp r o g r a m m a b l el o g i cu n i t su s e dt o i m p l e m e n tt h ee q u i v a l e n tl o g i c f u n c t i o no ft h ed e s i g n e dc i r c u i t s ，w h i c hn o to n l yd e c r e a s e st h ea r e au s e db yt h e r e q u i r e dp r o g r a m m a b l eu n i t s ，b u tm a k e si te a s i e rt or o u t eb e t w e e nt h ep r o g r a m m a b l e u n i t ss i n c ef e w e ru n i t sm e a n sf e w e rt o t a li n t e r f a c e s t h ec o n t r i b u t i o no ft h i st h e s i s ： 1 p r e s e n t sam e t h o dt od e a lw i t hc i r c u i t sw i t hc o m b i n a t i o n a ll o g i cf e e d b a c k 2 c o n s i d e r st h et e c h n o l o g ym a p p i n gp r o b l e mg l o b a l l ya n dp r e s e n t san e wa l g o r i t h m 3 p r e s e n t sa ne d g e b a s e dm o d u l et ob r i d g ee d g e sa n dm a p p i n gs o l u t i o n s 4 p r e s e n t sam e t h o dt o p r o d u c e l u tc o n f i g u r ei n f o r m a t i o n b yu t i l i z i n g b i t o p e r a t i o n k e y w o r d s ：p r o g r a m m a b l el o g i c ；t e c h n o l o g ym a p p i n g ；l u t ；s i m u l a t e da n n e a l i n g 第一章引言 第一章引言 1 1 可编程逻辑器件软件系统 利用可编程逻辑器件开发产品可以降低开发费用，缩短产品开发周期，并 且拥有功能可改变性，正是由于这些特点，它得到了越来越广泛的应用。可编 程逻辑器件从硬件上看一般包括可编程逻辑单元，可编程布线资源和输入输出 单元3 部分。一个电子系统在可编程逻辑器件上进行实现需要把这些硬件资源 进行合理的配置，正确的配置信息是由可编程逻辑器件配套的软件系统根据用 户的设计输入来实现的。 图1 1 可编程逻辑的设计流程 第一章引言 可编程逻辑设计流程( 如图1 1 所示) 的各个步骤都需要有软件的支持， 在可编程逻辑器件的配套软件系统中，一般包括设计输入( 包括原理图输入、 v h d l 输入、状态图输入等) 、逻辑综合、功能模拟、工艺映射、布局、布 线、时序验证、编程下载等模块。利用软件系统设计时，一般用户所要做的只 是选择合适的输入方法进行正确的系统设计，加上系统所要求的约束条件，就 能够使设计的系统在可编程逻辑器件上实现，软件系统的自动化程度很高。但 有的熟练用户可能希望能更多地介入设计控制，以设计出高性能、高利用率的 芯片，因此集成的开发环境也设有控制开关供设计人员干预设计过程，比如在 x i l i n xi s e x i l i 等软件系统中就可以对布局，布线过程进行手工控制。 在这些模块中，功能仿真检查设计的逻辑正确性；逻辑综合把输入的设计 转化为门级网表。门级网表一般包含有基本的逻辑门( 比如与门、或门) 和基 本的时序元件( 比如d 触发器) ，但现在有些软件系统对逻辑综合过程进行了 特殊处理，它在这个过程中可以综合出比较优化的在可编程逻辑器件中的特殊 元件，这种处理可以使芯片的性能更加优化。 工艺映射是利用可编程逻辑设计系统的一个特有的步骤，它用可编程逻辑 器件中特有的可编程逻辑单元来替代逻辑综合步骤中得到的门级逻辑元件，使 替代后的逻辑功能不作任何改变。逻辑综合出来的网表中的元件主要是基本逻 辑门，但在可编程器件中并没有这些逻辑门单元来直接实现它们的功能。可编 程逻辑器件的其中一个组成部分是可编程逻辑单元，这些单元可以编程实现一 定的逻辑功能，工艺映射就是对这些可编程逻辑单元进行适当的编程，把门级 网表分块到各个可编程逻辑单元之中。工艺映射很多算法，它们一方面是针对 不同逻辑结构的算法，另外方面是针对同一种逻辑结构但不同优化目标而提 出的算法。 布局阶段将工艺映射产生的各个可编程逻辑单元放到适当的位置。工艺映 射完成后般需要用多个可编程逻辑单元来实现一个系统的设计，在一个可编 程逻辑器件中如何合理的放置这些可编程逻辑单元就是布局所要做的工作。在 布局过程中一般有约束条件驱动，比如可编程逻辑器件的可编程布线资源是有 限的，因此布局可以把布通率作为优化目标。 在布局完成后，芯片中放置了合理布局的各个可编程逻辑单元，但这些可 编程逻辑单元并不是孤立的，它们实际上是一个有机的整体，因此需要把这些 一 第一章引言 可编程逻辑单元按照需要进行连接，这是布线模块该完成的工作。在可编程器 件中含有可编程布线资源，布线资源中有编程开关，对这些开关进行编程就可 以取得所需要的走线。 在布线完成后，所设计系统的时延信息才能真正确定，目前很多设计都有 时延方面的约束，所以在布线完成后，一般的软件系统都可以提供时序验证的 功能，验证时序是否可以符合要求，如果不能符合要求则需要对设计本身或者 设计流程步骤进行更改。 在时序验证完成后，进行的是编程下载工作，前面步骤中的可编程逻辑单 元的编程，可编程布线资源的编程等都将产生一定的配置信息，只有把这些信 息放入到可编程器件中才能让它真正工作。编程下载模块将编程信息固化在可 编程逻辑器件的某种存储介质上。 1 2 工艺映射算法的发展 可编程逻辑单元是可编程逻辑器件中的核心部分，它一般含有两部分，一 部分用来编程实现组合逻辑功能，另一部分用来实现时序相关的逻辑功能。比 如在x i l i n x 4 0 0 0 系列 x i l i 中的一个逻辑单元结构( 图1 2 ) 中，有三个被称为 函数发生器的模块用来编程实现组合逻辑；后面的两个触发器可以被编程为d 触发器或者锁存器，用来实现时序相关的逻辑。 图1 2x i l i n x 4 0 0 0 系列可编程逻辑单元结构 第一章引言 工艺映射模块使用可编程逻辑单元的结构去替代综合后的门级网表实现等 效的逻辑功能。它在处理问题时一般先把综合产生的门级网表进行分类，把整 个网表分为组合逻辑部分和时序逻辑部分：网表中的组合逻辑部分通过一定的 算法用可编程逻辑单元中可以编程为组合逻辑的模块去替代实现；在综合后网 表的组合逻辑部分被可编程逻辑单元中的特殊逻辑替代完成后，再把这些特殊 逻辑和综合后网表中的时序逻辑一起结合放入到整个可编程逻辑单元之中完成 工艺映射过程。在这些过程中，最为关键研究最多的是如何用可编程逻辑单元 中的可编程组合逻辑部分去有效的替代综合产生的组合部分逻辑网表，它对系 统实现后的性能有着决定性的作用。关于把映射完成的组合逻辑和时序逻辑结 合到可编程逻辑单元这个过程，被称为p a c k ，有专门的p a c k 算法研究，比 如v p a c k b e t z 9 7 、r p a c k b o z 0 0 1 。学术上提及的“工艺映射算法 仅仅 指组合逻辑部分的替代，对于可编程逻辑单元中的时序可编程部分并不关注， 本文中所说的工艺映射算法研究的也是指可编程的组合逻辑部分，而以下“可 编程逻辑单元 所指的也只是整个可编程逻辑单元中的可编程的组合逻辑。 自从8 0 年代可编程逻辑器件的产生开始，就有了工艺映射算法的研究。工 艺映射算法有结构的针对性，各个可编程逻辑器件生产厂商采用的结构有所不 同，比如a c t e l a c t e l 采用了m u x 的逻辑单元结构；x i l i n x x i l i 主要基于 l l r r 的结构；而a l t e r a a l t e 贝l j 采取了可编程与或阵列的结构。不同的结构使 得产生了不同的工艺映射算法，比如a m a p k a r p 9 1 】、a c t i o n g u n t 0 0 等 算法针对m u x 结构；f l o w m a p c o n g 9 4 、p r a e t o r c o n g 9 9 等针对l 的结构； c i e s 9 2 】、 s h i h 0 2 等是与或阵列的工艺映射算法；现在还有混合结 构逻辑器件的产生，因此也诞生了与之相应的工艺映射算法 w e n 0 4 。 工艺映射有一定的优化目标，比如 d e t j 8 7 】、c h o r t l e f r a n 9 1 】、 p r a e t o r c o n g 9 9 等为了实现面积优化，也就是减少实现综合后网表逻辑功 能所用的可编程逻辑单元数目，这个优化目标对于集成度不高或者可编程逻辑 资源较少的场合有重要意义；用可编程器件进行系统设计相对于a s i c ( a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t ) 设计的其中一个缺点是速度相对较慢， 有的工艺映射算法d a g m a p c h e n 9 2 、f l o w m a p c o n g 9 4 等为了弥补这个 缺点，就把时延优化作为它的目标，使得映射后可编程逻辑单元组成的网表中 的级数尽量少：在可编程逻辑器件的硬件资源中，布线资源占用了整个芯片的 - 第一章引言 大部分面积，因此连线布通率是可编程器件实现逻辑的重大挑战之一，为了取 得较高的布通率产生了以布局、布线为驱动的工艺映射算法 s c h l 9 4 、 t o g a 9 8 ；现在便携式电子设备很为流行，困扰便携式设备的一个重大问题是 设备的功耗问题，目前低功耗问题被广泛关注，在工艺映射领域也产生了不少 降低功耗的算法研究 a n d e r 0 2 、 c h e n 0 4 ，功耗优化是目前工艺映射算法研 究的主流；另外还有其它优化目标工艺映射算法的提出比如有针对可测性而提 出的算法 p o m e 9 4 等。 1 3 可编程ip 核 现在s o p c ( s y s t e mo np r a g r a m m a b l ec h i p ) 的发展日益成为重要的潮流， 它的一种实现方案是在s o c 中嵌入可编程i p 核，从而给s o c 提供了可重配置 的功能，提高s o c 的灵活性。这种灵活性在很多领域得到应用：芯片厂家可以 用同一种嵌入可编程i p 核的芯片方便的提供不同特性的产品，满足不同用户需 要；可以把芯片中的i p 核部分作为芯片的测试单元，根据测试需要下载不同的 测试电路就能方便的测试芯片；芯片的需求经常会产生一些微小的变化，利用 可编程i p 核可以快速的实现这些变化，从而避免重新开发芯片付出的高昂成本 和极长的产品再开发周期。 相对普通的可编程逻辑器件而言，s o p c 中嵌入i p 核的可编程逻辑资源非 常有限，怎样利用有限的资源实现尽量多的逻辑功能是待解决的一个重大问 题，这让对可编程i p 核的工艺映射过程中更需要考虑面积优化。另外面积优化 的目标减少了实现设计可编程逻辑单元数目，也就减少了单元之间的接口数 目，所以对提高连线布通率也会有很大的帮助。 1 4 工作重点 现有的工艺映射算法没有提出含有反馈的组合逻辑( 其实构成了异步时序 电路) 的处理办法，因而不能直接对这类电路进行处理。本文的工作之一是： 提出了这类问题的一个解决办法：先利用图深度优先搜索断开电路中的反馈 ( 在断开反馈时保留原来的连接信息) ，使得处理后的电路能够利用已有的工 第一章引言 艺映射算法进行映射，而原来的连接信息可以方便的在布线阶段进行恢复，从 而实现原来电路的逻辑功能。 在芯片中嵌入可编程i p 核实现s o p c 的做法提供给可编程i p 核的面积资源 是十分有限的。相对一般的可编程逻辑器件而言，在对这些i p 核进行工艺映射 时更需要考虑的是面积优化，也就是减少实现电路逻辑能的可编程逻辑单元数 目：减少编程使用的可编程逻辑单元数目不仅可以有效的减小所需的芯片面 积；另外较少的逻辑单元数目意味着较少的单元间接口，因此它还能缓减布线 资源的需求。 逻辑网表的面积优化在输入端大于3 的l u t 下映射是个n p 问题 【f a r r a 9 4 ，现在已有的算法采用的都是启发式算法，只是从各个局部去实现 优化目标，但启发式算法的一个缺点是容易把结果定位在局部的优化解。 本文的工作重点之二是：针对l u t 结构提出了一种基于退火过程的工艺映 射算法s a m a p ，从全局范围对整个网表的映射进行面积的优化，实验结果表 明s a m a p 可以得出很好的优化映射结果。 第二章研究背景 第二章研究背景 2 1 可编程逻辑单元结构 工艺映射算法的基础是可编程逻辑单元的具体结构，不同的逻辑单元结 构需要不同的工艺映射算法去完成映射工作，下面将简要介绍一下逻辑单元的 常用结构以及一般采用的映射算法。 2 1 1 选择器( m u x ) 结构 选择器结构主要被a c t e l a c t e l 】公司所采用，比如a c t 一1 、a c t 2 、 4 0 m x 、4 2 m x 等产品。图2 1 是a c t 1 的可编程组合逻辑结构，在结构中有八 个输入端和一个输出端。通过输入端的不同组合，这种结构能够实现四种基本 的逻辑函数( n a 卜d ，a n d ，o r 及n o r ) ，其中包括任意二输入的函数，大 部分三输入函数和部分四八输入函数，总共可实现7 0 2 种逻辑函数。 选择器结构的可编程逻辑单元占用的硬件面积小，实现逻辑的速度较快， 但是它可以实现的逻辑功能相对其它结构而言也相对较弱。 对选择器结构工艺映射算法研究的时间比较早，比较早的算法比如 d e t j 8 7 、 k e u t 8 7 首先建立以图为基础的单元库，再用单元库匹配的去覆盖 综合后得到的电路网表：【m a i l 9 0 、【s c h 9 3 改变了用 图作为单元库基础的做法，而是把布尔代数作为单元库 的基础进行综合后网表的匹配映射；a m a p k a r p 9 1 采 用一种类似c 语言形式的i f - t h e n e l s e 语句对综合后网表 进行描述，再把它转化到m u x 的可编程逻辑单元结构 中：a c t i o n 【g u n t 0 0 、 m a r i k 0 4 $ l j 用b d d ( b i n a r y d e c i s i o nd i a g r a m s ) 建模综合后网表进行工艺映射，采用 b d d 模型是现在对选择器单元结构进行工艺映射的常用 方法。 图2 1a c t 一1 中 采用的逻辑结构 第二章研究背景 2 1 2 查询表( l u t ) 结构 l u t 是最常用的一种可编程逻辑单元结构，对于k 个输入端的l u t ，它可以实 现任何输入端数目不超过k ，输出端数目为1 的组合逻辑函数。它实际上是一个 多输入单输出的r a m ，对于一个k 输入的l u t 单元，它的输入端充当了2 xb i t s 容 量的r a m 的地址线。一个k 输入单输出的组合逻辑函数，它的真值表对应了2 k 种 不同的情况，对l u t 的2 置b i t s 单元根据组合逻辑函数的真值表进行编程，就可 以用这k 个地址线寻址得到和组合逻辑函数对应的逻辑输出值，因此说一个k 输 入的l u t 可以实现任何不超过k 个输入单输出的组合逻辑函数。图2 2 是一个电路 以及对应的l u t 的编程示例。针对l u t 结构的工艺映射算法，l u t 输入端数目是 它的一个约束条件。 ( a ，b ，c ) l0 ( 0 ，0 ，0 ) ( 0 ，0 ，1 ) ( 0 ，1 。0 ) ( 0 ，1 ，1 ) ( 1 ，0 ，0 ) ( 1 ，0 ，1 ) ( 1 ，1 ，0 ) ( 1 ，1 ，1 ) 霞。j0 。一。 9 t1 ： ：0 ，。 i1 ；0。= i 、 1 1： 巍，1 、一 图2 2l u t 编程示例 基于l u t 的结构的可编程逻辑单元功能非常灵活，功能也比较强大，被很 多可编程逻辑产品所广泛应用。 l u t 结构的工艺映射算法有很多研究，关于这个结构的映射算法介绍将在 本章后面的2 2 节再作介绍。 2 1 3 与或阵列( p l a l i k e ) 结构 a l t e r a a l t e 公司的很多产品都采用了类似p l a 的与或阵列作为它的基本单 元，比如m a x 7 0 0 0 系列产品。这种结构可以用图2 3 来表示，图中的“”表示编 程开关。它有1 个输入端，每个输入端都有本身以及取反后的输入，前面部分是 1 0 第二章研究背景 一个可编程的与阵列，可以组成任何想要的乘积项，在某个特定的与或可编程 逻辑单元中，它容许产生的不同乘积项的个数是一定的，比如图中容许产生的 不同乘积项个数是p 个；在这个结构中，还存在一个或阵列，可以将前面与阵列 产生的不同乘积项相或。任何一个组合逻辑函数总是可以写成2 级逻辑结构，即 最小项相或的形式，因此只要待实现的组合逻辑函数的输入端个数不超过1 个， 最小项的数目不超过p 个，并且输出端个数不超过0 个，它的逻辑功能就可以用 图2 3 的结构来等效实现。对与或阵列结构的可编程逻辑单元，通常用( i ，p ，0 ) 这三个参数来描述，它们分别表示输入端，容许的乘积项和输出端的数目。多 个输出端及乘积项数目的限制是这种结构和l u t 结构的两个不同之处。 ii n p u t s 图2 3 与或阵列结构 o o u t p u t s 屯 屯 z = 2 宏 ： 皇 与或阵列逻辑单元结构可实现的逻辑功能复杂，所占面积也较大，有利于 实现高输入的函数，在应用上适合于状态机、译码电路等控制逻辑。 早先使用的针对p l a 结构的工艺映射算法 c i e s 9 2 考虑了p l a 是与或阵列 的特性，利用两级逻辑化简来完成映射过程；但随着p l a 规模的增大，两级逻 辑化简解决这个问题的效率很低，于是出现了新的算法，t e m p l a a n d e r 9 8 】 中提出的先把综合后网表分解为树的组合，把每棵树映射到p l a 中，然后加以 组合同时进行p l a 的合并优化操作；【s h i h 0 2 先把综合后网表映射到l u t 中，然后对映射生成的l u t 转换到p l a 中，在这基础上进行p l a 的合并优化 操作。对于p l a 结构的工艺映射，乘积项数目的限制使得算法相对于l u t 的 结构有更大的难度。 第二章研究背景 2 1 4 混合逻辑( h y b r i d ) 结构 目前，已经有些可编程逻辑产品不是单单采用某一种特定的逻辑结构，而 是采用几种基本结构相结合来设计可编程逻辑单元结构，比如由复旦大学研制 的f d p i o o k m a 0 4 采用t m u x 和l u t 相结合的逻辑单元( 见图2 4 ) 和 k a v l 9 9 】中 提出得h f p a ( h y b r i df i e i dp r o g r a m m a b l ea r c h i t e c t u r e ) 结构( 见图2 5 ) 。 b l o c k 1 e v e l2 l i t r a c k s 1 i r 1 6 p a l b i i n p u t s + 图2 4f d p 单元结构 8 0c l u s t e r l e v e lt r a c k s 卜 jl l u t b 8l u t b s l 听b 1 、 l p a 量_ b 8p a l b s p a l b 1r 图2 5h f p a 结构示例 第二章研究背景 采用混合的方式有时可以利用不同单元结构的各自特点使得在特定场合下 逻辑功能的实现更为有效。 混合结构的工艺映射算法根据结构的不同方式有所不同，比如对于f d p 结构 的工艺映射采用的是一种利用两级逻辑化减的方法 w e n 0 4 。 2 2l u t 结构工艺映射算法 l u t 结构能够实现强大的逻辑功能，可单独作为组合逻辑的可编程单元， 也容易和其它结构共同完成组合逻辑部分的编程，它应用的灵活性以及强大的 功能使它得到非常广泛的应用。其它结构的有些工艺映射算法比如 s h i h 0 2 是 建立在l u t 结构映射算法基础上的，因此对l u t 结构的工艺映射算法很具有 研究价值，目前已经有不少l u t 结构的工艺映射算法，下面将对这种结构映 射的一些具有代表性的算法作些介绍，在这之前，先介绍和算法相关的模型和 术语。 2 2 1 映射的有向图模型 组合逻辑电路可以用d a g 1 ( d i r e c t e da c y c l i cg r a p h ) 进行描述： 另：( y ，三) ，v 表示原始输入、输出端和电路内部逻辑单元的集合。当节点“的 输出是节点1 ，的输入时，存在有向边e ( u ，1 ，) ，其中节点u 称为边e 。的始节点，v 称为边；的终结点：原始输入端节点没有输入边，而原始输出端节点没有输出 边；如果图中任何一个节点的输出边数目不超过1 ，则称这个图为自由扇出 ( f a n o u t f r e e ) 的；对于节点，v ，用i n p u t ( v ) 表示给节点v 提供输入边的节点 集合，即： i n p u t ( v ) = u vle ( u ，v ) e ) 例如图2 6 中给节点v 2 提供输入边的节点集合可以表示为：i n p u t ( v 2 ) = 6 ，v 1 ) 。 同样对于一个节点子集飚v ，用i n p u t ( v s ) 表示集合( 矿一v s ) 2 中给v s 内 的节点提供输入边的节点集合，也就是： ( 1 )对于存在环路的组合电路，将在第三章中介绍变为d a g 模型的方法 ( 2 ) 本文用“一来表示集合的运算爿一b 表示两集合a n b 的运算 第二章研究背景 i n p u t ( v s ) = ule ( u ，v ) e ，u ( v v s ) a n d1 ，i s ) 比如图2 6 中的子集 u ，v 5 ，) 为例，给这个子集提供输入边的节点集合为： i n p u t ( v 4 ，v 5 ，屹 ) = 口，v 2 ，v 3 ) 。 对于节点u v ，有类似的定义o u t p u t ( u ) ，它表示和结点u 输出边相连的节 点集合，可以表示为： o u t p u t ( u ) = v ve ( u ，) e ) 比如在图2 6 中o u t p u t ( v , ) = v 4 ，v 5 ) 。 玎用来特别表示电路内部逻辑节点的集合： v i = 1 ，刚i n p u t ( v ) i ( 3 ) 0a n dl o u t p u t ( v ) | 0 ) 图2 6 中的内部逻辑节点集合为：i = v l , v 2 ，v 3 ，屹，v 5 ，v 6 ) 。 在节点u 和节点1 ，之间如果存在一条从u 到v 有向路径，称节点u 为节点1 ， 的前驱节点，而节点v 被称为节点u 的后继节点，比如图2 6 中的节点m 和屹都 是节点v 5 的前驱节点，v 5 是v 1 和1 ，：的后继节点；v 是由节点1 ，节点1 ，的所有 前驱节点以及所有这些节点之间连接边组成的子图，比如图2 6 子图虬的节点 集合为 c ，d ，e ，v l ，v 3 ) ，而它的边集合为 p ( c ，m ) ，e ( d ，m ) ，p ( h ，y 3 ) ，e ( e ，屹) 。 锥集( c o n e ) c = v 1v 2 v o v k 是电路内部逻辑节点集合v 的一个子集， 它满足可以找到一个特殊节点v o c ，使锥集c 中的其它任何节点 v ( c 一 心) ) 总能找到一条从v i 到屹的路径，并且路径上经过的所有节点都在 锥集c 之中。由于锥集中存在着一个特殊节点，可以用它来辅助标记某个锥 集，以匕为特殊节点的锥集记为c 。如果l 却甜f ( c 屹) l 1 ) 但在实验过程中发现，先接受非法的映射方案的做法只是延长了程序的执行时 间，而对映射结果却没什么改进，因此舍弃了接受非法映射的做法。在s a m a p 中，当某条边的值的改变引起非法映射时，将会用随机函数重新选取另外 的边进行值的改变。 1 o 图4 64 输入l u t 映射下非法映射产生示例 理论上模拟退火算法在每一个特定的温度下需要通过足够的变化，以达到 准平衡状态，前面讲过足够多的变换将会导致运行时间的指数增长。在s a - m a p 里，每一个特定温度下，如果产生的新状态被接受，那么这个温度下的变 换就结束；如果产生的新状态没有被接受，则继续在该温度下进行新状态的产 生，当变换次数达到1 0 次仍然没有被接受，则也终止该温度下的变换而进入温 度的调节步骤。 4 4 4 状态接受判断 s a - m a p 采用b o l t z m a n n 测试来判断是否接受新产生的状态： e x p 整丝乒业业 占， 1 k + l 第四章s a - m a p 算法 其中占【o ，1 ) ，它由随机函数来产生；c ( m 川) 表示新状态对应的映射方案中的 l u t 单元数目；c ( m k ) 表示当前状态对应的映射方案中的目标函数值；正+ ，为 当前的温度值。从这个测试函数可以知道，如果新产生映射方案中的l u t 单元 的个数比当前状态映射方案的l u t 单元数目更少时，表达式肯定成立，也就是 说当新的映射方案比当前状态使用更少的单元数目时将用新的状态替代当前状 态，在新状态基础上继续退火过程；如果新的映射方案比当前方案用了更多的 单元数目，测试表达式也还是有一定概率成立，这就说明算法有一定概率接受 比原来更差的解，接受更差的方案正是模拟退火算法相对于其它启发式算法的 优越之处，使得它能够以一定概率跳出局部的优化状态。从测试表达式还可以 知道，在温度较高时比当前状态差的新状态比较容易被接受，当温度很小时接 受更差解的概率也很小，而那时的解应该已经是相对优化的解了。 4 4 5 温度控制 温度参数是模拟退火算法中最关键的参数之一，主要包括初始温度的选 取，温度的下降方法和退出模拟退火的停止温度。 从理论上来说，起始温度应该保证平稳分布中每一个状态的概率相等，但 这个温度值很难计算出来，如果温度取得太大，会导致退火时间过长，取得太 d , 贝j j 使算法过早陷入局部最优解，考虑到解的优化性，实际操作中一般会把初 始温度取的相对较大。在s a m a p 中，退火的初始温度取为初始解中的l u t 单元个数。温度确定为初始映射方案的l u t 单元个数具有一定的合理性，如果 初始映射方案中的l u t 单元数目较多，说明电路的规模相应较大，充分逼近全 局优化需要进行的搜索也就会相应的增多，而大的初始温度使得温度下降到退 出温度所经历的温度状态数也就越多，可以为更多的搜索提供条件；如果初始 映射的l u t 单元数目不大，这个网表的规模很有可能也是相应的较小，解空间 的范围也就相应少些，需要进行的搜索次数也就可以少些，小的初始温度让达 到温度的退出状态所需的状态数也少些，这样在不损失解优化性的前提下可以 加快算法的执行时间。 s a m a p 的温度下降采用分段式正比例因子衰减的方法： 正+ 1 = 口互 第四章s a - m a p 算法 其中口是衰减系数，当瓦1 0 0 时口取值为o 8 ；当瓦 1 0 0 时口的值为0 9 9 5 。 在实验过程中发现，在退火的初始阶段基本上任何新状态都会被接受，这个阶 段对于结果的优化程度影响相对小些，因此让温度在初始阶段较快程度的下 降；在退火到达后面阶段时，为了让状态尽量接近准平衡，温度下降速度应该 慢一些。在确定分段的正比例衰减方案后，具体的衰减因子由试验得出。 理论要求温度下降到零，整个系统以概率1 收敛全局最优。实际操作中当 温度下降到一定程度后就认为系统已经达到了很高的优化程度，在这基础上很 难取得更好的优化，算法继续执行的意义也就不是很大，会退出算法的执行。 s a m a p 里设置了退出算法的温度为0 0 0 1 ，因为新的映射方案和原来方案之间 相差的单元数目是整数，在温度为0 0 0 1 时如果新状态比原来状态更差，则通 过e 指数运算得出的结果很难再大于随机函数产生的 1 ，0 ) 随机数，所以可以认 为温度o 0 0 1 已经是足够低了。 4 4 6 结束退火条件 s a m a p 结束退火的条件有以下四个： 1 产生的新状态总数达到9 9 9 9 9 。新状态的次数和产生的边值变化的总数有所 区别，当边值变化导致非法映射方案时，那次的边值变化并不引起新状态产 生次数的增加。 2 温度下降到0 0 0 1 ，这个条件已经在3 4 5 节有所说明。 3 连续产生非法映射方案的次数达到1 0 0 次。 4 连续产生不被接受的新状态数目达到1 0 0 0 次。 4 5 映射方案生成 s a m a p 建立了边的取值和映射方案之间的一种对应关系，通过模拟退火 算法对边的取值进行调整，最后确定边值的分配方案之后，可以用图4 7 中的 方法得到映射方案： 第四章s a - m a p 算法 a l g o r i t h mg e t _ m a p p i n g c = 存放锥集的集合置空 m = 矽映射方案置空 n = ul e ( u ，v ) e ，i o u w u t ( v ) 0 ) 和原始输出端相连的节点放入集合v w h i l en 西d o r e m o v ean o d evf r o mna n dm a r kya sp r o c e s s e d c r e a t eac o n ee 建立一个以y 为特殊节点的锥集 b a c k t r a c ef r o myi na l lp o s s i b l ep a t h s 向着原始输入节点回朔 u n t i lm e e t i n ge d g ew ( e ( s ，r ) ) = l i fn o d esi sa nu n p r o c e s s e dn o n - i n p u tn o d e | t h e n p u tsi n t on e n di f p u ta l lt h en o d e si nt h ep a t h si n t oc o n ee c = c uc v e n dw h i l e f o re a c hc o n ec v c ，d o a d da ne l e m e n tl vi n t ot h em a p p i n gp l a nm e n df o r e n da l g o r i t h m 图4 7 映射方案生成伪代码 这个过程先为每一个输出的逻辑门都各自建立一个锥集，然后从该输出逻 辑门开始从各种可能的路径向着输入端搜索，直到这些路径上都碰到值为l 的 边，搜索停止后扩充该输出逻辑门位于的锥集，把搜索路径上边值为0 的边的 两个端的节点连同终止搜索的