Saya memiliki histogram yang jarang dengan kunci sebagai tempat sampah dan nilai sebagai hitungan. Saya ingin menggunakan kunci dan jumlah dalam histogram untuk membuat larik nilai kunci lainnya. Kunci-kunci dalam larik ini adalah tempat sampah tetapi waktu penghitungan berulang, dan pada akhirnya setiap kunci akan memiliki nilai yang sama dengan hitungan yang sesuai. Kunci dalam histogram dan array diurutkan dalam urutan menaik.

Misalnya jika histogram terlihat seperti ini:

    Key/Bins:       0 2 4 5 6 7
    Values/Counts:  3 2 1 4 2 3 

Array kunci yang nilainya ingin saya temukan terlihat seperti ini:

 Key:     0 0 0 2 2 4 5 5 5 5 6 6 7 7 7

Setelah mengisi nilai menggunakan histogram, array nilai kunci baru akan terlihat seperti ini:

   Key:     0 0 0 2 2 4 5 5 5 5 6 6 7 7 7
   Values:  3 3 3 2 2 1 4 4 4 4 2 2 3 3 3 

Saya dapat melakukan ini menggunakan loop dan memeriksa apakah dua kunci sama tetapi apakah ada cara yang efisien untuk melakukan ini menggunakan Thrust?

Terima kasih!

0
KuroNeko 15 Maret 2017, 00:31

2 jawaban

Jawaban Terbaik

Berikut adalah salah satu metode yang mungkin:

  1. gunakan thrust::transform menggunakan dua versi offset dari larik key untuk menandai awal setiap segmen

    Key:     0 0 0 2 2 4 5 5 5 5 6 6 7 7 7
    seg:     0 0 0 1 0 1 1 0 0 0 1 0 1 0 0
    
  2. dengan awal setiap segmen ditandai, lakukan thrust::inclusive_scan untuk mengubah penanda segmen menjadi satu set indeks pencarian

    Key:     0 0 0 2 2 4 5 5 5 5 6 6 7 7 7
    seg:     0 0 0 1 0 1 1 0 0 0 1 0 1 0 0
    idx:     0 0 0 1 1 2 3 3 3 3 4 4 5 5 5
    
  3. indeks pencarian ini kemudian dapat digunakan dengan thrust::permutation_iterator untuk menyalin nilai yang diindeks dari array nilai/jumlah ke dalam output yang diinginkan

    Key:     0 0 0 2 2 4 5 5 5 5 6 6 7 7 7
    seg:     0 0 0 1 0 1 1 0 0 0 1 0 1 0 0
    idx:     0 0 0 1 1 2 3 3 3 3 4 4 5 5 5
    Val:     3 3 3 2 2 1 4 4 4 4 2 2 3 3 3
    

Berikut adalah contoh yang berhasil:

$ cat t1299.cu
#include <thrust/device_vector.h>
#include <thrust/iterator/zip_iterator.h>
#include <thrust/iterator/permutation_iterator.h>
#include <thrust/transform.h>
#include <thrust/remove.h>
#include <thrust/copy.h>
#include <iostream>

struct my_remove
{
  template <typename T>
  __host__ __device__
  bool operator()(const T &t)
  {
    return (thrust::get<0>(t) == 0);
  }
};

struct my_cmp
{
  template <typename T>
  __host__ __device__
  int operator()(const T &t)
  {
    if (thrust::get<0>(t) != thrust::get<1>(t)) return 1;
    return 0;
  }
};

using namespace thrust::placeholders;

int main(){

  int kb[] = {0,2,4,5,6,7};
  int vc[] = {3,2,1,4,2,3};
  int key[] = {0,0,0,2,2,4,5,5,5,5,6,6,7,7,7};
  int kbsize = sizeof(kb)/sizeof(int);
  int keysize = sizeof(key)/sizeof(int);

  thrust::device_vector<int> dkb(kb, kb+kbsize);
  thrust::device_vector<int> dvc(vc, vc+kbsize);
  thrust::device_vector<int> dkey(key, key+keysize);
  thrust::device_vector<int> dval(keysize);
  thrust::copy(dkey.begin(), dkey.end(), std::ostream_iterator<int>(std::cout, ","));
  std::cout << std::endl;

  //first remove any zero count values from kb/vc

//  thrust::remove_if(thrust::make_zip_iterator(thrust::make_tuple(dvc.begin(), dkb.begin())), thrust::make_zip_iterator(thrust::make_tuple(dvc.end(), dkb.end())), my_remove());

  // next, mark the segments in the key array

  thrust::transform(thrust::make_zip_iterator(thrust::make_tuple(dkey.begin(), dkey.begin()+1)), thrust::make_zip_iterator(thrust::make_tuple(dkey.end()-1, dkey.end())), dval.begin()+1, my_cmp());

  // prefix sum to generate lookup indices
  thrust::device_vector<int> didx(keysize);
  thrust::inclusive_scan(dval.begin(), dval.end(), didx.begin());

  // use lookup indices to populate values vector

  thrust::copy(thrust::make_permutation_iterator(dvc.begin(), didx.begin()), thrust::make_permutation_iterator(dvc.begin(), didx.end()), dval.begin());

  // display results

  thrust::copy(dval.begin(), dval.end(), std::ostream_iterator<int>(std::cout, ","));
  std::cout << std::endl;
  return 0;
}
$ nvcc -arch=sm_35 -o t1299 t1299.cu
$ ./t1299
0,0,0,2,2,4,5,5,5,5,6,6,7,7,7,
3,3,3,2,2,1,4,4,4,4,2,2,3,3,3,
$

Contoh tipikal optimasi dorong adalah mencari "fusi" operasi. Dalam hal ini, karena kita memiliki operasi transformasi yang segera diikuti dengan pemindaian inklusif, contoh sederhana dari fusi adalah menggantinya dengan thrust::transform_inclusive_scan

1
Robert Crovella 15 Maret 2017, 04:06

Tampaknya Anda melakukan pencarian tabel di GPU. Berikut implementasi menggunakan cuckoo hash pada GPU dengan CUDA. https://github.com/shixing/cuckoo/tree/master

Proses pembangunan diimplementasikan pada CPU:

create_hash_cpu(h_keys,h_values,h_key_1,h_key_2,h_value_1,h_value_2, N, KOSONG_KUNCI);

Proses pencarian ada di GPU:

cuckoo_lookup<<<(M+255)/256, 256>>>(d_keys_lookup, d_values_lookup, d_key_1, d_value_1, d_key_2, d_value_2, M, N, EMPTY_KEY, EMPTY_VALUE);

1
Xing Shi 15 Maret 2017, 07:34