Новости
О Центре
Кластер
Общее описание
Программная архитектура
Система управления кластером
Результаты вычислительных эксперементов
Обучение
Исследования
Конференции
Полезные ссылки
NVIDIA
Контакты
О сайте
Имя:
Пароль:
запомнить:
Забыли пароль? Регистрация

Результаты вычислительных эксперементов

5. Анализ эффективности параллельных алгоритмов

Наряду с технологической оптимизацией (выбор системного программного обеспечения, использование преимущества общей памяти, учет архитектурных особенностей процессоров), проблемы которой рассматривались в предыдущих разделах настоящего отчета, существенное влияние на эффективность вычислений оказывает выбор параллельного способа (алгоритма) решения задачи. В данном разделе проблема выбора параллельного алгоритма осуществляется на примере матричного умножения (см. раздел 2), принятого в качестве иллюстративного при изложении результатов вычислительных экспериментов. Для анализа и оценки эффективности выбраны широко используемые в практических приложениях три разных способа организации параллельных матричных вычислений (см, например, Kumar and etc.(1994)):

·      ленточный (striped) алгоритм (см. раздел 6);

·      блочный алгоритм Фокса (Fox's algorithm);

·      блочный алгоритм Кеннона (Cannon's algorithm).

Ленточный алгоритм требует меньшего количества обменов данными, чем блочные алгоритмы Фокса и Кеннона, но использует больший объем памяти для хранения данных.

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

5.1. Оценка эффективности алгоритмов

Целью этой серии экспериментов была оценка эффективности алгоритмов при разном числе вычислительных узлов типа (1х1.3). На рис. 5.1 и 5.2 представлены результаты при использовании двух и четырех рабочих станциях соответственно.

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

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

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

Рис 5.3. Результаты экспериментов, полученные при использовании алгоритма Кеннона

5.2. Масштабируемость алгоритмов

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

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

Рис 5.5. Результаты экспериментов, полученные при использовании алгоритма Фокса

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


<< вернуться  |   Документ от: 09.09.2005 11:52

Новости

22.10.2012
04.09.2012
05.04.2012
06.03.2012
02.03.2012