Load Balancing and Static Placement/Scheduling Heuristic on Distributed Heterogeneous Architecture


(*) Corresponding author


Authors' affiliations


DOI's assignment:
the author of the article can submit here a request for assignment of a DOI number to this resource!
Cost of the service: euros 10,00 (for a DOI)

Abstract


In this work, we are concerning by the improvement of optimized static heuristic in distributed and heterogeneous architecture. Thus, in order to take into account the load-balancing criterion, a need for a dynamic model is related to the use of heuristic based on list scheduling. The greedy list algorithms are well adapted, for they help the designer to rapidly obtain an efficient implementation and so to shorten development cycle of an application. This paper presents a dynamic model based on agent concept, coupled with an off line (static) heuristic. Our model has been simulated in programming parallel environment Xpvm. We show the integration of our model in the transformations flow, that implicates a heuristic to generating a real time distributed executive. This integration will be implemented in system level CAD software tool called SynDEx which, is a seamless flow based on graphs transformations.
Copyright © 2016 Praise Worthy Prize - All rights reserved.

Keywords


Multi Agents Systems; Distribution/Scheduling Heuristics; Static Load Balancing; AAA Methodology; Graph Models; Graph Transformations

Full Text:

PDF


References


A. Vicard, Y. Sorel, Formalization and static optimization for parallel implementation. In DAPSYS’98 Workshop on Distributed and Parallel Systems, Budapest, Hungary, September 1998.

D. Kebbal, E-G. Talbi, J-M. Geib, Ordonnancement multi-applications, JRPRC'2 Journées de Recherche sur le Placement et la Régulation de Charge, Lille, Mars 1998.

T. GrandPierre, Modeling of heterogeneous parallel architectures for automatic generating an optimized real time distributed executives, PHD Thesis, Paris XI Orsay University, Nov. 2000.

T. GrandPierre, C. Lavarenne and Y. Sorel, Optimized rapid prototype for real embedded heterogeneous multiprocessors, In proc. of IEEE CODES’99 7th Int. workshop on hardware/software Co-Design, Rome, May 1999.

Y. Sorel, Massively parallel computing systems with real time constraints, the algorithm architecture adequation methodology, In Proc. of the Massively Parallel Computing Systems, May 1994.

M. Raulet, F. Urban, J-F. Nezan, C. Moy, O. Déforges, Y.Sorel, Rapid prototypimg for heterogeneous multicomposant: An MPEG-4 Stream Over An UMTS, Communication Link, journal of Applied Signal Processing (JASP), 2005.

A. Girault, H. Kalla, and Y. Sorel, A scheduling heuristic for distributed real-time embedded systems tolerant to processor and communication media failures, International Journal of Production Research, 42(14): 2877–2898, July 2004.

A. Kalinov et A. Lastovetsky, Heterogeneous distribution of computations while solving linear algebra problems on networks of heterogeneous computers, In HPCN Europe 1999 (P. Sloot, M. Bubak, A. Hoekstra and B. Hertzberger, editors), LNCS 1593, Springer Verlag, pp. 191-200. p. 15, 1999.

O. Beaumont, V. Boudet, A. Petitet, F. Rastello and Y. Robert, A proposal for a heterogeneous cluster ScaLAPACK (dense linear solvers) . IEEE Trans. Computers 50, n.10, 1052-1070, p. 15, 2001.

A. Pinar et C. Aykanat, Fast optimal load balancing algorithms for 1D, Partitioning Journal of Parallel and Distributed Computing 64 , 974-996, p. 16, 2004.
A. S. Grimshaw et J. B.Weissman, Aframework for partitioning parallel computations in heterogeneous environments, Concurrency: practice and experience 7, 455-478. p. 16, 1995.

G. Cybenko, Dynamic load balancing for distributed memory multiprocessors, J. Parallel Distrib. Comput.7, n. 2, 279-301, p. 11, 1989.

J. Bahi, R. Couturier and F. Vernier, Synchronous Distributed Load Balancing on Dynamic Networks, Journal of Parallel and Distributed Computing 65, 1397-1405, p. 11, June 2005.

M. Hamdi et C. Lee. Dynamic load balancing of data parallel applications on a distributed network. In 9th International Conference on Supercomputing ICS'95, ACM Press, 170-179, p. 13, p.18,1995.

M. Cierniak, M. Zaki et W. Li, Customized dynamic load balancing for a network of workstations, The Computer Journal 40, n. 6 , 356-372, p. 12-14, 1997.

F. Berman, High-performance schedulers, In The Grid ( Blueprint for a New Computing Infrastructure), I. Foster and C. Kesselman, editors, Morgan-Kaufmann, 279-309. p. 12, 1999.

SynDEx is a system level CAD software based on the "algorithm- architecture adequation" (AAA) methodology, for rapid prototyping and optimizing the implementation of distributed real-time embedded applications onto "multicomponent" architectures, http://www-rocq.inria.fr/syndex/

J. Ferber, Multi agent systems towards a collective intelligence. (Inter Editions, 1995).

Florea Adina, Daniel Kayser and Stefan Pentiuc, Agents Intelligents, (Web course, Polytechnic University of Bucharest, 2002).

J. Ferber, O. Gutknecht, Aalaadin: A meta-model for the analysis and design of organizations in multi-agent systems. In. Y. Demazeau, editor, Proceedings of the Third International conference on Multi Agent Systems, ICMAS’98, p 128-135, Paris, France, IEEE Computer Society, July 1998.

Chaïbdraa B, Interaction between agents in routines, familiar and unfamiliar situations. International Journal of cooperative Information systems (5): 1-25. 1996.

Jean Pierre Müller, Organizational Modeling multi agent systems, S.E of ARCo. jui2000.

H. Willebeek-LeMair et P. Reeves, Strategies for Dynamic Load Balancing on Highly parallel Computers, IEEE Transactions on Parallel and Distributed Systems 4, n. 9, p. 13, September 1993.

D. Gorgé, M-P. Gleizes, P. Glize, Conception de systèmes adaptatifs a fonctionnalité émergente: la Théorie Amas, Revue d’Intelligence Artificielle, RSTI série RIA, Vol. 17, N.4, pp.591-626, 2004.


Refbacks

  • There are currently no refbacks.



Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2022 Praise Worthy Prize