(交大论文）基于llvm的海量数据排序算法研究.pdf
免费下载
基于 LLVM 的海量数据排序算法研究
2019 年 12 月
目录
1 课题介绍 ......................................................... 3
2 相关工作 ......................................................... 3
2.1 海量数据排序算法 ........................................... 3
2.2 其他海量数据处理系统 ....................................... 5
2.2.1 Greenplum ............................................ 5
2.2.2 Hadoop 体系 .......................................... 5
2.2.3 Impala ............................................... 6
2.3 LLVM 相关应用 .............................................. 7
3 基于 LLVM 的海量数据排序算法 ...................................... 8
3.1 二维表排序算法 ............................................. 8
3.2 LLVM 代码生成技术 .......................................... 9
3.3 二维表排序优化测试 ........................................ 11
3.4 结果及分析 ................................................ 13
4 总结及展望 ...................................................... 15
1 课题介绍
LLVM（Low Level Virtual Machine，底层虚拟机）是一个开源编译框架，
最初是伊利诺伊大学的一个研究项目，目标是提供一种现代的、基于 SSA（静态
单变量赋值）的编译策略，能够支持任意编程语言的静态和动态编译。目前 LLVM
已经成长为一个由许多子项目组成的伞形项目，其中许多子项目被各种各样的商
业和开源项目用于生产，并被广泛用于学术研究。
LLVM 有着一套独立的、完善的、严格约束的中间代码(IR)。
LLVM 前端生成这种类汇编的中间代码，优化器进行优化和分析，后端生成对应
平台的机器码。
图 1 LLVM 编译器架构
此外，LLVM 还支持 JIT（Just-In-Time，即时编译）技术，能根据需要在程
序中编译并执行生成的机器码，以此提升动态语言的执行速度。
本课题中，我们的任务是探究 LLVM 在海量数据排序算法中的应用。我们通
过梳理海量数据场景的排序算法，调研了主流的开源分布式数据库，对目前市场
上的数据库架构、特点有了大致了解。在此基础上，我们学习了 LLVM 的使用，
并利用其 C-API 和 JIT 技术用于排序算法中，以减少判断分支，提升代码运行效
率。实验证明，在数据量较大的情况下，使用 LLVM 工具后对二维表排序的效率
有一定提升。
2 相关工作
2.1 海量数据排序算法
当今信息爆炸的时代，对于计算机系统数据处理中的搜索、过滤、挖掘等等
of 16
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
相关文档
评论