Abstract
We presented a parallel simulation environment for polymers, DNA and protein molecular chain simulations. The system is intended to help automatically parallelise computer simulations of complex polymers, DNA and protein molecules. In this paper we look at a load balancing algorithm for a class of computational problems where the topology of the problem is important, as well as just the dynamic problem structure. We study the algorithm and find the crossover points when it is beneficial to apply the algorithm. Both a theoretical model and experimental data from an implementation on a Cray T3D are used.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. Baumgartner. Statics and dynamics of the freely jointed polymer chain with lennard-jones interaction. Journal of Chemical Physics, 72(2):871–879, Jan. 1980.
E.S. Biagioni. Scan Directed Load Balancing. PhD thesis, University of North Carolina at Chapel Hill, 1991.
R. H. Bisseling and W. F. McColl. Scientific computing on bulk synchronous parallel architectures. Technical Report 836, Dept. of Mathematics, University of Utrecht, December 1993. Short version in Proc. 13th IFIP World Computer Congress. Volume I (1994), B. Pehrson and I. Simon, Eds., Elsevier, pp. 509–514.
W.J. Camp, S.J. Plimpton, B.A. Hendrickson, and R.W. Leland. Massively Parallel Methods for Engineering and Science Problems. Communication of the ACM, 37(4):31–41, April 1994.
C. Che Chen, J.P. Singh, W.B. Poland, and R.B. Altman. Parallel Protein Structure Determination from Uncertain Data. In Proc. of Supercomputing'94, 1994.
E.A. Colbourn. Computer Simulation of Polymers. Longman, 1994.
Message Passing Interface Forum. MPI: A Message-Passing Interface Standard. University of Tennessee, Knoxville, Tennessee, May 1994. URL: http://www.mcs.anl.gov/Projects/mpi/standard.html.
R.F. Freund and H.J. Siegel. Heterogeneous Processing. IEEE Computer, (6):13–17, June 1993.
M. Furuichi, K. Taki, and N. Ichiyoshi. A Multi-level Load Balancing Scheme for OR-Parallel Exhaustive Search Programs on the Multi-PSI. In Proc. of the 2nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 50–59, 1990.
David F. Hegarty, M. Tahar Kechadi, and K.A. Dawson. Dynamic Domain Decomposition and Load Balancing for Parallel Simulations of Long-Chained Molecules. In Proc. of PARA'95, volume 1041 of Lecture Notes in Computer Science, pages 303–312, Copenhagen, Denmark, August 1995. Springer-Verlag.
G. Karypis and V. Kumar. Unstructured Tree Search on SIMD Parallel Computers. Technical Report 92-21, Dept. of Computer Science, University of Minnesota Minneapolis, MN 55455, April 1992.
T. Kechadi, P. Kiernan, D. Hegarty, and K. Dawson. Parallel Simulation Environment for Polymers, DNA and Protein Molecular Chains. In Proc. of the International Conference and Exhibition on High-Performance Computing and Networking (HPCN'96), Brussels, Belgium, April 1996.
D. E. Keyes and W. D. Gropp. A Comparison of Domain Decomposition Techniques for Elliptic Partial Differential Equations and their Parallel Implementation. SIAM Journal of Scientific and Statistical Computing, 8:166–202, March 1987.
M.H. Willebeek-Le Mair and A.P. Reeves. Strategies for Dynamic Load Balancing on Highly Parallel Computers. IEEE Transactions on Parallel and Distributed Systems, 4(9), September 1993.
W. F. McColl. Bsp programming. In G. E. Blelloch, K.M. Chandy, and S. Jagannathan, editors, Specification of Parallel Algorithms. Proc. DIMACS Workshop, Princeton, May 9–11, 1994, volume 18 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 21–35. American Mathematical Society, 1994.
S. Patil and P. Banerjee. A Parallel Branch and Bound Algorithm for Test Generation. IEEE Transactions on Computer Aided Design, 9(9), March 1990.
W. Shu and L.V. Kale. A Dynamic Scheduling Strategy for the Chare-Kernel System. In Proc. of Supercomputing'89, pages 389–398, 1989.
L. G. Valiant. A bridging model for parallel computation. Communications of the ACM, 33(8):103–111, 1990.
B.W. Wah and Y.W. Eva Ma. MANIP — A Multicomputer Architecture for Solving Combinatorial Extremum-Search Problems. IEEE Transactions on Computers, C-33(5), May 1984.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hegarty, D.F., Kechadi, M.T., Dawson, K.A. (1996). On the crossover points for dynamic load balancing of long-chained molecules. In: Waśniewski, J., Dongarra, J., Madsen, K., Olesen, D. (eds) Applied Parallel Computing Industrial Computation and Optimization. PARA 1996. Lecture Notes in Computer Science, vol 1184. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-62095-8_41
Download citation
DOI: https://doi.org/10.1007/3-540-62095-8_41
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62095-2
Online ISBN: 978-3-540-49643-4
eBook Packages: Springer Book Archive