Поиск совпадений в массиве на OpenCL

Тема в разделе "OpenCL", создана пользователем _qwe8013, 1 мар 2018.

  1. _qwe8013

    _qwe8013 Member

    Публикаций:
    2
    Регистрация:
    30 ноя 2016
    Сообщения:
    112
    Есть большой массив чисел ([math]2^{21}[/math] штук). Нужно найти такое же количество совпадений чисел в этом массиве (на самом деле их больше, но все не нужны). Решаю задачу на OpenCL следующим образом: создаю [math]2^{21}[/math] потоков, каждому соответствует одно из чисел, и сравниваю в каждом потоке это число с остальными (так, чтобы n-ое число с m-ым сравнивалось 1 раз) и в случае совпадения записываю пары индексов в выходной массив. Для доступа к массиву использую атомарные операции (см. Shader.cl в приложении). Запускаю код на моей карте GeForce GT 750M, всё вроде бы нормально, но при попытке чтения результата (clEnqueueReadBuffer) возвращается CL_OUT_OF_RESOURCES (хотя clCreateBuffer работает нормально). Если удалить код, пишущий в массив вместе atomic_cmpxchg, то ошибка проподает, как собственно и результат. Что мне с этим делать?
    ОС Win10 x64, карта GeForce GT 750M ноутбук.
     

    Вложения:

  2. TermoSINteZ

    TermoSINteZ Синоби даоса Команда форума

    Публикаций:
    1
    Регистрация:
    11 июн 2004
    Сообщения:
    3.020
    Адрес:
    Russia
    зачем вам тут атомики?
    каждый тред = индексу елемента в новом выходном массиве, ничего не перекрывается.
     
  3. _qwe8013

    _qwe8013 Member

    Публикаций:
    2
    Регистрация:
    30 ноя 2016
    Сообщения:
    112
    А если один тред найдёт несколько совпадений? Если например все числа кроме одного будут одинаковыми? На самом деле я не совсем верно написал условие: искать я буду все совпадения, просто порциями.
     
  4. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.036
    _qwe8013, правильное решение данной задачи:
    к каждому элементу цепляем его индекс и сортируем получившиеся пары по значениям
    на выходе получаем массив в котором элементы с одинаковыми значением будут рядом
    ну и соответственно далее можно записать это в файл в виде таких строк:
    имеется N элементов со значением X, индексы у них i1 i2 i3 ...
    имеется M элементов со значением Y индексы у них j1 j2 j3 ...

    кому будет нужно легко по этим строкам построит все возможные пары индексов
     
    TermoSINteZ нравится это.
  5. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    1.922
    Есть AVL деревья для быстрого поиска, это и должно использоваться, раз массив не линеен. Зачем нужны атомики представить сложно.
     
  6. _qwe8013

    _qwe8013 Member

    Публикаций:
    2
    Регистрация:
    30 ноя 2016
    Сообщения:
    112
    Буду делать с помощью сортировки, спасибо за ответы.
    PS
    Раз уж речь зашла об атомиках, они вообще как-либо серьёзно влияют на производительность?
     
  7. TermoSINteZ

    TermoSINteZ Синоби даоса Команда форума

    Публикаций:
    1
    Регистрация:
    11 июн 2004
    Сообщения:
    3.020
    Адрес:
    Russia
    _qwe8013, да, очень серьезно. Надо стараться их избегать. Особенно когда идет работа не с шаред мемори и с оч большим кол-вом потоков, где нельзя спрогнозировать, как много будет коллизий.
     
  8. _qwe8013

    _qwe8013 Member

    Публикаций:
    2
    Регистрация:
    30 ноя 2016
    Сообщения:
    112
    В общем последовал совету и стал сначала сортировать. Написал алгоритм сортировки на OpenCL и продублировал его на CPU. Так вот, начиная с размера массива [math]2^{12}[/math] алгоритм на OpenCL начинает выдавать некорректный результат (результат не отсортирован) на любом OpenCL устройстве, хотя CPU отрабатывает корректно. Ткните идиота в ошибку.
     

    Вложения:

    • OpenCLError.zip
      Размер файла:
      4,7 КБ
      Просмотров:
      32
  9. _qwe8013

    _qwe8013 Member

    Публикаций:
    2
    Регистрация:
    30 ноя 2016
    Сообщения:
    112
    В общем выяснил, что в шейдере в цикле по переменной "i" В КОНЦЕ КОТОРОГО СТОИТ barrier(CLK_GLOBAL_MEM_FENCE) почему-то некоторые потоки исполняют первую итерацию когда другие исполняют ещё только нулевую WTF?
     

    Вложения:

    • Shader.txt
      Размер файла:
      2,5 КБ
      Просмотров:
      122