Как переложить задачу на GPU?

@nigri_lupus · Регистрация: 14.12.2020

Студворк — интернет-сервис помощи студентам

Здравствуйте, много слышал о работе с GPU. О том, что GPU используется в задачах по вычислению и бруту кричит весь интернет, приводя примеры начиная от майнинга и заканчивая сложением матриц.
Но КАК работать с GPU, как к нему обратиться-то?
к примеру, переложить на GPU-шные плечи следующий код:

PureBasic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
Width=8000 
Height=8000 
Dim a(Width,Height,7)
Dim b(Width,Height,7)
 
;  для теста рандомом заполняются 
 
For y=0 To Height
  For x=0 To Width
    For n=0 To 7
a(x,y,n)=Random(5000)
b(x,y,n)=Random(5000)
Next
Next
Next
 
 
; ОСНОВНОЙ АЛГОРИТМ ВЫЧИСЛЕНИЯ!
 
For y=0 To Height
  For x=0 To Width
    For n=0 To 7
      If Max_a<a(x,y,n)
        Max_a=a(x,y,n)
      EndIf
      If Min_a>a(x,y,n)
        Min_a=a(x,y,n)
      EndIf
      
      If Max_b<b(x,y,n)
        Max_b=b(x,y,n)
      EndIf
      If Min_b>b(x,y,n)
        Min_b=b(x,y,n)
      EndIf
    Next
  Next
Next
 
For depth_a=Min_a To Max_a
  For depth_b=Min_b To Max_b
    For y=0 To Height
      For x=0 To Width
        For n=0 To 7
          If a(x,y,n)<=depth_a
            drowned_a+1
          Else
            Not_drowned_a+1
          EndIf
          If b(x,y,n)<=depth_b
            drowned_b+1
          Else
            Not_drowned_b+1
          EndIf
          If ((a(x,y,n)<=depth_a) And (b(x,y,n)<=depth_b)) Or ((a(x,y,n)>depth_a) And (b(x,y,n)>depth_b))
            ruler_coincidence+1
          EndIf
        Next
        If drowned_a<8 And drowned_b<8 And not_drowned_a<8 And not_drowned_b<8 And ruler_coincidence=8
          glass_coincidence+1
        EndIf
        drowned_a=0
        Not_drowned_a=0
        drowned_b=0
        Not_drowned_b=0
        ruler_coincidence=0
      Next
    Next
    If Max_glass_coincidence<glass_coincidence
      Max_glass_coincidence=glass_coincidence
    EndIf
    glass_coincidence=0
  Next
Next
result=Max_glass_coincidence

@VTsaregorodtsev · 15.10.2023, 09:27

Сообщение от nigri_lupus

к примеру, переложить на GPU-шные плечи следующий код:

С точки зрения процессора - данный код упирается в память, а не в вычисления.
Просто посчитай размеры массивов в байтах - и сравни их с размерами кэша процессора.

@nigri_lupus · 15.10.2023, 11:18 **[ТС]**

VTsaregorodtsev, размер массивов тут, конечно.....большой...не спорю....
Но допустим, у нас в какой-то игре (типа "герои 3") warcraft и т.п. Там есть карта....немаленькая скажу я Вам, (ни один экран)
Так вот при скроллинге она перерисовывет все точки экрана, причем так быстро, что саму перерисоаку пользователь не замечает. (это я к тому, что обработать большущее кол-во информации за короткий промежуток времени возможно) Знать бы как...

@locm · 15.10.2023, 15:00

GPU не может выполнять код Intel x86/x64.

@VTsaregorodtsev · 15.10.2023, 15:41

Сообщение от nigri_lupus

(это я к тому, что обработать большущее кол-во информации за короткий промежуток времени возможно) Знать бы как...

Так и процессор тоже может.
Как 1: надо использовать SIMD-команды процессора. Или написанием кода ручками на ассемблере - или применением векторизующего компилятора (т.е. если Pure Basic сам в векторизацию не умеет - то ой).
Как 2: надо уделять внимание организации данных в памяти. Например, первый строенный цикл в коде (там, где максимумы-минимумы вычисляются) можно переписать в виде одиночного цикла с числом итераций Height*Width*8 - т.е. для доступа к элементу массива не потребуется вычислять его адрес с использованием аж трёх прежних переменных (плюс ещё указатель на начало массива). Но это в случае, если выделение памяти для многомерного массива происходит без вставки каких-либо невидимых элементов для "выравнивания" длин блоков данных (иначе вместо трёхмерного массива надо будет сделать одномерный массив).

@nigri_lupus · 15.10.2023, 17:47 **[ТС]**

Сообщение от VTsaregorodtsev

Как 1: надо использовать SIMD-команды процессора. Или написанием кода ручками на ассемблере - или применением векторизующего компилятора (т.е. если Pure Basic сам в векторизацию не умеет - то ой)

Ассемблер для меня одно сплошное ОЙ-Е-ОЙ. Умеет ли Pure Basic в векторизацию - понятия не имею. А что такое SIMD-команды процессора? Я конечно погугдю на это тему, но сам вряд ли что-то пойму...

Сообщение от VTsaregorodtsev

иначе вместо трёхмерного массива надо будет сделать одномерный массив

Да заменить трехмерные массивы одномерными - не беда... даст ли это более-менее ощутимое ускорение...?Вот в чем вопрос...

Сообщение от VTsaregorodtsev

надо уделять внимание организации данных в памяти. Например, первый строенный цикл в коде (там, где максимумы-минимумы вычисляются)

Меня лично пугает кусок кода, начинающийся с 40-й строки.... там аж 5 циклов....
Вот чуток более оптимизированная версия того же кода (пока еще с той же мерностью массивов)

PureBasic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
Width=7700 ; Максимально возможное значение Ширина ванной
Height=4400 ; Максимально возможное значение Высота ванной
Dim a(Width,Height,7)
Dim b(Width,Height,7)
 
; Исключительно для теста рандомом заполняются 
; размеры "линеек"
For y=0 To Height
  For x=0 To Width
    For n=0 To 7
a(x,y,n)=Random(5000)
b(x,y,n)=Random(5000)
Next
Next
Next
 
; ОСНОВНОЙ АЛГОРИТМ ВЫЧИСЛЕНИ!
Dim unic_a_test(5000)
Dim unic_b_test(5000)
Dim unic_a(Width*Height)
Dim unic_b(Width*Height)
For y=0 To Height
  For x=0 To Width
    For n=0 To 7
      If unic_a_test(a(x,y,n))=0
        unic_a_test(a(x,y,n))=1
        unic_a(unic_a_num)=a(x,y,n)
        unic_a_num+1
      EndIf
If unic_b_test(b(x,y,n))=0
        unic_b_test(b(x,y,n))=1
        unic_b(unic_b_num)=b(x,y,n)
        unic_b_num+1
      EndIf
    Next
  Next
Next
unic_a_num-1
unic_b_num-1
SortArray(unic_a(), #PB_Sort_Ascending, 0, unic_a_num)
SortArray(unic_b(), #PB_Sort_Ascending, 0, unic_b_num)
 
For LIST_a=0 To unic_a_num
For LIST_b=0 To unic_b_num
  depth_a=unic_a(LIST_a)
  depth_b=unic_b(LIST_b)
    For y=0 To Height
      For x=0 To Width
        For n=0 To 7
          If a(x,y,n)<=depth_a
            drowned_a+1
          Else
            Not_drowned_a+1
          EndIf
          If b(x,y,n)<=depth_b
            drowned_b+1
          Else
            Not_drowned_b+1
          EndIf
          If ((a(x,y,n)<=depth_a) And (b(x,y,n)<=depth_b)) Or ((a(x,y,n)>depth_a) And (b(x,y,n)>depth_b))
            ruler_coincidence+1
          EndIf
        Next
        If drowned_a<8 And drowned_b<8 And not_drowned_a<8 And not_drowned_b<8 And ruler_coincidence=8
          glass_coincidence+1
        EndIf
        drowned_a=0
        Not_drowned_a=0
        drowned_b=0
        Not_drowned_b=0
        ruler_coincidence=0
      Next
    Next
    If Max_glass_coincidence<glass_coincidence
      Max_glass_coincidence=glass_coincidence
    EndIf
    glass_coincidence=0
  Next
Next
result=Max_glass_coincidence

Оптимизация тут заключается в том, что перебираются не все значения depth_a и depth_b от минимума, до максимума, а лишь уникальные из них....
Еще бы придумать как сделать так, чтобы перебирались не все группы чисел a(x,y,n) и b(x,y,n) на которые depth_a и depth_b как-то влияют....
А то ведь сколько не сравнивай группу чисел, допустим A : 150, 299, 50, 100,150,200,300,500 c depth_a в интервале от 50-99, а результат будет одни: 1, 1, 0, 1,1,1,1,1. (лишние итерации) только вот я пока не придумал как правильно это сделать.)

Добавлено через 2 минуты
locm, Может я путаю горячее, с плоским, но как же тогда работают программы-майнеры, использующие видеокарту под 32-битным windows?

@nigri_lupus · 16.10.2023, 10:34 **[ТС]**

VTsaregorodtsev, Начал переписывать алгоритм на основе одномерных массивов и сражу же столкнулся с загадкой....
Если написать :

PureBasic
1
2
3
4
Width=7700 ; Максимально возможное значение Ширина ванной
Height=4400 ; Максимально возможное значение Высота ванной
Dim a(Width,Height,7)
Dim b(Width,Height,7)

Машина выдает ошибку - невозможен доступ к памяти.
Если же написать:

PureBasic
1
2
3
4
5
6
7
 Width=7700 ; Максимально возможное значение Ширина ванной
Height=4400 ; Максимально возможное значение Высота ванной
; Dim a(Width,Height,7)
; Dim b(Width,Height,7)
 
Dim a(Width*Height*8)
Dim b(Width*Height*8)

Ошибки не возникает.
В чем разница-то?
Тип массивов одинаковый, у второй пары даже размер чуть побольше, но в первом случае ошибка есть, а во втором нет. Почему?

@VTsaregorodtsev · 16.10.2023, 10:46

nigri_lupus, я бейсиком не пользовался уже 30+ лет

А Pure Basic я вообще никогда не видел.
Т.е. в тему я зашёл просто посмотреть "кто виноват (задача / алгоритм / транслятор / процессор) и что делать" - и оценить расхождение своего мнения с мнениями других.

@nigri_lupus · 16.10.2023, 11:05 **[ТС]**

Сообщение от VTsaregorodtsev

я бейсиком не пользовался уже 30+ лет
А Pure Basic я вообще никогда не видел.
Т.е. в тему я зашёл просто посмотреть "кто виноват (задача / алгоритм / транслятор / процессор) и что делать" - и оценить расхождение своего мнения с мнениями других.

Бывает...

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

@Usaga · 16.10.2023, 11:09

Сообщение от nigri_lupus

Но допустим, у нас в какой-то игре (типа "герои 3") warcraft и т.п. Там есть карта....немаленькая скажу я Вам, (ни один экран)
Так вот при скроллинге она перерисовывет все точки экрана, причем так быстро, что саму перерисоаку пользователь не замечает.

Warcraft 2 тоже имел не маленькие карты, но рисовал всё исключительно силами процессора. И быстро это делал.

@nigri_lupus · 16.10.2023, 11:18 **[ТС]**

Сообщение от Usaga

Warcraft 2 тоже имел не маленькие карты, но рисовал всё исключительно силами процессора. И быстро это делал.

Причем настолько быстро, что сейчас на своей машине(а она у меня старенькая) я в него играть не могу - карта улетает - буквально! Просто отреагировать не успеваю....

Но вот КАК Warcraft 2 это делал? Через обычный cpu или использовал встроенный в материнку граф. процессор - я не знаю...

@Usaga · 16.10.2023, 11:22

Сообщение от nigri_lupus

Но вот КАК Warcraft 2 это делал? Через обычный cpu или использовал встроенный в материнку граф. процессор - я не знаю...

Через CPU. Инструкциями пакетного копирования байтов. Тогда все игры так работали - напрямую с видеопамятью. Видеопроцессоры тех лет вообще без ускорителя были.

@nigri_lupus · 16.10.2023, 12:20 **[ТС]**

VTsaregorodtsev, тики переписал код в виде одномерных массивов:

PureBasic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
Width=7700 ; Максимально возможное значение Ширина ванной
Height=4400; Максимально возможное значение Высота ванной
Size=Width*Height*8-1
Dim a.u(Size)
Dim b.u(Size)
Dim Temp_a.u(7)
Dim Temp_b.u(7)
Dim unic_a.u(5000)
Dim unic_b.u(5000)
Dim unic_a_test.a(5000)
Dim unic_b_test.a(5000)
j.a=0
For i=0 To Size
  a(i)=Random(500)
  b(i)=Random(500)
Next
 
Size-8
For i=0 To Size Step 8
  FillMemory(@Temp_a(0) , 16 , a(i) ,#PB_Unicode)
  If CompareMemory(@Temp_a(0) , @a(i) , 16)
    a(i)=5001  
  Else
    FillMemory(@Temp_b(0) , 16 , b(i) ,#PB_Unicode)
    If CompareMemory(@Temp_b(0) , @b(i) , 16)
      a(i)=5001
    Else
      For j=0 To 7
        ZU=i+j
        If unic_a_test(a(zu))=0
          unic_a_test(a(zu))=1
          unic_a(unic_a_num)=a(zu)
          unic_a_num+1
        EndIf
        If unic_b_test(a(zu))=0
          unic_b_test(a(zu))=1
          unic_b(unic_a_num)=a(zu)
          unic_b_num+1
        EndIf
      Next 
    EndIf
  EndIf
Next 
unic_a_num-1
unic_b_num-1
 
For LIST_a=0 To unic_a_num
  For LIST_b=0 To unic_b_num
    depth_a=unic_a(LIST_a)
    depth_b=unic_b(LIST_b)
    For i=0 To Size Step 8
      If a(i)<5001
        For j=0 To 7
          ZU=i+j
          If (a(ZU)<=depth_a And b(ZU)<=depth_b) Or (a(ZU)>depth_a And b(ZU)>depth_b)   
            ruler_coincidence+1
          EndIf
        Next
        If ruler_coincidence=8
          glass_coincidence+1
        EndIf
        ruler_coincidence=0
      EndIf
    Next
    If Max_glass_coincidence<glass_coincidence
      Max_glass_coincidence=glass_coincidence
    EndIf
  Next
Next
result=Max_glass_coincidence

@Quiet Snow · 09.11.2023, 19:09

Сообщение от nigri_lupus

Но вот КАК Warcraft 2 это делал? Через обычный cpu или использовал встроенный в материнку граф. процессор - я не знаю...

Варик второй как гласит вики написан под кучу платформ. Под DOS это чистое CPU.
Под Windows скорее всего первые версии DirectDraw, которые в те времена были очень быстрые.
Плюсом идёт максимальная оптимизация программ тех лет. Проги середины нулевых уже писали
на порядок хуже.

Как правильно упомянул locm, GPU не может выполнить x86\x64 код, там используется
сильное распараллеливание на сотни и тысячи ядер, не каждый алгоритм можно этому подвергнуть,
т.е. это технологии OpenCL или CUDA. Примеры с OpenCL скорее всего можно найти на пурике,
насчёт CUDA - предположу, что нет, т.к. это прерогатива плюсов и тамошнего SDK.

Новые блоги и статьи Все статьи Все блоги /
JWT аутентификация в ASP.NET Core UnmanagedCoder 18.06.2025 Разрабатывая веб-приложения, я постоянно сталкиваюсь с дилеммой: как обеспечить надежную аутентификацию пользователей без ущерба для производительности и масштабируемости? Классические подходы на. . .	Краткий курс по С# aaLeXAA 18.06.2025 Здесь вы найдете все необходимые функции чтоб написать програму на C# Задание 1: КЛАСС FORM 1 public partial class Form1 : Form { Spisok listin = new Spisok(); . . .	50 самых полезных примеров кода Python для частых задач py-thonny 17.06.2025 Эффективность работы разработчика часто измеряется не количеством написаных строк, а скоростью решения задач. Готовые сниппеты значительно ускоряют разработку, помогают избежать типичных ошибок и. . .	C# и продвинутые приемы работы с БД stackOverflow 17.06.2025 Каждый . NET разработчик рано или поздно сталкивается с ситуацией, когда привычные методы работы с базами данных превращаются в источник бессонных ночей. Я сам неоднократно попадал в такие ситуации,. . .	Angular: Вопросы и ответы на собеседовании Reangularity 15.06.2025 Готовишься к техническому интервью по Angular? Я собрал самые распространенные вопросы, с которыми сталкиваются разработчики на собеседованиях в этом году. От базовых концепций до продвинутых. . .
Архитектура Onion в ASP.NET Core MVC stackOverflow 15.06.2025 Что такое эта "луковая" архитектура? Термин предложил Джеффри Палермо (Jeffrey Palermo) в 2008 году, и с тех пор подход только набирал обороты. Суть проста - представьте себе лук с его. . .	Unity 4D GameUnited 13.06.2025 Четырехмерное пространство. . . Звучит как что-то из научной фантастики, правда? Однако для меня, как разработчика со стажем в игровой индустрии, четвертое измерение давно перестало быть абстракцией из. . .	SSE (Server-Sent Events) в ASP.NET Core и .NET 10 UnmanagedCoder 13.06.2025 Кажется, Microsoft снова подкинула нам интересную фичу в новой версии фреймворка. Работая с превью . NET 10, я наткнулся на нативную поддержку Server-Sent Events (SSE) в ASP. NET Core Minimal APIs. Эта. . .	С днём независимости России! Hrethgir 13.06.2025 Решил побеседовать, с утра праздничного дня, с LM о завоеваниях. То что она написала о народе, представителем которого я являюсь сам сначала возмутило меня, но дальше только смешило. Это чисто. . .	Лето вокруг. kumehtar 13.06.2025 Лето вокруг. Наполненное бурями и ураганами событий. На фоне магии Жизни, священной и вечной, неумелой рукой человека рисуется панорама душевного непокоя. Странные серые краски проникают и. . .

@nigri_lupus 3 / 3 / 0 Регистрация: 14.12.2020 Сообщений: 171
	15.10.2023, 11:18 [ТС]
	VTsaregorodtsev, размер массивов тут, конечно.....большой...не спорю.... Но допустим, у нас в какой-то игре (типа "герои 3") warcraft и т.п. Там есть карта....немаленькая скажу я Вам, (ни один экран) Так вот при скроллинге она перерисовывет все точки экрана, причем так быстро, что саму перерисоаку пользователь не замечает. (это я к тому, что обработать большущее кол-во информации за короткий промежуток времени возможно) Знать бы как... 0

@locm 6202 / 2896 / 311 Регистрация: 28.10.2011 Сообщений: 11,186 Записей в блоге: 6
	15.10.2023, 15:00
	GPU не может выполнять код Intel x86/x64. 0

@VTsaregorodtsev 1673 / 1569 / 261 Регистрация: 19.02.2010 Сообщений: 4,178
	16.10.2023, 10:46
	nigri_lupus, я бейсиком не пользовался уже 30+ лет А Pure Basic я вообще никогда не видел. Т.е. в тему я зашёл просто посмотреть "кто виноват (задача / алгоритм / транслятор / процессор) и что делать" - и оценить расхождение своего мнения с мнениями других. 0