elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Сложно ли упереться в скорость последовательной работы с памятью?
elizarov

Я показывал простой способ, которым можно сравнить скорость последовательного и случайного доступа к памяти, запуская идентичный код с разными параметрами. Получалось отличие почти в 19 раз. Случайный доступ к памяти работает так медленно, что даже сложный код, работающий с память непоследовательно, скорей всего будет ограничен в скорости своей работы именно памятью. Однако, последовательный доступ давал скорость работы с памятью не превышающую 3 ГБ в секунду. А это далеко до предела. Код упирался в CPU, а не в скорость работы с памятью. Очевидно, что упростив код можно увеличить скорость его работы. Проведем эксперимент.

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

    public int run() { 
        int sum = 0; 
        for (int i = 0; i < N; i++) 
            sum += a[i]; 
        return sum; 
    }

На моей машине получится 0.77 ± 0.02 нс на элемент массива, что соответствует скорости работы с памятью в 5.2 ГБ в секунду. Дальнейшее ускорение можно получить несколькими способами, которые грубо разбиваются на три категории:

  1. Использование SIMD инструкций процессора.
  2. Использование специфичиских особенностей подсистемы работы с памятью процессора.
  3. Использование нескольких ядер процессора одновременно (параллелизация).
Увидеть эффект от SIMD легко. Можно взять мою тестовую программу IntVectorIterationTiming.cpp, которая также занимается сложением целых чисел в массиве, и скомпилировать её используя "g++ -O3 -funroll-loops -march=core2 -o IntVectorIterationTiming.exe IntVectorIterationTiming.cpp". Полученный код с использованием SIMD (MMX) инструкций будет работать порядка 0.60 нс на итерацию, что соответствует примерно 6.7 ГБ в секунду.

Но и без SIMD можно добиться ускорения, однако код придется усложнить. Нужно посылать в память несколько запросов в разные области одновременно и избавиться от лишних зависимостей по данным, подсчитывая несколько промежуточных сумм (в примере ниже их две):

    public int run() { 
        int sum0 = 0; 
        int sum1 = 0; 
        for (int i = 0; i < N / 2; i++) { 
            sum0 += a[i]; 
            sum1 += a[i + N / 2]; 
        } 
        return sum0 + sum1; 
    }

Такой код, суммирующий две части массива одновременно, фактически выполняет два разных потока вычисления одновременно, путем ручного перемешивания их инструкций в одном коде. Получается такой SMT (который Intel называет HyperThreading), только написанный "ручками" со всеми его преимуществами в виде более полного использования вычислительных блоков процессора и более полной загрузкой памяти. Получаем 14% ускорения по сравнению с простым кодом: 0.67 ± 0.02 нс на элемент массива, что дает уже почти 6 ГБ в секунду.

Разбиение массива на три части аналогичным образом дает уже 0.64 ± 0.02 нс на элемент массива, что эквивалентно 6.2 ГБ в секунду и близко к скорости полученной применением SIMD инструкций. Конечно, можно скомбинировать оба подхода, но проще всего полностью загрузить память процессора распараллелив вычисления по обоим физическим ядрам и логическим потокам внутри них (всего на четыре потока в моем случае).

На Java это проще всего сделать использую библиотеку для параллелизации Fork/Join задач, хорошим примером которой и является задача о суммировании элементов массива. Для начала надо создать ForkJoinPool и посылать туда вычислительную задачу:

    private final static ForkJoinPool FJP = new ForkJoinPool(4); 

    public int run() { 
        SumTask task = new SumTask(0, N); 
        FJP.invoke(task); 
        return task.sum; 
    } 

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

    class SumTask extends RecursiveAction { 
        final int from; 
        final int to; 
        final int[] a = SequentialVsRandomMemoryTiming.this.a; 
 
        int sum; 
 
        public SumTask(int from, int to) { 
            this.from = from; 
            this.to = to; 
        } 
 
        @Override 
        protected void compute() { 
            if (to - from <= SEQ_LIMIT) { 
                int sum = 0; 
                for (int i = from; i < to; i++) 
                    sum += a[i]; 
                this.sum = sum; 
            } else { 
                int mid = (from + to) / 2; 
                SumTask lo = new SumTask(from, mid); 
                SumTask hi = new SumTask(mid, to); 
                invokeAll(lo, hi); 
                sum = lo.sum + hi.sum; 
            } 
        } 
    } 

В результате получим 0.56 ± 0.01 нс на элемент массива, что соответствует скорости работы с памятью в 7.15 ГБ в секунду. Полный код для всех вариантов выложен здесь.

Распараллеливание в 4 раза не убыстрило исходный простой код в 4 раза. Ускорение произошло всего на 37%. Даже простой однопоточный код практически всё время ожидал получения данных из памяти, несмотря на то, что происходил самый быстрый, последовательный доступ в память. Простой вычислительный код упирается в скорость работы с памятью даже при последовательной работе с памятью, даже в одном потоке, даже без использования SIMD инструкций. Это происходит как только данные перестают влезать в кэш (в этих тестах массив данных занимал больее 100 МБ памяти).


  • 1
Ром, с "простым" кодом всегда ОЧЕНЬ много нюансов... например в приведенном примере роль играет буквально все. какая ОС (как шкедулились потоки) процессор (архитектура), где (в каком потоке) ты выделил память и в каком суммировал, да, ну и хинт -- побить большой кусок памяти на равные куски и запустить 4 потока, явно не самый быстрый способ... fork/join - Он же не для того чтоб быстро, а чтоб параллельно :)))

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

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

private final static ForkJoinPool FJP = new ForkJoinPool(4);
private static final int SEQ_LIMIT = N / 4;

А может, всё-таки, помельче порезать? И раз уж код публичный, опирайся на Runtime...getAvailableProcessors().

Пробовал я и мельче резать. Ничего заметно не меняется, пока куски не становятся очень мелкими и становится заметен накладняк. Но вариация результатов растет, поэтому для иллюстрации я остановился на таком варианте.

быстрая память

Здравствуйте, Роман!
Может для ускорения считать сумму в момент изменения элементов массива?
Аналогично переиндексация в БД в момент изменения БД.
В этом случае сумма будет доступна сразу после изменения массива с данными.

Re: быстрая память

Сумма это просто игрушечный пример в данном случае. Конечно, если бы стояла реальная задача суммирования элементов БД, то можно было предложить массу альтернативных способ её решения.

  • 1
?

Log in

No account? Create an account