Memory Partitioning for Parallel Multipattern Data Access in Multiple Data Arrays

作者：Yin, Shouyi^*; Xie, Zhicong; Meng, Chenyue; Ouyang, Peng; Liu, Leibo; Wei, Shaojun

来源：IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(2): 431-444.

DOI：10.1109/TCAD.2017.2693274

• Bank merging
• memory partitioning
• parallel data access

Memory bandwidth bottlenecks severely restrict parallel access of data elements from data arrays. To realize high throughput out of a relatively low bandwidth, memory partitioning algorithms have been proposed to separate data arrays into multiple memory banks, from which multiple data can be accessed in parallel. However, previous partitioning schemes only considered the case of single-pattern and single-array. In the case of multipattern and multiarray, the previous partitioning schemes will use too much time to find a partition solution and cause excessively high storage overhead. In this paper, we propose an efficient two-step memory partitioning strategy for multipattern data access in multiple arrays. First, a fast, low complexity and low overhead difference-based data splitting algorithm provides a multibank solution for multiple patterns access. Then an area-efficient bank merging algorithm merges those partitioned banks from different arrays which satisfy conflict-free requirement in order to reduce the area overhead caused by partitioning. Experimental results show that our data splitting algorithm saves up to 83.0% in searching time and reduces 39.4% storage overhead compared to the state-of-the-art approaches. With the further optimization of area-efficient bank merging, the memory area overhead are saved up to 18.9% and the total partitioning time are saved up to 45.6%.

• 出版日期2018-2
• 单位清华大学