메모리 액세스 패턴

Memory access pattern

컴퓨팅에서 메모리 액세스 패턴 또는 IO 액세스 패턴은 시스템 또는 프로그램이 2차 스토리지에서 메모리를 읽고 쓰는 패턴입니다.이러한 패턴은 참조 지역 수준이 다르며 캐시 [1]성능에 큰 영향을 미치며 공유 메모리 [4]시스템의 워크로드 병렬화[2][3] 및 분산에 대한 접근 방식에도 영향을 미칩니다.또한 캐시 일관성 문제는 멀티프로세서 [5]성능에 영향을 미칠 수 있습니다.즉, 특정 메모리액세스 패턴은 병렬화에 제한을 두고 있습니다(다양한 핵심 접근 방식은 이를 [6]깨려고 합니다).

컴퓨터 메모리는 보통 "랜덤 액세스"로 설명되지만 소프트웨어에 의한 트래버설은 여전히 효율을 위해 악용될 수 있는 패턴을 보여줍니다.시스템[7] 설계자와 프로그래머가 메모리 액세스 패턴을 이해, 분석 및 개선하기 위한 다양한 툴이 존재합니다.VTune 및 Vectorization Advisor [8][9][10][11][12]등 GPU 메모리 액세스[13] 패턴에 대응하는 툴도 포함됩니다.

메모리 액세스 패턴은 [14][15]보안에도 영향을 미칩니다.[16][17]이 때문에 프라이버시상의 이유로 프로그램의 액티비티를 숨기려고 하는 사람도 있습니다.

예

일부 출판물에서는 순차 패턴과[18] 선형 패턴이 서로 대응되는 패턴으로 잘못 그려지지만 실제 워크로드에는 거의 무수한 패턴이 포함되어 있습니다.

시퀀셜

주요 기사:시퀀셜 액세스

가장 간단한 것은 시퀀셜액세스 패턴입니다.이 패턴에서는, 데이터의 읽기, 처리, 기입은, 간단한 증가/감소 어드레싱으로 행해집니다.이러한 액세스 패턴은 프리페치에 매우 적합합니다.

기울어져 있다

스트라이드형 또는 단순한 2D, 3D 액세스 패턴(예를 들어 다차원 어레이를 통한 단계적 접근)도 마찬가지로 쉽게 예측할 수 있으며 선형 대수 알고리즘 및 이미지 처리 구현에서 찾을 수 있습니다.루프 타일링은 효과적인 [19]접근법입니다.DMA를 탑재한 일부 시스템에서는 대규모 2D 어레이의 서브파일과 스크래치패드 [20]메모리 간에 데이터를 전송하는 스트라이드 모드를 제공했습니다.

선형

선형 액세스 패턴은, 메모리 주소가 몇개의 인덱스의 선형 조합으로부터 계산되는 「스트라이드」와 밀접하게 관련지어져 있다.선형 패턴을 사용하여 인덱스를 순차적으로 통과하면 비스듬히 액세스할 수 있습니다.쓰기용 선형 액세스 패턴(중복되지 않는 읽기용 액세스 패턴 포함)은 알고리즘을 병렬화할 수 있으며, 이는 컴퓨팅 커널을 지원하는 시스템에서 이용됩니다.

가장 가까운 이웃

가장 가까운 네이버메모리 액세스패턴이 시뮬레이션에 표시되며 순차 패턴 또는 스트라이드 패턴과 관련되어 있습니다.알고리즘은 계산을 수행하기 위해 데이터 요소의 가장 가까운 인접(하나 이상의 차원)으로부터의 정보를 사용하여 데이터 구조를 통과할 수 있다.이는 [21]그리드 상에서 동작하는 물리 시뮬레이션에서 공통적으로 나타난다.가장 가까운 네이버는 클러스터 내의 노드간 통신을 참조할 수도 있습니다.이러한 로컬접근 패턴에 의존하는 물리 시뮬레이션은 클러스터 노드로 분할된 데이터와 병렬화할 수 있으며, 이들 사이에 순수하게 가장 가까운 네이버 통신이 있어 지연 및 통신 대역폭에 이점이 있을 수 있습니다.이 사용 사례는 torus 네트워크 [22]토폴로지에 잘 매핑됩니다.

공간적으로 일관성이 있는 2D

3D 렌더링에서 텍스처 매핑 및 작은 프리미티브 래스터라이제이션(복잡한 표면의 임의 왜곡 포함)을 위한 액세스 패턴은 선형과는 거리가 멀지만 여전히 공간적 인접성(예: 화면 공간 또는 텍스처 공간)을 나타낼 수 있습니다.텍스처 맵과 프레임 버퍼 데이터(공간 영역을 캐시 라인에 매핑)에 대한 모튼[23] 순서와 타일을 조합하거나 타일 기반 지연 [24]렌더링을 통해 프리미티브를 정렬함으로써 메모리 인접성을 높일 수 있습니다.선형 대수 라이브러리에서 [25]행렬을 모르톤 순서로 저장하는 것도 유리할 수 있습니다.

흩어지다

산란 메모리 액세스 패턴은 순차 읽기와 쓰기용 [26]색인/랜덤 주소 지정을 결합합니다.수집에 비해 처리 요소가 소스 데이터에 예측 가능한 프리페치(또는 DMA)를 사용하면서 "fire and forget" 방식으로 쓰기를 디스패치할 수 있기 때문에 캐시 계층에 대한 부하를 줄일 수 있습니다.

그러나 쓰기가 상호 [27]작용하지 않는다는 보장이 없기 때문에 병렬화가 더 어려울 수 있으며, 많은 시스템은 여전히 하드웨어 캐시가 많은 작은 쓰기를 더 큰 쓰기로 통합한다고 가정하여 설계되어 있습니다.

과거에는 순방향 텍스처 매핑이 소스 텍스처 정보를 순차적으로 읽으면서 "쓰기"로 랜덤성을 처리하려고 시도했습니다.

PlayStation 2 콘솔은 기존의 역 텍스처 매핑을 사용했지만 EDRAM을 사용하여 "온칩" 산란/수집 처리를 처리했으며, 메인 메모리의 3D 모델(및 많은 텍스처 데이터)은 DMA에 의해 순차적으로 공급되었습니다.그렇기 때문에 인덱스된 프리미티브를 지원하지 않았고 때로는 디스플레이 목록에서 "앞으로" 텍스처를 관리해야 했습니다.

모이다

수집 메모리 액세스 패턴에서는, 읽기는 랜덤으로 행선지 지정 또는 인덱스 지정되지만, 쓰기는 시퀀셜(또는 리니어)[26]입니다.예를 들어 스캔 라인에 걸쳐 데이터를 직선적으로 쓸 수 있는 역 텍스처 매핑에서 랜덤 액세스 텍스처 주소가 픽셀 단위로 계산된다.

분산에 비해 캐시(및 지연 시간 무시)는 이제 작은 요소의 효율적인 읽기에 필수적이지만 쓰기가 중복되지 않도록 보장되므로 병렬화가 더 쉽다는 단점이 있습니다.이와 같이, gpgpu 프로그래밍에서는,[27] 읽기 지연을 숨기기 위해서 대규모 스레드화([27]병렬화에 의해서 유효)가 사용되는, 개더 어프로치가 보다 일반적입니다.

집합과 산포의 조합

알고리즘은 하나의 소스에서 데이터를 수집하여 로컬 또는 칩 메모리에서 계산을 수행하고 결과를 다른 곳으로 분산시킬 수 있습니다.이는 기본적으로 3D 렌더링을 수행할 때 GPU 파이프라인의 전체 작동으로, 인덱싱된 정점과 텍스처를 수집하고 화면 공간에 음영 처리된 픽셀을 산란시킵니다.깊이 버퍼를 사용한 불투명한 프리미티브의 래스터화는 "가환적"으로, 병렬 실행을 용이하게 하는 정렬을 가능하게 합니다.일반적인 경우 동기화 프리미티브가 필요합니다.

랜덤

주요 기사: 랜덤 액세스

정반대인 것은 진정한 랜덤 메모리 액세스 패턴입니다.일부 멀티프로세서 시스템은 이러한 [28]문제에 대처하기 위해 특화되어 있습니다.PGAS 접근법은 데이터를 기준으로 작업을 즉시 정렬하는 데 도움이 될 수 있습니다(문제는 *정렬되지 않은 [21]데이터의 인접성을 파악하는* 경우에 유용합니다).포인터 추적에 크게 의존하는 데이터 구조는 정렬이 도움이 될 수 있지만 종종 참조 인접성이 저하될 수 있습니다.정말로 랜덤한 메모리액세스 패턴을 지정하면, 그 패턴을 분해할 수 있습니다(스캐터 스테이지나 수집 스테이지, 또는 그 외의 중간 정렬을 포함한다).이것은 대부분의 경우 병렬화의 전제 조건입니다.

접근

데이터 지향 설계

데이터 지향 설계는 보다 일반적인 객체 지향 접근법(즉, 데이터 레이아웃이 액세스 [29]패턴을 명시적으로 반영하도록 구성)과 대조하여 프로그램의 다양한 단계에서 데이터를 통과하는 방법에 따라 데이터를 구성함으로써 참조의 인접성을 극대화하려는 접근법이다.

참조 지역과의 대조

참조 인접성은 메모리 액세스 패턴에 의해 표시되는 속성을 나타냅니다.프로그래머는 메모리 액세스 패턴(알고리즘의 재작업에 의해)을 변경하여 [30]참조의 인접성을 향상시키고/[26]또는 병렬화 가능성을 높인다.프로그래머 또는 시스템 설계자는 특정 메모리 액세스 [31][32]패턴을 캡슐화하는 프레임워크 또는 추상화(예를 들어 C++ 템플릿 또는 고차 함수)를 작성할 수 있습니다.

메모리 액세스 패턴에 대한 다른 고려사항은 참조의 장소(읽기와 쓰기의 분리)를 넘어 병렬로 나타납니다.예: 읽기와 쓰기가 "완벽한" 로컬인 경우에도 의존관계로 인해 병렬화가 불가능할 수 있습니다.읽기와 쓰기를 다른 영역으로 분리하면 메모리 액세스 패턴이 생깁니다.처음에는 순수한 로컬 용어로 볼 때 더 나빠 보일 수 있지만 최신 [26]병렬 하드웨어를 활용하는 것이 좋습니다.

참조의 인접성은 개별 변수(예를 들어 컴파일러의 레지스터 캐시 기능)를 참조할 수도 있지만 메모리 액세스 패턴이라는 용어는 인덱스 가능한 메모리(특히 메인 메모리)에 보관된 데이터만을 참조할 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ "data oriented design" (PDF).
  2. ^ Jang, Byunghyun; Schaa, Dana; Mistry, Perhaad & Kaeli, David (2010-05-27). "Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures". IEEE Transactions on Parallel and Distributed Systems. New York: IEEE. 22 (1): 105–118. doi:10.1109/TPDS.2010.107. eISSN 1558-2183. ISSN 1045-9219. S2CID 15997131. NLM unique id 101212014.
  3. ^ Jeffers, James; Reinders, James; Sodani, Avinash (2016-05-31). xeon phi optimization. ISBN 9780128091951.
  4. ^ "Analysis of Energy and Performance of Code Transformations for PGAS-based Data Access Patterns" (PDF).
  5. ^ "enhancing cache coherent architectures with memory access patterns for embedded many-core systems" (PDF).
  6. ^ "intel terascale" (PDF).
  7. ^ analysis of memory access patterns. WWC '98. 29 November 1998. p. 105. ISBN 9780769504506.
  8. ^ "QUAD a memory access pattern analyser" (PDF).
  9. ^ "Dymaxion: Optimizing Memory Access Patterns for Heterogeneous Systems" (PDF).
  10. ^ "evaluation of a memory access classification scheme for pointer intensive and numeric programs". 1996. CiteSeerX 10.1.1.48.4163. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  11. ^ Matsubara, Yuki; Sato, Yukinori (2014). "Online Memory Access Pattern Analysis on an Application Profiling Tool". 2014 Second International Symposium on Computing and Networking. pp. 602–604. doi:10.1109/CANDAR.2014.86. ISBN 978-1-4799-4152-0. S2CID 16476418.
  12. ^ "Putting Your Data and Code in Order: Data and layout".
  13. ^ CuMAPz: a tool to analyze memory access patterns in CUDA. Dac '11. 5 June 2011. pp. 128–133. doi:10.1145/2024724.2024754. ISBN 9781450306362. S2CID 16065152.
  14. ^ "Memory Access Pattern Protection for Resource-constrained Devices" (PDF).
  15. ^ "understanding cache attacks" (PDF).
  16. ^ "protecting data in the cloud".
  17. ^ "boosting-cloud-security-with----oblivious-ram". 24 September 2013.메모리 액세스 패턴의 취약성을 회피하는 RAM 설계 제안
  18. ^ Chuck Paridon. "Storage Performance Benchmarking Guidelines - Part I: Workload Design" (PDF). In practice, IO access patterns are as numerous as the stars
  19. ^ "optimizing for tiling and data locality" (PDF).종이 커버 루프 타일링 및 병렬 코드의 시사점
  20. ^ "Optimal 2D Data Partitioning for DMA Transfers on MPSoCs" (PDF).
  21. ^ a b "partitioned global address space programming". YouTube.PGAS가 승리하는 경우, 데이터가 아직 정렬되지 않은 경우(예: 복잡한 그래프 처리)를 다룬다. "불규칙 스펙트럼에 걸친 과학"을 참조한다.
  22. ^ "Quantifying Locality In The Memory Access Patterns of HPC Applications" (PDF).에 클러스터 내에서 가장 가까운 네이버접근 패턴을 나타냅니다.
  23. ^ "The Design and Analysis of a Cache Architecture for Texture Mapping" (PDF).morton order 참조, 액세스 패턴 표시
  24. ^ "morton order to accelerate texturing" (PDF).
  25. ^ "Morton-order Matrices Deserve Compilers' Support Technical Report 533" (PDF).행렬에 대한 모르톤 질서의 중요성을 논하다
  26. ^ a b c d "gpgpu scatter vs gather". Archived from the original on 2016-06-14. Retrieved 2016-06-13.
  27. ^ a b c GPU gems. 2011-01-13. ISBN 9780123849892.에서는 텍스트 내의 '메모리 액세스 패턴'과 '메모리 액세스 패턴'에 대해 설명합니다.
  28. ^ "Cray and HPCC: Benchmark Developments and Results from the Past Year" (PDF).Cray X1에 대한 글로벌 랜덤 액세스 결과 참조. 지연 시간을 숨기기 위한 벡터 아키텍처, 캐시 일관성에 그다지 민감하지 않음
  29. ^ "data oriented design" (PDF).
  30. ^ "optimize-data-structures-and-memory-access-patterns-to-improve-data-locality".
  31. ^ "Template-based Memory Access Engine for Accelerators in SoCs" (PDF).
  32. ^ "Multi-Target Vectorization With MTPS C++ Generic Library" (PDF).최적화된 메모리 액세스 패턴을 생성하기 위한 C++ 템플릿 라이브러리