Temporal task partitioning algorithm for dynamically reconfigurable systems
Lingdi Ping · Journal of Zhejiang University(Engineering Science) · 2007
A temporal task partitioning algorithm for multi-objective optimization was proposed to improve the execution efficiency of dynamically reconfigurable systems.The task data flow graph(DFG) was partitioned into several sub-modules under hardware resource constraint.The delay cost of sub-modules and the communication cost between sub-modules were abstracted into one general cost by different weights to trade-off between delay optimization and communication optimization and guarantee the normal operation sequence.A ready list was also built to avoid deadlock between sub-modules.Experimental results showed that the proposed algorithm had better performance than other partitioning algorithms and the time complexity of this algorithm was O(|V|2+|V||E|)(|V| and |E| are the numbers of vertices and edges in DFG,respectively).