（物理电子学专业论文）基于gpu的wpawpa2psk高速破译方法研究.pdf

摘要 摘要 w p a ( w i f ip r o t e c t e da c c e s s ) 是一种保护无线网络安全的系统，有w p a 和 w p a 2 两个标准，w p a w p a 2 p s k ( p r e s h a r e d k e y ，预共享密钥) 的破译研究具 有很高的实用价值。为了满足对破译w p a w p a 2 p s k 速度的需求，本文提出了 使用c u d a ( c o m p u t eu n i f i e dd e v i c e 觚h i t e 咖e ，统一计算设备架构) 将 w p a w p a 2 p s k 破译算法移植到g p u ( g r a p h i cp r o c e s s i n gu n i t ，图形处理器) 上，在g p u 上快速运算破译算法的方法。 本文详细分析了t e s l ag p u 图形与计算架构和c u d a 统一计算设备架构，详 细描述了如何对计算任务进行并行分解，并通过c u d a 的双层并行编程模型映射 到t e s l ag p u 上。 在本文的实现部分，以软件开发流程为主线，首先将w p a w p a 2 p s k 破译 算法中反复调用的两个散列算法s h a l 和m d 5 移植到g p u 上并测试这两个算法 在g p u 上的运行速度。之后将w p a w p a 2 p s k 破译算法通过c u d a 移植到g p u 上，并测试破译算法在g p u 上的运行速度，最后将w p a w p a 2 p s k 破译算法在 g p u 上的运行速度和在c p u 上的运行速度进行比较分析并对破译算法的c u d a 实现进行优化。 关键词：g p uc u d aw p a w p a 2 p s k 破译 a b s t r a c t a b s t r a c t w p a ( w i - f ip r o t e c t e da c c e s s ) i sak i n do fs y s t e mw h i c hi su s e dt op r o t e c tt h e s a f e t yo fw i r e l e s sn e t w o r k w p ai n c l u d e sw p as t a n d a r da n dw p a 2s t a n d a r da n d d e c o d i n gw p a w p a 2 一p s k ( p r e s h a r e d k e y ) h a sh i g hp r a c t i c a lv a l u e i no r d e rt o m e e tt h ed e m a n do fs p e e do nd e c o d i n gw p a w p a 2 一p s kt h i sp a p e rp r o p o s ea m e t h o dt h a tu s ec u d at ol e tw p a w p a 2 一p s kd e c o d i n ga l g o r i t h mr u no ng p u ( g r a p h i cp r o c e s s i n gu n i t ) t h i sd i s s e r t a t i o na n a l y z e st h et e s l ag p ug r a p h i c sa n dc o m p u t i n ga r c h i t e c t u r e ， a n dt h ec u d ac o m p u t i n gu n i f i e dd e v i c ea r c h i t e c t u r e i td e s c r i b e dh o wt od e c o m p o s e ac o m p u t ew o r kl o a dt op a r a l l e lf o r m ，a n dm a pi tt ot e s l ag p u t h r o u g ht h el e v e l e d p r o g r a m m i n gm o d e lo fc u d a i nt h ei m p l e m e n tp a r to ft h i sd i s s e r t a t i o n ，a c c o r d i n gt ot h es o f t w a r ed e v e l o p m e n t p r o c e s s ，f i r s tt w oh a s ha l g o r i t h ms h a la n dm d 5w h i c hi s u s e df r e q u e n t l yi n w p a w p a 2 - p s k d e c o d i n ga l g o r i t h m i s i m p l e m e n t e d o n g p u u s i n g c u d a s e c o n d ，u s ec u d at ol e tw p a w p a 2 一p s kd e c o d i n ga l g o r i t h mr u no ng p u a n dt e s tt h es p e e d ，t h e nc o m p a r ea n da n a l y s i st h es p e e dw h i c ha r er e s p e c t i v e l yr u no n c p ua n dg p u f i n a l l y ，t h ed e c i p h e r i n ga l g o r i t h mw h i c hi si m p l e m e n t e du s i n gc u d a i so p t i m i z e dt om a k et h ep r o g r a mm o r ee f f i c i e n t k e y w o r d s ：g p uc u d aw p a f w p a 2 - p s kd e c o d e 创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：! 虱；量日期垒立! 望：5 ：! f 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期问论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 喜会墓耄! 蛰导师签名：堇垂量鳖至 日期2 区q ：& ：! 1 日期兰璺兰鱼一 第一章绪论 第一章绪论 本文首先论述了g p u 高速实现w p a w p a 2 p s k 破译的研究背景和意义，进 而分析和回顾了国内外在这个领域的发展现状，最后简要分析了本文的研究对象、 研究范围以及本文特点。 1 1 研究背景及重要意义 w p a 全名为w i f ip r o t e c t e da c c e s s ，有w p a 和w p a 2 两个标准，是一种 保护无线电脑网络( w i f i ) 安全的技术，它是研究者在前一代的系统有线等效加 密( w e p ) 中找到的几个严重的弱点而产生的，它有针对性的解决了w e p 的几 个弱点【l 】【2 1 。 w p a 采用两种认证方式：共享密钥认证和i e e e8 0 2 1 x 认证。前者模式比较 简单，没有认证服务器，只需要一个密钥即可实现，较多使用于一些小的企业、 家庭，s o h o 以及一些公共热点地区，这种方式也叫做p s k 模式，后者用户需要 提供的认证所需的有效凭证，通过特定的认证服务器来实现【3 】。 到目前为止，w p a w p a 2 p s k 的高速破解主要使用的是w p a p s kh a s h t a b l e s 的技术方法( 即直接建立一个文件，里面事先记录了采用和目标使用的同 样算法计算后生成的h a s h 散列数值) 。在破解的时候直接调用这样的文件进行 对比，破解的速度可以达到1 0 0 0 0 8 0 0 0 0 k e y s 4 1 。由于w p a w p a 2 一p s k 破译算 法是在c p u 上运行的，由于c p u 架构本身的局限，使得一次只能对一个数据进 行计算，而破译w p 刖w p a 2 p s k 需要处理的数据量巨大，因此虽然破译的速度 达到了1 0 0 0 0 8 0 0 0 0 k e y s ，但是破译p s k 花费的时间还是很长。由此可见，在 c p u 架构下运行w p a w p a 2 p s k 破译算法，要想进一步提高破译的速度受到限 制。 一种新的名为图像处理器( g r a p h i cp r o c e s su n i t ，g p u ) 的高性能数据处理 器件的出现，可能为w p a w p a 2 p s k 的高速破解的研究提供新的解决途径。g p u 在高性能运算方面具有三个突出优点：第一，g p u 拥有强大的并行数据处理能力， 目前的普通的g p u 拥有同时处理超过6 5 ，0 0 0 个线程的能力，峰值浮点运算能力 超过3 4 0 g f l o p s ，而高性能的g p u 可以同时拥有超过4 9 0 ，0 0 0 条数据处理通道， 峰值浮点运算能力超过1 8 t f l o p s ；第二，g p u 拥有出色的高密集运算能力，其 内部内存位宽高达1 2 8 、2 5 6 位，甚至4 4 8 位，由此支持数十g ，甚至两百g 以 上的数据传输带宽；第三，g p u 拥有良好的可编程性，支持多种高级语言编程， 由n v i d i a 公司生产的g p u 甚至支持c 语言编程，对大规模的数据流并行处理方 2 基于g p u 的w p a w p a 2 一p s k 高速破译方法研究 面具有明显的优势1 5 , 6 。2 0 0 7 年，n v i d i a 推出的c u d a 并行计算技术，采用对 标准c 扩展的方式，使g p u 通用计算( c p g p u ) 从图形硬件流水线和高级绘制 语言中解放出来，开发人员无须掌握图形学编程方法即可在单任务多数据模式下 完成高性能计算，从而大大降低了开发门槛【_ 7 引。 由于破译w p a w p a 2 p s k 需要处理海量的数据，这些数据都是相互独立， 每一个数据都要经过相同算法的计算，而g p u 在高性能运算方面的以上三个优 势，使得w p a w p a 2 p s k 破译算法非常适合移植到g p u 上运行，利用g p u 架 构的优势，提高w p a w p a 2 一p s k 破译速度。首先，g p u 拥有的良好的可编程性， 特别是c u d a 并行计算技术，使得把w p a w p a 2 p s k 破译算法移植到g p u 上 运行具有了可行性；其次，由于g p u 强大的并行数据处理能力，使得g p u 能同 时处理上万个数据，而g p u 拥有的出色的高密集运算能力，使得在同时处理上万 个数据的时候，这些待处理的数据能及时的被传输到需要的地方，而不会因为数 据传输的延迟而导致程序效率的下降。因此，以拥有密集型并行数据处理能力的 g p u 为处理平台，以c u d a 为软件建模环境，以w p a p s kh a s ht a b l e s 技术为 破解算法核心，能实现基于g p u 的w p a w p a 2 p s k 高速破译。 而对于w p a w p a 2 一p s k 的高速破解的研究，能够帮助无线用户，甚至很多 的已经完成或者j 下在进行无线网络规划的军警机构、大中型企业及特殊部门，更 清楚的认识到无线网络的风险，以及清楚的知道黑客门所使用的破解的方法，从 而尽可能的完善自身的不足，避免不必要的损失。同时通过对w p a w p a 2 p s k 的破解，能找到w p a 加密信息的缺点，从而促进找到更好更安全的方法来保障 无线电脑网络的安全。 1 2 国内外发展状况 如前一节所述，破译w p a w p a 2 p s k 需要进行计算的数据量巨大。目前采 用w p a p s kh a s ht a b l e s 的方法可以使破解速度从以前的3 0 1 5 0 k e y s 的普通单 机破解速度提高到1 0 0 0 0 - 8 0 0 0 0 k e y s ，提升了2 0 0 3 0 0 0 倍，这个方法在现在的 w p a w p a 2 p s k 的破译中得到了广泛的运用。 g p u 拥有强大的密集并行数据处理能力，有可能为解决限制 w p a w p a 2 p s k 破译速度的瓶颈提供新的解决途径。将g p u 用于 w p a w p a 2 一p s k 破译是一个崭新的概念。主要原因有三个：第一，g p u 是一类 新型的针对高密集并行运算的数据处理器件，1 9 9 9 年才由n v i d i a 公司正式提出 g p u 的概念；第二，g p u 是专门针对图形处理而开发的，其主要的数据处理为顶 点渲染、像素渲染、光栅处理等，这些处理方式与通常的数据处理有明显的不同； 第一章绪论 3 第三，将g p u 应用于通用计算( 区别于图形绘制的普通的数据处理) 是g p u 的 全新应用，是2 0 0 0 年才出现，2 0 0 7 年才全面得到接受和认可的g p u 应用研究。 就基于g p u 的通用计算而言，鉴于g p u 强大的密集并行处理能力，以及随 着技术的进步而逐步提升的可编程性，人们对将g p u 通用科学计算投入了极大的 关注，开展大量了的研究，而且随着g p u 技术的进步而不断深入。在g p u 出现 的早期，l a r s e n 等人在2 0 0 1 年利用多纹理技术实现了矩阵运算操作。2 0 0 1 年后， 随着n v i d i ag e f o r c e3g p u 的出现，顶点级可编程( v e r t e xp r o g r a m ) 开始普及。 虽然这个时候片段级上还只是固定的几条指令，但利用g p u 进行通用计算方面的 应用已经全面展开。t h o m p s o n 等人在顶点级实现了一个代数运算的框架系统， 其中包括矢量运算和矩阵乘法等。2 0 0 2 年，人们开始利用t e x t u r es h a d e r 结合 r e g i s t e rc o m b i n e r 来求解扩散方程。2 0 0 3 年片段级可编程( f r a g m e n tp r o g r a m ) 出现，大大加速了g p u 通用计算方面的研究。很多研究人员开始利用片段程序来 求解一般代数问题，包括流体模拟、物理现象仿真、有限差分方程组求解和优化 等。2 0 0 4 年，美国研制的g p u 集群系统( t h es t o n yb r o o kv i s u a lc o m p u t i n g c l u s t e r ) 运用于城市气流模拟。另外，美国北卡罗莱那大学将g p u 计算应用于数 据库领域，利用g p u 硬件对数据库的关系查询、合取选择、聚集操作等进行加速 和优化。同年，美国国防技术情报中心公开发布了g p u ：未来高性能计算引擎 的科技报告，内容包括对g p u 通用计算应用于高性能计算领域的发展展望和未来 面临的挑战。2 0 0 5 年1 0 月n v i d i a 和a t i 公司相继开发基于g p g p u 的物理计 算a p i ，使得g p u 能够利用浮点片段着色器单元处理包含大量并行操作的科学计 算任务。2 0 0 6 年，分布式计算项目f o l d i n g h o m e 在蛋白质折叠的研究中充分发 挥了g p u 的高性能优势。该项目利用a t ig p u 获得了每台计算机1 0 0 g f l o p s 的高性能。另外，a t i 公司在s i g g r a p h 2 0 0 6 上做了数据并行虚拟机( d a t a p a r a l l e l v i r t u a lm a c h i n e ) 的演示，并使用了专门为g p u 通用计算而设计的“c l o s et ot h e m e t a l ”a p i 。通过在一个显卡上使用多个g p u 来形成数据流处理集群，通过强大 的数据并行处理机的性能来解决g p u 并行数据加速的问题。 目前，国内在g p u 通用计算方面的研究也在一些科研机构和院校逐步开展起 来。清华大学利用g p u 的并行计算能力和数据流处理能力，在g p u 上实现了一 种新的辐射度计算方法，并实现了j a c o b i 迭代法快速求解线性方程组；西安电子 科技大学利用g p u 实现了大气辐射传输、红外成像系统成像效应等高速仿真处理 模型。另外，中科院计算技术研究所、华中科技大学、西南交通大学等也相继针 对特定应用在g p u 上进行了实验验证。 在g p u 通用计算的软件开发环境方面，o p e n g l 作为事实上的工业标准已为 学术界和工业界所普遍接受，其中包括了g p u 厂商以及o p e n g l 架构委员会 ( a i 也) 所扩充的函数，以此来实现g p u 厂商提供的新功能。d i r e c t x 则根据g p u 4 基于g p u 的w p a w p a 2 一p s k 高速破译方法研究 新产品功能的扩充与进展及时的发布新的版本。二者在实现g p u 通用计算方面都 需要使用者非常熟悉g p u 图形绘制的原理和硬件结构等许多具体问题。高级绘制 语言和实时绘制语言的出现，如n v i d i a 的c g ，o p e n g ls h a d i n gl a n g u a g e ，h i g h l e v e ls h a d i n gl a n g u a g e 等，为编程人员提供了直接基于图形a p i ( o p e n g l 或 d i r e c t x ) 编程的较为方便和高层次的工具【9 】。而最新的由n v i d i a 公司推出被称 作统一计算设备架构( c o m p u t eu n i f i e dd e v i c ea r c h i t e c t u r e ，c u d a ) 的通用计算 解决方案，包含了a p i 、c 编译器等组成部分，允许开发人员在不考虑图形绘制 和硬件结构的情况下，充分利用g p u 的可编程性，以c 语言为工具编写面向通 用计算的绘制程序，从而大大简易了研究者对g p u 高性能计算资源的利用，对 g p u 的通用计算应用起到了极大的推动作用【l 们。由于g p u 的特点是处理密集型 数据和并行数据计算，因此c u d a 非常适合需要大规模并行计算的领域。目前 c u d a 除了可以用c 语言开发，也已经提供f o r t r a n 的应用接口，未来可以预 计c u d a 会支持c + + 、j a v a 、p y t h o n 等各类语言【l 1 1 。 w p a - p s kp a s s w o r da u d i t r a l d a $ 1 0 t o - _ _ _ _ _ _ _ 一让如 h d 翻”口1 2 h d 4 啪 洲狮 c o r e 2 q u d q 6 弓 c o r e 2 d u ee 帮阳o 图1 1 使用g p u 进行w p ah a s h 运算测试数值比较 利用g p u 进行w p a w p a 2 一p s k 的破译属于基于g p u 的通用计算领域的范 畴。一家俄罗斯软件公司e l c o m s o f i 在2 0 0 9 年1 月1 5 日推出了“w i r e l e s ss e c u r i t y a u d i t o r1 0 ，号称可以利用g p u 的运算性能快速攻破无线网络w p a p s k 及 w p a 2 p s k 密码，运算速度相比使用c p u 可提高最多上百倍。这款软件的工作 方式很简单，就是利用字典对无线a p ( a p ，a c c e s sp o i n t ，无线访问节点、会话 点或存取桥接器) 上的w p a 和w p a 2 密码实施暴力破解。软件支持字母大小写、 数字替代、符号顺序变换、缩写、元音替换等1 2 种变量设定，在a t i 和n v i d i a 显卡上均可运行i l l 。官方给出的破译速度如下图1 1 显示：在c o r e2d u oe 4 5 0 0 和c o r e2q u a dq 6 6 0 0 处理器上，该软件每秒钟可以试验4 8 0 个和l1 0 0 个密码， 换成g e f o r c eg t x2 8 0 、r a d e o nh d4 8 7 0 、r a d e o nh d4 8 7 0x 2 等普通终端非专业 显卡能大幅增至每秒1 1 8 0 0 个、1 5 7 5 0 个和3 1 5 0 0 个，在更为先进的n v i d i a 的 视觉计算系统t e s l as 1 0 7 0 中，每秒钟可达5 2 4 0 0 个，相当于e 4 5 0 0 的1 1 0 倍【l j ! 第一章绪论 5 由此可见g p u 在快速破解w p a p s k 及w p a 2 p s k 密码时，确实有自己很 大的优势。值得指出的是，e l c o m s o f t 声称其中使用了他们“独家开发的g p u 加 速技术 ，而非基于n v i d i ac u d a 、a t is t r e a m 或者o p e n c l 等。由于n v i d i a c u d a 具有更好的通用性，在本文中，将研究如何利用通用g p u 计算的新架构 c u d a 实现w p a p s k 及w p a 2 p s k 密码的高速破译。 1 3 1 研究内容 1 3 本文研究内容与特色 利用g p u 强大的密集并行数据处理能力，在c u d a 基础上，建立利用g p u 进行 通用数据处理的框架。进而在此框架下实现基于g p u 的w p a w p a 2 - p s k 高速破译。 本文将首先分析g p u 的体系结构，在c u d a 架构的基础上，建立基于g p u 的通用数 据并行处理框架：针对现有的w p a w p a 2 - p s k 破译算法，研究其在g p u 通用数据并 行处理框架下的实现；分析基于g p u 的w p a w p a 2 - p s k 破译的性能，由此为g p u 通用数据处理技术在无线信息破译处理方面的应用奠定基础。 本文的具体研究研究内容及简单分析如下： ( 1 ) 建立基于g p u 的通用数据并行处理框架 g p u 本是针对图形处理应用开发的，因而相对一般的数据处理器件，其体系 结构具有特殊性，即使随着技术的发展，g p u 的可编程性和可控性有了很大的改 善，可以用于非图形绘制应用的通用科学计算，然而g p u 目前最主要的应用仍然 是图形绘制，其内部的数据处理架构仍然以图形绘制为基础。为实现基于g p u 的通用计算，必须针对g p u 的体系架构特点，在充分理解其数据处理流程、方式 的基础上，建立基于g p u 的通用数据并行处理框架，为后续利用g p u 进行无线 信息破译处理奠定基础。 ( 2 ) w p a w p a 2 p s k 破译算法在g p u 通用数据并行处理框架下的实现 w p a w p a 2 p s k 破译具有数据大、数据密集、数据处理并行性高等特点， 而g p u 具有强大的密集并行数据处理能力，因而g p u 适合于w p a w p a 2 一p s k 的破译需求。对于w p a w p a 2 p s k 破译算法而言，其并行性是显性的，它所处 理的所有数据都具有独立性的特点( 即各个数据都要接受相同的处理) 。为了充 分利用g p u 的并行处理能力，必须将w p a w p a 2 p s k 破译中所遇到的数据在并 行性上进行优化，并针对g p u 的结构与数据处理特点，移植到g p u 通用数据处 理框架下。 ( 3 ) 基于g p u 的w p a w p a 2 一p s k 破译性能分析 6 基于g p u 的p a 1 r p a 2 一p s k 高速破译方法研究 针对w p a w p a 2 p s k 破译算法，测试其在g p u 平台下的性能指标，如数据 输入、输出速度及处理速度等，由此分析利用g p u 进行w p a w p a 2 。p s k 破译的 性能。 1 3 2 结构安排 本文在结构上共分为五章，结构安排和每章的主要内容如下： 第一章绪论。首先指出本文的研究背景和意义，然后简单介绍g p u 通用计 算和w p a w p a 2 p s k 高速破解的发展，最后给出本文的研究内容和框架。 第二章t e s l ag p u 架构与c u d a 介绍。首先简述c u d a 的软硬件组成，然 后详细介绍t e s l a 框架和c u d a 编程模型，为分析破译w p a w p a 2 p s k 的算法 的并行实现提供了依据。 第三章介绍w p a w p a 2 p s k 破译算法中反复调用的两个算法及其c u d a 实现。w p a w p a 2 p s k 破译算法中反复调用的两个算法为s h a l 算法和m d 5 算 法，在这一章中，将分别在g p u 和c p u 实现这两种算法，最后比较和分析g p u 和c p u 处理数据的速度。 第四章w p a w p a 2 p s k 破译算法的c u d a 实现。首先详细介绍w p a w p a 2 的工作原理及其破译w p a w p a 2 p s k 的方法，为后续破译算法的c u d a 实现做 准备。然后将w p a w p a 2 p s k 破译算法在c u d a 构架上进行移植并测试速度， 并将其与在c p u 下运行的速度进行比较和分析。最后，将w p a w p a 2 p s k 破译 算法的c u d a 实现进行优化。 第五章全文总结。对本论文所作的工作给予全面的归纳总结，并指出目前工 作的不足和未来的工作方向。 1 3 - 3 研究特点 目前国内破译w p a w p a 2 p s k 都是在c p u 下进行的，虽然使用w p a p s k h a s ht a b l e s 的技术方法能使破译速度提升到1 0 0 0 0 - 8 0 0 0 0 k e y s ，但是却很难实现 速度的进一步提升。本文对w p a w p a 2 p s k 高速破译问题另辟研究蹊径，在充 分分析破解算法并行性特征的基础上，以拥有密集型并行数据处理能力的g p u 为处理平台，以c u d a 为软件建模环境，以w p a p s kh a s ht a b l e s 技术为破解算 法核心，实现基于g p u 的w p a w p a 2 p s k 高速破译。研究结果不但具有较高的 实际应用价值，更为w p a t w p a 2 一p s k 的高速破译展现了新的破解途径。 本文研究有以下特点： 第一章绪论 7 详细分析了g p u 架构和c u d a 体系，研究如何将应用中的计算任务 进行并行化分解，并通过c u d a 的双层并行编程模型将算法映射到硬 件上。 对w p a w p a 2 p s k 破译算法基于的两个散列算法s h a l 算法和m d 5 算法进行分析，找出这两个算法处理数据的特点，并将其计算任务进 行并行分解，在此基础上建立这两个算法的c u d a 框架。测试这两个 算法在g p u 架构下处理数据的速度，并和在c p u 架构下处理数据的 速度进行比较，以反映g p u 在处理密集型数据方面的巨大优势。 分析了w p a w p a 2 的工作原理，并在此基础了给出了w p a w p a 2 - p s k 破 译的原理及算法。通过分析破译w p a w p a 2 一p s k 时计算任务的特点，将 w p a w p a 2 一p s k 破译算法的计算任务进行并行化分解，提出破译算法的 c u d a 实现方案。将破译算法使用c u d a 移植到g p u 架构上实现，并测 试算法在处理不同数量的数据所需要的时间。最后，优化c u d a 程序， 使其运行效率更高，破译时间更短。 ) ) ) l 2 3 ( ( ( 第二章t e s l ag p u 架构与c u d a 介绍 9 第二章t e s l ag p u 架构与c u d a 介绍 2 1 引言 以c p u 为基本单元构建的大型集群是目前高性能计算的主流，但困扰其大规 模扩展的关键问题一直没得到根本解决，主要存在如下关键问题【1 2 】： 内存墙和i o 墙( m e m o r ya n di ow a l l ) ：由于物理上的限制，存储器性能 与处理器性能差距越来越大，本地带宽及延迟和全局带宽及延迟发展不一致造成 了阻碍性能提升的“内存墙”( m e m o r yw a l l ) ；系统从i o 输入到i o 输出的不 均衡带宽设计形成了“i 0 墙 ( i ow a l l ) 。 功耗墙( p o w e r c o n s u m p t i o nw a l l ) ：功耗也已经成为制约高效能计算机系统 发展的主要因素之一，当前每个集群节点耗电在3 0 0 到1 5 0 0 瓦之间，而一个机柜 耗能在2 0 到3 0 千瓦左右。 编程墙( p r o g r a m m i n gw a l l ) ：在编程方面，用户为完成一个具体的并行应 用在建模、编码、调试、优化、运行、维护和故障处理上所遇到的各种困难交错 形成了“编程墙”( p r o g r a m m i n gw a l l ) ，编程墙的主要问题是如何的利用好为 数众多的处理器和管理大量的并发线程。 复杂性墙( c o m p l e x i t yw a l l ) ：在管理方面，高性能计算机软硬件系统交 织，管理的复杂性随之成倍增长，形成了新的“复杂性墙 ( c o m p l e x i t yw a l l ) 。 可靠性墙( a v a i l a b i l i t yw a l l ) ：对高性能计算机系统来说，可靠性也是其挑 战之一，当其扩展到成万或十万颗之多c p u 以及几百t e r a b y t e s 内存时，如何保 障硬件系统的可靠性，同时在这样大规模的系统运行中，软件错误也很难避免。 扩展性墙( s c a l a b i l i t yw a l l ) ：在目前的集群中，用户不必过于关注延时，但 随着系统规模进一步扩展，延时将变成一个非常重要的问题。同时，今天基本上 没有系统软件和应用软件能扩展到这样一个处理器的规模，因此需要重新设计软 件硬件编程模型，以适应系统的大规模扩展和求解问题的大规模扩展，并确保其 高效性和高并行度。 与此同时，在另一方面，虽然多核处理器是当前乃至未来构建高性能计算机 的基础，但多核处理器也对传统的系统结构提出了新的挑战，如存储器壁垒，芯 片、板极、系统级均衡设计以及可移植性等方面的问题。 可以看到，上述内存墙、i o 墙、功耗墙、复杂性墙、编程墙、扩展性墙等 诸多问题为以c p u 为基础的高性能计算机的发展及其平民化应用设置了重重障 碍。而与此同时，微软公司在d i r e c t x l 0 规范中描述了s h a d e rm o d e l4 0 标准，它 的架构发生了重大变化，为了更加合理的利用g p u 硬件资源，d i r e c t x l 0 提出了 1 0 基于g p u 的w p a w p a 2 一p s k 高速破译方法研究 统一着色器架构。这一架构要求在g p u 内部使用“流处理单元 代替以往分离的 顶点着色单元和像素着色单元 8 0 】。n v i d i a 推出的支持d i r e c t x lo 规范的g p u 采 用了t e s l a 图形处理和计算架构【1 3 】。t e s l a 架构采用了由标量计算单元组成的处理 器阵列，并拥有共享存储器和硬件同步机制。 t e s l ag p u 在每瓦特性能上相对于c p u 有优势，缓解了功耗墙问题；高于 c p u 一个数量级的显存带宽减轻了内存墙的影响；大量处理器处于同一芯片内， 减轻了系统的可靠性和复杂性问题。 对于编程墙问题，n v i d i a 推出了为t e s l a 架构开发的c u d a 通用计算编程模 型与开发环境。c u d a 是第一种能够通过类c 语言在支持d i r e c t x l 0 的g p u 进 行通用计算程序设计的编程模型和开发环境，在计算功能和开发效率上都超过了 传统的g p g p u 开发方式。 本章将讨论t e s l a 图形与计算架构，以及如何通过c u d a 将通用计算任务映 射到采用t e s l a 架构的g p u 上。 2 2t e s l a 图形与计算架构简介 t e s l a 体系架构的设计重点是能够在处理数据并行问题时获得很高的数据吞 吐量( c o m p u t a t i o n a lt h r o u g h p u t ) 。为了提高芯片整体的性能，单个线程的性能和 执行时间做出了牺牲。这与通用处理器( 如c p u 等) 形成了反差：通用处理器的 设计重点是提高单个线程的性能，减少执行和通信延迟，而不在计算吞吐量上。 n v i d i a 在t e s l a 体系架构中使用了新的统一着色单元替代了原来分离的顶点 与像素着色单元，能够通过c 语言在c u d a 并行编程模型下使用相应的开发工具 满足高性能通用计算的需要。使用t e s l a 图形处理和计算架构的g e f o r c e 系列和 q u a d r o 系列g p u ，被广泛应用于笔记本电脑，桌面计算机，工作站和服务器中。 n v i d i a 在2 0 0 7 年发布的t e s l ag p u 高性能计算平台也采用相同的体系架构【1 4 j 。 2 2 1 统一着色单元 g p u 是由可编程的处理器和固定功能的图形处理单元组成的。在传统的g p u 中，有两种不同的可编程处理单元：顶点着色单元和像素着色单元，分别处理3 d 图像着色不同阶段中的任务，它们是互相分置彼此不干涉的。这种方式对图形的 渲染流程见图2 1 。 但是在长期的发展中发现，要达到最佳的性能和电力使用效率，还是必须使 用统一着色器逻辑，否则在很多情况下顶点着色器计算压力很轻造成大量顶点着 色器单元处于闲置状态，而像素着色器资源有限，当遇到大量三角形的时候则一 第二章t e s l ag p u 架构与c u d a 介绍 直忙碌。反过来，当画面中需要绘制很多三角形的时候，则会发生相反的情况。 图2 - 1 传统g p u 渲染构架 从图2 1 【l5 】中也可以看出，每一帧渲染中顶点着色器和像素着色器负载压力几乎 没有相关性，总是在出现资源闲置和资源紧缺，所以有必要使用统一着色器。 在统一着色器架构的g p u 中，不再区分像素与顶点着色单元，而是由流处理 器单元按照负载动态的执行包括像素和顶点在内的各种着色指令。流处理单元是 个完整的图形处理体系，它即能够执行对顶点操作的指令，又能执行对像素操作 的指令，g p u 内部的流处理单元甚至能够根据需要随意切换调用【1 6 1 。 t e s l a 架构的主要设计目标就是只使用统一着色单元执行顶点和像素( 片元) 着色程序，并使这种体系架构能够自动平衡图形流水线中的顶点处理、像素处理 和d i r e c t x l o 中几何处理的负载。t e s l a 架构是由大量统一处理单元组成的阵列， 辅以少量的图形学固定功能单元构成的，它是专为通用计算而生的。基于分离着 色单元的传统g p g p u 开发方法通常只利用了g p u 中的可编程像素着色单元，而基 于统一处理单元的g p u 则可以用所有的可编程处理单元执行通用计算程序，如今 的g p u 拥有数十倍于c p u 的浮点运算能力。 1 2 基于g p u 的1 】r p a 1 r p a 2 一p s k 高速破译方法研究 2 2 2t e s l ag p u 体系架构 t e s l a 体系架构是一块具有可扩展处理器数量的处理器阵列，下图2 2 为g t 8 0 架构示意图。 图2 - 2g 8 0 架构 g p u 在工作时，工作负载从p c i e 总线传入，按照体系架构的层次自顶向下 分发。p c i e2 0 1 6 插槽为上下行数据各提供了高达8 g b s 的带宽，而p c i e1 o 1 6 插槽的上下行数据带宽各为4 g b s 。考虑到p c i e 数据封包的影响，实际可 用的带宽大约在5 - 6 g b s ( p c i e2 0 1 6 ) 或者2 3 g b s ( p c i e1 0 1 6 ) 。 t e s l a 体系架构由两部分组成，从图2 2 中所示，分别为流处理阵列( s c a l a b l e s t r e a m i n gp r o c e s s o ra r r a y ，s p a ) 和存储器系统，两部分由一个片上互联网格组成。 流处理器阵列和存储器系统可以分别扩展，规格可以根据产品的市场定位裁减或 者增强。存储器系统由几个部分组成：存储器控制器( m m c ) 、固定功能的光栅 操作单元( r a s t e ro p e r a t i o np r o c e s s o r s ，r o p ) ，以及二级纹理缓冲。存储器控制器 负责控制片外的d r a m 显存，每个存储器可以提供6 4 b i t s 位宽；而r o p 则可以 对存储器内的数据进行颜色和深度操作。通过片上互联总线，s p a 可以将计算得 到的深度和颜色信息发送给r o p ，也可以直接读写d r a m ，或者通过纹理缓冲以 只读方式访问d r a m 。 g p u 的强大计算能力来自s p a 中的大量计算单元，g p u 的所有可编程的计 算任务都由s p a 执行。s p a 结构可以分为两层：第一层是若干个t p c ( t r c a d p r o c e s s i n gc l u s t e r ，线程处理器群) ，t p c 结构见图2 3 ：第二层是每个t p c 中的 第二章t e s l ag p u 架构与c u d a 介绍 2 3 个s m ( s t r e a m i n gm u l t i p r o c e s s o l s m ) 和一个纹理流水线组成，s m 结构见图 2 - 4 。如上图2 2 的g 8 0 ，它拥有8 个t p c ，每个t p c 中有两个s m 。实际上n v i d i a 的g p u 里，最基本的处理单元就是s m 。每个s m 大致相当于一个具有8 路s i m d 的处理器，但指令带宽不是8 ，而是3 2 ( 即w a r ps i z e ) 。s m 拥有独立的完整前 段，包括取指、译码、发射和执行指令，但s m 的存储器流水线是与同一个t p c 中的其它s m 共享的。每个s m 中包含8 个线程处理器( t h r e a dp r o c e s s o r ，t p ) ， 也可叫流处理器( s t r e a m i n gp r o c e s s o r , s p ) 或渲染核( s h a d c rc o r e ) 。s p 并不是 独立的处理器核，它们有独立的寄存器和指令指针，但没有取指和调度单元构成 的完整前段。因此，s p 更加类似于当前的多线程c p u 中的一条流水线。 图2 - 3t p c 架构 妾一鲴 基于g p u 的w p a w p a 2 一p s k 高速破译方法研究 s i c a c h e m ti s s l j e c c a c h e 习医 型l 兰 圄匝 s h a r e ( 削2 - 4s m 架构 g p u 执行通用处理任务时的工作流程是：由计算分配单元将计算线程组成的 c t a 阵列( c o o p e r a t i v e t h r e a d a w a y ，协作线程阵列) 分发到s p a 中的各个t p c 中执行。s p 可以同时处理属于多个不同流的任务。 2 3 c u d a 概述 多核( m u l t i - c o r e ) c p u 与众核( m a n y - c o r e ) g p u 这两类并行系统已经成为 了目前计算机系统的主流 1 7 , 1 s 3 9 1 ，它们的计算能力都按摩尔定律提高。由于架构 和频率的限制，单核心处理器的性能提高余地已经不大，因此g p u 和c p u 的核 心数量还将进一步增加。在过去几年里，o p u 的更新速度比c p u 快了一倍，由 于用于专用的处理器发展成为高度并行的可编程的处理器，因此编程成为用户关 注的特征，c u d a 就是在此种情况下n v i d i a 公司推