현대의 듀얼인라인 메모리 모듈 (DIMM)은 메모리 뱅크 근처에 위치한 인-DIMM 프로세서 (IDP)를 구현함으로써 프로세싱-인-메모리 (PIM)을 지원한다. PIM은 빈번한 메모리 액세스로 인해 제한되는 인메모리 조인의 성능을 호스트 중앙 처리 유닛 (...
현대의 듀얼인라인 메모리 모듈 (DIMM)은 메모리 뱅크 근처에 위치한 인-DIMM 프로세서 (IDP)를 구현함으로써 프로세싱-인-메모리 (PIM)을 지원한다. PIM은 빈번한 메모리 액세스로 인해 제한되는 인메모리 조인의 성능을 호스트 중앙 처리 유닛 (CPU)에서 IDP로 연산을 오프로드함으로써 크게 가속화할 수 있다. 그러나 실제 PIM 하드웨어는 최근까지 상용화되지 않았으며, 이전 PIM 지원 조인 알고리즘은 IDP와 빠른 상호-IDP 통신 및 공유 메모리를 가정하는 PIM 하드웨어 시뮬레이터에 의존했다. 반면, 상용 PIM-지원 DIMM에서 IDP는 메모리를 서로 공유하지 않으며, CPU가 IDP 간 통신을 조율해야한다. 이러한 구조적 특성의 차이점으로 인해 이전 연구는 PIM-지원 DIMM과 호환되지 않는다. 그렇기 때문에 PIM을 활용하기 위해서는 DIMM과 그 구조적 특성을 고려하여 설계 및 최적화된 새로운 조인 알고리즘이 필요하다.
본 논문에서는 UPMEM DIMM을 활용한 빠른 인메모리 조인 알고리즘 프로세싱-인-DIMM 조인 알고리즘 (PID-Join)을 설계하고 분석한다. PIM-지원 DIMM은 IDP의 제한된 계산 능력과 공유하지 않는 특성, 빠른 상호-IDP 통신을 위한 하드웨어 지원 부재 및 IDP와 주 메모리 간 느린 데이터 전송 등을 통해 조인을 효율적으로 가속화하는데 핵심적인 도전 과제를 제시한다. PID-Join은 이러한 도전 과제를 극복하기 위해 IDP에 최적화된 해시, 정렬-병합 및 중첩 루프 알고리즘을 프로토타이핑하고 평가하며, 호스트 CPU 캐시스트리밍과 벡터 명령어를 사용하여 빠른 상호-IDP 통신을 가능하게하며, IDP와 주 메모리 간 랭크별 데이터 전송을 가속한다. 8개의 UPMEM DIMM과 1,024개의 IDP를 장착한 실제 시스템을 사용하여 수행한 평가는 PID-Join이 다양한 CPU 기반 인메모리 조인 알고리즘 대비 인메모리 조인의 성능을 크게 향상시킨다.
현대의 듀얼 인라인 메모리 모듈 (DIMM)은 메모리 뱅크 근처에 위치한 인-DIMM 프로세서 (IDP)를 구현함으로써 프로세싱-인-메모리 (PIM)을 지원한다. PIM은 빈번한 메모리 액세스로 인해 제한되는 인메모리 조인의 성능을 호스트 중앙 처리 유닛 (CPU)에서 IDP로 연산을 오프로드함으로써 크게 가속화할 수 있다. 그러나 실제 PIM 하드웨어는 최근까지 상용화되지 않았으며, 이전 PIM 지원 조인 알고리즘은 IDP와 빠른 상호-IDP 통신 및 공유 메모리를 가정하는 PIM 하드웨어 시뮬레이터에 의존했다. 반면, 상용 PIM-지원 DIMM에서 IDP는 메모리를 서로 공유하지 않으며, CPU가 IDP 간 통신을 조율해야한다. 이러한 구조적 특성의 차이점으로 인해 이전 연구는 PIM-지원 DIMM과 호환되지 않는다. 그렇기 때문에 PIM을 활용하기 위해서는 DIMM과 그 구조적 특성을 고려하여 설계 및 최적화된 새로운 조인 알고리즘이 필요하다.
본 논문에서는 UPMEM DIMM을 활용한 빠른 인메모리 조인 알고리즘 프로세싱-인-DIMM 조인 알고리즘 (PID-Join)을 설계하고 분석한다. PIM-지원 DIMM은 IDP의 제한된 계산 능력과 공유하지 않는 특성, 빠른 상호-IDP 통신을 위한 하드웨어 지원 부재 및 IDP와 주 메모리 간 느린 데이터 전송 등을 통해 조인을 효율적으로 가속화하는데 핵심적인 도전 과제를 제시한다. PID-Join은 이러한 도전 과제를 극복하기 위해 IDP에 최적화된 해시, 정렬-병합 및 중첩 루프 알고리즘을 프로토타이핑하고 평가하며, 호스트 CPU 캐시 스트리밍과 벡터 명령어를 사용하여 빠른 상호-IDP 통신을 가능하게하며, IDP와 주 메모리 간 랭크별 데이터 전송을 가속한다. 8개의 UPMEM DIMM과 1,024개의 IDP를 장착한 실제 시스템을 사용하여 수행한 평가는 PID-Join이 다양한 CPU 기반 인메모리 조인 알고리즘 대비 인메모리 조인의 성능을 크게 향상시킨다.
Modern dual in-line memory modules (DIMMs) support processing-in-memory (PIM) by implementing in-DIMM processors (IDPs) located near memory banks. PIM can greatly accelerate in-memory join, whose performance is frequently bounded by main-memory accesses, by offloading the operations of join from hos...
Modern dual in-line memory modules (DIMMs) support processing-in-memory (PIM) by implementing in-DIMM processors (IDPs) located near memory banks. PIM can greatly accelerate in-memory join, whose performance is frequently bounded by main-memory accesses, by offloading the operations of join from host central processing units (CPUs) to the IDPs. As real PIM hardware has not been available until very recently, the prior PIM-assisted join algorithms have relied on PIM hardware simulators which assume fast shared memory between the IDPs and fast inter-IDP communication; however, on commodity PIM-enabled DIMMs, the IDPs do not share memory and demand the CPUs to mediate inter-IDP communication. Such discrepancies in the architectural characteristics make the prior studies incompatible with the DIMMs. Thus, to exploit the high potential of PIM on commodity PIM-enabled DIMMs, we need a new join algorithm designed and optimized for the DIMMs and their architectural characteristics.
In this paper, we design and analyze Processing-In-DIMM Join (PID-Join), a fast in-memory join algorithm which exploits UPMEM DIMMs, currently the only publicly-available PIM-enabled DIMMs. The DIMMs impose several key challenges on efficient acceleration of join including the shared-nothing nature and limited compute capabilities of the IDPs, the lack of hardware support for fast inter-IDP communication, and the slow IDP-wise data transfers between the IDPs and the main memory. PID-Join overcomes the challenges by prototyping and evaluating hash, sort-merge, and nested-loop algorithms optimized for the IDPs, enabling fast inter-IDP communication using host CPU cache streaming and vector instructions, and facilitating fast rank-wise data transfers between the IDPs and the main memory. Our evaluation using a real system equipped with eight UPMEM DIMMs and 1,024 IDPs shows that PID-Join greatly improves the performance of in-memory join over various CPU-based in-memory join algorithms.
Modern dual in-line memory modules (DIMMs) support processing-in-memory (PIM) by implementing in-DIMM processors (IDPs) located near memory banks. PIM can greatly accelerate in-memory join, whose performance is frequently bounded by main-memory accesses, by offloading the operations of join from host central processing units (CPUs) to the IDPs. As real PIM hardware has not been available until very recently, the prior PIM-assisted join algorithms have relied on PIM hardware simulators which assume fast shared memory between the IDPs and fast inter-IDP communication; however, on commodity PIM-enabled DIMMs, the IDPs do not share memory and demand the CPUs to mediate inter-IDP communication. Such discrepancies in the architectural characteristics make the prior studies incompatible with the DIMMs. Thus, to exploit the high potential of PIM on commodity PIM-enabled DIMMs, we need a new join algorithm designed and optimized for the DIMMs and their architectural characteristics.
In this paper, we design and analyze Processing-In-DIMM Join (PID-Join), a fast in-memory join algorithm which exploits UPMEM DIMMs, currently the only publicly-available PIM-enabled DIMMs. The DIMMs impose several key challenges on efficient acceleration of join including the shared-nothing nature and limited compute capabilities of the IDPs, the lack of hardware support for fast inter-IDP communication, and the slow IDP-wise data transfers between the IDPs and the main memory. PID-Join overcomes the challenges by prototyping and evaluating hash, sort-merge, and nested-loop algorithms optimized for the IDPs, enabling fast inter-IDP communication using host CPU cache streaming and vector instructions, and facilitating fast rank-wise data transfers between the IDPs and the main memory. Our evaluation using a real system equipped with eight UPMEM DIMMs and 1,024 IDPs shows that PID-Join greatly improves the performance of in-memory join over various CPU-based in-memory join algorithms.
주제어
#Join algorithms Main memory engines Processing-in-Memory 조인 알고리즘 메인 메모리 엔진 프로세싱-인-메모리
학위논문 정보
저자
임채민
학위수여기관
Graduate School, Yonsei University
학위구분
국내석사
학과
Department of Artificial Intelligence
지도교수
Youngsok Kim
발행연도
2023
총페이지
viii, 85장
키워드
Join algorithms Main memory engines Processing-in-Memory 조인 알고리즘 메인 메모리 엔진 프로세싱-인-메모리
※ AI-Helper는 부적절한 답변을 할 수 있습니다.