南开19年9月考试《并行程序设计》考核要求[答案]

南开19年9月考试《并行程序设计》考核要求[答案]答案

南开大学现代远程教育学院考试卷 
2019年度春季学期期末(2019.9)  《并行程序设计》
主讲教师： 王刚
 
学习中心：____________________________    专业：_______________________
姓    名：_________________ 学  号：_______________ 成绩：___________
 
一 、请同学们在下列题目中任选一题，写成期末论文。
（一）并行算法研究类
对某一问题，研究其并行算法的设计、实现，分析其性能，进行实验验证，撰写研究论文。例如：
1、对矩阵相乘问题，设计pthread多线程结合SSE/AVX的两层并行算法，实现并行程序。讨论算法层面不同策略对性能的影响，例如多个线程间不同的任务分配方式、不同的线程同步策略等，讨论不同并行编程方法对性能的影响，例如SSE/AVX的对齐和不对齐内存访问等等。对不同的矩阵规模、不同的线程数测试程序性能，撰写研究论文。
2、对高斯消去法问题（其串行算法伪代码示意如下面算法1所示），设计pthread多线程结合SSE/AVX的两层并行算法，实现并行程序。讨论算法层面不同策略对性能的影响，例如多个线程间不同的任务分配方式、不同的线程同步策略等，讨论不同并行编程方法对性能的影响，例如SSE/AVX的对齐和不对齐内存访问等等。对不同的矩阵规模、不同的线程数测试程序性能，撰写研究论文。
3、其他类似难度的问题。
（二）并行编程工具调研类
对某种并行编程工具进行调研，选取某个问题（例如矩阵相乘问题），用这种编程工具编写并行程序求解这个问题，进行实验验证，撰写研究论文介绍这种并行编程工具的特色、基本编程（使用）方法、如何用它解决实际问题（以你选定的问题为例）。例如：
1、C++、Java等语言本身对并行编程提供的支持。
2、Hadoop MapReduce编程工具。
3、其它并行编程工具。
 

南开19年9月考试《并行程序设计》考核要求[答案]标准满分答案

专业答案:----

二、论文写作要求
（一）并行算法研究类
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