Performance-Oriented Partitioning for Task Scheduling of Parallel Reconfigurable Architectures

Dynamic reconfiguration is important for reconfigurable platforms. Parallel reconfigurable computing (PRC) architecture consists of multiple dynamic reconfigurable computing (DRC) units. Thus, for a circuit to be implemented on a parallel reconfiguration system, it needs to be partitioned such that each sub-circuit can be executed to the DRC units in a PRC system. For high performance, this paper proposes a greedy algorithm that maximizes data parallelism for task scheduling of parallel reconfigurable architectures with unlimited resources. The proposed algorithm generates an optimal solution in polynomial time O(n³), where n is the total number of the tasks. After obtaining a depth optimal solution, we reduce the resources without decreasing performance by the duplication packing operations whose time complexity is O(n³). To demonstrate the performance of the proposed algorithm, we not only compare the existing methods with standard benchmarks but also implement on physical systems, like DSP, FIR, and JPEG. The experimental results show that the proposed algorithms satisfy the requirements of the performance-oriented systems with limited resources. Hence, we have sufficient reason to believe that the runtime must be reasonable for general applications.