[离线作业] 南开大学并行程序设计-(2009)参考资料

[复制链接]
发表于 2020-7-6 17:45:25 | 显示全部楼层 |阅读模式
南开大学现代远程教育学院考试卷  
2020年度春季学期期末(2020.9)  《并行程序设计》
主讲教师: 王刚

学习中心:____________________________    专业:_______________________
姓    名:_________________ 学  号:_______________ 成绩:___________

一 、请同学们在下列题目中任选一题,写成期末论文。
(一)并行算法研究类
对某一问题,研究其并行算法的设计、实现,分析其性能,进行实验验证,撰写研究论文。例如:
1、对矩阵相乘问题,设计pthread多线程结合SSE/AVX的两层并行算法,实现并行程序。讨论算法层面不同策略对性能的影响,例如多个线程间不同的任务分配方式、不同的线程同步策略等,讨论不同并行编程方法对性能的影响,例如SSE/AVX的对齐和不对齐内存访问等等。对不同的矩阵规模、不同的线程数测试程序性能,撰写研究论文。
2、对高斯消去法问题(其串行算法伪代码示意如下面算法1所示),设计pthread多线程结合SSE/AVX的两层并行算法,实现并行程序。讨论算法层面不同策略对性能的影响,例如多个线程间不同的任务分配方式、不同的线程同步策略等,讨论不同并行编程方法对性能的影响,例如SSE/AVX的对齐和不对齐内存访问等等。对不同的矩阵规模、不同的线程数测试程序性能,撰写研究论文。
3、其他类似难度的问题。
(二)并行编程工具调研类
对某种并行编程工具进行调研,选取某个问题(例如矩阵相乘问题),用这种编程工具编写并行程序求解这个问题,进行实验验证,撰写研究论文介绍这种并行编程工具的特色、基本编程(使用)方法、如何用它解决实际问题(以你选定的问题为例)。例如:
1、C++、Java等语言本身对并行编程提供的支持。
2、Hadoop MapReduce编程工具。
3、其它并行编程工具。

二、论文写作要求
(一)并行算法研究类
1、论文应详细描述清楚所研究的问题,并行算法的设计。
2、鼓励大家选择课堂教学之外的问题,通过文献调研,研究其并行求解方法,甚至有自己提出新的方法。
3、最好能有求解一个问题的多种并行算法之间的对比分析。
(二)并行编程工具调研类
1、应调研较新的工具,避免调研太“古老”的工具。
2、不能只是工具相关资料的调研和文字的汇总、整理,重点仍是并行编程——用调研的工具编程解决一个具体问题。
3、鼓励大家进行不同并行编程工具间的对比,例如调研的工具与课堂讲授的工具之间的对比。

三、论文写作格式要求:
论文题目要求为宋体三号字,加粗居中;
正文部分要求为宋体小四号字,标题加粗,行间距为1.5倍行距;
应符合科技论文写作规范,题目、摘要、关键字、章节、参考文献等等完整、正确。这方面可参考附件范文。
四、论文提交注意事项:
1、论文一律以此文件为封面,写明学习中心、专业、姓名、学号等信息。论文保存为word文件,以“课程名+学号+姓名”命名。
2、论文一律采用线上提交方式,在学院规定时间内上传到教学教务平台,逾期平台关闭,将不接受补交。
3、不接受纸质论文。
4、与论文一同打包提交源程序,注意,是提交.cpp、.h等源程序,不要将工程文件、编译后的目标文件等打包提交。
5、如有抄袭雷同现象,将按学院规定严肃处理。

jieba分词的局部并行化处理
摘要
Jieba分词为中文处理的一个工具集,主要功能为对文章进行长短句切割和分词,其在国内对中文的自然语言处理中使用率较高。本文分析了jieba分词中生成前缀词典和中文分词部分的算法并对其实现了并行化算法。最终使前缀词典生成效率(最大)提高2.3倍,分词效率提高2.7倍。
关键字:jieba分词、并行计算、前缀词典、进程池
一、引言
在自然语言处理中,能将长句准确地切割成单词、短语是之后算法的关键。目前国内外已有很多关于中英文分词的算法和工具,在分词准确率上已达到较高水平,其中应用最广泛的是基于词典的机械匹配算法,这也是本文选用的算法。它的本质是将文本与词典进行字符串匹配,算法实现比较容易,但是对于一词多义、组配灵活的汉语实行简单的机械切分,将会产生无法克服的切分歧义,同时由于词库容量的限制,对于词库中没有收录的新词将无法识别。单纯采用机械匹配方式进行分词由于切分精度不高难以满足中文信息处理中对汉语分词的要求。为了提高机械匹配对切分歧义的处理能力,人们提出了将其他切分歧义处理策略与机械匹配相结合的中文分词算法,并取得了不错的效果,它是目前中文分词方法研究中一个比较成熟的发展方向。
对一个成熟的算法,切分精度和切分速度是两个最重要的目标。对机械匹配算法来说,切分精度已达到要求,但速度却较慢,尤其是在大文本量的前提下。以github上star数较高的(13.1k)中文分词工具jieba分词来说,使用的仍然是串行算法。在速度方面,国内已有越来越多的学者开始研究引入并行技术,如郭翠珍[1][2]等人提出的一个基于网格的分词服务系统的研究,刘怀英[3]提出的基于分布式并行计算的中文分词研究等。
本文在jieba分词的基础上,分析了原有的算法并探讨了对算法并行加速的可行性。参考了相关文献后选择在jieba分词的前缀字典生成 和中文分词 两部分进行了并行化的实验,在多种并行方案中找到了最合适的方案并最终取得了良好的加速效果。
二、实验环境
        属性
操作系统        Ubuntu 16.04 LTS
物理内核数        2 个
编程语言        Python 3.6
分词工具        Jieba 1.8.1
内存大小        8 GB
三、前缀字典生成的并行化
1. 串行算法与并行可行性分析
Jieba分词中,实际分词的过程是从一条语句中出现的某个汉字开始,依次遍历其后的所有汉字来构成一个短语,之后在构建的前缀字典中查找该短语,若字典中有对应短语且其词频大于0,则可认为成功找到一个词语。该函数在jieba分词中由get_DAG函数完成,伪代码:
for word in sentence: // 遍历对语句中的每一个汉字
初始化短语列表为空
for 该汉字之后的每个汉字 i:
    短语 = sentence[word: i]
    if 前缀字典中存在该短语:
        if 词频大于1:
            将该短语加入word对应的短语列表
        endif
    else
        break
    endif
endfor
endfor
(算法的具体分析见第四章)
从伪代码中可看出,分词是否准确的关键在于所查找的前缀字典是否足够全面,以覆盖绝大部分常用的中文短语。若词典过小,则可能出现语句中部分有效短语未被识别的情况,不仅影响到该词语的查找,更可能影响该词语之后的短语的切割准确率。
进一步分析字典的生成过程,这一步在jieba分词中由gen_pfdict实现。在源码中,该函数接收一个指定格式的字典文件(dict.txt),文件中包含需要用到的所有的短语和其对应的词频、词性。代码:
def agen_pfdict(self, f):
    lfreq = {}
    ltotal = 0
    f_name = resolve_filename(f)
    for lineno, line in enumerate(f, 1):
        try:
            line = line.strip().decode('utf-8')
            word, freq = line.split(' ')[:2]
            freq = int(freq)
            lfreq[word] = freq  # 不同线程间无依赖
            ltotal += freq
            for ch in xrange(len(word)):
                wfrag = word[:ch + 1]
                if wfrag not in lfreq:
                    lfreq[wfrag] = 0
        except ValueError:
            raise ValueError(
                'invalid dictionary entry in %s at Line %s: %s' % (f_name, lineno, line))
    return lfreq, ltotal
该算法读取文件的全部内容并串行的逐行遍历,依次将得到的短语以python字典的形式加入全局的词典中,得到的词频累加到全局的总词频中;之后对于每个词语,找到所有可能的前缀组合(共L-1个,L为词语长度),设其词频为0并将其加入全局的词典中。该串行代码的时间复杂度为O(n),其中n为字典文件的行数。
在试图并行化该算法时首先分析不同数据间的依赖性。从整体上看,不同行所代表的短语直接显然不存在依赖性,且从常识也可知道字典中的每个词语都是相互独立的;但总代码中发现,由于前缀词典还包含了每个短语的所有前缀组合,所以不同短语之间有可能出现重复,比如在短语“机器人”和“机器学习”中,都存在前缀组合“机器”,同时添加进字典会有冲突。但实际上,从本文的实现代码中可看到,最终不同进程产生的字典在合并过程中会自动删除重复数据,因此并不存在上述的异常情况。
2. 并行算法实现
在分析了并行算法的可行性后,我试图使用多线程的方式直接拆分字典文件的遍历过程,并在每个线程结束任务后使用互斥锁更新全局的前缀字典和词频总和。代码:
def recordline(self, no):
    block = len(self.content) // self.threads
    start, end = no * block, no * block + block
    local_total, local_freq = 0, {}
    lines = self.content[start: end]
    for line in lines:
        try:
            word, freq = line.split(' ')[:2]
            freq = int(freq)
            local_freq[word] = freq  # 不同线程间无依赖
            local_total += freq
            for ch in xrange(len(word)):
                wfrag = word[:ch + 1]
                if wfrag not in local_freq:
                    local_freq[wfrag] = 0
        except ValueError:
            raise ValueError(
                'invalid dictionary entry ')
    self.lock.acquire()
    self.FREQ.update(local_freq)
    self.total += local_total
    self.lock.release()
    return local_freq, local_total
def gen_pfdict(self, f):
    self.content = f.read().decode("utf-8").split("\n")
    thread_list = []
    for i in xrange(self.threads):
        t = threading.Thread(target=self.recordline, args=(i, ))
        t.start()
        thread_list.append(t)
    for t in thread_list:
        t.join()
    return self.FREQ, self.total
在多线程版本的gen_pfdict中,函数开启指定个数的线程,并分配计算任务,之后等待所有线程结束后返回词典。在record_line中,每个线程根据线程ID得到遍历的起始位置与结束位置并开始生成自己的局部前缀字典,结束后更新全局字典。
在开启两个线程的情况下,理论上算法效率应较串行算法有明显的提升(起码大于串行算法),但在实际运行后发现,无论字典文件的规模多大(30万~800万行)或开启几个的线程数,并行算法花费的时间都基本等同于串行算法,不同条件下实验得到的加速比数据如下:
规模/线程数        2        3        4        6        8
10w        1.0311        0.8997        1.1201        0.9271        0.8264
30w        1.0944        0.9370        1.0244        1.0290        1.0813
表格 1不同字典规模, 线程数下的加速比
图 1不同字典规模, 线程数与加速比的关系
初步分析后认为,该现象的原因有可能是因为每个线程的计算任务过大,每个线程的任务分配不均,使得线程空闲等待的时间较长。对此,我使用了动态任务分配的方式为每个线程分配任务,代码:
def recordline(self, no):
    block = len(self.content) // self.threads
    start, end = no * block, no * block + block
    while self.start < len(self.content):
        start, end = self.start, self.start + self.block
        self.lock2.acquire()
        self.start = end + 1
        self.lock2.release()
        local_total, local_freq = 0, {}
        lines = self.content[start: end]
        for line in lines:
            try:
                word, freq = line.split(' ')[:2]
                freq = int(freq)
                local_freq[word] = freq  # 不同线程间无依赖
                local_total += freq
                for ch in xrange(len(word)):
                    wfrag = word[:ch + 1]
                    if wfrag not in local_freq:
                        local_freq[wfrag] = 0
            except ValueError:
                raise ValueError(
                    'invalid dictionary entry ')
        self.lock2.acquire()
        self.FREQ.update(local_freq)
        self.total += local_total
        self.lock2.release()
        return local_freq, local_total
给定文件规模为30万行时,使用不同的线程数和任务块,算法得到的加速比如下:
块大小/线程数        2        3        4        6        8
400        0.6686        0.5026        0.4582        0.4551        0.2773
800        1.3547        0.8130        0.4626        0.4708        0.3485
表格 2不同块大小, 线程数的加速比
图 2不同块大小, 线程数与加速比的关系
从表格中可看出,使用动态分配后,在线程数为2,块大小为800时算法的加速比会大于1,略微快于串行算法,当线程数大于2后,加速比迅速下降;但大部分情况下算法的效率仍然低于串行方案,且较之前的静态分配算法来说,平均加速比反而更低。
通过查阅资料后得知,python中由于GIL锁的存在(保证程序在多个CPU时的同一时刻仅有一个线程在执行),多线程仅能做到并发的任务处理,因此使用多线程版本的并行方案时,算法实际运行情况基本等同于串行算法。
因此才会出现当使用静态任务分配时,得到的加速比基本为1(此函数为计算密集型,实际加速比略小于1);在使用了动态任务分配时,又会因为更频繁的线程同步操作耗费大量时间,导致算法效率过低,加速比仅在0.5左右。
针对上述情况,为了做到真正的并行处理,实验中将多线程版本中开启线程的地方修改为了开启进程,得到了多进程版本的并行算法。
多进程版本的gen_pfdict:
def gen_pfdict(self, f):
    self.content = f.read().decode("utf-8").split("\n")
    process_list = []
    t1 = time.time()
    for i in xrange(self.threads):
        p = Process(target=self.recordline, args=(i,)) # 多进程版本
        # p = threading.Thread(target=self.recordline, args=(i,)) # 多线程版本
        p.start()
        process_list.append(p)
    for p in process_list:
        p.join()
    t2 = time.time()
    # f.close()
    return self.FREQ, self.total
使用了多进程并行后,算法效率得到了显著提升并且高于串行算法。实验中,使用jieba默认的字典文件(约30万行),同时开启两个线程时得到的加速比约为1.9466。
3. 加速效果及分析
实验在文件规模分别为5000、20000、100000、300000,进程数为2、3、4、6、8的情况下进行,每种组合分别独立的进行了多次实验,最后取加速比的均值作为该组合最终的实验加速比,实验数据见表格X。
从表格数据中可粗略地看出:
1. 进程数在4-6左右时,算法的加速比最大,最高可以达到2.35
2. 进程数在2-3左右时,算法的效率最大
规模/进程数        2        3        4        6        8
5k        1.0095        1.3235        1.2312        1.1827        0.9240
2w        1.2027        1.3235        1.9395        2.1496        1.8003
10w        1.8201        1.9844        2.3211        2.2670        2.1283
30w        1.9466        2.1957        2.3052        2.3588        2.3719
表格 3 不同字典规模, 进程数下的加速比
从折线图中可进一步印证上述结论,且可以看出:
1. 在字典规模较小时,加速效果并不明显
2. 加速比随进程数增多时先增大,之后趋于稳定,最后下降
3. 算法的并行效率随进程数增多而不断下降,在进程数为2时取得最大值
最终我们可以认为,在多进程版本的前缀词典生成函数中,实验中的并行算法在字典规模较大时可以起到一定的加速效果。
图 3 不同字典规模, 进程数与加速比的关系
图 4不同字典规模,, 进程数下的并行效率
三、语句分词的并行化
1. 串行算法分析
jieba的语句分词从原理上看,主要基于一个根据语句生成的DAG,分词过程等同于后向遍历DAG(有向无环图)的过程,由函数get_DAG完成。在该DAG中,节点表示语句中的每个汉字,有向边代表从起点到终点中经过的汉字可构成一个词语,构造DAG的过程及结果如下:
def __cut_all(self, sentence):
    dag = self.get_DAG(sentence)
    old_j = -1
    for k, L in iteritems(dag):
        if len(L) == 1 and k > old_j:
            yield sentence[k[0] + 1]
            old_j = L[0]
        else:
            for j in L:
                if j > k:
                    yield sentence[k:j + 1]
                    old_j = j
def get_DAG(self, sentence):
    self.check_initialized()
    DAG = {}
    N = len(sentence)
    for k in xrange(N):
        tmplist = []
        i = k
        frag = sentence[k]
        while i < N and frag in self.FREQ:
            if self.FREQ[frag]:
                tmplist.append(i)
            i += 1
            frag = sentence[k:i + 1]
        if not tmplist:
            tmplist.append(k)
        DAG[k] = tmplist
    return DAG
在get_DAG中函数依次拿到传入语句的每一个汉字grag;对于每一个frag,遍历其后的所有汉字并与frag构成一个词语,如果该词语不存在于前缀字典中(无论词频是否为0)循环结束,否则将所有词频为1的词语加入以当前汉字为起始的短语词典中;循环结束后将该局部词典加入全局词典并继续遍历下一个汉字。语句遍历结束后得到的DAG即为算法的分词结果,DAG以python的字典形式存储。
以句子”他已赢回主帅信任“为例,其在该算法中最后生成的DAG应为:
>>> {0: [0], 1: [1], 2: [2, 3], 3: [3], 4: [4, 5], 5: [5], 6: [6, 7], 7: [7]}
其中,键值“4”:对应的值为列表[4, 5]表示以“主”开头的词语有“主”和“主帅”。图形化描述的构造过程为:
图 5 DAG构造过程
从上述算法中可以看出,在拆分一条语句中,每个汉字是否可以组成短语与其他汉字有关,即存在依赖。比如例子中的“主帅”二字,其中“主”可以构成短语(DAG中有出度)是因为它后面的汉字为”帅“。因此,拆分单个语句进行并行化是困难的。但对于多条语句,从常识也可知道,其(由标点符号分隔的)不同语句之间是没有词性上的依赖的,且大部分使用中文分词的情况都是基于一大段文字的(很少有人会先手动拆分一段文字再逐句切割)。
        在jieba分词的源码中并没有区分sentence是由几句话构成,而是将其当作一句话来构造DAG。虽然从语义上看,得到的结果与独立构造每条语句的DAG相同;但从性能上看,不同语句的拆分是完全串行化的,因此效率较低。
我们要做的就是在大段文字切分的情况下来并行化切分过程达到加速效果。
图 6 分词流程图
2. 并行算法实现
从上一节的分析过程中可以知道,最直接的并行方法即是先将大段文字以句子为单位拆分,再并行的对每个语句进行分词。这里直接给出并行化过程:
def _pcut(sentence, cut_all=False, HMM=True):
    parts = strdecode(sentence).splitlines(True)
    if cut_all:
        result = pool.map(_lcut_all, parts,chunksize=chunk_size)
    elif HMM:
        result = pool.map(_lcut, parts,chunksize=chunk_size)
    else:
        result = pool.map(_lcut_no_hmm, parts,chunksize=chunk_size)
    for r in result:
        for w in r:
            yield w
该函数的第一行做的是将传入的文字(单个或多个句子)按行拆分成语句列表;之后的的工作就是使用进程池,每个进程计算列表中的一部分,大小由chunk_size指定,并将分词结果融合得到result;最后,函数以generator的形式返回每个分词结果。
3. 性能分析
实验中为了满足适合并行化的场景(包含多条语句的大段文字),选择的需要分词的语句相对较长,从新闻快报到中篇小说均有涉及。在使用不同的进程数和文章规模的情况下,得到以下数据:
规模/进程数        2        3        4        6        8
100        1.6047        1.6038        1.4012        1.3742        1.2961
2000        1.7457        1.8191        1.7412        1.7868        1.7866
8000        1.7368        1.7581        1.8298        1.7046        1.6715
20000        1.5080        1.4431        1.7581        1.5932        1.4992
表格 4 不同语句长度, 进程数下的加速比
从表格数据中可粗略看出,不同的进程数得到的加速比无较大差异且均小于2。并行效率在进程数为2时最大。
图 7 不同语句长度, 进程数与加速比的关系
图 8不同语句长度, 进程数与并行效率的关系
四、总结
本文研究了目前分词算法中使用最广泛的机械匹配算法,以jieba分词作为该算法的实现方案。结合并行计算技术对该算法做了细微的优化,加快了分词的速度。不足之处在于:
1. 更复杂的并行环境:算法仍仅停留在单机环境中,在集群环境中算法速度仍可能有较大的突破,需要在未来继续完善
2. 效率有待提高:在多进程分词时,加速比无法突破2,仍需要深入探讨该问题的原因。
与郭翠珍、刘怀英等人的并行方案相比,突出的地方在于,算法在保证了加速比的同时,整个并行体系更简单。
参考文献
[1]:郭翠珍,朱巧明,李培峰,钱培德.基于信息网格的分词服务的研究[J】.微电子学
与计算机,2006,23(5):P121.123
[2]:郭翠珍.基于网格的分词服务系统的研究与实现[D】.浙江苏州:苏州大学,2006
[3]:刘怀英.基于分布式并行计算的搜索引擎的研究与设计【D】.湖北武汉:武汉理工大学,2005
[4]:甘雨.基于并行计算的中文分词系统的研究与实现[D].广东工业大学,2010. DOI:10.7666/d.y1745731
[5]:孙铁利,刘延吉.中文分词技术的研究现状与困难[J】.信息技术,2009,7:P187.189
[6]:刘迁,贾惠波.中文信息处理中自动分词技术的研究与展望【J].计算机工程与应用,2006,3:P175.177.
[7]:费洪晓,康松林,朱小娟,谢文彪.基于词频统计的中文分词的研究【J].计算机工程与应用,2005,7:P67.68.



发表于 2021-8-31 14:29:32 | 显示全部楼层
快速回复 返回顶部 返回列表