병렬성 : 자원이 많은 것 (우리가 원하는 것)
- 순차 프로그래밍 : 병렬 자원이 하나인 "것처럼" (비효율적임 2005년 : Dennard scaling 끝)
- 병렬 프로그래밍 : 병렬 자원을 명확하게 인식(ex : 멀티 쓰레드)
병렬 프로그래밍의 어려움
- 동시성 : 여러 자원( ex: 멀티 쓰레드 )이 같은 자원(ex: 메모리)을 공유하고 동시 접근.
- 모듈성 저하 : 다른 자원의 불의의 습격(data race, use-after-free,...)
- 복잡한 동기화 : 공격적인 최적화로 인해 (불의의 습격에도 불구하고...)
- 새로운 병렬 자원
- 계산 : GPU, NPU,(DNN 가속기)..
- 저장 : 분산 메모리 시스템, 분산 스토리지 시스템, 영속성 메모리,...
- 통신 : 8000Gbps, 프로그래밍 가능한 스위치,
- 하드웨어: 전깃줄/기억장치를 "소프트웨어 짜듯이"..
우리의 목표 : 쉬운 병렬 프로그래밍.
- 추상화(PL) : 복잡한 세부사항을 감추는 간단한 언어/라이브러리
- 최종 목표 : 순차 프로그래밍과 같은 난의도로 병렬 프로그래밍
- 추상화 디자인
- 병렬 프로그래밍의 어려움을 정확하게 해결
- 프로그래머의 의도를 명확하게 포착
- 추상화 검증
- 수학적으로 엄밀하게 증명(Coq <- 증명하기 위한 도구)
- 경험 : 엄밀하게 증명 안 하면 대체로 틀림..(POPL 2017, PLDI 2017..)
병렬 프로그램 디자인 및 검증 프로젝트
- 연구주제
- 영속성 메모리
- 하드웨어
- 스케줄링
- 약한 메모리
- 메모리 재활용
동시성 프로그램의 메모리 재활용 문제
상황 : Linked LIst 있고, 여러 쓰레드가 있는 상황.
L1이 한 블럭(노드1)을 보고 있는 상태에서 L2가 같은 블럭(노드1)을 삭제하면(노드 연결해제) use-after-free문제 발생.
-> L1이 다 사용할 때까지 기다렸다가 free 해야 함.
포인터 보호 기법(Hazard pointers)
보고 있던 블럭(노드1)를 보호(다 사용했다고 알릴 때까지) 한 상태. 즉 보호를 함으로써 문제 해결.
-> 그렇지만 성능 안 좋아. protect, unprotect함수를 불러야 하기에.
단점: 높지 않은 성능
다양한 메모리 재활용 기법
| 성능 | 사용성 | 낙관적 순위 적용 |
긴 작업 적용 | 기타 적용성 | 막힘없는 재활용 |
|
| 포인터 보호 기법 |
중간 | 낮음 | 불가능 | 가능 | 특이사항 x | 가능 |
| 영역 보호 기법 | 높음 | 높음 | 가능 | 불가능 | 특이사항x | 불가능 |
| VBR | 높음 | 높음 | 가능 | 불가능 | free한 객체도 접근함 | 가능 |
| NBR | 높음 | 높음 | 가능 | 불가능 | 읽기/쓰기 교차불가능 | 가능 |
전부 만족은 어려움. <- 이론적으로 불가능.
| PEBR (PLDI 2020) |
중간 | 낮음 | 가능 | 불가능 | 특이사항x | 가능 |
| HP++ 해저드 포인터 (submitted) |
중간 | 낮음 | 가능 | 가능 | 특이사항x | 가능 |
Q. 이 지표 중 동시성 메모리에서 가장 중요한 요소는?
-> 낙관적 순회, 긴 작업, 기타 적용성이 중요한 듯. 범용성을 위해서.
배경1 포인터 보호기법
잘 보호됐는지 확인 필요.(보호하다가 잠들 수도 있음)
일어나서 뒤늦게 보호하려고 하면 use-after-free 발생. 자기는 보호했다고 착각
포인터 보호한 다음, 그 포인터가 free 되지 않음을 확인(전 노드와 연결되어 있는지)
확인 방법 : Linked list에서 끊어낼 노드의 연결 끊기 -> retire->free 순서대로 실행되므로 보호하고, 연결 안 끊겼는지만 확인하면 충분
단점 : 깊숙이 순회하면 보호 확인이 까다로워
ex : 각각 20,30을 값으로 가진 노드 두 개를 지우려고 한다.
깊은 노드를 보호하려 한다. 연결이 끊겼는지 확인하려면 순회를 해야 하는데(n제곱)
- 임의의 노드가 첫 노드와 연결됐는지 알기 어려워
-끊긴 노드의 다음 노드로 넘어가는 것은 위험.((끊긴) 노드 - 노드)
보호 확인 요령 1. 삭제 전 경고
(노드(위험을 알리는 부분을 1로 설정)-노드)
보호 확인 요령 2. 경고 확인
포인터 보호 기법은 많은 자료구조에 적용 불가
-> 보호확인은 위험을 과대평가함.
연결이 아직 안 끊겼어도 굳이 재시작을 해야 하기에 성능저하가 이뤄짐.
배경 2: 영역 보호기법(Epoch-Based Reclamation)
포인터를 뭉탱이로 보호하는 기법 set_active()~set_quiescent()
어떤 쓰레드도(뭉태기로)보호 안 해줄 때 free
고성능 : 여러 포인터를 뭉태기로 보호
낙관적 순회 가능: 뭉태기로 보호하므로
알고리즘 : Epoch 합의 알고리즘
규칙: Epoch는 동시에 최대 1차이
모든 retire은 보호영역 안에서.
문제 : 한 쓰레드가 깽판 치면 메모리 재활용 막힘.
HP++포인터 보호기법 + 낙관적 순회
핵심 idea
- 연결 끊은 후에 뒷북 경고 (안전성에 대한 문제가 생길 수 있기에 아래처럼 떔빵)
- 끊기 전 빈틈을 땜빵
뒷북 경고 효과 : 안 끊겼으면 재시작 불필요
경계노드를 보호함. 그 후 연결을 끊는다.
성능 평가
- 낙관적 순회하는 더 빠른 자료구조에 적용 가능
- 작은 오버헤드.
- 메모리 재활용이 막히지 않는다
