Alexander_KS/SAPFOR
4
2
Fork 0
Code Issues Pull Requests Packages Projects Releases Wiki Activity

[improvement] Concept of sequential regions #51

New Issue
Closed
opened 2024-09-22 18:55:54 +00:00 by xnpster · 6 comments
xnpster commented 2024-09-22 18:55:54 +00:00
Collaborator
Copy Link

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

Существующий механизм областей распараллеливания

В системе SAPFOR области распараллеливания задаются при помощи директивы PARALLEL_REG <name>:

      subroutine foo ()
      integer ::  a(100,100),i,j
!$SPF PARALLEL_REG reg1
      do  i = 1,100
         do  j = 2,100
            a(i,3 + j * j) = a(i,1 + j * j * j)
         enddo  
      enddo  
!$SPF END PARALLEL_REG
      a(1,1) = 0
      a(2,2) = 1
!$SPF PARALLEL_REG reg1
      do  i = 1,100
         do  j = 2,100
            a(3 + j * j,i) = a(3 + j * j * j,i)
         enddo  
      enddo  
!$SPF END PARALLEL_REG
      end

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

Больше про области распараллеливания можно прочитать в магистерской диссертации Яшина Сергея Владимировича (прикреплённый файл).

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

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

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

Я больше склоняюсь к введению новой директивы, вот причины:

  • PARALLEL_REG всё же обозначает параллельный регион

  • текущая форма PARALLEL_REG требует наличия поля <name> которое теряет смысл при задании последовательного региона

  • сейчас запрещены вложенные директивы PARALLEL_REG

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

Далее приведу несколько примеров, чтобы было понятно, как и в каких случаях можно будет использовать эту директиву:

Пример 1

      subroutine foo ()
      integer ::  a(100),i

;LOOP 1
      do  i = 1,100
         a(i) = i
      enddo

;LOOP 2 
!$SPF SEQUENTIAL_REG 
      do  i = 1,100
         a(i) = i
      enddo  
!$SPF END SEQUENTIAL_REG

      end

В программе нет параллельных регионов, поэтому распараллеливаться будет всё, кроме второго цикла из-за директивы.

Пример 2

      subroutine foo ()
      integer ::  a(100),i

;LOOP 1
!$SPF PARALLEL_REG reg1 
      do  i = 1,100
         a(i) = i
      enddo
!$SPF END PARALLEL_REG

;LOOP 2 
!$SPF SEQUENTIAL_REG 
      do  i = 1,100
         a(i) = i
      enddo  
!$SPF END SEQUENTIAL_REG

      end

В программе есть один параллельный регион на первом цикле, поэтому распараллеливаться будет только он, директива SEQUENTIAL_REG тут допустима, но не имеет эффекта.

Пример 3

      subroutine foo ()
      integer ::  a(100),i

;LOOP 1
!$SPF PARALLEL_REG reg1 
      do  i = 1,100
         a(i) = i
      enddo

;LOOP 2 
!$SPF SEQUENTIAL_REG 
      do  i = 1,100
         a(i) = i
      enddo  
!$SPF END SEQUENTIAL_REG
!$SPF END PARALLEL_REG

      end

Директива SEQUENTIAL_REG может быть вложена в директиву PARALLEL_REG. В таком случае опять первый цикл должен будет распараллелен, второй - нет.

Пример 4

      subroutine foo ()
      integer ::  a(100, 100),i

;LOOP 1
!$SPF PARALLEL_REG reg1 
      do  i = 1,100
      
;LOOP 2 
!$SPF SEQUENTIAL_REG 
         do j = 1, 100   
            a(i, j) = i
         enddo
!$SPF END SEQUENTIAL_REG

      enddo
!$SPF END PARALLEL_REG
      
      end

Директива SEQUENTIAL_REG может быть вложена в директиву PARALLEL_REG, при этом они могут находится на разных уровнях вложенности (но соответствующие директивы SEQUENTIAL_REG, END SEQUENTIAL_REG должны находиться на одном уровне). Такая конструкция означает, что внушний цикл может быть распараллелен, а внутренний нет (SAPFOR должен сгенерировать директиву PARALLEL (i), но не PARALLEL (i, j)). Аналогично директива SEQUENTIAL_REG может быть вложена в PARALLEL_REG неявно, то есть находится в теле функции, вызываемой явно или неявно из фрагмента директивы PARALLEL_REG.

Устранение конфликтов

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

Если говорить обобщённо, то возможны следующие случаи при определении области последовательного выполнения:

  1. Она не может разорвать параллельный регион (например, если она стоит внутри распараллеливаемого цикла как в примере 4). Тогда она никак не влияет на копирование массивов и функций.

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

Пример 5 (разрыв параллельного региона)

!DVM$ INTERVAL (-(2147426303)) 
      a_l1 = a 
!DVM$ ACTUAL (a_l1) 
!DVM$ END INTERVAL 
!$SPF PARALLEL_REG reg1  
!DVM$ REGION  
!DVM$ PARALLEL (i) ON a_l1(i), PRIVATE (i) 
      do  i = 1,100 
         a_l1(i) = i 
      enddo   
!DVM$ END REGION 
!$SPF END PARALLEL_REG 
!DVM$ INTERVAL (-(2147409919)) 
!DVM$ GET_ACTUAL (a_l1) 
      a = a_l1 
!DVM$ END INTERVAL 
      
!$SPF SEQUENTIAL_REG 
      do j = 1, 100   
         a(i) = i
      enddo
!$SPF END SEQUENTIAL_REG

!DVM$ INTERVAL (-(2147373055)) 
      a_l1 = a 
!DVM$ ACTUAL (a_l1) 
!DVM$ END INTERVAL 
!$SPF PARALLEL_REG reg1  
!DVM$ REGION  
!DVM$ PARALLEL (i) ON a_l1(i), PRIVATE (i) 
      do  i = 1,100 
         a_l1(i) = i 
      enddo   
!DVM$ END REGION 
!$SPF END PARALLEL_REG 
!DVM$ INTERVAL (-(2147356671)) 
!DVM$ GET_ACTUAL (a_l1) 
      a = a_l1 
!DVM$ END INTERVAL

Распараллеливание на общую память

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

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

В целом связка проходов устрение конфликтов (для случая с распределением) + распараллеливание на общую память работает корректно.

Примерная реализация

На этапе парсинга директив PARALLEL_REG будут также парсится директивы SEQUENTIAL_REG. Сейчас параллельные регионы отражены в системе при помощи структуры ParallelRegion которая в свою очередь хранит множество фрагментов, составляющих регион, отражённых структурами ParallelRegionLines.

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

# Механизм последовательных регионов ## Существующий механизм областей распараллеливания В системе SAPFOR области распараллеливания задаются при помощи директивы `PARALLEL_REG <name>`: ``` subroutine foo () integer :: a(100,100),i,j !$SPF PARALLEL_REG reg1 do i = 1,100 do j = 2,100 a(i,3 + j * j) = a(i,1 + j * j * j) enddo enddo !$SPF END PARALLEL_REG a(1,1) = 0 a(2,2) = 1 !$SPF PARALLEL_REG reg1 do i = 1,100 do j = 2,100 a(3 + j * j,i) = a(3 + j * j * j,i) enddo enddo !$SPF END PARALLEL_REG end ``` Они позволяют сузить распараллеливание до отдельных фрагментов, так как часто распараллелить программу полностью сложно или невозможно. Больше про области распараллеливания можно прочитать в магистерской диссертации Яшина Сергея Владимировича (прикреплённый файл). ## Механизм последовательных регионов Регионы последовательного выполнения планируется использовать для того, чтобы исключить фрагмент(ы) программы из распараллеливания. На данный момент в сапфоре такого функционала нет, в некоторых случаях нужного поведения можно добиться путём покрытия всей программы за исключением избранных фрагментов параллельными регионами. Идея состоит в том, чтобы ввести новую директиву (или новую форму директивы `PARALLEL_REG`) с помощью которой можно помечать фрагменты, внутри которых системе не следует проводить распараллеливание. Я больше склоняюсь к введению новой директивы, вот причины: * `PARALLEL_REG` всё же обозначает _параллельный_ регион * текущая форма `PARALLEL_REG` требует наличия поля `<name>` которое теряет смысл при задании последовательного региона * сейчас запрещены вложенные директивы `PARALLEL_REG` Далее будем считать, что для создания последовательных регионов будет использоваться (несуществующая) директива `SEQUENTIAL_REG`. Далее приведу несколько примеров, чтобы было понятно, как и в каких случаях можно будет использовать эту директиву: ### Пример 1 ``` subroutine foo () integer :: a(100),i ;LOOP 1 do i = 1,100 a(i) = i enddo ;LOOP 2 !$SPF SEQUENTIAL_REG do i = 1,100 a(i) = i enddo !$SPF END SEQUENTIAL_REG end ``` В программе нет параллельных регионов, поэтому распараллеливаться будет всё, кроме второго цикла из-за директивы. ### Пример 2 ``` subroutine foo () integer :: a(100),i ;LOOP 1 !$SPF PARALLEL_REG reg1 do i = 1,100 a(i) = i enddo !$SPF END PARALLEL_REG ;LOOP 2 !$SPF SEQUENTIAL_REG do i = 1,100 a(i) = i enddo !$SPF END SEQUENTIAL_REG end ``` В программе есть один параллельный регион на первом цикле, поэтому распараллеливаться будет только он, директива `SEQUENTIAL_REG` тут допустима, но не имеет эффекта. ### Пример 3 ``` subroutine foo () integer :: a(100),i ;LOOP 1 !$SPF PARALLEL_REG reg1 do i = 1,100 a(i) = i enddo ;LOOP 2 !$SPF SEQUENTIAL_REG do i = 1,100 a(i) = i enddo !$SPF END SEQUENTIAL_REG !$SPF END PARALLEL_REG end ``` Директива `SEQUENTIAL_REG` может быть вложена в директиву `PARALLEL_REG`. В таком случае опять первый цикл должен будет распараллелен, второй - нет. ### Пример 4 ``` subroutine foo () integer :: a(100, 100),i ;LOOP 1 !$SPF PARALLEL_REG reg1 do i = 1,100 ;LOOP 2 !$SPF SEQUENTIAL_REG do j = 1, 100 a(i, j) = i enddo !$SPF END SEQUENTIAL_REG enddo !$SPF END PARALLEL_REG end ``` Директива `SEQUENTIAL_REG` может быть вложена в директиву `PARALLEL_REG`, при этом они могут находится на разных уровнях вложенности (но соответствующие директивы `SEQUENTIAL_REG`, `END SEQUENTIAL_REG` должны находиться на одном уровне). Такая конструкция означает, что внушний цикл может быть распараллелен, а внутренний нет (SAPFOR должен сгенерировать директиву `PARALLEL (i)`, но не `PARALLEL (i, j)`). Аналогично директива `SEQUENTIAL_REG` может быть вложена в `PARALLEL_REG` неявно, то есть находится в теле функции, вызываемой явно или неявно из фрагмента директивы `PARALLEL_REG`. ## Устранение конфликтов Для устранения конфликтов областей распараллеливания сейчас, в основном, производится две операции: создание массивов-копий и функций-копий. Чтобы сохранить корректность распараллеливания, нужно посмотреть на эти операции с точки зрения добавляемых областей последовательного выполнения. Если говорить обобщённо, то возможны следующие случаи при определении области последовательного выполнения: 1. Она не может разорвать параллельный регион (например, если она стоит внутри распараллеливаемого цикла как в примере 4). Тогда она **никак** не влияет на копирование массивов и функций. 2. Она разрывает регион. Тогда на образовавшихся границах нужно добавить ещё по копированию (в обе стороны) каждого массива, использующегося в выделенной области. Если в этой области есть функции которые больше в параллельной области не используются, их можно не копировать; никакие вызовы функций в такой выделенной области менять не нужно (должны вызываться оригинальные функции). Пример 5 (разрыв параллельного региона) ``` !DVM$ INTERVAL (-(2147426303)) a_l1 = a !DVM$ ACTUAL (a_l1) !DVM$ END INTERVAL !$SPF PARALLEL_REG reg1 !DVM$ REGION !DVM$ PARALLEL (i) ON a_l1(i), PRIVATE (i) do i = 1,100 a_l1(i) = i enddo !DVM$ END REGION !$SPF END PARALLEL_REG !DVM$ INTERVAL (-(2147409919)) !DVM$ GET_ACTUAL (a_l1) a = a_l1 !DVM$ END INTERVAL !$SPF SEQUENTIAL_REG do j = 1, 100 a(i) = i enddo !$SPF END SEQUENTIAL_REG !DVM$ INTERVAL (-(2147373055)) a_l1 = a !DVM$ ACTUAL (a_l1) !DVM$ END INTERVAL !$SPF PARALLEL_REG reg1 !DVM$ REGION !DVM$ PARALLEL (i) ON a_l1(i), PRIVATE (i) do i = 1,100 a_l1(i) = i enddo !DVM$ END REGION !$SPF END PARALLEL_REG !DVM$ INTERVAL (-(2147356671)) !DVM$ GET_ACTUAL (a_l1) a = a_l1 !DVM$ END INTERVAL ``` ## Распараллеливание на общую память В случае распараллеливания на общую память ситуация становится только легче, так как копирование массивов их копий можно опустить (так как массивы не распределяются). Но это относится скорее не к теме областей последоательного выполнения, а к проходу устранения конфликтов, точнее к эффективной поддержке в нём режима распараллеливания на общую память. В целом связка проходов устрение конфликтов (для случая с распределением) + распараллеливание на общую память работает корректно. ## Примерная реализация На этапе парсинга директив `PARALLEL_REG` будут также парсится директивы `SEQUENTIAL_REG`. Сейчас параллельные регионы отражены в системе при помощи структуры `ParallelRegion` которая в свою очередь хранит множество фрагментов, составляющих регион, отражённых структурами `ParallelRegionLines`. Планируется завести аналогичное множество структур `ParallelRegionLines` (на самом деле структуру `ParallelRegionLines` можно переименовать в `CodeFragment`, так как ничего касательно параллельности там не содержится, только фрагмент из АСТ программы) и использовать его как множество фрагментов, которые следует исключить из распараллеливания. Заполняться эти множество будут в момент парсинга директив `SEQUENTIAL_REG` для параллельных регионов (на самом деле одного региона), в которые вложен текущий фрагмент. При распараллеливании будет учитываться тот факт, что внутри этих фрагментов распараллеливание вести не следует.
👍 1
Alexander_KS was assigned by xnpster 2024-09-22 18:55:54 +00:00
xnpster commented 2024-09-26 20:32:18 +00:00
Author
Collaborator
Copy Link

UPD: добавил мысли по поводу устранения конфликтов областей

_UPD_: добавил мысли по поводу устранения конфликтов областей
xnpster commented 2024-09-26 20:35:40 +00:00
Author
Collaborator
Copy Link

Не хочу переходить отсюда в трекер, потому что там не распознаётся Markdown, туда просто продублирую. Файл с диссертацией можно найти там же.

Не хочу переходить отсюда в трекер, потому что там не распознаётся Markdown, туда просто продублирую. Файл с диссертацией можно найти там же.
xnpster commented 2024-09-26 20:37:49 +00:00
Author
Collaborator
Copy Link

Я не уверен, что стоит думать сразу над несколькими проблемами, может быть стоит хотя бы на уровне ТЗ разобраться с областями?

Я не уверен, что стоит думать сразу над несколькими проблемами, может быть стоит хотя бы на уровне ТЗ разобраться с областями?
Alexander_KS commented 2024-09-27 05:59:53 +00:00
Owner
Copy Link

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

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

Пункт устранения конфликтов мне кажется не до конца продумано, так как здесь описываются ситуации с распараллеливанием на общую память. В такой постановке по идее надо знать, какой режим распараллеливания будет использоваться и уже в зависимости от него, либо создавать копии, либо нет. Из-за того, что ранее был только один режим, требовались разрежения конфликтов и создание массивов копий, так как без этого просто невозможно распараллелить программу. Теперь мы приходим к тому, что у нас есть два режима и в каждом из режимов нужно действовать по разному. И возникает вопрос, как нам теперь контролировать этот момент при расстановке областей и работы с ними?
xnpster commented 2024-10-01 14:00:41 +00:00
Author
Collaborator
Copy Link

UPD: обновил параграф с устранением конфликтов, немного написал о том, как жто соотносится с общей памятью

_UPD:_ обновил параграф с устранением конфликтов, немного написал о том, как жто соотносится с общей памятью
xnpster commented 2024-10-16 20:43:45 +00:00
Author
Collaborator
Copy Link

Решили сделать это проще и только для операторов ввода-вывода

Решили сделать это проще и только для операторов ввода-вывода
Sign in to join this conversation.
No Branch/Tag Specified
Branches Tags
Labels
No items
No Label
Milestone
No items
No Milestone
Projects
Clear projects
No project
Assignees
Clear assignees
abrosim0v Dudarenko EgorMayorov gr_gusev IgorBobrov oleg_nikitin xnpster Alexander_KS
No Assignees Alexander_KS
2 Participants
Notifications
Due Date
No due date set.
Dependencies

No dependencies set.

Reference: Alexander_KS/SAPFOR#51
Delete Branch "%!s()"

Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?