Сегментированная агрегация в массиве

У меня есть большой массив примитивных типов значений. Массив фактически является одномерным, но логически представляет 2-мерное поле. Когда вы читаете слева направо, значения должны стать (исходное значение текущей ячейки) + (результат, вычисленный в ячейке слева). Очевидно, за исключением первого элемента каждой строки, который является просто исходным значением.

У меня уже есть реализация, которая выполняет это, но полностью итеративна по всему массиву и чрезвычайно медленна для больших (1M + элементов) массивов.

Учитывая следующий пример массива,

0 0 1 0 0
2 0 0 0 3
0 4 1 1 0
0 1 0 4 1

становится

0 0 1 1 1
2 2 2 2 5
0 4 5 6 6
0 1 1 5 6

И так далее, до проблемных размеров (1024x1024)

Массив необходимо обновить (в идеале), но при необходимости можно использовать другой массив. Объем памяти не является большой проблемой, но производительность имеет решающее значение, так как эти массивы содержат миллионы элементов и должны обрабатываться сотни раз в секунду.

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

Есть ли другой способ структурировать данные, чтобы ускорить их обработку?

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

7 голосов | спросил selkathguy 10 WedEurope/Moscow2014-12-10T21:46:33+03:00Europe/Moscow12bEurope/MoscowWed, 10 Dec 2014 21:46:33 +0300 2014, 21:46:33

4 ответа


0

Правильное кодирование и немного понимания того, как .NET знает, что вещи также помогают: -)

Некоторые практические правила, которые применяются в этом случае:

  1. Если вы можете намекнуть JIT, что индексация никогда не выйдет за пределы массива, она удалит лишнюю ветвь.
  2. Вы должны векторизовать его только в нескольких потоках, если он действительно медленный (например,> 1 секунда). В противном случае переключение задач, очистка кеша и т. Д., Вероятно, просто израсходуют добавленную скорость, и вы в итоге будете хуже.
  3. Если возможно, сделайте доступ к памяти предсказуемым, даже последовательным. Если вам нужен другой массив, пусть будет так, если нет - предпочтите.
  4. Используйте как можно меньше инструкций IL, если хотите получить скорость. Обычно это работает.
  5. Протестируйте несколько итераций. Одной итерации может быть недостаточно.

Используя эти правила, вы можете сделать небольшой тестовый пример следующим образом. Обратите внимание, что я увеличил ставки до 4Kx4K, поскольку 1K настолько быстр, что вы не можете его измерить: -)

public static void Main(string[] args)
{
    int width = 4096;
    int height = 4096;

    int[] ar = new int[width * height];
    Random rnd = new Random(213);
    for (int i = 0; i < ar.Length; ++i)
    {
        ar[i] = rnd.Next(0, 120);
    }

    // (5)...
    for (int j = 0; j < 10; ++j)
    {
        Stopwatch sw = Stopwatch.StartNew();

        int sum = 0;
        for (int i = 0; i < ar.Length; ++i)  // (3) sequential access
        {
            if ((i % width) == 0)
            {
                sum = 0;
            }

            // (1) --> the JIT will notice this won't go out of bounds because [0<=i<ar.Length]
            // (5) --> '+=' is an expression generating a 'dup'; this creates less IL.
            ar[i] = (sum += ar[i]); 
        }

        Console.WriteLine("This took {0:0.0000}s", sw.Elapsed.TotalSeconds);
    }
    Console.ReadLine();
}

Одна из этих итераций займет здесь примерно 0,0174 секунды, и, поскольку это примерно в 16 раз худший сценарий, который вы описываете, я полагаю, ваша проблема с производительностью решена.

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

for (int j = 0; j < 10; ++j)
{
    Stopwatch sw = Stopwatch.StartNew();
    Parallel.For(0, height, (a) =>
    {
        int sum = 0;
        for (var i = width * a + 1; i < width * (a + 1); i++)
        {
            ar[i] = (sum += ar[i]);
        }
    });
    Console.WriteLine("This took {0:0.0000}s", sw.Elapsed.TotalSeconds);
}

Если вам действительно нужна производительность, вы можете скомпилировать ее в C ++ и использовать P /Invoke. Даже если вы не используете GPU, я полагаю, что инструкции SSE /AVX могут уже дать вам значительное повышение производительности, которого вы не получите с .NET /C #. Также я хотел бы отметить, что компилятор Intel C ++ может автоматически векторизовать ваш код - даже для PHI Xeon. Без особых усилий это может дать вам хороший прирост производительности.

ответил atlaste 18 ThuEurope/Moscow2014-12-18T10:48:39+03:00Europe/Moscow12bEurope/MoscowThu, 18 Dec 2014 10:48:39 +0300 2014, 10:48:39
0

Ну, я не знаю слишком много о GPU, но не вижу причин, почему вы не можете распараллелить его, поскольку зависимости только слева направо.

Зависимости между строками отсутствуют.

0 0 1 0 0  - process on core1 |
2 0 0 0 3  - process on core1 |
-------------------------------
0 4 1 1 0  - process on core2 |
0 1 0 4 1  - process on core2 |

Хотя приведенное выше утверждение не совсем верно. Там все еще скрытые зависимости между строками, когда дело доходит до кеша памяти.

Вполне возможно, что будет кеш очистки. Вы можете прочитать о «неверном совместном использовании кэша», чтобы понять проблему и посмотреть, как ее преодолеть.

ответил Erti-Chris Eelmaa 13 SatEurope/Moscow2014-12-13T17:20:18+03:00Europe/Moscow12bEurope/MoscowSat, 13 Dec 2014 17:20:18 +0300 2014, 17:20:18
0

Как сказал @Chris Eelmaa, возможно параллельное выполнение строки. Использование Parallel.For можно переписать так:

static int[,] values = new int[,]{
    {0, 0, 1, 0, 0},
    {2, 0, 0, 0, 3},
    {0, 4, 1, 1, 0},
    {0, 1, 0, 4 ,1}};
static void Main(string[] args)
{
    int rows=values.GetLength(0);
    int columns=values.GetLength(1);
    Parallel.For(0, rows, (row) =>
    {
        for (var column = 1; column < columns; column++)
        {
            values[row, column] += values[row, column - 1];
        }
    });

    for (var row = 0; row < rows; row++)
    {
        for (var column = 0; column < columns; column++)
        {
            Console.Write("{0} ", values[row, column]);
        }
        Console.WriteLine();
    }

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

static void Main(string[] args)
{
    var values = new int[1024 * 1024];
    Random r = new Random();
    for (int i = 0; i < 1024; i++)
    {
        for (int j = 0; j < 1024; j++)
        {
            values[i * 1024 + j] = r.Next(25);
        }
    }

    int rows = 1024;
    int columns = 1024;

    Stopwatch sw = Stopwatch.StartNew();
    for (int i = 0; i < 100; i++)
    {
        Parallel.For(0, rows, (row) =>
        {
            for (var column = 1; column < columns; column++)
            {
                values[(row * columns) + column] += values[(row * columns) + column - 1];
            }
        });
    }

    Console.WriteLine(sw.Elapsed);
}

Но не так быстро, как графический процессор. Чтобы использовать параллельную обработку GPU, вам нужно переписать ее в C ++ AMP или посмотрите, как перенести эту параллель на cudafy: http://w8isms.blogspot.com.es/2012/09/cudafy-me-part-3-of-4.html

ответил jmservera 13 SatEurope/Moscow2014-12-13T17:51:29+03:00Europe/Moscow12bEurope/MoscowSat, 13 Dec 2014 17:51:29 +0300 2014, 17:51:29
0

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

int[] texture;

у вас есть,

int[][] texture;

Изолировать операцию строки как,

private static Task ProcessRow(int[] row)
{
    var v = row[0];
    for (var i = 1; i < row.Length; i++)
    {
        v = row[i] += v;
    }

    return Task.FromResult(true);
}

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

Task.WhenAll(texture.Select(ProcessRow)).Wait();

Если вы хотите остаться с одномерным массивом, аналогичный подход подойдет, просто измените ProcessRow.

private static Task ProcessRow(int[] texture, int start, int limit)
{
    var v = texture[start];
    for (var i = start + 1; i < limit; i++)
    {
        v = texture[i] += v;
    }

    return Task.FromResult(true);
}

затем один раз,

var rowSize = 1024;
var rows =
    Enumerable.Range(0, texture.Length / rowSize)
    .Select(i => Tuple.Create(i * rowSize, (i * rowSize) + rowSize))
    .ToArray();

затем в каждом цикле.

Task.WhenAll(rows.Select(t => ProcessRow(texture, t.Item1, t.Item2)).Wait();

В любом случае каждая строка обрабатывается параллельно.

ответил Jodrell 18 ThuEurope/Moscow2014-12-18T14:11:54+03:00Europe/Moscow12bEurope/MoscowThu, 18 Dec 2014 14:11:54 +0300 2014, 14:11:54

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132