АНАЛИЗ МЕТОДОВ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛЕНИЙ ПРИ РЕШЕНИИ ЗАДАЧ БЕЗОПАСНОСТИ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

Аннотация

В настоящее время все большее значение как в реализации криптосистем [1], так и в исследованиях вычислительной стойкости криптоалгоритмов [2] приобретают распределенные вычисления. Одним из стратегических направлений развития современных компьютерных технологий является широкое использование кластеров (clusters). Под кластером обычно понимается (см., например, [3]) множество отдельных компьютеров, объединенных в сеть при помощи специальных аппаратно- программных средств. Важным преимуществом параллельных программ, разработанных с использованием кластера, является их мобильность. Так, при решении задач большой временной сложности программы, разработанные для кластера с использованием MPI-технологии, могут быть перенесены практически без доработки на более производительный суперкомпьютер, например на Многопроцессорную вычислительную систему Межведомственного суперкомпьютерного центра РАН [3]. Вместе с этим следует отметить, что организация взаимодействия вычислительных узлов кластера при помощи передачи сообщений может приводить к значительным временным задержкам, что накладывает дополнительные ограничения на тип разрабатываемых параллельных алгоритмов и программ. Таким образом, для эффективной реализации распределенных вычислений требуется обеспечить равномерную вычислительную нагрузку для всех процессоров кластера и минимальные информационные потоки передачи данных между этими процессорами [4, 5]. Естественной моделью решения этой задачи является граф, вершины которого соответствуют подзадачам и взвешены временной сложностью этих подзадач, а ребра представляют собой обмен сообщениями между подзадачами и взвешены соответствующими коммуникационными затратами. В терминах этой модели решение указанной выше задачи сводится к разбиению вершин графа на непересекающиеся подмножества с максимально близкими значениями суммарных весов вершин подмножеств и при минимальном значении суммы весов ребер, соединяющих вершины из разных подмножеств. В качестве пространства решений задачи рассматривается множество всех допустимых разбиений графа на непересекающиеся подграфы