Почему время выполнения отличается для этих методологий цикла fortran 95?

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

Я использую Ubuntu 14.04 с GNU Fortran 4.8.4.

Код:

program main
implicit none

integer :: i,j
real :: start, finish
real,dimension(256,256) :: arr1

!ROW format - put 0 to main diagonal
call cpu_time(start)
do i=1,255,1
    do j=1,255,1
        arr1(i,j)=0
    end do
end do
call cpu_time(finish)

write(*,100) 'Execution time arr(i,j) in seconds= ', (finish-start)
100 format (A,f12.9)

!COLUMN format - put 1 to main diagonal
call cpu_time(start)
do j=1,255,1
    do i=1,255,1
        arr1(i,j)=1
    end do
end do
call cpu_time(finish)

write(*,100) 'Execution time arr(j,i) in seconds = ', (finish-start)

end program

Скомпилировать:

gfortran main.f95 -o main

Вывод:

Execution time arr(i,j) in seconds=  0.000736000
Execution time arr(j,i) in seconds =  0.000164000

Первый метод занимает примерно в 4,5 раза больше времени выполнения по сравнению со вторым методом.

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


loops fortran fortran95
person 343_458    schedule 08.08.2015    source источник
comment
Мой вопрос отличается от того, что касается этого вопроса. Обновлена ​​часть «Изменить» в моем вопросе.   -  person 343_458    schedule 09.08.2015
comment
Это разумный вопрос, но было бы полезно знать, какое базовое понимание у вас есть, или глубину ответа, который вы хотели бы получить. Конечно, вы могли бы подробно обсудить кеш и шаблоны доступа, но в равной степени и порядка элементов массива может быть достаточно для ваших нужд. Я не могу сказать, что вы хотите/нужно. На данный момент ваш первый вопрос: важен ли порядок? что предполагает, что потребуется ответ очень высокого уровня, но позже вы говорите, что понимаете, что это так.   -  person francescalus    schedule 09.08.2015
comment
Мне было интересно узнать подробную причину этого, связанную с кешем, как вы сказали. На самом деле, я только что обновил это в своем вопросе.   -  person 343_458    schedule 09.08.2015

Ответы (2)


arrow_upward
3
arrow_downward

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

  1. написать две разные программы, по одной на каждый случай;
  2. запускайте каждую программу несколько раз и берите среднее время;

Вы также можете заменить второй шаг циклом в зависимости от того, что вас интересует.

Теперь, возвращаясь к вашему беспокойству, я сначала упомяну, что вопрос слишком широк, как упомянул Франческал. Короче говоря; Память компьютера организована в иерархию:

  1. ОЗУ;
  2. Кэш (уровней может быть много, для простоты считаем один уровень);
  3. Регистры

У любого уровня есть свои преимущества и недостатки:

  1. Оперативная память может быть большой (гигабайты), но очень медленной (около десятков наносекунд, от 50 до 70).
  2. Кэш не очень большой (от нескольких килограммов до нескольких мегабайт), быстрее, чем оперативная память (несколько наносекунд от 0,5 до 2,5)
  3. регистр не большой (всего десятки байт), очень быстрый.

См., например, эту ссылку для получения дополнительной информации. . Я проигнорировал диски, которые являются другим уровнем памяти, а также сетью.

Данные обычно переходят только с одного уровня памяти на другой: то есть из ОЗУ в кэш и из кеша в ОЗУ, из кеша в регистр и из регистра в кеш. ЦП работает только с регистрами, доступ к которым быстрее. Таким образом, для каждой операции данные заносятся из ОЗУ в регистр, а после вычисления возвращаются обратно в ОЗУ. О нет, не так быстро. Давайте не будем усложнять и скажем, что ЦП работает с байтами (если вы пойдете глубже, вы узнаете понятие слов, представляющих собой группу смежных байтов, и понятие страниц, представляющее собой группу смежных слов).

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

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

a(1,1) a(2,1) a(3,1) ... a(M,1) a(1,2) a(2,2) a(3,2) ... a(M,2) ...

Итак, петля

do j=1,255,1
    do i=1,255,1
        arr1(i,j)=1
    end do
end do

обращается к элементам в том порядке, в котором они хранятся в памяти. Количество переходов между оперативной памятью и кешем сведено к минимуму.

Для другой петли

do i=1,255,1
    do j=1,255,1
        arr1(i,j)=1
    end do
end do

Вы просто не обращаетесь к элементам в правильном порядке. Например, если ваш кеш может содержать меньше столбца вашей матрицы, это означает, что для любой итерации внутреннего цикла система должна пополнить кеш. И это не так просто, чтобы пополнить кеш, система сначала скопирует обратно в оперативную память данные, которые находятся в кеше, если они были изменены, как здесь. Чтобы увидеть это, увеличьте матрицу до максимального размера, который может выдержать ваша оперативная память, и вы увидите, что значит не следовать логике хранения, разрыв будет увеличиваться. Вы можете переходить постепенно, 1000x1000, затем 10000x10000 и т. д. Когда вы кэшируете только один столбец или меньше, вы получите коэффициент, близкий к коэффициенту между временем доступа к ОЗУ и кэшу. Помните, больше 10.

Тема памяти является предметом многих курсов информатики. Я хотел дать тебе только то, что могу дать быстро.

person innoSPG    schedule 09.08.2015

arrow_upward
1
arrow_downward

Чтобы работать с данными, ЦП должен прочитать их из ОЗУ в свой кеш. Для чтения одного байта требуется примерно столько же времени, сколько для чтения большого количества последовательных байтов.

Если ваш внутренний цикл находится в несмежном измерении, ЦП должен независимо читать и записывать каждое отдельное значение из и в ОЗУ. Если ваш внутренний цикл находится в непрерывном измерении, он может прочитать множество значений за один раз, а затем обработать их в своем кеше.

person chw21    schedule 09.08.2015