Способы организации параллельных вычислительных систем. Параллельные вычисления

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

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

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

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

1. Взаимодействие через разделяемую память (например, в Java или C#). Данный вид параллельного программирования обычно требует какой-то формы захвата управления для координации потоков между собой.

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

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

1. OpenMP используется в параллельных системах с общей памятью (например, современные компьютеры с многоядерными процессорами);

2. MPI (Message Passing Interface) является стандартом систем передачи сообщений между параллельно исполняемыми процессами, используется при разработке программ для суперкомпьютеров;

3. POSIX Threads является стандартом реализации потоков выполнения;

4. Операционная система Windows имеет встроенную поддержку многопоточных приложений для C++ на уровне API;

5. PVM (Parallel Virtual Machine) позволяет объединять разнородные связанные сетью компьютеры в общий вычислительный ресурс.

Системы на базе нескольких компьютеров относят к классу систем для распределенных вычислений. Подобные решения используются довольно давно. Наиболее яркий пример технологии распределенных вычислений - MPI (Message Passing Interface - интерфейс передачи сообщений). MPI является наиболее распространённым стандартом интерфейса обмена данными в параллельном программировании, существуют его реализации для огромнейшего числа компьютерных платформ. MPI предоставляет программисту единый механизм взаимодействия ветвей внутри параллельного приложения независимо от машинной архитектуры (однопроцессорные/многопроцессорные с общей/раздельной памятью), взаимного расположения ветвей (на одном процессоре или на разных).

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

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

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

OpenMP (Open Multi-Processing) - это набор директив компилятора, библиотечных процедур и переменных окружения, которые предназначены для программирования многопоточных приложений на многопроцессорных системах с общей памятью.

Разработку спецификации OpenMP ведут несколько крупных производителей вычислительной техники и программного обеспечения, чья работа регулируется некоммерческой организацией, называемой OpenMP Architecture Review Board (ARB).

Первая версия появилась в 1997 году, предназначалась для языка Fortran. Для С/С++ версия разработана в 1998 году. В 2008 году вышла версия OpenMP 3.0. Интерфейс OpenMP стал одной из наиболее популярных технологий параллельного программирования. OpenMP успешно используется как при программировании суперкомпьютерных систем с большим количеством процессоров, так и в настольных пользовательских системах или, например, в Xbox 360.

OpenMP реализует параллельные вычисления с помощью многопоточности, в которой «главный» (master) поток создает набор подчиненных (slave) потоков и задача распределяется между ними. Предполагается, что потоки выполняются параллельно на машине с несколькими процессорами (количество процессоров не обязательно должно быть больше или равно количеству потоков).

Задачи, выполняемые потоками параллельно, также как и данные, требуемые для выполнения этих задач, описываются с помощью специальных директив препроцессора соответствующего языка - прагм. Например, участок кода на языке Fortran, который должен исполняться несколькими потоками, каждый из которых имеет свою копию переменной N, предваряется следующей директивой: !$OMP PARALLEL PRIVATE(N)

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

Ключевыми элементами OpenMP являются

1. конструкции для создания потоков (директива parallel);

2. конструкции распределения работы между потоками (директивы DO/for и section);

3. конструкции для управления работой с данными (выражения shared и private для определения класса памяти переменных);

4. конструкции для синхронизации потоков (директивы critical, atomic и barrier);

5. процедуры библиотеки поддержки времени выполнения (например, omp_get_thread_num);

6. переменные окружения (например, OMP_NUM_THREADS).

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

Число потоков в группе, выполняющихся параллельно, можно контролировать несколькими способами. Один из них - использование переменной окружения OMP_NUM_THREADS. Другой способ - вызов процедуры omp_set_num_threads(). Еще один способ - использование выражения num_threads в сочетании с директивой parallel.

В этой программе два массива (a и b) складываются параллельно десятью потоками.

#include

int main(int argc, char *argv)

float a[N], b[N], c[N];

omp_set_dynamic(0); // запретить библиотеке openmp менять число потоков во время исполнения

omp_set_num_threads(10); // установить число потоков в 10

// инициализируем массивы

for (I = 0; I < N; i++)

// вычисляем сумму массивов

#pragma omp parallel shared(a, b, c) private(i)

for (I = 0; I < N; i++)

c[i] = a[i] + b[i];

printf (“%f\n”, c);

Эту программу можно скомпилировать, используя gcc-4.4 и более новые с флагом –fopenmp. Очевидно, если убрать подключение заголовочного файла omp.h, а также вызовы функции настроки OpenMP, программу возможно скомпилировать на любом компиляторе С как обычную последовательную программу.

OpenMP поддерживается многими современными компиляторами:

1. Компиляторы Sun Studio поддерживают официальную спецификацию - OpenMP 2.5 - с улучшенной производительностью под ОС Solaris; поддержка Linux запланирована на следующий релиз.

2. Visual C++ 2005 и выше поддерживает OpenMP в редакциях Professional и Team System.

3. GCC 4.2 поддерживает OpenMP, а некоторые дистрибутивы (такие как Fedora Core 5 gcc) включили поддержку в свои версии GCC 4.1.

4. Intel C++ Compiler, включая версию Intel Cluster OpenMP для программирования в системах с распределённой памятью.

Message Passing Interface (MPI, интерфейс передачи сообщений) - программный интерфейс (API) для передачи информации, который позволяет обмениваться сообщениями между процессами, выполняющими одну задачу. Разработан Уильямом Гроуппом, Эвином Ласком (англ.) и другими.

MPI является наиболее распространённым стандартом интерфейса обмена данными в параллельном программировании, существуют его реализации для большого числа компьютерных платформ. Используется при разработке программ для кластеров и суперкомпьютеров. Основным средством коммуникации между процессами в MPI является передача сообщений друг другу. Стандартизацией MPI занимается MPI Forum. В стандарте MPI описан интерфейс передачи сообщений, который должен поддерживаться как на платформе, так и в приложениях пользователя. В настоящее время существует большое количество бесплатных и коммерческих реализаций MPI. Существуют реализации для языков Фортран 77/90, Си и Си++.

В первую очередь MPI ориентирован на системы с распределенной памятью, то есть когда затраты на передачу данных велики, в то время как OpenMP ориентирован на системы с общей памятью (многоядерные с общим ЭШем). Обе технологии могут использоваться совместно, дабы оптимально использовать в кластере многоядерные системы.

Первая версия MPI разрабатывалась в 1993-1994 году, и MPI 1 вышла в 1994.

Большинство современных реализаций MPI поддерживают версию 1.1. Стандарт MPI версии 2.0 поддерживается большинством современных реализаций, однако некоторые функции могут быть реализованы не до конца.

передача и получение сообщений между отдельными процессами;

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

взаимодействия в группах процессов;

реализация топологий процессов;

динамическое порождение процессов и управление процессами;

односторонние коммуникации (Get/Put);

параллельный ввод и вывод;

расширенные коллективные операции (процессы могут выполнять коллективные операции не только внутри одного коммуникатора, но и в рамках нескольких коммуникаторов).

Версия MPI 2.1 вышла в начале сентября 2008 года.

Базовым механизмом связи между MPI процессами является передача и приём сообщений. Сообщение несёт в себе передаваемые данные и информацию, позволяющую принимающей стороне осуществлять их выборочный приём:

1. отправитель - ранг (номер в группе) отправителя сообщения;

2. получатель - ранг получателя;

3. признак - может использоваться для разделения различных видов сообщений;

4. коммуникатор - код группы процессов.

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

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

Ниже приведён пример программы вычисления числа π на языке C с использованием MPI:

// Подключение необходимых заголовков

#include

// Подключение заголовочного файла MPI

#include «mpi.h»

// Функция для промежуточных вычислений

double f(double a)

return (4.0 / (1.0+ a*a));

// Главная функция программы

int main(int argc, char **argv)

// Объявление переменных

int done = 0, n, myid, numprocs, I;

double PI25DT = 3.141592653589793238462643;

double mypi, pi, h, sum, x;

double startwtime = 0.0, endwtime;

char processor_name;

// Инициализация подсистемы MPI

MPI_Init(&argc, &argv);

// Получить размер коммуникатора MPI_COMM_WORLD

// (общее число процессов в рамках задачи)

MPI_Comm_size(MPI_COMM_WORLD,&numprocs);

// Получить номер текущего процесса в рамках

// коммуникатора MPI_COMM_WORLD

MPI_Comm_rank(MPI_COMM_WORLD,&myid);

MPI_Get_processor_name(processor_name,&namelen);

// Вывод номера потока в общем пуле

fprintf(stdout, “Process %d of %d is on %s\n”, myid,numprocs,processor_name);

// количество интервалов

fprintf(stdout, “Enter the number of intervals: (0 quits) “);

if(scanf(“%d”,&n) != 1)

fprintf(stdout, “No number entered; quitting\n”);

MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);

h = 1.0 / (double) n;

// Обсчитывание точки, закрепленной за процессом

for(I = myid + 1 ; (I <= n) ; I += numprocs)

x = h * ((double)I – 0.5);

// Сброс результатов со всех процессов и сложение

MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

// Если это главный процесс, вывод полученного результата

printf(“PI is approximately %.16f, Error is %.16f\n”, pi, fabs(pi – PI25DT));

endwtime = MPI_Wtime();

printf(“wall clock time = %f\n”, endwtime-startwtime);

// Освобождение подсистемы MPI

Наиболее распространенными реализациями MPI на сегодняшний день являются:

MPICH - самая распространённая бесплатная реализация, работает на UNIX-системах и Windows NT

LAM/MPI - ещё одна бесплатная реализация MPI. Поддерживает гетерогенные конфигурации, LAM (http://www.lam-mpi.org) поддерживает гетерогенные конфигурации, пакет Globus и удовлетворяет IMPI (Interoperable MPI).

Поддерживаются различные коммуникационные системы (в том числе Myrinet).

WMPI - реализация MPI для Windows

MPI/PRO for Windows NT - коммерческая реализация для Windows NT

Intel MPI - коммерческая реализация для Windows / Linux

Microsoft MPI входит в состав Compute Cluster Pack SDK. Основан на MPICH2, но включает дополнительные средства управления заданиями. Поддерживается спецификация MPI-2.

HP-MPI - коммерческая реализация от HP

SGI MPT - платная библиотека MPI от SGI

Mvapich - бесплатная реализация MPI для Infiniband

Open MPI - бесплатная реализация MPI, наследник LAM/MPI

Oracle HPC ClusterTools - бесплатная реализация для Solaris SPARC/x86 и Linux на основе Open MPI

MPJ - MPI for Java

POSIX Threads - стандарт POSIX реализации потоков выполнения, определяющий API для создания и управления ими.

Библиотеки, реализующие этот стандарт (и функции этого стандарта), обычно называются Pthreads (функции имеют приставку «pthread_»). Хотя наиболее известны варианты для Unix-подобных операционных систем, таких как Linux или Solaris, но существует и реализация для Microsoft Windows (Pthreads-w32)

Pthreads определяет набор типов и функций на языке программирования Си. Заголовочный файл - pthread.h.

Типы данных:

1. pthread_t – дескриптор потока;

2. pthread_attr_t – перечень атрибутов потока.

Функции управления потоками:

1. pthread_create() – создание потока;

2. pthread_exit() – завершение потока (должна вызываться функцией потока при завершении);

3. pthread_cancel() – отмена потока;

4. pthread_join() – заблокировать выполнение потока до прекращения другого потока, указанного в вызове функции;

5. pthread_detach() – освободить ресурсы занимаемые потоком (если поток выполняется, то освобождение ресурсов произойдёт после его завершения);

6. pthread_attr_init() – инициализировать структуру атрибутов потока;

7. pthread_attr_setdetachstate() – указать системе, что после завершения потока она может автоматически освободить ресурсы, занимаемые потоком;

8. pthread_attr_destroy() – освободить память от структуры атрибутов потока (уничтожить дескриптор).

Функции синхронизации потоков:

2. pthread_mutex_init(), pthread_mutex_destroy(), pthread_mutex_lock(), pthread_mutex_trylock(), pthread_mutex_unlock();

3. pthread_cond_init(), pthread_cond_signal(), pthread_cond_wait().

Пример использования потоков на языке C:

#include

static void wait_thread(void)

time_t start_time = time(NULL);

while (time(NULL) == start_time)

/* do nothing except chew CPU slices for up to one second. */

static void *thread_func(void *vptr_args)

for (I = 0; I < 20; i++)

fputs(“ b\n”, stderr);

pthread_t thread;

if (pthread_create(&thread, NULL, thread_func, NULL) != 0)

return EXIT_FAILURE;

for (I = 0; I < 20; i++)

if (pthread_join(thread, NULL) != 0)

return EXIT_FAILURE;

return EXIT_SUCCESS;

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

Программа на C создает один новый поток для печати "b", а основной поток печатает "a". Основной поток (после печати "aaaaa….") ждёт завершения дочернего потока.

Контрольные вопросы

Что такое параллельная программа?
В чем отличие между процессом и потоком выполнения?
Может ли программа создать 5 потоков при работе на четырехядерном процессоре?
Каковы особенности параллельных программ с разделяемой памятью?
Какие существуют программные средства для разработки параллельных программ?
Почему большое распространение при создании программ для ПК получил именно OpenMP, а не, например, MPI?

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

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

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

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

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

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

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

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

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

Революционным шагом было появление в 1964 году операционной системы фирмы IBM - OS 360. Появившаяся у компьютера операционная система стала его полновластным хозяином - распорядителем всех его ресурсов. Теперь программа пользователя могла быть выполнена только под управлением операционной системы. Операционная система позволяла решить две важные задачи - с одной стороны обеспечить необходимый сервис всем программам, одновременно выполняемым на компьютере, с другой - эффективно использовать и распределять существующие ресурсы между программами, претендующими на эти ресурсы. Появление операционных систем привело к переходу от однопрограммного режима работы к мультипрограммному, когда на одном компьютере одновременно выполняются несколько программ. Мультипрограммирование это еще не параллельное программирование , но это шаг в направлении параллельных вычислений.

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

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

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

Появление операционной системы означало, что компьютер нельзя рассматривать только как "железо" ( память , процессоры, другие устройства). Теперь у него две составляющие - хард ( hard ) и софт ( soft ) - аппаратная и программная составляющие, взаимно дополняющие друг друга. За полвека существования компьютеров оба компонента стремительно развивались.

Для аппаратуры характерен экспоненциальный рост, что нашло отражение в известном эмпирическом законе Мура, - экспоненциально росли все важнейшие характеристики - объем памяти на всех уровнях, уменьшение времени доступа к памяти, быстродействие процессоров. Согласно закону Мура (Гордон Мур - один из основателей фирмы Intel) каждые полтора года значения характеристик увеличивались вдвое. Росло и число процессоров, включаемых в состав компьютера. Изменялась и архитектура компьютера . Эти изменения во многом были шагами в сторону распараллеливания вычислений. Вот лишь некоторые изменения в архитектуре процессоров, связанные непосредственно с процессом распараллеливания:

Конвейерная обработка команд. Процесс выполнения потока команд процессором уже не рассматривался как последовательное выполнение команды за командой. Обработка потока команд выполнялась на конвейере, так что сразу несколько команд готовились к выполнению. При конвейерной обработке команды, не связанные между собой по данным, могли выполняться одновременно, что является уже настоящим параллелизмом.
"Длинные команды". Архитектура некоторых компьютеров включала несколько процессоров, позволяющих выполнять логические и арифметические операции над целыми числами, несколько процессоров, выполняющих операции над числами с плавающей точкой. Длинная команда позволяла указать в одной команде действия, которые должен выполнить каждый из существующих процессоров. Опять таки, это позволяло реализовать параллелизм на аппаратном уровне.
Векторные и матричные процессоры. В набор команд таких процессоров включаются базисные операции над векторами и матрицами. Одной командой, например, можно сложить две матрицы. Такая команда фактически реализует параллельные вычисления. Приложения, где эти операции составляют основу обработки данных, широко распространены. Реализуемая аппаратно параллельная обработка данных позволяет существенно повысить эффективность работы приложений этого класса.
Графические процессоры. Еще одним важным видом приложений, где на аппаратном уровне происходит параллельное выполнение, являются приложения, интенсивно работающие с графическими изображениями. Эту обработку осуществляют графические процессоры. Графическое изображение можно рассматривать как набор точек. Обработка изображения зачастую сводится к выполнению одной и той же операции над всеми точками. Распараллеливание по данным легко реализуется в такой ситуации. Поэтому графические процессоры давно уже стали многоядерными, что позволяет распараллелить обработку и эффективно обрабатывать изображение.
Суперкомпьютеры. К суперкомпьютерам относят компьютеры с максимальными характеристиками производительности на данный момент. В их состав входят сотни тысяч процессоров. Эффективное использование суперкомпьютеров предполагает самое широкое распараллеливание вычислений.

В научных исследованиях и в новых технологиях всегда есть задачи, которым требуется вся мощь существующих вычислительных комплексов. Научный потенциал страны во многом определяется существованием у нее суперкомпьютеров. Понятие суперкомпьютера это относительное понятие. Характеристики суперкомпьютера десятилетней давности сегодня соответствуют характеристикам рядового компьютера. Сегодняшние суперкомпьютеры имеют производительность , измеряемую в петафлопсах (10 15 операций с плавающей точкой в секунду). К 2020 году ожидается, что производительность суперкомпьютеров повысится в 1000 раз и будет измеряться в экзафлопсах.

Классификация компьютеров

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

SISD (Single Instruction stream - Single Data stream) - одиночный поток команд - одиночный поток данных. К этому классу относятся обычные "последовательные" компьютеры с фон-Неймановской архитектурой, когда команды программы выполняются последовательно, обрабатывая очередной элемент данных.
SIMD (Single Instruction stream - Multiple Data stream) - одиночный поток команд - множественный поток данных. К этому типу относятся компьютеры с векторными и матричными процессорами.
MISD (Multiple Instruction stream - Single Data stream) - множественный поток команд - одиночный поток данных. К этому типу можно отнести компьютеры с конвейерным типом обработки данных. Однако, многие полагают, что такие компьютеры следует относить к первому типу, а компьютеры класса MISD пока не созданы.
MIMD (Multiple Instruction stream - Multiple Data stream) - множественный поток команд - множественный поток данных. Класс MIMD чрезвычайно широк и в настоящее время в него попадают многие компьютеры достаточно разной архитектуры. Поэтому предлагаются другие классификации, позволяющие более точно классифицировать компьютеры, входящие в класс MIMD.

Мы не будем рассматривать подробную классификацию компьютеров класса MIMD. Остановимся только на другом способе разделения компьютеров на три класса:

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

Текущая версия страницы пока не проверялась

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от, проверенной 5 октября 2014; проверки требуют.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Другой аргумент связан с возможной перспективой развития вычислительной техники. Скорости решения больших задач приходится повышать сегодня и заведомо придется повышать в будущем. Как правило, основные надежды связываются с созданием на основе различных технологических достижений более скоростных универсальных систем. Но повышать скорость работы вычислительной техники можно и за счет ее специализации . Уже давно практикуется использование спецпроцессоров, осуществляющих очень быструю реализацию алгоритмов быстрого преобразования Фурье, обработки сигналов, матричных операций и т.п. А теперь вспомним гипотезу о типовых структурах. Если она верна, то в конкретных прикладных областях можно будет выделить наиболее часто используемые алгоритмы и для них тоже построить спецпроцессоры. Тем самым открывается путь создания специализированных вычислительных систем для быстрого и сверхбыстрого решения задач из заданной предметной области .

Основная трудность введения в практикум заданий, связанных с изучением структуры алгоритмов, является отсутствие в настоящий момент доступного и простого в использовании программного обеспечения для построения графов алгоритмов и проведения на их основе различных исследований. По существу есть только одна система, которая реализует подобные функции. Это система V-Ray, разработанная в Научно- исследовательском вычислительном центре МГУ. Она дает возможность для различных классов программ строить графы алгоритмов и изучать их параллельную структуру. Система V-Ray реализована на персональном компьютере и не зависит от целевого компьютера. Последнее обстоятельство исключительно важно для организации практикума, поскольку частый выход с мелкими задачами на большие вычислительные системы не очень реален даже для вузов с хорошим техническим оснащением. На персональных же компьютерах время освоения задач практикума практически неограниченно. В настоящее время V-Ray представляет сложную исследовательскую систему. Далеко не все ее функции нужны для организации практикума. Со временем система V-Ray станет доступной для широкого использования. Информацию о ней и ее возможностях можно получить

Параллельные вычислительные процессы и системы (Лекция 13)

Виды параллелизма

Параллельная обработка данных имеет две разновидности: конвейерность и собственно параллельность.

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

Конвейерная обработка. Что необходимо для сложения двух вещественных чисел, представленных в форме с плавающей запятой? Целое множество мелких операций таких, как сравнение порядков, выравнивание порядков, сложение мантисс, нормализация и т.п. Процессоры первых компьютеров выполняли все эти "микрооперации" для каждой пары аргументов последовательно одна за одной до тех пор, пока не доходили до окончательного результата, и лишь после этого переходили к обработке следующей пары слагаемых. Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции, причем каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Получается очевидный выигрыш в скорости обработки за счет совмещения прежде разнесенных во времени операций. Предположим, что в операции можно выделить пять микроопераций, каждая из которых выполняется за одну единицу времени. Если есть одно неделимое последовательное устройство, то 100 пар аргументов оно обработает за 500 единиц. Если каждую микрооперацию выделить в отдельный этап (или иначе говорят– ступень) конвейерного устройства, то на пятой единице времени на разной стадии обработки такого устройства будут находится первые пять пар аргументов, а весь набор из ста пар будет обработан за 5 + 99 = 104 единицы времени – ускорение по сравнению с последовательным устройством почти в пять раз (по числу ступеней конвейера).

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

Реализация параллельных систем

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

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

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

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

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

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

Другие модели машин. Рассмотрим важнейшие компьютерные архитектуры. Мультикомпьютер очень похож на то, что часто называют компьютером с распределенной памятью MIMD (Multiple Instruction Multiple Data ). MIMD означает, что каждый процессор может обрабатывать отдельный поток инструкций над его собственными локальными данными. Распределенная память означает, что память распределена между процессорами. Принципиальным отличием MIMD компьютера от мультикомпьютера – это то, что стоимость доставки сообщения между двумя узлами не зависит от местоположения узла и сетевого трафика. Основные представители этого класса: IBM SP, Intel Paragon , Thinking Machines CM 5, Cray T 3D , Meiko CS -2, и CUBE .

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

Доступ к этому кэшу намного быстрее, чем доступ к разделяемой памяти, следовательно, локальность очень важна. Программы, разработанные для мультикомпьютеров, могут так же эффективно работать на мультипроцессорах, потому что разделяемая память позволяет эффективную реализацию передачи сообщений. Представители этого класса – Silicon Graphics Challenge, Sequent Symmetry и многие мультипроцессорные рабочие станции.

Более специализированный класс параллельных компьютеров – это SIMD (Single Instruction Miltiple Data) компьютеры. В SIMD машинах все процессоры оперируют с одним и тем же потоком инструкций над различными порциями данных. Этот подход может уменьшить сложность программного и аппаратного обеспечения, но это имеет смысл только для специализированных проблем, характеризуемых высокой степенью закономерности, например обработка изображений и определенные виды цифрового моделирования. Алгоритмы, применимые на мультикомпьютерах, не могут в общих чертах эффективно выполняться в SIMD компьютерах.

Нейровычислительные системы.

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

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

· программная эмуляция нейросетевых алгоритмов на основе использования обычных вычислительных средств и ППО по моделированию нейросетей;

· программно-аппаратная эмуляция нейросетей на основе стандартных вычислительных средств с подключаемым виртуальным нейросетевым блоком, выполняющим основные нейрооперации, и ППО, осуществляющим функции общего управления;

· аппаратная реализация нейронных сетей.

Несмотря на то, что наибольшего эффекта при реализации нейросетевых алгоритмов удается добиться лишь с использованием нейрокомпьютеров третьего направления, их широкое применение ограничивается высокой. Например, нейрокомпьютер Synaps1 – один из представителей нейрокомпьютеров третьего направления, имеет мультипроцессорную архитектуру, оригинальное построение подсистемы памяти, а для выполнения вычислительных операций использует сигнальные процессоры и специальные сигнальные матричные процессоры МА16. За счет этого производительность нейрокомпьютера составила порядка несколько миллиардов умножений и сложений в секунду. Программное обеспечение данной системы включает в себя ОС Synaps1 с библиотекой нейроалгоритмов, а также ППО: базовую библиотеку НС, компилятор языка программирования нейроалгоритмов (nAPL) (набор библиотечных функций для С++) и т.п. Прикладные исследования показали, что использование нейрокомпьютеров третьего направления позволяет повысить производительность обычных вычислительных систем как минимум на три порядка и моделировать НС с миллионами соединений. Так, например, Synaps1 позволяет моделировать нейросеть с 64 миллионами синапсов с использованием различных активационных функций.

Два класса компьютерных систем, которые иногда используют как параллельные компьютеры – это локальная сеть (LAN), в которой компьютеры, находящиеся в физической близости (например, то же строение), связываются быстрой сетью, и глобальная сеть (WAN), в которой соединены географически удаленные компьютеры. Хотя системы такого типа доставляют дополнительные проблемы, такие как безопасность, надежность, они могут быть рассмотрены для различных целей как мультикомпьютеры, хотя и с высокой стоимостью удаленного доступа.

Сложности использования параллельных систем

Гигантская производительность параллельных компьютеров и супер-ЭВМ с лихвой компенсируется сложностями их использования.

У вас есть программа и доступ, скажем, к 256-процессорному компьютеру. Что вы ожидаете? Да ясно что: вы вполне законно ожидаете, что программа будет выполняться в 256 раз быстрее, чем на одном процессоре. А вот как раз этого, скорее всего, и не будет.

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

Следствие закона Амдала. Для того, чтобы ускорить выполнение программы в q раз, необходимо ускорить не менее, чем в q раз не менее, чем (1-1/q ) -ю часть программы. Следовательно, если есть желание ускорить программу в 100 раз по сравнению с ее последовательным вариантом, то необходимо получить не меньшее ускорение не менее, чем для 99.99% кода!

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

Программирование параллельных систем

Модель машины фон Неймана предполагает, что процессор выполняет последовательность инструкций. Инструкции могут определять в дополнение к различным арифметическим операциям адреса данных, которые надо прочитать/записать в памяти, и/или адрес следующей инструкции, которую надо выполнить. Пока возможно только программировать компьютер с точки зрения этой основной модели, этот метод для большинства целей недопустимо сложен из-за того, что мы должны следить за миллионами позиций памяти и организовать выполнение тысяч машинных инструкций. Следовательно, прикладывается модульная техника разработки, посредством которой сложные программы создаются из простых компонент, и компоненты структуры с точки зрения абстракций более высокого уровня (такие, как структуры данных, итерационные циклы и процедуры). Абстракции (например, процедуры) делают эксплуатацию модульности легче, допуская объекты, которыми должны управлять без беспокойства для их внутренней структуры. Так сделаны высокоуровневые языки, как, например, Fortran, C, Ada и Java , которые допускают разработку, выраженную с точки зрения этих абстракций, которые переводятся автоматически в выполняемый код. Параллельное программирование вводит дополнительные источники сложности: если мы должны запрограммировать на самом низком уровне, нам нужно не только увеличить количество выполняемых инструкций, но также управлять выполнением тысяч процессоров и координированием миллионов межпроцессорных взаимодействий. Следовательно, абстракция и модульность по крайней мере так же важны, как и в последовательном программировании. Фактически, мы выделим модульность как четвертое фундаментальное требование для параллельного программного обеспечения, дополнительно к параллелизму, масштабируемости, и локальности.

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

1.Параллельное вычисление состоит из одной или более задач. Задачи выполняются параллельно. Количество задач может меняться во время выполнения программы.

2.Задача изолирует последовательную программу и локальную память. Вдобавок набор вводов и выводов определяет свой интерфейс в своей среде.

3.Задача может выполнять четыре основных действия дополнительно к чтению и записи в локальной памяти: послать сообщение на свои порты вывода, получить сообщение со своих портов ввода, создать новые задачи и уничтожить (завершить) задачу.

4.Операция отправления сообщения – асинхронная, она завершается немедленно. Операция получения – синхронная, она вызывает выполнение задачи, блокируя процесс, пока сообщение не будет получено.

5.Пары ввода/вывода могут связываться сообщениями в очереди, называемыми каналами. Каналы могут создаваться и удаляться, и ссылки на каналы (порты) способны включаться в сообщения, так что связность изменяется динамически.

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

Абстракция задач требует свойство локальности: данные, содержащиеся в локальной памяти задачи – «закрытые»; другие данные – «удаленные». Канальная абстракция обеспечивает механизм для указания, вычисление каких данных из одной задачи требуется для начала работы другой задачи. (Это охарактеризовано зависимостью данных). Модель задач и каналов обладает и некоторыми другими свойствами:

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

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

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

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