标签: stream-compaction

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

使用SSE内在函数,我可以使用_mm_shuffle_epi8()进行相当有效的操作,它执行16条表查找(收集并行计算术语).shuffle索引是预先计算的,并使用位掩码查找.

for (i = 0; i < n; i += 8)
{
  v8n_Data = _mm_load_si128(&data[i]);
  mask = _mm_movemask_epi8(&is_valid[i]) & 0xff;     // is_valid is byte array
  v8n_Compacted = _mm_shuffle_epi8(v16n_ShuffleIndices[mask]);
  _mm_storeu_si128(&compacted[count], v8n_Compacted);

  count += bitCount[mask];
}

我的问题是现在我想为Altivec SIMD实现这个(不要问为什么 - 错误的商业决策).Altivec没有_mm_movemask_epi8()的等价物,这是一个关键因素.所以,我需要找到一种方法

1. 模拟_mm_movemask_epi8() - 似乎很贵,有几个班次和OR

2. 直接生成有效的shuffle指数 -

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

element_valid:   0 0 1 0 1 0 0 1 0
gather_indices:  x x x x x x 6 4 1
scatter_indices: 3 3 2 2 1 1 1 0 0

串行执行此操作非常简单,但我需要它是并行(SIMD).使用前缀sum生成散列索引似乎很容易,但由于AltiVec和SSE都没有散点指令,我需要收集索引.收集索引是散射指数的反函数,但是如何并行获得？我知道在GPU编程的开创性时代,将散射转换为收集是一种常见的技术,但这两种方法中没有一种看似实用.

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

我知道cassandra合并sstables,row-keys,删除墓碑等等.

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

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

我知道什么是压实,但想知道它是如何实现的(T)

我在Kafka 0.8.1.1中的server.properties文件中进行了更改,即在创建主题时添加log.cleaner.enable=true并启用cleanup.policy=compact了.现在,当我测试它时,我将以下消息推送到主题,其中包含以下内容(Key,Message).

• 偏移量:1 - (123,abc);
• 偏移量:2 - (234,def);
• 抵消:3 - (345,ghi);
• 抵消:4 - (123,已更改)

现在我用与早期输入相同的键推送第4条消息,但更改了消息.这里的日志压缩应该会出现.使用Kafka工具,我可以看到主题中的所有4个偏移.我怎么知道日志压缩是否有效？是否应删除先前的消息,或者在推送新消息时日志压缩工作正常.是否有做的任何事情log.retention.hours或topic.log.retention.hours或log.retention.size配置？这些配置在日志压缩中的作用是什么.PS - 我已经彻底浏览了Apache文档,但仍然不清楚.

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

例如：

K: V
1: 99
1: 100
1: 100
1: 100
1: 103
2: 103
2: 105
3: 45
3: 67

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

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

1: 99
1: 100
1: 103
2: 103 <-- This should remain, since key is different
2: 105
3: 45
3: 67

我查看了Thrust中可用的流压缩函数，但找不到任何可以实现此目的的函数。Thrust 可以做到这一点吗？或者我是否需要编写自己的内核来标记模板中的重复项，然后删除它们？