实现于图形处理器之高效能平行多字符串比对算法
发布日期：2018-05-22
时间：5月22日9:30
地点：学术报告厅
主讲人：林政宏
主讲人简介：
林政宏(Cheng-Hung Lin)博士为台湾新竹清华大学资讯工程博士，现任台湾师范大学电机工程系副教授。目前的研究兴趣包括并行计算，图形处理器程序设计，机器学习和物联网。他的数篇论文获得高等级期刊IEEE Transactions on Computers (TC)、IEEE Transactions on Parallel and Distributed Systems (TPDS)、IEEE Transactions on Very Large Scale Integration (VLSI) Systems接受刊登。林政宏博士致力于开源软件的开发，他所开发的一个开源库，名为「PFAC」为目前全世界最快速的多字符串比对算法之一，公开于Google Code 与GitHub，获得许多研究者的引用与下载使用。此外，他於2017获得本院教学杰出奖，近年来并主持多项国际产学计划，与产业界合作密切。
发表论文：
1.Cheng-Hung Lin et al., "Accelerating Pattern Matching Using a Novel Parallel Algorithm on GPUs," in IEEE Transactions on Computers, Vol. 62, No. 10, pp. 1906-1916, 2013.
2.Cheng-Hung Lin et al., "Perfect Hashing Based Parallel Algorithms for Multiple String Matching on Graphic Processing Units, " in IEEE Transactions on Parallel and Distributed Systems (TPDS), Volume: 28, No. 9, Sept. 1, pp.2639 - 2650, 2017.
3.PFAC library, https://github.com/pfac-lib/PFAC
讲座内容概要：
多字符串比对(Multiple string matching)算法主要应用于网络入侵检测系统(Network Intrusion Detection System，NIDS) ，用来比对网络封包是否含有攻击病毒的字符串特征，其中以Aho-Corasick algorithm最被广泛使用。为改善网络入侵检测系统的效能以满足网络带宽的要求，改善多字符串比对算法的效能成为最重要的课题。报告人在过去的研究中，提出一个高效能的并行算法，称为Parallel Failureless Aho-Corasick (PFAC)算法，并实现于图形处理器上，效能上获得非常巨大的改善，此项成果于2013发表于IEEE Transactions on Computers期刊上。之后鉴于攻击病毒的字符串特征持续增加会导致内存需求大量增加，这对实现GPU是很大的挑战，因此为减轻该算法的内存需求，以更能适用于GPU上，报告人进一步提出使用完美哈希(Perfect hashing)来压缩内存，减少超过99％以上的内存需求，对于内存需求得到巨大的改善，此项研究成果于2017发表于IEEE Transactions on Parallel and Distributed Systems上。此外，这两项算法的研究成果也已开发成函示库，公开于Github (https://github.com/pfac-lib/PFAC)，获得许多研究者的下载与引用。本次讲座将详细介绍PFAC算法与内存优化技术。
