Вложение структур параллельных программ в структуры живучих распределенных вычислительных систем

摘要

Предложен метод вложения структур параллельных программ в структуры живучих распределенных вычислительных систем (ВС). Разработаны эффективные алгоритмы для реализации этапов метода: 1) эвристический алгоритм отображения вершин графа параллельной программы в граф распределенной ВС, существенно сокращающий время вложения по сравнению с известным алгоритмом Бохари; 2) децентрализованный алгоритм отображения ребер графа программы, не совпадающих с ребрами графа ВС, в кратчайшие пути на графе ВС. Исследовано вложение одномерных (линейка, кольцо) и двумерных (решетка, тор) структур параллельных программ в регулярные структуры (тор, двумерный циркулянт, гиперкуб) живучих вычислительных систем с неисправными компонентами (машинами и межмашинными соединениями). Показано, что одномерные структуры параллельных программ вкладываются в структуры распределенных ВС лучше, чем двумерные, и при возникновении дефектов в структуре ВС (отказов компонентов ВС) качество вложения одномерных структур ухудшается меньше, чем качество вложения двумерных структур.