Модель PRAM

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

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

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

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

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

Тем самым у нас есть четыре комбинации возможностей чтения и записи: конкурентное чтение / конкурентная запись (CRCW), конкурентное чтение / исключительная запись (CREW), исключительное чтение / конкурентная запись (ERCW), исключительное чтение / исключительная запись (EREW).

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >