A problem of mapping graphs of parallel programs onto graphs of distributed computer systems by recurrent neural networks is formulated. The network parameters providing the absence of incorrect solutions are experimentally determined. By introduction of a penalty coefficient into the Lyapunov function for the program graph edges non-coincided with the edges of the computer system, the optimal solutions are computed for mapping the "line" program graph onto a two-dimensional torus. To increase the optimal solution probability a method of the mapping decomposition is proposed. The method essence is a reduction of the solution matrix to a block-diagonal shape. For exclusion of incorrect solutions in mapping the line onto three-dimensional torus, a recurrent Wang network is used because it is converged more rapidly than the Hopfield network.
Download file
Counter downloads: 72
- Title ON MAPPING GRAPHS OF PARALLEL PROGRAMS ONTO GRAPHS OF DISTRIBUTED COMPUTER SYSTEMS BY RECURRENT NEURAL NETWORKS
- Headline ON MAPPING GRAPHS OF PARALLEL PROGRAMS ONTO GRAPHS OF DISTRIBUTED COMPUTER SYSTEMS BY RECURRENT NEURAL NETWORKS
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 4(10)
- Date:
- DOI
Keywords
recurrent Wang network, Hopfield network, distributed computer systems, graphs of parallel programs, mapping, рекуррентная сеть Вана, сеть Хопфилда, нейрон, распределенные вычислительные системы, графы параллельных программ, вложениеAuthors
References
Dijkstra E. W. Self-stabilizing systems in spite of distributed control // Commun. ACM. 1974. V. 17. No. 11. P. 643-644.
Wang J. Analysis and Design of a Recurrent Neural Network for Linear Programming // IEEE Trans. On Circuits and Systems-I: Fundamental Theory and Applications. 1993. V. 40. No. 9. P. 613-618.
Тарков М. С. Построение гамильтоновых циклов рекуррентной нейронной сетью в тороидальных графах с дефектами ребер // Труды XII Всерос. науч.-технич. конф. «НЕЙР0ИНФ0РМАТИКА-2010». Ч.2. М., 2010. С. 26-34.
Feng G., Douligeris C. The Convergence and Parameter Relationship for Discrete-Time Continuous-State Hopfield Networks // Proc. of Intern. Joint Conference on Neural Networks. 2001. P. 376-381.
Tarkov M. S., Lapukhov S. A. Mapping a parallel program structure onto distributed computer system structure by the Hopfield neural network with fuzzy scheduling parameters // Bulletin of the Novosibirsk Computing Center, Comp. Science. 2003. No. 19. P. 83-88.
Меламед И. И. Нейронные сети и комбинаторная оптимизация // Автоматика и телемеханика. 1994. №11. С. 3-40.
Kate A. S. Neural Networks for Combinatorial Optimization: A Review of More Than a Decade of Research // INFORMS J. Computing. 1999. V. 11. No. 1. P. 15-34.
Абрамов С. М., Заднепровский В. Ф., Шмелев А. Б., Московский А. А. СуперЭВМ ряда 4 семейства «СКИФ»: Штурм вершины суперкомпьютерных технологий // Вестник Нижегородского университета им. Н.И. Лобачевского. 2009. №5. С. 200-210.
Yu H., Chung I.-H., Moreira J. Topology Mapping for Blue Gene/L Supercomputer // Proc. of the ACM/IEEE SC2006 Conf. on High Performance Networking and Computing, November 11-17, 2006, Tampa, FL, USA. ACM Press, 2006. P. 52-64.
Cray T3E: <http://www.cray.com/products/systems/crayt3e/1200e.html>
Корнеев В. В. Архитектура вычислительных систем с программируемой структурой. Новосибирск: Наука, 1985. 166 с.
Тарков М. С. Вложение структур параллельных программ в структуры живучих распределенных вычислительных систем // Автометрия. 2003. Т. 39. №3. С. 84-96.
ON MAPPING GRAPHS OF PARALLEL PROGRAMS ONTO GRAPHS OF DISTRIBUTED COMPUTER SYSTEMS BY RECURRENT NEURAL NETWORKS | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2010. № 4(10).
Download full-text version
Download fileCounter downloads: 182