美文网首页
Shared memory parallelization of

Shared memory parallelization of

作者: 世间五彩我执纯白 | 来源:发表于2016-01-27 15:43 被阅读0次

    1. Abstract

    • focus on 数据挖掘任务的并行共享内存
    • 贡献1:并行策略(full replication, buffering, full locking, fixed locking, group locking, optimized full locking)
    • 贡献2:编程接口(reduction object)
    • 贡献3:性能测试(apriori association mining, k-means clustering, k-nearest classifier)

    2. 并行策略

    2.1. Full replication

    • 每个consumer线程保存一个reduction object的副本
    • 独立地更新自己的副本
    • 不需要锁
    • 本地所有数据处理完后,merge所有副本的增量

    2.2. Buffering

    • full replication的空间开销大
    • 为每个consumer线程创建一个buffer,consumer线程将对reduction object的更新存储在buffer中
    • 需要存reduction object中element的指针,也要存reduction function的参数
    • 需要single lock锁住所有的reduction object

    2.3. Full locking

    • reduction object中的每个element一个lock
    • 问题是很多lock带来的开销大,因此提出了3种优化方法

    2.4. Fixed locking

    • 固定数量的锁,数量是l,element i 的锁是i mod l
    • 因为多个element associate with 同一个锁,并行度被限制

    2.5. Group locking

    • 为每个group分配一个锁来减少锁的数量
    • 代价是并行度受限

    2.6. Optimized full lock

    • full lock的主要开销是在获取锁时会cache miss
    • 创建结构来同时存储element和它的锁
    • 这样使得element和clock在一个cache block的概率增加

    3. Related work

    3.1. 分布式association mining,分布式关联规则

    • Parallel mining of association rules
    • Scalable parallel datamining for association rules
    • Parallel and distributed association mining: a survey

    3.2 分布式K-means clustering

    • A data-clustering algorithm on distributed memory multiprocessors

    3.3. 分布式Decision tree classifier,分布式决策树

    • Clouds: Classification for large or out-of-core datasets
    • Efficient parallel classification using dimensional aggregates
    • Scalparc: A new scalable and efficient parallel classification algorithm for mining large datasets
    • Sprint: A scalable parallel classifier for data mining
    • Parallel formulations of decision-tree classification algorithms

    3.4. 数据挖掘算法的分布式框架

    • Mining of association rules in very large databases: A structured parallel approach. 但是focus on分布式内存的并行化,I/O需要用户自己处理
    • Strategies for parallel data mining. 挖掘不同分布式算法的并行策略的相似性,本文的不同之处在于提供了中间件来利用这种相似性,同时使得并行应用的开发变得简单
    • OpenMP. 共享内存编程的通用标准,但是只支持scalar reduction 变量和少量的简单reduction操作,因此不适用数据挖掘算法。而且目前的OpenMP不支持对disk-resident dataset的高效acceess。

    4. Summary

    • focus on 数据挖掘算法的shared memory parallelization
    • 挖掘不同数据挖掘任务的并行算法上的相似性,开发了一个编程interface。用户只需要稍微改写一个sequential code,使用reduction object接口来对reduction object中的element进行更新。
    • 6种并行技术
    • 实验:关联规则,k-means聚类,k近邻。full replication的结果最好。

    相关文章

      网友评论

          本文标题:Shared memory parallelization of

          本文链接:https://www.haomeiwen.com/subject/awbdkttx.html