访存高效并行求解(l,d)-Motif发现问题  

Cache-Efficient Parallel Solving(l,d)-Motif Finding Problem

作　　者：张静[1] 钟诚[1] 李智[1,2] 

机构地区：[1]广西大学计算机与电子信息学院,广西南宁530004 [2]广西科技信息网络中心,广西南宁530012

出　　处：《微电子学与计算机》2014年第6期97-102,共6页Microelectronics & Computer

基　　金：国家自然科学基金项目(60963001);广西研究生教育创新计划项目(YCSZ2013006);广西教育厅-广西大学博士点建设基金(P11900119)

摘　　要：充分利用多核结构的共享三级缓存、私有二级和一级缓存,将采用Modeling算法求解(l,d)-Motif发现问题过程中产生的大量不同位置组合的数据,以多轮方式调度分配到各级缓存中,通过线程绑定以平衡核心负载,设计实现了一种访存高效的(l,d)-Motif发现线程级并行算法.实验结果表明,与已有的并行求解(l,d)-Motif发现算法相比,本文给出的算法更高效、具有较好的加速比和可扩展性,并且能够成功求解更长l的(l,d)-Motif发现问题.By utilizing fully the shared L3Cache,private L2Cache and L1Cache on the multi-core architecture,the produced large-scale data with the different combination of positions are distributed to the multi-level caches while the Modeling algorithm is used to solve(l,d)-Motif finding problem,and a cache-efficient thread-level parallel(l, d)-Motif finding algorithm is designed on multi-core computer by binding the threads to the cores to balance their computational loads.The experimental results show that,compared with the existing parallel algorithm to solve(l, d)-Motif finding problem,the presented algorithm is efficient and has good speedup and scalability,and it can solve successfully the(l,d)-Motif finding problem with longer l.

关 键 词：(l d)-Motif发现 Modeling算法 组合计算 多级缓存 线程级并行 

分 类 号：TP338.6[自动化与计算机技术—计算机系统结构]