%0 Journal Article %1 Seredyski:2001:FGCS %A Seredyski, F. %A Koronacki, J. %A Janikow, C. Z. %D 2001 %J Future Generation Computer Systems %K Decomposition Multi-agent Multiprocessor algorithms, criterion genetic of optimization programming, scheduling, systems, %N 4 %P 387--396 %R doi:10.1016/S0167-739X(99)00119-3 %T Distributed multiprocessor scheduling with decomposed optimization criterion %U http://www.sciencedirect.com/science/article/B6V06-4234BR7-6/1/9ac251ca310222336e096ca3ecf27e22 %V 17 %X n this paper, a new approach to scheduling of parallel and distributed algorithms for multiprocessor systems is proposed. Its main innovation lies in evolving a decomposition of the global optimization criteria. For this purpose, agents "local decision making units" are associated with individual tasks of the program graph. Thus, the program can be interpreted as a multi-agent system. A game-theoretic model of interaction between agents is applied. Agents take part in an iterated game to find directions of migration in the system graph, with the objective of minimizing the total execution time of the program in a given multiprocessor topology. Competitive coevolutionary genetic algorithm, termed loosely coupled genetic algorithm, is used to implement the multi-agent system. The scheduling algorithm works with a global optimization function, what limits its efficiency. To make the algorithm truly distributed, decomposition of the global optimization criterion into local criteria is proposed. This decomposition is evolved with genetic programming. Results of successive experimental study of the proposed algorithm are presented.

@article{Seredyski:2001:FGCS, abstract = {n this paper, a new approach to scheduling of parallel and distributed algorithms for multiprocessor systems is proposed. Its main innovation lies in evolving a decomposition of the global optimization criteria. For this purpose, agents {"}local decision making units{"} are associated with individual tasks of the program graph. Thus, the program can be interpreted as a multi-agent system. A game-theoretic model of interaction between agents is applied. Agents take part in an iterated game to find directions of migration in the system graph, with the objective of minimizing the total execution time of the program in a given multiprocessor topology. Competitive coevolutionary genetic algorithm, termed loosely coupled genetic algorithm, is used to implement the multi-agent system. The scheduling algorithm works with a global optimization function, what limits its efficiency. To make the algorithm truly distributed, decomposition of the global optimization criterion into local criteria is proposed. This decomposition is evolved with genetic programming. Results of successive experimental study of the proposed algorithm are presented.}, added-at = {2008-06-19T17:35:00.000+0200}, author = {Seredyski, F. and Koronacki, J. and Janikow, C. Z.}, biburl = {https://www.bibsonomy.org/bibtex/21149e300dab54368fdebe027b6c97b47/brazovayeye}, doi = {doi:10.1016/S0167-739X(99)00119-3}, interhash = {3ffa1db74e61d0cd3147beb91051d57a}, intrahash = {1149e300dab54368fdebe027b6c97b47}, journal = {Future Generation Computer Systems}, keywords = {Decomposition Multi-agent Multiprocessor algorithms, criterion genetic of optimization programming, scheduling, systems,}, number = 4, pages = {387--396}, timestamp = {2008-06-19T17:51:26.000+0200}, title = {Distributed multiprocessor scheduling with decomposed optimization criterion}, url = {http://www.sciencedirect.com/science/article/B6V06-4234BR7-6/1/9ac251ca310222336e096ca3ecf27e22}, volume = 17, year = 2001 }