计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2015年
5期
1187-1197
,共11页
叶楠%郝子宇%郑方%谢向辉
葉楠%郝子宇%鄭方%謝嚮輝
협남%학자우%정방%사향휘
广度优先搜索算法%众核处理器%体系结构%分析模型%协同研究
廣度優先搜索算法%衆覈處理器%體繫結構%分析模型%協同研究
엄도우선수색산법%음핵처리기%체계결구%분석모형%협동연구
breadth-first search(BFS)%many-core processor%architecture%analytical model%cooperative research
以图计算为代表的数据密集型应用获得越来越广泛的关注,而传统的高性能计算机处理这类应用的效率较低.面向未来高性能计算机体系结构要有效支持数据密集型计算,深入研究以广度优先搜索(breadth-first search,BFS)算法为代表的图计算的典型特征,设计实现轻量级启发式切换BFS算法,该算法通过基本搜索方式的自动切换,避免冗余内存访问,提高搜索效率;针对BFS算法的离散随机数据访问特征以及众核处理器执行机制,建立面向BFS算法的众核处理器体系结构分析模型;全面、深入研究了BFS算法在典型众核处理器上的运行特征和性能变化趋势.测试结果表明:Cache命中率、内存带宽、流水线利用效率等相关参数均处于较低水平,无法完全满足BFS算法的需求,因此需要能够支持大量离散随机访问和简单执行机制的新型众核处理器体系结构.
以圖計算為代錶的數據密集型應用穫得越來越廣汎的關註,而傳統的高性能計算機處理這類應用的效率較低.麵嚮未來高性能計算機體繫結構要有效支持數據密集型計算,深入研究以廣度優先搜索(breadth-first search,BFS)算法為代錶的圖計算的典型特徵,設計實現輕量級啟髮式切換BFS算法,該算法通過基本搜索方式的自動切換,避免冗餘內存訪問,提高搜索效率;針對BFS算法的離散隨機數據訪問特徵以及衆覈處理器執行機製,建立麵嚮BFS算法的衆覈處理器體繫結構分析模型;全麵、深入研究瞭BFS算法在典型衆覈處理器上的運行特徵和性能變化趨勢.測試結果錶明:Cache命中率、內存帶寬、流水線利用效率等相關參數均處于較低水平,無法完全滿足BFS算法的需求,因此需要能夠支持大量離散隨機訪問和簡單執行機製的新型衆覈處理器體繫結構.
이도계산위대표적수거밀집형응용획득월래월엄범적관주,이전통적고성능계산궤처리저류응용적효솔교저.면향미래고성능계산궤체계결구요유효지지수거밀집형계산,심입연구이엄도우선수색(breadth-first search,BFS)산법위대표적도계산적전형특정,설계실현경량급계발식절환BFS산법,해산법통과기본수색방식적자동절환,피면용여내존방문,제고수색효솔;침대BFS산법적리산수궤수거방문특정이급음핵처리기집행궤제,건립면향BFS산법적음핵처리기체계결구분석모형;전면、심입연구료BFS산법재전형음핵처리기상적운행특정화성능변화추세.측시결과표명:Cache명중솔、내존대관、류수선이용효솔등상관삼수균처우교저수평,무법완전만족BFS산법적수구,인차수요능구지지대량리산수궤방문화간단집행궤제적신형음핵처리기체계결구.
