Verimli kısmi indirimler, alt grupların ofsetleri ve uzunlukları verili

Question

Uygulamam için daha sonra bölünmüş ve daha küçük kovalara ayrılan bir grup nesneyi (int s diyelim) ele almam gerekiyor. Bu amaçla, ilgili kovanın birinci eleman ve alt liste uzunlukları uzaklıklar ile verilir, tek bir sürekli dizi

arr = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14...} 

elemanları ve bölümleri (sublists) hakkında bilgi depolamak.

Dolayısıyla, örneğin, aşağıdaki bölünmeler olmasına neden olur

offsets = {0,3,8,..} 
sublist_lengths = {3,5,2,...} 

verilen:

0 1 2 || 3 4 5 6 7 || 8 9 || ... 

Ne aradığım azalmalar gibi algoritmalar, çalıştırmak için biraz genel ve etkili bir yoldur, yalnızca özel çekirdekler veya thrust kitaplığı kullanarak kovalarda. kova toplarsak vermelidir:

Ben ile geldim ne

3 || 25 || 17 || ... 

:

• seçenek 1: Özel çekirdekleri uğraşının bir biraz gerektirir paylaşılan belleğe kopyalar, doğru seçim blok ve ızgara boyutlarının ve tarama, azaltma, vb. gibi algoritmaların kendi gerçekleştirilmesi. Ayrıca, her bir işlem kendi özel çekirdeğini gerektirir. Genelde, ancak daha akıllı yolu var olabileceğini izlenimi var son birkaç gün için thrust kullandıktan sonra bunu nasıl bana açıktır

• seçenek 2: gelen tuşları bir dizi oluşturmak ofsetler (yukarıdaki örnekte {0,0,0,1,1,1,1,1,2,2,3,...}) ve thrust::reduce_by_key kullanın. Yine de fazladan bir liste oluşturmayı sevmiyorum.

• seçenek 3: thrust::counting_iterator ile birlikte kullanın thrust::transform_iterator anında yukarıda verilen anahtar listesini oluşturmak için. Maalesef, cihazdaki ofset listesindeki endekslerin artışını gerektirmeyen ve paralelliği yitiren bir uygulamayla gelemiyorum.

Bunu gerçekleştirmenin en aklı başında ne olurdu?

Answer 1

Thrust içinde, Seçenek 2'den daha iyi bir çözüm düşünemiyorum. Performans korkunç olmayacak, ama kesinlikle uygun değil.

Veri yapınız, seyrek matrisleri saklamak için Compressed Sparse Row (CSR) biçimindeki benzerliğe sahiptir; bu nedenle, daha iyi bir performans istiyorsanız, bu matrisler için sparse matrix-vector multiplies (SpMV) bilgi işlem için geliştirilmiş teknikleri kullanabilirsiniz. CSR biçimindeki "ofset" dizisinin, N satırlı bir matris için (N, 1) olduğu, son ofset değerinin arr uzunluğunun olduğu durumda olduğuna dikkat edin. Cusp'daki CSR SpMV code biraz kıvrımlıdır, ancak çekirdeğiniz için iyi bir başlangıç ​​noktası görevi görür. Herhangi bir referansı Aj veya x kodundan kaldırın ve offsets ve arr sırasıyla Ap ve Av argümanlarına geçirin.

Answer 2

Kepçelerin ne kadar büyük olduğunu söylemediniz. Eğer kovalar yeterince büyükse, ofsetleri ve sublist_length'leri ana bilgisayara kopyalayarak, bunları tekrarlayarak ve her bir kova için ayrı bir Thrust çağrısı yaparak uzaklaşabilirsiniz. Fermi aynı anda uçuşta 16 taneye sahip olabilir, bu yüzden bu mimaride daha küçük kovaları ele alabilir ve yine de iyi bir kullanım elde edebilirsiniz.