Решение задачи выполнимости cnf

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

  1. __constant__ int constVec[10000];
  2. __global__ void Search(int K, int M, int num_it, int p_num, int l_num, int * prob, int * best_num){
  3.  
  4.         int i, j, b, h, d, s;
  5.         int Eli, veci;
  6.  
  7.         int idx = blockIdx.x * blockDim.x + threadIdx.x;
  8.  
  9.         int p_numId = idx * p_num;
  10.         int p_numId1 = idx * (p_num + 1);
  11.         int l_numId = idx * l_num;
  12.         int it_Id = idx * num_it;
  13.  
  14.         __shared__ int mul[32]; // NUM_THREADS
  15.         __shared__ int gprob[544]; // (p_num + 1)* NUM_THREADS
  16.         __shared__ int res[2688]; // l_num * NUM_THREADS
  17.         __shared__ char str[672]; // p_num*l_num
  18.  
  19.         for (i = 0; i < l_num; i++){
  20.                 str[p_numId + i] = 48; // В этом векторе будем хранить знаачение переменных в соотв дизъюнкте
  21.         }
  22.  
  23.         for (i = 0; i < M; i++){
  24.                 best_num[i] = 0; // Здесь будем хранить номер набора, на котором удалось разрешить формулу. Если набор найден, ставим его номер. Если нет, 0.
  25.         }
  26.  
  27.  for (Eli = it_Id; Eli < it_Id + num_it; Eli++, i++){
  28.                 for (i = 0; i < l_num; i++){
  29.                         res[l_numId + i] = 0;
  30.                 }
  31.                 for (i = 0; i < threadIdx.x; i++){
  32.                         mul[i] = 1;
  33.                 }
  34.                 for (j = 0; j <= p_num; j++){
  35.                         gprob[p_numId1 + j] = 999;
  36.                 }
  37.  
  38.                 // Перевод номера набора в двоичный вид
  39.  
  40.                 i = 0;
  41.  
  42.                 b = Eli;
  43.  
  44.                 // Вычисляем значение набора переводя его номер в двоичную систему.
  45.                 while (b != 0){
  46.                         if((abs(b)%2) != 0){
  47.                                 str[p_numId + i] = '1';
  48.                         } else {
  49.                                 str[p_numId + i] = '0';
  50.                         }
  51.                         i++;
  52.                         b = abs(b) / 2;
  53.                 }
  54.  
  55.                 d = 0;
  56.                 s = 0;
  57.  
  58.                 // подсчет значений результатов дезъюнктов
  59.  
  60.                 for (j = 0; j < K; j++){
  61.                         gprob[p_numId1 + s] = constVec[j];
  62.                         prob[j] = constVec[j];
  63.  
  64.                         if (constVec[j] == 100500){
  65.                                 for (i = 0; i < p_num; i++){
  66.                                         for (veci = 0; veci < p_num; veci++){
  67.                                                 if (gprob[p_numId1 + veci] == (i + 1)){
  68.                                                         gprob[p_numId1 + veci] = str[p_numId + i] - 48;
  69.                                                 } else if (gprob[p_numId1 + veci] == -(i + 1)){
  70.                                                         gprob[p_numId1 + veci] = !(str[p_numId + i] - 48);
  71.                                                 }
  72.                                         }
  73.                                 }
  74.                                 for (h = 0; h < p_num; h++){
  75.                                         if (gprob[p_numId1 + h] != 100500){
  76.                                                 res[l_numId + d] = gprob[p_numId1 + h] || res[l_numId + d];
  77.                                         } else {
  78.                                                 h = p_num;
  79.                                         }
  80.                                 }
  81.                                 if (res[l_numId + d] == 0){
  82.                                         break;
  83.                                 }
  84.                                 d++;
  85.                                 s = 0;
  86.                         } else {
  87.                                 s++;
  88.                         }
  89.  
  90.                 }
  91.  
  92.                 // Вычисление конъюнкции полученных на предыдущем шаге дезъюнктов формулы
  93.                 for (j = 0; j < l_num; j++){
  94.                         mul[threadIdx.x] = mul[threadIdx.x] && res[l_numId + j];
  95.                 }
  96.                 if (mul[threadIdx.x] == 1){
  97.                         best_num[Eli] = Eli;
  98.                 }
  99.         }
  100. }

Forums: 

вроде в тэгах стало довольно

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

Хочется посоветоваться

Хочется посоветоваться насколько неэффективный алгоритм я реализовал...
очень неэффективный. Массив символов для хранения нулей и единиц (в символьном виде!) и т.п.

или вообще посоветуете отказаться от подобного решения

да, советую отказаться от подобного решения.

Первое что пришло на ум, это следующий подход:
-один поток проверяет один или несколько наборов значений переменных.
-номер набора из целого(если переменных больше чем битов в самом большом доступном целом, то можно использовать несколько целых..) никуда не надо переводить - каждый бит, показывает значение соответствующей переменной
-сама кнф хранится в таком виде, в котором её дизъюнкты можно за пару операций применить к набору значений(которые хранятся в одном или нескольких целых). Например, каждый дизъюнкт хранится в виде двух целых(или 2*N, в зависимости от количества целых на один набор значений), одно из целых представляет собой AND-маску используемых в данном дизъюнкте переменных, другое является xor-маской предназначенной для "отрицаний" (нулевые биты, на позициях где нет отрицаний;единичные биты на позициях где есть отрицание). Сначала применяется xor-маска, потом and-маска (в принципе, если добавить небольшое уточнение в описание xor-маски, то порядок не важен.. но это не так важно сейчас..). Если полученное целое число не равно 0, то результат этого дизъюнкта истина, если 0 то ложь.
-результаты всех дизъюнктов хранить не обязательно...

P.S. Что это за курсовая работа, которая длится три семестра?? http://www.gpgpu.ru/node/222

Спасибо большое за ответ

Спасибо большое за ответ J0hn.
Постараюсь воспользоваться советом.. Но вот по неподтвержденной информации... слышал, что работа с битами на cuda очень медленная... Никогда не сталкивался?

p.s. работа слегка переросла.. вот занимаюсь ей дальше