Abstract
Runtime data alignment has been paid attention recently since it can allocate data segment to processors dynamically according to applications’ requirement. One of the key optimizations of this problem is to schedule simultaneous communications to avoid contention and to minimize the overall communication costs. The NP-completeness of the problem has instigated researchers to propose different heuristic algorithms. In this paper, we present an algorithm independent technique for optimizing scheduling stability of different scheduling heuristics. The proposed technique introduces a new scheduling policy, Local Message Reduction (LMR), to obtain better communication schedule adaptive to different environments. o evaluate the performance of the proposed technique, we have implemented LMR along with two existing algorithms, the two-phase degree reduction and the list scheduling algorithms. The experimental results show that the proposed technique is effective in terms of scheduling stability, communication efficiency and easy to implement.
The work of this paper is supported by National Science Council, Taiwan, under grant number NSC94-2213-E-216-002.
Chapter PDF
Similar content being viewed by others
References
Bandera, G., Zapata, E.L.: Sparse Matrix Block-Cyclic Redistribution. In: Proceeding of IEEE Int’l. Parallel Processing Symposium (IPPS 1999), San Juan, Puerto Rico (April 1999)
Guo, M., Nakata, I.: A Framework for Efficient Array Redistribution on Distributed Memory Multicomputers. The Journal of Supercomputing 20(3), 243–265 (2001)
Guo, M., Nakata, I., Yamashita, Y.: Contention-Free Communication Scheduling for Array Redistribution. Parallel Computing 26(8), 1325–1343 (2000)
Guo, M., Pan, Y., Liu, Z.: Symbolic Communication Set Generation for Irregular Parallel Applications. The Journal of Supercomputing 25, 199–214 (2003)
Hsu, C.-H., Yang, D.-L., Chung, Y.-C., Dow, C.-R.: A Generalized Processor Mapping Technique for Array Redistribution. IEEE Transactions on Parallel and Distributed Systems 12(7), 743–757 (2001)
Kaushik, S.D., Huang, C.H., Ramanujam, J., Sadayappan, P.: Multiphase data redistribution: Modeling and evaluation. In: Proceeding of IPPS 1995, pp. 441–445 (1995)
Chen, S.-C., Hsu, C.-H., Lan, C.-Y., Yang, C.-T., Li, K.-C.: Efficient Communication Scheduling Methods for Irregular Array Redistribution in Parallelizing Compilers. In: Malyshkin, V.E. (ed.) PaCT 2005. LNCS, vol. 3606, pp. 216–225. Springer, Heidelberg (2005)
Lee, S., Yook, H., Koo, M., Park, M.: Processor reordering algorithms toward efficient GEN_BLOCK redistribution. In: Proceedings of the ACM symposium on Applied computing (2001)
Prylli, L., Touranchean, B.: Fast runtime block cyclic data redistribution on multiprocessors. JPDC 45, 63–72 (1997)
Park, N., Prasanna, V.K., Raghavendra, C.S.: Efficient Algorithms for Block-Cyclic Data redistribution Between Processor Sets. IEEE Trans. on PDS 10(12), 1217–1240 (1999)
Wakatani, A., Wolfe, M.: Optimization of Data redistribution for Distributed Memory Multicomputers. short communication, Parallel Computing 21(9), 1485–1490 (1995)
Wang, H., Guo, M., Wei, D.: Divide-and-conquer Algorithm for Irregular Redistributions in Parallelizing Compilers. The Journal of Supercomputing 29(2) (2004)
Yook, H.-G., Park, M.-S.: Scheduling GEN_BLOCK Array Redistribution. In: Proceedings of the IASTED International Conference Parallel and Distributed Computing and Systems (November 1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hsu, CH., Lan, CY., Chen, SC. (2006). Optimizing Scheduling Stability for Runtime Data Alignment. In: Zhou, X., et al. Emerging Directions in Embedded and Ubiquitous Computing. EUC 2006. Lecture Notes in Computer Science, vol 4097. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11807964_83
Download citation
DOI: https://doi.org/10.1007/11807964_83
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-36850-2
Online ISBN: 978-3-540-36851-9
eBook Packages: Computer ScienceComputer Science (R0)