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

1. Модели программирования для систем с разделяемой, распределенной памятью.

Программирование в модели общей памяти. (POSIX threads, OpenMP). Для SMP-систем существуют сравнительно эффективные средства автоматического распараллеливания. Подробнее см. Вопросы .

Программирование в модели распределенной памяти. Программирование в рамках модели передачи сообщений (MPI, PVM, BSPlib).

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

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

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

Программирование в модели обработки данных – параллелизм по данным. Подробнее см. Вопросы 45, 46.

1. Разделение последовательных программ на параллельные нити.

В системах с общей памятью

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

Все производители симметричных мультипроцессорных систем в той или иной мере поддерживают стандарт POSIX Pthread и включают в программное обеспечение распараллеливающие компиляторы для популярных языков программирования или предоставляют набор директив компилятору для распараллеливания программ. В частности, многие поставщики компьютеров SMP архитектуры (Sun, HP, SGI) в своих компиляторах предоставляют специальные директивы для распараллеливания циклов. Однако эти наборы директив, во-первых, весьма ограничены и, во-вторых, несовместимы между собой. В результате этого разработчикам приходится распараллеливать прикладные программы отдельно для каждой платформы.

1. Ограничения на распараллеливание циклов.

Распараллеливание циклов возможно, если все итерации цикла независимы. Тело цикла не должны содержать:

• операторов перехода

• операторов ввода-вывода

Индексные выражения не должны иметь индекс в индексе А(В(С))

+ см. вопрос 64

1. Синхронизация параллельных процессов. Барьеры.

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

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

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

инициализация и разрушение барьеров: pthread_barrier_init(), pthread_barrier_destroy()

#include <pthread.h>

int pthread_barrier_init (

pthread_barrier_t *restrict barrier,

const pthread_barrierattr_t

*restrict attr,

unsigned count);

int pthread_barrier_destroy (

pthread_barrier_t *barrier);

синхронизация на барьере: pthread_barrier_wait() (см. листинг 2.37);

#include <pthread.h>

int pthread_barrier_wait (

pthread_barrier_t *barrier);

инициализация и разрушение атрибутных объектов барьеров: pthread_barrierattr_init(), pthread_barrierattr_destroy() (см. листинг 2.38);

#include <pthread.h>

int pthread_barrierattr_init (

pthread_barrierattr_t *attr);

int pthread_barrierattr_destroy (

pthread_barrierattr_t *attr);

опрос и установка атрибутов барьеров в атрибутных объектах: pthread_barrierattr_getpshared(), pthread_barrierattr_setpshared() (см. листинг 2.39).

#include <pthread.h>

int pthread_barrierattr_getpshared

(const pthread_barrierattr_t

*restrict attr,

int *restrict pshared);

int pthread_barrierattr_setpshared

(pthread_barrierattr_t *attr,

int pshared);

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

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

if ((status = pthread_barrier_wait(

&barrier)) ==

PTHREAD_BARRIER_SERIAL_THREAD) {

/* Выделенные (обычно – объединительные) */

/* действия. */

/* Выполняются каким-то одним потоком */

/* управления */

} else {

/* Эта часть выполняется всеми */

/* прочими потоками */

/* управления */

if (status != 0) {

/* Обработка ошибочной ситуации */

} else {

/* Нормальное "невыделенное" */

/* завершение ожидания */

/* на барьере */

}

}

/* Повторная синхронизация – */

/* ожидание завершения выделенных действий */

status = pthread_barrier_wait (&barrier);

/* Продолжение параллельной работы */

. . .

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

1. Критические секции. Двоичные и общие семафоры.

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

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

P(S) - декремент и анализ семафора

S := S-1

IF (S < 0) THEN <блокировка текущего процесса>

ENDIF

V(S) - инкремент семафора

S := S+1

IF S <= 0 THEN <запустить блокированный процесс>

ENDIF

P и V операции неделимы: в каждый момент только один процесс может выполнять Р или V операцию над данным семафором.

Если семафор используется как счетчик ресурсов, то:

S >= 1 - есть некоторое количество (S) доступных ресурсов,

S = 0 - нет доступного ресурса,

S < 0 - один или несколько (S) процессов находятся в очереди к ресурсу.

Вводится, также, операция инициализации семафора (присвоение начального значения).

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

Семафоры позволяют:

- синхронизировать работу процессов,

- управлять распределением ресурсом (использованием положительного диапазона значений семафора как счетчика ресурсов) ,

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

В системах программирования вводится специальный тип данных, оп­ределяющий структуру семафора, например, SEMAPHOR,SIGNAL,GETA.

Использование семафоров

begin integer S; S:=1;

parbegin

task1: begin

do while (true)

P(S);

<критический участок 1>;

V(S);

<обычный участок>;

enddo

end;

task2: begin

do while (true)

P(S);

<критический участок 2>;