에 배열 찾고 나는 방법 더 efficent 것 나사산 2 perallel을 사용하여 배열에 값을 검색하는 동안효율 문제 - 병렬 스레드
요청 인터뷰 질문 우연히
1 읽기 배열의 각 반은 다른 스레드에 있습니다 (반으로 분할) (2) 홀수 및 짝수 위치의 배열 (홀수 위치를 읽는 스레드
및 배열의 짝수 번째 위치를 읽는 스레드).
왜 다른 사람이 더 효과적인지 이해하지 못합니다. 다른 누군가가 나를 위해 이것을 해결할 경우 미리 감사드립니다.
배열을 반으로 분할하는 것은 거의 확실합니다. 거의 절대로 느리지 않으며 훨씬 빨라질 수 있습니다.
이유는 매우 간단합니다. 메모리에서 데이터를 읽을 때 프로세서는 일반적으로 한 번에 전체 캐시 라인을 읽습니다. 정확한 크기는 프로세서에 따라 다르지만 전체적으로 중요하지는 않습니다 (64 바이트와 같은 것이 신경 쓰이는 곳에서는 야구장에있을 것입니다). 요점은 한 번에 여러 바이트의 연속 된 청크를 읽는 것입니다 .
홀수/짝수 버전의 경우 두 스레드를 실행하는 두 프로세서 모두 모두의 데이터를 읽어야합니다. 데이터를 절반으로 나누면 각 코어는 절반의 데이터 만 읽습니다. 분할이 캐시 라인 경계에 있지 않으면 각각은 약간의 여분을 읽습니다 (캐시 라인의 크기까지 반올림해야합니다). 평균적으로 각각의 캐시 라인을 절반으로 늘려 읽을 필요가 있습니다.
"프로세서"가 실제로 동일한 프로세서 다이에서 2 개의 코어 인 경우, 어떤 방법 으로든 큰 차이를 내지 않을 가능성이 있습니다. 이 경우 병목 현상은 일반적으로 주 메모리에서 가장 낮은 수준의 프로세서 캐시로 데이터를 읽는 것입니다. 단 한 개의 스레드로도 메모리에서 읽을 수있는만큼 빠르게 데이터를 검색 할 수 있으며 (데이터 사용 방법에 관계없이) 스레드를 추가 할 수는 없습니다. 일을 많이 향상시킵니다 (전혀).
나는 위의 주석을 달았습니다. 지금은 약간의 어리석은 소리를냅니다. 왜냐하면 두 프로세서 모두 캐시 라인에 맞는 데이터 양을 읽을 것이기 때문입니다. –
차이점은 절반 분할의 경우 메모리는 인덱스 0 -> N/2 및 N/2 -> N에서 각각 검색하여 캐시를 최대화하는 왼쪽에서 오른쪽으로 각 스레드에 의해 선형으로 액세스된다는 것입니다 메모리의 프리 페치가 선형 적으로 수행되기 때문에 사용량이 늘어납니다.
두 번째 경우 (짝수 홀수)에서는 캐시 성능이 나빠질 수 있습니다. 사용하지 않는 항목을 프리 페치 할 때뿐만 아니라 (스레드 0은 요소 0, 1 등을 사용하지만 그 중 절반 만 사용하기 때문에)), 또한 캐시 핑퐁 효과 (쓰기의 경우, 그러나 이것은 당신의 예제에서 행해지 지 않음) 때문이기도합니다.
이것은 아마도 캐시 성능에 관한 것입니다. – thiton
두 스레드가 같은 시작 주소 에서 읽을 수 있기 때문에 캐시의 나머지 절반의 데이터를 읽을 때 배열의 두 번째 절반을 읽지 않을 수 있습니다. –
예. 그 대답은 자답이 될 것입니다. – thiton