论文部分内容阅读
自从1993年,数据库专家E.F.Codd提出联机分析处理(On-Line AnalyticalProcessing,OLAP)的概念以来,OLAP获得学术界和产业界的广泛关注,并取得了大量研究成果,创造了一个每年几十亿美元的商务智能市场。但据BISURVEY调查数据显示,在所罗列的OLAP产品的15个问题中,“性能太差”排在第一,而且用户关于性能的抱怨以很大的比例逐年上升。OLAP虽然采用了各种各样的优化策略,如实体化视图、预建索引、数据聚簇存放等,查询性能在一定程度上得到了提高,但仍然无法满足用户的需求,更难以支持复杂的基于用户驱动的规划类应用,例如What-if假设分析。 与此同时,近年来计算机体系结构发生了重大改变,突出特征是内存越来越大和多核CPU及图形处理器(Graphics Processor Units,GPU)的广泛应用。大内存允许将企业核心数据集完全加载到内存中,从而消除磁盘I/O,造成原有算法失效。另外,由于仅仅提高单核芯片的频率会产生过多的热量,而无法带来性能的提升,制造商通过在一个芯片内集成多个计算核心来提高性能,从而诞生了多核CPU;同时,GPU从图形图像处理进入通用计算领域,称为GPGPU(General-Purpose computing GPU)。 随着计算机体系结构的重大改变,必将为OLAP技术带来革命性的变化,而现有的OLAP技术大多数没有考虑现代计算机体系架构。设计基于现代计算机架构的OLAP技术和系统,已成为迫切需要解决的问题。 方体(Cube)计算是OLAP系统的一项核心功能,本文主要对OLAP中的方体计算技术进行了研究,包括缓存敏感的方体算法、基于多核CPU和GPU的并行方体算法等。What-if分析是OLAP中一种对性能要求较高的数据分析技术,也对What-if分析技术进行了研究,提出了基于MDX查询重写的解决方案。本文主要的研究工作如下: 1.提出了一种基于MDX查询重写的What-if分析解决方案。该方法通过将用户的What-if分析进行转换,从而避免了代价较高的方体重计算工作,提高了效率。通过多维代数表示what-if分析,对MDX扩展了Union、Difference、Update和子查询等操作,使之支持What-if分析。并在开源OLAP系统Mondrian中实现了相关操作,通过与基于差分表的What-if分析解决方案进行比较,方法具有较高的效率。 2.提出了缓存敏感的CC-BUC算法,算法利用现代处理器的缓存特征和列存储。原始数据每列单独存储,并分别处理。算法整合了自底向上和广度优先的分区策略。自底向上可以利用剪枝操作减少不必要的计算,广度优先保证每列单独处理和结果序列输出。算法有效的减少了内存I/O,加强了缓存(Cache)的本地性,提高了缓存行(Cache Line)利用率。缓存和TLB(Translation LookasideBuffer)缺失(Miss)被限定在一个列的范围。算法比原始BUC算法获得2-3倍的加速。针对多核CPU的特征,对经典的BUC和Multi-Way算法设计了并行版本,算法通过数据划分和共享扫描,保持了负载均衡,有效的提高了处理器的利用率,同时避免了缓存竞争,获得了较高的加速比。 3.提出了基于GPU的并行方体算法GPU-Cubing。该方法基础数据每列单独存储和处理,减少内存I/O,提高了缓存利用率。算法利用广度优先遍历的特点,多个分区同步处理,分区内多线程并行。GPU-Cubing与GPU的体系结构相适应,实现了块间和块内两层并行架构,通过详尽的实验分析,GPU-Cubing算法相比传统的方体算法获得了一个数量级的加速比。 4.设计了GPUOLAP原型系统,并已实现了部分模块。GPUOLAP系统定位为利用新一代计算机硬件体系结构开发实时内存联机分析处理系统(In-memory Real-time OLAP),从而全面提高OLAP的效率和应用范围。系统采用EXCEL为前端展示工具,利用GPU为计算引擎,利用CPU管理元数据,并利用CPU缓存进一步提高效率,支持What-if分析。GPUOLAP为提高国产商务智能软件的竞争力是一种有益的尝试。