（计算机应用技术专业论文）基于多目标演化算法的soc设计空间搜索策略研究.pdf

哈尔滨1 科人学硕士学位论文 摘要 随着硅片上集成的晶体管数量迅猛增加，基于i p 核的s o c 已成为v l s i 实现技术发展的趋势。目前s o c 的系统设计主要采用基于i p 核的配置并执 行方法。这种方法是从一个预设计的参数化s o c 体系结构出发，以参数化的 i p 核为组件，通过编写代码、设置参数的方式，对可编程的i p 核进行配置以 实现设计，通过模拟器仿真执行以完成功能验证，最后产生物理芯片。由于 i p 核的多样性及其可优化参数的矛盾性，使得s o c 的设计空间极其复杂。 能否找到一组最优的参数，直接关系到设计的成败。s o c 系统综合的主要任 务之一就是针对具体的应用在可能的设计空间中找到一组满足设计约束的i p 可行配置集，其本质是求多目标优化问题的最优解。 多目标优化问题的经典求解方法是使用目标函数线性聚合或者基于 p a r e t o 方法。这类方法通常是将若干个子目标聚合成向量函数，转换成单目 标优化问题，其最大的缺点是优化结果为单个解而非p a r e t o 最优集合。使用 演化算法求解多目标优化问题的优点在于该方法将解集作为群体，并行搜索 多个p a r e t o 最优解对应的目标空间节点。在对s o c 系统综合本质和多目标演 化算法分析的基础上，针对s o c 设计空间的复杂性，提出了一个新的搜索策 略，使得s o c 系统应用在消耗较低功率的同时，执行的更快。该搜索策略以 多目标演化算法为核心，依据参数依赖性概念对设计空间进行大幅度的缩减 并使用空间阈值技巧增加了策略的适应性。通过与敏感度分析策略和穷举搜 索策略的对比，证明了该搜索策略具有运行时间快、求解质量高的优点。 关键词：参数化s o c 系统结构；设计空间搜索；多目标优化：多目标演化算 法；参数依赖性 堕玺鎏。! ：型盔兰堡主兰篁篓兰 a b s t r a c t t h ea v a i l a b i l i t yo fl a r g en u m b e r so ft r a n s i s t o r so nac h i ph a sl e a dt ot h e g r o w t h o f i p ( i n t e l l e c t u a lp r o p e r t y ) b a s e dd e s i g ns o c ( s y s t e m - o n a c h i p ) a r c h i t e c t u r e s m a n y i pb a s e ds o cd e s i g n a p p r o a c h e s f o c u so nm a p p i n ga n a p p l i c a t i o no n t oap r e v i o u s l yd e s i g n e dc o m p l e xs o c a r c h i t e c t u r eb u i l tf r o ma n e x i s t i n gi pb yc o n f i g u r i n g a n d e x t e n d i n g t h ea r c h i t e c t u r e ，r e p r e s e n t i n ga c o n f i g u r e a n de x e c u t em e t h o d o l o g y s u c ha p a r a m e t e r i z e ds o c a r c h i t e c t u r ei ss u p p o r t e db y ap r o g r a m m i n gs i m u l a t i o na n de m u l a t i o ne n v i r o n m e n t ，a n dm a yb ep r o v i d e da s h d ls o u r c ec o d e ，a sa na c t u a lc h i p ，o rb o t h d u et ot h ev a r i e t i e so fi pa n dt h e c o n f l i c to fi pp a r a m e t e r , t h es o c d e s i g ns p a c ei sv e r yc o m p l e x a ni m p o r t a n t s o cd e s i g nw o r ki st h e c o n f i g u r i n go f a l l c o r e s p a r a m e t e r s ，s u c ht h a t t h e a r c h i t e c t u r ei st u n e df o rt h ea p p l i c a t i o n ，i e ，t h es o f t w a r er u n n i n go nt h es o c a r c h i t e c t u r e ，a n df o rt h ep o w e r , s i z ea n dp e r f o r m a n c ec o n s t r a i n t so fs o c o n e m a i nt a s ko ft h es o c s y s t e m - l e v e ls y n t h e s i si sd e s i g ns p a c ee x p l o r a t i o n t h e e s s e n t i a lo ft h et a s ki sf i n d i n gt h eo p t i m a ls e to fs o l u t i o n st oam u l t i o b j e c t i v e o p t i m i z a t i o np r o b l e m t h ec l a s s i cs o l u t i o nt o m u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m i s u s i n g o b j e c t i v ef u n c t i o nl i n e a r i t ya g g r e g a t i o no rp a r e t ob a s e da p p r o a c h t h e s ek i n d so f m e t h o d su s u a l l ya g g r e g a t es o m es u b o b j e c t i v ef u n c t i o ni n t ov e c t o rf u n c t i o ns oa s t oc o n v e r tm u l t i o b j e c t i v ep r o b l e mi n t o s i n g l eo b j e c t i v e t h em o s td e f e c to f t h e s e a p p r o a c h e s i st h a tt h e o p t i m i z e d r e s u l ti sa s i n - g l es o l u t i o n ，n o t p a r e t o o p t i m a ls e to fs o l u t i o n s t h ea d v a n t a g eo ft h ee v o l u t i o n a r ya l g o r i t h mi s t h a ti t e x p l o r e sp a r a l l e ln u m e r o u sp a r e t o o p t i m a ls o l u t i o n sc o r r e s p o n d i n gt ot h e o b j e c t i v es p a c en o d eb yr e g a r d i n g s o l u t i o ns e ta sp o p u l a t i o n b a s e do nt h ea n a l y s i so fs o cs y s t e m - l e v e l s y n t h e s i s a n dm u l t i o b j e c t i v e e v o l u t i o n a r ya l g o r i t h mt h e o r y ，w ep r o p o s e d an e wd e s i g n s p a c ee x p l o r a t i o n s t r a t e g yt of i n da t r a d e o f fo f p o w e r a n de x e c u t et i m ef o ra na p p l i c a t i o n r u n n i n g o n t h e p a r a m e t e r i z e d s o c a r c h i t e c t u r e t h e s t r n e g y u s e si p p a r a m e t e r i n t e r d e p e n d e n c y t or e d u c et h ed e s i g ns p a c ea n dc h o o s e se x p l o r a t i o na l g o r i t h mt o e x p l o r ed e s i g ns p a c ea c c o r d i n gt o t h et h r e s h o l do fs p a c es i z e t h es t r a t e g yi s d r o v e dt ob ea b l et of i n db e t t e rp a r e t o - o p t i m a lc o n f i g u r a t i o ne f f e c t i v e l y , a n d a tt h e s a m et i m ea c c e l e r a t et h es p e e do ft h ed e s i g ns p a c ee x p l o r a t i o nc o m p a r e dw i t h s e n s i t i v i t ya n a l y s i ss t r a t e g ya n d e x h a u s t i v es e a r c ha l g o r i t h m k e y w o r d s ：p a r a m e t e r i z e d s o ca r c h i t e c t u r e ；d e s i g n s p a c ee x p l o r a t i o n ： m u l t i o b j e c t i v eo p t i m i z a t i o n ；m u l t i o b j e c t i v e e v o l u t i o n a r ya l g o r i t h m ；p a r a m 。 i n t e r d e p e n d e n c y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本人声明的法律结果由本人承担。 作者( 签字) ： 日期：衫呼年7 月，矿日 哈尔滨i 。样人学硕士学位论文 第1 章绪论 随着信息产业的飞速发展，为了追求更高性能、更短面市时间和更低制 造成本，适应科技发展和市场竞争的需要，系统设计人员正在将完整的系统 功能集成到单芯片中，从而导致集成电路i c 技术发生了翻天覆地的变化。以 软硬件协同设计、i p ( i n t e l l e c t u a lp r o p e r t y ) 核、超深亚微米技术为支撑的s o c ( s y s t e m o n a c h i p ) 则是超大规模集成电路的发展趋势和主流技术。 1 1 s o c 设计技术概述 随着集成电路设计技术和超深亚微米制造技术的迅速发展，集成电路已 进入片上系统时代。所谓片上系统，也称为系统级芯片( s o c ) ，是指在单一 硅芯片上实现信号采集、转换、存储、处理和i 0 等一个系统的功能。s o c 是在a s i c 的基础上发展起来的，但与a s i c 相比，又具有很多独特的优点。 s o c 实现了一个系统的功能，速度快、集成度高、功耗低。同时，由于s o c 集成了多个功能，使整机成本和体积都大大降低，加快了整机系统更新换代 的速度。s o c 的这些优点正好顺应了通信、电脑、消费类电子产品向轻、薄、 小和低功耗的发展方向，对于移动通信、掌上电脑和多媒体产品的生产厂商 有非常大的吸引力，因此市场对s o c 产品有强烈的需求。 尽管s o c 设计方法只是近几年才发展起来的，但发展势头迅猛。目前 s o c 是微电子业界最热门的话题之。如果说v l s i 促进了p c 的广泛应用 而带来了信息产业的第一次革命，那么s o c 的发展正带来信息产业的第二次 革命。美国、日本和欧洲许多国家的各大半导体公司纷纷加大对s o c 生产线 的投资力度，建立新的s o c 生产线。e d a 厂商也不断推出新的设计工具和 环境，提出新的s o c 设计方法，方便和加快s o c 的设计。 s o c 芯片的集成度越来越高，单芯片e 的集成度达到几千万个门，操作 频率达到5 0 0 1 0 0 0 m h z ，而且投放市场的时问要求越来越短。为了实现这 样的系统，设计者越来越依赖于i p 模块的重用。因为i p 模块是预先设计好 哈尔滨。【：程大学硕+ 学位论文 的，并经过了预先的验证，设计者可以把更多的注意力集中于整个系统，而 不必考虑各个模块的正确性和性能。但是，使用i p 模块构造s o c 是一个费 时费力的过程，而且很容易出错。随着可重用i p 模块的增加，以及人们越来 越多地依赖i p 模块进行s o c 的设计，i p 模块的标准化显得非常重要。一些 s o c 厂商建立了自己的片上总线标准，提出了自己的坤模块设计标准。但 是，现在的s o c 设计不再单纯使用某一个厂商的i p 模块，而是多厂商i p 模 块的组合，所以出现了v s ；i a ( v i r t u a ls o c k e ti n t e r f a c ea i l i a n c e ) l i j 和a s i c c o u n c i l 这样的标准化组织，为s o c 的设计建立相应的设计规范和标准【2 】。 s o c 设计的复杂性进一步提高了系统抽象描述的层次。对系统级描述的 语言和s o c 设计的方法提出了新的要求。嵌入式软件占整个芯片功能的 5 0 - - 9 0 ，所以系统的软硬件协同设计和测试是一项重要的工作。使用传 统的h d l ( v h d l 或v e r i l o g ) 产生了软件设计语言不一致的问题，为系统的 设计、验证和测试带来了很大的不便。因为c c + + 是目前芯片结构设计师、 系统工程师和软件工程师使用的主要语言。所以使用基于c 的方法进行硬件 建模是未来的一个发展方向，它提供更自然的方式划分软件和硬件之间的功 能。高层次的抽象描述也带来了不同e d a 厂商的不同工具之间互操作问题， o l a 标准试图实现这些工具之间的互操作，统一访问不同厂商的1 p 模块库。 1 2 s o c 的自顶向下设计方式 传统的专用集成电路( a s i c ) 设计采用自底向上( b o t t o m u p ) 的方式 较多，其基本思路是从系统需求出发，根据已存在的硬件基本单元划分设计 树最末枝的单元模块。硬件基本单元是由e d a 库提供，或外购及其它项目已 开发出的单元。b o t t o m u p 设计是基于简单1 c 设计提出的方式，已不能满足 复杂a s i c 特别是s o c 芯片的设计要求。 自顶向下( t o p d o w n ) 方式整体考虑了s o c 芯片软、硬件系统设计的 要求。把系统需求、处理机制、芯片体系结构、各层次电路及器件、算法模 型、软件结构、协同验证等紧密结合起来，从而用单个或极少几个芯片完成 整个系统的功能，其设计流程如图1 1 所示，分为咀下几个主要步骤： 1 ) 系统总体方案设计：卷片系统功能、指标定义、需求分析、产品市场 哈尔滨i ：程大学硕 ：学位论文 定位，软硬件划分、指标分解等整体方案论证。 2 ) 软硬件方案设计：确定软、硬件体系结构，模块功能的详细描述及 技术指标要求，时序及接口定义等工作。 3 ) 模块设计开发：完成硬件模块的开发，行为及时序仿真测试，底层硬 件驱动程序编写，算法设计及仿真，协议和应用软件的设计与开发。对于复 杂的功能模块，可进一步划分成子模块。在算法仿真时，根据系统指标的要 求划分出信号处理硬件加速模块。 4 ) 软硬件协同仿真测试：主要测试系统方案和软、硬件模块设计功能 的正确性。 5 ) 样机平台的测试：主要是自建或专用的验证平台，测试整个设计的功 能、性能指标是否达到要求。 图1 _ 1t o p d o w n 设计流程 t o p d o w n 设计过程体现了层次化及目标化的系统设计思想。在s o c 芯 片设计时具有如下的优点： 1 ) 整体考虑了s o c 芯片中软件及硬件设计。s o c 芯片通常内嵌了m c u 和d s p 处理器，软件包含了硬件驱动、算法、协议、应用程序、实时操作系 统等。在设计工作中软件占有相当大的比例，软件的难度和工作量随芯片复 杂度的增加而进一步提高。 2 ) 采用软硬件协同设计，使软硬件丌发、测试工作并行进行。 哈尔滨1 样人学硕十学位论文 3 ) 有利于i p 核的采用和可重用i p 核成果的产生。 4 ) 更加完善的测试、验证手段。由于a s i c 的集成度、复杂度不断增加 和投片费用较高，芯片功能和性能测试以及验证在s o c 开发工作中起着越来 越重要的作用。 5 ) 增加了对投片厂家选择的灵活性，符合当今芯片设计中，系统及前端 设计与后端工作无关性的准则。 综上所述，采用t o p d o w n 方式设计s o c 芯片，可充分保证芯片功能和 性能技术指标达到设计要求，有利于缩短开发周期，降低开发成本及产品的 单片价格。 1 3s o c 中的i p 模块重用技术 1 3 1 i p 模块 s o c 芯片不仅集成了一个复杂的系统，而且芯片的集成度高、速度快， 还要求解决各种干扰问题，要毫无问题地完成系统级设计，是一项十分艰巨 的任务。现在电子产品的生命期正在不断缩短，要求完成芯片设计的时间更 短，如果从头完成s o c 芯片的设计，不仅浪费大量的人力物力，而且难以在 规定的时间内完成设计。为了加快s o c 的设计，提高s o c 的设计效率和可 靠性，人们把经过验证的i c 电路以模块的形式加入s o c 芯片的设计，从而 简化芯片设计，缩短设计时间。这些已验证的可重复使用的i c 模块就称为 i p ( 知识产权) 模块，也称为系统宏单元、虚拟部件或芯核，这种设计方法 就称为基于口模块的s o c 设计，或称为基于核的s o c 设计【3 l o i p 模块通常分为3 类n 即硬i p 、软i p 和固i p 。 1 ) 硬i p 的电路布局和工艺是固定的，有全物理的晶体管和互连掩膜信 息，完成了全部的前端和后端设计，制造也已固定。它的特点是提供可预测 的性能和快速的设计，但灵活性差，难以移植到不同的加工工艺。 2 ) 软i p 通常在抽象的较高层次描述，包括逻辑描述、网表和不能物理 实现的用于测试的文档。软i p 需要综合，进行布局布线等。它的特点是灵活 性大，可移植性好，用户能方便地把r t l 和门级h d l 表达的软i p 修改为自 哈尔滨r 程人学硕仁学位论文 己所需要的设计，综合到选定的加工工艺上。但与硬i p 相比，可预测性差， 设计时间长。 3 ) 固i p 是介于硬1 p 和软i p 之间的i p ，通常以r t l 代码和对应具体工 艺网表的混合形式提供。固i p 既不是独立的，也不是固定的，可以根据用户 的需要进行修改，使它适合于某种可实现的工艺过程。 1 3 2 l p 模块的重用 s o c 设计的最大挑战之一是i p 模块的有效使用和重用。设计一种复杂 的系统芯片需要很长的时间，系统设计、软件、微电子研究开发的专业人员 必须组成紧密合作的实体，以保证产品及时上市。近年来电子产品的更新换 代周期不断缩短，而系统芯片的设计时间却在增长。采用传统的设计方法， 这一矛盾必将进一步加居0 。s o c 设计普遍采用基于已有i p 模块的设计方法。 芯片的设计从以硬件为中心转向以软件为中心，芯片设计不再是门级设计， 而是在i p 模块和i p 接口级的设计。i p 模块重用，除能缩短s o c 芯片设计的 时间外，还能降低设计和制造成本，提高可靠性，因此将会给i c 产业和电子 工业带来巨大的商业利益，并引起i c 产业结构的变革。可重用i p 模块越多， 设计过程的效率越高。v s i a 估计从1 9 9 1 年到2 0 0 1 年，芯片设计经历了9 0 新模块和1 0 重用模块到1 0 新模块到9 0 重用模块的过程【2 】o 因为i p 模块是预先设计好的，并经过了预先的验证，设计者可以把注意 力集中于整个系统，而不必考虑各个模块的正确性和性能。所以使用i p 模块 可简化系统设计，缩短设计时间。 1 3 3l p 模块重用面临的问题 使用基于口模块的设计方法简化了系统设计，缩短了设计时间，但随着 s o c 复杂性的提高和设计时问要求的进一步缩短，l p 模块越来越多，为i p 模块的重用带来了许多问题。 首先，由于构建一个系统的过程是很复杂的，要求设计者决定使用什么 类型的c p u 、软件和硬件要实现的功能、系统达到的性能、系统的目标应用 等。这些问题决定了我们要使用什么i p 模块，但存许多情况下，这些问题只 有在设计过程的后期才能得出答案。 哈尔滨工科人学硕七学位论文 其次，如果i p 模块集成到s o c 中的工作主要由手工进行，很容易出错， 它要求设计者完全理解复杂i p 模块的功能、接口和电气特性，如微处理器、 存储器控制器、总线仲裁器等。 另外，由于系统的复杂性很高，很难达到完全的时序吻合，而且系统的 物理设计也是一个大问题，即使每个i p 模块的布局是预先定义的，但把它们 集成在一起仍会产生一些不可预见的问题，如噪声，这对系统的性能有很大 的影响。另外，系统验证是s o c 设计的主要瓶颈之一。即使i p 模块是预先 验证好的，并不意味着它们集成在一起时整个系统就没有问题，即使各个模 块是：正确的，各种接口和时序问题也会引起系统故障。 i p 模块的标准化是目前要解决的一个重要问题。由于缺少统一的业界标 准和有效的接口综合工具，使不同供应商的i p 模块很难集成到同一个s o c 中。为了解决i p 模块的接口和通信协议问题，s o c 的主要供应商开发了自 己的s o c 片上总线结构标准，如m m 的c o r e c o n n c c t 和a r m 的a m b a ， 它们通常与一个处理器体系结构关联，如p o w e r p c 或a r m 。 1 4 基于平台的s 0 0 设计方法 由于s o c 设计复杂性和集成度的提高，以及s o c 芯片上市时间要求的 进一步缩短，使基于i p 模块的设计方法面临着巨大的挑战，设计重用和设计 自动化成为s o c 设计的主要技术障碍，需要使用新的设计方法解决这些问 题。基于平台的设计方法【删将功能( 应用) 与实现( 平台) 分开。应用开发 采用结构化的语义模型来描述，而平台的开发可以独立进行，使用应用软件 开发与平台配置相结合的方式，由应用专家( 而不是硬件专家) 完成芯片的 设计。基于平台的设计过程主要包括模块生成、i p 模块重用、芯片集成和软 件开发等部分。在系统级软硬件协同设计中，平台可以描述为抽象的体系结 构和组件模型，应用功能映射到平台体系结构，实现软硬件的划分，进行抽 象的虚拟分析，如图1 2 所示。它要求使用新的开发工具，包括应用开发环 境、“映射”工具以及平台分析和配置工具。 堕0 j 鋈土垒垒耋至。! ；兰篁童銮 图1 2 基于平台的设计方法 基于平台的设计方法使用标准的预先设计和验证的基本构件，如处理器 核、存储器模块和接口模块等，使s o c 的设计更加简单，然后在设计中插入 定制逻辑，加入特定的软件程序。这个方法的主要好处是减少了设计和验证 的工作量，缩短了芯片的开发时间，增加了系统的可预测性，降低了设计风 险。 这种高度参数化的复杂s o c 平台体系结构需要有可编程的模拟仿真环 境支撑。这种平台可以h d l 源码或实际芯片的形式提供。开发这样复杂的 s o c 平台体系结构及其支撑环境，以及原型芯片往往需要投入巨大的脑力和 资金。不过这种初期的投资成本，可以分摊到以后系统应用的开发设计中。 由于芯片集成度与开发者生产力之间不断增长的巨大鸿沟，这种基于平台的 s o c 设计方法是未来高集成度芯片设计重用的主要方式之一。 1 4 1 s o c 设计平台的分类 s o c 设计平台可以分成自行设计平台、可定制平台、特定应用平台和可 编程平台。 1 ) 自行设计的平台是指用户自己创建的平台，允许用户使用特定的模块 和定制逻辑。用户必须考虑非标准模块到总线的集成，自行设计并发通信。 a s i c 背板和片上总线标准就属于这种平台。 2 ) 可定制平台是不完整的平台，仅完成大约8 0 ，为定制逻辑的快速 集成提供可编程逻辑。它在可扩展性和可配置性方面有定的限制，j 出片使 用效率较低，集成逻辑的验证有一定风险性。 哈尔滨t 程人学硕 ：学位论文 3 ) 特定应用平台以某一应用领域为目标( 如数码相机、视频等) ，提供 有限的可编程性，并提供硬编码的应用加速器。但它的灵活性差，特别是缺 少i o 和硬件的灵活性。这种类型的平台有p h i l i p s 的n e x p e r i a 、e q u a t o rm a p 等媒体处理器，以及c p o r t 公司和s i l i c o n s p i c e 公司的网络处理器。 4 ) 可编程平台提供很强的可配置性和可编程性，通过加入一系列的可扩 展可配置处理器和可编程i o ，支持各种应用，但高度的可编程性带来一定 的系统开销( 指令存储器和处理器控制器) 。可编程平台有i m p r o v 的p s a 和 s u nm i c r o s y s t e m 的m a j c 。 一个平台可以有多级可配置性平台的宏结构( 如处理器核的数目和核之 间的互连) ，i o 功能和资源、各个处理器的特性、以及用户自定义的加速器。 高度的可配置件允许设计者根据应用的需要裁剪可用资源，允许数据和指令 存储器的流水线化，优化定制处理器和加速器的使用，以及根据系统要求来 匹配i o 。 1 4 2 平台中的处理器核 处理器核是任何平台实现的核心，常用的处理器核有以下几类： 1 ) 传统r i s c d s p 。它的特征是每条指令一个操作，处理能力通常在1 0 b 3 0 0 m i p s 的范围内，功耗为1 1 2 m i p s w ( a r m 9 ) 至5 0 m l p 趴( o a k t e a k ) 。 这些处理器核的优点是有一个软件解决方案库，并且产生相对小的代码。 2 ) 超标量v l i w 。每条指令多个操作，提供“细粒度”并行性。典型的 性能指标是1 6 0 0m i p s ( 2 0 0m h z t ic 6 2 0 1 ) 和1 3b o p s ( i o o m h z 的i m p r o v j a z z ) 。i m p r o vj a z z 的功耗是1 3 0m i p s w 。超标量结构允许指令的动态调度， 硬件复杂而编译器简单；v l i w 结构使用静态调度方法，硬件简单，但编译 器复杂。 3 ) 伪i l 驯混合i l p 。采用有限的指令集并行( i l p ) ，并增加传统的处理 方法，如使用r i s c 技术，再加上v l i w 来加速关键循环的处理，v l i w 部 分通常是由应用开发者硬编码的。 1 4 3s o c 平台配置空间的复杂性 由于l p 核的多样性( 存储器、内存、d m a 控制器、编码解码器、总线 哈尔滨i 。群大学硕士学位论文 等) 及其可优化参数的矛盾性( 性能、功率、面积等) ，使得s o c 的设计空 间极其复杂。能否找到一组最优的参数，直接关系到应用设计的成败。另外， s o c 的设计空间是由问题来说明的，通常是多维、非连续的不规范空间，因 而无法完全搜索整个设计空间。s o c 系统综合的主要任务之一就是针对具体 应用在可能的设计空间中找到一组满足约束的优化的i p 可行配置集，其本质 是求多目标优化问题的最优解。 1 5 本文的主要工作 近年来参数化系统设计研究是v l s i 领域内的一大热点，有很多学者在 设计空间搜索领域从事研究工作。f o m a c i a r iw 使用敏感度分析方法为c a c h e 存储器搜索最小化功率时延时间积配置【7 | 。a s c i ag 使用单目标遗传算法为存 储器层级结构搜索基于面积、功率、寻址时间的优化配置吼t e i c hj 基于层 次模式提出p f a 方法用于嵌入式系统空间搜索【9 h a u b e l tc 又对该算法进行 了改进【l o 】。d g i v a r g i st 基于c p u 、c a c h e s 、主存、总线使用穷举方法对功率 性能设计空间进行搜索【l ”。 本文基于多目标演化算法提出了一个新的s o c 设计空间搜索策略，并将 其集成到p l a t u n e 平台，通过与敏感度分析搜索策略的实验对比，证明了该策 略的有效性。主要工作包括如下几方面： 1 ) 分析了s o c 设计面临的主要问题，对主流设计技术进行了归纳总结。 2 ) 对s o c 系统综合的任务、方法、形式化描述进行了深入的研究。 3 ) 对多目标演化算法进行了分类分析，对典型的算法进行了对比研究。 4 ) 利用参数依赖性概念，有效缩减了s o c 设计空间。 5 ) 提出根据设计空间阈值选择搜索算法的搜索策略。 6 ) 提出一个用于s o c 设计空间搜索的多目标演化算法。 7 ) 在p l a t u n e 上对新搜索策略与敏感分析策略进行集成验证，并对3 个 应用上的实验统计数据加以对比分析。 本论文受国家自然科学基金( 6 0 2 7 3 0 8 1 ) 资助研究。 哈尔滨，t ：l t d 大学硕士学位论文 第2 章s o o 系统级综合的形式化描述 先进的s o c 高级综合工具可以帮助设计者显著的缩短开发时间，以至更 复杂的设计可以在更短的时间内完成。省下时间可以考察自动综合工具不同 的系统实现方式，这一过程通常称为设计空间搜索。人们渐渐地发现对于 c a d 的研究已经达到一个更高的抽象级别系统级。 2 1 $ 0 0 系统综合概述 2 1 1 s o o 系统综合的任务 s o c 系统综合是一个将应用的行为级描述( 算法、任务、过程等功能性 描述) 映射到结构级描述( 异质软硬件体系结构中，包括处理器、总线、内 存、r o m 、存储程序等) 的优化过程。 具体说来s o c 的系统综合要完成三个任务【1 2 】： 1 ) 选择合适的体系结构。 2 ) 将行为级描述映射到选定的体系结构上。 3 ) 搜索设计空间以找到满足一定代价和性能约束的配置集。 图2 1 给出了s o c 系统综合的过程。其中a ) 子图是一个基于数据流图 的功能描述，作为综合工具的输入；子图是综合工具的映射约束；c ) 子 图是目标结构模板；d ) 子图是综合优化工具；e ) 子图使用演化算法进行优 化得到的实现集。整个过程实质就是一个设计空问搜索的过程，过程的最终 结果是一组优化实现，这组实现相互之间可能具有完全不同的体系结构特征， 讵如图所示的那样。 2 1 2 $ 0 0 系统综合的方法 有很多方法已用于s o c 的系统综合，一些方法用于对控制为主的系统 ( c o n t r o l - d o m i n a n ts y s t e m s ) 进行综合，另一些方法用于处理数据流为主的设计 ( d a t a f l o w d o m i n a n td e s i g n ) 。 哈尔滨【程人学硕士学位论文 通信节 d ) 系统描述图 用 多目标 演化算法 搜索设计空间 对点总线 目标函数 配置参数 弦雌 墨 图2 1s o c 系统综合的过程 从系统综合的目标结构( t a r g e ta r c h i t e c u t e s ) 来看，又可分为三类： 1 ) 基于v l s i 的专用控制数据通路( d e d i c a t e dc o n t r o la n d d a t ap a t hi nv l s i 、 1 3 - 1 5 j 。这类方法将详细的功能描述划分为专用的硬件体系结构，该体系结构 包括控制通路和数据通路。 2 ) 多芯片专用v l s i 体系结构( m u l t i c h i p d e d i c a t e dv l s i a r c h i t e c t u r e ) i x 6 】。 这类方法关注多芯片v l s l 解决方案，系统芯片的所有功能都映射到总线互 连的多芯片组的体系结构上。 3 ) 硬软件体系结构( h a r d w a r e s o f t w a r ea r c h i t e c t u r e ) 。大多数方法都将目 标指向到固定的目标体系结构上。文献1 1 7 的目标足一个处理器和通过内存 映射i o 通信的定制硬件，文献 1 8 1 的目标是一个r i s c 处理器、多个定制块 和通过单c s p 协议通信的预定义硬件模块，文献1 1 9 1 的目标是一个可编程的 哈尔滨i ：程大学硕士学位论文 组件和多个通过系统总线通信的硬件模块。 另外，按照综合中所采用的优化技术，综合方法又可分为两类： 1 ) 精确方法。这类方法有穷举搜索法和整数线性规划法。这种方法的缺 点是运行时间长，仅当对性能和代价有高度精确要求且目标空间较小的情况 下，值得使用。 2 ) 启发式方法。g u p t ar 提出使用启发式方法进行硬，软件划分，具体做 法是先将系统的所有功能尽可能的映射为硬件结构，然后在保证系统性能约 束的前提下将尽可能多的功能用处理器的来实现【1 9 】。e r n s tr 提出先将系统的 所有功能尽可能的映射为软件与处理器的结构，然后将系统的一部分功能用 硬件来实现，直到满足系统的时间约束为止1 1 8 1 。 2 1 3 演化算法用于s o c 系统综合的优点 演化算法是一种很好的系统综合技术，具体表现在如下三点【1 2 l ： 1 ) 演化算法可以同时对组实现种群( ap o p u l a t i o no f i m p l e m e n t a t i o n s ) 进 行优化。 2 ) 演化算法不要求代价函数( q u a l i t y c o s tf u n c t i o n ) 是线性的。 3 ) 演化算法对于大型非凸空间的搜索性能表现良好。 2 2s o c 系统综合的形式化描述 2 2 1 系统功能的形式化描述 系统的功能描述以及目标体系结构都用统一的依赖 雪( d e p e n d e n c eg r a p h l g ( v ，e ) 描述。综合工具定义的映射约束用描述图f s p e c i f i c a t i o n g r a p h ) g ( k ，b ) 描述。与描述图的节点和边相关联的操作是激活，这是分 配和绑定的一个特征。以下将依次给出每个图的定义和示例。 定义2 1 依赖图( d e p e n d e n c eg r a p h ) 依赖图是一个有向图g ( v ，e ) ， 其中矿是节点的有穷集合，e ( v v ) 是有向边集合。 示例1 描述一个给定算法的依赖图称为问题图( p r o b l e mg r a p h ) q ( ， e ，) ，其中作集合中的节点代表功能操作或通信操作，e ，集合中的边代表操 作之间的偏序关系。图2 2 给出了通过在任务级数据流图的每条边中插入通 哈尔滨【：样人学硕十学位论文 信节点而得到的问题图。 a ) 系统的体系结构b ) 相应的结构图q 图2 3 一个结构图g 。( ，只) 示例3 描述包括多芯片组的目标体系结构的依赖图，称为芯片l 蛩( c h i p 哈尔滨i 程人学硕士学位论文 g r a p h ) g 。( ，e 。o 其中k 集合中的节点代表功能资源和通信资源，艮集 合中的边代表资源之间的有向连接。图2 4 给出了一个包括2 个i c ( c h i p l 和c h l p 2 ) 和1 条双向点对点总线资源的目标体系结构以及相应的芯片图 g c 。 片外总线 b ) n c h i p i 甄 () 片外总线 碰 () c h i p 2 a ) 系统的多芯片结构b ) 相应的芯片图q 图2 4 一个芯片图g r ( k ，墨) 下面将给出描述图的定义，下一节分配和绑定的形式化描述都要用到描 述图。 定义2 2 描述l 羽( s p e c i f i c a t i o ng r a p h ) 描述图是一个有向图g ( k ，e s ) ， 包括d 个依赖图g 】( k ，e i ) ，1 s fs d 和一个映射边集合。其中k ；u f 。k ， e si 峨leu ，e m ；u ：1 ，k k + 1 ，1 s f e d a 示例4 可以看出描述图包括几层依赖图和连接邻近两个依赖图结点的 映射边。这些层次对应不同的抽象级别，算法级描述用问题图，结构级描述 用结构图，系统级描述用芯片图。有向边代表用户定义的约束：起始点可以 由目标点来实现。图2 5 给出了一个描述图，该图包括了问题图g 。、结构图 g 、芯片图g 。，以及描述所有映射约束的约束边“。和：。由图可以看出 操作h 只能在。上执行，操作v 。和v ：可以在。和。：上执行，通信操 作屿可以由。、k 。或。执行a 约束还进一步描述出r i s c 处理器、硬 件模块h w m l 与h w m 2 以及通信模块b r l 与b r 2 可以在c h i p l 上实现， 此外b r l 还可以出片外总线o c b 来实现。 为了描述一个给定的映射或实现，下面给出描述图激活的定义，下一节 分配和绑定的形式化描述也要用到此概念。 哈尔滨r 程大学硕士学位论文 定义2 3 激活( a c t i v a t i o n ) 描述图q ( k ，b ) 的激活是一个 ku 风h o ，1 ) 的过程，是一个对每个节点i - k 和每条边e e 。赋值1 ( 激 活) 和0 ( 不激活) 的过程。 图2 5 一个描述图g ( k ，e 。) 2 2 2 系统综合的形式化描述 定义2 4 分配( a l l o c a t i o n ) 一个给定描述图g ( k ，e s ) 的一个分配a 是一 个依赖图所有激活节点和边的子集。 a = 唧u a d ，= v ki 口( v ) = 1 ) d = u e ei a ( e ) = 1 ) l 1 定义2 5 绑定( b i n d i n 曲一个给定描述图g 。( k ，e s ) 的个绑定卢是e 0 的一个子集，包括所有激活映射边。 哈尔滨t 程人学硕士学位论文 卢i 和i n ( e ) = n 定义2 6 可行绑定( f e a s i b l eb i n d i n g ) 给定一个描述图q ( k ，e s ) 和一个 分配a ，满足以下条件的绑定称为可行绑定： 1 ) 每个激活边e e f l 开始且结束于激活节点： v e = ( v ，f ) 卢：v ，f , e a 2 ) 对每个激活节点v o ，且v k ，1 s f d ，有且只有一条输出边e 巨， 1 s i d 被激活： i e 芦l e = ( v ，i ) ，i k + 。) i ；1 3 ) 对每一个激活边e t ( u ，y ，) a k e e e , ，1 s i z + ，对于所有的边e 。( u ，v ，) e v ，有： t ( v ，) r ( q ) + d e l a y ( v i ，芦) r ( v 。) 代表节点u 的开始时问，延迟取决于实际的绑定。 定义2 9 实现( i m p l c m e n t a t i o n ) 给定一个描述图g ，一个可行的实现由 哈尔滨1 程人学硕十学位论文 三部分构成( a ，卢，r ) ，其中a 是一个分配，卢是一个可行绑定，r 是一个调度。 示例5 图2 6 给出了图2 5 所示描述图的一个实现。没有分配的节点和 边，以及没有激活的边e e “用虚线给出n 这罩节点的分配唧= v 。， v h w m l ，v b r l ，v c h i p i ) 绑定卢2 “，v r i s c ) ，( v 2v 1 2 1 s c ) ，电，v h w l ) ，0 4 ，v p d s c ) ( v 5 ，v 1 ) ，( v 6 ，v