557_Obrabotka_informatsii_i_matematicheskoe_modelirovanie_2014_

4.Галлагер Р.Г. Теория информации и надежная связь. М.: Советское радио,

1974.

5.Трофимов В.К., Храмова Т.В. Сжатие неравнозначными символами информации, порожденной неизвестным источником без памяти. // Автометрия. Новосибирск, 2012. т.48, №1, С.30-44.

6.Трофимов В.К., Храмова Т.В. Сжатие информации порожденной неизвестным источником.// Электросвязь. Москва, 2012. №4, С.41-44.

7.Трофимов В.К., Храмова Т.В. Универсальное кодирование марковских источников неравнозначными символами.// Дискретный анализ и исследование операций. Новосибирск. Май—июнь 2013. Том 20, № 3. – С. 71-83.

8.Кричевский P.E. Длина блока, необходимая для получения заданной избыточности. – ДАН СССР, 1965, т.171, № I. – С. 37-40.

9.Krichevsky R. E., Trofimov V. K. The performance of universal encoding // IEEE Transactions on Information Theory. 1981. – V. 27, № 2. – P. 199-207.

10.Рябко Б.Я. Дважды универсальное кодирование.// Проблемы передачи информации. – 1984. Т. 20, № 3. – С. 24-28.

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

РЕЖИМЕ

Шурина Э.П.1,2, Штабель Н.В. 2, Михайлова Е.И. 1,2 1 НГТУ, 2 ИНГиГ им. А.А. Трофимука СО РАН, Новосибирск

e-mail: mik_kat@ngs.ru

С ростом технических возможностей производства значительно возрос интерес к искусственным материалам. Перспективными направлениями исследований являются разработка технологий изготовления композитных материалов и изучение их свойств. Композитные материалы представляют собой искусственные среды, обладающие определенными свойствами, резко отличающимися от свойств естественных материалов. Такие материалы могут состоять как из диэлектрических, так и проводящих элементов (включений), иметь как периодическую, так и хаотическую структуру. Также может варьироваться форма включений [1-2]. В силу сложной геометрии, широкого рабочего диапазона частот, значительно зависящего от электромагнитных характеристик и структуры материала, исследование их аналитическими методами затруднительно. Поэтому предлагается использовать методы численного моделирования. В данной работе для исследования таких структур был применен векторный метод конечных элементов [3-4].

Композитные материалы, рассмотренные в работе, состоят из проводящих микровключений и матрицы. Под матрицей мы понимаем материал образца, окружающий включения. Малые размеры включений по сравнению с длиной волны возбуждаемого поля и общими размерами образца позволяют описать свойства композитного материала с помощью эффективных характеристик.

71

Среда с эффективным коэффициентом – это материал, свойства которого близки к средним значениям образца с микровключениями.

Вработе предложен способ определения эффективной тензорной (анизотропной) характеристики электрофизических свойств среды. Коэффициент включает в себя проводящие и диэлектрические свойства образца

ивычисляется по результатам прямого моделирования электромагнитного поля в областях с включениями в виде комплекснозначного тензора второго ранга.

Вкачестве прямой задачи рассматривается задача моделирования электромагнитного поля, изменяющегося во времени по гармоническому закону. Решается векторное уравнение Гельмгольца относительно

проницаемость [Гн/м], μr – относительная магнитная проницаемость, µ0 = 4π ×10-7 Гн/м; σ – электропроводность среды [См/м], Ω – трехмерная область с

n E e E0 ,

1 rot E n m 0 .

Поставленная задача решается векторным методом конечных элементов. Для построения вариационной постановки вводятся функциональные пространства

H(rot, ) u L2 ( ) : rot u L2 ( ) ,

с нормой и скалярным произведением.

Вариационная постановка принимает вид: найти E H0 (rot,) E0 такое, что v H0 (rot, ) выполняется

Для построения дискретной вариационной постановки расчетная область Ω разбивается на n непересекающихся тетраэдров, вводится конечномерное

подпространство H0h (rot,) H0 (rot,) и базисные функции wik H0h (rot,) . Дискретная вариационная постановка формулируется следующим образом:

Неоднородность правой части получаем из неоднородного электрического краевого условия на уровне сборки системы линейных алгебраических уравнений (СЛАУ).

В данной работе предлагается представить композитный материал как некоторую анизотропную среду. Рассматриваются среды, однородные по своим магнитным свойствам. Эффективный тензор Z является аналогом коэффициента i , содержащего информацию о свойствах включений. Тогда, уравнение второго порядка с эффективным коэффициентом принимает вид:

rot 1 rot E i ZE 0

где Z – комплекснозначный тензор второго ранга.

Для того, чтобы вычислить элементы тензора Z, воспользуемся законом

Ампера. Напряженность магнитного поля H можно найти из закона Фарадея следующим образом:

H (i) 1 rot E.

На основе вычисленных полей E и H выполняется расчет эффективного коэффициента сложной среды в виде осредненного плотного тензора.

Вработе предлагаются и сравниваются два способа вычисления тензора Z.

Входе выполненных исследований один из способов дал некорректные результаты для тестовой задачи в однородной среде. Для проверки корректности вычисленного эффективного коэффициента среды были выполнены расчеты для анизотропной задачи с полученным эффективным коэффициентом Z.

Для решения анизотропной задачи вводятся те же функциональные пространства, что и для изотропной. Вариационная постановка принимает вид

Для полученных эффективных характеристик проведено моделирование электромагнитного поля и сравнение с результатами моделирования в областях с включениями. Выполнено сравнение результатов расчета изотропной [5] и анизотропной задач [6-8] для композитных материалов различной конфигурации. Расчеты выполнены на низких и на высоких частотах для разного способа возбуждения поля. Исследована область применимости полученного метода вычисления тензорного коэффициента.

Результаты моделирования анизотропной задачи сравниваются с результатами исходной изотропной задачи. Конфигурация электрического поля, полученного решением задачи с тензорным коэффициентом Z, хорошо согласуется с конфигурацией электрического поля изотропной задачи (с учетом того, что включения в анизотропной задаче не идентифицируются).

73

Литература

1.Smith D. R., Kroll N. Negative refractive index in left-handed materials //Physical Review Letters. – 2000. – Vol. 85. – №. 14. – p. 2933.

2.Li J., Huang Y. Introduction to Metamaterials //Time-Domain Finite Element Methods for Maxwell's Equations in Metamaterials. – Springer Berlin Heidelberg, 2013.

3.Nédélec J. C. Mixed finite elements in R3 //Numerische Mathematik. – 1980. – Vol. 35. – №. 3. – pp. 315-341.

4.Nédélec J. C. A new family of mixed finite elements in R3 // Numerische Mathematik. –1986. – Vol.50. – №.1. – pp. 57-81.

5.Эпов М. И., Шурина Э. П., Михайлова Е. И. Моделирование электромагнитного поля в неоднородных по электрофизическим свойствам средах //Теория и численные методы решения обратных и некорректных задач.

– 2013. – С. 107.

6.Орловская Н.В., Шурина Э.П., Эпов М.И. Mоделирование электромагнитных полей в среде с анизотропной электропроводностью // Вычислительные технологии. 2006. Т. 11. № 3. С. 99-116.

7.Орловская Н.В., Шурина Э.П., Эпов М.И. Тензорный коэффициент электропроводности в геофизических приложениях // Вычислительные технологии. 2008. Т. 13. № 1. – С. 99-112.

8.Шурина Э. П., Штабель Н. В. Анализ векторных конечноэлементных аппроксимаций уравнений Максвелла в анизотропных средах //Вычислительные технологии. – 2013. – Т. 18. – №. 4. – С. 91-104.

74

Секция 2

ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ

АЛГОРИТМЫ УПРАВЛЕНИЯ РЕСУРСАМИ ОБЛАЧНЫХ СИСТЕМ2

Ефимов А.В. СибГУТИ, Новосибирск

e-mail: efimov@cpct.sibsutis.ru, тел.: (383) 269-82-75

Под облачными технологиями обычно понимают инструментарий (аппаратурный и программный) позволяющий по запросу из сети удалённо получать вычислительные ресурсы, которые расположены на распределённых вычислительных системах (ВС).

Эффективность функционирования ВС зависит от того, как организовано управление её ресурсами. Перспективной считается технология параллельного мультипрограммирования [1], согласно которой все ресурсы системы разделяются между несколькими одновременно решаемыми задачами пользователей.

Одним из подходов реализации мультипрограммного режима является использование облачных вычислений на основе технологии виртуализации ресурсов. В рамках указанной технологии гипервизор формирует пул всех ресурсов системы, из которого каждому пользователю по запросу предоставляется виртуальная машина (ВМ) с необходимым количеством ресурсов. В зависимости от загрузки ресурсов, их количество масштабируется системой в автоматическом режиме. Одной из задач планирования в гипервизоре является оптимизация количества ВМ и физических узлов, что позволяет повысить эффективность использования ресурсов, за счёт снижения потребления электроэнергии, и повышении загрузки ресурсов.

В докладе рассмотрены основные подходы к распределению ресурсов в облачных системах, а так же их достоинства и недостатки. Приведены результаты сравнительного исследования алгоритмов управления ресурсами в гипервизоре KVM [2] и программном комплексе OpenStack [3] проводилось на ресурсах ЦПВТ ФГОБУ ВПО «СибГУТИ» [4].

Литература 1. Хорошевский В.Г. Архитектура вычислительных систем. Издание 2,

переработанное и дополненное. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2008. –

с. 508.

2. Сайт проекта KVM (for Kernel-based Virtual Machine). – URL: http://www.linux-kvm.org/page/Main_Page (дата обращения 15.02.2014 г.)

2 Работа выполнена при поддержке Российского фонда фундаментальных исследований (гранты № 13-07-00160, 12-07-00188) и Совета по грантам Президента РФ (грант № МД-2620.2014.9)

75

3.Сайт проекта OpenStack. – URL: http://www.openstack.org/ (дата обращения

15.02.2014 г.)

4.Сайт Центра параллельных вычислительных технологий Федерального государственного образовательного бюджетного учреждения высшего профессионального образования «Сибирский государственный университет телекоммуникаций и информатики». – URL: http://cpct.sibsutis.ru/ (дата обращения 15.02.2014 г.)

ФОРМИРОВАНИЕ СТРУКТУРНОЙ ИЗБЫТОЧНОСТИ В ПЛАНИРОВЩИКЕ РЕСУРСОВ MAUI

Ефимов А.В.1, Павский К.В.2

1СибГУТИ, Новосибирск, e-mail: efimov@cpct.sibsutis.ru, тел. (383) 269-82-75

2 ИФП СО РАН, Новосибирск, e-mail: pkv@isp.nsc.ru, тел. (383) 330-56-26

Среднее время безотказной работы компонентов современных вычислительных систем (ВС) оценивается как 104 – 106 ч. Для достижения уровня производительности в несколько PetaFLOPS требуются сотни тысяч процессорных ядер. По оценкам экспертов, среднее время между частичными отказами (отказами одного или нескольких компонентов) в ВС такого масштаба будет менее 20 часов.

Важной является задача организации отказоустойчивого выполнения параллельных программ на ВС. Основным подходом к решению данной проблемы является периодическое сохранение состояния таких программ в контрольных точках (КТ) [1].

Современные ВС эксплуатируются в моно- и мультипрограммных режимах функционирования [2]. При частичном отказе ВС замену вышедших из строя элементарных машин (ЭМ) на исправные осуществляет диспетчер ее ресурсов. При этом производится освобождение вычислительных ресурсов, занимаемых программами, которые использовали отказавшую ЭМ. Далее для каждой из программ выполняется повторная процедура планирования для выделения новых вычислительных ресурсов.

В работе предложен подход, обеспечивающий возможность возобновления прерванных программ без повторения процедуры планирования. Данный подход предполагает формирование вычислительной подсистемы ЭМ со структурной избыточностью. Количество резервных ЭМ рассчитывается по заданным интенсивностям отказов и восстановлений ЭМ в соответствии с разработанной ранее математической моделью функционирования ВС [3].

Предложенный подход реализован в виде расширения функционала планировщика MAUI, используемого в составе популярных диспетчеров ресурсов, таких как TORQUE, SLURM, LoadLeveler, SGE и др.

76

Литература 1. Поляков А.Ю. О восстановлении программ из контрольной точки // Вестник

ЮУрГУ. Серия "Математическое моделирование и программирование". – 2010.

– № 35(211), № 6. – С. 91-103.

2. Хорошевский В.Г. Архитектура вычислительных систем. М.: МГТУ им. Баумана, 2008, 520 с.

3. Хорошевский В.Г., Павский В.А., Павский К.В. Математическая модель и расчет показателей функционирования вычислительных систем со структурной избыточностью // Известия ЮФУ. Технические науки. – Таганрог: Изд. ТТИ ЮФУ. № 5 (130), 2012 г., С. 37-41.

ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ДОСТУПА К РАСПРЕДЕЛЕННЫМ МАССИВАМ В ПРОГРАММАХ

НА ЯЗЫКЕ IBM X103

Кулагин И.И., Курносов М.Г. СибГУТИ, Новосибирск

e-mail: ivan.i.kulagin@gmail.com, mkurnosov@gmail.com

Мультиархитектурная организация современных вычислительных систем (ВС) [1] диктует необходимость создания высокоуровневых языков параллельного программирования.

В рамках проекта High Productivity Computing Systems компании IBM

и Cray инициировали разработку языков параллельного программирования IBM X10 и Cray Chapel, которые реализуют на распределенной ВС (её распределенной памяти) разделённое глобальное адресное пространство

(Partitioned Global Address Space – PGAS).

Вотличие от стандарта MPI программы на IBM X10 не обращаются напрямую к коммуникационным функциям, а оперируют распределенными структурами данных (массивами, списками) и конструкциями языка для управления параллельными задачами (activities, tasks).

Вмире активно развиваются модели и алгоритмы оптимизирующей компиляции программ на IBM X10 [2]. Одной из остро стоящих проблем является оптимизация неявных информационных обменов между вычислительными узлами. Например, в программах на языке IBM X10 часто встречается итерационное обращение к данным находящимся на другом вычислительном узле (в терминах языка IBM X10 place). Это приводит к копированию данных на каждой итерации с удаленного узла (place) на локальный, причем, некоторые данные могут копироваться многократно на тот же самый узел.

Вданной работе предлагается метод компиляторной оптимизации доступа

кмассивам в параллельных программах на языке IBM X10. Метод основан на

3 Работа выполнена при поддержке РФФИ (гранты № 12-07-00145,13-07-00160)

77

опережающей (перед итерациями) передачи массива на удаленные вычислительные узлы (place). Поиск локального массива, доступ к которому

на распределенный по узлам массив (scalar replacement). Это обеспечивает сокращение времени выполнения программы за счет уменьшения количества коммуникационных операций и объема передаваемых данных.

На рисунке показан пример оптимизации передачи массива A. В случае неоптимизированной версии (рисунок 1а) на каждой итерации цикла массив A передается узлу с номером idx. В оптимизированной версии (риунок 1б) производится предварительное копирование массива A на каждый узел единожды, сохраняя его в распределенном массиве sharedA.

Рисунок 1 – Пример оптимизации передачи массива A в параллельной

программе на языке IBM X10:

а) не оптимизированный код, б) оптимизированный код

Рисунок 2 – Зависимость объема S передаваемых данных от количества n вычислительных узлов (place), в тестовой программе на IBM X10 (сеть связи Gigabit Ethernet): 1 – неоптимизированная программа;

2 – оптимизированная программа

78

В результате оптимизации тестовой программы, работающей с распределенным массивом с элементами типа Long, объем коммуникаций в среднем сокращен в 4-6 раз (рисунок 2).

Эффективность метода повышается с увеличением количества обращений к элементам удаленного массива. Ускорение выполнения параллельной программы, обеспечиваемое применением предложенного метода, варьируется в пределах от 20% до 60%.

Литература

1.Хорошевский В.Г. Распределенные вычислительные системы с программируемой структурой // Вестник СибГУТИ. – 2010. – № 2 (10). – С.3-41.

2.Rajkishore Barik, Jisheng Zhao, David Grove, Igor Peshansky, Zoran Budimlic, and Vivek Sarkar. Communication Optimizations for Distirbuted-Memory X10 Programs // IEEE International Parallel and Distributed Processing Symposium, 2011. – P. 4 – 12.

ВЫПОЛНЕНИЕ ПАРАЛЛЕЛЬНЫХ МАСШТАБИРУЕМЫХ ПРОГРАММ НА РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ 4

Мамойленко С.Н. 1, Крамаренко К.Е. 1, Ефимов А.В.2, Перышкова Е.Н.2 1 СибГУТИ, Новосибирск

2 ИФП СО РАН, Новосибирск

1 E-mail: {msn, kostya}@cpct.sibsutis.ru, тел. (383) 269-82-75

2 E-mail: {efimov, e_perishkova}@cpct.sibsutis.ru, тел. (383) 330-56-26

Распределенные вычислительные системы (ВС) являются основой современной индустрии высокопроизводительной обработки информации. Исследования в данной области характеризуются массовым использованием кластерных ВС и внедрением GRID-технологий.

Эффективность функционирования ВС зависит от того, как организовано распределение её ресурсов. Перспективной считается технология параллельного мультипрограммирования [1], согласно которой все ресурсы системы разделяются между несколькими одновременно выполняющимися параллельными программами.

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

4 Работа выполнена при поддержке Российского фонда фундаментальных исследований (гранты № 13-07-00160, 12-07-00188) и Совета по грантам Президента РФ (грант № МД-2620.2014.9)

79

Одним из популярных планировщиков распределенных ВС является MAUI, который может работать с разными СПО имеющими модульную архитектуру, и позволяющими менять компоненты в рамках заданных интерфейсов. В качестве алгоритма планирования MAUI использует backfilling (обратное заполнение) с резервированием ресурсов, позволяющий достичь загрузки ВС в среднем до 90%. MAUI не поддерживает планирование выполнения масштабируемых программ. Такие задачи могут выполняться на не четко заданной конфигурации ресурсов и допускают их варьирование. Учет свойства адаптации масштабируемой программы к ресурсам для её решения может повысить степень загрузки ВС.

В докладе рассматривается результаты натурного моделирования модифицированного планировщика MAUI [2], в котором реализована возможность учитывать свойства масштабируемых программ при планировании загрузки ресурсов вычислительной системы.

Литература

1.Хорошевский В.Г. Архитектура вычислительных систем. Издание 2, переработанное и дополненное – М.: Изд-во МГТУ им. Н.Э. Баумана, 2008. –

C. 508.

2.Сайт проекта Maui Scheduler. –

URL: http://docs.adaptivecomputing.com/maui/ (Дата обращения 15.02.2014 г.).

ОЦЕНКА ФУНКЦИИ РАСПРЕДЕЛЕНИЯ ВРЕМЕНИ ПРЕБЫВАНИЯ РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ В СОСТОЯНИИ НИЗКОЙ ПРОИЗВОДИТЕЛЬНОСТИ *

Павский В.А., Павский К.В.

КТИ, Кемерово, СибГУТИ, Новосибирск e-mail: pavvm@kemtipp.ru, pkv@isp.nsc.ru тел.: (3842) 73-42-00 , (383) 330-56-26

Использование колоссальных потенциальных возможностей современных большемасштабных распределенных вычислительных систем (ВС), безусловно, определяется их надежностью, производительностью, и способами организации функционирования [1]. Несмотря на высокую надежность элементов микроэлектроники, в силу большемасштабности ВС, вероятность возникновения отказов в таких системах повышается с ростом количества вычислительных узлов [2, 3]. В такой ситуации особую актуальность приобретает анализ потенциальных возможностей распределенных ВС.

В работе рассматриваются распределенные, масштабируемые вычислительные системы со структурной избыточностью (резервом) [1]. Такие ВС состоят из десятков и сотен тысяч ядер (или элементарных машин (ЭМ) – самостоятельная вычислительная единица) [1, 4]. Современные системы

*) Работа выполнена при поддержке РФФИ (грант №13-07-00160, №12-07-00145).

80