Performance Evaluation of Global Sequence Alignment Algorithm on Multicore Architectures With Reference to Cache

摘要

Several experimental studies have been conducted over last decade on block data array in conjunction with tiling as a data transformation technique to improve cache performance. Based on the tile size and cache performance analysis, we propose a new data block size selection method - here we call it as a buffer size selection, which tightly fits into cache to get optimal solution for wave front computation. Due to significant latency of memory accesses cache performs an important role in memory intensive applications. In this paper, we analyze cache performance using our own technique of buffer size selection and a new method of tiling to improve locality and cache exploitation for sequence alignment algorithms using wave front technique which has a specific data access pattern. Since a direct application of standard loop parallelization technique is not helpful due to memory limitations. The consistency of performance improvement achieved is heavily dependent on the appropriate selection of tile size that maximizes L1 cache line utilization on different architectures. To validate our analysis, we conducted experiments on real life DNA sequences from gene databases. Experiments on platforms like dual core, quad core and 12-core workstation having different cache configuration shows that this new technique of buffer size and tiling achieves good speed-ups for variable datasets.