SIMD를 사용한 HOG 최적화

Question

OpenCV, Dlib 및 Simd과 같이 HOG 설명자를 계산할 때 여러 가지 시도가 있습니다. 그들 모두는 HOG 히스토그램으로 결과 크기를 추가하는 스칼라 코드를 사용

는

float histogram[height/8][width/8][18]; 
float ky[height], kx[width]; 
int idx[size]; 
float val[size]; 

for(size_t i = 0; i < size; ++i) 
{ 
    histogram[y/8][x/8][idx[i]] += val[i]*ky[y]*kx[x]; 
    histogram[y/8][x/8 + 1][idx[i]] += val[i]*ky[y]*kx[x + 1]; 
    histogram[y/8 + 1][x/8][idx[i]] += val[i]*ky[y + 1]*kx[x]; 
    histogram[y/8 + 1][x/8 + 1][idx[i]] += val[i]*ky[y + 1]*kx[x + 1]; 
} 

이 size의 값은 구현에서 따라 다르지만 일반적으로 의미는 동일합니다.

저는 histogram calculation with using of SIMD의 문제가 간단하고 효과적인 해결책이 없다는 것을 알고 있습니다. 그러나이 경우에는 작은 크기 (18)의 막대 그래프가 있습니다. SIMD 최적화에서 도움이 될 수 있습니까?

Answer 1

해결책을 찾았습니다. 시간 버퍼입니다. 처음에는 히스토그램을 임시 버퍼에 더합니다 (이 작업을 벡터화 할 수 있음). 그럼 출력 히스토그램 버퍼로부터 추가 합 (이 동작은 벡터화 할 수있다) :

float histogram[height/8][width/8][18]; 
float ky[height], kx[width]; 
int idx[size]; 
float val[size]; 
float buf[18][4]; 

for(size_t i = 0; i < size; ++i) 
{ 
    buf[idx[i]][0] += val[i]*ky[y]*kx[x]; 
    buf[idx[i]][1] += val[i]*ky[y]*kx[x + 1]; 
    buf[idx[i]][2] += val[i]*ky[y + 1]*kx[x]; 
    buf[idx[i]][3] += val[i]*ky[y + 1]*kx[x + 1]; 
} 

for(size_t i = 0; i < 18; ++i) 
{ 
    histogram[y/8][x/8][i] += buf[i][0]; 
    histogram[y/8][x/8 + 1][i] += buf[i][1]; 
    histogram[y/8 + 1][x/8][i] += buf[i][2]; 
    histogram[y/8 + 1][x/8 + 1][i] += buf[i][3]; 
} 

Answer 2

SIMD를 사용하여 모든 (병합 된) 막대 그래프 인덱스와 빈 증분을 계산하여 부분 최적화를 할 수 있습니다. 그런 다음 나중에 스칼라 루프로 처리하십시오. 임시 빈 인덱스를 유지하고 캐시에서 증가시키기 위해 한 번에 한 행을 처리하도록이 작업을 제거해야 할 수도 있습니다. 임시 중간 버퍼의 사용으로 인해 이것이 비효율적으로 보일 수도 있지만, 실제로는 유사한 시나리오에서 전반적인 유용성을 보았습니다.

uint32_t i = 0; 

for (y = 0; y < height; ++y) // for each row 
{ 
    uint32_t inds[width * 4]; // flattened histogram indices for this row 
    float vals[width * 4];  // histogram bin increments for this row 

    // SIMD loop for this row - calculate flattened histogram indices and bin 
    // increments (scalar code shown for reference - converting this loop to 
    // SIMD is left as an exercise for the reader...) 

    for (x = 0; x < width; ++x, ++i) 
    { 
     indices[4*x] = (y/8)*(width/8)*18+(x/8)*18+idx[i]; 
     indices[4*x+1] = (y/8)*(width/8)*18+(x/8 + 1)*18+idx[i]; 
     indices[4*x+2] = (y/8+1)*(width/8)*18+(x/8)*18+idx[i]; 
     indices[4*x+3] = (y/8+1)*(width/8)*18+(x/8 + 1)*18+idx[i]; 

     vals[4*x] = val[i]*ky[y]*kx[x]; 
     vals[4*x+1] = val[i]*ky[y]*kx[x+1]; 
     vals[4*x+2] = val[i]*ky[y+1]*kx[x]; 
     vals[4*x+3] = val[i]*ky[y+1]*kx[x+1]; 
    } 

    // scalar loop for this row 

    float * const histogram_base = &histogram[0][0][0]; // pointer to flattened histogram 

    for (x = 0; x < width * 4; ++x) // for each set of 4 indices/increments in this row 
    { 
     histogram_base[indices[x]] += vals[x]; // update the (flattened) histogram 
    } 

}