НАУКА и ОБРАЗОВАНИЕ

Файл статьи: SE-BMSTU...o091.pdf (1604.49Кб)

УДК 681.322.01

1 МГТУ им. Н.Э. Баумана, Москва, Россия

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

Список литературы

1. Wlodarczyk J. Decomposition of Birational Toric Maps in Blow-Ups and Blow-Downs // Transactions of the American Mathematical Society. 1997. Vol . 349, no . 1. P . 373-411. Режим доступа:http://www.ams.org/journals/tran/1997-349-01/S0002-9947-97-01701-7/S0002-9947-97-01701-7.pdf (дата обращения 01.03.2016).
2. Welker V. , Ziegler G.M., Zivaljevic R. Т . Homotopy colimits – comparison lemmas for combinatorial applications // Journal für die reine und angewandte Mathematik. 1999. Vol. 1999, no. 509. P. 117-149. DOI:10.1515/crll.1999.509.117
3. Филин Б.П. Методы анализа структурной надёжности сетей связи. М.: Радио и связь, 1988. 208 с.
4. Ziegler G.M. Projected products of polygons // Electronic research announcements of the american mathematical society. 2004. V ol . 10. P. 122-134. Режим доступа: http://www.ams.org/journals/era/2004-10-14/S1079-6762-04-00137-4/S1079-6762-04-00137-4.pdf (дата обращения 01.03.2016).
5. Бухштабер В.М. Кольцо простых многогранников и дифференциальные уравнения // Труды Математического института имени В.А. Стеклова. 2008. Т. 263. С. 18-43.
6. Toporkov V.V. Models of distributed computations. Moscow: Fizmatlit, 2011. 320 p.
7. Харари Ф. Теория графов: пер с англ. 3-е изд. М.: КомКнига, 2006. 296 с.
8. Деза М.М., Лоран М. Геометрия разрезов и метрик: пер. с англ. / под ред. В.П. Гришухина. М.: МЦНМО, 2001. 736 с.
9. Деза М., Гришухин В.П., Штогрин М.И. Изометрические полиэдральные подграфы в гиперкубах и кубических решетках: пер. с англ. М.: МЦНМО, 2008. 192 с.
10. Звонкин А.К., Ландо С.К. Графы на поверхностях и их приложения. М.: МЦНМО, 2010. 480 с.
11. Андреев А.М., Можаров Г.П., Сюзев В.В. Многопроцессорные вычислительные системы: теоретический анализ, математические модели и применение. М.: Изд-во МГТУ им. Н.Э. Баумана, 2011. 334 с.
12. Циглер Г.М. Теория многогранников: пер. с англ. / под ред. Н.П. Долбилина. М.: МЦНМО, 2014. 568 с.
13. Деммель Дж. Вычислительная линейная алгебра. Теория и приложения: пер. с англ. М.: Мир, 2001. 430 с.
14. Бухштабер В.М., Панов Т.Е. Торические действия в топологии и комбинаторике. М.: МЦНМО, 2004. 272 с.
15. Тиморин В.А. О многогранниках, простых в ребрах // Функциональный анализ и его приложения. 2001. Т. 35, вып. 3. С. 36-47. DOI : 10.4213/faa257