mg4355党委办公室、校长办公室 纪律检查委员会办公室(监察处) 党委巡察办公室 党委组织部 党委党校 党委宣传部(资讯办公室) 党委统战部 党委学生工作部 党委研究生工作部 党委保卫部 人民武装部 机关党委 财院校区党工委 离退休处党委 校工会 共青团mg4355委员会 发展规划办 教务处 现代工程训练中心 研究生院 招生与就业引导处 科学技术研究院 社会科学处 人力资源处 计划财务处 人才工程办公室 资产管理中心 国际合作与交流处 监察处 审计处 实验室建设与设备管理处 后勤与房地产管理处 基本建设处 离退休处 法律事务办公室 档案与校史馆 财院校区管委会 校友工作办公室 校园信息化建设与管理办公室 图书馆 远程与继续教育学院 空军选培办 两型社会研究院 国家超级计算长沙中心 互联网信息服务研究中心 资产经营有限企业 出版社有限责任企业 期刊社 后勤服务总企业 校医院 普通教育与继续教育管理办公室 招标与采购中心 学生创新创业中心
机械与运载工程学院 电气与信息工程学院 材料科学与工程学院 信息科学与工程学院 建筑学院 环境科学与工程学院 土木工程学院 设计艺术学院 化学化工学院 生物学院 数学学院 物理与微电子科学学院 经济与贸易学院 金融与统计学院 工商管理学院 法学院 马克思主义学院 资讯传播与影视艺术学院 教育科学研究院 体育学院 中国语言文学学院 岳麓书院 外国语学院 国家高效磨削工程技术研究中心 汽车车身先进设计制造国家重点实验室 化学生物传感与计量学国家重点实验室 经济管理研究中心 机器人学院 公共管理学院 艺术教育中心
当前位置: mg4355 >> 校园生活 >> 学术活动 >> 学院讲座 >> 正文
统计数据 / lectrue notice
  • 排序 学院 发文量
    1 物理与微电子科学学院 177
    2 岳麓书院 166
    3 机械与运载工程学院 155
    4 化学化工学院 154
    5 材料科学与工程学院 82
    6 数学与计量经济学院 75
    7 土木工程学院 69
    8 信息科学与工程学院 64
    9 教务处 42
    10 建筑学院 40
  • 排序 学院 发文量
    11 经济与贸易学院 38
    12 电气与信息工程学院 35
    13 生物学院 34
    14 工商管理学院 28
    15 外国语学院 15
    16 法学院 15
    17 资讯传播与影视艺术学院 9
    18 研究生院 8
    19 经济与管理研究中心 6
    20 马克思主义学院 5
    21 中国语言文学学院 4
信科院:Speedup Set Intersections in Graph Algorithms using SIMD Instructions (SIGMOD 2018)
学术地点 信息科学与工程学院220(原106) 主讲人 Lei Zou
讲座时间 2019年11月2日(周六)下午2:30


Speedup Set Intersections in Graph Algorithms using SIMD Instructions (SIGMOD 2018)




Lei Zou received his BS degree and Ph.D. degree in Computer Science at Huazhong University of Science and Technology (HUST) in 2003 and 2009, respectively. He received a CCF (China Computer Federation) Doctoral Dissertation Nomination Award in 2009, won Second Class Prize of CCF Natural Science Award in 2014 and Second Class Prize of Natural Science of the Ministry of Education, China in 2017. Since September 2009, he joined Institute of Computer Science and Technology (ICST) of Peking University (PKU) as a faculty member. He has been a professor in PKU since August 2017.Before joining PKU, Lei Zou visited Hong Kong University of Science and Technology in 2007 and University of Waterloo in 2008 as a visiting scholar. His recent research interests include graph databases, knowledge graph, particularly in graph-based RDF data management. He has published more than 40 papers, including more than 30 papers published in reputed journals and major international conferences, such as SIGMOD, VLDB, ICDE, AAAI, TODS, TKDE, VLDB Journal.


In this talk, I focus on accelerating a widely employed computing pattern—set intersection, to boost a group of relevant graph algorithms. Graph’s adjacency-lists can be naturally considered as node sets, thus set intersection is a primitive operation in many graph algorithms. We propose QFilter, a set intersection algorithm using SIMD instructions. QFilter adopts a merge-based framework and compares two blocks of elements iteratively by SIMD instructions. The key insight for our improvement is that we quickly filter most of unnecessary comparisons in one byte-checking step.We also present a binary representation called BSR that represent sets in a compact layout. From the combination of QFilter and BSR, we achieve dataparallelism in two levels—inter-chunk and intra-chunk parallelism. Furthermore, we find that node ordering impacts the performance of intersection in graph algorithms by affecting the compactness of BSR. We formulate the graph reordering problem as an optimization of the compactness of BSR, and prove its strong NP-completeness. Thus we propose an approximate algorithm that can find a better ordering and improve the performance by 39% on average.

下一条:信科院:Maximum Elastic Scheduling Based on the Hose Model

XML 地图 | Sitemap 地图