Abstract
Solving time constraint problems in wide area distributed computing environment is a challenge. We address this challenge by providing programmers a method to express their problems based on a parallelization scheme. The scheme consists of a decomposition tree defining possible decompositions of a problem into sub-problems and the decomposition dependency graph showing the relative order of execution of sub-problems. We have developed algorithms to address the following issues of the parallelization scheme: the execution of the scheme, the dependency of sub-problems, the min-max problem related to the time constraints of decomposed components. A genetic algorithm has been developed for the max-min problem. Experiment results show the good scalability of the algorithms up to thousands of nodes in each decomposition.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
I. Foster, C. Kesselman, S. Tuecke. The Anatomy of the Grid: Enabling Scalable Virtual Organizations. International J. Supercomputer Applications, 15(3), 2001.
David Barkai. Peer-to-Peer Computing: Technologies for Sharing and collaborating on the Net. Intel Press, 2002.
Object Management Group. Real-Time CORBA specification. http://www.omg.org.
T. D. Braun, H. J. Siegel and A. A. Maciejewski. Static Mapping Heuristics for Tasks with Dependencies, Priorities, Deadlines and Multiple Versions in Heterogeneous Environments. 16th International Parallel and distributed Processing Symposium, 2002.
M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen and R. F. Freund. Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems. Journal of Parallel and distributed Computing Vol. 59(2), p. 107–131, Nov. 1999.
T. A. Nguyen, P. Kuonen. A Model of Dynamic Parallel Objects for Metacomputing. The 2002 International Conference on Parallel and Distributed Processing Techniques and Applications, 2002, Las Vegas, Nevada, USA.
P. Jęedrzejowicz, I. Wierzbowska. Scheduling multiple variant programs under hard real-time constraints. European Journal of Operational Research 127 (2000) 458–465.
J. Gunnels, C. Lin, G. Morrow and R. van de Geijn. Analysis of a Class of Parallel Matrix Multiplication Algorithms. Proc. of the First Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing, p. 110–116, 1998.
J.-P. Cagnard. The Parallel Cellular Programming Model. The 8th euromicro workshop on Parallel and Distributed Processing, 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nguyen, TA., Kuonen, P. (2003). Parallelization Scheme for an Approximate Solution to Time Constraint Problems. In: Sloot, P.M.A., Abramson, D., Bogdanov, A.V., Dongarra, J.J., Zomaya, A.Y., Gorbachev, Y.E. (eds) Computational Science — ICCS 2003. ICCS 2003. Lecture Notes in Computer Science, vol 2657. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44860-8_18
Download citation
DOI: https://doi.org/10.1007/3-540-44860-8_18
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40194-0
Online ISBN: 978-3-540-44860-0
eBook Packages: Springer Book Archive