（微电子学与固体电子学专业论文）现场可编程门阵列的布局软件开发.pdf

摘要 现场可编程门阵列( f p g a ) 是八十年代中期出现的新型可编程逻辑器件。 通过编程，可以把一个通用的可编程逻辑器件配置成为用户需要的硬件数字电 路，从而大大加快电路产品的研发周期，降低研发成本，缩短电子产品的上市时 间。其可重配置的灵活能力提供了将同一芯片用到不同领域中去的机会，尤其适 用于不断变化的产品开发，例如通讯和网络芯片，有效地缩短了产品的开发和上 市时间，并降低了产品的升级成本。 一套高效的c a d 系统是使用f p g a 的基础。f p g a 可编程结构的灵活性， 对相应的c a d 系统提出了巨大的挑战。 在对布线软件中布线资源图研究的基础上，并且根据运行国际经典软件的工 作经验，本论文对f p g a 的详细布线资源结构进行了深入的研究：本论文根据 f p g a 的详细布线资源结构建立了带总线及大块s r a m 的f p g a 芯片结构模型， 该模型能够给f p g a 布局和布线软件提供必要的f p g a 详细布线资源信息；此 外，本论文在复杂网表电路中对三态门、总线和大r a m 建立元器件模型。 本论文对适用于f p g a 的布局软件进行研究，基于所建立的f p g a 模型，本 论文改进了模拟遇火算法，从而使得布局软件能够支持带总线和多个大s r a m 的复杂网表在f p g a 中的布局，完成了宏模块和简单模块的混合布局，以及满足 了用户对布局提出的位置限制要求：本文提出几个布局目标函数，目的是探索提 高布局布线软件中的布通率的方法。 关键词：现场可编程门阵列，布图、布局，布线 a b s t r a c t f i e l d p r o g r a m m a b l eg a t ea r r a y ( f p g a ) ，an e wp r o g r a m m a b l el o g i cd e v i c e ，w a s i n t r o d u c e di nt h em i d - t e r mo f t h e1 9 8 0 s t h ep r o g r a m m i n gc a nc o n f i g u r eau n i v e r s a l p l dt ob e c o m et h ed i g i t a lc i r c u i tr e q u i r e db yu s e r s ，s oa st os p e e dt h er & dc y c l e g r e a t l y ，r e d u c e t h en r e ( n o n r e c u r r i n g e n g i n e e r i n g ) c o s t ，d e c r e a s e t h e t i m e t o - m a r k e t c o s to fe l e c t r o n i c p r o d u c t s t h e f l e x i b l e c a p a b i l i t y o f r e - c o n f i g u r a b i l i t yp r o v i d e st h eo p p o r t u n i t yt h a to n ec h i pc a l lb ea p p l i c a b l et od i f f e r e n t u s e s ，e s p e c i a l l ys u i t a b l ef o rd i f f e r e n tp r o d u c td e v e l o p m e n t ，s u c hc o m m u n i c a t i o na n d i n t e r n e tc h i p s a ne f f i c i e n tc a d s y s t e mi st h eb a s i sf o ru s i n gf p g a t h ef l e x i b i l i t yo ff p g a b r i n g sa b o u tm a n yc h a l l e n g e st oi t sc o r r e s p o n d i n gc a ds y s t e m b a s e do nt h er e s e a r c ho ft h er o u t i n gr e s o u r c eg r a p hi nr o u t i n gs o f t w a r e ，a n d a c c o r d i n gt ot h ew o r ke x p e r i e n c eo fn m n i n gt y p i c a ls o f t w a r ei nt h ew o r l d ，t h et h e s i s i n v e s t i g a t ed e e p l yt h ed e t a i l e dr o u t i n gr e s o u r c ef o rf p g a ；t h et h e s i sb u i l d st h e f p g ac h i pm o d e lb a s e do nt h ef p g ar o u t i n gr e s o u r c es t r u c t u r e ，b e i n gc a p a b l et o p r o v i d et h en e c e s s a r yi n f o r m a t i o no fr o u t i n gr e s o u r c ef o rf p g ap l a c e m e n ta n d r o u t i n gs o f t w a r e ；b e s i d e s ，t h et h e s i sb u i l d sd e v i c em o d u l e sf o rt r i g a t e s ，b u s e s ，b i g r a m si nc o m p l e xc i r c u i t s t h et h e s i ss t u d i e sp l a c e m e n ts o f t w a r ea p p l i c a b l ef o rf p g a ，a n do nt h eb a s i so f m o d e l sb u i l t ，t h et h e s i se n h a n c e sa n n e a l i n gs i m u l a t e da l g o r i t h mt o s u p p o r t t h e p l a c e m e n to fc o m p l e xc i r c u i t sw i t hb u s e sa n dm u l t i p l eb u s e si nf p g a ，c o m p l e t et h e m i x - p l a c e m e n t o fm a c r o - m o d u l e sa n ds i m p l em o d u l e s ；s a t i s f i e st h ep o s i t i o n c o n s t r a i n tr e q u i r e m e n tb yu s e r s ；t h et h e s i sp r o p o s e ss e v e r a lp l a c e m e n tc o s tf u n c t i o n ， s oa st oe x p l o r et h em e t h o d o l o g yo fi n c r e a s i n gt h er o u t a b i l i t yi np l a c e m e n ta n d r o u t i n gs o f t w a r e k e y w o r d s ：f p g a ，p & r ，p l a c e m e n t ，r o u t i n g 第一章引言 1 1 可编程逻辑器件背景知识 在7 0 年代，出现了早期的基于与或阵列的可编程逻辑器件( 简称p l d ) f h u a n g 9 7 。这种可编程逻辑器件的结构简单，只能实现用少量的乘积项来 表示的小规模逻辑电路。1 9 8 4 年，a l t e r a 公司 a l t e 采用c m o s 的e p r o m 工艺，研制了首块可擦写的可编程逻辑器件( 称为e p l d ) ，它可用紫外线擦 除并重复编程。1 9 8 5 年l a t t i c e 公司 l a t t 用e e p r o m 工艺研制出电可擦除 的可编程逻辑器件g a l ( 通用逻辑阵列) ，它具有设计灵活、高速、低功耗、 改写迅速方便的特点，成为当时的一种常用工业标准器件之一。 x i l i n x 公司x i l i 于1 9 8 5 年推出了首块现场可编程门阵列f p g a ( f i e l d p r o g r a m m a b l eg a t ea r r a y ) 。它结合了p l d 的可编程性和掩模可编程门阵列 ( m p g a ) 的通用连线结构，使得可编程器件具有较高的逻辑密度。f p g a 中 的基本单元电路、输入输出单元和连线通过编程单元加以定义，其编程方法分 为一次性可编程f p g a 和可重复编程f p g a ，前者采用了反熔丝的技术，其原 始状态为断开，编程后将需要的连接点接通。可重复编程的f p g a 采用了 s r a m 的技术，在编程时将结构数据写入s r a m ，可反复使用，掉电后s r a m 的数据丢失，在每次上电时必须将数据重新写n 。 a s i c 0 3 。其后，各公司又相 继推出了各种功能强劲的f p g a 系列产品。 在总体结构上，f p g a 是逻辑门级的可编程，c p l d 是逻辑块级的可编程。 不过f p g a 和c p l d 各自的结构在发展过程中相互取长补短，界限越来越模糊， 且均类属于可编程器件。 1 2 可编程逻辑器件c a d 系统 可编程逻辑器件的设计流程一般包括设计输入( 包括原理图输入、v h d l 或 者v e r i l o g 输入、状态图输入等) 、综合、功能仿真、映射、划分、打包、布局、 布线、时序分析和验证、图形显示、生成位流文件和编程下载等过程( 如图1 - l 所示) 。 图1 - 1 可编程逻辑器件设计流程 通过输入原理图，或者写h d l 代码，设计电路；之后进行功能仿真；用第 三方软件进行综合，实现从电路行为到逻辑结构的转换，例如d c 和s y n p l i f y 软 件都可以综合，对特定可编程逻辑器件厂家的特定型号器件，最好使用特定的元 件库。 映射将电路中的元件映射到逻辑单元之中。优化逻辑单元数目的映射将尽量 减少使用的逻辑单元数目；优化时延特性的映射将尽量减少信号经过的逻辑单元 2 的数目，以满足用户对时延限制的要求，所谓时延限制指由用户指定电路中任何 一根线网的最大延时和任意两根线网之间最大的时延差值。工艺映射要基于 f p g a 中逻辑单元的结构来完成，如 w e n 0 3 就提出了针对m u x 和u j t 混合结 构的f p g a 工艺映射算法。 划分把m a p p i n g 后的网表划分为几块规模比较小的网表，每一块分别放在一 块f p g a 芯片里面，划分时也要考虑满足用户对时延限制的要求 w a n g y u 0 5 。 打包把由映射和划分后得到的电路网表中的器件，譬如l u t 、d 触发器等， 用逻辑模块来实现，并根据需要保证网表中的r a m 以及宏模块信息不变，打包 时也要考虑满足用户对时延限制的要求 h u y u n 0 5 。在打包算法中往往着重考虑 降低功耗和面积，例如 a m i ts i n g h 0 2 就兼顾了这两者。 布局阶段将各逻辑模块、1 0 单元和大块r a m 放到适当的位置。一般情况下， 由于可编程逻辑器件布线资源的有限性，布局阶段的优化目标首先是布通率，通 道密度的均匀性。但是实用中还有一些其它问题要考虑。例如用户对某些路径的 时延提出限制，或指定一些线网的重要程度，或要求管脚锁定，甚至由用户指定 某个逻辑模块在f p g a 芯片中的位置或者位置范围，这样布局算法就要综合考 虑。在三维f p g a 布局方面，k i a r a s h 9 9 提出了用模拟退火算法和贪婪算法进行 可重配置讨。算系统的三维布局；在时延驱动的布局方面， s e o k j i n 0 2 提出基于拉 格朗日松弛方法的针对时延驱动的f p g a 布局算法； j a s o n 0 3 对时延驱动的布局 算法进行优化： f g a n 9 0 4 提出了同步的基于时延的f p g a 打包和布局算法。在 给宏模块布局方面，m a n i s h 0 4 对宏模块初始布局提出了新的算法；在提高布局 软件运行速度方面， k e n 0 5 提出在模拟退火阶段缩小选择范围的f p g a 布局算 法。 布线阶段实现逻辑模块、i o 单元和大块r a m 之间的连线。布线要求百分 之百的布通率，否则就是布线失败。因为可编程逻辑器件布线资源的特殊性 布线资源都己确定，布线实际上只是确定哪些编程点接通而哪些不接通。布线时 也要考虑满足用户对时延限制的要求。在时延驱动的布线研究方面， s t e v e n 0 1 提出了考虑串扰的针对时延驱动的f p g a 布线方法；在利用s a t 问题解决布线 问题的研究中，h u i 0 3 提出了一种应用于布线的松弛布尔可满足性问题的构建 方法；在三维f p g a 布局布线方面， c r i s t i n e l 0 4 提出了针对三维f p g a 的布局 布线算法。 布线完成以后，各路径的时延值才能最后确定。这时，需要进行时序验证和 分析，考察用户设计的电路的时延和速度指标，以检查电路在有时延的情况下工 作是否正常。此外，还可以根据布局布线结构显示电路在f p g a 中的布图情况。 【w m a g y i 0 5 3 位流文件生成模块根据映射、划分、打包、布局和布线产生的结果，生成二 进制的编程信息，控制f p g a 芯片中各个开关的状态 x i n g h o n 9 0 5 。 编程下载，把位流文件下载进入f p g a 芯片。 1 3 主要研究工作 f p g a 的供应商需要根据客户的需要，定制各种规模、结构不同的f p g a 。 f p g a 结构的灵活性，对相应的c a d 系统的布线有明显的影响。本文的一部分 工作介绍如何利用v p r 软件来寻找最佳的f p g a 布线结构。 为了c a d 系统能够处理不同结构、不同规模的f p g a ，我们需要对f p g a 进行结构建模，便于用高级语言描述。 f p g a 除了i o 输入输出口和逻辑模块以外，还有一些其他特殊的模块，例 如，总线模块和大r a m 模块，这些模块对f p g a 布局具有重要的影响。本文的 一部分工作介绍如何对带总线和大r a m 的f p g a 布局。 用户设计的实际电路往往调用元器件库中的一些现存模块，电路网表文件包 括宏模块，如何给宏模块合理的分配位置是至关重要的。 f p g a 一般规模较小，资源有限，对布图系统的布通率提出了更高的要求。 f p g a 为了提高性能或者布通率，一般会在f p g a 中增加特殊的可编程资源，例 如i 0 布线池，布图系统需要能够充分利用这些资源并有较好的适应性。 4 第二章研究背景 2 1f p g a 结构研究 f p g a 硬件结构的研究一直得到广泛的关注，研究方向可以分为两大类：一 方面针对f p g a 的结构设计中所涵盖的整体结构、可编程逻辑模块结构、可编程 连线结构 a m i t 0 2 1 、可编程i o 、内嵌i p 核、版图设计等问题，以面积、速度、 功耗 f e i 0 4 1 为目标进行优化设计。同时，由于在不同的应用领域中，需要f p g a 实现的最终设计差别很大，无法使某个f p g a 结构对所有应用都达到最优化，因 此这一方面的研究也包括针对特定应用领域进行的f p g a 结构优化设计。另一方 面是针对高可靠性、动态重配置、容错结构等新应用而进行的研究。本论文的研 究集中在前一个方向上。 f p g a 的整体结构确定了器件中的各个可编程功能模块如何组织在一起。层 次式的f p g a 结构如图2 1 中所示，是通过分层的方法组织可编程功能模块。每 一个层次的可编程逻辑模块都由低一层次上的若干可编程逻辑模块和可编程连 线构成，整个器件由最顶层的可编程逻辑模块、可编程连线和可编程i o 组成。 可编程逻辑模块能够实现一定的逻辑函数，连通盒将可编程逻辑模块的输入输出 连接到金属线上，开关盒连接不同的金属线。这种结构速度性能较好，在f p g a 的规模很大时也能够方便c a d 软件对可编程功能模块进行处理。 f d p l 0 0 k 芯片是复旦大学专用集成电路与系统国家重点实验室2 0 0 4 年研制 的具有完全自主知识产权1 0 万门针对数据通路的f p g a 芯片 m a x i 0 3 1 。f d t 2 0 0 k 试验芯片是复旦大学专用集成电路与系统国家重点实验室正在研制的具有完全 自主知识产权的2 0 万门新一版f p g a 芯片 s u n 0 5 1 。本文的工作是基于这两块芯 片的硬件设计完成的。 本论文的工作包括了部分f d t 2 0 0 k 试验芯片布线资源设计，根据可编程逻 辑模块结构的特点确定几种互连的基本结构，利用图2 - 2 的软件流程，把提出的 多种候选互连资源结构在软件中进行描述，使得软件能够依据所提出的各种互连 结构对网表进行布局布线，根据布局布线结果来选择最佳的互连基本结构。 5 图2 - 1 层次式f p g a 结构( 图中共3 个层次) 图2 - 2 设计互连资源的软件流程 图2 2 中，f l o w m a p c o n 9 9 4 的功能是分解测试网表，按照用户的要求将 网表映射到m 输入的u 仃和d 触发器中。t _ v p a c k b e t z 9 7 是将测试网表中的 逻辑单元进行打包的软件。v p r b e t z 9 7 是一个f p g a 布局布线的软件。 6 2 1 1 可编程逻辑模块结构和l ，o 结构 f d p l 0 0 k 的逻辑模块，英语名称c l u s t e r ，在结构上采用基于一位查询表 和多路选择器的混合形式，c l u s t e r 内部不再包括子逻辑模块。c l u s t e r 可 以编程为组合逻辑状态或时序逻辑状态。c l u s t e r 结构精简，占用芯片面积小。 f d t 2 0 0 k 试验芯片在结构上采用基于查询表和多路选择器的混合形式，一 个c l u s t e r 由两个s l i c e 组成，s l i c e 是c l u s t e r 的子逻辑块，一个s l i c e 由两个l c 组成，l c 是s l i c e 的子逻辑块。f d t 2 0 0 k 试验芯片内部的可编程逻 辑模块是基于l u t 查询表结构。如图2 - 3 是f d t 2 0 0 k 试验芯片的一个c l u s t e r 结构。 图2 - 3f d t 2 0 0 k 试验芯片的c l u s t e r 内部结构 可编程逻辑电路的可编程i ob l o c k 的主要功能为实现可编程双向三态 7 i o ，实现可编程输入、输出寄存器，实现可编程倒相的输入输出。本论文把芯片 中包含的i o 模块称为i ob l o c k ，其中包含的子i o 单元称为i o p a d 。f d t 2 0 0 k 试验芯片的水平可编程i ob l o c k 包含1 个i op a d ，垂直方向上的可编程i o b l o c k 包含4 个i op a d 。f d t 2 0 0 k 试验芯片的垂直可编程i ob l o c k 的结构 示意图如图2 - 4 所示。 图2 - 4 垂直方向上的i o b l o c k 结构 2 1 2 布线资源 f d p l 0 0 k 芯片和f d t 2 0 0 k 试验芯片的互连资源，分成三个类型：全局层次 的长线( l o n gl i n e ) 、局部连线层次的可分割长线( d i v i d a b i el o n gl i n e ) 和相邻 高速互连层次的短线( s h o r tl i n e ) 。短线具有最快的连线速度，c l u s t e r 通过 短线可以和相邻的c l u s t e r 进行连接。水平和垂直方向上的可分割长线将可编 程逻辑电路中任何c l u s t e r 进行连接，并且其上的分隔开关可根据需要将可分 割长线分割为较小的单位，提高互连资源的利用效率。长线提供了大跨距的高速 互连资源，其结构与可分割长线类似，但这种固定长度的连线，贯穿整个可编程 8 逻辑电路芯片，不可分割。引入了长线资源使得可编程逻辑电路的连线布通率和 速度性能得到提高。本论文着重介绍f d t 2 0 0 k 试验芯片的布线资源。 图2 - 5 快速互连结构 f d t 2 0 0 k 试验芯片的短线结构如图2 5 所示，左边逻辑单元的时序输出端 可以只通过一个可编程开关管与右边逻辑单元的一个组合输入端相连。 f d t 2 0 0 k 试验芯片的c l u s t e r 阵列规模是4 行1 6 列，共5 个水平通道1 7 个垂直通道，每个水平通道内跨4 个c l u s t e r 的可分割线1 5 根，跨8 个 c ：l u s t e r 的可分割线1 2 根，长线4 根，每个垂直通道内跨1 个c l u s t e r 的 可分割线1 5 根，跨2 个c ：l u s t e r 的可分割线1 2 根，长线4 根。 f d p 2 0 0 k 试验芯片可分割长线呈网格状结构，如图2 - 6 所示，提供了跨若 干个c l u s t e r 的可编程连接，c l u s t e r 的输入端和输出端在水平和垂直方向 上各通过两个连通盒与一组可分割长线连接，即一个c l u s t e r 上下左右共4 个 c u j s t e r 。两组相交的可分割长线在彼此相交处用可分割长线开关盒相连。在 同一个方向上，相邻的可分割长线单元可以用一组可编程分割开关控制相互的连 接或断开，这样获得所需长度的连线，将芯片内任意两个c l u s t e r 之间用可分 割长线连接。 9 厂 c l u s t e r i u l u 4 辩彘 i 鞲g 连通盒 开关盒 图2 - 6f d t 2 0 0 k 试验芯片可分割长线 2 1 3 总线结构和大r a m 总线是将信息以一个或多个源部件传送到一个或多个目的部件的一组传输 线。通俗的说，就是多个部件间的公共连线，用于在各个部件之间传输信息。 x i l i n x 公司的x c 4 0 0 0 系列产品中包含了总线结构。其结构如图2 7 所示。每个 逻辑模块右侧上下各有2 个三态门，c l u s t e r 的输出管脚连入三态门数据的输 入端，由三态门数据输出端连入总线。但是，c l u s t e r 的一些管脚也可以直接 连入总线，而且其他的布线资源也可以直接和总线相连。 上t 工上il ll t tt r t 乏c c i l ， 上 上 上 l ， q 一 ： ， e v -一 1 ，c - 1 ijj l _h t t t 工t 一 l 工ttl 工 图2 7 x c 4 0 0 0 的总线 1 0 图2 - 8f d t 2 0 0 k 试验芯片中的总线、三态门结构 f d t 2 0 0 k 试验芯片提供了8 位总线，水平总线均匀的在芯片中分布，每根 总线可以由6 4 个部件经过三态门驱动，而总线上的信号直接连入c l u s t e r 的 输入管脚，没有任何其他布线资源能够和总线连接 s u n 0 5 1 。f d t 2 0 0 k 试验芯片 总线示意图如图2 _ 8 所示。 现代下载到f p g a 芯片中的电路往往需要包含存储器。因此，目前的f p g a 有必要实现存储器。f d t 2 0 0 k 试验芯片内r a m 的3 4 个信号端口被分成1 7 组 ( 每组包括两个信号端口) ，通过专用的连通盒连入了芯片的1 7 个竖直布线通道 中，如图2 - 9 所示。 i ：；l ； ；l l ；l i ； l ；l i ；l 强；辫毒：l l “。；1 l l i ；l 嚣差 1 l、 么形7 。 l 口 、 - 一 口 图2 - 9f d t 2 0 0 k 试验芯片的r a m 与布线资源的连接 2 2 可编程逻辑器件布图方法 布图( 包括布局和布线) 是可编程逻辑器件编译过程中的重要环节，也是可 编程逻辑器件的c a d 系统中的重要组成部分。 可编程逻辑器件的布局就是当电路被综合并映射到可以放置到c l u s t e r 和i op a d 中的一个个子电路后，根据逻辑模块和i o 单元之间的互连关系将它 们放到目标可编程逻辑器件芯片上的恰当位置的过程 w a n g 0 4 1 。布局阶段的输 入是一组可以放置到c l u s t e r 和i op a d 中的子电路、子电路对应c l u s t e r 和i op a d 的有效引线端、以及它们之间的互连关系。 可编程逻辑器件布局问题可正式描述为： 1 、给定一个代表电路的超图g ( v ，e ) ，其中v 是顶点集( 代表逻辑模块 和i o 单元) ，e 是边集( 代表线网) ，对每条边e e ，其线网权重w ( e ) r + ( r + 是正实数集) 。顶点数i v l = n 。并给定一个具有长宽格点阵列为r s 的可编程逻 辑器件，其中r ，s n ，n 是正整数，同时满足r s - - - - t i 。 2 、寻找一个放置的映射，p ：v 一 1 ，r 】x 1 ，s ，使顶点集v 在可编程逻 辑器件的格点集上一一对应 3 、优化，即最小化某个目标函数c o s t ( p ) 。此目标函数是根据用户的需求对 某些资源费用的评估，比如线网总长最短，时延最小或者它们的组合。 布局的优化是一个典型的组合最优化问题。当完成初始布局后，改善布局总 是在某种优化算法的指导下通过布局迭代而得到的。初始布局一般采用构造算 法，构造算法只能得到局部最优解，布局结果不理想，但速度很快。改善布局使 用得最多的是模拟退火算法，模拟退火算法是一个非常耗时的优化算法，但是它 在理论上可以得到与最优解充分逼近的解 s k i r 8 3 x i n g 9 8 z h o u 9 9 1 。在可编 程逻辑器件布局中，布局的最小目标是c l u s t e r ，而时下业界最大规模的可编 程逻辑器件也只不过十万c l u s t e r 的级别，比如x i l i n x 公司的高端产品 v i r t e x i ip r o 系列，其规模也只不过为3 k 到1 2 5 k 个c l u s t e r x i l i ，因此使 模拟退火算法在可编程逻辑器件布局中变得可以接受。 模拟退火算法是模拟退火工艺逐渐冷却过程的一种求解全局最优解 的方法。模拟退火用控制参数t 的一个递减有限序列 t k l ，k = l ，2 ，3 ，以及 与之对应的链长为l k 的有限长齐次m a r k o v 链序列去控制算法的进程，而 这些参数的集合称之为冷却进度表。构造冷却进度表的核心概念就是准平 衡，所谓模拟退火达到准平衡，指在第k 个m a r k o v 链的l k 次变换后，解的 概率分布充分逼近t = t k 时的平稳分布。理论上已经证明，算法至少要进 行解空间规模的平方次变换才能达到准平衡。显然对准平衡的任意逼近将 导致模拟退火算法的指数执行时间。 1 2 t i m b e r w o l f c s e c 8 5 是一个集成的布局布线工具，它可用于标准单元，定 制宏以及门阵列的布局，是业界最早实现的模拟退火布局算法。这一算法的中心 思想是基于这样的一个概念：由一个温度参量t 来引导在众多的布局构造中的 探索。由此来决定这些降低了或减小了布局质量的构造在布局的搜索过程中是否 被接收的概率。 c h a u 9 3 把布局与映射结合在一起，对电路进行构造布局。算 法从整个电路的输出端开始慢慢回溯到输入端。每完成一步，就考虑下一个逻辑 块的所有可能的映射方案，对每一个映射方案的每一个可能放的位置做出评价， 最后决定取哪种映射的哪一个位置。 v p r ( v e r s a t i l ep l a c ea n dr o u t e ) f b e t z 9 7 a l e x a n d e r 0 0 是一个用于f p g a 布图 研究的通用算法，在布局阶段，采用了模拟退火算法。v p r 参考并吸收了很多 以前的相关研究的成果，提出一个自适应退火( a d a p t i v ea n e a l i n g ) 模型，定义 每个温度下交换( 移动) 的次数，温度进化的规律，退火结束判据。 首先，对于模拟退火起始温度t s ，v p r 根据前人研究结果，采用下述方法 获得：设n b l o c k 为待布电路的逻辑块和i o 单元数目的和，则起始温度设为电路 交换n b l o c k 次目标函数标准偏差的2 0 倍，以便对于所有在退火初始时刻的所有 交换刚刚能接受。对于每一个温度下交换的次数，v p r 也采用已有的研究结果， 即： 协v 甜p 打t e m p 口砌f “旭= 咖n g r 聊f n b l o c k s ) 4 ” ( 2 1 ) 式中i n r l e r n u m 是一个布局时问线性调整因子，默认值为1 0 。减小或增大此 值将会有限地影响布局的结果。对于退火结束条件，v p r 采取下式作为结束判据： 丁 o 9 6o 5 0 8 a 0 9 60 9 o 1 5 a 0 8o 9 5 a 0 1 5 o 8 表2 1v p r 湿t 度进化表 容易想象，当温度很高，几乎所有的交换都被接受时，目标函数的改善并不 1 3 明显，而相反，当温度很底，接受概率很小的时候，目标函数的改善也不大，基 于这样的考虑，v p r 采取了上面的温度进化表。 在计算线网目标函数的时候，v p r 采用了线性拥挤度目标函数，就是不但考 虑线网的长度，而且考虑线网位置的平均资源费用。线性拥挤度目标函数如下式 所示： n n e t s c o s t = q ( 挖) 4 ( 皇坐! 12 c 一。( n ) b b y ( n ) c 。，( n ) ( 2 3 ) b b x 和b b y 分别表示线网x 和y 方向的幅度。c x 幕u c y 分别表示线网资源平均 分布情况。布线宽度越宽，值越大。q ( n ) 是多端线网补偿因子，它由下式决定： g 似= ，n u m t e r m i n a l s 3 ( 2 5 ) 最后，v p r 还引入了一个附加参数交换范围因子r ，r 用于限定两个待交换 的c l u s t e r ( 或者i op a d ) 之间的距离，也就是说，当待交换的两个c l u s t e r ( 或者1 0p a d ) 的第一个已经确定的前提下，第二个必须在以第一个c l u s t e r ( 或者1 0p a d ) 为中心，边长为r * f p g ar a n g e 正方形中选取。实验证明，这 种方式比没有限制框的交换效率要高。v p r 中的r 由下式确定： r 淼= m i n ( r 淼+ ( 1 0 4 4 + 口) ，1 ) ( 2 6 ) r 在初始温度时等于1 ，它保持不变直到。等于o 4 4 ，随后r 逐渐减小，最 后随着温度降低而使交换只能在相邻c l u s t e r ( 或者i op a d ) 间进行。 a l e x a n d e r 0 0 在v p r 工作的基础上，提出了带时延驱动的f p g a 布局方法。 该方法提出了每一个线网的关于时延的目标函数值，如下式所示： c r i t i c a l i t ve x d o n e n t，、 t i m i n g _ c o s t ( i , j ) = d e l a y ( i d ) c r i t i c a l i t y ( i , j 、 l2 7j i 代表电路中某根线网的源点，往往指电路中的输入i o 单元或者寄存器的 输出管脚，而 代表电路中某根线网的某个终点，往往指电路中的输出i o 单元 或者寄存器的输入管脚。d e l a y ( i , j ) 是连接源点i 和终点i 的边上的时延值。 c r i t i c a l i t y 的定义如( 2 _ 8 ) 所示，d m a x 是整个电路关键路径的时延。s l a c k 是指在 不增加d m a x 的前提下一根线网能够增加的时延值。在新的目标函数中，依据 c r i t i c a l i t y 计算每个线网的 的一个乘方值，如公式( 2 7 ) ，从而 控制不同_ _ e x p o n e n t 的线网的相对重要c r 程i t i 度c a l 。i t y c r i t i c a l i t y而一个电路的总体的时间目标函数 1 4 值是所有线网的时间目标函数值的总和，如公式( 2 9 ) 所示。 c 渤1 i 娟) _ 1 一絮 ( 2 8 ) t i m i n g _ c o s t = 己t i m i n g _ c o s t ( i , j )( 2 9 ) v i d c c i r e u i t 下面是自动归一化的目标函数值。自动归一化目标函数值依靠于时延目标函 数值和线网目标函数值。它采用了一个称作为 的折衷变量来决定给每个组成部 分多少权重。为了归一化这两个组成部分，使用了两个归一化变量，称为 p r e v i o u s t i m i n g _ c o s t 和p r e v i o u s w i r i n g _ c o s t ，它们在每一个温度下更新一 次。这两个归一化组成部分的效果是使得函数仅仅按照 来权衡两个组成部分， 而不管它们的实际值。这是方便的，因为它自动调整两个组成部分的权重，从而 算法总是给t i m i n g c o s t 的变化分配 的重要性，给w i r i n g _ c o s t 的变化分配( 卜 ) 的重要性。 a t i m i n gc o s tw i f i n gc o s t a c 2 ) 、。p r e v i o u s t _ 二i m 2 i n g c o s t + ( 1 - x ) 。p r e v i o u s ：2 一 ( 2 1 0 ) _ w i r i n g _ c o s t a l e x a n d e r 0 0 已经发展了一个新的布局软件，称作为t - v p l a c e ，这是对原始 的v p l a c e 算法的一个扩展。t - v p l a c e 既可以线长驱动，也可以时延驱动。同时 考虑减少线长和降低关键路径的时延是非常重要的，因为仅仅考虑时延驱动的方 法将导致电路需要无法接受的布线资源，而仅仅考虑布线资源将导致实现的电路 速度很慢。t - v p l a c e 同时考虑了关键路径的时延和线长，并且在这两者之间找到 一个合理的折衷。t - v p l a c e 是基于模拟退火算法的，它采用了和原始的v p l a c e 一样的退火表。 可编程逻辑器件的布线是通过选择芯片上合适的线段和开关资源将互连线 网连通，与a s i c 布线时资源可动态分配( 通过加大模块间距离) 不同，这种走 线是在有限的资源下进行的，所以可编程逻辑器件的布线算法强烈地依赖可编程 逻辑器件的结构尤其是布线资源结构，并且布通率是布线甚至布局开始就必须考 虑的问题 d w i g 9 1 g u y g 9 3 。可编程逻辑器件布线算法可分为两大类：基于 通道的布线算法和基于线网的布线算法。 基于通道的布线算法分总体布线和详细布线两步。总体布线借鉴标准元胞和 门阵列设计方法中已较为成熟的总体布线算法，优化目标偏重布线的均匀性，避 免局部走线过密导致布不通。详细布线实际上是为每条连线找出一组可编程开 关，使这组开关连通它们所接的布线段，构成所需的连线。可编程逻辑器件详细 1 5 布线是跨通道的，以线网为单位进行。选择构成连线段时为每一条可能用到的线 段计算代价函数，代价函数反映其它线网对被考察线段的需用程度，然后在众多 可能的构成方案中选取线段代价总和最低的一组线段。最优解的求解是n p 完全 问题，所以必须采用启发式算法降低时间复杂度 h o n g 9 8 。还有一种基于图论 的详细布线算法 y u l l 9 6 1 ，适用于某一类结构( 如x i l i n x 公司的x c 4 0 0 0 系列) 。 基于线网的布线算法 a m i t 9 4 y a c h 9 3 y u h s 9 7 以线网为单位，采用迷 宫算法布线。迷宫算法的优点是对每一条线网而言，能求得当时的( 针对线网长 度的) 最优解，且如果存在通路，总能找到解：缺点是耗时太大。所以一般v l s i 设计中总是用迷宫算法来解决其它算法不能解决而遗留下来的问题。可编程逻辑 器件阵列不大，迷宫算法得以广泛应用。基于线网的布线算法都无法避免布线顺 序对布线质量的影响，可以单独或并用以下方法提高性能：一、布线之前为线网 排序，精心设计排序算法；二、应用“拆线重布”算法，通过几个循环的重布使 结果收敛于较优解 z h o u 9 9 。 c g e s t e p 9 2 是一个著名的可编程逻辑器件详细布线算法。此算法在详细 布线前把线网都划分成二端线网，并已经过总体布线，将每个二端线网做扩展， 把二端线网从“源”端到“目的”端在指定通道内所有可能的走法都列举出来。 v p r ( v e r s a t i l ep l a c ea n dr o u t e ) v a u g 9 7 j o r d a n 9 8 是一个用于f p g a 布图 研究的通用算法，在布线阶段采用了改进型迷宫布线算法。v p r 在普通迷宫算 法中另外加入了用于指导布线的资源拥挤度预测，以提高布通率。在具体操作上 它分两步完成布线，首先不管布线资源的重用，以每条线网的最短路径为目标对 所有线网进行布线，计算所有布线资源的重用率，每个布线资源的重用率作为拥 挤度预测指示而影响下一次迭代时使用此布线资源的费用。第二步使用撕裂重布 的办法进行迭代重布线。 v p r 的详细布线算法是利用一个有向图来表示详细的布图资源连接关系。 在这个有向图中，布线资源和逻辑模块的管脚( 如果是可编程逻辑器件的话，还 包括可编程输入输出块) 就是资源图的顶点，而可编程的连通开关足资源图的 有向边。在可编程电路里可以用开关或者缓冲器作为可编程的连通开关，它们分 别对应于双向和单向的有向边。图2 1 0 是从布线资源转化为布线资源图的实例。 1 6 c l u 翟1 排! c l u s t e r n 1ti h 0广士一i 广_，l jo _ n l l 二一i l c l u s t e r 陌 - 2 , 刮i n l u s t e r l 一 图2 1 0 布线资源图 f d t l 0 0 k 芯片的配套布线软件的算法核心思想和v p r 的算法思想是一致 的。其特点是能够支持f d t l 0 0 k 的详细布线资源结构，本论文的工作包括在 f d t l 0 0 k 布线软件中构建了描述f d t l 0 0 k 详细布线资源连接关系的有向图。 1 7 第三章带总线资源和r a m 的f p g a 建模 3 1f p g a 建模背景 一套高效的c a d 系统是使用可编程逻辑器件的必要条件。和普通v l s i 的 c a d 系统不同，可编程逻辑器件的c a d 系统往往需要处理一系列或者不同系列 的可编程逻辑器件芯片，因此可编程逻辑器件的c a d 系统处理的对象更加灵活。 在这些c a d 系统中，如何使软件系统可以处理各种各样的可编程逻辑器件的结 构，是个很重要的问题。 d w i g 9 1 将可编程逻辑器件所有的可编程开关都放在一个文件中描述，然 而，随着商业可编程逻辑器件规模的目益扩大，这种方法很快就不适用了。有关 资料表明，一个包含8 0 0 0 个4 输入u j t 的可编程逻辑器件芯片的可编程开关描 述文件的大小将近3 0 m b v a u g 9 9 。c g e s t e p 9 2 、s e g a g u y g 9 3 等可编程 逻辑器件布线程序的建模方法比较简单。 v p r v a u g 9 7 是一个用于可编程逻辑器件布图研究的通用算法，它采用的 建模方法比c g e 、s e g a 详细 v a u g 0 0 ，也提出了较完整的布图方法的解决方 案，但v p r 对可编程逻辑器件的结构描述存在着问题，它能够描述一些非常复 杂的布线资源类型，譬如模型描述各个通道宽度呈高斯分布，但是实际的物理芯 片中很少有这种类型的通道宽度分布，此外，模型本身支持的连通盒和开关盒的 类型有限，因此它只能支持有限类型的f p g a 芯片；随着f p g a 布线资