压缩缓冲区的快速算法

Question

我正在执行图像压缩。

图像I被分解成K个代码块{Bi}。

每个块都有固定大小的 MxN 像素。

每个块都是独立压缩的。

所有具有压缩大小 {Pi} 的压缩块 {Ci} 存储在大小为 K * M 的线性缓冲区 B 中，其中 M 是大于所有尺寸 Pi 的固定尺寸。

现在，我想将缓冲区 B 打包到缓冲区 C 中，并在每个压缩代码块的结尾 Ci.

所以，我需要一个内核：

对于每个块 Ci，找到 k < i 的所有 Pk 的总和，（称之为 offset_i）
将每个 Ci 的数据从 B 复制到 C，大小为 Pi offset_i

任何关于如何做到这一点的想法将不胜感激！！

Answer 1

我对你的问题的理解是这样的：您有一组压缩缓冲区，每个缓冲区都有不同的长度。

最后，您需要一个没有空格的简单大缓冲区。为什么不像这样简单地将所有缓冲区存储在一个块中 -首先将缓冲区的数量N写入long值 - 第二个存储长度为 N 的长值数组，其大小为每个缓冲区的大小 - 最后写下你的 N 个缓冲区

我不明白为什么你需要一个内核

Answer 2

这是代码片段，（我想）它进行了流压缩。它包含大量算法，但可以并行化到所需的度量。

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Block {
    int size;
    int buf[8];
} Block;

typedef struct BlockPos {
    int t_size; //Temporary size for compaction
    int f_size; //Actual size
    int pos;    //Position
} BlockPos;

int main()
{
    const int num_blocks = 16;
    Block blocks[num_blocks];
    BlockPos pos[num_blocks];

    srand(time(NULL));
    for (int i = 0; i < num_blocks; i++) {
        //Every block has non-zero length, that's easier
        blocks[i].size = rand() % 7 + 1;

        printf("Block %d len %d:\t", i, blocks[i].size);
        for(int j=0; j<blocks[i].size; j++){
            //Just to make print easier
            blocks[i].buf[j] = rand() % 33;
            printf("%d, ", blocks[i].buf[j]);
        }
        printf("\n");
    }

    for(int i=0; i<num_blocks; i++){
        pos[i].f_size = blocks[i].size;
        pos[i].t_size = pos[i].f_size;
        pos[i].pos = 0;
    }

    int step = 2;
    /* At every step we reduce number of blocks, being processed, two times.
     * This loop can't be done in parallel. */
    for (int count = 1; count < num_blocks; count *= 2) {

        /* All odd-numbered blocks are compacting to nearest left-side neighbour.
         * This loop can be done in parallel. */
        for (int i = count; i < num_blocks; i += step) {
            int dif = pos[i].pos;
            pos[i].pos = pos[i - count].pos + pos[i - count].t_size;
            pos[i - count].t_size += pos[i].t_size;
            dif -= pos[i].pos;

            // "Replace" previously compacted blocks
            for (int j = i+1; count > 1 && j < i+count; j++) {
                pos[j].pos = pos[j-1].pos + pos[j-1].f_size;
            }
        }
        step *= 2;
    }

    printf("\nPos,\tLen:\n");
    for(int i=0; i<num_blocks; i++){
        printf("%d,\t%d\n", pos[i].pos, pos[i].f_size);
    }

    printf("\n");
    return 0;
}

内部循环（第 54 行）可以作为 OpenCL 内核实现，直到处理的元素数量足够大。在此之后，您将拥有结构数组，每个元素将显示放置压缩块的位置。然后可以并行完成。

Answer 3

您需要有权访问您的树莓派的大小。我会使用一个临时缓冲区，它的长度是块的总数。当你压缩一个块时，你将压缩块的长度存储到这个临时缓冲区中。然后你最新的内核可以使用这个临时缓冲区来计算它必须在哪个地址写入最终缓冲区。出于性能原因，您可以将此临时缓冲区复制到本地内存中（在最后一个内核中）。

Answer 4

所以，原来我需要写一个stream compaction算法。

这将需要两个内核：

内核 1：所有前缀和算法（也称为扫描）计算缓冲区偏移量：Parallel Prefix Sum (Scan) with CUDA.

库 clpp 具有用 OpenCL 编写的扫描算法，这是我的目标 GPGPU 语言。

内核 2：每个工作组使用在内核 1 中计算的偏移量合并从输入缓冲区读取并写入输出缓冲区。

压缩缓冲区的快速算法

Fast algorithm for compacting a buffer

opencl