Как сделать Speedy комплексную арифметику в C # - PullRequest
0 голосов
/ 16 февраля 2011

Я сейчас работаю над проектом C # Fractal Generator, который требует много арифметики с комплексными числами, и я пытаюсь придумать способы ускорить математику.Ниже приведен упрощенный набор кода, который проверяет скорость вычисления Мандельброта с использованием одного из трех методов хранения данных, показанных в TestNumericsComplex, TestCustomComplex и TestPairedDoubles.Пожалуйста, поймите, что Мандельброт - всего лишь пример, и я намерен, чтобы будущие разработчики могли создавать плагинальные фрактальные формулы.

В основном я вижу, что использование System.Numerics.Complex - это хорошая идея, при использовании парыдвойников или пользовательская сложная структура - сносные идеи.Я могу выполнить арифметику с помощью графического процессора, но разве это не ограничит или не нарушит мобильность?Я пытался изменить порядок внутренних циклов (I, X, Y) безрезультатно.Что еще я могу сделать, чтобы помочь ускорить внутренние петли?Я сталкиваюсь с проблемами страницы?Принесет ли мне использование системы счисления с фиксированной запятой какую-либо скорость, в отличие от значений с плавающей запятой?

Я уже знаю Parallel.For в C # 4.0;это опущено в моих примерах кода для ясности.Я также знаю, что C # обычно не является хорошим языком для высокой производительности;Я использую C #, чтобы использовать преимущества Reflection для плагинов и WPF для управления окнами.

using System;
using System.Diagnostics;

namespace SpeedTest {
class Program {
    private const int ITER = 512;
    private const int XL = 1280, YL = 1024;

    static void Main(string[] args) {
        var timer = new Stopwatch();
        timer.Start();
        //TODO use one of these two lines
        //TestCustomComplex();
        //TestNumericsComplex();
        //TestPairedDoubles();
        timer.Stop();
        Console.WriteLine(timer.ElapsedMilliseconds);
        Console.ReadKey();
    }

    /// <summary>
    /// ~14000 ms on my machine
    /// </summary>
    static void TestNumericsComplex() {
        var vals = new System.Numerics.Complex[XL,YL];
        var loc = new System.Numerics.Complex[XL,YL];

        for (int x = 0; x < XL; x++) for (int y = 0; y < YL; y++) {
            loc[x, y] = new System.Numerics.Complex((x - XL/2)/256.0, (y - YL/2)/256.0);
            vals[x, y] = new System.Numerics.Complex(0, 0);
        }

        for (int i = 0; i < ITER; i++) {
            for (int x = 0; x < XL; x++)
            for (int y = 0; y < YL; y++) {
                if(vals[x,y].Real>4) continue;
                vals[x, y] = vals[x, y] * vals[x, y] + loc[x, y];
            }
        }
    }


    /// <summary>
    /// ~17000 on my machine
    /// </summary>
    static void TestPairedDoubles() {
        var vals = new double[XL, YL, 2];
        var loc = new double[XL, YL, 2];

        for (int x = 0; x < XL; x++) for (int y = 0; y < YL; y++) {
                loc[x, y, 0] = (x - XL / 2) / 256.0;
                loc[x, y, 1] = (y - YL / 2) / 256.0;
                vals[x, y, 0] = 0;
                vals[x, y, 1] = 0;
            }

        for (int i = 0; i < ITER; i++) {
            for (int x = 0; x < XL; x++)
                for (int y = 0; y < YL; y++) {
                    if (vals[x, y, 0] > 4) continue;
                    var a = vals[x, y, 0] * vals[x, y, 0] - vals[x, y, 1] * vals[x, y, 1];
                    var b = vals[x, y, 0] * vals[x, y, 1] * 2;
                    vals[x, y, 0] = a + loc[x, y, 0];
                    vals[x, y, 1] = b + loc[x, y, 1];
                }
        }
    }


    /// <summary>
    /// ~16900 ms on my machine
    /// </summary>
    static void TestCustomComplex() {
        var vals = new Complex[XL, YL];
        var loc = new Complex[XL, YL];

        for (int x = 0; x < XL; x++) for (int y = 0; y < YL; y++) {
            loc[x, y] = new Complex((x - XL / 2) / 256.0, (y - YL / 2) / 256.0);
            vals[x, y] = new Complex(0, 0);
        }

        for (int i = 0; i < ITER; i++) {
            for (int x = 0; x < XL; x++)
            for (int y = 0; y < YL; y++) {
                if (vals[x, y].Real > 4) continue;
                vals[x, y] = vals[x, y] * vals[x, y] + loc[x, y];
            }
        }
    }

}

public struct Complex {
    public double Real, Imaginary;
    public Complex(double a, double b) {
        Real = a;
        Imaginary = b;
    }
    public static Complex operator + (Complex a, Complex b) {
        return new Complex(a.Real + b.Real, a.Imaginary + b.Imaginary);
    }
    public static Complex operator * (Complex a, Complex b) {
        return new Complex(a.Real*b.Real - a.Imaginary*b.Imaginary, a.Real*b.Imaginary + a.Imaginary*b.Real);
    }
}

}

РЕДАКТИРОВАТЬ

GPU представляется единственным возможным решением;Я не обращаю внимания на совместимость с C / C ++, потому что не чувствую, что ускорение было бы достаточно значительным, чтобы заставить меня принудительно взаимодействовать с будущими плагинами.

После изучения доступных опций графического процессора (которыми я на самом деле былизучая в течение некоторого времени), я наконец нашел то, что я считаю превосходным компромиссом.Я выбрал OpenCL в надежде, что большинство устройств будут поддерживать стандарт к моменту выпуска моей программы. OpenCLTemplate использует cloo , чтобы обеспечить простой для понимания интерфейс между .Net (для логики приложения) и "OpenCL C99" (для параллельного кода).Плагины могут включать ядра OpenCL для аппаратного ускорения наряду со стандартной реализацией с System.Numerics.Complex для простоты интеграции.

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

Для тех, кто в будущем заинтересован в интеграции ускорения графического процессора с .NetПроект, я настоятельно рекомендую OpenCLTemplate.Есть допущенные накладные расходы на изучение OpenCL C99.Однако это лишь немного сложнее, чем изучение альтернативного API, и, вероятно, получит лучшую поддержку от примеров и общих сообществ.

Ответы [ 3 ]

2 голосов
/ 16 февраля 2011

Я думаю, что вам лучше всего смотреть на загрузку этих вычислений на видеокарту. Существует openCL, который может использовать видеокарты для такого рода вещей, а также использовать шейдеры openGL.

Чтобы по-настоящему воспользоваться этим, вы хотите рассчитывать параллельно. Допустим, вы хотите получить квадратный корень (простой, я знаю, но принцип тот же) 1 миллион чисел. На процессоре вы можете делать только одно по одному или вычислять, сколько у вас ядер, разумно ожидать, скажем, 8 ядер, и каждое из них должно выполнять вычисления на подмножестве данных.

Если вы, например, перенесете свои расчеты на видеокарту, вы «загрузите» в свои данные, скажем, кучу 1/4 миллиона трехмерных точек в пространстве (это четыре поплавка на вершину), а затем получите вершинный шейдер вычислить квадратный корень каждого xyzw каждой вершины. у видеокарт чертовски много ядер, даже если их всего 100, она все равно может работать на гораздо большем количестве, чем процессор.

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

EDIT

глядя на эту дешевую карту родственников NVIDEA GT 220 вы можете видеть, что у нее 48 ядер 'CUDA'. Это то, что вы используете, когда используете такие вещи, как openCL и шейдеры.

РЕДАКТИРОВАТЬ 2

Хорошо, похоже, вы довольно заинтересованы в использовании ускорения GPU. Я не могу помочь вам с использованием openCL, никогда не рассматривал его, но я предполагаю, что он будет работать во многом с теми же приложениями openGL / DirectX, которые используют шейдеры, но без реального графического приложения. Я собираюсь поговорить о вещах DirectX, так как это то, что я знаю (примерно), но, насколько я понимаю, это почти одинаково для openGL.

Во-первых, вам нужно создать окно. Если вам нужна кроссплатформенность, GLUT - это, вероятно, лучший путь, это не лучшая библиотека в мире, но она дает вам окно красиво и быстро. Поскольку вы фактически не собираетесь показывать какой-либо рендеринг, вы можете просто сделать его крошечным окном, достаточно большим, чтобы установить для заголовка что-то вроде «HARDWARE ACCELERATING».

Как только ваша видеокарта настроена и готова к рендерингу, вы переходите к этому этапу, следуя учебным пособиям . Это приведет вас к тому, что вы сможете создавать 3D-модели и «анимировать» их на экране.

Далее вы хотите создать буфер вершин, который вы заполняете входными данными. вершина обычно составляет три (или четыре) числа с плавающей точкой. Если все ваши ценности независимы, это круто. но если вам нужно сгруппировать их, скажем, если вы на самом деле работаете с 2D-векторами, то вам нужно убедиться, что вы правильно упаковали данные. скажем, вы хотите выполнять математику с 2D-векторами, а openGL работает с 3D-векторами, тогда vector.x и vector.y - это фактически входной вектор, а vector.z будет просто резервными данными.

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

Итак, вы установили буфер вершин и поместили его на видеокарту. Вам также нужно написать «вершинный шейдер», это текстовый файл с языком, подобным Си, который позволяет вам выполнять некоторые математические операции. Это не полная реализация C, но она выглядит достаточно похоже на C, чтобы вы знали, что делаете. Точные входы и выходы шейдеров openGL мне не известны, но я уверен, что простой урок достаточно легко найти.

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

ваш расчет будет выглядеть примерно так

createvertexbuffer()
loadShader("path to shader code", vertexshader) // something like this I think
// begin 'rendering'
setShader(myvertexshader)
setvertexbuffer(myvertexbuffer)
drawpoints() // will now 'draw' your points
readoutputbuffer()

Надеюсь, это поможет. Как я уже сказал, я все еще учусь этому, и даже тогда я изучаю DirectX.

0 голосов
/ 19 июня 2012

Делая вашу изменяемую структуру я получил 30%. Это уменьшает звонки и использование памяти

//instead of writing  (in TestCustomComplex())
vals[x, y] = vals[x, y] * vals[x, y] + loc[x, y];

//use
vals[x,y].MutableMultiAdd(loc[x,y]);

//defined in the struct as
public void MutableMultiAdd(Complex other)
    {
        var tempReal = (Real * Real - Imaginary * Imaginary) + other.Real;
        Imaginary =( Real * Imaginary + Imaginary * Real )+ other.Imaginary;
        Real = tempReal;
    }

Для Matrix Multiply вы также можете использовать «Unsafe {Fixed () {}}» и получать доступ к своим массивам. Используя это я получил 15% для TestCustomComplex ().

private static void TestCustomComplex()
    {
        var vals = new Complex[XL, YL];
        var loc = new Complex[XL, YL];

        for (int x = 0; x < XL; x++)
            for (int y = 0; y < YL; y++)
            {
                loc[x, y] = new Complex((x - XL / 2) / 256.0, (y - YL / 2) / 256.0);
                vals[x, y] = new Complex(0, 0);
            }

        unsafe
        {
            fixed (Complex* p = vals, l = loc)
            {
                for (int i = 0; i < ITER; i++)
                {
                    for (int z = 0; z < XL*YL; z++)
                    {
                        if (p[z].Real > 4) continue;
                        p[z] = p[z] * p[z] + l[z];
                    }
                }
            }
        }
    }
0 голосов
/ 16 февраля 2011

Лично, если это серьезная проблема, я бы создал DLL C ++, а затем использовал ее для выполнения арифметики.Вы можете вызвать этот плагин из C #, чтобы вы могли по-прежнему использовать преимущества WPF, рефлексии и т. Д.

Следует отметить, что вызов плагина не совсем «быстрый», поэтому вы хотите убедиться, что вы прошлиВСЕ ваши данные за один раз, и не называйте это очень часто.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...