查看完整版本 : GPU sorting Integers ...

煙民母親生賤種 2017-10-19 03:43 AM

GPU sorting Integers ...

今晚得閒又試下玩 gpu computing...
今次是用 nvidia 的 lib Thrust 中的 sorting
sort 1 億個 random nums

快 cpu [color=Magenta][b][size=5]20 倍[/size][/b][/color]... :fst_012:而且 thrust 的 code, 只係 1 行, 唔洗寫 kernel ... :fst_008:
[b][u]但是  cpu sorting 我只係用 C11 的 sort, 係單線程... [/u][/b]

code :
[url=https://ideone.com/A45uun]https://ideone.com/A45uun[/url]

[attach]7466428[/attach]

[[i] 本帖最後由 煙民母親生賤種 於 2017-10-19 03:48 AM 編輯 [/i]]

ncream 2017-10-23 11:39 AM

[quote]原帖由 [i]煙民母親生賤種[/i] 於 2017-10-19 03:43 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=469588940&ptid=27001031][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
今晚得閒又試下玩 gpu computing...
今次是用 nvidia 的 lib Thrust 中的 sorting
sort 1 億個 random nums

快 cpu 20 倍... :fst_012:而且 thrust 的 code, 只係 1 行, 唔洗寫 kernel ... :fst_008:
但是  c ... [/quote]

Ching,int N = 100000000,你Sort 咁多個?


我見你screen出兩位數字,但rand你min, max 係1 to 1000000000。唔係幾明,可否教教小弟。

[[i] 本帖最後由 ncream 於 2017-10-23 11:59 AM 編輯 [/i]]

Susan﹏汪汪 2017-10-23 01:42 PM

[quote]原帖由 [i]ncream[/i] 於 2017-10-23 11:39 AM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=469797545&ptid=27001031][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]


Ching,int N = 100000000,你Sort 咁多個?


我見你screen出兩位數字,但rand你min, max 係1 to 1000000000。唔係幾明,可否教教小弟。 [/quote]
佢sort好之後D數字由小至大排

段code只print頭100個數字、咪只見到頭100個兩位數

ncream 2017-10-23 04:47 PM

[quote]原帖由 [i]煙民母親生賤種[/i] 於 2017-10-19 03:43 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=469588940&ptid=27001031][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
今晚得閒又試下玩 gpu computing...
今次是用 nvidia 的 lib Thrust 中的 sorting
sort 1 億個 random nums

快 cpu 20 倍... :fst_012:而且 thrust 的 code, 只係 1 行, 唔洗寫 kernel ... :fst_008:
但是  c ... [/quote]

30秒會唔會慢小小,sort()係咪有問題,我寫開C,array限65536,若果唔係可以寫一段比較下。
CPU一定慢過GPU,但再慢都無咁離譜,我認為係C++ sort() function寫得差,應該只係差2倍左右。

[[i] 本帖最後由 ncream 於 2017-10-23 04:52 PM 編輯 [/i]]

煙民母親生賤種 2017-10-24 02:55 AM

[quote]原帖由 [i]ncream[/i] 於 2017-10-23 04:47 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=469810462&ptid=27001031][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]


30秒會唔會慢小小,sort()係咪有問題,我寫開C,array限65536,若果唔係可以寫一段比較下。
CPU一定慢過GPU,但再慢都無咁離譜,我認為係C++ sort() function寫得差,應該只係差2倍左右。 [/quote]c++ std::sort() 應該都係 C 既野來... :fst_007:
C 都可以用 pointer malloc(), 你不妨試下。:fst_005:

jasonchan35 2017-10-24 08:19 AM

[quote]原帖由 [i]煙民母親生賤種[/i] 於 2017-10-24 02:55 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=469832400&ptid=27001031][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
c++ std::sort() 應該都係 C 既野來... :fst_007:
C 都可以用 pointer malloc(), 你不妨試下。:fst_005: [/quote]

std::sort() 要 template, 所以係 C++ 唔係 C, 不過家下都無咩 compiler 無 C++

ncream 2017-10-24 08:50 AM

[quote]原帖由 [i]jasonchan35[/i] 於 2017-10-24 08:19 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=469835959&ptid=27001031][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]


std::sort() 要 template, 所以係 C++ 唔係 C, 不過家下都無咩 compiler 無 C++ [/quote]


我用個款係無C++。:smile_42::smile_42:


學C LANGUAGE要自己SORT。多謝師兄指教細佬。:loveliness:

ncream 2017-10-24 08:50 AM

[quote]原帖由 [i]煙民母親生賤種[/i] 於 2017-10-24 02:55 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=469832400&ptid=27001031][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
c++ std::sort() 應該都係 C 既野來... :fst_007:
C 都可以用 pointer malloc(), 你不妨試下。:fst_005: [/quote]

多謝師兄指教,我未學過malloc(),現在寫緊。:loveliness:

jasonchan35 2017-10-24 12:29 PM

[quote]原帖由 [i]ncream[/i] 於 2017-10-24 08:50 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=469836875&ptid=27001031][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

我用個款係無C++。:smile_42::smile_42:
學C LANGUAGE要自己SORT。多謝師兄指教細佬。:loveliness: [/quote]

咩 compiler / platform ?
對上我用唔到 C++ 要用 C, 應該係 PlayStation2


Sorting in Array
[url]https://www.youtube.com/watch?v=B9og2-3Rpu8&list=PLeGk08zVu454WgM_8uE-dUayT_EOoVEQS&index=6[/url]

Malloc
[url]https://www.youtube.com/watch?v=cUz6q1FICBM&list=PLeGk08zVu454WgM_8uE-dUayT_EOoVEQS&index=20[/url]

ncream 2017-10-24 12:42 PM

[quote]原帖由 [i]jasonchan35[/i] 於 2017-10-24 12:29 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=469846339&ptid=27001031][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]


咩 compiler / platform ?
對上我用唔到 C++ 要用 C, 應該係 PlayStation2


Sorting in Array
[url=https://www.youtube.com/watch?v=B9og2-3Rpu8&list=PLeGk08zVu454WgM_8uE-dUayT_EOoVEQS&index=6]https://www.youtube.com/watch?v=B9og2-3Rpu8&list=PLeGk08zVu454WgM_8uE-dUayT_EOoVEQS&index=6[/url]

Malloc
... [/quote]

我已經揾到CODE,下午會試寫。到時POST上來。

:lDD_001:

Susan﹏汪汪 2017-10-24 01:12 PM

隨意寫寫[code]#include <iostream>

template <class T> void swap (T& a, T& b)
{
    T c(std::move(a)); a=std::move(b); b=std::move(c);
}

template <class Compare, class BirdirectionalIterator>
void sort(BirdirectionalIterator first, BirdirectionalIterator last, Compare comp)
{
   
    typedef typename std::iterator_traits<BirdirectionalIterator>::value_type value_type;
   
    BirdirectionalIterator _l = last - 1;
   
    if (first < _l) {
        
        BirdirectionalIterator forward = first;
        BirdirectionalIterator backward = last;
        
        value_type val = *_l;
        
        for (--backward; forward < backward; ++forward)
        {
            while (comp(*forward, val) && forward < backward) ++forward;
            while (comp(val, *backward) && forward < backward) --backward;
            swap(*forward, *backward);
        }
        swap(*backward, *_l);
        
        sort(first, backward, comp);
        sort(backward, last, comp);
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
   
    int a[] = {3, 6, 8, 2, 5};
   
    sort(a, a + 5, [](auto a, auto b) { return a < b; });
   
    std::cout << a[0] << std::endl;
    std::cout << a[1] << std::endl;
    std::cout << a[2] << std::endl;
    std::cout << a[3] << std::endl;
    std::cout << a[4] << std::endl;
    return 0;
}[/code]

ncream 2017-10-24 01:46 PM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-10-24 01:12 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=469848159&ptid=27001031][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
隨意寫寫#include

template  void swap (T& a, T& b)
{
    T c(std::move(a)); a=std::move(b); b=std::move(c);
}

template
void sort(BirdirectionalIterator first, BirdirectionalIterator last, C ... [/quote]

是否快過sort() 30948ms,post screen 上來。


你個code無寫timer。要寫埋計時code上去。

Susan﹏汪汪 2017-10-24 02:05 PM

[quote]原帖由 [i]ncream[/i] 於 2017-10-24 01:46 PM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=469849732&ptid=27001031][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]


是否快過sort() 30948ms,post screen 上來。


你個code無寫timer。要寫埋計時code上去。 [/quote]
段code應該有錯

ncream 2017-10-24 02:07 PM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-10-24 02:05 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=469850734&ptid=27001031][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

段code應該有錯 [/quote]

快唔過sort()即是證明c++ sort() library好過你。咁無意義。

Susan﹏汪汪 2017-10-24 02:17 PM

[quote]原帖由 [i]ncream[/i] 於 2017-10-24 02:07 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=469850853&ptid=27001031][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]


快唔過sort()即是證明c++ sort() library好過你。咁無意義。 [/quote]
咁當然

上面段code只不過係隨便寫左幾分鐘
最簡單的quick sort

汪汪話可能錯係指排錯次序

下面執左少少
應該冇排錯次序[code]#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <ctime>

template <class T> void swap (T& a, T& b)
{
    T c(std::move(a)); a=std::move(b); b=std::move(c);
}

template <class Compare, class BirdirectionalIterator>
void sort(BirdirectionalIterator first, BirdirectionalIterator last, Compare comp)
{
   
    typedef typename std::iterator_traits<BirdirectionalIterator>::value_type value_type;
   
    const auto _l = last - 1;
   
    if (first < _l) {
        
        auto forward = first, backward = _l;
        const value_type val = *_l;
        
        for (; forward < backward; ++forward)
        {
            while (comp(*forward, val) && forward < backward) ++forward;
            while (comp(val, *backward) && forward < backward) --backward;
            swap(*forward, *backward);
        }
        swap(*backward, *_l);
        
        sort(first, backward, comp);
        sort(backward, last, comp);
    }
}

int main(int argc, const char * argv[]) {
   
    int N = 1 << 20;
   
    int *a = new int[N];
    int *b = new int[N];
   
    for (int i = 0; i < N; ++i) {
        int val = rand();
        a[i] = val;
        b[i] = val;
    }
   
   
    std::clock_t start_1, start_2;
   
    start_1 = std::clock();
   
    sort(a, a + N, [](auto a, auto b) { return a < b; });
   
    std::cout << "sort " << (std::clock() - start_1) / (double)CLOCKS_PER_SEC << std::endl;
   
    start_2 = std::clock();
   
    std::sort(b, b + N, [](auto a, auto b) { return a < b; });
   
    std::cout << "std::sort " << (std::clock() - start_2) / (double)CLOCKS_PER_SEC << std::endl;
   
    std::cout << a[0] << " " << a[1] << " " << a[2] << " " << a[3] << " " << a[4] << std::endl;
    std::cout << b[0] << " " << b[1] << " " << b[2] << " " << b[3] << " " << b[4] << std::endl;
   
    delete [] a;
    delete [] b;
   
    return 0;
}[/code][code]sort 0.095081
std::sort 0.083371
1003 5255 7872 8383 10249
1003 5255 7872 8383 10249[/code]

ncream 2017-10-24 02:54 PM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-10-24 02:17 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=469851372&ptid=27001031][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

咁當然

上面段code只不過係隨便寫左幾分鐘
最簡單的quick sort

汪汪話可能錯係指排錯次序

下面執左少少
應該冇排錯次序#include
#include
#include
#include

template  void swap (T& a, T&  ... [/quote]

要做:100000000 個sorting
rand出來要100000000

唔係點比較。

Susan﹏汪汪 2017-10-24 03:00 PM

[quote]原帖由 [i]ncream[/i] 於 2017-10-24 02:54 PM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=469853060&ptid=27001031][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]


要做:100000000 個sorting
rand出來要100000000

唔係點比較。 [/quote]
你用你自己部電腦試

部部電腦速度唔同、就算汪汪講左時間出來都做唔到比較

ncream 2017-10-24 03:28 PM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-10-24 01:12 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=469848159&ptid=27001031][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
隨意寫寫#include

template  void swap (T& a, T& b)
{
    T c(std::move(a)); a=std::move(b); b=std::move(c);
}

template
void sort(BirdirectionalIterator first, BirdirectionalIterator last, C ... [/quote]

我唔熟c++,有無ching可以幫手改佢個code n=10000000,rand 10000000。compile埋測試

就咁睇個code 我唔覺得會快得過sort()。

ncream 2017-10-24 05:05 PM

[quote]原帖由 [i]煙民母親生賤種[/i] 於 2017-10-19 03:43 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=469588940&ptid=27001031][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
今晚得閒又試下玩 gpu computing...
今次是用 nvidia 的 lib Thrust 中的 sorting
sort 1 億個 random nums

快 cpu 20 倍... :fst_012:而且 thrust 的 code, 只係 1 行, 唔洗寫 kernel ... :fst_008:
但是  c ... [/quote]
Ching,我個C code gen唔到long int,去到rand gen 出來random number唔超過65536

你個邊
h_input[i] = GetRandomNumber(1, 100000000);
有無辦法gen到100000以上的random number????
因為要公平,確保到可以有平均random number,以測試 CPU/GPU速度。

我用malloc寫左big array。但差random number make sure to compile。

:smile_53:

Susan﹏汪汪 2017-10-24 06:20 PM

[quote]原帖由 [i]ncream[/i] 於 2017-10-24 05:05 PM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=469858852&ptid=27001031][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]

Ching,我個C code gen唔到long int,去到rand gen 出來random number唔超過65536

你個邊
h_input = GetRandomNumber(1, 100000000);
有無辦法gen到100000以上的random number????
因為要公平,確保到可以有 ... [/quote]
你唔係同一部電腦試係冇意思

就算汪汪改左int N = 100000000;
時間得到
[code]
sort 10.5648
std::sort 9.63601
[/code]

或者你#18
N = 10000000
時間得到
[code]
sort 0.962007
std::sort 0.832517
[/code]

ncream 2017-10-24 06:45 PM

[quote]原帖由 [i]jasonchan35[/i] 於 2017-10-24 12:29 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=469846339&ptid=27001031][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]


咩 compiler / platform ?
對上我用唔到 C++ 要用 C, 應該係 PlayStation2


Sorting in Array
[url=https://www.youtube.com/watch?v=B9og2-3Rpu8&list=PLeGk08zVu454WgM_8uE-dUayT_EOoVEQS&index=6]https://www.youtube.com/watch?v=B9og2-3Rpu8&list=PLeGk08zVu454WgM_8uE-dUayT_EOoVEQS&index=6[/url]

Malloc
... [/quote]


[size=16px]Ching, 我依家用兩個random number 相乘。得出大的亂數。但因為咁又得唔到細既亂數。[/size]
[size=16px]
[/size]
[size=16px]到底點先做到均勻亂數。[/size]
[size=16px]
[/size]
[size=16px]C 真係咩都唔得。唔知。C++ 亂數出唔出到均勻而又範圍大亂數。[/size]

ncream 2017-10-24 06:48 PM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-10-24 06:20 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=469862442&ptid=27001031][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

你唔係同一部電腦試係冇意思

就算汪汪改左int N = 100000000;
時間得到

sort 10.5648
std::sort 9.63601


或者你#18
N = 10000000
時間得到

sort 0.962007
std::sort 0.832517
[/quote]

10???s? ms??

當你10s 。即是你個program sort 得重快過樓主使用既c++ sort() library。 。咁恭喜你,你唔使玩。去nvidia做都得。

我繼續寫同樓主一樣既sort

[[i] 本帖最後由 ncream 於 2017-10-24 06:53 PM 編輯 [/i]]

Susan﹏汪汪 2017-10-24 06:53 PM

[quote]原帖由 [i]ncream[/i] 於 2017-10-24 06:48 PM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=469863829&ptid=27001031][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]


10???s? ms??

當你10s 。即是你個program sort 得重快過c++ sort() library。 。咁恭喜你,你唔使玩。去nvidia做都得。

我繼續寫同樓主一樣既sort [/quote]
你數清楚個N幾多個零先

ncream 2017-10-24 06:55 PM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-10-24 06:53 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=469864026&ptid=27001031][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

你數清楚個N幾多個零先 [/quote]

要我講白d。ok

做唔到樓主program同一測試條件。無得比較。再發100post都無意思。

Susan﹏汪汪 2017-10-24 06:59 PM

[quote]原帖由 [i]ncream[/i] 於 2017-10-24 06:55 PM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=469864116&ptid=27001031][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]


要我講白d。ok

做唔到樓主program同一測試條件。無得比較。再發100post都無意思。 [/quote]
頭先果句原本係回覆你講0.9s果個時間

不過你改左post的話就無視汪汪果句「個N幾多個零」

Susan﹏汪汪 2017-10-24 07:04 PM

[quote]原帖由 [i]ncream[/i] 於 2017-10-24 06:55 PM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=469864116&ptid=27001031][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]


要我講白d。ok

做唔到樓主program同一測試條件。無得比較。再發100post都無意思。 [/quote]
其次

講左好多次
唔同的電腦、速度都唔同

汪汪部電腦本身快過樓主部電腦
所以跑出黎嘅時間快過佢個C++ sort係正常

做速度測試一定係需要同一部電腦去做
呢個一向係基本條件

ncream 2017-10-24 07:06 PM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-10-24 07:04 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=469864472&ptid=27001031][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

其次

講左好多次
唔同的電腦、速度都唔同

汪汪部電腦本身快過樓主部電腦
所以跑出黎嘅時間快過佢個C++ sort係正常

做速度測試一定係需要同一部電腦去做
呢個一向係基本條件 [/quote]

若果測試條件相同。樓主自然會將你個code一。放係樓主電腦再run自然可比較。

而你亦可用樓主code 係你部電腦run

咪可以比較到

Susan﹏汪汪 2017-10-24 07:08 PM

[quote]原帖由 [i]ncream[/i] 於 2017-10-24 07:06 PM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=469864556&ptid=27001031][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]


若果測試條件相同。樓主自然會將你個code一。放係樓主電腦再run自然可比較。

而你亦可用樓主code 係你部電腦run

咪可以比較到 [/quote]
所以汪汪個測試時間咪有兩個數字

一個係sort
一個係std::sort

ncream 2017-10-24 07:13 PM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-10-24 07:08 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=469864632&ptid=27001031][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

所以汪汪個測試時間咪有兩個數字

一個係sort
一個係std::sort [/quote]

哦! 明白了。sorry

咁代表你慢過sort() 10%左右。

咁無意思。只係證明到你sort得慢過library。無其他。

應該要sort得快過library先有value

Susan﹏汪汪 2017-10-24 07:16 PM

[quote]原帖由 [i]ncream[/i] 於 2017-10-24 07:13 PM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=469864834&ptid=27001031][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]


哦! 明白了。sorry

咁代表你慢過sort() 10%左右。

咁無意思。只係證明到你sort得慢過library。無其他。

應該要sort得快過library先有value [/quote]
好容易就加到速

係最後果步recursive
開兩條thread就可以
頁: [1] 2 3 4 5 6 7 8 9 10
查看完整版本: GPU sorting Integers ...