c - 有符号整数的谓词 "less than or equal"的高效并行字节计算-6ren

c - 有符号整数的谓词 "less than or equal"的高效并行字节计算

转载作者：塔克拉玛干更新时间：2023-11-03 03:23:42

25

4

<分区>

在各种情况下，例如生物信息学，对字节大小的整数进行计算就足够了。为了获得最佳性能，许多处理器架构提供 SIMD 指令集(例如 MMX、SSE、AVX)，它将寄存器划分为字节、半字和字大小的组件，然后分别对相应的组件执行算术、逻辑和移位操作。

但是，某些架构不提供此类 SIMD 指令，需要对其进行仿真，这通常需要大量的位操作。目前，我正在研究 SIMD 比较，特别是有符号字节大小整数的并行比较。我有一个我认为使用可移植 C 代码非常有效的解决方案(请参阅下面的函数 vsetles4)。它基于 2000 年彼得·蒙哥马利 (Peter Montgomery) 在 newsgroup posting 中所做的观察。 , (A+B)/2 = (A AND B) + (A XOR B)/2 在中间计算中没有溢出。

这个特定的仿真代码(函数 vsetles4)能否进一步加速？首先订购任何基本操作数较少的解决方案都符合条件。我正在寻找可移植 ISO-C99 中的解决方案，而不使用特定于机器的内在函数。大多数架构都支持 ANDN (a & ~b)，因此就效率而言，可以假定这可作为单个操作使用。

#include <stdint.h>

/*
   vsetles4 treats its inputs as arrays of bytes each of which comprises
   a signed integers in [-128,127]. Compute in byte-wise fashion, between
   corresponding bytes of 'a' and 'b', the boolean predicate "less than 
   or equal" as a value in [0,1] into the corresponding byte of the result.
*/

/* reference implementation */
uint32_t vsetles4_ref (uint32_t a, uint32_t b)
{
    uint8_t a0 = (uint8_t)((a >>  0) & 0xff);
    uint8_t a1 = (uint8_t)((a >>  8) & 0xff);
    uint8_t a2 = (uint8_t)((a >> 16) & 0xff);
    uint8_t a3 = (uint8_t)((a >> 24) & 0xff);
    uint8_t b0 = (uint8_t)((b >>  0) & 0xff);
    uint8_t b1 = (uint8_t)((b >>  8) & 0xff);
    uint8_t b2 = (uint8_t)((b >> 16) & 0xff);
    uint8_t b3 = (uint8_t)((b >> 24) & 0xff);
    int p0 = (int32_t)(int8_t)a0 <= (int32_t)(int8_t)b0;
    int p1 = (int32_t)(int8_t)a1 <= (int32_t)(int8_t)b1;
    int p2 = (int32_t)(int8_t)a2 <= (int32_t)(int8_t)b2;
    int p3 = (int32_t)(int8_t)a3 <= (int32_t)(int8_t)b3;

    return (((uint32_t)p3 << 24) | ((uint32_t)p2 << 16) |
            ((uint32_t)p1 <<  8) | ((uint32_t)p0 <<  0));
}

/* Optimized implementation:

   a <= b; a - b <= 0;  a + ~b + 1 <= 0; a + ~b < 0; (a + ~b)/2 < 0.
   Compute avg(a,~b) without overflow, rounding towards -INF; then
   lteq(a,b) = sign bit of result. In other words: compute 'lteq' as 
   (a & ~b) + arithmetic_right_shift (a ^ ~b, 1) giving the desired 
   predicate in the MSB of each byte.
*/
uint32_t vsetles4 (uint32_t a, uint32_t b)
{
    uint32_t m, s, t, nb;
    nb = ~b;            // ~b
    s = a & nb;         // a & ~b
    t = a ^ nb;         // a ^ ~b
    m = t & 0xfefefefe; // don't cross byte boundaries during shift
    m = m >> 1;         // logical portion of arithmetic right shift
    s = s + m;          // start (a & ~b) + arithmetic_right_shift (a ^ ~b, 1)
    s = s ^ t;          // complete arithmetic right shift and addition
    s = s & 0x80808080; // MSB of each byte now contains predicate
    t = s >> 7;         // result is byte-wise predicate in [0,1]
    return t;
}

25

4

0

文章推荐： java - 是否会删除 Java 中已弃用的项目

文章推荐： algorithm - 了解 Spark CosineSimillarity 输出

文章推荐： java - 是否可以为 Java 控制台应用程序实现 MVC？

文章推荐： algorithm - 我怎样才能展开重复: T(n)=2T((n+2)/3)

java - 尽管有默认的 "OR"谓词，但 ViewerFilter 上的 "And"谓词？
我正在开发一个包含 TreeViewer 的 RCP 应用程序，我想在其上激活多个应与“OR”谓词配合使用的过滤器，例如: A |--B |--|--redColor |--|--blueColor
c++ - 我的类型在 std 函数中未能通过 enable_if 谓词。有没有办法 "debug"谓词？
我的问题是关于 enable_if通常标准库中的谓词，但我将在迭代器类型的上下文中构建它，因为这是我目前遇到此问题的地方。我有一个自定义迭代器类型 It , 这样 std::iterator_tra
Scala 谓词
关闭。这个问题不满足Stack Overflow guidelines .它目前不接受答案。想改善这个问题吗？更新问题，使其成为 on-topic对于堆栈溢出。 4年前关闭。 Improve thi
Prolog 谓词 - 无限循环
我需要使用自然数为 2 的幂创建一个 Prolog 谓词。自然数是:0、s(0)、s(s(0)) 等等。例如: ?- pow2(s(0),P). P = s(s(0)); false. ?- po
iphone - 核心数据 ANY BETWEEN 谓词
我正在尝试创建一个 NSPredicate 来查找在特定日期范围内包含“ session ”的“项目”。我一开始尝试过这个: [NSPredicate predicateWithFormat:@"AN
Prolog powerset 谓词
很难说出这里问的是什么。这个问题是含糊的、模糊的、不完整的、过于宽泛的或修辞性的，无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开它，visit the help center 。已关
java - 如何在JOOQ中编写多字段 `in`谓词？
在JOOQ中，我可以编写如下SQL这样的代码吗？我不知道如何编写具有多个字段的in谓词。 select some_value from t1 where (t1.id1, t1.id2) i
具有可变数量参数的 Prolog 谓词
我正在用 PROLOG 编写一个数独求解器。我希望求解器能够处理所有可能大小的数独，因此我自然需要构造采用可变数量参数的谓词。 (例如在数独中构建“ block ”。) 如何构造或模拟具有可变数量参数
java - 如何在Ebean中实现 "not in"谓词？
我有一个包含一些 id 的列表，我希望我的 ebean 查询排除这些 id。所以基本上我需要在 ebean 中使用“not in”谓词，就像 sql 一样，但遗憾的是找不到。还有其他方法可以实现这一目
c# - 如何创建一个通用方法来遍历对象的字段并将其用作 Where 谓词？
我正在构建一个通用接口(interface)以从类中公开选定的字符串属性，然后我想在每个字段中搜索文本，以检查它是否匹配。这是我的 IFieldExposer接口(interface): using
java - 搜索嵌套对象的规范/谓词
我将 Spring Boot 与 Spring JPA 和 Specification Executor 结合使用。我的规范/谓词组合成功地在我的类中搜索了简单的属性。但是，我在搜索其中的对象时遇到了
MySQL 并跳过 WHERE 谓词
如果下面的 last_name 为 NULL，它会跳过该列的 WHERE 比较以提高性能吗？ AND (last_name IS NULL OR sp.last_name LIKE CONCAT('%
c++ - 谓词...或其他术语？
出于好奇:如果我有一个接受多个参数(通常为 1 或 2)并返回 3 个值中的 1 个(而不是 bool 值 true 或 false)的类运算符(或函数等)，它是否仍应被调用谓词？还是模糊逻辑的特例？
返回装箱值类型是否为该类型的默认值的 C# 谓词
是否可以创建一个采用装箱值类型并返回该值类型是否等于该类型默认值的方法？所以我想创建一个具有以下签名的方法: bool IsDefault(object boxedValueType); 注意:当
swift - RealmSwift ALL 谓词
let selectedConsoles = ["Xbox", "Playstation 4"] let players = realm.objects(Person).filter("console
swift - NSSet 谓词
我正在尝试根据用户搜索文本过滤来自核心数据的结果，但效果很好。我正在努力做到有几个关键术语可以返回特定结果。我有一个Colour 实体，它与另一个实体ProjectColour 具有对多关系。 P
C++ is_str_empty 谓词
std::vector lines; typedef std::vector::iterator iterator_t; iterator_t eventLine = std::find_if(lin
c# - IndexOf 谓词？
我想在一个列表中找到一个元素的索引，该列表匹配某个谓词，有没有比以下更好的方法: var index = list.IndexOf(list.Find(predicate)); ? 最佳答案你在找
prolog - 高阶 "solutions"谓词
我正在使用缺少 findall 的高阶 Prolog 变体. 还有一个关于实现我们自己的问题 findall这里:Getting list of solutions in Prolog . 低效的实现
breeze - 如何测试空的 Breeze 谓词？
我正在使用 Breeze 过滤客户端请求的数据。我的代码看起来有点像这样: 客户端 - 创建过滤谓词 var predicates = []; var criteriaPredicate = null

首页

博学

6Ren·AI

商城

c - 有符号整数的谓词 "less than or equal"的高效并行字节计算