问题标签 [stream-compaction]

我有一对大小相等的数组，我将它们称为键和值。

例如：

对键进行排序，并对与每个键关联的值进行排序。如何删除与每个键及其对应键关联的重复值？

也就是说，我想将以上内容压缩为：

我查看了Thrust中可用的流压缩功能，但找不到任何这样做的东西。推力可以做到这一点吗？还是我需要编写自己的内核来标记模板中的重复项，然后删除它们？

我正在尝试使用 SIMD 内在函数编写流压缩（获取数组并删除空元素）。循环的每次迭代一次处理 8 个元素（SIMD 宽度）。

使用 SSE 内在函数，我可以使用 _mm_shuffle_epi8() 相当有效地做到这一点，它执行 16 个条目的表查找（收集并行计算术语）。随机索引是预先计算的，并使用位掩码进行查找。

我的问题是现在我也想为 Altivec SIMD 实现这个（不要问为什么——错误的商业决策）。Altivec 没有关键成分 _mm_movemask_epi8() 的等效项。所以，我需要找到一种方法

1. emulate _mm_movemask_epi8() - 看起来很贵，需要几个班次和 OR

2. 直接有效地生成洗牌索引 -

即，索引 i 将是未压缩数据中第 i 个有效元素的索引

串行执行此操作很简单，但我需要它是并行的（SIMD）。生成带有前缀总和的分散索引似乎很容易，但由于 AltiVec 和 SSE 都没有分散指令，所以我需要收集索引。收集索引是分散索引的反函数，但是如何并行得到呢？我知道在 GPU 编程的开创性日子里，将散点图转换为集合是一种常见的技术，但所描述的这两种方法似乎都不实用。

也许如果不坚持压缩保留元素顺序将允许更有效的实施？我可以放弃那个。

我知道 cassandra 合并了 sstables、行键、删除墓碑等等。

1. 但我真的很想知道它是如何执行压缩的？

2. 由于 sstables 是不可变的，它是否会将所有相关数据复制到新文件中？并且在写入这个新文件时，它会丢弃墓碑标记的数据。

我知道压缩是做什么的，但想知道它是如何实现的（T）

我们有 24 个节点和复制因子 2 的 Cassandra-0.8.2 集群。其中一个节点非常慢，并且该节点上的大多数 sstables 已损坏。（我们无法运行压缩，甚至无法清理）

那么是否可以清理该节点的数据、缓存和提交日志目录并使用 bootstrap=true 重新启动？将所有数据流返回到该节点是否有帮助？

如果可能的话，有什么可能造成问题的吗？应该注意什么以避免任何危险？

流压缩算法中的最终排他扫描值应该如何处理？

这是挑选所有“A”字符的示例。

序列A：

序列 B（除最后一个值外相同）：

显然，第二个示例基于对写入这些地址的扫描值进行简单循环，给出了错误的最终结果。

我在这里想念什么？

更新：

据我了解扫描算法，我将执行以下等效操作：

同时，这将涉及分散指令。

我的程序生成充满布尔值的大型数组。我需要最紧凑的方式将它们保存在文件中。

我在这里读到http://www.kirupa.com/forum/showthread.php?339670-How-is-boolean-represented-in-memory内存中的 8 个布尔值可能表示为单个字节，因此单个布尔值是单个位。但是我怎样才能将这些布尔数组同样紧凑地保存到一个文件中呢？我知道 - 文件写入函数是使用字节而不是位来操作的。

很快 - 我希望能够将布尔数组保存到文件中，大小比 Array.Length 小 8 倍

我正在为我的 cuda 程序寻找优化策略。在内核的 for 循环内的每次迭代中，每个线程都会产生一个分数。我正在维护分数的共享优先级队列，以维护每个块中的前 k 个分数。请看下面的伪代码：

希望上面的代码对你们有意义。现在，我正在寻找一种方法来消除原子操作开销 st 每个线程保存“1”或“0”，具体取决于值是否应该进入优先级队列。我想知道内核中是否有任何流压缩的实现，以便我可以将“1000000000100000000”减少到“11000000000000000000”缓冲区（或知道“1”的索引），最后在队列中插入与“1”相对应的分数。
请注意，在这种情况下，'1' 将非常稀疏。

尝试使用推力 zip 迭代器压缩多个 CUDA 数组时，我遇到了一个令人困惑的错误。我的情况很简单：我有一个表示对象状态的整数推力::向量，以及表示对象在 3D 中的位置和速度的六个浮点向量。当状态（整数）向量元素的值为1时，我想从所有向量中删除该元素并缩小向量。

按照这个例子，我使用了一个 7 路元组和一个谓词。

但是，这似乎错误地删除了额外的元素。例如，当在 100 的向量中存在单个标记对象时，向量的压缩后大小为 52，而不是预期的 99。我错过了什么？

我正在使用 openmp 来并行化我的代码。我有一个原始数组：

和一个标记数组：

使用数组 M 我可以在这个打包数组中压缩我的原始数组：

我想使用多线程方法解决这个问题。C++ 的库“推力”解决了这个问题，但我无法为 Fortran 找到类似的工具。是否有一个库，比如 C++ 的“推力”，我可以用来执行流压缩？或者，是否有一种我可以使用 fortran 和 openmp 自己编写的算法来解决这个问题？

概括：

关于如何进一步改进 CUDA 中的基本分散操作的任何想法？特别是如果有人知道它只会用于将更大的阵列压缩成更小的阵列？或者为什么以下向量化内存操作和共享内存的方法不起作用？我觉得我可能缺少一些基本的东西，任何帮助都将不胜感激。

编辑 03/09/15：所以我发现这篇Parallel For All 博客文章“使用 Warp-Aggregated Atomics 优化过滤”。为此，我曾假设原子本质上会变慢，但我错了——尤其是因为我认为我不关心在模拟过程中维护数组中的元素顺序。我将不得不考虑更多，然后实施它以查看会发生什么！

编辑 01/04/16：我意识到我从来没有写过我的结果。不幸的是，在那篇 Parallel for All 博客文章中，他们将紧凑的全局原子方法与 Thrust 前缀和紧凑方法进行了比较，这实际上非常慢。CUB 的 Device::IF 比 Thrust 快得多——我使用 CUB 的 Device::Scan + 自定义代码编写的前缀和版本也是如此。warp-aggregate 全局原子方法仍然快约 5-10%，但远不及我根据博客中的结果所希望的 3-4 倍。我仍然使用前缀和方法，因为虽然不需要维护元素顺序，但我更喜欢前缀和结果的一致性，并且原子的优势不是很大。我仍然尝试各种方法来改善紧凑，

细节：

我正在 CUDA 中编写一个模拟，在其中我压缩了我不再对每 40-60 个时间步进行模拟感兴趣的元素。从分析看来，分散操作在压缩时占用的时间最多 - 比过滤器内核或前缀总和更多。现在我使用一个非常基本的分散函数：

freq_Index 是旧数组中的元素数。标志数组是过滤器的结果。Scan_ID 是标志数组上前缀和的结果。

我为改进它所做的尝试是首先将标记的频率读入共享内存，然后从共享内存写入全局内存——这个想法是对全局内存的写入将在扭曲之间更加合并（例如，而不是线程 0写入位置 0，线程 128 写入位置 1，线程 0 将写入 0，线程 1 将写入 1）。我还尝试将读取和写入矢量化——而不是读取和写入浮点数/整数，我尽可能从全局数组中读取/写入 float4/int4，因此一次四个数字。我认为这可能会通过更少的内存操作传输更多的内存来加速分散。具有矢量化内存加载/存储和共享内存的“厨房水槽”代码如下：

显然它变得有点复杂。:) 虽然当数组中有数十万个元素时，上述内核看起来很稳定，但我注意到当数组数以千万计时出现竞争情况。我仍在尝试追踪错误。

但无论如何，没有一种方法（共享内存或矢量化）一起或单独提高性能。我对向量化内存操作缺乏好处感到特别惊讶。它对我编写的其他函数有所帮助，但现在我想知道它是否有帮助，因为它在其他函数的计算步骤中增加了指令级并行性，而不是减少了内存操作。