（微电子学与固体电子学专业论文）fpga装箱和划分算法研究.pdf

摘要 摘要 随着集成电路的设计规模越来越大，f p g a 为了满足这种设计需求，其规模 也越做越大，传统平面结构的f p g a 无法满足实际设计需求。首先是硬件设计上 的很难控制，其次就是计算机软件面临很大挑战，所有复杂问题全部集中到布局 布线( p & r ) 这一步，而实际软件处理过程中，p r 所占的时间比例是相当大 的。为了缓解这种软件和硬件的设计压力，多层次化结构的f p g a 得以采用。所 谓层次化就是可配置逻辑单元内部包含多个逻辑单元( 相对于传统的单一逻辑单 元) ，并且内部的逻辑单元之间共享连线资源，这种结构有利于减少芯片面积和 提高布通率。与此同时，f p g a 的e d a 设计流程也多了一步，那就是在工艺映 射和布局之间增加了基本逻辑单元的装箱步骤，该步骤既可以认为是工艺映射的 后处理，也可认为是布局和布线模块的预处理，这一步不仅需要考虑打包，还要 考虑布线资源的问题。装箱作为连接软件前端和后端之间的桥梁，该步骤对 f p g a 的性能影响是相当大的。 本文通过研究和分析影响芯片步通率的各种因素，提出新的f p g a 装箱算 法，可以同时减少装箱后可配置逻辑单元( c l b ) 外部的线网数和外部使用的引 脚数，从而达到减少御线所需的通道数。该算法和以前的算法相比较，无论从面 积，还是通道数方面都有一定的改进。算法的时间复杂度仍然是线性的。与此同 时本文还对f p g a 的可配置逻辑单元内部连线资源做了分析，如何设计可配置逻 辑单元内部的连线资源来达到即减少面积又保证芯片的步通率，同时还可以提高 运行速度。 另外，本文还提出将电路分解成为多块，分别下载到各个芯片的解决方案。 以解决f p g a 由于容量限制，而无法实现某些特定电路原型验证。该算法综合考 虑影响多块芯片性能的各个因数，采用较好的目标函数来达到较优结果。 关键字：装箱，布通率，划分，非全连通 中图法分类：t p 3 9 1 a b s t r a c t t r a d i t i o n a lf l a t t e nd e s i g ns t y l eo ff p g aa r c h i t e c t u r ec a n tf u l f i l lc u r r e n t l y r e q u i r e m e n tw h e nt h es c a l eo fa s i cb e c o m e sl a r g e r t h ed e s i g n e r so ff p g aa l s o p r o p o s es o m en e ws o l u t i o n st os o l v et h i sp r o b l e mi no r d e rt om e e tt h em a r k e t t h e r e a r es e v e r a li s s u e st h a tn e e dt ob ef i x e d n ef i r s to n ei sh o wt oc o n t r o lt h ec o m p l e x i t y o ft h eh a r d w a r e ，i n c l u d i n gd e s i g n , v e r i f i c a t i o na n dm a n u f a c t u r e t h es e c o n di st h a t t h es o f t w a r eh a st of a c eg r e a tc h a l l e n g ew h e ni m p l e m e n t i n gt h o s el a r g es c a l ec i r c u i t s , e s p e c i a l l yt h ep & rm o d u l e ，f o rt h i sm o d u l ew i l lt a k ea l m o s t7 0p e r c e n to ft h et o t a l t i m e i n0 r d e rt or e l i e ft h ep r e s s u r eo fb o t hh a r d w a r ea n ds o f t w a r e t h ef p g aw i t h h i e r a r c h i c a la r c h i t e c t u r eh a sb e e np r o p o s e d t h eh i e r a r c h i c a la r c h i t e c t u r em e a n st h a t o n ec o n f i g u r a b l eb l o c kw i t hm a n yb a s i cl o g i ce l e m e n t sw h e nc o m p a r e dw i t hp r e v i o u s o n eb a s i cl o g i ce l e m e n t ( l e ) t h o s el e sc a ns h a r ei n t e r - c o n n e c t so ft h ec o n f i g u r a b l e l o g i cb l o c k s ，t h i sk i n do fs t r u c t u r ec a ni m p r o v et h er o u t a b i l i t ya n dd e c r e a s ea r e ao f t h e f p g a w eh a v et oa d do n em o r es t e pt op r e v i o u sd e s i g nf l o wt h a ti sp a c k i n go ft h e l e sw h i c hi sj n s tb e t w e e nm a p p i n ga n dp & ra tt h es a m et i m e 碱ss t e pc a nb et a k e n a st h ep o s tp r o c e s so ft h em a p p i n go ra st h ep r e p r o c e s so ft h ep & f o ri th a st o c o n s i d e rh o wt op a c k i n gm o r el e st o g e t h e ra n dh o wt oi m p r o v et h er o u t a b i l i t y p a c k i n gf l o wh a sag r e a ti m p a c to nt h ep e r f o r m a n c eo f t h ef p g af o ri ta l s oa c t sa st h e b r i d g eb e t w e e nt h ef i o n t - e n da n db a c k - e n d i nt h i sp a p e r , an e w p a c k i n ga l g o r i t h mi sp r o p o s e da f t e rd o i n gs o m er e s e a r c h a n dm a k i n gs o m ea n a l y s i so v e rf a c t o r st h o s ea f f e c tr o u t , a b i l i t yo ft h ef p g a n l e n u m b e ro ft h eu s e dp i n so ft h ec l ba n dt h ei n t e r - c l bw i r e sc a l lb er e d u c e da tt h e s a n l et i m et h r o u 曲t h i sa l g o r i t h ma n da l lo ft h o s ew i l lr e s u l ti nl e s st r a c k sn e e d e d b o t hn u m b e ro fn e t sa n dr o u t i n gt r a c k sh a v eb e e ni m p r o v e dw h e nc o m p a r e dw i t l l p r e v i o u sa l g o r i t h m s t h et i m ec o m p l e x i t yo ft h i sa l g o r i t h mi ss t i l ll i n e a r t h e nw e p r o p o s ean e wa l g o r i t h mt od ot h ea n a l y s i so fi n t e r - c o n n e c t so ft h ec o n f i g u r a b l el o g i c b l o c k ，t h r o u g ht h i sa l g o r i t h mw ec a l lm a k es o m ee v a l u a t i o na n dg e t $ o m ec o n c l u s i o n a b o u ts t r u c t u r eo f t h ec l b f i n a l l y , w ep r o p o s ean e ws o l u t i o nt os o l v et h ep r o t o t y p i n go fc i r c u i tt h a tc a n t b ep u ti ns i n g l ef p g a c h i p t h es o l u t i o ni st op a r t i t i o nt h ec i r c u i ti n t os e v e r a ls u b m o d u l e sa n dt h e ni m p l e m e n t ss e p a r a t e l y t h i sp a r t i t i o na l g o r i t h mc o n s i d e r ss e v e r a l f a c t o r st o g e t h e ra n dt h e ng e n e r a t e sa l lo p t i m a lr e s u l t i i 摘要 k e y w o r d s ：p a c k i n g ；r o u t a b i l i t y - d r i v e n ；p a r t i t i o n ；n o n f u l l yc o n n e c t e d m 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果论文中 除了特男d 加以标注和致谢的地方外不包含其他入威其它机构已经发表或撰写 过的研究成果其他同志对本研究的启发和所做的贡献均已在论文中作了明确 的声明并表示了谢意 储釜名：j 函i 一日期：删一7 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定即：学校有权保 留送交论文的复印件允许论文被查阅和借阅：学校可以公布论文的全部或部 分内容可以采用影印、缩印或其它复制手段保存论文保密的论文在解密后 遵守此规定 作者签名：址导师辇名：二主兰丝日期：堑f 兰盟? 罗 第l 章引言 第1 章引言 1 1f p g a 的发展和设计流程 1 1 1f p g a 的发展和现状 自从集成电路的出现，这个产业经历许多革新，其中包括a s i c 设计，c p u 的设计，模拟集成电路，和f p g a 。f p g a 是在1 9 8 4 年被提出的，在经历了2 0 多年的发展之后，f p g a 已经成为一种实现数字电路的最流行途径之一，并且 f p g a 每年在全球的销售额已经达到几十亿美金。f p g a 之所以成功的一个最主 要的原因是由于它的可编程性，可以快速实现任何数字电路的逻辑功能。 f p g a 在相对于a s i c 和m p g a ( m a s k - p r o g r a m m e dg a t ea r r a y s ) 不仅在上 市时间，而且在电路调试和重复设计方面也有很大的优势。另外，f p g a 还为工 程师提供方案，可以为已经制造好的芯片解决某些错误或为该系统添加新功能的 特性。由于f p g a 可以在瞬间实现任何数字电路的功能，使它在实现小规模的数 字电路或紧急需要的硬件很有优势，因为不再需要像a s i c 那样重新设计和制造。 f p g a 的这些优势是以牺牲菜些特性的为代价的，首先f p g a 的运行速度只 有a s i c 电路的1 3 ，面积是a s i c 电路十倍左右。造成f p g a 芯片速度很慢的 原因是：逻辑单元和其它逻辑单元之间的连接是通过金属导线和开关晶体管实现 的，而a s i c 电路中逻辑单元之间的连接是通过金属导线实现的，开关晶体管相 对于金属导线有很大的电阻和电容，根据r c 时延模型，可以得出金属导线加开 关晶体管的延时是很大的。另外，由于f p g a 内部的逻辑单元之间的连线长度是 在布线之后生成的，逻辑单元之间的连线长度实际大于他们之间的曼哈顿距离， 也是造成电路运行速度较慢的原因之一。f p g a 为了实现可编程的特性，在实际 设计电路的时候，为了保证芯片的布通率，提供了很多可以编程的布线资源，而 这些布线资源在整个f p g a 芯片中所占面积的比重达到了7 0 - - 8 0 ，而与 a s i c 芯片的所有布线连接基本上都在逻辑单元之上实现的，所以造成f p g a 芯 片的面积很大。f p g a 逻辑单元的利用率也是造成面积很大的因素之一。 随着工艺技术进入到深亚微米，工艺尺寸的减少并不能提高芯片的运行速 度，虽然工艺尺寸的减少可以降低晶体管的延时，但是在深亚微米时，真正制约 芯片运行速度是连线延时，工艺尺寸的下降不仅没有缓解连线延时，反而造成更 第1 章引言 大的连线电阻和电容。 由于现在e d a 领域的大部分算法都是一些n p 完全问题，实际计算机求解 出的结果离最优解还有一定差距，可以通过改善软件的算法来提高特定结构 f p g a 的整体性能。由于f p g a 芯片的面积很大，所以在将电路映射到f p g a 芯 片的过程中，提高芯片的布通率是很有意义的。 1 1 2f p g a 软件设计流程 f p g a 的设计流程包括：网表优化，工艺映射，电路划分，逻辑单元的装箱， 布局布线，码点生成，编程下载，如图1 - 1 所示。网表优化实现消除冗余的逻辑， 减少电路实际所需的面积。工艺映射实现将优化后网表转化为由查询表( 1 0 0 k u p t a b l e ，简称l u t ) 和时序单元组成的电路，月输入l u t 可以实现输入数目不超 过r 任何组合逻辑功能，因此，工艺映射的目标就是在满足输入约束的条件下， 将更多的组合逻辑放入到一个l u t ，以减少所需f p g a 的容量。工艺映射之后， 根据生成的l u t 数目，可以知道给定f p g a 是否可以实现该电路的逻辑功能， 如果电路的规模大小超过f p g a 的容量，可以采用电路划分，将电路划分成为几 块比较小的，可以分别放进到给定的f p g a 。 匪蛰一+ 围爹 因 y 三) 一 习一巨丑 国叵 图1 1f p g a 设计流程 前面这些步骤基本上都属于逻辑优化和电路的描述方式的转换，逻辑单元的 2 第1 章引言 装箱和给定f p g a 结构有很大关系，由于层次化结构的运用，才出现装箱这个步 骤，装箱算法在某种程度上依赖于f p g a 的结构，实现将多个逻辑单元( 1 0 9 i c e l e m e n t ，简称l e ，如图l 一2 中的a 所示) 打包到一个可配置逻辑单元( c o n f i g u r a b l e l o g i cb l o c k ，简称c l b ) 。目前比较流行的结构如图1 - 2 中的b 所示，就是一个 c l b 内部包含多个l e ，这些l e 之间共享输入，同时它们的输出也可以通过互 连资源反馈到输入端。布局实现将装箱之后的c l b 单元映射到实际f p g a 的各 个逻辑位置，以达到减少c l b 之间连线的交错度，这样可以缓解布线模块的压 力。布线模块将c l b 之间的各个连接采用f p g a 内部已经存在连线资源连接起 来，这样整个电路就被完全映射到给定的f p g a 芯片。位流生成模块将前面生成 的数据进行汇总，产生需要被打通的编程点的物理位置，然后再由编程下载程序 将生成的位流下载到f p g a 。 i 一一一一一一一一一l i l f r b 一 “ ! 劳一一 i i i j k 一一一l e j i ( a ) 慕本逻辑单元l e ( l u t 和d f f 组成)( b ) 可配置逻辑单元( c l b ) 图1 2 c l b 结构 1 2 装箱算法的发展 目前比较常用装箱算法相对而言是比较少，t v - p a c k i m 州9 9 1 是一种效果较好 的装箱算法，该算法是在1 9 9 9 年被提出，它同时考虑时延和面积。v p a c k i 蚴1 是t vp a c k 的前身，v p a c k 这个算法是1 9 9 7 被提出的，v p a c k 只是考虑l e 之 间输入引脚的共享，而没有考虑电路的时延问题，但是t v - p a c k 布通率比v p a c k 要高。r p a c k 8 0 z o o l 】是一种基于布通率的装箱算法，它在装箱的目标函数中，同时 考虑影响电路布通率的几种因素，其布通率相对于v p a c k 有较大的提高。 i r a p 8 1 ”9 0 2 是一篇关于装箱和布局的算法，该算法通过改变原有算法的目标函数 并根据r e n t s 规则来控制每个c l b 的输入引脚数目，起到增加装箱后c l b 的数 目，在布线通道数目固定的条件下，采用更大的阵列规模来提高布通率，该算法 相对以前的装箱来说，在布通率方面有较大的提高。i r a cr e p l i c a m a v 0 5 是一种 第1 章引言 新的装箱算法，该算法认为文献 s i n 9 0 2 】通过控制每个c l b 使用的引脚数目并不 是很有效，而是采用通过控制装箱到每个c l b 中l e 数目来改善电路的布通率。 文献 s i n 9 0 2 和 m a r y 0 5 是通过是以牺牲阵列规模为代价，从而提高布通率，而 本文在后面的章节中提出的算法是在保证阵列规模不变大的条件下，提高芯片的 布通率。 1 3 本文的主要工作 由于现有的装箱算法都是基于提高时延性能或以牺牲c l b 的数目来提高电 路的布通率，本文是在总结和分析前人的研究成果的基础上，分析得出哪些因数 是影响电路的布通率，哪些因数会影响电路的时延性能，然后根据这些结论提出 新的目标函数，该目标函数可以在不增加c l b 数目的条件下，有效的减少c l b 之间的连线数目，同时还控制每个c l b 外部使用的引脚数目，这样就可以很大 程度的降低布局后局部拥挤度，从而降低布线模块的压力来提高芯片的布通率。 另一方面，本文也对非全连通的c l b 的结构作了研究和分析，比较不同的 连接方式和不同的连通度对芯片面积和芯片的布通率之间的关系。由于非全连通 的c l b 在装箱的时候，需要考虑是否当前各个l e 之间的连接关系是否超越c l b 所能提供的连接资源，如果超越，那么当前几个l e 的组合是不可行的，反之， 是可行的，为此本文还提出比较有效的算法，来解决非全连通c l b 的装箱问题， 所有对非全连通c l b 结构的分析和研究都是基于该程序输出的结果。 由于实际a s i c 电路的规模是在不断的增大，并且该增大的趋势远大于 f p g a 芯片容量的增长，于是出现很多a s i c 电路在使用f p g a 进行原型验证时， 无法全部下载下去，为此，本文针对这种情况提出相应的解决方案，该方案将一 个大规模的电路通过划分，分解成为几块比较小的并且可以被放进f p g a 芯片的 子电路，然后在通过p c b 将它们分别连接起来，这样就可以对大规模的a s i c 进行原型验证。该划分算法是在前人的研究成果的基础上，改进而来的。该算法 可以很大程度上减少划分后，各个模块之间的连线数目，是一种较好的划分算法。 1 4 论文组织结构 在接下来的几章中，本文将详细介绍各个算法的研究和开发。具体组织如下， 第二章，介绍f p g a 的研究背景和前人所做的一些工作；第三章中，介绍全连通 结构的c l b 和l e 的构成，以及它们之间的连接方式，和针对这种结构的装箱 算法，实验数据的分析和比较；第四章介绍非全连通结构的c l b 和l e 的构成， 4 第1 章引言 何种比例的连通度是对减少芯片面积和时延是最有效，以及处理非全连通结构的 装箱的特殊算法，实验数据的分析和比较；第五章提出解决大规模a s i c 电路原 型验证的方法，并且详细介绍电路划分算法的研究与开发，实验数据的分析和比 较；第六章中，我们给出全文的总结并对未来的工作进行一些展望； 5 第2 章研究背景和前人t 作 第2 章研究背景和前人工作 在这一章中，我们将首先介绍f p g a 的整体架构，并且主要介绍f p g a 的可 配置逻辑单元。然后介绍将网表映射到f p g a 芯片中需要使用的c a d 工具，并 且将详细介绍l e 装箱算法和电路的划分发展历史等等。 2 1f p g a 的结构 通常，f p g a 由c l b ，l e ，i o 单元和可编程的布线资源构成( 如图2 1 所 示) 。为了在f p g a 芯片上实现一个电路的功能，通过对l e 单元进行合适的编 程可以实现某些小的单元功能，然后在通过对可编程的布线资源进行编程，可以 将各个小的功能单元连接起来，就可以实现更大功能的电路，f p g a 芯片上的i o 通过编程可以用来映射电路的输入输出端口，这样一个电路就被完整的下载到 f p g a 芯片中。f p g a 芯片中可配置逻辑单元类型对f p g a 芯片的性能有很大的 影响，因此我们将介绍可配置逻辑单元，以及如何在f p g a 的性能和面积方面进 行折中。 1 0 bi 口口 口口口口 口巳业 c l b 隹刍c b 苣三1c l be ! 引c b 三ic l b c b c l b 巨引c b 巨三lc l be 引c b 鲁三fc l b c b c l b 引c be 三fc l b 引c b jc l b 口口口口口口口口口口 图2 - 1f p g a 芯片结构 6 口口口口口口口口口口 口口口口口口口口口口 第2 章研究背景和前人工作 2 1 1 基于簇结构的逻辑单元 我们将介绍由基本逻辑单元通过快速局部互连相连构成的可配置逻辑单元。 通常，l e 是最小的不可再分，包含组合和时序逻辑单元，这里介绍的基本逻辑 单元由一个4 输入的l u t 和d f f 构成( 如图2 2 中的a 所示) 。可配置逻辑单元包含 多个基本逻辑单元被称为逻辑簇。例如，a l t e r a 公司f l e x 6 k ，f l e x8 k ，和f l e x 1 0 k a l t e 9 8 等产品系列，还有x i l i n x 公司在x i l i n x5 2 0 0 x i l i 9 7 和v e r t e xf x i l i 9 8 1 等系列产品中使用的可配置逻辑单元。图2 2 中的b 描述了逻辑单元由一个或多 个基本逻辑单元组成，它们之间要通过布线而连接起来。 i n p u t s t t 一一一 。 铂一一! ： j t 一l e 二 _ = l _ ( a ) 基本逻辑单元l e ( l u t 和d f f 组成)( b ) 可配置逻辑单元( c l b ) 图2 2c l b 结构 可配置逻辑单元包含两种类型，一种是全连通的，另外一种是部分连通。所 谓全连通就是可配置逻辑单元的输入和逻辑单元的输出可以连接到逻辑单元的 任何输入。由于可配置逻辑单元是全连通的，所以可配置逻辑单元的一个输入端 可以将外部线网连接到内部任何一个基本逻辑单元的输入端，同样基本逻辑单元 的输出端的信号也可以连接到任何一个基本逻辑单元的输入端。这样可配置逻辑 单元实际所需要的外部输入端口数将要少于全部基本逻辑单元的输入数目之和。 全连通的另外一个好处，就是可以简化装箱工具的实现，因为所有的基本逻辑单 元是逻辑等价。 所谓非全连通就是基本逻辑单元的输入可以连接到逻辑簇的部分输入和部 分基本逻辑单元的输出。尽管它们之间的连通度可能不是很高，而通过采用较好 的装箱算法，在可配置逻辑单元外部输入数目小于所有基本逻辑单元的输入数目 之和的约束情况下，同样可以保证装箱到可配置逻辑单元内部的基本逻辑单元数 7 第2 幸研究背景和前人丁作 目的比例。由于内部的基本逻辑单元之间不是等价，所以非全连通的可配置逻辑 单元装箱工具较全连通结构的要复杂一些，那就需要对内部的连接进行布线。 由基本逻辑单元构成的可配置逻辑单元，用以下4 参数进行描述： l u t 的输入数目( 七) 夺可配置逻辑单元包含的基本逻辑单元数目( ) 可配置逻辑单元的输入数目( ，) 可配置逻辑单元的c l o c k ，r e s e t 和s e t 数目 文献 b e t z 9 9 ，b e t z 9 8 的工作主要集中在研究，以u j t 输入数目为4 ，c l o c k 输入数为1 的条件的可配置逻辑单元。所有基本逻辑单元的输入数目为托 r ，而 实际可配置逻辑单元的输入数目为。文献 b e t z 9 8 通过研究显示，输入数目为， = 2 ，+ 2 的情况下( 的取值范围在1 1 0 之间) ，f p g a 的面积是最优的。这 个研究结果是在没有考虑电路的时延的条件得出，尽管如此，越大，对f p g a 的时延性能提升越高。 8 第2 章研究背景和前人工作 2 2f p g a 设计的c a d 工具和算法 图2 3 给出将网表映射到f p g a 芯片中去的主要c a d 流程。这个c a d 流 程是被f p g a 和a s i c 设计者采用较多的流程。首先将提供的网表使用s i s 岱“j 做逻辑优化，然后再采用f l o w m a p 【o 呻9 9 4 】算法将整个电路的组合部分映射成为4 输入的l u t ，如果该电路不能够被全部放在一个f p g a 芯片，我们将调用p a r t i t o n 程序对电路进行划分，t v p a c k ( 该工具将会被我们开发的工具替代) 被用来将 l u t 和d f f 打包到c l b ，最后我们再采用v p r 通过布局将c l b 放到特定的x ， y 的坐标上去，再调用布线将这些c l b 通过内部的布线资源连接起来。 可放进y e s 输出结果 图2 - 3f p g a 的c a d 流程 9 第2 章研究背景和前人工作 2 2 1 基于簇结构f p g a 的装箱算法 装箱算法的目的为了将由l u t 和d f f 组成的网表转化成为由c l b 构成的 网表。它包含将l u t 和d f f 合并成为l e ，然后再将多个l e 装箱成为c l b 。 装箱时需要满足以下几个条件： a 全连通结构的c l b 1 装箱到c l b 内部的l e 数目必须小于或等于 2 所有l e 的不同输入的总数之和必须小于或等于c l b 外部允许 的输入数， b 非全连通结构 1 装箱到c l b 内部的l e 数目必须小于或等于 2 所有l e 的不同输入的总数之和必须小于或等于c l b 外部允许 的输入数 3 c l b 内部的l e 之间的连接关系不能超越c l b 所能提供的连接 资源 a l t e r a 公司拥有将电路映射成为簇结构的工具 a l t e 9 5 】，x i l i n x 公司也拥有同样类 似的工具，用来将电路映射至u 5 2 0 0 x i l i 9 7 和v i r t e x x i l i 9 8 1 系列e b c l b ，尽管如 此，这些工具是属于商业性质的，我们是无法得到。在这一节中，我们将介绍几 个学术性质的装箱工具和算法，它们是v p a c k ，t v p a c k ，r p a c k 等等。 2 2 1 1 。基于面积优化的v p a c k 装箱算法 v p a c k 算法的输入为由l u t 和d f f 组成的网表，输出为由c l b 组成的网 表。参数( ，k ，朋矶) 作为程序输入参数在运行时传进去。v p a c k 首先将 l u t 和d f f 合并成为一个l e ，然后在将多个l e 装箱成为一个c l b ( 如图2 4 所示) 。下面是v p a c k 算法的伪代码： l e t ：u n c l u s t e r e d l eb et h es e t o f l e s n o tc o n t a i n e di na n yc l u s t e r cb et h es e to f l e sc o n t a i n e di nt h ec u r r e n tc l u s t e r l o g i c c l u s t e r sb et h ec l u s t e r s ( w h e r ee a c hc l u s t e ri sa s e to f l e s ) u n c l u s t e r e d l es = p a t t e r n m a t c h t o l e s ( l u t s , d f f s ) ； l o g i c c l u s t e r s = n u l l ； w h i l e ( u n c l u s t e r l e s ! = n u l l