Сложность доступа к массиву fortran в цикле - PullRequest
Новая
       7

Сложность доступа к массиву fortran в цикле

0 голосов
/ 05 марта 2019

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

program main

    implicit none

    integer, parameter :: mp = SELECTED_REAL_KIND(15,307)
    integer, parameter :: Np=10, rep=100
    integer*8, parameter :: Ng(7) = (/1E3,1E4,1E5,1E6,1E7,1E8,1E9/)
    real(mp), allocatable :: x(:)
    real(mp) :: time1, time2
    integer*8 :: i,j,k, Ngj 
    real(mp) :: temp
    integer :: g

    ! print to screen
    print *, 'calling program main'

    do j=1,SIZE(Ng)   !test with different Ng

        !initialization with each Ng. Don't count for complexity.
        Ngj = Ng(j)
        if(ALLOCATED(x)) DEALLOCATE(x)
        ALLOCATE(x(Ngj))
        x = 0.0_mp

        !!===This is the part I want to check the complexity===!!
        call CPU_TIME(time1)

        do k=1,rep
            do i=1,Np
               call RANDOM_NUMBER(temp)
               g = floor( Ngj*temp ) + 1 

              x( g ) = x( g ) + 1.0_mp
            end do
        end do

        call CPU_TIME(time2)

        print *, 'Ng: ',Ngj,(time2-time1)/rep, '(sec)'

    end do

    ! print to screen
    print *, 'program main...done.'

contains

end program

Сначала я думал, что его сложность - O (Np).Но это измерение времени для Np = 10: 

 calling program main
 Ng:                  1000   7.9000000000000080E-007 (sec)
 Ng:                 10000   4.6000000000000036E-007 (sec)
 Ng:                100000   3.0999999999999777E-007 (sec)
 Ng:               1000000   4.8000000000001171E-007 (sec)
 Ng:              10000000   7.3999999999997682E-007 (sec)
 Ng:             100000000   2.1479999999999832E-005 (sec)
 Ng:            1000000000   4.5719999999995761E-005 (sec)
 program main...done.

Эта Ng-зависимость очень медленная и появляется только для очень больших Ng, но не доминирует при увеличении Np;увеличение Np просто умножает постоянный коэффициент на это масштабирование времени.Кроме того, похоже, что наклон масштабирования увеличивается, когда я использую более сложные подпрограммы, а не случайное число.Вычислено, что temp и g не зависят от Ng.В этой ситуации есть два вопроса:

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

1 Ответ

0 голосов
/ 05 марта 2019
  1. Как я понимаю эту сложность?Какую стоимость я пропустил, чтобы учесть?Я предполагаю, что стоимость доступа к элементу в массиве зависит от размера массива.Несколько сообщений о переполнении стека говорят, что доступ к массиву стоит только O (1) для некоторых языков.Я думаю, что это также должно относиться и к фортрану, но я не знаю, почему это не так.

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

Есть ли способ избежать этой стоимости?

Это ответ 1: -)

Теперь, для решения: я завершил ваш пример и позволилэто выполняется за сотни миллионов итераций.См. Ниже: 

program time_random

  integer, parameter :: rk = selected_real_kind(15)
  integer, parameter :: Ng = 100
  real(kind=rk), dimension(Ng) :: x = 0
  real(kind=rk) :: temp
  integer :: g, Np

  write(*,*) 'Enter number of loops'
  read(*,*) Np

  do i=1,Np
     call RANDOM_NUMBER(temp)
     g = floor( Ng*temp ) + 1
     x(g) = x(g) + 1
  end do

  write(*,*) x

end program time_random

Я скомпилировал его с помощью gfortran -O3 -Wall -o time_random time_random.f90 и рассчитал время с помощью функции time из bash.Остерегайтесь, что это очень грубо (и объясняет, почему я сделал количество итераций таким большим).Это также очень просто настроить: 

for ii in 100000000 200000000 300000000 400000000 500000000 600000000
do
time echo $ii | ./time_random 1>out
done

Теперь вы можете собирать тайминги и наблюдать линейную сложность.Мой компьютер сообщает 14 нс за итерацию.

Замечания:

  1. Я использовал selected_real_kind, чтобы указать реальный тип.
  2. Я пишу x после циклачтобы убедиться, что цикл не оптимизирован.
...