Exploitation of Locality for Energy Efficiency for Breadth First Search in Fine-Grain Execution Models  

作　　者：Chen Chen Souad Koliai Guang Gao 

机构地区：[1]Department of Electrical and Computer Engineering,University of Delaware

出　　处：《Tsinghua Science and Technology》2013年第6期636-646,共11页清华大学学报（自然科学版（英文版）

基　　金：National Science Foundation of USA(Nos.CCF-0833122,CCF-0925863,CCF-0937907,CNS-0720531,and OCI-0904534);supported by the Department of Energy(National Nuclear Security Administration)under the Award Number DE-SC0008717.Moreover;partly supported by European FP7 project TERAFLUX,id.249013

摘　　要：In the upcoming exa-scale era, the exploitation of data locality in parallel programs is very important because it benefits both program performance and energy efficiency. However, this is a hard topic for graph algorithms such as the Breadth First Search （BFS） due to the irregular data access patterns. This study analyzes the exploitation of data locality in the BFS and its impact on the energy efficiency with the Codelet fine-grain dataflow-inspired execution model. The Codelet Model more efficiently exploits data locality than the OpenMP-like execution models which traditionally focus on coarse-grain parallelism inside loops. A BFS algorithm is then given to exploit the locality between two loop iterations that belong to two different loops （inter-loop locality）. This kind of locality can be exploited by the Codelet Model but not by traditional coarse-grain execution models like OpenMR Tests were performed on fsim which is a simulation platform developed by Intel for the Ubiquitous High Performance Computing （UHPC） project to design future exa-scale architectures. The results show that this BFS algorithm saves up to 7% of the dynamic energy for memory accesses compared to a BFS implementation based on OpenMP loop scheduling.In the upcoming exa-scale era, the exploitation of data locality in parallel programs is very important because it benefits both program performance and energy efficiency. However, this is a hard topic for graph algorithms such as the Breadth First Search （BFS） due to the irregular data access patterns. This study analyzes the exploitation of data locality in the BFS and its impact on the energy efficiency with the Codelet fine-grain dataflow-inspired execution model. The Codelet Model more efficiently exploits data locality than the OpenMP-like execution models which traditionally focus on coarse-grain parallelism inside loops. A BFS algorithm is then given to exploit the locality between two loop iterations that belong to two different loops （inter-loop locality）. This kind of locality can be exploited by the Codelet Model but not by traditional coarse-grain execution models like OpenMR Tests were performed on fsim which is a simulation platform developed by Intel for the Ubiquitous High Performance Computing （UHPC） project to design future exa-scale architectures. The results show that this BFS algorithm saves up to 7% of the dynamic energy for memory accesses compared to a BFS implementation based on OpenMP loop scheduling.

关 键 词：breadth first search LOCALITY fine grain execution model 

分 类 号：TP391.3[自动化与计算机技术—计算机应用技术]