（计算机科学与技术专业论文）基于应用程序特征分析的soc任务分配技术研究与实现.pdf

国防科学技术大学研究生院硕士学位论文 摘要 随着超大规模集成电路技术的迅速发展，片上系统( s y s t e m 0 1 1 c h i p ，s o c ) 的 集成度不断增高，系统功能日益丰富，设计复杂性越来越大，s o c 设计方法学面 临严峻的技术挑战。s o c 设计的主要目标是能高效运行系统应用程序，并实现低 功耗和低成本。对应用程序特征进行充分而有效的分析，是设计实现s o c 应用高 效能的有效技术途径。本文面向粗粒度可重构密码处理s o c 体系结构设计和系统 任务分配的需求，研究s o c 应用程序特征分析方法，研究基于应用特征分析的s o c 任务分配方法，以及相应工具的设计实现技术。完成的主要工作如下： 1 粗粒度可重构密码处理s o c 采用可重构协处理器进行加速，协处理器可重构运 算部件的指令集对应用程序的适用程度，决定了粗粒度可重构加密s o c 芯片在 实际应用中的效果。本文以应用程序特征分析为基础，提出了一种可有效支持 可重构协处理器指令集设计的应用特征自动分析方法。该方法可自动生成可视 化的密码算法控制流图，自动分析程序的计算特征、指令序列特征、操作数特 征，循环特征、循环结构特征和核心循环特征、自动提取核心代码块等，为粗 粒度可重构密码处理s o c 体系结构设计，提供可靠的分析结果。 2 提出了一种基于应用程序特征分析的可重构密码处理s o c 任务分配方法。该 方法使用图节点多着色模型描述任务分配问题，并使用课题组提出的进化蚁群 算法进行分配空间探索，寻找高质量的分配方案。实验结果表明：相对于同类 典型方法，本文方法可以获得高质量的分配解，并较大幅度地加快了收敛速度， 对提高粗粒度可重构加密s o c 处理性能具有重要作用。 3 采用所提出的方法，实现了一个s o c 应用程序特征分析工具原型和一个基于 应用程序特征分析的s o c 任务分配工具原型。利用程序特征分析工具对典型的 几种加密算法进行分析，得到了可重构协处理器指令集和体系结构设计所需的 特征信息；在粗粒度可重构加密s o c 体系结构确定的基础上，利用基于应用程 序特征分析的s o c 任务分配工具，对典型密码应用处理任务进行自动分配，结 果以简明直观的方式提供给s o c 设计人员，有利于提高可重构密码处理s o c 任务分配的质量和效率。典型的应用实例，验证了本文方法的有效性。 本文方法不仅可以辅助支持粗粒度可重构s o c 专用指令集设计与s o c 任 务分配工作，同时也可为其它领域的程序分析、s o c 编译优化等工作提供一定 的设计辅助指导。 主题词：多处理器片上系统，任务分配，程序分析，密码处理，蚁群优化， 遗传算法 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t a st h ev l s i t e c h n o l o g yd e v e l o p i n g s y s t e m o n c h i p sa l s od e v e l o pv e r yf a s t b o t l li nt h ei n t e g r a t i o na n dt h ep o w e r f u lf u n c t i o n a n dt h em o r ec o m p l e xd e s i g n i n gw o r k c o m ea tt h es a m et i m e s y s t e mo nc h i p sa i m sa th i g hp e r f o r m a n c ei nt h es p e c i a lf i e l d a n dl o wd o w nt h ec o s ta n dt h ep o w e r e f f e c t i v ea n a l y s i so ft h ep r o g r a m m ei s n e e d e d ，w h i c hi sae f f i c i e n c yw a yt od e s i g nas y s t e m o n c h i p s a c c o r d i n gt ot h e p r o g r a mf e a t u r ea n a l y s i s ，t h ep a p e rp r o p o s e da na u t o m a t i ct a s ka l l o c a t i o nm e t h o d w h i c hf o r t h ed e s i g n i n go fs p e c i f i ci n s t r u c t i o n sa n dt h em i d d l ec o d e ，a n dt h e n ，b a s e do n t h er e s u l to fp r o g r a mf e a t u r ea n a l y s i s ，w ep r o p o s ea l la l l o c a t i o nm e t h o df o rt h ee n c r y p t s o c i nt h i sp a p e r ，w es t u d ys o ch a r d w a r e s o f t w a r ec o d e s i g na n dd e s i g nr e u s i n g t e c h n o l o g i e s t h ef o l l o w i n ga c h i e v e m e n t si sr e s u l t e d ： f i r 晚s o cu s u a l l ya d o p t sa na p p l i c a t i o n s p e c i f i ci n s t r u c t i o n s e tp r o c e s s o r ( a s i p ) t oc a r r y i n go u ta c c e l e r a t i o n ，a n dt h ed e s i g no fs p e c i f i ci n s t r u c t i o n si so n eo ft h ek e y p o i n t si na s i pd e s i g n a p p l i c a b i l i t yo fs p e c i f i ci n s t r u c t i o n sa n di t sa p p l i c a t i o nf i e l d d e t e r m i n et h ee f f e c to ft h es o ci ns p e c i f i ca p p l i c a t i o n s oi tn e e d se f f e c t i v ea n a l y s i so f t h ep r o g r a m m ew h e nd e s i g n i n gs p e c i f i ci n s t r u c t i o n s t h ee f f i c i e n to fa p p l i c a t i o n f e a t u r e sa n a l y s i sd e t e r m i n e st h ed e s i g n i n gq u a l i t yo fs p e c i f i ci n s t r u c t i o n sa n dt h et h e e f f e c to ft h es o ci ns p e c i f i ca p p l i c a t i o n 0 n l ya f t e rs u f f i c i e n ta n de m c i e n ta n a l y s i so f t h ea p p l i c a t i o nf e a t u r e ，w ec a ne f f e c t i v e l yd i r e c tt h ed e s i g no fs p e c i f i ci n s t r u c t i o n sa n d i m p r o v et h ep e r f o r m a n c eo fs o ci nt h i sa p p l i c a t i o nf i e l d a f t e rt h ea c h i e v e m e n ti s d e s i g n e d ，b a s e do nt h ea n a l y s i so fp r o g r a mf e a t u r e ，w en e e de f f e c t i v et a s ka l l o c a t i o n m e t h o dt oc a r r yo u tt h ee f 丘c i e n ta l l o c a t i o no fp r o g r a mi ns p e c i a lf i e l di no r d e rt o i m p r o v et h ei n t e g r a t e dp e r f o r m a n c eo fs o cd e s i g n s e c o n d ，t h i sp a p e rp r o p o s e da na u t o m a t i ct a s ka l l o c a t i o nm e t h o dw h i c hf o rt h e d e s i g n i n go fs p e c i f i ci n s t r u c t i o n sa n dt h em i d d l ec o d e a n dt h e n ，b a s e do nt h er e s u l to f p r o g r a mf e a t u r ea n a l y s i s 。w ep r o p o s ea l la l l o c a t i o nm e t h o df o rt h ee n c r y p ts o c n l e t a s ka l l o c a t i o np r o b l e mi sd e f i n e du s i n gg r a p hn o d e c o l o r i n gm o d e l a n dt h e e v o l u t i o n a la n t c o l o n yo p t i m i z a t i o ni sp r o p o s e da n da p p l i e dt o f i n dh i g h q u a l i t y a l l o c a t i o ns c h e m e t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep r o p o s e dm e t h o dc a l lf i n d b e t t e ra l l o c a t i o ns c h e m ew i t h i nl e s st i m ec o m p a r e dw i t ho t h e rm e t h o d w h i c hi m p r o v e s t h es y s t e m o n - c h i pp e r f o r m a n c e f i n a l l y ，b a s e do nt h ea b o v em e t h o d t h ep a p e rr e a l i z et h ec o r r e s p o n d i n gp r o g r a m f e a t u r ea n a l y s i sa n dt a s ka l l o c a t i o nt 0 0 1 a n dw eu s et h i st o o lt og e tc h a r a c t e r i z e so f c o n t r o l ，i n s t r u c t i o nf e a t u r e s c o r ec o m p u t i n ga n do t h e rf e a t u r e sf o ra p p l i c a t i o n s p e c i f i c i n s t r u c t i o n - s e td e s i g n l a t e r ，t h ep a p e rc a r r i e so u tt h et a s ka l l o c a t i o n u s i n gt h e e v a l u a t i v ea n tc o l o n yo p t i m i z a t i o nb a s e do nt h er e l a t i v ei n f o r m a t i o n i t sg r a p h i c s d i s p l a ya n df r i e n d l yi n t e r f a c em a k ei ts i m p l ea n dc o n v e n i e n t i tc a ni m p r o v et h eq u a l i t y a n de 硒c i e n c yo fa p p l i c a t i o ns p e c i f i ci n s t r u c t i o ns e td e s i g n i n g a tt h ee n do ft h i sp a p e r ， w ev a l i d a t et h ee f f i c i e n c yo fo u rm e t h o dt h r o u g he x a m p l e so ft h ea n a l y s i so fs o m e t y p i c a le n c r y p t i o na l g o r i t h m t 1 1 i st o o ln o to n l yc a nb eu s e df o ra s i pi n s t r u c t i o nd e s i g n a n da p p l i c a t i o nt oa r c h i t e c t u r ew o r k ，b u ta l s oi no t h e rf i e l da b o u ta n a l y s i st h e p r o g r a m m e a n df o rt h e c o m p l i e r i t sg r a p h i c sd i s p l a ya n df r i e n d l yi n t e r f a c em a k ei t s i m p l ea n dc o n v e n i e n t k e yw o r d s ：m u l t i p r o c e s s o rs y s t e m o n c h i p ( m p s o c ) t a s ka l l o c a t i o n , a p p l i c a t i o nf e a t u r ea n a l y s i s ，a n tc o l o n yo p t i m i z a t i o n ，g e n e t i ca l g o r i t h m 第i i 页 国防科学技术大学研究生院硕士学位论文 表 目录 表1a e s 计算特征分析结果。2 4 表2d e s 计算特征分析结果2 5 表3m d 5 计算特征分析结果2 5 表4 计算特征分析结果2 6 表5 核心运算分析结果2 7 表6d e s 典型算法函数级运行时间2 7 第1 v 页 国防科学技术大学研究生院硕士学位论文 图1 1 图1 2 图1 3 图1 4 图1 5 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图2 9 图2 1 0 图 图 图 图 1 1 2 3 图3 4 图3 5 图3 6 图3 7 图3 8 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图目录 d e s 算法流程2 a e s 算法流程3 五类可重构计算系统5 c 砒心a 密码可重构加速处理阵列6 应用驱动的s o c 系统设计方法7 程序特征分析与指令集设计、任务分配关系图示意图1 3 本文分析方法与s u i f 平台之间的关系1 4 s u i f l 平台结构1 5 s u i f 2 体系结构图16 s u i f 2 主要模块1 6 s u i f 驱动模块工作示意图18 s u i f 中间表示高层结构1 9 控制流图框架示意图2 0 执行时间分析过程示意图2 3 a e s 、d e s 算法的控制流图2 3 m d 5 算法的控制流图2 4 t g 模型3 0 c r a g 模型3 l 粗粒度可重构s o c 任务分配问题示例3l 有向无环图的双着色模型3 2 s g a 流程图3 3 蚂蚁寻找最短路径示意图3 6 进化蚁群算法流程图3 9 d e s 任务分配图4 5 a i 迮s 工具截图4 6 系统结构示意图4 7 程序预处理模块4 8 特征提取模块4 8 特征信息库模块。4 9 任务分配模块5 0 可视化模块5 0 程序初始化界面5l 第v 页 国防科学技术大学研究生院硕士学位论文 图4 图4 图4 图4 9 程序操作特征分析结果示意图5 2 1 0 寄存器数数据特征分析可视化结果5 2 1 1 立即数数据特征可视化分析结果5 2 1 2 任务分配结果举例5 3 第v i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特别加以标注和致谢的地方外论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目：基王廛旦堡庄挂堑佥堑鲍苎q 丝壹佥墼垫盔塑蕉兰塞塑! 学位论文作者签名： 彪盔主左 日期： 多幻7 年17 - r q 了f 日 学位论文版权使用授权书 本入完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：基士廑囝堡庄鲎焦佥堑鲍苎q 堡堡查佥墼垫盔叠塞生塞塑 学位论文作者签名：2 强要重多五日期：2 卯 年f 2 月3 j 日 作者指导教师张津趔猫眦沪歹年t 月；f 日 国防科学技术大学研究生院硕士学位论文 1 1 1 密码处理 第一章绪论 1 1 研究背景 计算机和电子通讯技术的迅猛发展，使电子化、数字化的趋势已经波及社会 生活的许多方面。随之而来的是各种窃密的黑客技术的发展，对信息安全领域提 出了越来越高的挑战。加密技术是保障信息安全的核心。如何确保重要信息在公 开网络上传送时不会被窃取窃听伪造和篡改，这就要求使用各种加密技术对数据 进行加密处理。目前，加密技术已经从外交和军事领域走向民用，且已发展成为 一门结合数学、计算机科学、电子与通信和微电子等技术的交叉学科，使用加密 技术不仅可以保证信息的机密性，而且可以保证信息的完整性和确定性，防止信 息被篡改、伪造和假冒。 密码技术是信息安全的核心，而密码算法又是密码技术的核心。密码算法可 以看作是一个复杂的函数变换c _ f ( m ，k e y ) 。其中c 代表密文，即加密后得到的 字符序列；m 代表明文即待加密的字符序列，k e y 表示密钥是秘密选定的一个字 符序列，只有拥有解密密钥的收信人可以对密文进行解密即反变换得到明文。所 以密码算法是保障信息安全的核心之核心，其重要性不言而喻。 密码算法通常提供如下安全性服务： ( 1 ) 私密性服务。通常只有经过授权的人才可以访问数据的内容这项服务内容 包括保护用户在两点之间传送的所有数据。 ( 2 ) 完整性服务。只有经过授权的用户才可以修改系统配置和传输的数据。修 改包括写、更改、更改状态、删除、创建和延迟或重发信息。需要指出的是，完 整性服务涉及到主动攻击检测的功能，还可以提供数据恢复功能。 ( 3 ) 验证服务。确保信息的起源拥有合法授权，通过通道传递的信息将被鉴别， 包括用户合法性、数据起源、数据内容、发送时间等内容。这项服务可以被细分 为两个主要的模块：用户验证和数据验证。 ( 4 ) 非否认服务。防止用户否认其在电子世界中的行为。 密码算法主要分以下几类i l l ： 1 1 1 1 对称性密钥算法 对称性密钥算法是指加解密密钥相同，或者解密密钥能够通过加密密钥容易 地计算出来反之亦然。这种算法的主要功能是高速加密数据。对称性密钥算法需 要发送者与接收者在通信之前协商密钥对称性密钥算法的安全性依赖于密钥，泄 第1 页 国防科学技术大学研究生院硕士学位论文 露密钥意味着任何人可以加解密数据，因此会话密钥必须保密。对称性密钥算法 主要有a e s 、d e s 、r c 6 、r c 5 、t e a 等。由于对称算法是大规模数据加密处理主 要使用的算法，现对经典的对称加密算法d e s 与a e s 算法进行相关介绍。 d e s 算法。典型的f e i s t e lc i p h e r ，消息分组块大小6 4 b i t s 、密钥长度6 4 b i t s ， 有效密钥5 6 b i t s ，每8 位有一位为奇偶校验位。算法运算流程如下图所示： 1 6 r o u n d 图1 1d e s 算法流程 算法中的轮计算，每轮计算过程相同，上一轮的计算结果左右交换后进行下 一轮计算。其中i p 和i p 1 为初始操作和最终操作，即根据两个表格，对数据进行 重排序。d e s 的核心功能对一个分组消息进行十六轮的计算。 a e s 算法1 2 i 。数据分组长度1 2 8 位，密钥长度可为1 2 8 、1 9 2 、2 5 6 位。不同 密钥长度需要不同的迭代运算次数，分别进行l o 、1 2 、1 4 次迭代运算。a e s 运算 过程对1 2 8 位输入数据进行字节分组，并按照4 x 4 矩阵的形式进行访问。 第2 页 国防科学技术大学研究生院硕士学位论文 i n i t i a l r o u n d g r o u n d s f i n a l r o u n d 图1 2a e s 算法流程 a e s 加密过程首先将输入数据与子密钥异或，然后进行1 0 轮( 1 2 8 位密钥) 加 密运算。最后进行字节替换、行移位和子密钥异或。 对称性密钥算法一个主要的问题是需要寻找一个有效的手段协商和交换安全 的公共密钥，即密钥分发问题。由此1 9 7 7 年，d i f f i e 和h e l l m a n 提出了公钥密码 体制的概念【l j 。 1 1 1 2 公钥密码算法 公钥密码体制的思想是将加解密密钥分离。任何个人想要发送一个信息到a 方，就必须用s 方的公钥对明文进行加密，并且只有a 能够利用他的私钥对密文 进行解密。在公钥密码算法的执行过程中a 方的私钥在任何时候都是秘密的，它 是基于一个非常简单的数论思想：“将两个素数乘起来是很容易的但是分解该乘积 是非常困难的。”典型的公钥密码算法为r s a 、e c c 算法等。下面以r s a 这一典 型公钥密码算法为例对对公钥密码算法的进行简单的分析。 r s a 公钥密码算法。r s a 密码算法的公钥部分由两个数组成：模n 和一个公 开的指数e ；私钥部分也是由两个数组成：与公钥相同的模1 1 和一个私密的指数d ， 其中模n 是两个大素数p 、q 的乘积，即：n = p q 。 密钥对( e ，n ) 用于加密报文，而密钥对( d ，n ) 用来解密报文。 r s a 算法的加解密过程如下： 1 产生两个大素数p 、q ( 保密) 2 求模r l pq ( 公开) ，q ( n ) = ( p - 1 ) ( q 一1 ) ( 保密) ； 第3 页 国防科学技术大学研究生院硕士学位论文 3 选取满足g c d ( e ，p ( n ) ) = 1 的随机整数e ，公钥e 可以通过欧几里德算法得到。 g c d ( e ，q ( n ) ) = 1 是求e 与叩( n ) 的最大公因数。 4 计算d ，满足de - 1 ( m o d9 ( n ) ) ( 保密) ，密钥d 可以根据求g c d ( n l ，n 2 ) 的斯泰 因算法获得。 设明文为m ，密文为c ，则加密与解密过程为： 加密：c = e ( m ) 兰m d ( m o dn ) 解密：m = d ( c ) = - - cd ( r o o dn ) 由于公钥密码算法较对称密码算法相比复杂，所以一般应用于对少量的信息 进行加密，即应用于对称加密密钥的加密处理上。 i i 1 3 安全h a s h 算法 安全h a s h 算法，目的在于保证传输过程的正确性，常用的安全h a s h 算法 有m d 5 、s h a 2 5 6 、r e p e m d 等。 通常在实际的信息传输中会在信息处理的不同步骤用到以上提到的不同类型 的加密算法。 在本课题中选择了对称性密钥算法中a e s 、d e s 、r c 6 、r c 5 、t e a 算法，公 钥密码算法中的r s a 、e c c 算法，安全h a s h 算法的m d 5 、s h a 2 5 6 、r e p e m d 算法作为研究内容。 1 i 2 粗粒度可重构s o c 当前，越来越多的应用领域同时要求计算的高性能和灵活性，a i s c 和微处理 器两种不同的实现方式显示出了各自的不足。计算密集的应用需要比以前更多的 计算能力来支持，比如科学计算、流视频、图像识别和处理以及交互式服务。同 时，对功耗、生产成本和上市时间的需求也在日益增长，特别是在嵌入式处理器 领域。在面对这些挑战的多种计算实现技术中，可重构计算成为其中最有优势的 计算形式。典型的可重构系统由一个或多个处理器，可重构单元阵列和多个存储 器组成。根据可重构单元阵列与c p u 之间的耦合度，可以把可重构系统分为五类 ( 见图1 3 ) 。 第4 页 国防科学技术大学研究生院硕士学位论文 一 主处理嚣 卜、 c i 口口 日 j c i 、1 手 i 口 口口 o n v oo 可重构处理单元 a 外部独立处理单元 b 可重构功能单元 c 协处理器 一 主处理器 8 c i 窘 一h ? 、一 i o 口口 山一 口口 可重构处理单元 d 附属处理单元 e 嵌入处理器的可重构阵列 图1 3 五类可重构计算系统 可重构处理器由处理单元阵列、互连网络和配置存储器三大部分组成。基本 工作原理是将对应用算法的描述存放在配置存储器中，该配置决定了每个处理单 元的功能和互连网络的数据交换方式，类似定制计算中算法到硬件电路的映射。 通过改变配置存储器的内容，重新构造处理单元和互连网络，可重构处理器能够 处理各种应用算法。可重构处理器定位于与通用微处理器配合作为算法加速协处 理器使用。随着大规模集成电路芯片容量的持续增加，单芯片多核处理器体系结 构已经成为未来发展方向，可重构处理器可与通用微处理器构成异构多核体系结 构。通用微处理器擅长处理复杂控制型应用，与之配合的可重构处理器处理计算 密集型或数据密集型应用，能够发挥各自的优势。 可重构体系结构被分为粗粒度可重构体系结构和细粒度可重构体系结构。细 粒度可重构体系结构由可以实现位级操作的功能单元组成，f p g a 便是典型的结 构；粗粒度可重构体系结构中处理单元主要是执行字节级操作的算术逻辑功能单 第5 页 国防科学技术大学研究生院硕士学位论文 元。 粗粒度可重构体系结构与细粒度结构相比，除了在面积和功耗方面的优势外， 在配置存储器和配置时间的需求上也有很大的降低，同时它还降低了布局布线问 题的复杂度。一些结构引入了多粒度解决方案，通过对资源的绑定可以得到更大 粒度的功能单元，比如4 个4 - b i t 的a l u 可以组成一个1 6 - b i t 的a l u 。德国 k a i s e r s l a u t e m 大学的r 。h a r t e n s t e i n 教授对过去1 0 年来的粗粒度可重构体系结构 进行了总结，认为粗粒度可重构平台由于弥补了a s i c 和微处理器各自的不足，已 经处于主流位置。 课题组自主研发了3 2 位r i s c 通用嵌入式微处理器e s t a r i i i ，并投片成功。面 向密码处理的可重构s o c 也在研发过程中。该s o c 由1 个3 2 位嵌入式主处理器 和1 个可重构加速协处理器组成。嵌入式主处理器为e s t a r i i i ；可重构加速处理器 由多个可配置、可重构的运算处理单元组成，如图1 4 所示。 图1 4c r a p a 密码可重构加速处理阵列 在s o c 的设计过程中，协处理器指令集设计完成之前，需对专用加速部件即 协处理器的加速指令集进行设计，在协处理器指令集设计完成之后，还需对应用 领域的程序面向体系结构进行任务分配工作，以达到系统整体性能的最优。本文 以可重构密码处理s o c 系统结构为研究模型，研究面向s o c 应用程序分析和和任 务分配的技术和方法。 1 1 3s o c 设计方法学 近年来，s o c 系统设计方法不断完善，经历了基于模块的设计、基于i p 核的 设计到基于平台设计的发展过程，设计重用能力不断提高。其中，基于平台的设 第6 页 国防科学技术大学研究生院硕士学位论文 计方法( p l a t f o r mb a s e dd e s i g n ，p b d ) 是一种面向集成、强调系统架构重用的s o c 设计方法，它在已有平台的基础上开发复杂的产品，能有效降低设计风险与开销， 缩短上市时间。 目前，已有的s o c 设计方法仍有三个可改进的地方： ( 1 ) 系统层仅考虑加速特定的核心算法，虽然对特定核心算法可获得高性能， 但缺乏对领域应用的整体性能统筹考虑。 ( 2 ) 可重构s o c 需要高效执行多种算法时，往往在多种算法之间多态切换，未 能提取多种算法计算中的共性，指导体系结构设计，使体系结构适应应用特征从 而发挥出更好的性能。 ( 3 ) 没有明确的应用特征信息指导，导致设计探索空间大、设计复杂性高。 针对当前s o c 设计方法可改进的地方，一种应用驱动的s o c 系统级设计方法 ( a p p l i c a t i o nd r i v e ns o cs y s t e ml e v e ld e s i g n ，a d s l d ) 被提出，该方法以特定应 用为背景，采用软硬件协同设计以提高设计水平，缩短开发时间。其关键在于利 应用特征分析技术，尽早分析领域应用的特征。通过提取应用程序中的操作类型 特征、运算操作次数与频率、依赖性相关性分析等特征，指导性能优化、设计规 划、系统编译等；并将该应用驱动的设计方法集成到已有的层次平台设计中，实 现了一种新的应用驱动的s o c 系统级设计方法。 计平台 系统层建模与仿真系统层 应用特征分析与优化 下嚅广任务划分i j 任务映射j 事务层建模 事务层 性能分析与评价 事务层仿真优化与验证 1 协同编译r 一 i编译优化1 篁堡塑鏖上- 一 肌层建模 r t l 层 性能分析与评价 基于模拟器的仿真与验证 后续设计 辅助工具 图1 5 应用驱动的s o c 系统设计方法 图1 5 为应用驱动的s o c 系统设计方法的示意图，利用这种设计方法进行设 计密码处理s o c 过程中，第一步是对密码算法进行程序特征分析，这是应用驱动 第7 页 墨蓦 一一一一一一一一一 国防科学技术大学研究生院硕士学位论文 的s o c 系统设计方法的基础部分，通过对密码算法进行充分而有效的分析，可以 有效地指导系统层、事务层、r t l 层的建模工作。程序特征不单是体系结构设计 人员设计时的重要参考，更为后续的任务分配提供了量化的依据。程序特征分析 的质量直接决定了整个s o c 设计的好坏。 1 2 i 程序特征分析 1 2 相关研究 程序特征分析一直是计算机研究人员关注的焦点。准确的程序特征能够为计 算机系统及编译器研究人员提供有益参考，使他们的设计有更多的数据支持，而 不仅仅依赖于经验。尤其是当各种专用计算机系统出现后，对特定应用领域程序 特征的分析显得尤为重要。它直接决定了整个系统软、硬件的设计方案和性能优 化策略。程序特征尤其是程序的存储特征和循环特征的分析和研究已经成为提高 计算机系统性能的一个关键。传统的设计中，计算机研究人员主要还是依靠阅读 代码的方式来获取他们需要的程序特征信息，耗费大量的时间和人力，效率低， 准确性和覆盖率也不能保证。近些年来来随着体系结构的发展，程序特征提取和 分析自动化工具也逐步发展起来。 程序特征分析分为公共特征分析和s o c 设计相关的特征分析两大类： 体系结构无关的特征分析。 体系结构无关的特征分析需要分析操作类型特征、运算操作次数与频率、依 赖性相关性分析等特征。体系结构无关的特征分析的结果为性能优化与设计规划 提供依据。 体系结构相关的特征分析。 体系结构相关的特征分析需要可重构密码处理s o c 软硬件协同仿真环境的支 持。在程序运行期间，得到处理器、存储器、总线的运行特征、访存特征、处理 器核间通信特征，发现性能瓶颈，并进行体系结构探索与优化。 如前所述应用驱动的s o c 系统级设计方法( a p p l i c a t i o nd r i v e ns o cs y s t e m l e v e ld e s i g n ，a d s l d ) 也正是以程序特征分析的结果为指导，而展开下一步设计 工作的。 比较典型的分析工具主要有以下几种： s u i f l 3 i ( s t a n f o r du n i v e r s i t yi n t e r m e d i a t ef o r m a t ) 系统。s u i f 是斯坦福大学 开发的一个编译器框架，其为用户提供了程序的中间表示与操作中间表示的一整 套a p i 函数。s u i f 中间表示是对程序层次结构及相关信息的抽象描述其采用层次 化的表示方式，分别描述了文件组、文件、函数、基本块和执行等层次结构上的 第8 页 国防科学技术大学研究生院硕士学位论文 详细信息，例如：符号、操作码、操作数等。s u i f 中间表示涵盖了程序的各个细 节，通过分析s u i f 中间表示可以获取程序信息并实现绝大部分的特征分析功能。 h a l t l 4 l 是个基于编译器的程序动态分析工具。在编译前由用户向应用程序 的合适位置插入观测点和分析例程。在程序执行时调用分析例程统计动态特征。 其分析的粒度包括：指令、基本块、循环和函数等。其可以分析的特征包括：执 行时间、数据使用频率、函数调用次数等。 f l a t l 5 l 是一个指导程序应用分配的循环特征分析工具。分别以g c c 和s i m i c s 为平台实现了对程序静态与动态的分析。可以提取出程序中关键循环，并获得关 键循环的循环频率、执行时间、循环大小及所占比例，为循环的应用分配提供有 效的指导。 a q t i m e i 6 l 是一款调试与性能优化的综合工具，以w i n d o w s 为分析平台，采用 动态分析的方法，得到程序运行时关键的性能信息和内存、资源分配等信息，掌 握应用程序的运行性能。 c l a l 7 i 。c l a ( cl o o pa n a l y z e r ) 是一款基于s u i f 2 中间代码的c 程序循环特征 分析工具。对程序本身特征规律进行了有效的挖掘。和传统的“基于源码”的分析软 件不同，c l a 采用了“基于中间表示”的设计方案，它不直接作用于源程序，而是 通过对源程序的s u i f 中间表示的分析来获取目标程序的信息。c l a 包括循环结构 特征分析和循环内数据相关分析两大部分。 t r i m a n r a n i 引。t r i m a n r a n 是一个编译器的底层平台，开发的目的是为 了研究针对指令级并行体系结构的编译优化技术。它当前主要的方向是e p i c 体系 结构，重点考虑一些编译器后端技术，如指令调度、寄存器分配与机器有关的优 化等。同时t r i m a n r a n 也提供了可扩展的中间程序表示，他有内部语言和文本 语言两种格式，两种格式间有确定的转换规则且容易转换。其中的文本语言叫做 r e b e l 。它能够清楚表达控制流，数据和控制相关及其他信息。 除了上面的几个典型研究，还有很多优秀的程序特征分析方法及工具，例如： a t o m 9 1 、a l t o 1 0 】等。应用特征分析对于专用指令集设计有着重要意义。然而， 现有特征分析工具大多并未对s o c 任务分配与指令集设计提供良好的支持，导致 设计人员在设计时需手工】或同时使用多种分析工具来获取所需信息。这种情况 致使s o c 设计人员工作繁琐、效率低，并难以得到高质量的设计方案。 1 2 2 任务分配 任务分配是粗粒度可重构s o c 设计的关键问题，其以s o c 系统的功能模型分 配到要实现的软硬件体系结构上为目标，在满足系统约束的条件下，使系统整体 性能达到最优。目前，大多数研究以综合优化s o c 系统的延迟、面积和功耗等性 第9 页 国防科学技术大学研究生院硕士学位论文 能指标为目标，利用启发式算法进行任务分配，不同的算法以不同的启发式信息 为指导，从而使搜索过程逐步向最优解收敛。国际上对s o c 任务分配方法的研究 很多，取得了一些成果： 利用遗传算法进行任务分配。p i e r r e a n d r em u d r y 和g u i l l a u m ez u f f e r e y 等人 提出了使用遗传算法进行带约束的s o c 任务分配方法【1 2 1 ，该方法可以通过输入高 层程序和面积约束来进行任务分配，找到不同粒度的功能模块，使其在加速部件 上运行，从而达到提高系统性能的目的。 利用蚁群算法1 1 3 i 进行任务分配。g a n gw a n g ，w e n r u ig o n g 等人提出应用基本 蚁群算法求解s o c 任务分配问题的一般方法【1 4 1 ，该方法综合运用局部和全局启发 式信息，通过蚂蚁间的协作，进行有效的随机搜索，以获取最优划分解。 自动化的编译时划分与调度算法i l 射。t h e e r a y o dw i a n g t o n g 面向细粒度可重构 s o c 实现了自动化的编译时划分与调度算法【1 5 】，并进行了遗传算法、模拟退火和 禁忌搜索的实验比较与分析。 利用启发式算法进行任务分配1 1 6 l 。p r a m o dk 等人，利用启发式算法，面向基 于f p g a 的细粒度可重构s o c ，求解满足系统功耗和时延约束的任务分配。该方 法支持动态可重构，利用了快速的划分机制，达到了功耗与性能的折衷。该方法 是面向细粒度可重构s o c 领域的任务分配方法。 利用超图着色算法进行任务分配1 1 7 1 。y u a n q i n gg u o 提出的超图着色算法是面 缶粗粒度可重构s o c 其中较为典型的分配方法。超图着色算法的基本思想是把输 入的高层应用c 程序转换为c d f g 表示的超图，然后对得到的超图中的任务进行 分组与着色，把高层应用分配到粗粒度可重构体系结构m o n t i u m 上。 现阶段面向细粒度可重构s o c 的任务分配算法相对成熟，但面向粗粒度可重 构s o c 的算法却相对较少。针对已有的粗粒度可重