'

Автоматизация разработки параллельных программ для современных высокопроизводительных ЭВМ В.А. Крюков Факультет ВМК МГУ, Институт прикладной математики им. М.В. Келдыша РАН krukov@keldysh.ru 25.08.2012

Понравилась презентация – покажи это...





Слайд 0

Автоматизация разработки параллельных программ для современных высокопроизводительных ЭВМ В.А. Крюков Факультет ВМК МГУ, Институт прикладной математики им. М.В. Келдыша РАН krukov@keldysh.ru 25.08.2012


Слайд 1

2 План изложения Модели и языки программирования с явным параллелизмом (абстрактная и целевая машина, уровень, компилятор/библиотека, новый язык/расширение существующего, новые конструкции/директивы компилятору) Языки программирования с неявным параллелизмом + автоматическое распараллеливание (Fortran, C, C++) Автоматизация преобразования имеющихся последовательных программ в эффективные параллельные программы на языках с явным или неявным параллелизмом Автоматизация отладки


Слайд 2

3 Модели и языки программирования с явным параллелизмом абстрактная параллельная машина и целевая ЭВМ: многоядерный кластер с ускорителями/ многоядерный кластер/ одноядерный кластер/ узел кластера/ много ускорителей/ один ускоритель высокий или низкий уровень, глобальный или фрагментарный взгляд компилятор или библиотека новый язык или расширение существующего новые конструкции или директивы компилятору


Слайд 3

4 Модели и языки с явным параллелизмом


Слайд 4

5 Алгоритм Якоби на языке Fortran PROGRAM JACOB_SEQ PARAMETER (L=8, ITMAX=20) REAL A(L,L), B(L,L)   PRINT *, '********** TEST_JACOBI **********' DO IT = 1, ITMAX DO J = 2, L-1 DO I = 2, L-1 A(I, J) = B(I, J) ENDDO ENDDO   DO J = 2, L-1 DO I = 2, L-1 B(I, J) = (A(I-1, J) + A(I, J-1) + A(I+1, J) + * A(I, J+1)) / 4 ENDDO ENDDO ENDDO END


Слайд 5

6 Distribution of array A [8][8]


Слайд 6

7 PROGRAM JACOB_MPI include 'mpif.h' integer me, nprocs PARAMETER (L=4096, ITMAX=100, LC=2, LR=2) REAL A(0:L/LR+1,0:L/LC+1), B(L/LR,L/LC) C arrays A and B with block distribution integer dim(2), coords(2) logical isper(2) integer status(MPI_STATUS_SIZE,4), req(8), newcomm integer srow,lrow,nrow,scol,lcol,ncol integer pup,pdown,pleft,pright dim(1) = LR dim(2) = LC isper(1) = .false. isper(2) = .false. reor = .true. call MPI_Init( ierr ) call MPI_Comm_rank( mpi_comm_world, me, ierr ) call MPI_Comm_size( mpi_comm_world, nprocs, ierr) call MPI_Cart_create(mpi_comm_world,2,dim,isper, * .true., newcomm, ierr) call MPI_Cart_shift(newcomm,0,1,pup,pdown, ierr) call MPI_Cart_shift(newcomm,1,1,pleft,pright, ierr) call MPI_Comm_rank (newcomm, me, ierr) call MPI_Cart_coords(newcomm,me,2,coords, ierr)


Слайд 7

8 C rows of matrix I have to process srow = (coords(1) * L) / dim(1) lrow = (((coords(1) + 1) * L) / dim(1))-1 nrow = lrow - srow + 1 C colomns of matrix I have to process scol = (coords(2) * L) / dim(2) lcol = (((coords(2) + 1) * L) / dim(2))-1 ncol = lcol - scol + 1 call MPI_Type_vector(ncol,1,nrow+2,MPI_DOUBLE_PRECISION, * vectype, ierr) call MPI_Type_commit(vectype, ierr)     IF (me .eq. 0) PRINT *, '***** TEST_JACOBI *******'    DO IT = 1, ITMAX DO J = 1, ncol DO I = 1, nrow A(I, J) = B(I, J) ENDDO ENDDO C Copying shadow elements of array A from C neighbouring processors before loop execution


Слайд 8

9 call MPI_Irecv(A(1,0),nrow,MPI_DOUBLE_PRECISION, * pleft, 1235, MPI_COMM_WORLD, req(1), ierr) call MPI_Isend(A(1,ncol),nrow,MPI_DOUBLE_PRECISION, * pright, 1235, MPI_COMM_WORLD,req(2), ierr) call MPI_Irecv(A(1,ncol+1),nrow,MPI_DOUBLE_PRECISION, * pright, 1236, MPI_COMM_WORLD, req(3), ierr) call MPI_Isend(A(1,1),nrow,MPI_DOUBLE_PRECISION, * pleft, 1236, MPI_COMM_WORLD,req(4), ierr) call MPI_Irecv(A(0,1),1,vectype, * pup, 1237, MPI_COMM_WORLD, req(5), ierr) call MPI_Isend(A(nrow,1),1,vectype, * pdown, 1237, MPI_COMM_WORLD,req(6), ierr) call MPI_Irecv(A(nrow+1,1),1,vectype, * pdown, 1238, MPI_COMM_WORLD, req(7), ierr) call MPI_Isend(A(1,1),1,vectype, * pup, 1238, MPI_COMM_WORLD,req(8), ierr) call MPI_Waitall(8,req,status, ierr) DO J = 2, ncol-1 DO I = 2, nrow-1 B(I, J) = (A( I-1, J ) + A( I, J-1 ) + * A( I+1, J) + A( I, J+1 )) / 4 ENDDO ENDDO ENDDO call MPI_Finalize(ierr) END


Слайд 9

10 PROGRAM JACOB_OpenMP PARAMETER (L=4096, ITMAX=100) REAL A(L,L), B(L,L) PRINT *, '********** TEST_JACOBI **********' !$OMP PARALLEL DO IT = 1, ITMAX !$OMP DO DO J = 2, L-1 DO I = 2, L-1 A(I,J) = B(I,J) ENDDO ENDDO !$OMP DO DO J = 2, L-1 DO I = 2, L-1 B(I,J) = (A(I-1,J) + A(I,J-1) + * A(I+1,J) + A(I,J+1)) / 4 ENDDO ENDDO ENDDO !$OMP END PARALLEL END


Слайд 10

11 module jac_cuda contains attributes(global) subroutine arr_copy(a, b, k) real, device, dimension(k, k) :: a, b integer, value :: k integer i, j i = (blockIdx%x - 1) * blockDim%x + threadIdx%x j = (blockIdx%y - 1) * blockDim%y + threadIdx%y if (i.ne.1 .and. i.ne.k .and. j.ne.1 .and. j.ne.k) then a(i, j) = b(i, j) endif end subroutine arr_copy attributes(global) subroutine arr_renew(a, b, k) real, device, dimension(k, k) :: a, b integer, value :: k integer i, j i = (blockIdx%x - 1) * blockDim%x + threadIdx%x j = (blockIdx%y - 1) * blockDim%y + threadIdx%y if (i.ne.1 .and. i.ne.k .and. j.ne.1 .and. j.ne.k) then b(i,j) = (a(i-1,j) + a(i+1,j) + a(i,j-1) + a(i, j+1))/4 endif end subroutine arr_renew end module jac_cuda


Слайд 11

12 program JACOB_CUDA use cudafor use jac_cuda parameter (k=4096, itmax = 100, block_dim = 16) real, device, dimension(k, k) :: a, b integer it type(dim3) :: grid, block print *, '********** test_jacobi **********‘ grid = dim3(k / block_dim, k / block_dim, 1) block = dim3(block_dim, block_dim, 1) do it = 1, itmax call arr_copy<<<grid, block>>>(a, b, k) call arr_renew<<<grid, block>>>(a, b, k) end do end program jacob_CUDA


Слайд 12

13 PROGRAM JACOB_PGI_APM PARAMETER (L=4096, ITMAX=100) REAL A(L,L), B(L,L) PRINT *, '********** TEST_JACOBI **********‘ !$acc data region copyout(B), local(A) DO IT = 1, ITMAX !$acc region DO J = 2, L-1 DO I = 2, L-1 A(I,J) = B(I,J) ENDDO ENDDO DO J = 2, L-1 DO I = 2, L-1 B(I,J) = (A(I-1,J ) + A(I,J-1 ) + * A(I+1,J ) + A(I,J+1 )) / 4 ENDDO ENDDO !$acc end region ENDDO !$acc end data region END


Слайд 13

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


Слайд 14

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


Слайд 15

16 HPF (High Performance Fortran) HPF (1993 год) - расширение языка Фортран 90 HPF-2 (1997 год) - расширение языка Фортран 95 Распределение данных производится в два этапа с помощью директивы ALIGN задается соответствие между взаимным расположением элементов нескольких массивов группа массивов с помощью директивы DISTRIBUTE отображается на решетку процессоров Заданное распределение данных может быть изменено на этапе выполнения программы с помощью операторов REALIGN и REDISTRIBUTE


Слайд 16

17 PROGRAM JAC_HPF PARAMETER (L=8, ITMAX=20) REAL A(L,L), B(L,L) !HPF$ PROCESSORS P(3,3) !HPF$ DISTRIBUTE ( BLOCK, BLOCK) :: A !HPF$ ALIGN B(I,J) WITH A(I,J) C arrays A and B with block distribution PRINT *, '********** TEST_JACOBI **********' DO IT = 1, ITMAX !HPF$ INDEPENDENT DO J = 2, L-1 !HPF$ INDEPENDENT DO I = 2, L-1 A(I, J) = B(I, J) ENDDO ENDDO !HPF$ INDEPENDENT DO J = 2, L-1 !HPF$ INDEPENDENT DO I = 2, L-1 B(I, J) = (A(I-1, J) + A(I, J-1) + * A(I+1, J) + A(I, J+1)) / 4 ENDDO ENDDO ENDDO END


Слайд 17

18 PROGRAM JACOB_DVM PARAMETER (L=4096, ITMAX=100) REAL A(L,L), B(L,L) CDVM$ DISTRIBUTE ( BLOCK, BLOCK) :: A CDVM$ ALIGN B(I,J) WITH A(I,J) C arrays A and B with block distribution PRINT *, '********** TEST_JACOBI **********' DO IT = 1, ITMAX CDVM$ PARALLEL (J,I) ON A(I,J) DO J = 2, L-1 DO I = 2, L-1 A(I,J) = B(I,J) ENDDO ENDDO CDVM$ PARALLEL (J,I) ON B(I,J),SHADOW_RENEW (A) C Copying shadow elements of array A from C neighboring processors before loop execution DO J = 2, L-1 DO I = 2, L-1 B(I,J) = (A(I-1,J) + A(I,J-1) + * A(I+1,J) + A(I,J+1)) / 4 ENDDO ENDDO ENDDO END


Слайд 18

19 Новые языки параллельного программирования (PGAS) PGAS – Partitioned Global Address Space (не DSM !) CAF (Co-Array Fortran), UPC (Unified Parallel C), Titanium (расширение Java) 2005 г.: Много нитей выполняют одну программу в стиле SPMD Уровень языков не намного выше MPI Нет аналога коммуникаторов Нет средств совмещения обменов с вычислениями


Слайд 19

20 Coarray Fortran PROGRAM Jac_CoArray PARAMETER (L=8, ITMAX=20, LR=2, LC=2) PARAMETER (NROW=L/LR, NCOL=L/LC) INTEGER ME, I, J, IT INTEGER ME_R, ME_C, ME_UP, ME_LEFT, ME_RIGHT, ME_DOWN REAL A (0: NROW +1,0:NCOL+1)[0:LR-1,0:*] REAL B (1:NROW,1:NCOL)[0:LR-1,0:*] ME = THIS_IMAGE() ME_R = (ME-1)/LR ME_C = (ME-1) - ME_R*LR ME_UP = MOD(ME_R-1+LR,LR) ME_DOWN = MOD(ME_R+1+LR,LR) ME_RIGHT = MOD(ME_C+1+LC,LC) ME_LEFT = MOD(ME_C-1+LC,LC)


Слайд 20

21 DO IT = 1, ITMAX CALL SYNC_ALL ( ) DO J = 1, NCOL DO I = 1, NROW A(I, J) = B(I, J) ENDDO ENDDO C Copying shadow elements of array A from C neighbouring images before loop execution A(1:NROW,NCOL+1) = A(1:NROW,1)[ME_R, ME_RIGHT] A(1:NROW,0) = A(1:NROW,NCOL)[ME_R, ME_LEFT] A(NROW+1,1:NCOL) = A(1,1:NCOL)[ME_DOWN,ME_C ] A(0,1:NCOL) = A(NROW,1:NCOL)[ME_UP,ME_C ] DO J = 1, NCOL DO I = 1, NROW B(I, J) = (A( I-1, J ) + A( I, J-1 ) + * A( I+1, J) + A( I, J+1 )) / 4 ENDDO ENDDO ENDDO CALL SYNC_ALL ( ) END


Слайд 21

22 Развитие языков (PGAS=>APGAS) Добавление асинхронности в CAF и UPC CAF 2.0: подгруппы процессов, топологии, новые средства синхронизации процессов, коллективные коммуникации, средства совмещения обменов с вычислениями, динамическое создание асинхронных активностей (этого нет в Фортране 2008)


Слайд 22

23 SEQ – последовательная программа, MPI –параллельная MPI-программа DVM – параллельная DVM-программа, CAF – параллельная CoArray Fortran программа


Слайд 23

24 Создаваемые языки параллельного программирования (HPCS) DARPA – High Productivity Computing Systems 2002-2010 (эффективность, программируемость, переносимость ПО, надежность) Chapel (Cray), APGAS X10 (IBM), APGAS ООП


Слайд 24

25 Цели разработки Chapel (Cray) Снизить трудоемкость программирования - написание программы, ее изменение, тюнинг, портирование, сопровождение Эффективность программ на уровне MPI - сравнимо на обычных кластерах - выше на более продвинутых архитектурах Эффективность при портировании - как MPI, но лучше OpenMP, CAF, UPC Надежность - исключить часто встречающиеся ошибки - повысить уровень абстракции чтобы снизить вероятность других ошибок


Слайд 25

26 Основные черты языка Chapel Полнота поддержки параллелизма - параллелизм по данным, параллелизм задач, вложенный параллелизм - отражение всех уровней параллелизма программы - использование всех уровней параллелизма ЭВМ Поддержка глобального (а не фрагментарного!) взгляда на программу (управление и данные) Управление локализацией данных и вычислений, задаваемые программистом методы распределения Включение широко используемых возможностей последовательных языков (ООП) Новый синтаксис (чтобы не путать с привычным!) и семантика конструкций языка


Слайд 26

27 Основные отличия X10 (IBM) Является расширением языка Java Отличие доступа к локальным и удаленным данным (как в языках PGAS) Свои методы синхронизации Ориентация на параллельные системы с распределенной памятью Open source проект


Слайд 27

28 PROGRAM JACOB_DVM_OpenMP PARAMETER (L=4096, ITMAX=100) REAL A(L,L), B(L,L) CDVM$ DISTRIBUTE ( BLOCK, BLOCK) :: A CDVM$ ALIGN B(I,J) WITH A(I,J) PRINT *, '********** TEST_JACOBI **********' C$OMP PARALLEL DO IT = 1, ITMAX CDVM$ PARALLEL (J,I) ON A(I, J) C$OMP DO DO J = 2, L-1 DO I = 2, L-1 A(I, J) = B(I, J) ENDDO ENDDO CDVM$ PARALLEL (J,I) ON B(I, J), SHADOW_RENEW (A) C$OMP DO DO J = 2, L-1 DO I = 2, L-1 B(I, J) = (A(I-1, J) + A(I, J-1) + A(I+1, J) + * A(I, J+1)) / 4 ENDDO ENDDO ENDDO C$OMP END PARALLEL END


Слайд 28

29 PROGRAM JACOB_DVMH PARAMETER (L=4096, ITMAX=100) REAL A(L,L), B(L,L) CDVM$ DISTRIBUTE ( BLOCK, BLOCK) :: A CDVM$ ALIGN B(I,J) WITH A(I,J) PRINT *, '********** TEST_JACOBI **********' DO IT = 1, ITMAX CDVM$ REGION CDVM$ PARALLEL (J,I) ON A(I, J) DO J = 2, L-1 DO I = 2, L-1 A(I, J) = B(I, J) ENDDO ENDDO CDVM$ PARALLEL (J,I) ON B(I, J), SHADOW_RENEW (A) DO J = 2, L-1 DO I = 2, L-1 B(I, J) = (A(I-1, J) + A(I, J-1) + A(I+1, J) + * A(I, J+1)) / 4 ENDDO ENDDO CDVM$ END REGION ENDDO END


Слайд 29

30 Времена выполнения программы JACRED_DVMH (сек) на кластере K-100


Слайд 30

31 План изложения Модели и языки программирования с явным параллелизмом (абстрактная и целевая машина, уровень, компилятор/библиотека, новый язык/расширение существующего, новые конструкции/директивы компилятору) Языки программирования с неявным параллелизмом + автоматическое распараллеливание (Fortran, C, C++) Автоматизация преобразования имеющихся последовательных программ в эффективные параллельные программы на языках с явным или неявным параллелизмом Автоматизация отладки


Слайд 31

32 Автоматизация параллельного программирования Два новых (2005 г.) направления автоматизации в системе DVM: дисциплина написания на языках последовательного программирования “потенциально параллельных программ” - таких программ, которые могут быть автоматически (без участия пользователя) преобразованы в эффективные параллельные программы автоматизированное (с участием пользователя) преобразование последовательных программ в потенциально параллельные программы


Слайд 32

33 Автоматизация разработки параллельных программ для кластеров Программа на последовательном языке S Задание на отладку Распараллеливающий компилятор с языка S Характеристики эффективности Средства функциональной отладки Средства отладки эффективности Протокол отладки Результаты компиляции Кластер Инструментальная ЭВМ


Слайд 33

34 Формирование вариантов распределения данных (ВРД) Анализ последовательной программы Для каждого ВРД формирование схем распараллеливания - добавление вариантов распределения вычислений и доступа к данным Оценка эффективности каждой схемы на множестве возможных решеток процессоров заданной ЭВМ и выбор наилучшей схемы Генерация параллельной программы по лучшей схеме Алгоритм работы распараллеливающего компилятора АРК-DVM


Слайд 34

35 Анализ последовательной программы Статический анализ – указатели, косвенная индексация, параметры…. Динамический анализ – ресурсы времени и памяти, представительность входных данных ? Дополнительные спецификации программиста (декларативные, без ориентации на модель параллелизма), например, независимость витков, размеры массивов,….


Слайд 35

36 Алгоритм Якоби на языке Fortran PROGRAM JACOB_SEQ PARAMETER (L=8, ITMAX=20) REAL A(L,L), B(L,L)   PRINT *, '********** TEST_JACOBI **********' DO IT = 1, ITMAX DO J = 2, L-1 DO I = 2, L-1 A(I, J) = B(I, J) ENDDO ENDDO   DO J = 2, L-1 DO I = 2, L-1 B(I, J) = (A(I-1, J) + A(I, J-1) + A(I+1, J) + * A(I, J+1)) / 4 ENDDO ENDDO ENDDO END


Слайд 36

37 Поиск наилучшей схемы распараллеливания Логическая сложность алгоритмов построения и оценки схем распараллеливания (мало зависит от выходного языка параллельного программирования P) Огромное число возможных схем => необходимы эвристики


Слайд 37

38 Блоки компилятора АРК-DVM Анализатор 1 Описание ЭВМ Фортран программа База данных Эксперт 1 Фортран-DVM программа Анализатор 2 Эксперт 2 Фортран-DVM/OpenMP программа


Слайд 38

39 Работа компилятора проверена на: тестах NAS LU, BT, SP (3D Навье-Стокс) - класс С и А программе MHPDV (трехмерного моделирования сферического взрыва во внешнем магнитном поле с помощью решения уравнений идеальной магнитогидродинамики) программе ZEBRA (расчет нейтронных полей атомного реактора в диффузионном приближении) Апробация компилятора АРК-DVM


Слайд 39

40 Характеристики программ


Слайд 40

41 Времена выполнения (сек) на МВС-100К DVM-программ класса С


Слайд 41

42 План изложения Модели и языки программирования с явным параллелизмом (абстрактная и целевая машина, уровень, компилятор/библиотека, новый язык/расширение существующего, новые конструкции/директивы компилятору) Языки программирования с неявным параллелизмом + автоматическое распараллеливание (Fortran, C, C++) Автоматизация преобразования имеющихся последовательных программ в эффективные параллельные программы на языках с явным или неявным параллелизмом Автоматизация отладки


Слайд 42

43 Автоматизированное распараллеливание последовательных программ Диалог с пользователем для: Исследования результатов анализа и задания характеристик программы, недоступных для анализа, но необходимых для распараллеливания Исследования предлагаемых вариантов распараллеливания и выбора из них наиболее предпочтительных Пользователю предоставляются прогнозируемые характеристики эффективности (всей программы и ее отдельных циклов) для разных конфигураций интересующих его ЭВМ


Слайд 43

44 44


Слайд 44

45 САПФОР: анализ программы и прогноз эффективности ее параллельного выполнения Скорректированная исходная программа FDVMH-компилятор FDVMH-программа Программа на PGI Fortran CUDA + Lib-DVMH (MPI+CUDA) Компиляторы Fortran CUDA и C CUDA Компилятор АРК-DVM Последовательная Фортран-программа Кластер с ГПУ Схема использования DVMH-модели Входная программа для компилятора АРК-DVM


Слайд 45

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


Слайд 46

47 План изложения Модели и языки программирования с явным параллелизмом Языки программирования с неявным параллелизмом + автоматическое распараллеливание (НОРМА, Fortran, C, C++) Автоматизация преобразования имеющихся последовательных программ в эффективные параллельные программы на языках с явным или неявным параллелизмом Автоматизация отладки


Слайд 47

48 Автоматизация функциональной отладки параллельных программ Автоматизированное сравнение поведения и промежуточных результатов разных версий последовательной программы Динамический анализ корректности параллельной программы (автоматический) Автоматическое сравнение поведения и промежуточных результатов параллельной и последовательной программ


Слайд 48

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


Слайд 49

50 Типы ошибок Синтаксические ошибки в DVM-указаниях и нарушение статической семантики Неправильная последовательность выполнения DVM-указаний или неправильные параметры указаний Неправильное выполнение вычислений из-за некорректности DVM-указаний и ошибок, не проявляющихся при последовательном выполнении программы Аварийное завершение параллельного выполнения программы (авосты, зацикливания, зависания) из-за ошибок, не проявляющихся при последовательном выполнении программы


Слайд 50

51 Динамический контроль Чтение неинициализированных переменных Выход за пределы массива Необъявленная зависимость по данным в параллельной конструкции Модификация в параллельной ветви размноженных переменных (не редукционных и не приватных) Необъявленный доступ к нелокальным элементам распределенного массива Чтение теневых граней распределенного массива до завершения операции их обновления Использование редукционных переменных до завершения операции асинхронной редукции


Слайд 51

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


Слайд 52

53 Автоматизация отладки эффективности параллельных программ Прогноз характеристик эффективности каждого варианта распараллеливания для разных конфигураций интересующих пользователя ЭВМ Прогноз характеристик эффективности полученной параллельной программы для разных конфигураций интересующих пользователя ЭВМ Получение реальных характеристик эффективности параллельной программы при ее запусках на разных конфигурациях ЭВМ Автоматическое сравнение прогнозируемых и реальных характеристик


Слайд 53

54 Эффективность выполнения параллельной программы Эффективность выполнения параллельной программы выражается в ускорении вычислений, что может привести: к сокращению времени выполнения задачи фиксированного размера; к росту размера задачи, которую удается решить за то же самое время.


Слайд 54

55 Критерии эффективности выполнения параллельных программ Ускорение Sn = T1 / Tn, где Tn — время исполнения параллельной программы на n процессорах, T1 — время ее выполнения на 1-ом процессоре (или время выполнения исходной последовательной программы, или прогнозируемое время выполнения на 1 процессоре параллельной программы). В идеальном случае (отсутствие накладных расходов на организацию параллелизма), как может показаться, ускорение равно n (линейное ускорение). Коэффициент эффективности Sn / n = T1 / nTn. В идеальном случае, как может показаться, он равен 1, или 100 %.


Слайд 55

56 Критерии эффективности выполнения параллельных программ Если ускорение линейно от n, то говорят, что такая программа обладает свойством масштабируемости (возможностью ускорения вычислений пропорционально числу процессоров). Особое внимание заслуживает случай Sn > n (суперлинейное ускорение). Требования исходной задачи могут превосходить возможности используемого процессора по его ресурсам (чаще всего это кеши различных уровней, буфер TLB, ОП). При запуске на нескольких процессорах на них попадают подзадачи меньшего объёма, и требования к объёму ресурсов процессора сокращаются. При преодолении таких порогов и возникает суперлинейное ускорение.


Слайд 56

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


Слайд 57

58 Характеристики эффективности параллельных программ Пользователь может получить следующие характеристики эффективности программы и отдельных ее частей: execution time - астрономическое время выполнения productive time - прогнозируемое время выполнения на одном процессоре parallelization efficiency – прогнозируемая эффективность параллельного выполнения = productive time / (N * execution time) lost time – потерянное время = N * execution time - productive time где N - число процессоров


Слайд 58

59 Характеристики эффективности параллельных программ Компоненты lost time: insufficient parallelism - потери из-за выполнения последовательных частей программы на одном или всех процессорах communication - потери из-за межпроцессорных обменов или синхронизаций Idle time - простои процессоров из-за отсутствия работы и важный компонент времени коммуникаций – real synchronization - реальные потери из-за рассинхронизации


Слайд 59

60 Характеристики эффективности параллельных программ Кроме того, выдаются характеристики: load imbalance - возможные потери из-за разной загрузки процессоров synchronization - возможные потери на синхронизацию time_variation - возможные потери из-за разброса времен overlap - возможное сокращение коммуникационных расходов за счет совмещения межпроцессорных обменов с вычислениями


Слайд 60

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


Слайд 61

62 Проблема – нестабильность характеристик Нестабильность коммуникаций Изменение состава процессоров при неоднородности коммуникационной среды Загрузка коммуникационной среды другими работами Можно выдавать стабильные характеристики коммуникаций (вычислять их по формулам, зависящим от длин сообщений, латентности и пропускной способности коммуникационной среды)


Слайд 62

63 Нестабильность производительности процессоров Попадание на медленные процессоры (появляется разбалансировка, можно запрашивать лишние процессоры и отключать медленные) Частая активизация системных процессов (возрастает время коммуникаций за счет времени реальной рассинхронизации) Можно моделировать не только коммуникации, но и загрузку процессоров => предсказание эффективности


Слайд 63

64 Предсказатель эффективности DVM-программ получает характеристики выполнения DVM-программы на рабочей станции и использует их для предсказания эффективности ее выполнения на кластере с заданными параметрами (конфигурация, производительность процессоров, количество и характеристики каналов связи) Для реализации такой схемы предсказания необходимо тщательное проектирование интерфейса с run-time системой


Слайд 64

65 Принципиальные трудности предсказания эффективности Для современных процессоров трудно прогнозировать время выполнения разных фрагментов программы (кэш-память и динамическое планирование выполнения) Трудно моделировать работу программных компонентов коммуникационной системы => очень сложно получить точные характеристики выполнения программы


Слайд 65

66 Предсказатель – инструмент отладки эффективности Он может довольно точно оценить влияние основных факторов: степень распараллеливания программы - доля параллельных вычислений в общем объеме вычислений равномерность загрузки процессоров во время выполнения параллельных вычислений время, необходимое для выполнения межпроцессорных обменов (и синхронизаций) степень совмещения межпроцессорных обменов с вычислениями => есть еще важный фактор – эффективное выполнение вычислений на процессорах


Слайд 66

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


Слайд 67

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


Слайд 68

69 Вопросы, замечания? СПАСИБО !


Слайд 69

70 Информация о DVM-системе Система (в виде исходных текстов и библиотек выполняемых программ) доступна через Интернет (http://www.keldysh.ru/dvm/) Вместе с системой поставляется набор демонстрационных DVM-программ, а также документация пользователя и разработчика


×

HTML:





Ссылка: