技术开发 频道

并行化我的应用:字符串并行处理项目

  【IT168技术】

  注:本文为IT168&NVIDIA联合举办的“如何并行化我的应用”方案征集活动参赛作品。本次方案征集活动详情见:http://cuda.itpub.net/thread-1299715-1-1.html。近期活动的大部分方案,将会逐步与大家分享,不可错过哦!

  CUDA ZONE专区:http://cuda.it168.com/

  CUDA技术论坛:http://cuda.itpub.net

  说明:

  本项目并非工程项目,带有研究性质,是由CUDA群里一位朋友提出的问题引申而来。这里提供的是我的解决方法。

  1、项目应用背景

  本项目解决的问题是:有一串字符串由N个子串组成,每个子串通过特定分隔符分割,如何快速地对整个字符串做某些操作。以我做实验的情况为例,随便找一篇英文的文本,统计该文本的字数。该文本是一个字符串,每个单词就是一个字串,分隔符是包含空格的任意的标点符号(也可认为非字母的都是分隔符),做的操作就是统计单词数。但应用不局限于此,如可以将一批文本形式的数转换为二进制型。凡是符合由多个字串组成的、通过特定分隔符分割的(即分隔符已知且子串内不含分隔符)、对子串做同一操作的字符串,都可以用这个项目的方法来解决。

  2、应用的业务瓶颈、规模

  由于项目具体应用不同,导致业务的瓶颈、规模各不相同。但其间共同的瓶颈在于:1)、文本较大时IO时间较长。2)、文本较大时处理时间较长。此处“较大”的概念是文本文件在数百M字节到数G字节。

  3、具体并行化的想法

  串行算法为顺序执行,从头扫描到分隔符,区间内的是一个子串,接下来对子串做处理,处理后记录结果并从分隔符后继续下一次扫描。

  并行化根据瓶颈有两方面的优化措施,比较容易做的是针对第二点,将整个字符串划分(大致均分)为多个大的子串,再对大的子串分别处理。处理方式等同于串行算法。对第一点的优化,则是需要将读取文件的过程分为多个部分,如同CUDA中Stream的概念,将前一步的处理子串和后一步的读取文件并行执行,达到加速的目的。

  4、具体实施和效果

  具体实施当然通过CUDA,首先读入整个文本(后面将对读入文本环节进行优化)并赋值给一个字符串。然后需要根据线程数对文本进行分割。我采取的办法是,创建一个元素是字符指针类型的数组,该数组的大小恰好比线程数大1。该数组的每个元素的内容是指向分割后的字符串位置的指针。即,通过访问该数组的第i个元素,能得到第i号“大的子串”的起始地址,而字串的末尾则是数组下一个元素所指向的地址之前。显然第0号元素指向的是整个字符串的起始地址,而最后一个元素指向的是整个字符串结尾后面的地址。

  各个分割点的选取,即该数组每个元素的内容,需要遵循两个原则,其一是尽量使分割后的每个大子串在处理时的工作量一样大,其二是每个大子串必须包含完整的子串,亦即分割位置不能处于一个子串中间。第一点实际上是不能满足的,因为在运行以前是不可能知道每个大子串工作量的大小的,所以只能使用近似的办法,即让每个大子串的大小近似一致。最简单的方法就是根据线程数平分。但在平分以后并不能直接应用,因为必须同时满足第二个条件。此时需要根据每个分割点,查看该分割点的地址指向的字符,如果是分隔符则认可该分割点,否则选择该字符后面的那个字符直到找到分割点。其实对于统计单词来说,分割时甚至不必保持子串的完整,但为了说明问题,也为了使该项目能够通用(绝大多数应用中需要保持子串完整),所以仍采用了保持子串完整的做法。

  找到分割点后,将分割点数组传入显存,并根据其确定大子串的边界并在GPU中进行处理。在统计单词数的应用中,处理的方式是统计分隔符的数量即可得知单词数量。统计结果首先在本线程内得到,然后在block中通过声明的share memory使用原子操作加和(需要支持1.3的设备),最后通过global memory的统计变量使用原子加得到总的单词数。

  对于如何优化I/O的应用。最基本的步骤是将文件一次性全部读入内存,并使用页锁定含有Zero-Copy特性的内存。这样可以显著节省带宽。但在文件过于庞大时I/O时间仍然较长,所以需要使用流的方法将整个流程分为多个部分,每个部分按照上述方式处理,最后将结果汇总。通过交错I/O和GPU运算,掩盖I/O的延迟。

  由于具体应用不同,加速比大致几十到百倍左右。相对来说,满足文本在500M以上、对字符串处理的操作比较复杂,子串数量比较多时,加速效果较好。

0
相关文章