프리 페치 예?
누구든지 __builtin_prefetch상당한 성능 이점을 얻기 위해 GCC (또는 일반적으로 asm 명령어 prefetcht0)에서 사용하는 예제에 대한 링크 나 예제를 제공 할 수 있습니까 ? 특히 다음 기준을 충족하는 예제를 원합니다.
- 간단하고 작으며 독립적 인 예입니다.
__builtin_prefetch명령을 제거하면 성능이 저하됩니다.- 치환 후의
__builtin_prefetch성능 저하에 대응하는 메모리 액세스 명령 결과.
즉, __builtin_prefetch최적화 없이는 관리 할 수없는 최적화 를 수행하는 가장 짧은 예를 원합니다 .
여기에 제가 더 큰 프로젝트에서 가져온 실제 코드가 있습니다. (죄송합니다. 프리 페치로 인해 눈에 띄는 속도가 빨라진 것 중 가장 짧은 코드입니다.)이 코드는 매우 큰 데이터 전치를 수행합니다.
이 예제는 GCC가 내보내는 것과 동일 할 수있는 SSE 프리 페치 명령어를 사용합니다.
이 예제를 실행하려면 x64 용으로 컴파일하고 4GB 이상의 메모리가 있어야합니다. 더 작은 데이터 크기로 실행할 수 있지만 시간이 너무 빠릅니다.
#include <iostream>
using std::cout;
using std::endl;
#include <emmintrin.h>
#include <malloc.h>
#include <time.h>
#include <string.h>
#define ENABLE_PREFETCH
#define f_vector __m128d
#define i_ptr size_t
inline void swap_block(f_vector *A,f_vector *B,i_ptr L){
// To be super-optimized later.
f_vector *stop = A + L;
do{
f_vector tmpA = *A;
f_vector tmpB = *B;
*A++ = tmpB;
*B++ = tmpA;
}while (A < stop);
}
void transpose_even(f_vector *T,i_ptr block,i_ptr x){
// Transposes T.
// T contains x columns and x rows.
// Each unit is of size (block * sizeof(f_vector)) bytes.
//Conditions:
// - 0 < block
// - 1 < x
i_ptr row_size = block * x;
i_ptr iter_size = row_size + block;
// End of entire matrix.
f_vector *stop_T = T + row_size * x;
f_vector *end = stop_T - row_size;
// Iterate each row.
f_vector *y_iter = T;
do{
// Iterate each column.
f_vector *ptr_x = y_iter + block;
f_vector *ptr_y = y_iter + row_size;
do{
#ifdef ENABLE_PREFETCH
_mm_prefetch((char*)(ptr_y + row_size),_MM_HINT_T0);
#endif
swap_block(ptr_x,ptr_y,block);
ptr_x += block;
ptr_y += row_size;
}while (ptr_y < stop_T);
y_iter += iter_size;
}while (y_iter < end);
}
int main(){
i_ptr dimension = 4096;
i_ptr block = 16;
i_ptr words = block * dimension * dimension;
i_ptr bytes = words * sizeof(f_vector);
cout << "bytes = " << bytes << endl;
// system("pause");
f_vector *T = (f_vector*)_mm_malloc(bytes,16);
if (T == NULL){
cout << "Memory Allocation Failure" << endl;
system("pause");
exit(1);
}
memset(T,0,bytes);
// Perform in-place data transpose
cout << "Starting Data Transpose... ";
clock_t start = clock();
transpose_even(T,block,dimension);
clock_t end = clock();
cout << "Done" << endl;
cout << "Time: " << (double)(end - start) / CLOCKS_PER_SEC << " seconds" << endl;
_mm_free(T);
system("pause");
}
ENABLE_PREFETCH를 활성화 한 상태에서 실행하면 다음과 같은 출력이 나타납니다.
bytes = 4294967296
Starting Data Transpose... Done
Time: 0.725 seconds
Press any key to continue . . .
ENABLE_PREFETCH를 비활성화 한 상태에서 실행하면 다음과 같이 출력됩니다.
bytes = 4294967296
Starting Data Transpose... Done
Time: 0.822 seconds
Press any key to continue . . .
따라서 프리 페치로 인한 속도가 13 % 향상되었습니다.
편집하다:
더 많은 결과는 다음과 같습니다.
Operating System: Windows 7 Professional/Ultimate
Compiler: Visual Studio 2010 SP1
Compile Mode: x64 Release
Intel Core i7 860 @ 2.8 GHz, 8 GB DDR3 @ 1333 MHz
Prefetch : 0.868
No Prefetch: 0.960
Intel Core i7 920 @ 3.5 GHz, 12 GB DDR3 @ 1333 MHz
Prefetch : 0.725
No Prefetch: 0.822
Intel Core i7 2600K @ 4.6 GHz, 16 GB DDR3 @ 1333 MHz
Prefetch : 0.718
No Prefetch: 0.796
2 x Intel Xeon X5482 @ 3.2 GHz, 64 GB DDR2 @ 800 MHz
Prefetch : 2.273
No Prefetch: 2.666
이진 검색은 명시 적 프리 페치의 이점을 얻을 수있는 간단한 예입니다. 이진 검색의 액세스 패턴은 하드웨어 프리 페처에 거의 무작위로 보이므로 가져올 항목을 정확하게 예측할 가능성이 거의 없습니다.
이 예에서는 현재 반복에서 다음 루프 반복의 두 가능한 '중간'위치를 프리 페치합니다. 프리 페치 중 하나는 사용되지 않지만 다른 하나는 사용됩니다 (최종 반복이 아닌 경우).
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
int binarySearch(int *array, int number_of_elements, int key) {
int low = 0, high = number_of_elements-1, mid;
while(low <= high) {
mid = (low + high)/2;
#ifdef DO_PREFETCH
// low path
__builtin_prefetch (&array[(mid + 1 + high)/2], 0, 1);
// high path
__builtin_prefetch (&array[(low + mid - 1)/2], 0, 1);
#endif
if(array[mid] < key)
low = mid + 1;
else if(array[mid] == key)
return mid;
else if(array[mid] > key)
high = mid-1;
}
return -1;
}
int main() {
int SIZE = 1024*1024*512;
int *array = malloc(SIZE*sizeof(int));
for (int i=0;i<SIZE;i++){
array[i] = i;
}
int NUM_LOOKUPS = 1024*1024*8;
srand(time(NULL));
int *lookups = malloc(NUM_LOOKUPS * sizeof(int));
for (int i=0;i<NUM_LOOKUPS;i++){
lookups[i] = rand() % SIZE;
}
for (int i=0;i<NUM_LOOKUPS;i++){
int result = binarySearch(array, SIZE, lookups[i]);
}
free(array);
free(lookups);
}
DO_PREFETCH를 활성화 한 상태에서이 예제를 컴파일하고 실행하면 런타임이 20 % 감소합니다.
$ gcc c-binarysearch.c -DDO_PREFETCH -o with-prefetch -std=c11 -O3
$ gcc c-binarysearch.c -o no-prefetch -std=c11 -O3
$ perf stat -e L1-dcache-load-misses,L1-dcache-loads ./with-prefetch
Performance counter stats for './with-prefetch':
356,675,702 L1-dcache-load-misses # 41.39% of all L1-dcache hits
861,807,382 L1-dcache-loads
8.787467487 seconds time elapsed
$ perf stat -e L1-dcache-load-misses,L1-dcache-loads ./no-prefetch
Performance counter stats for './no-prefetch':
382,423,177 L1-dcache-load-misses # 97.36% of all L1-dcache hits
392,799,791 L1-dcache-loads
11.376439030 seconds time elapsed
프리 페치 버전에서 두 배의 L1 캐시로드를 수행하고 있습니다. 실제로 더 많은 작업을 수행하고 있지만 메모리 액세스 패턴은 파이프 라인에 더 친숙합니다. 이것은 또한 장단점을 보여줍니다. 이 코드 블록은 격리 된 상태에서 더 빠르게 실행되지만 캐시에 많은 정크를로드했으며 이로 인해 애플리케이션의 다른 부분에 더 많은 부담을 줄 수 있습니다.
@JamesScriven과 @Mystical이 제공 한 훌륭한 답변에서 많은 것을 배웠습니다. 그러나 그들의 예제는 약간의 향상을 제공합니다.이 답변의 목적은 프리 페치가 더 큰 영향을 미치는 (약 4 인자 내 머신) 예제를 제시하는 것입니다.
최신 아키텍처에는 세 가지 가능한 병목 현상이 있습니다. CPU 속도, 메모리 대역폭 및 메모리 대기 시간입니다. 프리 페치는 메모리 액세스의 지연 시간을 줄이는 것입니다.
지연 시간이 X 계산 단계에 해당하는 완벽한 시나리오에서, 우리는 오라클을 가질 것입니다. 이것은 우리가 X 계산 단계에서 접근 할 메모리를 알려주고,이 데이터의 프리 페칭이 시작되고 바로 도착할 것입니다. 시간 X 계산 단계 이후.
많은 알고리즘에서 우리는이 완벽한 세상에 (거의) 있습니다. 간단한 for 루프의 경우 X 단계 이후에 필요한 데이터를 쉽게 예측할 수 있습니다. 비 순차적 실행 및 기타 하드웨어 트릭은 여기에서 매우 좋은 작업을 수행하여 대기 시간을 거의 완전히 숨 깁니다.
그렇기 때문에 @Mystical의 예가 약간 개선 된 이유입니다. 프리 페처는 이미 꽤 훌륭합니다. 개선의 여지가 많지 않습니다. 이 작업은 메모리 바운드이므로 대역폭이 많이 남아 있지 않을 수 있습니다. 이는 제한 요소가 될 수 있습니다. 내 컴퓨터에서 기껏해야 약 8 % 개선을 볼 수있었습니다.
@JamesScriven 예제의 중요한 통찰력 : 현재 데이터를 메모리에서 가져 오기 전에 우리도 CPU도 다음 액세스 주소를 알지 못합니다.이 종속성은 매우 중요합니다. 그렇지 않으면 비 순차적 실행으로 인해 미래를 예측할 수 있습니다. 하드웨어는 데이터를 미리 가져올 수 있습니다. 그러나 우리는 한 단계 만 추측 할 수 있기 때문에 그다지 잠재력이 없습니다. 내 컴퓨터에서 40 % 이상을 얻을 수 없었습니다.
따라서 경쟁을 준비하고 X 단계에서 액세스되는 주소를 알 수있는 방식으로 데이터를 준비하지만 아직 액세스하지 않은 데이터에 대한 종속성으로 인해 하드웨어가이를 찾을 수 없도록 만듭니다 (마지막에있는 전체 프로그램 참조). 답변) :
//making random accesses to memory:
unsigned int next(unsigned int current){
return (current*10001+328)%SIZE;
}
//the actual work is happening here
void operator()(){
//set up the oracle - let see it in the future oracle_offset steps
unsigned int prefetch_index=0;
for(int i=0;i<oracle_offset;i++)
prefetch_index=next(prefetch_index);
unsigned int index=0;
for(int i=0;i<STEP_CNT;i++){
//use oracle and prefetch memory block used in a future iteration
if(prefetch){
__builtin_prefetch(mem.data()+prefetch_index,0,1);
}
//actual work, the less the better
result+=mem[index];
//prepare next iteration
prefetch_index=next(prefetch_index); #update oracle
index=next(mem[index]); #dependency on `mem[index]` is VERY important to prevent hardware from predicting future
}
}
일부 비고 :
- 데이터는 오라클이 항상 올바른 방식으로 준비됩니다.
- 놀랍게도 CPU 바운드 작업이 적을수록 속도가 빨라집니다. 대기 시간을 거의 완전히 숨길 수 있으므로 속도는
CPU-time+original-latency-time/CPU-time.
리드 컴파일 및 실행 :
>>> g++ -std=c++11 prefetch_demo.cpp -O3 -o prefetch_demo
>>> ./prefetch_demo
#preloops time no prefetch time prefetch factor
...
7 1.0711102260000001 0.230566831 4.6455521002498408
8 1.0511602149999999 0.22651144600000001 4.6406494398521474
9 1.049024333 0.22841439299999999 4.5926367389641687
....
4에서 5 사이의 속도 향상으로.
목록 prefetch_demp.cpp:
//prefetch_demo.cpp
#include <vector>
#include <iostream>
#include <iomanip>
#include <chrono>
const int SIZE=1024*1024*1;
const int STEP_CNT=1024*1024*10;
unsigned int next(unsigned int current){
return (current*10001+328)%SIZE;
}
template<bool prefetch>
struct Worker{
std::vector<int> mem;
double result;
int oracle_offset;
void operator()(){
unsigned int prefetch_index=0;
for(int i=0;i<oracle_offset;i++)
prefetch_index=next(prefetch_index);
unsigned int index=0;
for(int i=0;i<STEP_CNT;i++){
//prefetch memory block used in a future iteration
if(prefetch){
__builtin_prefetch(mem.data()+prefetch_index,0,1);
}
//actual work:
result+=mem[index];
//prepare next iteration
prefetch_index=next(prefetch_index);
index=next(mem[index]);
}
}
Worker(std::vector<int> &mem_):
mem(mem_), result(0.0), oracle_offset(0)
{}
};
template <typename Worker>
double timeit(Worker &worker){
auto begin = std::chrono::high_resolution_clock::now();
worker();
auto end = std::chrono::high_resolution_clock::now();
return std::chrono::duration_cast<std::chrono::nanoseconds>(end-begin).count()/1e9;
}
int main() {
//set up the data in special way!
std::vector<int> keys(SIZE);
for (int i=0;i<SIZE;i++){
keys[i] = i;
}
Worker<false> without_prefetch(keys);
Worker<true> with_prefetch(keys);
std::cout<<"#preloops\ttime no prefetch\ttime prefetch\tfactor\n";
std::cout<<std::setprecision(17);
for(int i=0;i<20;i++){
//let oracle see i steps in the future:
without_prefetch.oracle_offset=i;
with_prefetch.oracle_offset=i;
//calculate:
double time_with_prefetch=timeit(with_prefetch);
double time_no_prefetch=timeit(without_prefetch);
std::cout<<i<<"\t"
<<time_no_prefetch<<"\t"
<<time_with_prefetch<<"\t"
<<(time_no_prefetch/time_with_prefetch)<<"\n";
}
}
에서 문서 :
for (i = 0; i < n; i++)
{
a[i] = a[i] + b[i];
__builtin_prefetch (&a[i+j], 1, 1);
__builtin_prefetch (&b[i+j], 0, 1);
/* ... */
}
예를 들어 하나의 명령어로 uint32_t [16]을 사전로드하기 위해 대부분의 최신 64 비트 프로세서의 경우 64 바이트 인 캐시 라인 크기로 프리 페칭 데이터를 최적화 할 수 있습니다.
For example on ArmV8 I discovered through experimentation casting the memory pointer to a uint32_t 4x4 matrix vector (which is 64 bytes in size) halved the required instructions required as before I had to increment by 8 as it was only loading half the data, even though my understanding was that it fetches a full cache line.
Pre-fetching an uint32_t[32] original code example...
int addrindex = &B[0];
__builtin_prefetch(&V[addrindex]);
__builtin_prefetch(&V[addrindex + 8]);
__builtin_prefetch(&V[addrindex + 16]);
__builtin_prefetch(&V[addrindex + 24]);
After...
int addrindex = &B[0];
__builtin_prefetch((uint32x4x4_t *) &V[addrindex]);
__builtin_prefetch((uint32x4x4_t *) &V[addrindex + 16]);
For some reason int datatype for the address index/offset gave better performance. Tested with GCC 8 on Cortex-a53. Using an equivalent 64 byte vector on other architectures might give the same performance improvement if you find it is not pre-fetching all the data like in my case. In my application with a one million iteration loop, it improved performance by 5% just by doing this. There were further requirements for the improvement.
the 128 megabyte "V" memory allocation had to be aligned to 64 bytes.
uint32_t *V __attribute__((__aligned__(64))) = (uint32_t *)(((uintptr_t)(__builtin_assume_aligned((unsigned char*)aligned_alloc(64,size), 64)) + 63) & ~ (uintptr_t)(63));
Also, I had to use C operators instead of Neon Intrinsics, since they require regular datatype pointers (in my case it was uint32_t *) otherwise the new built in prefetch method had a performance regression.
My real world example can be found at https://github.com/rollmeister/veriumMiner/blob/main/algo/scrypt.c in the scrypt_core() and its internal function which are all easy to read. The hard work is done by GCC8. Overall improvement to performance was 25%.
참고URL : https://stackoverflow.com/questions/7327994/prefetching-examples
'UFO ET IT' 카테고리의 다른 글
| 관리 빈과 백업 빈의 차이점 (0) | 2020.12.04 |
|---|---|
| 그래프 자동 레이아웃 알고리즘 (0) | 2020.12.04 |
| 파이썬을 사용하여 한 쌍의 비선형 방정식을 푸는 방법은 무엇입니까? (0) | 2020.12.04 |
| 크롬 : 포스트 데이터의 출처? (0) | 2020.12.04 |
| Swift에서 UILabel의 textColor를 설정하는 방법 (0) | 2020.12.03 |