Ж у р н а л   о   к о м п ь ю т е р н ы х   с е т я х   и   т е л е к о м м у н и к а ц и о н н ы х   т е х н о л о г и я х
СЕТИ И СИСТЕМЫ СВЯЗИ on-line
  ПОИСК: ПОДПИСКА НА НОВОСТИ: НОМЕР:
    ДОМОЙ • Архив: Новостей | Конференций | НомеровПодписка
 
   
 
   
    
РЕДАКЦИЯ
 
Все о журнале
Подписка
Как проехать
Где купить
Отдел рекламы
График выхода журнала
Адреса в Интернет

РУБРИКАТОР
   
• Инфраструктура
• Информационные
   системы

• Сети связи
• Защита данных
• Кабельные системы
• Бизнес
• Колонка редактора
• Электронная
   коммерция

• Только на сервере
• Системы
   учрежденческой
   связи

• Новые продукты


Rambler's Top100

  

Параллельные миры

Андрей Кузнецов

С момента появления первых вычислительных устройств, их создатели пытались усовершенствовать свои творения, в частности, повысить их эффективность за счет увеличения производительности или изобрести новые устройства, более совершенные. Более трехсот лет прошло с изобретения логарифмической линейки (1662 г., Уильям Оустред), первых механических “калькуляторов” и счетных машин (1624 г., Вильгельм Шикард и 1642 г. ,Блез Паскаль). Нынешний век – век компьютеров. Для решения той же задачи, что и сотни лет назад, задачи повышения быстродействия применяется множество путей. Одна из них – это параллельные вычисления.

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

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

Предположим, что в вашей программе доля операций, которые нужно выполнять последовательно, равна f, где 0<=f<=1 (при этом доля понимается не по статическому числу строк кода, а по числу операций в процессе выполнения). Крайние случаи в значениях f соответствуют полностью параллельным (f=0) и полностью последовательным (f=1) программам. Так вот, для того, чтобы оценить, какое ускорение S может быть получено на компьютере из 'p' процессоров при данном значении f, можно воспользоваться законом Амдала:

          1
S <= -----------
      f+(1-f)/p

Если 9/10 программы исполняется параллельно, а 1/10 по-прежнему последовательно, то ускорения более, чем в 10 раз получить в принципе невозможно вне зависимости от качества реализации параллельной части кода и числа используемых процессоров (ясно, что 10 получается только в том случае, когда время исполнения параллельной части равно 0). [3]

Таблица 1. Теоретическое увеличение производительности

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

Соотношение параллельного и последовательного кода

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

2

1.82

1.67

1.54

1.42

1.33

1.25

1.18

1.11

1.05

4

3.08

2.5

2.1

1.82

1.6

1.42

1.29

1.18

1.08

8

4.71

3.33

2.58

2.11

1.77

1.53

1.35

1.21

1.1

12

5.71

3.75

2.79

2.22

1.84

1.58

1.38

1.22

1.1

16

6.4

4.0

2.91

2.29

1.88

1.6

1.39

1.23

1.1

24

7.27

4.29

3.04

2.35

1.92

1.62

1.4

1.24

1.11

32

7.8

4.44

3.1

2.39

1.94

1.63

1.41

1.24

1.11

64

8.77

4.71

3.22

2.44

1.97

1.65

1.42

1.25

1.11

128

9.34

4.85

3.27

2.47

1.98

1.65

1.42

1.25

1.11

 

Посмотрим на проблему с другой стороны. Как за максимальное время перевезти на повозке с лошадью поклажу из пункта A в пункт B? Вместо одной лошади запрячь пару, правда скорость не увеличится в два раза. Если запрячь тройку, то можно еще немножечко выиграть. Но дальше увеличивать количество лошадей бесполезно, скорость не возрастет. Можно несколько модифицировать пример. Вместо увеличения количества лошадей в одной повозке, увеличим количество повозок. Однако несколько повозок на одной дороге могут (и будут!) мешать друг другу. Так же происходит и в компьютере. Если с решением определенной задачи справляется один процессор за определенное время, то совсем не обязательно, что N-процессорная система решит ее быстрее, а тем более в N раз быстрее. Необходимы накладные расходы на взаимодействие процессоров в рамках системы, параллельных процессов друг с другом и пр.

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

Целесообразность применения и примеры использования HPC систем.

Какие же задачи предъявляют высокие требования к производительности систем и почему самые обыкновенные PC, по производительности сравнимые с суперкомпьютерами прошлых десятилетий, не могут справиться с этими задачами? Вот только небольшой список отраслей, в которых не обойтись без использования HPC (High Performance Computing):

    • автомобилестроение
    • авиационная промышленность
    • атомная промышленность
    • космические исследования
    • разведка нефти и газа
    • фармакология
    • прогноз погоды
    • сейсмическая разведка
    • химическая промышленность
    • системы принятия решений

Госпиталь для детей (HSC), расположенный в Торонто (Канада), в январе-феврале 1999 года установил суперкомпьютер, который позволит специалистам-медикам значительно ускорить свои исследования в области детских болезней и их лечения. Данная 64-процессорная система Cray Origin2000 укомплектованная 16GB оперативной памяти и 1TB дискового пространства. Установленный суперкомпьютер будет использоваться, главным образом, для исследований в двух ключевых областях: быстрый поиск сходств в генетических последовательностях и построение трехмерных моделей человеческих протеинов.

Корпорация Sun Microsystems сообщила, что ее серверы серии Sun Enterprise, RAID-системы хранения данных StorEdge и ОС Solaris были выбраны в качестве основной платформы для создания новой интегрированной информационной системы (ILS, Integrated Library System) для библиотеки конгресса США. Система ILS будет использовать два сервера серии Sun Enterprise: 56-процессорный Enterprise 10000 (также известный как Starfire) с 30GB оперативной памяти и 8-процессорный Enterprise 3500, который будет служить в качестве Web-сервера, а также систему хранения данных StorEdge D1000.

Корпорация Silicon Graphics объявила о том, что Нью-Йоркская фондовая биржа (NYSE) установила шесть многопроцессорных систем Onyx2 (это специализированный суперкомпьютер для задач визуализации) в своем недавно переоборудованном операционном центре. Система, программное обеспечение для которой было разработано Securities Industry Automation Corp., позволяет пользователям получать ясное изображение всех финансовых потоков и сложных деловых транзакций, протекающих на бирже. Это, в свою очередь, революционным образом отразится на эффективности и качестве работы всех участников фондового рынка.

Для того, чтобы оценить сложность решаемых на практике задач, возьмем конкретную предметную область, например, оптимизацию процесса добычи нефти. Имеем подземный нефтяной резервуар с каким-то числом пробуренных скважин. По одним на поверхность откачивается нефть, по другим обратно закачивается вода. Нужно смоделировать ситуацию в данном резервуаре, чтобы оценить запасы нефти или понять необходимость в дополнительных скважинах. Примем упрощенную схему, при которой моделируемая область отображается в куб, однако и ее будет достаточно для оценки числа необходимых арифметических операций. Разумные размеры куба, при которых можно получать правдоподобные результаты - это 100*100*100 точек. В каждой точке куба надо вычислить от 5 до 20 функций: три компоненты скорости, давление, температуру, концентрацию компонент (вода, газ и нефть - это минимальный набор компонент, в более реалистичных моделях рассматривают, например, различные фракции нефти). Далее, значения функций находятся как решение нелинейных уравнений, что требует от 200 до 1000 арифметических операций. И наконец, если исследуется нестационарный процесс, т.е. нужно понять, как эта система ведет себя во времени, то делается 100-1000 шагов по времени. Что получилось:

106(точек сетки)*10(функций)*500(операций)*500(шагов по времени) = 2.5*1012

2500 миллиардов арифметических операций для выполнения одного лишь расчета! А изменение параметров модели? А отслеживание текущей ситуации при изменении входных данных? Подобные расчеты необходимо делать много раз, что накладывает очень жесткие требования на производительность используемых вычислительных систем. [3]

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

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

Все компании, производящие параллельные системы и множество независимых производителей уделяют особое внимание проблемам HPC в плане разработки программных средств и компиляторов для параллельного программирования. Существуют различные варианты специализированных параллельных языков (Ada, DVM-система и др.), расширений существующих языков программирования (Cray MMP Fortran, HPF, Compositional C++ и др.), коммуникационные интерфейсы (MPI, PVM, OpenMP и др.) и многое другое.

Программная реализация параллельных приложений.

Из вышесказанного вытекает логический вывод: при реализации решения HPC приложения необходимы, кроме соответствующей техники, параллельные языки программирования, средства анализа производительности, средства автоматического распараллеливания, инструментальные системы и коммуникационные интерфейсы для построения распределенных приложений. Приложение в параллельной архитектуре (HPC кластер, SMP или cc-NUMA) должно создаваться с расчетом на эффективное использование ресурсов этой архитектуры. Под этим понимается то, что приложение должно быть “разделено” на части, способные исполняться параллельно на нескольких процессорах, и разделено эффективно, чтобы отдельно исполняемые “куски" программы минимально влияли на исполнение остальных частей.

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

for (i=0, i<n, i++) a[i]=b[i] + c[i];

этот пример очень просто преобразовать с использованием элементов параллельного программирования:

for (i=0;i<5;i++) a[i]=b[i]+c[i];
for (j=5;j<10;j++) a[j]=b[j]+c[j];
for (k=10;k<15;k++) a[k]=b[k]+c[k];
...
...
for (l=n-5;l<n;l++) a[l]=b[l]+c[l];

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

Необходимо разделить понятия “конкурентность” и “параллельность”. Конкурентными называются такие участки программного кода, которые могут исполняться независимо друг от друга. Параллельными частями программы являются те же самые конкурентные части, но которые исполняются (или должны исполняться) одновременно на разных процессорах. Это важное замечание, поскольку “конкурентность” - это свойство программы, а параллелизм – свойство машины. Основным лимитирующим фактором в параллельной архитектуре является латентность (время инициации посылки сообщения) и скорость коммуникаций между вычислительными узлами. Несмотря на то, что в SMP системах доступ к памяти происходит гораздо быстрее, чем обмен сообщениями в HPC кластерах, латентность все равно присутствует. Многие бенчмарки, используемые для определения производительности параллельных систем, являются задачами с сильно развитым параллелизмом и коммуникации между параллельными вычислениями не являются в них узким местом. Но чаще всего реальные приложения не так просты как тесты и исполнение конкурентных участков кода в параллель при значительных затратах на взаимодействие может привести к уменьшению производительности. Иными словами, время взаимодействия должно уступать времени вычислений, иначе параллельное выполнение конкурентных частей программы будет неэффективным. Для достижения эффективной параллельной обработки необходимо добиться равномерной загрузки всех процессоров, иначе часть процессоров будет простаивать, ожидая окончания работы остальных, что может значительно снизить производительность.

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

  1. Возможностью использования параллельных алгоритмов в программе.
  2. Возможностью равномерно распределить вычислительную нагрузку по процессорам.
  3. Накладными расходами на управление параллелизмом.
  4. Коммуникациями.

Кратное описание наиболее популярных технологий.

С аппаратной точки зрения, для реализации параллельных систем могут быть применены две основные схемы. Первая – несколько отдельных систем, с локальной памятью и CPU, взаимодействующих в какой-либо среде посредством посылки сообщений. Вторая – системы, взаимодействующие через разделяемую память (SMP и cc-NUMA системы).

С программной точки зрения, есть так же два основных пути для реализации параллелизма. Это, опять же, обмен сообщениями между процессами и организация нитей (threads). Существуют и другие методы, но эти используются наиболее часто. Оба программных метода могут применяться как в SMP и сс-NUMA системах, так и в HPC кластерах.

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

Таблица 2. Messages и threads

 

Производительность на SMP системах

Производительность на HPC кластерах

Масштабируемость

Messages

Хорошая

Отличная

Отличная

Threads

Отличная

Удовлетворительная*

Удовлетворительная*

* требуется использование сс-NUMA(cache-coherent non-uniform memory architecture).

MPI (Message Passing interface).

Механизм для построения программ по модели обмена сообщениями. В данной программной модели вычисления производятся одним или несколькими процессами, обращающимися к специальным библиотечным функциям для посылки или получения сообщений. Существует множество реализаций MPI, как коммерческих, так и свободно распространяемых. Текущая версия стандарта 2.0.
См. www.mpi-forum.org

OpenMP.

OpenMP задуман как стандарт для написания программ на масштабируемых SMP-системах (SSMP, cc-NUMA и пр.) в модели общей памяти. OpenMP можно рассматривать как высокоуровневую надстройку над POSIX threads. OpenMP может быть использован для написания программ на C/C++ и Fortran. Программа, написанная с использованием OpenMP, на однопроцессорной платформе может исполняться как последовательная программа, т.е. нет необходимости поддерживать две версии, последовательную и параллельную.
См. www.openmp.org

Основные классы современных параллельных компьютеров.

Основным параметром классификации параллельных компьютеров является наличие общей (SMP) или распределенной памяти (MPP). Нечто среднее между SMP и MPP представляют собой NUMA-архитектуры, где память физически распределена, но логически общедоступна. Кластерные системы являются более дешевым вариантом MPP. Все большую популярность приобретают идеи комбинирования различных архитектур в одной системе и построения неоднородных систем.

Симметричные мультипроцессорные системы.

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

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

Массивно-параллельные системы.

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

Параллельно-векторные системы.

Основным признаком PVP-систем является наличие специальных векторно-конвейерных процессоров, в которых предусмотрены команды однотипной обработки векторов независимых данных, эффективно выполняющиеся на конвейерных функциональных устройствах. Как правило, несколько таких процессоров (1-16) работают одновременно над общей памятью (аналогично SMP) в рамках многопроцессорных конфигураций. Несколько таких узлов могут быть объединены с помощью коммутатора (аналогично MPP).

Системы с неоднородным доступом к памяти NUMA.

NUMA (nonuniform memory access) в отличие от привычной SMP архитектуры с разделяемой памятью представляет собой несколько отдельных процессоров, каждый из которых, кроме собственного кэша, обладает так же локальной памятью:

В подобной архитектуре процессор и модули памяти тесно интегрированы, следовательно, скорость доступа к локальной памяти гораздо выше, чем к памяти “соседнего” процессора. Подсистемы ввода-вывода могут быть частью каждого узла или консолидированы на выделенных узлах ввода-вывода. Если во всей системе поддерживается когерентность кэшей, то такую архитектуру называют cc-NUMA.

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

Кластерные системы представляют собой некоторое число недорогих рабочих станций или персональных компьютеров, объединенных в общую вычислительную сеть (подобно массивно-параллельным системам). Одним из примеров реализации кластерной HPC системы являетются кластеры Beowulf. Beowulf – это собственное имя первого кластера, созданного в GSFC (Goddard Space Flight Center), на основе компьютеров Intel архитектуры под ОС Linux. Проект Beowulf начался летом 1994 года в научно-космическом центре NASA. Первым кластером Beowulf была система, состоящая из 16 узлов (486DX4/100Mhz). В настоящее время термин Beowulf применяется ко всем аналогичным кластерным системам.

Кластер Beowulf состоит из нескольких отдельных узлов, объединенных в общую сеть. Оптимальным считается построение кластеров на базе двухпроцессорных компьютеров. Для уменьшения накладных расходов на взаимодействие между узлами применяют полнодуплексный 100 MB Fast Ethernet (реже используют SCI), создают несколько сетевых сегментов или соединяют узлы кластера через коммутатор. В качестве программного обеспечения применяют ОС Linux, бесплатные реализации MPI и пр.

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

Литература:

  1. Материалы NHSE (National HPCC Software Exchange), www.nhse.org
  2. Jacek Radajewski and Douglas Eadline "Beowulf HOWTO" v1.1.1, 22 November 1998
  3. Воеводин Вл.В. Курс лекций в Международном Университете г.Дубна.
  4. Воеводин Вл.В. “Суперкомпьютерная грань компьютерного мира”, www.parallel.ru/vvv/intro2hpc.html
  5. Материалы Информационно-аналитического центра по параллельным вычислениям www.parallel.ru
  6. Материалы Beowulf Project at CESDIS, www.beowulf.org


Android




  
8 '2000
СОДЕРЖАНИЕ

колонка редактора

• Тупую сеть интеллектом не испортишь

локальные сети

• Элегантные кабельные розетки пополняют ряды Категории 6

• Повышение гибкости кабельной проводки, или Вторая жизнь кабелепроводов

• Служба RIS Windows 2000: снижаем затраты на ИТ

услуги сетей связи

• Интервью с руководителем департамента радио, телевидения и спутниковой связи Министерства РФ по связи и информатизации Василием Илларионовичем Павловым

• Беспроводные коммуникации: взгляд Hewlett-Packard

• IP-телефония - это не только дешевая связь

• Беспроводные мосты соединяют

• Оптимизация решений для беспроводной IP-телефонии

• IP-телефония: "cветлое будущее" или..?

новые продукты

• SURPASS открывает новые горизонты перед операторами

только на сервере

• Snap Server 1000 впечатляет

• Проблемы интероперабельности решений на основе IPSec

• Параллельные миры

корпоративные сети

• Почему ваша сеть стала работать медленно? Откройте ей "второе дыхание". Часть 1

• Подключение карманных компьютеров к корпоративной сети

• Unix BSD: жизнь продолжается

защита данных

• Защита информации на предприятии

• Информационная защита сервера Windows NT

электронная коммерция

• XML достигает "совершеннолетия"

бизнес

• Мушкетеры отечественной промышленности: АПОС, СППОСС и РОСС

• Lucent объявляет о начале эры "Фотонной Долины"

• Новая стратегия Novell

• Дистрибуция конвергированных решений

системы учрежденческой связи

• Корабль телефонии меняет курс


• КАЛЕЙДОСКОП



 Copyright © 1997-2007 ООО "Сети и Системы Связи". Тел. (495) 234-53-21. Факс (495) 974-7110. вверх