Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364141
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8693)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: «Оптимизация кластерной системы на базе pvm компьютерной лаборатории физического факультета»

Название: «Оптимизация кластерной системы на базе pvm компьютерной лаборатории физического факультета»
Раздел: Остальные рефераты
Тип: реферат Добавлен 07:11:43 05 сентября 2011 Похожие работы
Просмотров: 54 Комментариев: 0 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

ИВАНОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Кафедра теоретической физики математического и компьютерного моделирования.

Курсовая работа на тему:

« Оптимизация кластерной системы на базе PVM компьютерной лаборатории физического факультета».

Выполнил: студент 4 курса 1 группы:

Медведев Алексей Александрович

Подпись:___________

Научный руководитель:

Гурьянов Андрей Владимирович

Подпись:___________

Работа защищена: «___» _________ 20__г.

Оценка:___________

Заведующий кафедрой:

доцент кафедры теоретической физики

математического и компьютерного моделирования

Логинов Евгений Константинович

Подпись:__________

Иваново 2010

Содержание.

Введение

Математические основы параллельных вычислений.

Реализация параллельных вычислений.

Кластерные системы.

Развитие кластерных систем.

Применение кластерных систем

Типичные задачи для кластерных систем.

Принципы построения кластера.

Производительность кластерной системы. Законы Амдала.

Описание системы PVM.

Оптимизация кластерной системы на базе PVM.

Описание оборудования и предыдущей конфигурации программного обеспечения кластера.

Установка и настройка новой конфигурации программного обеспечения кластера.

Процесс компиляции собственного программного обеспечения для работы с PVM.

Тестирование новой конфигурации вычислительной системы.

Нагрузочное тестирование сети.

Тест имитационной модели метода Монте-Карло.

Заключение

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

Приложение

Введение.

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

Несмотря на кажущуюся простоту решения, оно является подчас весьма нетривиальной задачей по проектированию вычислительной техники и разработки алгоритмов. Первая проблема состоит в том, что для того, чтобы задачу можно было решить с помощью параллельных вычислений алгоритм её решения должен допускать распараллеливание, но далеко не каждая задача может быть решена параллельным алгоритмом. Другой же, не менее важной проблемой является построение системы, на которой была бы возможна реализация параллельных вычислений.

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

Соответственно была поставлена задача: оптимизировать работу параллельной вычислительной машины (PVM), созданной на базе компьютерной лаборатории физического факультета, которую можно более эффективно использовать, как для обучения студентов приемам параллельного программирования, так и для решения затратных по времени задач. Таким образом, задачи, которые были поставлены передо мной в моей курсовой являются: изучение основных принципов построения распределенных вычислительных систем, установка графической консоли XPVM, изучение интерфейса и принципов ее работы, повышение эффективности работы PVM.

Математические основы параллельных вычислений

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

для того чтобы произвести второе умножение не требуется знать результата первого, следовательно, оба умножения можно произвести параллельно, и только после этого произвести сложение. Очевидно, не каждое вычисление можно распараллелить. Выражение:

можно вычислить только последовательно, сначала первое умножение, затем второе, и только после этого — сложение.

В основе анализа распараллеливаемости алгоритмов лежит исследование зависимостей по данным между операциями. Если от результата одной операции зависит результат другой, то вторая называется зависимой по данным от первой. Совокупность всех зависимостей по данным представляет собой ориентированный граф без циклов , в котором вершины — операции, а рёбра — зависимости. Длина самого протяжённого пути по этому графу называется минимальной высотой алгоритма и определяет минимально возможное время , за которое теоретически возможно выполнить вычисления по алгоритму. Практически это время не всегда достижимо по той причине, что может потребоваться параллельное вычисление очень большого количества операций, что может оказаться неосуществимым на выделенных вычислительных ресурсах или потребуются очень большие накладки на синхронизацию параллельных вычислительных потоков.

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

Иллюстрация распараллеливания фрагмента алгоритма быстрого преобразования Фурье «бабочка» (рис.1).

Фрагмент алгоритма БПФ (рис.1). Стрелками обозначены зависимости по данным, жирными стрелками — одна из длиннейших цепочек зависимостей. Слева написано, на каком по порядку такте процессора могут выполняться операции.

Последовательный

2 операции за такт максимум

3 операции за такт максимум

Предел параллельности

1. t1=br·qr

2. t2=bi·qi

3. t3=br·qi

4. t4=bi·qr

5. cr=t1−t2

6. ci=t3+t4

7. xr=ar+cr

8. xi=ai+ci

9. yr=ar−cr

10. yi=ai−ci

1. t1=br·qr

t2=bi·qi

2. t3=br·qi t4=bi·qr

3. cr=t1−t2 ci=t3+t4

4. xr=ar+cr xi=ai+ci

5. yr=ar−cr yi=ai−ci

1. t1=br·qr

t2=bi·qi t3=br·qi

2. t4=bi·qr cr=t1−t2

3. ci=t3+t4 xr=ar+cr yr=ar−cr

4. xi=ai+ci yi=ai−ci

1. t1=br·qr

t2=bi·qi t3=br·qi t4=bi·qr

2. cr=t1−t2 ci=t3+t4

3. xr=ar+cr xi=ai+ci yr=ar−cr yi=ai−ci

Следует заметить, что высота алгоритма может не иметь никакой зависимости по отношению к сложности алгоритма — алгоритм с большим порядком сложности может иметь гораздо меньшую высоту, и, соответственно, быстрее исполняться на параллельной системе.

Реализация параллельных вычислений.

Существует два основных подхода к распараллеливанию вычислений в микропроцессорных системах, называемые однопоточным и многопоточным параллелизмом. Различие заключается в использовании одного или нескольких потоков исполнения для параллельных вычислений.

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

Он реализуется внутри одного потока исполнения. Возможность однопоточного параллельного исполнения почти целиком лежит на архитектуре микропроцессора — именно она определяет способность микропроцессора выполнять инструкции параллельно.

Однопоточный параллелизм обладает своими достоинствами и недостатками. Достоинства:

- отсутствие необходимости синхронизации — все операции выполняются внутри одного потока, и, следовательно, в строго определённой последовательности.

- отсутствие необходимости поддержки параллелизма на уровне операционной системы.

- отсутствие необходимости в средствах управления разделяемыми ресурсами.

Недостатки:

- затруднённость использования в алгоритмах с условными переходами.

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

Многопоточный параллелизм — использование нескольких потоков для достижения параллельного исполнения операций. Для того чтобы обеспечить многопоточный параллелизм необходимо создать систему с несколькими процессорами или процессорными ядрами. Были разработаны специальные технологии для создания многопроцессорных систем. Которые позволяли обрабатывать данные параллельно, а, следовательно, быстрее. Соответственно создавались операционные системы, поддерживающие многопроцессорные технологии. Такие как: Solaris (Sun Microsystems), Unix-подобные OS: Irix (SGI), AIX (IBM); Linux RedHat; Windows XP и др. В подобного рода системах существует такое понятие как поток. Поток (thread) — это последовательность инструкций выполняемых в пределах контекста процесса. Эти операционные системы поддерживает многопоточные процессы. Слово «многопоточные» подразумевает содержание множества управляемых потоков. Традиционный UNIX процесс содержит один управляемый поток. Многопоточный, в свою очередь, содержит множество потоков, которые выполняются независимо. Так как каждый поток выполняется независимо, распараллеливание кода программы приводит к: улучшению чувствительности приложения, использование многопроцессорности более эффективно, улучшает структуру программы, использование меньше ресурсов системы.

Существуют следующие методы достижения параллельных вычислений :

- Упаковка данных для групповой обработки единичными инструкциями применением специальных методик. Например, возможно сложить две пары 8-битных данных 16-битной операцией исключив возможность переполнения. Метод имеет очень ограниченное применение.

- Суперскалярная архитектура. Устройство управления микропроцессора самостоятельно анализирует поток инструкций на предмет возможности параллельного исполнения и управляет нескольких функциональными устройствами.

- Векторная обработка. Микропроцессор имеет инструкции, производящие групповые однотипные операции. Однотипные операнды упаковываются в один векторный регистр. Этот метод аналогичен первому, но обеспечение параллельности лежит на микропроцессорной архитектуре. Векторные регистры, как правило, имеют большую разрядность. Требуется адаптировать программу для использования векторных инструкций или применять оптимизирующий компилятор.

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

Использование большего числа процессоров ускоряет работу программы, при обработке большого количества данных, соответственно рациональнее использовать многопроцессорные системы для решения сложных задач за более короткое время.

1. Кластерные системы.

Кластер — это модульная многопроцессорная система, созданная на базе стандартных вычислительных узлов, соединенных высокоскоростной коммуникационной средой. Сейчас слова «кластер» и «суперкомпьютер» в значительной степени синонимы, но прежде чем об этом стало можно с уверенностью говорить, аппаратные средства прошли длительный цикл эволюции.

Развитие кластерных систем.

В течение первых 30 лет с момента появления компьютеров, вплоть до середины 1980-х гг., под «суперкомпьютерными» технологиями понимали исключительно производство специализированных высоко производительных систем (High Performance Computing) для вычислений.

Однако появление однокристального микропроцессора практически стерло разницу между «массовыми» и «особо мощными» процессорами, и с этого момента единственным способом создания суперкомпьютера стал путь объединения процессоров для параллельного решения одной задачи. Примерно до середины 1990-х гг. основное направление развития суперкомпьютерных технологий было связано с построением специализированных многопроцессорных систем из массовых микросхем. Один из сформировавшихся подходов — SMP (Symmetric Multi Processing), подразумевал объединение многих процессоров с использо­ванием общей памяти, что сильно облегчало программирование, но предъявляло высокие требования к самой памяти. Сохранить быстродействие таких систем при увеличении количества узлов до десятков было практически невозможно. Кроме того, этот подход оказался самым дорогим в аппаратной реализации. На порядок более дешевым и практически бесконечно масштабируемым оказался способ МРР (Massively Parallel Processing), при котором независимые специализированные вычислительные модули объединялись специализированными каналами связи, причем и те и другие создавались под конкретный суперкомпьютер и ни в каких других целях не применялись.

Идея создания, так называемого, кластера рабочих станций фактически явилась развитием метода МРР, ведь логически МРР-система не сильно отличалась от обычной локальной сети. Локальная сеть стандартных персональных компьютеров, при соответствующем ПО, использовавшаяся как многопроцессорный суперкомпьютер, и стала прародительницей современного кластера. Эта идея получила более совершенное воплощение в середине 1990-х гг., когда благодаря повсеместному оснащению ПК высокоскоростной шиной PCI и появлению дешевой, но быстрой сети. Fast Ethernet кластеры стали догонять специализированные МРР-системы по коммуникационным возможностям. Это означало, что полноценную МРР-систему можно было создать из стандартных серийных компьютеров при помощи серийных коммуникационных технологий.

1.2. Применение кластерных систем.

Сфера применения кластерных систем сейчас нисколько не уже, чем суперкомпьютеров с другой архитектурой: они не менее успешно справляются с задачей моделирования самых разных процессов и явлений. Суперкомпьютерное моделирование может во много раз удешевить и ускорить вывод на рынок новых продуктов, а также улучшить их качество. Например, вместо того чтобы строить дорогостоящие тестовые модели новых автомобилей, чтобы затем разбить их об стенку ради проведения инженерных расчетов, можно быстрее и точнее все посчитать на компьютерных моделях. Благодаря этому многим западным автомобильным концернам удалось сократить срок разработки новой модели автомобиля в пять раз — с 10 до 2 лет. Компьютерная обработка геофизических данных позволяет создавать высокодетализированные модели нефтяных и газовых месторождений, обеспечивая более эффективную, безопасную и дешевую разработку скважин.

Именно развитие кластерных технологий сделало высокопроизво­дительные вычисления широкодоступными и позволило самым разным предприятиям воспользоваться их преимуществами. Вот как распределяются области применения 500 самых мощных компьютеров мира: 44,3% — добывающая, электронная, автомобильная, авиационная и др. отрасли тяжелой промышленности и машиностроения, чуть более 20% — наука и образование, суперкомпьютерные центры. Более 18% приходится на погодные и климатические исследования, 7% — ядерные, космические, энергетические и военные государственные программы, 3,5% — финансовые компании и банки. Кроме того, в списке есть компании и организации, занимающиеся медициной и разработкой новых лекарств, компьютерной графикой, перевозками, торговлей, производством продуктов питания, консалтингом и государственным управлением.

1.3. Типичные задачи для кластерных систем.

Сегодня можно говорить о том, что кластерные системы успешно применяются для всех задач суперкомпьютинга — от расчетов для науки и промышленности до управления базами данных. Практически любые приложения, требующие высокопроизводительных вычислений, имеют сейчас параллельные версии, которые позволяют разбивать задачу на фрагменты и обсчитывать ее параллельно на многих узлах кластера. Например, для инженерных расчетов (прочностные расчеты, аэромеханика, гидро- и газодинамика) традиционно применяются так называемые сеточные методы , когда область вычислений разбивается на ячейки, каждая из которых становится отдельной единицей вычислений. Эти ячейки обсчитываются независимо на разных узлах кластера, а для получения общей картины на каждом шаге вычислений происходит обмен данными, распространенными в пограничных областях. Для практических расчетов (3D-анимация, крэш-тесты, разведка нефтяных и газовых месторождений, прогнозирование погоды) обычно используются кластеры из 10-200 узлов. При этом основная задача — обеспечение эффективной работы кластера с конкретным приложением. Хотелось бы обратить внимание на класс задач эффективно подвергающихся распараллеливанию:

Одномерные массивы.

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

Двумерные массивы.

При исполнении вложенных циклов обычно эффективно распараллеливаются самые внешние циклы. Однако практически все действия с матрицами (сложение, умножение, умножение на вектор, прямое произведение) могут быть выполнены на кластере. Многие алгоритмы линейной алгебры (но не все) могут быть эффективно распараллелены. Некоторые библиотеки подпрограмм (например, LAPACK) существуют для параллельных машин. Совершенно неэффективно использовать кластеры для работы с матрицами низкой размерности (например, 3x3). Но можно переписать алгоритм для одновременной обработки нескольких (к примеру, 1000) матриц - обращение, поиск собственных чисел и т.д. При увеличении размера матриц растет эффективность работы программы, но растет и размер требуемой памяти для хранения матриц.

Клеточные автоматы.

Во многих областях знания встречаются задачи, которые сводятся к вычислению эволюции объектов, расположенных в дискретных точках и взаимодействующих с ближайшими соседями. Простейшей и, наверно, наиболее широко известной такой задачей является игра "Жизнь". Можно так же привести в качестве примера модель магнетиков Изинга, представляющую собой набор спинов (элементарных магнитов), расположенных в узлах решетки и взаимодействующих только с ближайшими соседями. Алгоритм построения эволюции магнетиков Изинга будет во многом идентичен алгоритму игры "Жизнь".

Системы дифференциальных уравнений.

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

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

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

1.4. Принципы построения кластера.

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

Каждый узел работает под управлением своей копии стандартной операционной системы, в большинстве случаев — Linux. Состав и мощность узлов могут быть разными в рамках одного кластера, однако чаще строятся однородные кластеры. Выбор конкретной коммуникационной среды (интерконнекта) определяется многими факторами: особенностями решаемых задач, доступным финансированием, требованиями к масштабируемости и т. п. В кластерных решениях применяются такие технологии интерконнекта, как Fast Ethernet, Gigabit Ethernet, SCI, Myrinet, QsNet, InfiniBand. Исходя из всего вышесказанного, можно утверждать, что использование кластера на физическом факультете позволит оптимизировать процесс расчета моделей сложных структур, таких как отдельные молекулы (в частности белки), смесей различных веществ, кристаллов и т.д.

Производительность кластерной системы. Законы Амдала.

Мерой измерения производительности любой вычислительной системы является Flops (floating point operations per second) — количество операций с плавающей точкой в секунду.

Самым важным ограничением повышения производительности от распараллеливания алгоритма решения задачи являются законы Амдала, утверждающие:

1-ый закон Амдала . Производительность вычислительной системы, состоящей из связанных между собой устройств, в общем случае определяется самым непроизводительным ее устройством.

Следствие . Пусть система состоит из простых устройств и граф системы связный. Асимптотическая производительность системы будет максимальной, если все устройства имеют одинаковые пиковые производительности.

Предположим, что по каким-либо причинам n операций из N мы вынуждены выполнять последовательно. Причины могут быть разными. Например, операции могут быть последовательно связаны информационно. И тогда без изменения алгоритма их нельзя реализовать иначе. Но вполне возможно, что мы просто не распознали параллелизм, имеющийся в той части алгоритма, которая описывается этими операциями. Отношение β = n /N назовем долей последовательных вычислений .

2-й закон Амдала . Пусть система состоит из s одинаковых простых универсальных устройств. Предположим, что при выполнении параллельной части алгоритма все s устройств загружены полностью. Тогда максимально возможное ускорение равно:

3-й закон Амдала . Пусть система состоит из простых одинаковых универсальных устройств. При любом режиме работы ее ускорение не может превзойти обратной величины доли последовательных вычислений.

Закон Амдала в сетевой форме.

Одной из главных характеристик параллельных систем является ускорение R параллельной системы, которое определяется выражением: , где T1 − время решения задачи на однопроцессорной системе, а Tn − время решения той же задачи на n − процессорной системе. Пусть W = Wск + Wпр, где W − общее число операций в задаче, Wпр − число операций, которые можно выполнять параллельно, а Wcк − число скалярных (нераспараллеливаемых) операций. Обозначим также через t время выполнения одной операции. Тогда получаем закон Амдала:Здесь a = Wск/W − удельный вес скалярных операций. Закон Амдала определяет принципиально важные для параллельных вычислений положения: 1. Ускорение зависит от потенциального параллелизма задачи (величина 1–а) и параметров аппаратуры (числа процессоров n). 2. Предельное ускорение определяется свойствами задачи. Пусть, например, a = 0,2 (что является реальным значением), тогда ускорение не может превосходить 5 при любом числе процессоров, то есть максимальное ускорение определяется потенциальным параллелизмом задачи. Очевидной является чрезвычайно высокая чувствительность ускорения к изменению величины а.

Основной вариант закона Амдала не отражает потерь времени на межпроцессорный обмен сообщениями. Эти потери могут не только снизить ускорение вычислений, но и замедлить вычисления по сравнению с однопроцессорным вариантом.

Поэтому необходима некоторая модернизация закона:

Здесь Wc − количество передач данных, tc − время одной передачи данных.


Выражение

и является сетевым законом Амдала . Коэффициент сетевой деградации вычислений с:

определяет объем вычислений, приходящийся на одну передачу данных (по затратам времени). При этом сА определяет алгоритмическую составляющую коэффициента деградации, обусловленную свойствами алгоритма, а сТ − техническую составляющую, которая зависит от соотношения технического быстродействия процессора и аппаратуры сети.

1.6. Описание системы PVM.

PVM (Parallel Virtual Machine) - это побочный продукт продвижения гетерогенных сетевых исследовательских проектов, распространяемый авторами и институтами, в которых они работают. Общими целями этого проекта являются исследование проблематики и разработка решений в области гетерогенных параллельных вычислений. PVM представляет собой набор программных средств и библиотек, которые эмулируют общецелевые, гибкие гетерогенные вычислительные структуры для параллелизма во взаимосвязанных компьютерах с различными архитектурами. Главной же целью системы PVM является обеспечение возможности совместного использования группы компьютеров совместно для взаимосвязанных или параллельных вычислений. Основные постулаты, взятые за основу для PVM, следующие:

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

Прозрачность доступа к оборудованию: прикладные программы могут “видеть” аппаратную среду как группу виртуальных вычислительных элементов без атрибутов или эксплуатировать по выбору возможности специфических машин из пула хостов путем ``перемещения'' определенных счетных задач на наиболее подходящие для их решения компьютеры.

Вычисления, производимые с помощью процессов: единицей параллелизма в PVM является задача (часто, но не всегда совпадает с процессом в системе UNIX) - независимый последовательный поток управления, который может быть либо коммуникационным, либо вычислительным. PVM не содержит и не навязывает карты связей процессов; характерно, что составные задачи могут выполняться на одном процессоре.

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

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

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

Система PVM состоит из двух частей. Первая часть - это “демон” под названием pvmd3 - часто сокращается как pvmd, - который помещается на все компьютеры, создающие виртуальную машину. (Примером программы-демона может быть почтовая программа, которая выполняется в фоновом режиме и обрабатывает всю входящую и исходящую электронную почту компьютера). Разработан pvmd3 таким образом, чтобы любой пользователь с достоверным логином мог инсталлировать его на машину. Когда пользователь желает запустить приложение PVM, он, прежде всего, создает виртуальную машину. После этого приложение PVM может быть запущено с любого UNIX-терминала на любом из хостов. Несколько пользователей могут конфигурировать перекрывающиеся виртуальные машины, каждый пользователь может последовательно запустить несколько приложений PVM. Вторая часть системы - это библиотека подпрограмм интерфейса PVM. Она содержит функционально полный набор примитивов, которые необходимы для взаимодействия между задачами приложения. Эта библиотека содержит вызываемые пользователем подпрограммы для обмена сообщениями, порождения процессов, координирования задач и модификации виртуальной машины.

Вычислительная модель PVM базируется на предположении, что приложение состоит из нескольких задач. Каждая задача ответственна за часть вычислительной нагрузки приложения. Иногда приложение распараллеливается по функциональному принципу, т. е. каждая задача выполняет свою функцию, например: ввод, порождение, счет, вывод, отображение. Такой процесс часто определяют как функциональный параллелизм. Более часто встречается метод параллелизма приложений, называемый параллелизмом обработки данных . В этом случае все задачи одинаковы, но каждая из них имеет доступ и оперирует только небольшой частью общих данных. PVM поддерживает любой из перечисленных методов отдельно или в комплексе. В зависимости от функций задачи могут выполняться параллельно и нуждаться в синхронизации или обмене данными, хотя это происходит не во всех случаях.

В настоящее время PVM поддерживает языки программирования C, C++ и Фортран. Этот набор языковых интерфейсов взят за основу в связи с тем, что преобладающее большинство целевых приложений написаны на C и Фортран, но наблюдается и тенденция экспериментирования с объектно-ориентированными языками и методологиями.

Привязка языков C и C++ к пользовательскому интерфейсу PVM реализована в виде функций, следующих общепринятым подходам, используемым большинством C-систем, включая UNIX - подобные операционные системы. Уточним, что аргументы функции - это комбинация числовых параметров и указателей, а выходные значения отражают результат работы вызова. Прикладные программы, написанные на C и C++, получают доступ к функциям библиотеки PVM путем прилинковки к ним архивной библиотеки (libpvm3.a) как часть стандартного дистрибутива.

Привязка к языку Фортрана реализована скорее в виде подпрограмм, чем в виде функций. Такой подход применен по той причине, что некоторые компиляторы для поддерживаемых архитектур не смогли бы достоверно реализовать интерфейс между C и Фортран функциями. Непосредственным следствием из этого является то, что для каждого вызова библиотеки PVM вводится дополнительный аргумент - для возвращения результирующего статуса в вызвавшую его программу. Также унифицированы библиотечные подпрограммы для размещения введенных данных в буферы сообщения и их восстановления, они имеют дополнительный параметр для отображения типа данных. Кроме этих различий (и разницы в стандартных префиксах при именовании: pvm_ - для C и pvmf_ - для Фортран), возможно взаимодействие “друг с другом” между двумя языковыми привязками. Интерфейсы PVM на Фортране реализованы в виде библиотечных надстроек, которые в свою очередь, после разбора и/или определения состава аргументов, вызывают нужные C-подпрограммы. Так, Фортран - приложения требуют прилинковки библиотеки-надстройки (libfpvm3.a) в дополнение к C библиотеке(libpvm3.a).

Оптимизация кластерной системы на базе PVM.

Описание оборудования и предыдущей конфигурации программного обеспечения кластера.

Парк оборудования компьютеризированной лаборатории физического факультета состоит из 10 машин с процессорами: AMD ATHLON-64 X2 4200+, оперативной памятью: 2 ГБ, сетевым адаптером: 10/100/1000 Мб/с.

Процессор: ATHLON-64 X2 4200+ - является суперскалярным, содержит 3 декодера команд, теоретически позволяющих достичь пиковой производительности до 3-х операций за 1 такт в каждом ядре. Таким образом, для данного процессора, имеющего в своём составе 2 ядра и работающего на частоте 2.2 ГГц теоретический предел производительности составляет 3х2х2.2=13.2 GFlops. В данную кластерную систему входи всего 9 компьютеров, значит теоретически предел всего кластера равен 13.2х9=118.8 GFlops.

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

Старая конфигурация программного обеспечения:

· Операционная система: Ubuntu Linux v.8.10

· Механизм коммуникации: внутренние механизмы связи PVM, основанные на стандартном транспортном протоколе.

· Интерфейс управления кластером: консоль PVM 3.4.2, GNU bash, version 3.2.48.

· Компилятор: GCC (GNU Compiler Collection) v.4.3.

Установка и настройка новой конфигурации программного обеспечения кластера.

1) Переустановка операционной системы.

Старая операционная система была заменена на более новую Ubuntu 9.10, с более новым ядром.

2) Установка и настройка PVM.

PVM версии 3.4.5. была скачана с официального сайта: http://www.netlib.org/pvm3/index.html. Распаковав скачанный архив в домашнюю папку пользователя (~/pvm3/). В конфигурационный файл командного интерпретатора bash (/etc/bash.bashrc) добавлены следующие строчки:

#pvm configuration

export PVM_ROOT=/home/root/pvm3

if [ -z $PVM_ROOT ]; then

if [ -d ~/pvm3 ]; then

export PVM_ROOT=~/pvm3

else

echo "Warning - PVM_ROOT not defined"

echo "To use PVM, define PVM_ROOT and rerun your .bashrc"

fi

fi

if [ -n $PVM_ROOT ]; then

export PVM_ARCH=`$PVM_ROOT/lib/pvmgetarch`

export PATH=$PATH:$PVM_ROOT/lib/$PVM_ARCH # arch-specific

export PATH=$PATH:$PVM_ROOT/bin/$PVM_ARCH

fi

export PVM_PATH=$PVM_ROOT/bin/$PVM_ARCH

export PVM_DPATH=pvm3/lib/pvmd

export PVMHOSTFILE=/home/root2/.rhosts

В системе установлен SSH. Для коммуникаций, PVM использует RSH или SSH, по умолчанию в файле конфигурационном файле для каждой операционной системы в PVM (например, для Linux 64-bit: ~/pvm3/conf/LINUX64.def), стоит RSH, но лучше использовать SSH. Для этого в этом файле нужно прописать значение переменной ARCHCFLAGS, параметр RSHCOMMAND должен содержать путь к команде SSH, например DRSHCOMMAND =\"/ usr / bin / ssh \" .

В каталоге /pvm3 выполняем команду для сборки и установки:

make

По окончании ее работы PVM будет готова к использованию. (На одном из этапов выполнения, команда завершилась выходом с ошибкой из-за отсутствия библиотеки m4_1.4.13-2_amd64 , которая необходимо было скачать через sudo apt - get install m4 из интернета.)

На этом процесс установки и настройки PVM завершен. Для удобства работы, данная конфигурация была скопирована на все узлы кластера.

Следующие действия проводились только на главном узле кластера .

Выполнена процедура создания беспарольного доступа пользователя root2 с консоли кластера на узлы кластера по протоколу SSH. Беспарольный доступ обеспечит более комфортную работу в PVM. Так, отпадет необходимость вводить пароли доступа при добавлении каждого нового узла и при копировании исполняемых модулей в локальные файловые системы узлов кластера. Алгоритм обеспечения беспарольного доступа следующий:

а) Логинимся к консоли кластера: ssh root2@server

б) Переходим в каталог ssh: cd ~/.ssh

в) Генерируем rsa-ключи: ssh-keygen -t rsa

г) На вопрос задать имя файла жмем Enter - остается имя по умолчанию id_rsa.

д) На просьбу задать пароль жмем Enter два раза (второй раз для проверки).

е) Копируем публичный ключ на узел кластера: scp id_rsa.pub

ж) root2@phys1:~/.ssh

з) Логинимся к узлу phys1: ssh root2@phys1

и) Переходим в каталог ssh: cd ~/.ssh

к) Копируем публичный ключ: cat id_rsa.pub >> authorized_keys2

л) Отключаемся от узла phys1

м) Повторяем пункты 6-10 для остальных узлов кластера (phys2 ... physN).

После проведения вышеописанной процедуры пользователь "root2" сможет подключаться к узлам кластера с консоли кластера, не вводя свой пароль. Следует отметить, таким образом, обеспечивается беспарольный доступ только для одного пользователя и только в одном направлении: консоль кластера -> узлы кластера. И только для случая, когда root2 подключается к узлам кластера под своим именем.

Также был установлен CSSH , для более комфортного управления всеми узлами кластера.

Для автоматического подключения узлов кластера в PVM в файле ~.rhosts были указаны имена всех хостов, которые должны входить в кластер и подключаться автоматически при старте PVM. В данном файле они указываются по принципу одно имя хоста - одна строчка, также в этом же файле можно указать дополнительные особенности конфигурации PVM на узлах кластера, за более подробным описанием данного файла рекомендуется обратиться к руководству PVM.

Для автоматической проверки конфигурации кластера в файл ~.pvmrc была введена команда conf. Данный файл PVM считывает построчно при запуске и исполняет все команды стоящие каждой строке, если она не начинается с символа комментария(#).

3) Установка и настройка XPVM.

Установка графической консоли проводилась только на главном узле кластера командой: sudo apt-get install xpvm .

Для автоматической регистрации хостов в XPVM в файл ~.xpvm_host необходимо добавить также как и в файл .rhosts имена хостов по тому же принципу.

Таким образом, новая конфигурация программного обеспечения:

· Операционная система: Ubuntu Linux v. 9.10 kernel 2.6.31-14

· Механизм коммуникации: внутренние механизмы связи PVM, основанные на стандартном транспортном протоколе.

· Интерфейс управления кластером: консоль PVM 3.4.5, GNU bash, version 4.0.33(1), SSH, CSSH, XPVM 1.2.5 .

· Компилятор: GCC (GNU Compiler Collection) v. 4.1.1

Процесс компиляции собственного программного обеспечения для работы с PVM.

Для того, чтобы писать программы для исполнения в параллельной вычислительной машиной следует использовать стандартные вызовы библиотеки pvm3.h, необходимо указывать дополнительный набор ключей для осуществления процесса компиляции ПО. Компиляция ПО проводилась в Qt-creator. Дополнительный набор ключей указывался в *.pro файле проекта: QMAKE_LIBS += -lpvm3 -lrt .

Обязательным условием для гетерогенных установок является компиляция исходных кодов ПО для каждой системы в отдельности, в нашем случае LINUX64. Далее следует разослать на все узлы кластера исполняемый файл, т.е. скопировать его в каталог ~/pvm3/bin/LINUX64 на каждом узле.

1.1. Тестирование новой конфигурации вычислительной системы.

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

1.1.1. Нагрузочное тестирование сети.

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

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

Коэффициент Kp – не меняется при данном тестировании по отношению к предыдущему. Коэффициент Kt используется для анализа прироста производительности кластера с учетом новой конфигурации системы и новыми условиями работы тестовой программы. Под новыми условиями работы понимается следующее: в старой конфигурации кластера процессы на разных узлах кластера предавали сообщения друг другу обычным способом, через посредника – демон pvmd, в новой конфигурации кластера программа скомпилирована таким образом, чтобы механизм коммуникаций между задачами работал на прямую, минуя демон pvmd, т.е. каждая задача самостоятельно предает нужные данные другим задачам и соответственно делают также. Таким образом, достигается значительный выигрыш в производительности всей кластерной системы при расчете на ней сильно связанной задачи, требующей частой синхронизации процессов. Об этом свидетельствуют следующие факторы:

1) Скорость пересылки информации по сети увеличивается с 1,5 МБайт/с (10 Мбит/c) до 7,5 Мбайт/с (60 Мбит/с), данный показатель был зафиксирован в Системном мониторе Ubuntu, где отражается статистика загрузки сети.

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

Обычная связь процессов старая конфигурация

Количество процессов

Посылок по сети, B

Расчетов на узле, С

Время работы главного процесса (астрономическое),D

Суммарное процессорное время кластера, Е

Kp = log(C/B)

Kt1 = E/D

18

1,00E+00

1,00E+09

99,10054

1186,258957

9

11,97026

18

1,00E+01

1,00E+08

112,6868

1058,926276

7

9,397075

18

1,00E+02

1,00E+07

107,7564

1038,060469

5

9,633397

18

1,00E+03

1,00E+06

113,0704

1033,268205

3

9,13827

18

1,00E+04

1,00E+05

144,8674

1038,608148

1

7,16937

18

1,00E+05

1,00E+04

341,0926

1115,252644

-1

3,269648

18

1,00E+06

1,00E+03

1592,878

1791,672389

-3

1,124802

18

1,00E+07

1,00E+02

14682,29

8547,911557

-5

0,582192

18

1,00E+08

1,00E+01

144365,1

74368,11773

-7

0,515139

Прямая связь процессов новая конфигурация

Количество процессов

Посылок по сети, B

Расчетов на узле, С

Время работы главного процесса (астрономическое),D

Суммарное процессорное время кластера, Е

Kp = log(C/B)

Kt2 = E/D

18

1

1000000000

119,7327823

1107,298489

9

9,248081

18

10

100000000

139,0967096

1058,176217

7

7,607486

18

100

10000000

127,1325296

1018,450738

5

8,010937

18

1000

1000000

147,4517699

1092,258965

3

7,407568

18

10000

100000

212,6682274

1212,215327

1

5,70003

18

100000

10000

387,8083071

1385,465934

-1

3,572554

18

1000000

1000

1702,352634

3398,62797

-3

1,99643

18

10000000

100

15483,53345

22804,68602

-5

1,472835

18

100000000

10

114135,2611

165196,0456

-7

1,447371


Обобщение результатов таблинчых значений:

Количество процессов

Посылок по сети, B

Расчетов на узле, С

Kt2/Kt1

Динамика Kt, %

1

18

1

1000000000

77%

-23

2

18

10

100000000

81%

-19

3

18

100

10000000

83%

-17

4

18

1000

1000000

81%

-19

5

18

10000

100000

80%

-20

6

18

100000

10000

109%

9

7

18

1000000

1000

177%

77

8

18

10000000

100

253%

153

9

18

100000000

10

281%

181

Из диаграммы видно, что при значении посылок сообщений по сети больше 100 тысяч, наблюдается значительный прирост коэффициента Kt. Таким образом , за счет прямой коммуникации задач в PVM эффективность кластерной системы возрастает при очень высокой связности вычислений. Небольшой снижение в динамике коэффициента Kt при малом количестве посылок по сети связано с тем, что время, затраченное на отправку сообщения: инициализация буфера передачи, упаковка сообщения, отсылка – приплюсовывается ко времени счета данной задачи, так как она сама выполняет эти действия, в то время как при старой конфигурации кластера эти действия за нее выполнял демон. Если оценивать такой показатель, как Астрономическое время работы главного процесс (D), то данный параметр также уменьшается при значительном увеличении количества посылок по сети, что видно из табличных значений. Также из них видно, что суммарное процессорное время кластера (Е) увеличивается при новой конфигурации, т.е. кластер считает дольше, но зато повышается эффективность его использования при сильно связанных вычислениях, так как значение коэффициента Kt стремится к значениям меньше 1 медленно, с ростом числа посылок по сети, по сравнению с предыдущей конфигурацией кластера, когда оно достигало их уже при миллионе пересылок по сети. Если значение коэффициента Kt становится меньшим 1, это говорит о том, что данную задачу затратно решать данным способом на кластере, так как скорость счета одной машины становиться больше скорости счета всей кластерной системы в целом, что видно из табличных значений старой конфигурации. Данный прирост производительности кластера не является предельным, зависит от коэффициента Kp, например, одном из тестирований он был равен log(100/10000) = -2 , то Kt возрос на 259% от старой конфигурации.

Графическая консоль XPVM .

Поначалу этого нагрузочного тестирования сети в работе использовалась графическая консоль (XPVM). Данная консоль содержит все те же самые наборы атрибутов и функций, что и обычна консоль PVM, только они представлены в графическом виде, в качестве кнопок и графиков.

Окно графической консоли разделено на две части. В верхней части сосредоточены кнопки управления кластером, а также наглядно представлена конфигурация кластерной системы в виде хостов. Когда они бездействуют, светятся белым, когда считают, зеленым. Нижняя часть она разделана на две взаимосвязанных части. Левая часть содержит номера TID запущенных задач, а правая иллюстрирует их поведение: пустая белая полоса задача запущена, зеленая - считается, красная – передает информацию, черные линии, отходящие от плоской задачи, свидельствуют об обмене информацией с другими задачами.

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

Иллюстрация графической консоли XPVM. (рис.4)

2.4.1 Тест имитационной модели метода Монте-Карло.

Имитационная модель метода Монте-Карло, широко применяющегося при решении задач математической физики. В качестве модельной задачи взяли последовательный алгоритм для нахождения числа Пи: случайным образом генерируем два числа из отрезка [0,1] — это координаты точки, проверяется, попадает ли эта точка в соответствующий сектор единичной окружности, если да — к счетчику прибавляется единица. Число Пи ищется как значение счетчика после проверки всех точек, умноженное на четыре и деленное на общее количество точек в опыте. Погрешность нахождения Пи уменьшается с ростом количества точек в опыте.

Данный алгоритм полностью подвергается распараллеливанию из-за того, что область данных можно разбить на не пересекающиеся отрезки, в него были добавлены те же изменения, что и в предыдущую программу нагрузочного тестирования сети. В опыте изменяется сразу две величины: первое - увеличивается количество точек, задействованных в эксперименте, с 106 до 1010 и второе - увеличивается количество расчетных процессов в кластере с 9 до 90.

Для оценки новой конфигурации кластера использовались два значения выводимые программой:

1) Среднее процессорное время кластера (Е).

Кол-во процессов

Общее количество точек на кластер

Среднее Проц-Время кластера Старое, E1

Среднее Проц-Время кластера Новое, Е2

E1-E2

9

1000000

0,068295269

0,068040326

0,00

18

1000000

0,068048359

0,070339206

0,00

27

1000000

0,069430465

0,071388097

0,00

36

1000000

0,071551692

0,073252535

0,00

45

1000000

0,073866028

0,074620868

0,00

54

1000000

0,075496824

0,075872485

0,00

63

1000000

0,077019329

0,077618713

0,00

72

1000000

0,07928147

0,078803145

0,00

81

1000000

0,079825395

0,080585617

0,00

90

1000000

0,081010961

0,081267964

0,00

9

10000000

0,661045693

0,647701333

0,01

18

10000000

0,675413639

0,673377255

0,00

27

10000000

0,67726336

0,656369116

0,02

36

10000000

0,69438044

0,645981136

0,05

45

10000000

0,702692726

0,671263983

0,03

54

10000000

0,704552913

0,680988712

0,02

63

10000000

0,721303162

0,674876851

0,05

72

10000000

0,72625546

0,683088815

0,04

81

10000000

0,733851275

0,685225308

0,05

90

10000000

0,737615887

0,687342186

0,05

9

100000000

6,139807484

5,950953849

0,19

18

100000000

6,181287627

6,03603047

0,15

27

100000000

6,212874967

5,999045691

0,21

45

100000000

6,216053396

6,067578798

0,15

63

100000000

6,134568011

6,073195363

0,06

Кол-во процессов

Общее количество точек на кластер

Среднее Проц-Время кластера Старое, E1

Среднее Проц-Время кластера Новое, Е2

E1-E2

72

100000000

6,17565295

6,053301312

0,12

81

100000000

6,214479306

6,058565829

0,16

90

100000000

6,230372889

6,07777647

0,15

9

1000000000

62,19087335

59,38107455

2,81

18

1000000000

62,29993233

59,23171841

3,07

27

1000000000

63,43304354

59,28884506

4,14

36

1000000000

62,11486847

59,19742158

2,92

45

1000000000

64,15349547

59,19926148

4,95

54

1000000000

63,90943245

59,21409718

4,70

63

1000000000

61,92625735

59,39892504

2,53

72

1000000000

63,87289228

59,29861706

4,57

81

1000000000

63,78063174

59,28395371

4,50

90

1000000000

61,7612

59,28268173

2,48

9

10000000000

611,8024851

592,4171916

19,39

18

10000000000

625,3053222

592,4245721

32,88

27

10000000000

639,5959873

595,1258813

44,47

36

10000000000

637,4668521

591,0551191

46,41

45

10000000000

641,7515958

595,0374052

46,71

54

10000000000

639,0328503

594,7466575

44,29

63

10000000000

641,5984646

595,4592241

46,14

72

10000000000

640,4067908

594,5784957

45,83

81

10000000000

647,1050188

595,1500482

51,95

90

10000000000

649,7285772

595,5870165

54,14

Из данной таблицы видно, что среднее процессорное время старой конфигурации кластера (Е1) больше, чем новой (E2), при любом числе запущенных процессов. Это проиллюстрировано на диаграммах (рис.5). Следует также отметить тот факт, что при количестве точек большем 1 миллиарда, число запущенных процессов практически не влияет на время счета задачи на кластерной системе , т.е. сколько бы мы процессов счета не запустили, время счета всей кластерной системы останется практически неизменным, а если увеличить число точек (увеличилось в 10 раз), то время счета увеличится во столько раз, во сколько увеличилось число точек (с 59 до 590), об этом свидетельствуют последние две диаграммы (рис.5), такой явной, прямой зависимости при тестировании предыдущей конфигурации не наблюдалось.

2) Среднее астрономическое время мастера (D), т.е. время работы главной задачи.

Множитель числа процессов

Среднее Астро время мастера старое, D1

Среднее Астро время мастера старое, D2

Динамика D2/D1, %

1

0,022743768

0,032634701

43,49

2

0,019742664

0,03169092

60,52

3

0,021301948

0,034691644

62,86

4

0,024832952

0,040115372

61,54

5

0,028491408

0,045345944

59,16

6

0,029647164

0,051315045

73,09

7

0,033450504

0,05683616

69,91

8

0,036737372

0,063799631

73,66

9

0,042951404

0,068065941

58,47

10

0,043405036

0,075527723

74,01

1

0,103664444

0,202463692

95,31

2

0,11484904

0,165041815

43,70

3

0,127870064

0,159635056

24,84

4

0,134409268

0,164022045

22,03

5

0,12639482

0,17818776

40,98

6

0,116823392

0,180488963

54,50

7

0,130211992

0,173872781

33,53

8

0,12740668

0,18057806

41,73

9

0,140798348

0,175055627

24,33

10

0,142984988

0,176062221

23,13

1

0,700494568

0,88411162

26,21

2

0,547940688

0,675269863

23,24

3

0,5114647

0,611737833

19,61

4

0,488551472

0,54348774

11,24

5

0,518046152

0,584736824

12,87

6

0,551513784

0,535651952

-2,88

7

0,575195352

0,550129908

-4,36

8

0,610063008

0,549478912

-9,93

9

0,592967288

0,5678019

-4,24

10

0,564720308

0,539328296

-4,50

1

7,264334296

8,459022909

16,45

2

5,388554972

6,425114483

19,24

3

4,501883604

5,537003825

22,99

4

4,138298968

4,9413291

19,40

5

3,92861094

4,767840401

21,36

6

3,843623388

4,602281532

19,74

7

3,829017744

4,507728879

17,73

Множитель числа процессов

Среднее Астро время мастера старое, D1

Среднее Астро время мастера старое, D2

Динамика D2/D1, %

8

3,793960948

4,397511392

15,91

10

3,69318834

4,190045288

13,45

1

89,95403528

75,49142178

-16,08

2

46,51671818

57,16418391

22,89

3

48,92022383

51,29661245

4,86

4

46,58261083

47,41044204

1,78

5

47,46935875

50,82233079

7,06

6

47,406562

45,80383927

-3,38

7

48,7799673

43,59741354

-10,62

8

47,51148996

42,6926881

-10,14

9

48,393231

42,1579862

-12,88

10

47,43611276

41,95229874

-11,56

Данный показатель имеет значения хуже, чем в старой конфигурации, но стремится к ее значениям с ростом количества точек участвующих в расчетах (рис.6,7), т.е. данный показатель можно считать практически неизменившимся, если брать в расчет количество точек равное 108 , 109 , 1010 .

Динамика среднего астрономического времени работы главной задачи (рис.6).

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

Заключение.

В ходе работы были изучены основные принципы построения распределенных вычислительных систем (HPC), оптимизирована работа параллельной виртуальной машины PVM на базе компьютеризированной лаборатории физического факультета: установлено новое программное обеспечение, изучен интерфейс и принципы работы графической консоли XPVM, дана оценка сферы ее применимости, оптимизирован алгоритм тестовых программ, повышены показатели производительности кластерной системы. Поставленные цели и задачи курсовой работы достигнуты.

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

1. PVM User’s Guide: http://www.netlib.org

2. Онлайн энциклопедия: http://ru.wikipedia.org/

3. Linux кластер – практическое руководство: http://cluster.linux-ekb.info/

4. Илья Евсеев - Использование PVM. Введение в программирование: http://www.cluster.bsu.by

5. Программа СКИФ союзного государства. PVM - параллельная виртуальная машина : http://www.skif.bas-net.by

6. Балуев А.Н. Перевод документации по PVM (мат-мех факультет СПбГУ): http://www.math.spbu.ru

7. Message Passing Toolkit: PVM Programmer's Manual: http://techpubs.sgi.com

8. Шпаковский Г.И., Серикова Н.В. Пособие по программированию матричных задач в MPI. - Минск: БГУ, - 2002. – 44 с.

Приложение.

Текст программы, использованной для нагрузочного тестирования сети:

//программа для нагрузочного тестирования запускается из консоли (кол-во посылок, решения)

#include <stdio.h>

#include <stdlib.h>

#include "pvm3.h"

#include "math.h"

#include <time.h>

//идентификаторы

#define msgtype_argv 0

#define msgtype_master_data 1

#define msgtype_slave_data 2

#define msgtype_slave_time 3

double x[2]; //массив для хранения решений кв.ур-ия

double timespecDiff(struct timespec *timeA_p, struct timespec *timeB_p)

{

return ((double)(timeA_p->tv_sec) + ((double)(timeA_p->tv_nsec))/1000000000)-((double)(timeB_p->tv_sec) + ((double)(timeB_p->tv_nsec))/1000000000);

}

int main(int argc, char *argv[])

{

int mytid; //переменная для иденификации основного процесс

int tids[100]; //массив значений tids для запущенных задач

long int N/*кол-во повторов решения на узле*/, i, j, k, np/*кол-во посылок по сети*/;

int nslaves/*число запущенныйх задач*/, nhosts/*количество хостов*/, narch/*количество различных форматов данных*/, master;

void raschet(double a, double b, double c); //к решению квадратного ураванения(коэффициенты a,b,c)))

double total_time_cpu_c=0; //общее время процессора

double time_cpu_master_c=0; //общее время работы процессора на локальных узлах

double time_global_master_l=0; //число тактов процессора на решение задачи

double time_slave_ci=0; //время работы процессора на локальном узле

struct pvmhostinfo *hostp; //При возврате, каждая структура pvmhostinfo содержит TID pvmd, имя хоста, имя архитектуры и относительную характеристику скорости процессора для определенного хоста в конфигурации

struct timespec start_c, start_l, end_l, end_c, start_ci, end_ci;

clock_gettime(CLOCK_MONOTONIC, &start_l); //старт точного измерения тактов процессора

clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start_c); //старт счета процессорного времени на решение задачи

mytid = pvm_mytid(); //регистрирует процесс в PVM, возвращает TID текущего процесса

pvm_setopt(PvmRoute, PvmRouteDirect); //``включение'' прямолинейной маршрутизации между задачами PVM

pvm_setopt(PvmFragSize,16384); //установить размер буфера передачи для сообщения

//pvm_setopt(PvmFragSize,65536); // субъективный параметр на скорость передачи не влияет

//pvm_setopt(PvmFragSize,114688); //хуже

//pvm_setopt(PvmFragSize,163840); //

//pvm_catchout(stdout); // для вывода на экран информации от подзадач

//pvm_setopt(PvmOutputTid,0);

//инициализация генератора псевдослучайных чисел

srand((unsigned)time(NULL)); //time() возвращает текущее время в сек

long double a, b, c; //переменные под коэффициенты кв.ур-ия

//определение местоположения для выполнения соответствующей части задачи.

//pvm_parent() - вернет TID задачи, которая породила задачу, сделавшую вызов

if(pvm_parent() == PvmNoParent) //если выполница, то это задача - главная порождающая остальные

{

//1 часть программы для главного узла

pvm_config( &nhosts, &narch, &hostp ); //возвращает информацию о виртуальной машине, включая количество хостов - nhost - и количество различных форматов данных - narch

//printf("%s \n",argv[0]);

/*&hostp - это указатель на декларированный пользователем массив из структур pvmhostinfo.

Размер массива должен быть длиной, по крайней мере, соответствующей nhosts.*/

//считывает число посылок по сети

sscanf(argv[1],"%lu",&np); //читает данные из argv[1], преобразовывая символы к значениям указателей на long unsigned int, в переменную np

//считывает число решений на одном узле

sscanf(argv[2],"%lu",&N); //

nslaves = 2*nhosts -1; //число запусков задач(2*число хостов-1)

printf("%d \t", nslaves+1); //печатаеть в stdout целочисленные десятичные наборы сиволы через таб длинной nslaves+1

printf("%lu\t%lu\t",np,N); //печатаеть в stdout long unsigned int наборы сиволы через tab и tab из преременных np и N

nslaves=pvm_spawn(&argv[0][0], (char**)0, 0, "", nslaves, tids); //ф-ция,которая запускает в PVM nslaves копий исполняемого файла с именем "argv[0][29]" с одинаковыми аргументами командной строки (char**)0 , на компьютере который выберет сама.

//отсылка

pvm_initsend(PvmDataInPlace); //инициализация буфера для отправки сообщения

pvm_pklong(&N, 1, 1); //упаковка в передающий буфер данных массива N длинной 1 с числом элементов 1 в одном эл-те массива

pvm_pklong(&np, 1, 1);

pvm_mcast(tids, nslaves, msgtype_argv); //присваевает сообщению идентификатор msgtype_argv и широковещательно посылает его задачам, идентификаторы которых перечислены в nslaves элементах массива tids

//цыклы для посылки по рассылки

for(j = 0; j < np; j++)

{

//задаем коэффициенты через rand

for(i = 0; i < nslaves; i++)

{

a = ((long double) rand() /((long double)RAND_MAX+1.0));

b = ((long double) rand() /((long double)RAND_MAX+1.0));

c = ((long double) rand() /((long double)RAND_MAX+1.0));

pvm_initsend(PvmDataInPlace); //инициализация буфера пересылки

pvm_pklong((long int *)(&a), 2, 1); //упаковка созданного коэф-та а

pvm_pklong((long int *)(&b), 2, 1); //упаковка созданного коэф-та b

pvm_pklong((long int *)(&c), 2, 1); //упаковка созданного коэф-та c

//отсылка коэф-тов на другие узлы для решения кв. ур-ия

pvm_send(tids[i], msgtype_master_data); //присваивает сообщению идентификатор msgtype_master_data и посылает сообщение задаче с идентификатором tids[i], т.е. всем что есть в массиве

}

//создание коэф-тов для решения ур-ия на этом узле

a = ((long double) rand() /((long double)RAND_MAX+1.0));

b = ((long double) rand() /((long double)RAND_MAX+1.0));

c = ((long double) rand() /((long double)RAND_MAX+1.0));

//решает кв.ур-ие с одними и теми же а,b,c на главном узле

for(k = 0; k < N; k++)

{

raschet(a, b, c); //посылает к решению кв.ур-ия

}

//получение решений с локальных узлов

for(i = 0; i < nslaves; i++)

{

pvm_recv(-1, msgtype_slave_data); //получение решения с друго узла

pvm_upkdouble(x , 2, 1 ); //распаковка полученного решения

}

}

//сумматор времени процессора, затр. на решение зад. на кластере

for(i = 0; i < nslaves; i++)

{

pvm_recv( -1, msgtype_slave_time); //ожидает сообщения с иденификатором msgtype_slave_time от задачи с идентификатором -1

pvm_upkdouble(&time_slave_ci, 1, 1); //распакует принятые данные из массива с указателем &time_slave_ci длинной 1 с 1 элементом указанного типа в одном элементе массива

//общее время решения ур-ия на всех локальных узлах кластера

time_cpu_master_c += time_slave_ci; //суммирует время решения задачи на других машинах

}

clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end_c); //окончание счета процессорного времени на решение задачи

clock_gettime(CLOCK_MONOTONIC, &end_l); //конец точного измерения тактов процессора

//общее процессорное время решения задачи на кластере

total_time_cpu_c = timespecDiff(&end_c, &start_c) + time_cpu_master_c; //сумма времен затраченных на решение задачи на кластере

time_global_master_l = timespecDiff(&end_l, &start_l); //сумма тактов процессора на решение задачи на главной машине

//печать в stdout общего процессорного времени решения задачи на всем кластере и тактов процессора на главной машине.

printf("%20.9f\t%20.9f\n", time_global_master_l, total_time_cpu_c);

}

//2 часть программы для локального узла

else

{

mytid = pvm_mytid(); //регистрирует процесс в PVM, возвращает TID текущего процесса

clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start_ci); //начало отсчета времени работы процессора

master = pvm_parent(); //узнает идентификатор родительской задачи

pvm_recv(master, msgtype_argv); //ожидает поступления сообщения с идентификатором msgtype_argv от задачи с идентификатором master

pvm_upklong(&N, 1, 1); //распаковка N

pvm_upklong(&np, 1, 1); //распаковка np

for(j = 0; j < np; j++)

{

pvm_recv(master, msgtype_master_data); //ожидает поступления сообщения с идентификатором msgtype_master_data от задачи с идентификатором master

pvm_upklong((long int *)(&a), 2, 1); //распаковка

pvm_upklong((long int *)(&b), 2, 1); //распаковка

pvm_upklong((long int *)(&c), 2, 1); //распаковка

for(k = 0; k < N; k++)

{

raschet(a, b, c); //посылает к решению кв.ур-ия

}

pvm_initsend(PvmDataInPlace); //инициализация буфера пересылки без кодировки для отправки решения

pvm_pkdouble(x, 2, 1); //упаковка решения кв.ур-ия

//отсылка решений на главный узел

pvm_send(master, msgtype_slave_data); //присваивает сообщению идентификатор msgtype_slave_data и посылает сообщение задаче с идентификатором master

}

clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end_ci); //конец отсчета времени работы процессора

time_slave_ci = timespecDiff(&end_ci, &start_ci); //время работы процессора на локальном узле

pvm_initsend(PvmDataInPlace); //инициализация буфера пересылки без кодировки

pvm_pkdouble(&time_slave_ci, 1, 1); //упаковка

//отсылка времени работы процессора на решение ур-ия на локальном узле

pvm_send(master, msgtype_slave_time); //присваивает сообщению идентификатор msgtype_slave_time и посылает сообщение задаче с идентификатором master

}

pvm_exit(); //завершение пользование услугами PVM

return 0;

}

//алгоритм решения квадратного уравнения, коэффициентами которого являются случайные вещественные числа

void raschet(double a, double b, double c)

{

double D;

D = b*b - 4*a*c;

if(D == 0)

{

x[0] = x[1] = -b/(a);

}

if(D < 0.)

{

double t = 1/(2.*a);

x[0] = -b*t; x[1] = sqrt(-1*D)*t;

}

if(D > 0.)

{

x[0] = (-b + sqrt(D))/(a*2.); x[1] = (-b - sqrt(D))/(a*2.);

}

}

Текст программы, для имитационной модели метода Монте-Карло:

//вывод число хостов, число задач запущенных, второй аргумент, первый аргумент,

#include <stdio.h>

#include <stdlib.h>

#include <stdint.h>

#include <pvm3.h>

#include <math.h>

#include <time.h>

double timespecDiff(struct timespec *timeA_p, struct timespec *timeB_p)

{

return ((double)(timeA_p->tv_sec) + ((double)(timeA_p->tv_nsec))/1000000000) -

((double)(timeB_p->tv_sec) + ((double)(timeB_p->tv_nsec))/1000000000);

}

int main(int argc, char *argv[])

{

int mytid; /* my task id */

int tids[100]; /* slave task ids */

int nslaves, i, msgtype, nhosts, narch, master;

/*unsigned*/ long int N, S, Si, nN, nH, np;

long double Pi;

long double PiTrue = 4.0 * ((long double)atan(1.0));

long int mk(unsigned long int);

double hostcputime, /*hostlocaltime,*/ timeElapsed_ci, /*timeElapsed_li,*/ timeElapsed_c, timeElapsed_l;

struct pvmhostinfo *hostp;

struct timespec start_c, start_l, end_l, end_c, start_ci,/* start_li, end_li,*/ end_ci;

clock_gettime(CLOCK_MONOTONIC, &start_l);

clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start_c);

mytid = pvm_mytid();/*tid master*/

pvm_setopt(PvmRoute, PvmRouteDirect);//``включение'' прямолинейной маршрутизации между задачами PVM

srand((unsigned)time(NULL));

if(pvm_parent() == PvmNoParent)

{

pvm_config( &nhosts, &narch, &hostp );

sscanf(argv[2],"%lu",&np);

sscanf(argv[1],"%lu",&N);

nslaves = np * nhosts - 1;

//число хостов, число задач запущенных на хосте, второй аргумент, первый аргумент

printf("%d\t%d\t%lu\t%lu\t", nhosts, (nslaves+1), np, N);

nslaves=pvm_spawn(&argv[0][0], (char**)0, 0, "", nslaves, tids);

nN = N / (nslaves + 1);

nH = N - nslaves * nN;

//nH, nN,

printf("%ld\t%ld\t", nH, nN);

pvm_initsend(PvmDataInPlace);

pvm_pklong(&nN, 1, 1);

pvm_mcast(tids, nslaves, 0);

S = mk(nH);

msgtype = 1;

for( i=0 ; i<nslaves ; i++ )

{

pvm_recv( -1, msgtype );

pvm_upklong( &Si, 1, 1 );

pvm_upkdouble(&timeElapsed_ci, 1, 1);

//pvm_upkdouble(&timeElapsed_li, 1, 1);

S += Si;

hostcputime += timeElapsed_ci;

//hostlocaltime += timeElapsed_li;

}

Pi = 4.0 * ((long double)S) / ((long double)N);

clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end_c);

clock_gettime(CLOCK_MONOTONIC, &end_l);

timeElapsed_c = timespecDiff(&end_c, &start_c);

timeElapsed_l = timespecDiff(&end_l, &start_l);

//расчетное значение ПИ, погрешность вычисления

printf("%20.18Lf\t%7.1Le\t",Pi,((long double)fabs(Pi-PiTrue)));

//время астронамическое, время процессорное

printf("%20.9f\t%20.9f\n", timeElapsed_l, (timeElapsed_c + hostcputime));

}

else

{

clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start_ci);

msgtype = 0;

pvm_recv( -1, msgtype );

pvm_upklong(&nN, 1, 1);

Si = mk(nN);

clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end_ci);

timeElapsed_ci = timespecDiff(&end_ci, &start_ci);

pvm_initsend(PvmDataInPlace);

pvm_pklong(&Si, 1, 1);

pvm_pkdouble(&timeElapsed_ci, 1, 1);

//pvm_pkdouble(&timeElapsed_li, 1, 1);

msgtype = 1;

master = pvm_parent();

pvm_send( master, msgtype );

}

pvm_exit();

}

long int mk(unsigned long int n)

{

unsigned long int i;

long int Sum;

long double x, y;

for(i = 0, Sum = 0; i < n; i++)

{

x = ((long double) rand() /((long double)RAND_MAX+1.0));

y = ((long double) rand() /((long double)RAND_MAX+1.0));

if( (x*x + y*y) <= 1.0) Sum++;

}

return Sum;}

Оценить/Добавить комментарий
Имя
Оценка

Работы, похожие на Реферат: «Оптимизация кластерной системы на базе pvm компьютерной лаборатории физического факультета»

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(222519)
Комментарии (3006)
Copyright © 2005-2019 BestReferat.ru bestreferat@gmail.com реклама на сайте

Рейтинг@Mail.ru