Mapping Algorithm of Coarse Grained Reconfigurable Cell Array for Multi- branch Tree Data Flow Graph

To cope with the problem of multi-branch tree temporal partitioning and mapping, this paper presented a row column pruning mapping（RCPM） algorithm based on grained row parallel（RP） reconfigurable architectures. Firstly, the mapping performances of two-dimensional no hop point-to-point near neighbor interconnect and RP interconnect reconfigurable cell array（RCA） were analysized and compared by three kinds of one loop four orders multi- branch trees. As for RP, experimental results show that the maximum reduction cycles are 63 and the minimum reduction are 20; Secondly, RCPM had been designed and implemented. The nodes were mapped by row pruning at first, the successor of mapped nodes were mapped by column pruning. In the constraints of areas and interconnects, in order to adjust dynamically the lists of node scheduling order, the queuing function was constructed with the guideline of the levels and the indegrees of computing nodes. The experiment results show that the average execution total cycles of RCPM decreased by 15.7%（RCA_4×4） and18.4%（RCA_5×5） comparing with place and router（PR） mapping algorithm. Comparing with split-push kernel mapping（SPKM）algorithm, the average execution total cycles of RCPM decreased by 30.0%（RCA_4×4） and 29.8%（RCA_5×5）. Experimental evaluation confirms the efficiency of our approach in order to solving multi-branch trees row parallel RCA and mapping algorithm.