高性能数据挖掘技术及其应用

刘 莹 博 士 副 教 授中 国 科 学 院 研 究 生 院 信 息 科 学 与 工 程 学 院高 性 能 数 据 挖 掘 技 术 及 其 应 用 2021-4-23 Ying Liu 2 简 介n 1999/07， 北 京 大 学 ， 计 算 机 科 学 与 技 术 ， 学 士n 2001/12， 美 国 西 北 大 学 (Northwestern University)， 计 算 机 工 程 ， 硕 士n 2005/06， 美 国 西 北 大 学 (Northwestern University)， 计 算 机 工 程 ， 博 士n 2005/06 2005/11， 助 理 研 究 员 ， 美 国 西 北 大 学n 2006/01 今 ， 副 教 授 ， 中 国 科 学 院 研 究 生 院 信 息 科学 与 工 程 学 院 ， 虚 拟 经 济 与 数 据 科 学 研 究 中 心 2021-4-23 Ying Liu 3 科 研 经 历n 美 国 国 家 航 空 航 天 局 (NASA): Mass Storage Performance Information Systemn 美 国 能 源 部 (DOE)： Scientific Data Management Integrated Software Infrastructure Centern Intel公 司 ： Characterizing Scalable Data Mining Kernels/Primitives on SMPsn 美 国 国 家 科 学 基 金 (NSF): High-Performance Techniques, Designs and Implementation of Software Infrastructure for Change Detection and Mining (IIS-0536994) 2021-4-23 Ying Liu 4 科 研 经 历n 负 责 中 国 人 民 银 行 横 向 课 题 个 人 信 用 评 分 系 统 研 究 n 主 持 自 然 科 学 基 金 创 新 群 体 项 目 子 课 题 海 量 数 据 的 挖 掘技 术 的 研 究 n 主 持 自 然 科 学 基 金 重 点 项 目 子 课 题 可 信 软 件 过 程 的 基 本属 性 和 度 量 模 型 n 主 持 教 育 部 留 学 归 国 人 员 启 动 基 金 基 于 传 感 器 网 络 的 交通 数 据 流 挖 掘 n 主 持 中 科 院 研 究 生 院 院 长 基 金 基 于 效 用 的 数 据 挖 掘 理 论与 技 术 的 研 究 2021-4-23 Ying Liu 5 科 研 成 果n 大 规 模 科 学 模 拟 计 算 中 的 高 性 能 数 据 挖 掘 天 体 物 理 模 拟 中 的 聚 类 算 法 HOP的 并 行 方 案 适 用 于 超 大 规 模 的 科 学 模 拟 计 算 中 ， 取 得 了 非 常 好 的 加 速 比 被 美 国 圣 地 亚 哥 超 级 计 算 中 心 (SDSC)使 用n 可 扩 展 的 数 据 挖 掘 算 法 的 性 能 评 估 可 扩 展 的 数 据 挖 掘 算 法 的 性 能 评 估 发 布 了 NU-Minebench， 第 一 个 数 据 挖 掘 算 法 的 基 准 组（ benchmark suite)， 被 下 载 1666次 （ 2005/06/15 今 ） 被 Intel公 司 使 用 2021-4-23 Ying Liu 6 提 纲n 数 据 挖 掘 简 介n 高 性 能 （ 并 行 /分 布 式 ） 数 据 挖 掘n 应 用 实 例 介 绍 天 体 模 拟 (cosmological simulation) 天 文 (astronomy) 航 天 (space operation) 生 态 系 统 (ecosystem) 生 物 信 息 学 (bioinformatics)n 总 结 2021-4-23 Ying Liu 7 数 据 挖 掘n 自 动 的 、 从 ” 海 量 ” 数 据 中 挖 掘 出 隐 藏 的 、 潜 在的 、 有 价 值 的 知 识 的 技 术n 挖 掘 的 结 果 （ 知 识 ） 是 用 户 感 兴 趣 的 ， 管 理 决 策支 持 系 统n 数 据 挖 掘 技 术 的 特 点 海 量 数 据 从 历 史 的 数 据 中 自 动 寻 找 高 效 可 扩 展 性 好 模 型 更 新 快 应 用 性 强 2021-4-23 Ying Liu 8 数 据 挖 掘 的 动 机 商 业 角 度n 收 集 和 存 储 的 数 据 量 太 大 电 子 商 务 商 业 交 易 数 据 信 用 卡 交 易 保 险n CPU的 处 理 速 度 每 年 增 长 15%， 不 能 满 足数 据 量 增 长 的 需 要n 提 供 更 好 的 个 性 化 服 务 ， 先 进 的 客 户 关 系管 理 手 段 等 数 据 爆 炸 ， 知 识 贫 乏 2021-4-23 Ying Liu 9 数 据 挖 掘 的 动 机 科 学 计 算 角 度n 海 量 数 据 (GB/hour) 遥 感 数 据 天 文 望 远 镜 巡 天 基 因 表 达 微 阵 列 (Microarrays) 科 学 模 拟n 帮 助 科 学 家 对 数 据 进 行 多 种 分 析 ， 如 分 类 、 分 层 等 2021-4-23 Ying Liu 10 数 据 挖 掘 的 起 源n 交 叉 学 科 统 计 方 法 机 器 学 习 方 法 神 经 网 络 数 据 库 并 行 计 算n 传 统 方 法 的 局 限 性 在 于 海 量 数 据 高 维 数 据 异 构 数 据 复 杂 数 据 类 型 2021-4-23 Ying Liu 11 流 程Data Cleaning and IntegrationDatabasesData WarehouseSelection and TransformationData MiningPattern EvaluationFlat files 2021-4-23 Ying Liu 12 数 据 挖 掘 的 主 要 技 术n 聚 类 (clustering)n 异 常 点 检 测 (anomaly detection)n 分 类 (classification)n 预 测 (prediction)n 关 联 规 则 (association rules mining)n 顺 序 模 式 (sequential pattern)n 时 间 序 列 (time-series ) 2021-4-23 Ying Liu 13 聚 类n 自 动 将 数 据 分 成 若 干 簇 ， 使 得 不 同 簇的 数 据 项 相 似 性 最 小 ， 簇 内 数 据 项 的相 似 性 最 大 。 （ 不 依 赖 于 预 先 定 义 好的 类 ， 不 需 要 训 练 集 ）n 应 用 模 式 识 别 地 理 信 息 系 统 图 像 处 理 生 物 基 因 序 列 分 析 天 体 模 拟 文 档 聚 类 n 常 用 算 法 K-means, BIRCH, DBSACN, EM npx.nfx.n1x . ipx.ifx.i1x . 1px.1fx.11x 2021-4-23 Ying Liu 14 异 常 点 检 测n 从 数 据 集 中 找 出 与 正 常 行 为 有 显 著 差 异 的 数 据 项n 应 用 信 用 卡 欺 诈 医 疗 数 据 分 析 网 络 入 侵 检 测n 常 用 算 法 聚 类 Statistical-based, Distance-based, Deviation-based 2021-4-23 Ying Liu 15 分 类n 根 据 从 训 练 集 数 据 （ training data） 中 分 析 得 来 的 数 据 各 域与 已 知 类 别 间 的 函 数 关 系 ， 预 测 一 个 新 的 数 据 记 录 的 类 别n 应 用 市 场 预 测 客 户 关 系 管 理 （ CRM） 营 销 策 略 信 用 评 分n 常 用 算 法 决 策 树 贝 叶 斯 分 类 神 经 网 络 K-近 邻 2021-4-23 Ying Liu 16 分 类 天 气 湿 度 温 度 风 况 运 动晴 热 高 无 不 适 合晴 热 高 有 不 适 合多 云 热 高 无 不 适 合 class 2021-4-23 Ying Liu 17 预 测n 根 据 历 史 数 据 建 立 数 学 模 型 ， 预 测 新 的 记 录 的 一 个 属 性的 值 。n 回 归 （ Regression） 方 法 ， 线 性 、 非 线 性 曲 线 拟 合n 常 用 算 法 线 性 回 归 Logistic回 归 y xy = x + 2021-4-23 Ying Liu 18 关 联 规 则n 从 数 据 中 找 出 频 繁 集 （ frequent itemsets)， 并 且 找 出 频繁 集 中 数 据 项 间 的 相 互 影 响 作 用n 应 用 市 场 组 合 分 析 套 装 产 品 分 析 目 录 设 计 交 叉 销 售n 常 用 算 法 Apriori DIC FP-growth A为 “ 北 京 附 近 有 冷 涡 ” ，B为 “ 北 京 地 区 有 降 水 ” ,A、 B同 时 出 现 的 概 率 较 高(s=60%), P(B|A)高 (c=75%),A 导 致 BTID Items10 A, B, D20 A, C, D30 A, B, E40 B, E, F50 A, B, D, E, F 2021-4-23 Ying Liu 19 顺 序 模 式n 从 与 时 间 顺 序 有 关 的 数 据 中 找 出 频 繁 的 （ frequent events)， 然 后 寻 找 出 频 繁 集 中 数 据 项 间 的 相 互 影 响作 用n 应 用 电 信 市 场 营 销 DNA序 列 分 析n 常 用 算 法 GSP SPADE 买 PC 买 打 印 机 买 墨 盒 买 新 的 CPU Time凡 是 购 买 了 新 电 脑 的 顾 客 ， 9个 月 后 很 可 能又 要 买 新 的 CPU 营 销 手 段 ： 9个 月 后 主 动 向 用 户 推 荐 ， 以 保 持 客 户 2021-4-23 Ying Liu 20 时 间 序 列n 随 时 间 变 化 的 数 值 序 列 ， 分 析 序 列 的 周 期 ， 不同 序 列 的 相 似 度 ， 以 及 预 测 序 列 的 趋 势n 应 用 股 票 价 格 医 疗 诊 断 电 力 消 耗 交 通 流 timeprice 2021-4-23 Ying Liu 21 Why High Performance Data Mining?n Lots of data being collected in commercial and scientific world, massive data setsn Strong competitive pressure to extract and use the information from the data, e.g. Climate simulation Astrophysics Molecular biology 2021-4-23 Ying Liu 22 Why High Performance Data Mining?n Data and/or computational resources needed for analysis are often distributedn Sometimes the choice is distributed data mining or no data mining Ownership, privacy, security issues INTERNETnetwork network network Accelerate the computation Use more memory from multiple machinesSolution: parallel computing ! 2021-4-23 Ying Liu 23 Progress in HPC - past 6 decades ENIACS 1945 100 K Hz 5 K Additions/second 357 Multiplications/second IBM Blue Gene/L CPU power increasing by a factor of 30-100 every decade Multi-Giga Hz, multi-Gigabyte, multi-core CPUs are commodity Teraflops computers are common Petaflops scale computing within reach Jaguar - Cray XT4/XT3 - Oak Ridge National LaboratoryEKA (HP Cluster Platform 3000BL) - Computational Research Laboratories 2021-4-23 Ying Liu 24 TOP 10 Machines 7/2008Rank Site Computer #proc TF/s Country1 DOE/NNSA/LANL IBM 122400 1375.78 USA2 DOE/NNSA/LLNL IBM 212992 596.38 USA3 Argonne National Laboratory IBM 163840 557.06 USA4 Texas Advanced Computing Center/Univ. of Texas Sun 62976 503.81 USA5 DOE/Oak Ridge National Laboratory Cray 30976 260.20 USA 6 Forschungszentrum Juelich (FZJ) IBM 65536 222.82 Germany7 New Mexico Computing Applications Center (NMCAC) SGI 14336 172.03 USA8 Computational Research Laboratories, TATA SONS HP 14384 172.61 India9 IDRIS IBM 40960 139.26 France10 Total Exploration Production SGI 10240 122.88 France 2021-4-23 Ying Liu 25 2021-4-23 Ying Liu 26 Supercomputers in Chinan 2004年 6月 ， 曙 光 超 级 服 务 器 ， 每 秒 峰 值运 算 速 度 万 亿 次 ， 列 全 球 第 十 ， 位 于 上 海 超 级 计算 中 心n 2008年 6月 ， 曙 光 5 超 级 服 务 器 ， 每 秒 峰 值 运算 速 度 160万 亿 次 ， 位 于 上 海 超 级 计 算 中 心n 联 想 深 腾 6800网 格 超 级 计 算 机 ， 265个 四 路 节 点 机 ，1060个 处 理 器 芯 片 ， 每 秒 峰 值 运 算 速 度 5万 亿 次 ， 列2003年 11月 世 界 TOP500第 14名 ， 位 于 中 科 院 网 络 信息 中 心 2021-4-23 Ying Liu 27 体 系 结 构 (Architectures)n Shared Address Space All processors share a single global address space Single address space facilitates a simple programming model Examples: SGI Origin 3000, IBM SP2PC PC PC IM M MProcessorsCachesInterconnectMemory PC PC PCIM M M ProcessorsCachesInterconnectMemory(a) UMA (b) NUMA 2021-4-23 Ying Liu 28 体 系 结 构 (Architectures)n Message passing platform Each processor has local memory with local address space Only way to exchange data is using explicit message passing Time taken for message depends on the relative locations of the source and destination processors Performance of a parallel program determined by how well the location of data matches its use Example: clusters, IBM SP and SGI Origin 3000 support it Processing UnitProcessing UnitProcessing Unit objectmemoryobjectmemoryobjectmemorymessages 2021-4-23 Ying Liu 29 体 系 结 构 (Architectures)Clusters of 4-way SMPsn Hybrid Most popular 2021-4-23 Ying Liu 30 Parallel Programmingn Construct or modify a series program for solving a given problem on a parallel machinen The programmers responsibility to identify the ways to decompose the computation and extract concurrencyn An exact copy of the program on each processorn Complex programming 2021-4-23 Ying Liu 31 Parallel Programmingn Data parallelism Partition the data across processors Each processor performs the same operations on its local data partitioningn Task parallelism Assign independent modules to different processors Each processor performs different operations 2021-4-23 Ying Liu 32 提 纲n 数 据 挖 掘 简 介n 高 性 能 （ 并 行 /分 布 式 ） 数 据 挖 掘n 应 用 实 例 介 绍 天 体 模 拟 (cosmological simulation) 航 天 (space operation) 生 态 系 统 (ecosystem) 生 物 信 息 学 (bioinformatics) 天 文 (astronomy)n 总 结 2021-4-23 Ying Liu 33 天 体 模 拟 （ Cosmological Simulation）n N-body simulation numerically approximates the evolution of the universen Each body represents a galaxy or a star, and bodies attract each other through the gravitational forcen Similar applications Protein folding Turbulent fluid flow simulation 2021-4-23 Ying Liu 34 2021-4-23 Ying Liu 35 HOP Clustering Algorithmn Difficult to discern which particles belong to the same group or cluster, computational intensiven HOP, density-based clustering algorithm by Daniel J. Eisenstein, Piet Hut, 1998n Automatically identify groups of particles in N-body simulationn Particle attributes: mass, three-dimension coordinatesn Four processing stages: Constructing a KD tree Generating density Hopping Grouping 2021-4-23 Ying Liu 36 1 st 2 nd 2 nd 3 rd3 rd 3 rd 3 rd 3 rd2 nd1 st bucket Find the median particle on the longest axis Recursively bisect the particles along the longest axis Nearby particles are in the same sub-domain Each internal node contains boundary n Two-dimensional KD TreeHOP Clustering Algorithm 2021-4-23 Ying Liu 37 n Generating density Traverse the tree to find Ndens neighbors for every particle Assign an estimated density to every particlen Hopping Associate each particle with its densest neighbor Each particle “hops” to its densest neighbor till it reaches a particle that is its own densest neighborn Grouping Define particles associated to the same densest neighbor as a group Refine and merge groupsHOP Clustering Algorithm 2021-4-23 Ying Liu 38 v Key idea n Load balance Assign approximate equal number of particles to each processorn Minimize communication overheads Requests for potential required remote particles are packed into a single message, and the required particles are transferred to the requesting processorsHOP Clustering Parallelization Ying Liu, Wei-keng Liao, Alok Choudhary, Northwestern University, USA 2021-4-23 Ying Liu 39 P2P1 P4P3 DomainDecompositionTreeLocalTree GlobalTreeP1 P2 P3 P41 st 2 nd2 nd3 rd 3 rd 3 rd3 rd Assign approximate equal number of particles to each processor Find the median particle in parallel on the longest axis Bisect particles along the longest axis Exchange particles between bisected processors Build local KD tree Maintain a global tree on each processor with no real particle transfer n Construct Parallel KD TreeHOP Parallelization 2021-4-23 Ying Liu 40 n Generate Density Intersection test Send out a single message to request the required remote particles Transfer the required particles Search for neighbors Calculate density P1 P2 P3 P4psearch radiusr intersecting with local bucketintersecting with non-local bucket intersecting with non-local bucket HOP Parallelization 2021-4-23 Ying Liu 41 n Hopping Hop to its highest density neighbor Book the required remote particles and send out requests Transfer the required particles to requesting processorsn Grouping Particles linked to the same densest particle are defined as a group Refine groupsHOP Parallelization 2021-4-23 Ying Liu 42 Experimentn ENZO An adaptive mesh refinement (AMR), grid-based hybrid code (hydro + N-Body), simulate the cosmological structure formation Use the algorithms of Berger & Collela to improve spatial and temporal resolution in regions of large gradients, such as gravitationally collapsing objects Software is flexible, can simulate a wide range of cosmological situations Parallelized using MPI and can run on any shared or distributed memory parallel supercomputer or clusters Simulations on 1024 processors have been carried out on the San Diego Supercomputing Centers Blue Horizon, an IBM SP 2021-4-23 Ying Liu 43Data set 1 Data set 2 Data SourcenEach data set contains 491520 particles 2021-4-23 Ying Liu 44 Total Timeon 1 ,4, 8, 16, 32, 64 processors 491520 particles, Ndens=128, bucket size=16 0 20 40 60 80 100 120 IBM SP2 SGI Orig in20 00 Linu x Cl uste r Time ( sec) Constructing KD Tree Generating Density Hopping Grouping Total Timeon 1 ,4, 8, 16, 32, 64 processors 491520 particles, Ndens=128, bucket size=16 0 20 40 60 80 100 120 140 IBM SP2 SGI Orig in20 00 Linu c Cl uste r Time ( sec) Constructing KD Tree Generating Density Hopping Grouping Density generation is the most time consuming stage Data set 2 takes longer execution time n Total Execution Time Data set 1 Data set 2 Performance Evaluation 2021-4-23 Ying Liu 45 The overall performance scales up on IBM SP2 and SGI Origin2000 when increasing number of processors It scales up to 32 processors on Linux Cluster n Speedups for Total Execution Time Speedups 491520 particles, Ndens=128, bucket size=16 0 5 10 15 20 25 0 8 16 24 32 40 48 56 64 Number of Processors IBM SP2 SGI Origin2000 Linux Cluster Speedups 491520 particles, Ndens=128, bucket size=16 0 5 10 15 20 25 0 8 16 24 32 40 48 56 64 Number of Processors IBM SP2 SGI Origin2000 Linux ClusterData set 1 Data set 2 Performance Evaluation 2021-4-23 Ying Liu 46 Generating density stage scales up on IBM SP2 and SGI Origin2000 It scales up to 32 processors on Linux Cluster n Speedups for Generating Density Speedups 491520 particles, Ndens=128, bucke sizet=16 0 5 10 15 20 25 0 8 16 24 32 40 48 56 64 Number of Processors IBM SP2 SGI Origin2000 Linux Cluster Speedups 491520 particles, Ndens=128, bucket size=16 0 5 10 15 20 25 0 8 16 24 32 40 48 56 64 Number of Processors IBM SP2 SGI Origin2000 Linux ClusterData set 1 Data set 2 Performance Evaluation 2021-4-23 Ying Liu 47 Communication Time 491520 particles, Ndens=128, bucket size=16 0 1 2 3 4 5 6 7 8 IBM SP2 SGI Origin2000 Linux Cluster Tim e(s ec) 4 procs 8 procs 16 procs 32 procs 64 procs Communication Time 491520 particles, Ndens=128, bucket size=16 0 2 4 6 8 10 IBM SP2 SGI Origin2000 Linux Cluster Tim e(s ec ) 4 procs 8 procs 16 procs 32 procs 64 procsData set 1 Data set 2 Communication time does not scale well Communication time increases when number of processors goes beyond 32 n Communication CostsPerformance Evaluation 2021-4-23 Ying Liu 48 提 纲n 数 据 挖 掘 简 介n 应 用 实 例 介 绍 天 体 模 拟 (cosmological simulation) 天 文 (astronomy) 航 天 (space operation) 生 态 系 统 (ecosystem) 生 物 信 息 学 (bioinformatics)n 高 性 能 （ 并 行 /分 布 式 ） 数 据 挖 掘n 总 结 2021-4-23 Ying Liu 49 天 文 （ Astronomy)University of Baltimore, USAn Predictive Mining of Time Series Data in Astronomy 发 觉 相 同 天 体 或 者 不 同 天 体 间 有 趣 的 周 期 性 的 行 为 或 者 巧 合 。 应 用 这种 周 期 性 的 行 为 来 预 测 或 者 分 析 天 体 行 为n 算 法 将 每 个 望 远 镜 收 集 的 数 据 看 成 时 间 序 列 对 时 间 序 列 用 sliding window处 理 ， 得 到 子 序 列 对 这 个 数 据 的 子 序 列 使 用 聚 类 的 算 法 进 行 分 析 ， 得 到 这 个 子 序 列 中 各种 pattern 用 这 些 pattern来 表 示 这 段 时 间 序 列n 意 义 如 果 pattern A出 现 在 时 间 序 列 1当 中 ， 那 么 在 此 后 T时 间 之 内 有 c%的几 率 ， pattern B会 出 现 在 时 间 序 列 1， 得 到 有 意 义 的 关 联 规 则 对 不 同 的 时 间 序 列 的 pattern进 行 比 较 2021-4-23 Ying Liu 50 天 文 （ Astronomy)分 析 天 体 周 期 性 行 为 的 框 架 2021-4-23 Ying Liu 51 天 文 （ Astronomy)Lawrence Livermore National Laboratory, USAn Mining the FIRST survey for galaxies with a bent-double morphology FIRST: Faint Images of the Radio Sky at Twenty Centimeters Radio equivalent of the Palomar Observatory Sky Survey (POSS) 10,000 square degrees survey of the North Galactic Cap Using the NRAO Very Large Array (VLA), B configuration 2021-4-23 Ying Liu 52 天 文 （ Astronomy)n The FIRST data 1.8 pixels, resolution 5,rms0.15mJy 90 radio sources per square-degree at 1mJy threshold The morphological type of a radio source provides clues to their emission mechanism, source class, and the properties of the surrounding medium The raw data from the telescopes is extensively processed Images maps and catalog available (sundog.stsci.edu) 2021-4-23 Ying Liu 53 天 文 （ Astronomy)n Use data mining to find “bent-doubles” in FIRSTn FIRST astronomers interested in “bent-doubles”indicates presence of clusters of galaxies first “identify” using a visual technique followed by optical observations and checks with other surveysn Visual identification is no longer feasible subjective, tedious, likely to miss cases .900,000 galaxies in the full surveyn Goal: replace the visual identification of bent doubles by a semi-automated one 2021-4-23 Ying Liu 54 天 文 （ Astronomy)n Detecting bent-double galaxies in 250GB image data, 78MB catalog data (as of 7/2000) 2021-4-23 Ying Liu 55 天 文 （ Astronomy)n Methodology Group the catalog entries into a “galaxy” Separate sources based on number of catalog entries 1-entry sources unlikely to be bent-doubles 3-entry sources all “interesting”study the 2-and 3-entry sources separatelyresults in splitting a small training set (313 - 118 + 195) 2021-4-23 Ying Liu 56 天 文 （ Astronomy) Calculate features for a galaxy (103 features) Use the features to train a decision tree Use the tree to classify the unlabeled galaxies and validate the results Use validated results to enhance training set 2021-4-23 Ying Liu 57 天 文 （ Astronomy)n Results using a single tree for 3-entry sources were satisfactory Labeled training set: 167 bents, 28 non-bents Performed several inner iterations using pruned trees (c5.0 decision tree software) Ten 10-fold cross-validation errors: mean (SE)using all the features: 9.7%(0.3%)using triple features only: 10.7%(0.3%) Discriminating features include geometrically calculated angles, relative distances, ellipticity and symmetry measures 2021-4-23 Ying Liu 58 New Trends GPUs+CUDAn GPU (Graphic Processing Unit), 图 形 处 理 器 ， 专 用 处 理 器 CPU和 GPU每 秒 浮 点 运 算 数 2021-4-23 Ying Liu 59 New Trends GPUs+CUDAn GPU与 CPU结 构 区 别 更 多 的 晶 体 管 高 内 存 带 宽 驱 动 的 多 核n GPU优 势 成 本 低 （ 几 百 美 元 ） 多 线 程 （ 几 百 个 线 程 ） 处 理 计 算 密 集 型 数 据 的效 率 远 高 于 CPUn GPU缺 点 编 程 难 2021-4-23 Ying Liu 60 New Trends GPUs+CUDAn CUDA 一 个 基 于 业 界 标 准 的C语 言 的 编 程 环 境 ，用 于 开 发 GPU的 计 算应 用 程 序 GPU并 行 执 行 非 常 多线 程 CPU把 计 算 密 集 的 、并 行 度 高 的 部 分 卸 载给 GPU 易 编 程 软 件 层 次 结 构 2021-4-23 Ying Liu 61 New Trends GPUs+CUDAn 原 来 只 能 由 workstation完 成 的 工 作 ， 可 以 由 PC完 成n 超 级 计 算 一 次 革 命 性 的 进 步n 成 功 例 子 斯 坦 福 大 学 利 用 CUDA开 发 了 在 GPU上 运 行 的 foldinghome,最 高运 行 速 度 比 CPU快 140倍 。 Foldinghome进 行 蛋 白 质 折 叠 模 拟 ，找 出 蛋 白 质 误 折 叠 的 后 果 。 Elemental Technologies利 用 CUDA开 发 了 在 使 用 基 于 GPU的Badaboom软 件 后 ， 视 频 编 码 的 转 换 过 程 最 高 比 传 统 方 法 快 了 18倍 。 有 了 CUDA的 帮 助 ， 地 理 信 息 系 统 中 ， 从 前 需 要 20分 钟 才 能 完 成 的运 算 现 在 只 需 30秒 即 可 完 成 ， 而 从 前 需 要 30到 40秒 钟 完 成 的 运 算 现在 能 够 实 现 实 时 运 算 。 CUDA技 术 是 自 微 处 理 器 发 明 以 来 计 算 行 业 内 所 诞 生 的 最 具 革 命 性 的 技 术 。 ” M 2021-4-23 Ying Liu 62 New Trends GPUs+CUDA 伊 利 诺 伊 大 学 (UIUC)利 用 GPU进 行 并 行 分 子 动 力 学 研 究 ， 用 于 分 析大 型 生 物 分 子 系 统 。 “ 未 来 计 算 性 能 的 加 强 将 直 接 来 自 多 核 GPU（ 图 形 处 理 器 ） 大 规 模 并 行 硬 件 。 目 前 的 最 大 挑 战 是 将 代 码 实 现 并行 化 ， 以 便 更 好 地 利 用 相 关 的 硬 件 ， 而 CUDA取 得 了 突 破 性 的 进 展 ，推 进 了 这 一 领 域 的 发 展 。 ” 胡 文 美 教 授 金 融 分 析 、 天 体 物 理 学 、 地 震 成 像 等 各 个 领 域 的 开 发 人 员 正 在 受 益于 CUDA的 开 发 工 具 。 “ 凭 借 CUDA， 我 们 很 容 易 地 就 可 利 用 GPU的 处 理 能 力 ， 减 少 时 间和 资 金 的 投 入 。 一 台 主 机 系 统 配 备 两 块 Tesla D870的 成 本 要 比 组 建16核 集 群 低 很 多 。 ” Technician “ Volera只 用 了 12个 GPU（ 图 形 处 理 器 ） 就 能 实 时 分 析 美 国 整 个 期权 市 场 ， 延 迟 时 间 不 超 过 10微 秒 。 而 达 到 这 样 的 速 度 则 通 常 会 至 少 需 要 60个 传 统 的 1U服 务 器 。 通 过 使 用 GPU， 我 们 的 客 户 可 以 用 更小 的 维 护 成 本 、 更 低 的 电 能 消 耗 以 及 更 小 的 占 地 空 间 实 现 更 好 的 效益 。 ” Hanweck Associates 2021-4-23 Ying Liu 63 Data Mining on GPUn University of Virginian University of Illinois at Urbana-Champaign n University of California at Davisn 中 国 科 学 院 研 究 生 院 2021-4-23 Ying Liu 64 High Performance Scientific Data Mining Projectsn Hillol Kargupta, University of Maryland, USAv Distributed Data Mining for Scalable Analysis of Data from Virtual Observatories, NASA, 2007-2010 Astronomers are unable to tap the riches of this collection of gigabyte, terabyte, and (eventually) petabyte catalogs without a computational backbone that includes support for queries and data mining across distributed virtual tables of de