Efficient fault-tolerant reconfiguration techniques are essential for improving the reliability of high performance architecture such as mesh-connected processor arrays. Meanwhile, reconfiguration must be achieved as fast as possible to meet the real-time constraints. Existing techniques of generating maximum logic array on parallel reconfiguration are only for the single logical column, and no maximum logic array algorithm is reported for reconfiguring multi-logical columns in parallel on processor arrays. According to the potential parallelism of mesh-connected processor arrays, based on the divide and conquer strategy, this paper proposes a parallel algorithm to reconstruct the logical array. The proposed algorithm divides processors array into subarrays, then reconfigures each subarray in parallel. After that, it merges the logical subarrays in parallel. The proposed algorithm can effectively accelerate the running speed by reducing the data redundancy in communication and calculation. Moreover, it is proved that the proposed algorithm can generate the maximum logic array. Experimental results show that the proposed algorithm is faster by nearly 39.6% than the existing parallel algorithm on a 64×64 processor array and has good scalability.