标签: reduction

这是我想要转换为openCL的循环.

for(n=0; n < LargeNumber; ++n) {    
    for (n2=0; n2< SmallNumber; ++n2) {
        A[n]+=B[n2][n];
    }                                                         
    Re+=A[n];       
}

到目前为止,这是我所拥有的,但我知道这是不正确的,并且缺少一些东西.

__kernel void openCL_Kernel( __global  int *A,
                         __global  int **B,  
                         __global  int *C, 
                         __global _int64 Re,
                                   int D) 
{

int i=get_global_id(0);
int ii=get_global_id(1);

A[i]+=B[ii][i];

//barrier(..); ?

Re+=A[i];

}

我是这类事的初学者.首先我知道我无法将全局双指针传递给openCL内核.如果可以的话,在发布解决方案之前等待几天左右,我想为自己解决这个问题,但如果你能帮我指出正确的方向,我将不胜感激.

我正在尝试开发一种在彩虹表生成器中使用的缩减功能.

缩减函数背后的基本原理是它接受散列,执行一些计算,并返回一定长度的字符串.

目前我正在使用SHA1哈希,我需要返回一个长度为3的字符串.我需要在以下任意三个随机字符上组成字符串:

abcdefghijklmnopqrstuvwxyz0123456789

我面临的主要问题是我编写的任何缩减函数总是返回已经生成的字符串.一个好的缩减函数只会很少返回重复的字符串.

有人可以提出任何想法来实现这一目标吗？或者对哈希到字符串操作的任何建议都会很棒.

提前致谢

玩笑

我有一个表达,假设,

a = 1 && (b = 1 || b != 0 ) && (c >= 35 || d != 5) && (c >= 38 || d = 6)

我希望它减少到,

a = 1 && b != 0 && (c >= 38 || d = 6)

有没有人有什么建议？指向任何算法的指针？

Nota Bene:我相信Karnaugh Map或Quine-McCluskey不是一个选择.由于这些方法不处理灰色案例.我的意思是,表达只能减少,就像A或A'或任何东西,或说黑色或白色或缺乏颜色.但是在这里,我有灰色阴影,正如大家们所看到的那样.

解决方案:我已经在Clojure中为此编写了程序.我使用了包含函数值的地图.这非常方便,只是几个组合的一些规则,你很好.谢谢你的有用答案.

我正在阅读 Mark Harris 的关于优化 CUDA 中的并行缩减的演示文稿。这是一张我有问题的幻灯片：

它说这种方法存在银行冲突问题。但为什么？所有线程都在访问位于不同库中的两个连续内存单元。它们都不会同时访问特定的存储单元。

首先,请允许我声明我已经充分意识到我的问题已经被提出:CUDA中的减少但是,正如我希望明确的那样,我的问题是对此的后续行动,我有特殊的需求使该OP发现的解决方案不合适.

所以,让我解释一下.在我当前的代码中,我在while循环的每次迭代中运行一个Cuda内核来对数组的值进行一些计算.举个例子,想象如下:

int max_iterations = 1000;
int iteration = 0;
while(iteration < max_iterations)
{
    __global__ void calcKernel(int* idata, int* odata)
    {
        int i = blockIdx.x*blockDim.x + threadIdx.x;
        if (i < n)
        {
            odata[i] = (idata[i] + 2) * 5;
        }
    }

    iteration++;
}

但是,接下来我必须为GPU完成看似艰巨的任务.在调用内核的while循环的每次迭代中,我必须对在其中生成的所有值求和odata并将结果保存在一个int数组中result,该数组在此类数组中与当前迭代对应的位置.它必须在内核中完成,或者至少仍然在GPU中完成,因为由于性能限制,我只能result在完成所有迭代后最终检索数组.

一个错误的天真尝试看起来像下面这样:

int max_iterations = 1000;
int iteration = 0;
while(iteration < max_iterations)
{
    __global__ void calcKernel(int* idata, int* odata, int* …

我试图将观察的 df 减少到单个观察（单行）。我想 summarise_if 是带有均值的数字，而 if 是带有模式的字符串或因子。下面的代码不起作用，但我希望它给出了想法。谢谢！

#data frame
num <- c(1:7)
str <- c("toy","control","play",NA,"give","toy","toy")
df_finale <- data.frame(num,str)

#mode function
Mode <- function(x) {
        ux <- unique(x)
        ux[which.max(tabulate(match(x, ux)))]
}

#df reduction
df_finale <- df_finale %>%
                    summarize_if(is.numeric, mean, na.rm = TRUE) %>%
                    summarize_else_if(!is.numeric, Mode)

我必须在GPU上解决一个非常标准的问题,但我对实际的GPGPU很新,所以我正在寻找解决这个问题的想法.

我在3空间中有很多分配给极少数组(每个点属于一个组),特别是在这种情况下为15(不会改变).现在我想计算所有组的均值和协方差矩阵.所以在CPU上它大致相同:

for each point p
{
    mean[p.group] += p.pos;
    covariance[p.group] += p.pos * p.pos;
    ++count[p.group];
}

for each group g
{
    mean[g] /= count[g];
    covariance[g] = covariance[g]/count[g] - mean[g]*mean[g];
}

由于组的数量非常小,最后一步可以在CPU上完成(无论如何我需要CPU上的那些值).第一步实际上只是一个分段缩减,但片段分散.

所以我提出的第一个想法是首先按照他们的小组对点进行排序.我想到了一个简单的桶排序atomic_inc用于计算桶大小和每点重定位指数(更好地分类？),原子可能不是最好的主意.之后,他们通过组排序,我可能拿出提出的分段扫描算法的适应这里.

但在这种特殊情况下,我每点得到的数据量非常大(9-10个浮点数,如果需要的话,甚至可以加倍),因此每个线程使用共享内存元素和每点线程的标准算法可能会产生问题将每个多处理器资源视为共享内存或寄存器(好吧,更多关于计算能力1.x而不是2.x,但仍然如此).

由于我认为可能有更好的方法,团体数量非常少且数量不变.也许已有的想法适合这种标准问题的这些特定属性.或者也许我的一般方法并不是那么糟糕,你有改进各个步骤的想法,比如适用于极少数键的良好排序算法或一些最小化共享内存/寄存器使用的分段缩减算法.

我正在寻找一般方法,不想使用外部库.FWIW我正在使用OpenCL,但它并不重要,因为GPU计算的一般概念在主要框架上并没有真正的不同.

我有一个平面数组b：

a = numpy.array([0, 1, 1, 2, 3, 1, 2])

以及c标记每个“块”开始的索引数组：

b = numpy.array([0, 4])

我知道我可以使用归约找到每个“块”中的最大值：

m = numpy.maximum.reduceat(a,b)
>>> array([2, 3], dtype=int32)

但是...有没有一种方法可以通过向量化操作（无列表、循环）找到<edit>块内最大值的索引</edit>（例如）？numpy.argmax

我正在编译这个简单的程序:

#include <numeric> 

int main()
{
    int numbers[] = {1, 2, 3, 4, 5};
    auto num_numbers = sizeof(numbers)/sizeof(numbers[0]);
    return std::accumulate(numbers,  numbers + num_numbers, 0);
}

它将整数1到5相加并返回该总和(即15).

我意识到在实现中std::accumulate可能会有一些技巧,但是,这仍然非常简单.尽管如此,我在编译时(在GodBolt上)我得到的结果让我感到惊讶.

随着-O3C++是一种面向编译时计算的语言,我得到了预期的结果:

main:
        mov     eax, 15
        ret

但是如果我继续-O2- 仍然是一些重要的优化 - 不仅我没有得到这个编译时计算,但我看到这个奇怪的程序集:

main:
        movabs  rax, 8589934593
        lea     rdx, [rsp-40]
        mov     ecx, 1
        mov     DWORD PTR [rsp-24], 5
        mov     QWORD PTR [rsp-40], rax
        lea     rsi, [rdx+20]
        movabs  rax, 17179869187
        mov     QWORD PTR [rsp-32], rax
        xor     eax, eax
        jmp …

raku 网页表示，应在归约运算符中为用户定义的函数使用额外的括号：https : //docs.raku.org/language/operators#Reduction_metaoperators

但是，当我将函数作为变量传递时出现错误（我使用的是 Rakudo Star 2010.10）：

> sub lessThan ($a, $b) { $a < $b }
&lessThan
> my @a = ((1,2,3), (6,5,4))
[(1 2 3) (6 5 4)]
> sub x (@arrOfArr, &func) { say @arrOfArr.grep( { [[&func]] ($_[0], $_[1], $_[2]) } ); }
&x
> x(@a, &lessThan)
((1 2 3) (6 5 4)) # <----------------------------------- this is not what I expected
> say @a.grep( { [<] ($_[0], $_[1], $_[2]) } );
((1 2 3)) # …