С/С++ вопрос. - Алгоритмы

Здравствуйте, shadows_s, Вы писали:

_>Программа, для вычисления интегралов,
То есть, на самом деле, нет никакого смысла в полноценном С или в С++. А вместо этого нужно уметь вычислять только формулы?

_>Что посоветуете оставить то что есть, или обязательно пробовать использовать внешние компиляторы и PTX?
Ну, я вижу несколько реалистичных вариантов, если все делать самому:

Использовать nvcc. Самый быстрый и простой способ. Недостаток один — нужен nvcc.
Разобраться с генерацией PTX-файлов. Для математических формул это сделать не сложно. Соответственно, загружать после этого на GPU код в виде PTX.
Реализовать в ядре на GPU простой интерпретатор байт-кода. То есть превращать текстовую запись формулы в последовательность команд для своего стекового вычислителя, например, и исполнять эту программу на GPU. Недостаток очевиден — ощутимые потери на интерпретацию. Нужно попробовать сделать прототип и понять, устраивает ли полученная производительность.

И разумеется, для счёта формул на GPU можно взять уже готовые реализации, коих множество, в которых все эти варианты уже помногу раз сделаны.
Берёшь, например, первый попавшийся проект типа PyCUDA в котором код просто хранится как строчки и смотришь как это у них сделано. Либо вообще сразу его начинаешь использовать.

Здравствуйте, shadows_s, Вы писали:

WM>>Здравствуйте, shadows_s, Вы писали:

_>На одном из этапов, нужно вычыслить функцию при всемозможных входных параметрах.
_>в опщем, нужно получить что-нибуть вида:
_>

_>__global__ void integral_kernel ( float * result_array )
_>{
_>        // ...код
_>    value = ФУНКЦИЯ_ВВЕДЕНАЯ_ПОЛЬЗОВАТЕЛЕМ( x, y ); 
_>}
_>

_>Вся проблема, в том как ефективно реализовать эту функцию.
Эффективно — это отдать эту задачу на откуп CUDA. Там уже внутри реализован один компилятор для PTX. Сложно (и даже вредно) пытаться писать при этом свой.
А вот PTX код уже можно получать или через nvcc или генерировать самостоятельно — вот тут есть свобода выбора.

_>А использование интерпретатора, заметно снижает производительность, что воопще ставит под сомнение целесообразность использовать CUDA...

Ну это не совсем правильная идея.
Если код может быть эффективно распараллелен, то CUDA позволяет его значительно ускорить. При этом будет ускоряться как изначально медленный, так и изначально быстрый код.
Просто иногда дешевле переписать исходный код. А иногда дешевле запустить медленный код на GPU. А вот одновременно оптимизировать код и переписывать его на CUDA нужно реже. Хотя, конечно, выигрыш в производительности в последнем случае получается самым большим, с этим не поспоришь.

Здравствуйте, shadows_s, Вы писали:

_>Подскажите пожалуйста.
_>У меня есть некоторый участок кода, например:
_>some_var = x + y;
_>нужно x + y заменять на функцию, которая вводится с клавиатуры,
_>каким методом это лучше организовать ?
_>Первое, что пришло на ум, сделать с помощью синтаксического анализатора.
_>Быстродействие играет большую роль, так как пишу программу под CUDA C.
_>Спасибо.

вам надо встроить интерпретатор или компилятор
ни в С ни в С++ аналогов eval() нет

Здравствуйте, shadows_s, Вы писали:

_>Быстродействие играет большую роль, так как пишу программу под CUDA C.
Так где у тебя этот код должен исполнятся? На CPU или на GPU?
В любом случае, если важна производительность, то нужен компилятор. Тут есть два варианта — либо готовый внешний компилятор, либо нечто, способное формировать код на лету. Первый вариант, как правило, проще. У второго чуть ниже накладные расходы. Но по скорости работы производимого кода они в целом равнозначны.

Итого:
Если брать CPU и внешний компилятор, то выбор просто огромен. Берешь любой. Передаёшь ему свой код и забираешь, например, в виде динамической библиотеки. Если же хочется на CPU компилировать внутри одного процесса, то можно взять что-то готовое, наприме libtcc.
В случае же GPU можно взять, очевидно, компилятор nvcc. Если же делать без него, то в CUDA можно редактировать и динамически загружать PTX-модули, полученные из исходного текста на C/C++. К сожалению, насколько я помню, напрямую компиляция из C-кода в CUDA недоступна — это возможно, но просто недоступен соответствующий API, хотя в том же OpenCL (который может полноценно работать в виде обёртки над CUDA) соответствующий API есть. Впрочем это не серьёзное техническое затруднение, для кодогенерации и PTX вполне может подойти; либо, конечно, можно посмотреть на OpenCL.

_>Первое, что пришло на ум, сделать с помощью синтаксического анализатора.
Это совсем дохлый путь. Eсли нужен транслятор, то только анализатором не обойтись.

Здравствуйте, Abyx, Вы писали:

A>ни в С ни в С++ аналогов eval() нет

прикрутить V8, например (ну или еще че-нить, имеющее JIT: luajit, ...)

Здравствуйте, shadows_s, Вы писали:

_>Подскажите пожалуйста.
_>У меня есть некоторый участок кода, например:
_>some_var = x + y;
_>нужно x + y заменять на функцию, которая вводится с клавиатуры,
_>каким методом это лучше организовать ?
_>Первое, что пришло на ум, сделать с помощью синтаксического анализатора.
_>Быстродействие играет большую роль, так как пишу программу под CUDA C.
_>Спасибо.

я бы посоветовал OpenCL — там код компилируется в runtime.
будет просто конкатенация строк.

Здравствуйте, shadows_s, Вы писали:

_>Подскажите пожалуйста.
_>У меня есть некоторый участок кода, например:
_>some_var = x + y;
_>нужно x + y заменять на функцию, которая вводится с клавиатуры,
_>каким методом это лучше организовать ?
Либо писать компилятор.. Плюсы, минусы и варианты тут уже популярно объяснили. Думаю нужно что-то в консерватории поменять. А именно сам проект в части ввода данных. Есть еще один вариант если все фунции заранее известны. Ну, этот вариант и сам способен реализовать.. Например, выбором функции из списка..

_>нужно x + y заменять на функцию, которая вводится с клавиатуры,
_>каким методом это лучше организовать ?

Или так:

(+ x y)

Или польская инверсная запись, но Lisp круче!

Подскажите пожалуйста.
У меня есть некоторый участок кода, например:
some_var = x + y;
нужно x + y заменять на функцию, которая вводится с клавиатуры,
каким методом это лучше организовать ?
Первое, что пришло на ум, сделать с помощью синтаксического анализатора.
Быстродействие играет большую роль, так как пишу программу под CUDA C.
Спасибо.

Здравствуйте, watch-maker, Вы писали:

WM>Так где у тебя этот код должен исполнятся? На CPU или на GPU?
На GPU.

WM>Это совсем дохлый путь. Eсли нужен транслятор, то только анализатором не обойтись.

На, данном этапе написал транслятор, образно говоря — мини калькулятор со встроенными математическими функциями и возможностью определения своих функций,
так если пишу например f(x,y)=sin(x)+cos(y)*2 то транслятор, анализирует типы токенов и записывает их в список.
Далее при вводе f(2,2), транслятор поочерёдно выполняет указанные в списке, и всё работает, результат правильный.

Программа, для вычисления интегралов, так что на GPU будет запущено несколько сотен тысяч нитей исполняющих данную функцию, но с разными x, y.
В общем, то что я сделал, кажется очень-очень примитивным.
Что посоветуете оставить то что есть, или обязательно пробовать использовать внешние компиляторы и PTX? *OpenCL, увы, нельзя использовать.

WM>Здравствуйте, shadows_s, Вы писали:

WM>То есть, на самом деле, нет никакого смысла в полноценном С или в С++. А вместо этого нужно уметь вычислять только формулы?
Если не вдаватся в подробности, то:
Решается задача вычисления двойных интегралов на заданой областе интегрирования.
На одном из этапов, нужно вычыслить функцию при всемозможных входных параметрах.
в опщем, нужно получить что-нибуть вида:

__global__ void integral_kernel ( float * result_array )
{
        // ...код
    value = ФУНКЦИЯ_ВВЕДЕНАЯ_ПОЛЬЗОВАТЕЛЕМ( x, y ); 
}

Вся проблема, в том как ефективно реализовать эту функцию.

WM>

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

WM>

Реализовать в ядре на GPU простой интерпретатор байт-кода. То есть превращать текстовую запись формулы в последовательность команд для своего стекового вычислителя, например, и исполнять эту программу на GPU. Недостаток очевиден — ощутимые потери на интерпретацию. Нужно попробовать сделать прототип и понять, устраивает ли полученная производительность.[/list]

Да, я сначала и пошел этим путём, но хочется большей ефективности.
А использование интерпретатора, заметно снижает производительность, что воопще ставит под сомнение целесообразность использовать CUDA...

Здравствуйте, watch-maker, Вы писали:

_>>Вся проблема, в том как ефективно реализовать эту функцию.

__global__ void fn1_kernel ( float * result_array ) { value = fn1( x, y );  }
__global__ void fn2_kernel ( float * result_array ) { value = fn2( x, y );  }
....
__global__ void fnN_kernel ( float * result_array ) { value = fnN( x, y );  }

Пользователю позволить выбирать fn1 .. fnN
А так просто делаешь обычный компилятор для стековой машины (можешь глянуть книжку)
которая будет тебе генерить c-код для компилятора cudы
парсишь функцию и строишь граф вычислений. оптимизируешь граф (разные тождественные преобразования). генериш код по графу.
потом его в тихоря компилишь и загружаешь на исполнение.

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

struct Compiler {
  Cgen cgen;
  Parser p;
  void compile() {
    compile_expression();
  }
  void compile_expression() {
    cgen.write("__global__ void expr_kernel ... {\n");
    r=0;
    int r1=L1();
    cgen.write("value=r%d;\n",r1);
    cgen.write("}\n");
  }
  int r; int allocReg(){ return ++r; }
  int L1() {
    int r1=L2();
    switch(p.get()) {
      case '+': { int r3=allocReg(); int r2=L2(); cgen.write("r%d=r%d + r%d;\n",r3,r1,r2); return r3; }
      case '-': { int r3=allocReg(); int r2=L2(); cgen.write("r%d=r%d - r%d;\n",r3,r1,r2); return r3; }
      ...
    }
    return r1;
  }
  int L2() {
    int r1=L3();
    switch(p.get()) {
      case '*': { int r3=allocReg(); int r2=L2(); cgen.write("r%d=r%d * r%d;\n",r3,r1,r2); return r3; }
      case '/': { int r3=allocReg(); int r2=L2(); cgen.write("r%d=r%d / r%d;\n",r3,r1,r2); return r3; }
      ...
    }
    return r1;
  }
  ...
  int L5() {
    if (p.check('(')) {
      int r1=L1();      
      if (!p.check(')')) throw_error("no closing )");
      return r1;
    }
    return L6();
  }
  int L6() { // digits, consts, variables, functions 
    int sign=+1;
    if (p.check('-')) sign=-1;
    int digit=p.getDigit();
    if (sign<0) digit=-digit;
    int r1=allocReg();
    cgen.write("r%d=%d;\n",r1,digit);
    return r1;
  }
}

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

_>>А использование интерпретатора, заметно снижает производительность, что воопще ставит под сомнение целесообразность использовать CUDA...
а нафига интерпритатор на куде? интерприти на пц и заливай в кодовские ядра готовый код.

WM>Если код может быть эффективно распараллелен, то CUDA позволяет его значительно ускорить. При этом будет ускоряться как изначально медленный, так и изначально быстрый код.
WM>Просто иногда дешевле переписать исходный код. А иногда дешевле запустить медленный код на GPU. А вот одновременно оптимизировать код и переписывать его на CUDA нужно реже. Хотя, конечно, выигрыш в производительности в последнем случае получается самым большим, с этим не поспоришь.
грамотно распараллелить это искусство. так что пиши в ручную.

	От:	watch-maker
	Дата:	15.05.12 13:38
	Оценка:	3 (1) +2

	От:	watch-maker
	Дата:	15.05.12 15:26
	Оценка:	3 (1) +2

	От:	Abyx
	Дата:	14.05.12 18:51
	Оценка:	4 (2)

	От:	watch-maker
	Дата:	14.05.12 20:29
	Оценка:	3 (1) +1

	От:	marat321
	Дата:	14.05.12 20:18
	Оценка:	2 (1)