О ВЛОЖЕНИИ ГРАФОВ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ В ГРАФЫ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ РЕКУРРЕНТНЫМИ НЕЙРОННЫМИ СЕТЯМИ | Прикладная дискретная математика. 2010. № 4(10).

Сформулирована задача вложения графов параллельных программ в графы распределённых вычислительных систем рекуррентными нейронными сетями. Экспериментально получены значения параметров, обеспечивающие отсутствие некорректных решений. Благодаря введению в функцию Ляпунова коэффициента штрафа для рёбер графа программы, не совпадающих с рёбрами графа ВС, при вложении «линейки» в двумерный тор получены оптимальные решения. Для увеличения вероятности оптимальных вложений предложен метод расщепления вложения, суть которого заключается в приведении матрицы решения к блочно-диа- гональному виду. Для исключения некорректных решений при вложении линейки в трехмерный тор использована рекуррентная сеть Вана, обладающая более быстрой сходимостью, чем сеть Хопфилда.
  • Title О ВЛОЖЕНИИ ГРАФОВ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ В ГРАФЫ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ РЕКУРРЕНТНЫМИ НЕЙРОННЫМИ СЕТЯМИ
  • Headline О ВЛОЖЕНИИ ГРАФОВ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ В ГРАФЫ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ РЕКУРРЕНТНЫМИ НЕЙРОННЫМИ СЕТЯМИ
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 4(10)
  • Date:
  • DOI
Ключевые слова
recurrent Wang network, Hopfield network, distributed computer systems, graphs of parallel programs, mapping, рекуррентная сеть Вана, сеть Хопфилда, нейрон, распределенные вычислительные системы, графы параллельных программ, вложение
Авторы
Ссылки
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.
 О ВЛОЖЕНИИ ГРАФОВ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ В ГРАФЫ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ РЕКУРРЕНТНЫМИ НЕЙРОННЫМИ СЕТЯМИ | Прикладная дискретная математика. 2010. № 4(10).
О ВЛОЖЕНИИ ГРАФОВ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ В ГРАФЫ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ РЕКУРРЕНТНЫМИ НЕЙРОННЫМИ СЕТЯМИ | Прикладная дискретная математика. 2010. № 4(10).