相关疑难解决方法(0)

假设我有一个数组 k = [1 2 0 0 5 4 0]

我可以按如下方式计算掩码 m = k > 0 = [1 1 0 0 1 1 0]

仅使用掩码m和以下操作

1. 向左/向右移动
2. 和/或
3. 加/减/乘

我可以将k压缩成以下内容 [1 2 5 4]

这是我目前的做法(MATLAB伪代码):

function out = compact( in )
    d = in
    for i = 1:size(in, 2) %do (# of items in in) passes
        m = d > 0
        %shift left, pad w/ 0 on right
        ml = [m(2:end) 0] % shift
        dl = [d(2:end) 0] % shift

        %if …

在测量某些东西的同时,我测量的吞吐量比我计算的要低得多,我将其缩小到LZCNT指令(它也发生在TZCNT中),如以下基准所示:

  xor ecx, ecx
_benchloop:
  lzcnt eax, edx
  add ecx, 1
  jnz _benchloop

和:

  xor ecx, ecx
_benchloop:
  xor eax, eax  ; this shouldn't help, but it does
  lzcnt eax, edx
  add ecx, 1
  jnz _benchloop

第二个版本要快得多.它不应该.LZCNT没有理由对其输出有输入依赖性.与BSR/BSF不同,xZCNT指令总是覆盖其输出.

我在4770K上运行它,所以LZCNT和TZCNT没有被执行为BSR/BSF.

这里发生了什么？

我有8个bool变量,我想将它们"合并"成一个字节.

有一个简单/首选的方法来做到这一点？

相反,如何将一个字节解码为8个独立的布尔值？

我认为这不是一个不合理的问题,但由于我无法通过谷歌找到相关文档,它可能是另一个"非你所有直觉都是错误的"案例.

如何最有效地计算C#中整数(日志基数2)所需的位数？例如:

int bits = 1 + log2(100);

=> bits == 7

我正在玩新的AVX512指令集,我试着了解它们是如何工作的以及如何使用它们.

我尝试的是交错由掩码选择的特定数据.我的小基准测试将x*32字节的对齐数据从内存加载到两个向量寄存器中,并使用动态掩码压缩它们(图1).得到的向量寄存器被分散到存储器中,因此两个向量寄存器是交错的(图2).

图1:使用相同的动态创建掩码压缩两个数据向量寄存器.

图2:用于交错压缩数据的分散存储.

我的代码如下所示:

void zipThem( uint32_t const * const data, __mmask16 const maskCompress, __m512i const vindex, uint32_t * const result ) {
   /* Initialize a vector register containing zeroes to get the store mask */
   __m512i zeroVec     = _mm512_setzero_epi32();
   /* Load data */
   __m512i dataVec_1   = _mm512_conflict_epi32( data );
   __m512i dataVec_2   = _mm512_conflict_epi32( data + 16 );
   /* Compress the data */
   __m512i compVec_1   = _mm512_maskz_compress_epi32( maskCompress, dataVec_1 );
   __m512i compVec_2   = _mm512_maskz_compress_epi32( maskCompress, dataVec_2 );

   /* Get …

我想使用 SSE 实现以下功能。它将 a 中的元素与 b 中的压缩元素混合在一起，其中元素仅在使用时才存在。

void packedBlend16(uint8_t mask, uint16_t* dst, uint16_t const* a, uint16_t const* b) {
  for (int i = 0; b < 8; ++i) {
    int const control = mask & (1 << i);
    dst[i] = control ? a[i] : *b++;
  }
}

对我来说棘手的部分是在向量中正确地间隔 b 的元素。

到目前为止，我的方法是：

1. 256 个条目LUT[mask]以进行随机播放，将 b 的元素扩展到正确的位置pshufb
2. 使用vpbroadcastw+ vpand+从蒙版构造混合向量vpcmpeqw
3. pblendvb a 与洗牌的元素 b

我怀疑 256 个条目的 LUT 不是最好的方法。我可能有 2 16 个入口 LUT 用于高位/低位。但是您必须根据掩码的低 4 位的 …

这个问题专门针对现代x86-64缓存一致性架构 - 我很欣赏其他CPU的答案可能会有所不同.

如果我写入内存,MESI协议要求首先将缓存行读入缓存,然后在缓存中进行修改(将值写入缓存行,然后将其标记为脏).在较旧的写入微架构中,这将触发高速缓存行被刷新,在写回期间,被刷新的高速缓存行可能会延迟一段时间,并且一些写入组合可能在两种机制下发生(更可能是回写) .我知道这与访问相同缓存行数据的其他核心如何交互 - 缓存监听等.

我的问题是,如果商店恰好匹配缓存中已有的值,如果没有单个位被翻转,那么任何英特尔微架构都会注意到这一点并且不将该行标记为脏,从而可能将该行标记为独占,以及在某些时候跟随的回写内存开销？

当我向更多的循环进行矢量化时,我的矢量化操作组合基元不会明确地检查值的变化,并且在CPU/ALU中这样做似乎很浪费,但我想知道底层缓存电路是否可以在没有显式编码的情况下完成(例如,商店微操作或缓存逻辑本身).由于跨多个内核的共享内存带宽变得更加成为资源瓶颈,这似乎是一种越来越有用的优化(例如,重复调整相同的内存缓冲区 - 如果它们已经存在,我们不会重新读取RAM中的值在缓存中,但强制写回相同的值似乎很浪费).回写缓存本身就是对这类问题的承认.

我可以礼貌地要求阻止"在理论上"或"它确实无关紧要"的答案 - 我知道记忆模型是如何工作的,我正在寻找的是关于如何写出相同价值的硬性事实(而不是避免一个商店)将影响内存总线的争用你可以安全地假设是一台运行多个工作负载的机器几乎总是受内存带宽限制.另一方面,解释为什么芯片不这样做的确切原因(我悲观地假设他们没有这样做)将具有启发性......

更新: 这里的预期线路上的一些答案https://softwareengineering.stackexchange.com/questions/302705/are-there-cpus-that-perform-this-possible-l1-cache-write-optimization但仍然很多推测"它必须很难,因为它没有完成",并说如何在主CPU核心中这样做会很昂贵(但我仍然想知道为什么它不能成为实际缓存逻辑本身的一部分).

我正在研究英特尔内在指南中的扩展和压缩操作.我对这两个概念感到困惑:

对于 __m128d _mm_mask_expand_pd (__m128d src, __mmask8 k, __m128d a) == vexpandpd

从a(在掩码k中设置各自的位)加载连续的有效双精度(64位)浮点元素,并使用写掩码k将结果存储在dst中(当相应的掩码位为时,从src复制元素)没有设置).

对于 __m128d _mm_mask_compress_pd (__m128d src, __mmask8 k, __m128d a) == vcompresspd

将有效双精度(64位)浮点元素连续存储在a(在写掩码k中设置各自的位)到dst,并从src传递剩余的元素.

是否有更清楚的描述或任何可以解释更多的人？

提前致谢.

KbL i7-8550U

我正在研究 uops-cache 的行为并遇到了关于它的误解。

如英特尔优化手册2.5.2.2（我的）中所述：

解码的 ICache 由 32 组组成。每组包含八种方式。 每路最多可容纳六个微操作。

——

Way 中的所有微操作表示在代码中静态连续的指令，并且它们的 EIP 位于相同的对齐 32 字节区域内。

——

最多三种方式可以专用于相同的 32 字节对齐块，从而允许在原始 IA 程序的每个 32 字节区域中缓存总共 18 个微操作。

——

无条件分支是 Way 中的最后一个微操作。

情况1：

考虑以下例程：

uop.h

void inhibit_uops_cache(size_t);

uop.S

align 32
inhibit_uops_cache:
    mov edx, esi
    mov edx, esi
    mov edx, esi
    mov edx, esi
    mov edx, esi
    mov edx, esi
    jmp decrement_jmp_tgt
decrement_jmp_tgt:
    dec rdi
    ja inhibit_uops_cache ;ja is intentional to avoid Macro-fusion
    ret

为了确保例程的代码实际上是 32 字节对齐的，这里是 asm …

我正在尝试用CUDA构造一个并行算法,它采用一个整数数组,并删除所有0的有或没有保持顺序.

例:

全局内存:{0,0,0,0,14,0,0,17,0,0,0,0,13}

主机内存结果:{17,13,14,0,0,...}

最简单的方法是使用主机删除0中的O(n)时间.但考虑到我有各种各样的1000元素,在发送之前将GPU上的所有内容保留并首先压缩它可能会更快.

优选的方法是创建设备上堆栈,使得每个线程可以(以任何顺序)弹出和推送到堆栈上或从堆栈中推出.但是,我不认为CUDA有这个实现.

等效(但速度要慢得多)的方法是继续尝试写入,直到所有线程都写完为止:

kernalRemoveSpacing(int * array, int * outArray, int arraySize) {
    if (array[threadId.x] == 0)
        return;

    for (int i = 0; i < arraySize; i++) {

         array = arr[threadId.x];

         __threadfence();

         // If we were the lucky thread we won! 
         // kill the thread and continue re-reincarnated in a different thread
         if (array[i] == arr[threadId.x])
             return;
    }
}

这种方法的好处在于我们会O(f(x))及时执行,其中f(x)是数组中非零值的平均数(f(x) ~= ln(n)对于我的实现,因此是O(ln(n)) …