我已经研究了很多关于减少的问题,但我有一个不好的问题:我从CLRS中得到这个:
"......通过"减少"解决问题A来解决问题B,我们使用B的"容易度"来证明A的"容易度"."
我从"Christos H. Papadimitriou的计算复杂性"中得出这个结论:
"......如果B减少到A,问题A至少和问题B一样难."
我对这两个概念感到困惑:当我们使用easyiness时,我们说问题X简化为问题Y,如果我们有Y的多项式时间算法,并且还原过程是在多项式时间内完成的,那么问题X在多项式时间内是可解的,X是比Y容易或至少不比Y更难.
但是当我们使用硬度时,我们说问题X减少到问题Y并且Y比X更容易或者至少不比X更难.
我真的很困惑,请帮帮我.特别感谢.
algorithm complexity-theory np-complete reduction computation-theory
我已经经历了一些例子,将一个元素数组减少到一个元素,但没有成功.有人在NVIDIA论坛上发布了此消息.我已经从浮点变量更改为整数.
__kernel void sum(__global const short *A,__global unsigned long *C,uint size, __local unsigned long *L) {
unsigned long sum=0;
for(int i=get_local_id(0);i<size;i+=get_local_size(0))
sum+=A[i];
L[get_local_id(0)]=sum;
for(uint c=get_local_size(0)/2;c>0;c/=2)
{
barrier(CLK_LOCAL_MEM_FENCE);
if(c>get_local_id(0))
L[get_local_id(0)]+=L[get_local_id(0)+c];
}
if(get_local_id(0)==0)
C[0]=L[0];
barrier(CLK_LOCAL_MEM_FENCE);
}
这看起来不错吗？第三个参数"大小",应该是本地工作规模,还是全球工作规模？
我设置了这样的论点,
clSetKernelArg(ocReduce, 0, sizeof(cl_mem), (void*) &DevA);
clSetKernelArg(ocReduce, 1, sizeof(cl_mem), (void*) &DevC);
clSetKernelArg(ocReduce, 2, sizeof(uint), (void*) &size);
clSetKernelArg(ocReduce, 3, LocalWorkSize * sizeof(unsigned long), NULL);
第一个参数是输入,我试图保留从之前启动的内核的输出.
clRetainMemObject(DevA);
clEnqueueNDRangeKernel(hCmdQueue[Plat-1][Dev-1], ocKernel, 1, NULL, &GlobalWorkSize, &LocalWorkSize, 0, NULL, NULL);
//the device memory object DevA now has the data to be …我正在努力使代码并行运行(CUDA).简化的代码是:
float sum = ... //sum = some number
for (i = 0; i < N; i++){
f = ... // f = a function that returns a float and puts it into f
sum += f;
}
我遇到的问题是sum+=f因为它需要sum在线程之间共享.我__shared__在声明sum(__shared__ float sum)时尝试使用该参数,但这不起作用(它没有给我正确的结果).我也听说过减少(并知道如何在OpenMP上使用它),但不知道如何在这里应用它.
任何帮助将不胜感激.谢谢!
虽然我理解了本文中描述的并行缩减背后的逻辑,但我似乎无法在输入数组为1的简单示例中运行它size.
这是我到目前为止所取得的成就.请记住,我正在使用推力库来管理输入和输出数据.
#include <iostream>
#include <thrust/host_vector.h>
#include <thrust/device_vector.h>
#include <thrust/sort.h>
#include <ctime>
#include <sys/time.h>
#include <sstream>
#include <string>
#include <fstream>
using namespace std;
__global__ void reduce0(int *g_idata, int *g_odata){
extern __shared__ int sdata[];
unsigned int tid = threadIdx.x;
unsigned int i = blockIdx.x*blockDim.x + threadIdx.x;
sdata[tid] = g_idata[i];
__syncthreads();
for(unsigned int s=1; s < blockDim.x; s *= 2) {
if (tid % (2*s) == 0) {
sdata[tid] += sdata[tid + s];
}
__syncthreads();
}
if (tid …我刚刚开始学习CUDA编程,我对减少有些困惑.
我知道全局内存与共享内存相比有很多访问延迟,但是我可以使用全局内存来(至少)模拟类似于共享内存的行为吗？
例如,我想总结一个长度正好的大数组的元素BLOCK_SIZE * THREAD_SIZE(网格和块的维度都是幂2),我试图使用下面的代码:
__global__ void parallelSum(unsigned int* array) {
unsigned int totalThreadsNum = gridDim.x * blockDim.x;
unsigned int idx = blockDim.x * blockIdx.x + threadIdx.x;
int i = totalThreadsNum / 2;
while (i != 0) {
if (idx < i) {
array[idx] += array[idx + i];
}
__syncthreads();
i /= 2;
}
}
我比较了这段代码的结果和在主机上串行生成的结果,奇怪的是:有时结果是相同的,但有时它们显然是不同的.在这里使用全局内存是否有任何原因？
假设A，B和C是决策问题。还假设A是B的多项式时间可约化的，而B是C的多项式时间可约化的。如果A和C都是NP完全的，那么是否意味着B也是NP完全的？
我知道，如果A是NP完全的并且可以多项式时间化简为B，那么B是NP难的。但是，要使问题成为NP完全问题，它必须满足（1）在NP中，以及（2）在NP中是困难的。
我不知道如何证明NP-complete的第一个要求。
我是CUDA的新手,也是一般的算法.有人可以告诉我,如果我正确地这样做,或者有更好的方法这样做.一个问题是代码的输入和输出应该在GPU上,因此主机和设备之间没有内存复制.
#include "cuda_runtime.h"
#include "device_launch_parameters.h"
#include <stdio.h>
#include <stdint.h>
#include <iostream>
#define TILE_WIDTH 8
__global__ void gpu_sumElements(int height, int width, float *in, float *out){
extern __shared__ float cache[];
int w = blockIdx.x * blockDim.x + threadIdx.x; // Col // width
int h = blockIdx.y * blockDim.y + threadIdx.y;
int index = h * width + w;
int cacheIndex = threadIdx.y * blockDim.x + threadIdx.x;
float temp = 0;
if ((w < width) && (h < height)){
temp += in[index];
//index …我目前正在学习使用C和OpenMP进行并行编程.我想编写简单的代码,其中两个共享值由多个线程递增.首先,我使用了还原指令,它的工作原理就是这样.然后我切换到使用关键指令启动关键部分 - 它也有效.出于好奇,我试图合并这两个解决方案并检查行为.我期待两个有效的,相等的值.
码:
#include <stdio.h>
#include <stdlib.h>
#include "omp.h"
#define ITER 50000
int main( void )
{
int x, y;
#pragma omp parallel reduction(+:x,y)
{
#pragma omp for
for (int i = 0; i < ITER; i++ )
{
x++;
#pragma omp critical
y++;
}
}
printf("non critical = %d\ncritical = %d\n", x, y);
return 0;
}
输出:
非关键= 50000
关键= 4246432
当然,当涉及到'critical'(变量y)时,输出是随机的,另一个表现为预期的并且总是50000.
x的行为是可以理解的 - 减少使其在单线程范围内是私有的.在将线程的增量值相加并传递给非局部x之后.
我不明白的是y的行为.它就像x一样私有,但它也在临界区内,所以它有多个原因让其他线程无法访问.然而,我认为,恰好是竞争条件.难道 …
在以下reduction + map操作中，没有。3让我感到困惑。谁能解释为什么
// 1
[1,2,3,4,5].filter(x => x==3).reduce((x, y) => y) // -> 3, all good
// 2
[1,2,3,4,5].filter(x => x<=3).reduce((x, y) => 0) // -> 0, still good
// 3
[1,2,3,4,5].filter(x => x==3).reduce((x, y) => 0) // -> 3, hello?
换句话说：如何减少一个元素的数组而忽略0操作映射？最终，它将用于对象数组，因为对象数组.reduce((x,y) => y.attr)也返回y而不是y.attr用于单个元素数组。
我正在寻找一种快速方法来减少排列为大向量的多个相同长度的块。我有 N 个子数组（连续元素），它们排列在一个大数组中。每个子数组都有固定的大小：k。所以整个数组的大小是：N*K
我正在做的是调用内核N次。每次它计算子数组的减少如下：我将迭代大向量中包含的所有子数组：
for(i=0;i<N;i++){
thrust::device_vector< float > Vec(subarray, subarray+k);
float sum = thrust::reduce(Vec.begin(), Vec.end(), (float)0, thrust::plus<float>());
printf("sum %f\n",sum);
}
对于纯 CUDA 我会这样做（伪代码）：
for(i=0;i<N;i++){
reduction_kernel(subarray)
}
您是否有另一种解决方案来一次性执行连续子数组的缩减？使用纯 CUDA 或 Thrust