Communication-sensitive loop scheduling for DSP applications

@article{citeulike:882807, abstract = {The performance of computation-intensive digital signal processing applications running on parallel systems is highly dependent on communication delays imposed by the parallel architecture. In order to obtain a more compact task/processor assignment, a scheduling algorithm considering the communication time between processors needs to be investigated. Such applications usually contain iterative or recursive segments that are modeled as communication sensitive data flow graphs (CS-DFGs), where nodes represent computational tasks and edges represent dependencies between them. Based on the theorems derived, this paper presents a novel efficient technique called cyclo-compaction scheduling, which is applied to a CS-DFG to obtain a better schedule. This new method takes into account the data transmission time, loop carried dependencies, and the target architecture. It implicitly uses the retiming technique (loop pipelining) and a task remapping procedure to allocate processors and to iteratively improve the parallelism while handling the underlying communication and resource constraints. Experimental results on different architectures demonstrate that this algorithm yields significant improvement over existing methods. For some applications, the final schedule length is less than one half of its initial length}, author = {Tongsima, S. and Sha, E. H. M. and Passos, N. L. }, citeulike-article-id = {882807}, journal = {Signal Processing, IEEE Transactions on [see also Acoustics, Speech, and Signal Processing, IEEE Transactions on]}, keywords = {scheduling, sdf}, number = {5}, pages = {1309--1322}, posted-at = {2006-10-03 20:02:45}, priority = {2}, title = {Communication-sensitive loop scheduling for DSP applications}, url = {http://ieeexplore.ieee.org/xpls/abs\_all.jsp?arnumber=575702}, volume = {45}, year = {1997} }

TY - JOUR ID - citeulike:882807 L3 - citeulike-article-id:882807 N2 - The performance of computation-intensive digital signal processing applications running on parallel systems is highly dependent on communication delays imposed by the parallel architecture. In order to obtain a more compact task/processor assignment, a scheduling algorithm considering the communication time between processors needs to be investigated. Such applications usually contain iterative or recursive segments that are modeled as communication sensitive data flow graphs (CS-DFGs), where nodes represent computational tasks and edges represent dependencies between them. Based on the theorems derived, this paper presents a novel efficient technique called cyclo-compaction scheduling, which is applied to a CS-DFG to obtain a better schedule. This new method takes into account the data transmission time, loop carried dependencies, and the target architecture. It implicitly uses the retiming technique (loop pipelining) and a task remapping procedure to allocate processors and to iteratively improve the parallelism while handling the underlying communication and resource constraints. Experimental results on different architectures demonstrate that this algorithm yields significant improvement over existing methods. For some applications, the final schedule length is less than one half of its initial length IS - 5 JF - Signal Processing, IEEE Transactions on [see also Acoustics, Speech, and Signal Processing, IEEE Transactions on] EP - 1322 TI - Communication-sensitive loop scheduling for DSP applications VL - 45 SP - 1309 KW - scheduling KW - sdf AU - Tongsima, S AU - Sha, EHM AU - Passos, NL PY - 1997/// UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=575702 ER -