멀티프로세서 확장에 따른 원자적 연산의 한계와 ABA 문제, x86의 DCAS, 락-프리 구조의 함정, 트랜잭션 메모리의 개념·예제·버스 프로토콜·캐시 설계, 지연(latency) 증가 요인(DDR3, NUMA, 코프로세서), 그리고 벡터 연산의 재부상을 다룬다.
이 글은 LWN 구독자들의 후원으로 제공됩니다 LWN.net 구독자들이 이 글 — 그리고 이를 둘러싼 모든 것 — 을 가능하게 했습니다. 콘텐츠가 마음에 드신다면 구독을 구매하시어 다음 기사들이 계속 나오도록 도와주세요.
[편집자 주: 마침내 울리히 드레퍼(Ulrich Drepper)의 “프로그래머라면 누구나 알아야 할 메모리 이야기” 마지막 편입니다. 이 8부작 연재는 지난 9월에 시작되었습니다. 이 결론편에서는 메모리 병목이 계속 악화되는 상황에서, 미래 기술이 성능 향상에 어떻게 기여할 수 있을지 살펴봅니다.
이번 문서를 함께 다듬고 독자들에게 전할 기회를 주신 울리히께 마지막으로 다시 한 번 감사드립니다. 울리히는 가까운 시일 내 전체 문서를 PDF 형태로 공개할 계획입니다. 공개되면 LWN에서 공지를 전하겠습니다.]
앞선 멀티프로세서 처리에 관한 섹션에서, CPU(또는 코어) 수가 늘어날수록 상당한 성능 문제를 예상해야 함을 보았다. 그러나 바로 이러한 확장은 앞으로 필연적으로 일어날 일이다. 프로세서는 점점 더 많은 코어를 갖게 될 것이며, 단일 코어 성능은 예전만큼 빠르게 오르지 않을 것이므로, 그 잠재력을 활용하려면 프로그램은 더욱 병렬화되어야 한다.
공유 데이터 구조에 대한 접근 동기화는 전통적으로 다음 두 가지 방식으로 이뤄진다.
락-프리 데이터 구조의 문제는, 프로세서가 전체 연산을 원자적으로 수행할 수 있는 프리미티브를 제공해야 한다는 점이다. 이 지원은 제한적이다. 대부분의 아키텍처에서 지원은 한 단어(word)를 원자적으로 읽고 쓰는 수준에 한정된다. 이를 구현하는 기본 방법은 두 가지다(6.4.2절 참고).
CAS 연산은 LL/SC 명령으로 쉽게 구현할 수 있다. 그래서 CAS 연산은 대부분의 원자적 연산과 락-프리 데이터 구조의 기본 블록이 된다.
일부 프로세서, 특히 x86과 x86-64 아키텍처는 훨씬 더 다양한 원자적 연산을 제공한다. 그중 상당수는 특정 목적을 위한 CAS 최적화다. 예컨대, 어떤 메모리 위치에 값을 원자적으로 더하는 연산은 CAS와 LL/SC로 구현할 수도 있지만, x86/x86-64의 네이티브 원자적 증가 지원이 더 빠르다. 프로그래머가 이러한 연산과, 이를 노출하는 인트린식에 대해 아는 것은 중요하지만, 새삼스러운 일은 아니다.
이 두 아키텍처의 특별한 확장은 더블워드 CAS(DCAS) 연산을 제공한다는 점이다. 이는 어떤 응용에는 매우 중요하지만 모든 경우에 해당하지는 않는다([dcas] 참조). DCAS의 사용 예로, 배열 기반 스택/LIFO 자료구조를 락-프리로 작성해보자. gcc 인트린식을 사용한 첫 시도는 그림 8.1과 같다.
struct elem { data_t d; struct elem *c; }; struct elem *top; void push(struct elem *n) { n->c = top; top = n; } struct elem *pop(void) { struct elem *res = top; if (res != NULL) top = res->c; return res; }
그림 8.1: 스레드 안전하지 않은 LIFO
이 코드는 명백히 스레드 안전하지 않다. 서로 다른 스레드의 동시 접근은 전역 변수 top을, 다른 스레드의 수정과 무관하게 바꿔버린다. 원소가 유실되거나, 제거된 원소가 갑자기 다시 나타날 수 있다. 상호 배제를 사용할 수 있지만, 여기서는 원자적 연산만으로 시도해보자.
문제를 고치기 위한 첫 시도는 원소를 삽입하거나 제거할 때 CAS 연산을 사용하는 것이다. 결과 코드는 그림 8.2와 같다.
#define CAS __sync_bool_compare_and_swap struct elem { data_t d; struct elem *c; }; struct elem *top; void push(struct elem *n) { do n->c = top; while (!CAS(&top, n->c, n)); } struct elem *pop(void) { struct elem *res; while ((res = top) != NULL) if (CAS(&top, res, res->c)) break; return res; }
그림 8.2: CAS를 사용한 LIFO
겉보기에는 잘 동작하는 해법처럼 보인다. top은 연산을 시작할 때 LIFO 맨 위에 있던 원소와 일치하는 경우에만 수정된다. 하지만 모든 수준의 동시성을 고려해야 한다. 다른 스레드가 최악의 순간에 스케줄될 수 있다. 여기서 한 가지로, 이른바 ABA 문제가 있다. pop의 CAS 직전에 두 번째 스레드가 스케줄되어 다음 연산을 수행한다고 해보자.
이 작업의 최종 효과는, LIFO의 이전 top 원소가 다시 top에 오지만 두 번째 원소가 달라졌다는 것이다. 첫 번째 스레드로 돌아오면, top 원소가 바뀌지 않았기 때문에 CAS 연산은 성공한다. 하지만 res->c 값은 올바르지 않다. 이는 원래 LIFO의 두 번째 원소를 가리키는 포인터이지 newelem이 아니다. 결과적으로 그 새 원소가 유실된다.
문헌 [lockfree]에는 이를 회피하기 위해 일부 프로세서에 있는 기능을 사용하라는 제안이 나온다. 구체적으로는 x86과 x86-64가 제공하는 DCAS 연산이다. 이를 사용한 세 번째 코드 버전이 그림 8.3이다.
#define CAS __sync_bool_compare_and_swap struct elem { data_t d; struct elem *c; }; struct lifo { struct elem *top; size_t gen; } l; void push(struct elem *n) { struct lifo old, new; do { old = l; new.top = n->c = old.top; new.gen = old.gen + 1; } while (!CAS(&l, old, new)); } struct elem *pop(void) { struct lifo old, new; do { old = l; if (old.top == NULL) return NULL; new.top = old.top->c; new.gen = old.gen + 1; } while (!CAS(&l, old, new)); return old.top; }
그림 8.3: 더블워드 CAS를 사용한 LIFO
앞의 두 예와 달리, 이는 (현재로서는) 의사코드다. gcc는 CAS 인트린식에서 구조체 사용을 처리하지 못한다. 그럼에도 접근법을 이해하기에는 충분하다. LIFO의 top 포인터에 세대(generation) 카운터를 추가한다. 이는 push와 pop 등 모든 연산에서 바뀌므로, 앞서 설명한 ABA 문제는 더 이상 문제가 되지 않는다. 첫 번째 스레드가 실제로 top 포인터를 교환하려 다시 실행될 때쯤이면 세대 카운터는 이미 세 번 증가했을 것이다. CAS 연산은 실패하고, 다음 루프에서 LIFO의 올바른 첫 번째와 두 번째 원소가 결정되어 LIFO는 깨지지 않는다. 보일라.
이게 정말 해결책일까? [lockfree]의 저자들은 그렇게 들리게 만들지만, 공을 들여 말하자면, 위 코드가 적용 가능하도록 LIFO용 데이터 구조를 구성할 수는 있다. 그러나 일반적으로, 이 접근법 역시 앞선 것과 마찬가지로 실패할 운명이다. 여전히 동시성 문제가 남아 있으며, 다만 다른 위치에 있을 뿐이다. 한 스레드가 pop을 실행하고 old.top==NULL 테스트 이후에 인터럽트된다고 가정해보자. 이제 두 번째 스레드가 pop을 호출해 LIFO의 이전 첫 번째 원소를 가져간다. 이 스레드는 그 원소로 무엇이든 할 수 있으며, 모든 값을 바꾸거나, 동적으로 할당된 원소라면 메모리를 해제할 수도 있다.
이제 첫 번째 스레드가 다시 시작된다. 변수 old에는 여전히 LIFO의 이전 top이 들어 있다. 더 구체적으로는, 그 top 멤버가 두 번째 스레드가 pop으로 꺼낸 원소를 가리킨다. new.top=old.top->c에서 첫 번째 스레드는 그 원소 안의 포인터를 역참조한다. 하지만 이 포인터가 가리키는 원소는 이미 해제되었을 수도 있다. 해당 주소 공간 영역은 접근 불가일 수 있고, 프로세스는 크래시할 수 있다. 이는 일반적인 자료형 구현에서는 허용될 수 없다. 이를 고치는 방법은 대단히 비싸다. 메모리를 결코 해제하지 않거나, 적어도 메모리를 해제하기 전에 어떤 스레드도 그 메모리를 참조하지 않음을 검증해야 한다. 락-프리 데이터 구조는 더 빠르고 더 높은 동시성을 제공해야 하는데, 이러한 추가 요구는 그 이점을 완전히 상쇄한다. 해당 기능을 지원하는 언어에서는 가비지 컬렉션을 통한 메모리 처리가 문제를 풀 수 있지만, 그 역시 대가가 따른다.
더 복잡한 데이터 구조에서는 상황이 더 나빠지는 경우가 많다. 앞서 인용한 논문은 FIFO 구현(후속 논문에서 개선)도 설명한다. 그러나 이 코드도 똑같은 문제가 있다. 기존 하드웨어(x86, x86-64)의 CAS 연산은 메모리에서 연속된 두 단어만 수정하는 데 한정되므로, 다른 흔한 상황들에는 전혀 도움이 되지 않는다. 예를 들어, 이중 연결 리스트의 어디에서든 원소를 원자적으로 추가하거나 제거하는 것은 불가능하다. {참고로, IA-64 개발자들은 이 기능을 포함하지 않았다. 그들은 두 단어를 비교하는 것은 허용하지만, 하나만 치환한다.}
문제는 일반적으로 하나 이상의 메모리 주소가 관여하고, 그 주소들의 값 가운데 어느 것도 동시에 바뀌지 않을 때에만 전체 연산이 성공할 수 있다는 데 있다. 이는 데이터베이스 처리에서 잘 알려진 개념이며, 바로 이 딜레마를 해결하는 가장 유망한 제안 중 하나가 이 분야에서 나온 이유다.
혁신적인 1993년 논문 [transactmem]에서 Herlihy와 Moss는, 소프트웨어만으로는 효율적으로 문제를 다룰 수 없으므로, 메모리 연산을 위한 트랜잭션을 하드웨어로 구현하자고 제안한다. 당시 디지털 이큅먼트 코퍼레이션(DEC)은 수십 개의 프로세서를 탑재한 하이엔드 하드웨어에서 확장성 문제와 싸우고 있었다. 원리는 데이터베이스 트랜잭션과 같다. 트랜잭션의 결과는 한 번에 모두 보이거나, 트랜잭션이 어보트되어 모든 값이 변하지 않은 채 남는다.
이 지점에서 메모리가 등장하며, 앞 절에서 원자적 연산을 사용하는 알고리즘을 길게 다룬 이유가 드러난다. 트랜잭션 메모리는 많은 상황, 특히 락-프리 데이터 구조에서, 원자적 연산을 대체하고 확장하기 위한 것이다. 트랜잭션 시스템을 프로세서에 통합하는 일은 무척 복잡하게 들리지만, 실제로 대부분의 프로세서는 어느 정도 유사한 기능을 이미 갖고 있다.
몇몇 프로세서가 구현한 LL/SC 연산은 하나의 트랜잭션이다. SC 명령은 메모리 위치가 건드려졌는지 여부에 따라 트랜잭션을 어보트하거나 커밋한다. 트랜잭션 메모리는 이 개념의 확장이다. 이제 간단한 두 개의 명령 대신, 다수의 명령이 트랜잭션에 참여한다. 이것이 어떻게 가능한지 이해하려면, 먼저 LL/SC 명령이 어떻게 구현될 수 있는지 보는 것이 유익하다. {실제 구현이 꼭 이렇다는 뜻은 아니다.}
8.2.1 Load Lock/Store Conditional 구현
LL 명령이 발행되면, 메모리 위치의 값이 레지스터로 로드된다. 이 동작의 일부로 그 값은 L1d에도 로드된다. 이후 SC 명령은 이 값이 변조되지 않았을 때만 성공할 수 있다. 프로세서는 이를 어떻게 감지할 수 있을까? 그림 3.18의 MESI 프로토콜 설명을 떠올려보면 답이 자명하다. 다른 프로세서가 해당 메모리 위치의 값을 변경하면, 첫 번째 프로세서의 L1d에 있는 그 값의 사본은 무효화되어야 한다. 첫 번째 프로세서에서 SC 명령이 실행될 때, 값이 다시 L1d에 로드되어야 함을 알게 될 것이다. 이는 프로세서가 이미 감지해야 하는 일이다.
문맥 전환(같은 프로세서에서의 수정 가능성)과, 다른 프로세서의 쓰기 이후 캐시 라인이 우발적으로 다시 로드되는 문제 등 몇 가지 세부사항을 다듬어야 한다. 이는 정책(컨텍스트 스위치 시 캐시 플러시)과 추가 플래그, 또는 LL/SC 전용의 분리된 캐시 라인 등으로 해결할 수 있다. 일반적으로, LL/SC 구현은 MESI 같은 캐시 일관성 프로토콜 구현에 거의 공짜로 따라온다.
8.2.2 트랜잭션 메모리 연산
트랜잭션 메모리가 일반적으로 유용하려면, 첫 번째 store 명령과 함께 트랜잭션이 끝나서는 안 된다. 대신 일정 수의 load와 store 연산을 허용해야 한다. 이를 위해서는 별도의 커밋과 어보트 명령이 필요하다. 잠시 뒤에 보겠지만, 트랜잭션의 현재 상태가 여전히 유효한지, 이미 어보트되었는지를 확인하는 추가 명령도 필요하다.
구현해야 할 메모리 연산은 세 가지다.
MESI 프로토콜을 보면, 두 번째 유형의 읽기 연산이 어떻게 유용한지 명확해진다. 일반 읽기는 'E'나 'S' 상태의 캐시 라인으로 충족될 수 있다. 두 번째 유형의 읽기는 'E' 상태의 캐시 라인이 필요하다. 왜 두 번째 유형의 메모리 읽기가 필요한지는, 아래 논의에서 어렴풋이 드러난다. 더 완전한 설명은 [transactmem]을 시작으로 트랜잭션 메모리에 관한 문헌을 참고하길 권한다.
추가로, 데이터베이스 트랜잭션 처리에서 익숙한 커밋과 어보트로 주로 구성되는 트랜잭션 처리 기능이 필요하다. 여기에 이론상 선택사항이지만, 트랜잭션 메모리를 사용한 견고한 프로그램을 위해 필수인 연산이 하나 더 있다. 이 명령은 스레드가 트랜잭션이 아직 예정대로 진행 중인지(나중에 커밋 가능), 아니면 이미 실패하여 어쨌든 어보트될 것인지를 검사할 수 있게 해준다.
이 연산들이 실제로 CPU 캐시와 어떻게 상호작용하는지, 버스 연산과는 어떻게 대응되는지를 논의할 것이다. 그 전에 트랜잭션 메모리를 사용하는 실제 코드를 보자. 그러면 이 절의 나머지를 이해하는 데 도움이 될 것이다.
8.2.3 트랜잭션 메모리를 사용한 예제 코드
예제로, 앞서 쓰던 사례를 다시 방문해 트랜잭션 메모리를 사용하는 LIFO 구현을 보여준다.
struct elem { data_t d; struct elem *c; }; struct elem *top; void push(struct elem *n) { while (1) { n->c = LTX(top); ST(&top, n); if (COMMIT()) return; ... delay ... } } struct elem *pop(void) { while (1) { struct elem *res = LTX(top); if (VALIDATE()) { if (res != NULL) ST(&top, res->c); if (COMMIT()) return res; } ... delay ... } }
그림 8.4: 트랜잭션 메모리를 사용한 LIFO
이 코드는 스레드 안전하지 않은 코드와 매우 비슷해 보인다. 이는 트랜잭션 메모리를 사용하는 코드 작성이 쉬워진다는 추가적 보너스다. 코드의 새로운 부분은 LTX, ST, COMMIT, VALIDATE 연산이다. 이 네 연산이 트랜잭션 메모리 접근을 요청하는 방법이다. 실제로는 LT라는 연산이 하나 더 있지만 여기서는 사용하지 않았다. LT는 비독점 읽기 접근을, LTX는 독점 읽기 접근을 요청하며, ST는 트랜잭션 메모리에 대한 저장(store)이다. VALIDATE 연산은 트랜잭션이 아직 커밋 가능한 경로에 있는지 확인하는 연산이다. 트랜잭션이 아직 OK라면 true를 반환한다. 트랜잭션이 이미 어보트로 표시된 경우에는 실제로 어보트되고, 다음 트랜잭션 메모리 명령이 새 트랜잭션을 시작한다. 이런 이유로, 위 코드에서는 트랜잭션이 계속 진행 중인 경우를 위한 새로운 if 블록을 사용한다.
COMMIT 연산은 트랜잭션을 끝낸다. 트랜잭션이 성공적으로 끝나면 true를 반환한다. 즉, 이 부분의 프로그램은 끝났고 스레드는 다음으로 넘어갈 수 있다. false를 반환한다면, 보통 전체 코드 시퀀스를 반복해야 함을 뜻한다. 위의 바깥 while 루프가 바로 이를 수행한다. 꼭 그럴 필요가 없는 경우도 있다. 어떤 경우에는 작업을 포기하는 것이 옳을 때도 있다.
LT, LTX, ST 연산의 흥미로운 점은, 이들이 실패해도 이를 직접적으로 알리지 않을 수 있다는 점이다. 프로그램이 이 정보를 요청하는 방법은 VALIDATE 또는 COMMIT 연산을 통해서다. 로드 연산의 경우, 레지스터에 실제로 로드된 값이 가짜일 수 있다. 그래서 위 예제에서 포인터 역참조 전에 VALIDATE를 사용하는 것이 필요하다. 다음 절에서 이 선택이 구현 관점에서 왜 현명한지 보게 된다. 트랜잭션 메모리가 널리 보급된다면, 프로세서가 다른 방식을 구현할 수도 있다. 하지만 [transactmem]의 결과는 여기서 설명한 바를 시사한다.
push 함수를 요약하면 이렇다. 리스트의 헤드 포인터를 읽어 트랜잭션이 시작된다. 나중에 이 변수를 쓸 것이므로 읽기에서 독점 소유권을 요청한다. 다른 스레드가 이미 트랜잭션을 시작했다면 로드는 실패하고, 태어나자마자 트랜잭션은 어보트로 표시된다. 이 경우, 실제로 로드된 값은 쓰레기일 수 있다. 이 값은 상태와 무관하게 새 리스트 원소의 next 필드에 저장된다. 이 원소는 아직 사용 중이 아니며 정확히 한 스레드만 접근하므로 괜찮다. 이어 리스트 헤드 포인터에 새 원소 포인터를 대입한다. 트랜잭션이 아직 OK라면 이 쓰기는 성공할 수 있다. 이는 정상적인 경우이며, 제공된 push/pop 외의 다른 코드가 이 포인터에 접근하지 않는 한 실패하지 않는다. ST 실행 시점에 트랜잭션이 이미 어보트되어 있으면 아무 일도 일어나지 않는다. 마지막으로 스레드는 트랜잭션을 커밋하려 시도한다. 성공하면 작업은 끝이고, 다른 스레드가 이제 트랜잭션을 시작할 수 있다. 실패하면 처음부터 반복해야 한다. 다만 그 전에 지연을 삽입하는 것이 좋다. 그렇지 않으면 스레드가 바쁜 대기 루프를 돌며(전력 낭비, CPU 과열) 시간을 허비할 수 있다.
pop 함수는 약간 더 복잡하다. 역시 리스트 헤드를 담은 변수를 독점 소유권을 요청하며 읽는 것으로 시작한다. 그리고 즉시 LTX 연산이 성공했는지 확인한다. 실패하면 이 라운드에서는 지연 외에 아무 것도 하지 않는다. top 포인터를 성공적으로 읽었다면 이는 그 상태가 좋다는 뜻이며, 이제 포인터를 역참조할 수 있다. 이는 원자적 연산만 사용할 때 문제가 되었던 바로 그 지점이다. 트랜잭션 메모리에서는 이 경우를 문제 없이 처리할 수 있다. 뒤따르는 ST 연산은 LIFO가 비어 있지 않을 때만 수행되는데, 이는 원래의 스레드-안전하지 않은 코드와 동일하다. 마지막으로 트랜잭션을 커밋한다. 성공하면 함수는 오래된 헤드 포인터를 반환하고, 실패하면 지연 후 재시도한다. 여기서 까다로운 점 하나는 VALIDATE 연산이 이미 실패한 트랜잭션을 어보트한다는 점이다. 다음 트랜잭션 메모리 연산은 새 트랜잭션을 시작하므로, 함수의 나머지 코드를 건너뛰어야 한다.
지연 코드가 어떻게 작동할지는, 트랜잭션 메모리가 하드웨어에 구현되어야 알 수 있다. 이를 잘못 구현하면 시스템 성능이 크게 저하될 수 있다.
8.2.4 트랜잭션 메모리의 버스 프로토콜
이제 트랜잭션 메모리의 기본 원리를 보았으니, 구현의 세부로 들어가 보자. 이는 실제 하드웨어에 기반한 것이 아니다. 원래의 트랜잭션 메모리 설계와 캐시 일관성 프로토콜에 관한 지식을 바탕으로 한다. 일부 세부는 생략하지만, 성능 특성에 관한 통찰을 얻기에는 충분할 것이다.
트랜잭션 메모리는 별도의 메모리로 구현되지 않는다. 스레드의 주소 공간 어디서든 트랜잭션을 원하므로, 별도 메모리는 말이 되지 않는다. 대신, 첫 번째 캐시 레벨에서 구현된다. 이론상 일반 L1d에서 구현할 수도 있지만, [transactmem]이 지적하듯 좋은 생각이 아니다. L1d와 병렬로 구현된 트랜잭션 캐시를 보게 될 가능성이 높다. 모든 접근은 상위 레벨 캐시를 L1d와 동일한 방식으로 사용한다. 트랜잭션 캐시는 L1d보다 훨씬 작을 가능성이 높다. 완전 연관(fully associative)이라면 그 크기는 트랜잭션이 포함할 수 있는 연산 수로 결정된다. 구현은 아키텍처나 프로세서 버전 별로 제한을 둘 가능성이 높다. 16개 항목, 또는 더 적은 항목을 가진 트랜잭션 캐시는 쉽게 상상할 수 있다. 위 예제에서는 단 하나의 메모리 위치만 필요했다. 더 큰 트랜잭션 작업 집합을 가진 알고리즘은 매우 복잡해진다. 동시에 하나 이상의 활성 트랜잭션을 지원하는 프로세서를 보게 될 수도 있다. 그 경우 캐시 항목 수가 곱절로 늘지만, 여전히 완전 연관으로 만들 만큼 충분히 작다.
트랜잭션 캐시와 L1d는 배타적(exclusive)이다. 즉, 한 캐시 라인은 둘 중 하나의 캐시에만 존재하고, 동시에 둘 다에는 존재하지 않는다. 트랜잭션 캐시의 각 슬롯은 언제나 MESI 프로토콜의 네 상태 중 하나에 있다. 여기에 더해, 슬롯은 트랜잭션 상태를 가진다. 상태는 다음과 같다([transactmem]의 명칭 사용).
EMPTY 캐시 슬롯에 데이터가 없다. MESI 상태는 항상 'I'다. NORMAL 캐시 슬롯에 커밋된 데이터가 있다. 이 데이터는 L1d에도 존재할 수 있다. MESI 상태는 'M', 'E', 'S'가 될 수 있다. 'M' 상태가 허용된다는 사실은, 트랜잭션 커밋이 데이터를 메인 메모리에 쓰도록 강제하지 않는다(메모리 영역이 언캐시드나 라이트스루로 선언되지 않은 한). 이는 성능 향상에 크게 도움이 될 수 있다.XABORT 캐시 슬롯에, 어보트 시 폐기할 데이터가 들어 있다. 이는 명백히 XCOMMIT의 반대다. 트랜잭션으로 생성된 모든 데이터는 트랜잭션 캐시에 유지되며, 커밋 전에는 메인 메모리에 아무 것도 쓰이지 않는다. 이는 최대 트랜잭션 크기를 제한하지만, 트랜잭션 캐시 외의 다른 메모리가 단일 메모리 위치에 대해 XCOMMIT/XABORT의 이중성을 알 필요가 없다는 뜻이다. 가능한 MESI 상태는 'M', 'E', 'S'다.XCOMMIT 캐시 슬롯에, 커밋 시 폐기할 데이터가 들어 있다. 이는 프로세서가 구현할 수 있는 최적화다. 트랜잭션 연산으로 메모리 위치가 변경되면, 기존 내용을 그냥 버릴 수 없다. 트랜잭션이 실패하면 기존 내용을 복원해야 하기 때문이다. MESI 상태는 XABORT와 같다. XABORT와의 한 가지 차이는, 트랜잭션 캐시가 가득 찬 경우 'M' 상태의 XCOMMIT 항목은 메모리에 기록한 다음, 모든 상태에서 폐기될 수 있다는 점이다.
LT 연산이 시작되면, 프로세서는 캐시에서 두 개의 슬롯을 할당한다. 희생(victim)은 먼저 해당 주소에 대한 NORMAL 슬롯(즉, 캐시 히트)에서 찾는다. 그런 항목을 찾으면 두 번째 슬롯을 확보하고, 값을 복사하여 한 항목을 XABORT로 표시하고 다른 하나를 XCOMMIT으로 표시한다.
해당 주소가 아직 캐시되지 않았다면 EMPTY 슬롯을 찾는다. 없다면 NORMAL 슬롯을 찾는다. 이때 MESI 상태가 'M'이면 이전 내용을 메모리에 플러시해야 한다. NORMAL 슬롯도 없다면 XCOMMIT 항목을 희생시킬 수 있다. 이는 구현 세부에 달렸을 것이다. 트랜잭션의 최대 크기는 트랜잭션 캐시의 크기로 결정되며, 트랜잭션 내 각 연산에 필요한 슬롯 수가 고정되어 있으므로, XCOMMIT 항목을 퇴거시키기 전에 트랜잭션 수를 제한할 수 있다.
해당 주소가 트랜잭션 캐시에 없다면, 버스에 T_READ 요청을 발행한다. 이는 일반 READ 버스 요청과 동일하지만, 트랜잭션 캐시용임을 나타낸다. 일반 READ와 마찬가지로, 다른 모든 프로세서의 캐시가 먼저 응답할 기회를 갖는다. 아무도 응답하지 않으면 메인 메모리에서 값을 읽는다. MESI 프로토콜은 새 캐시 라인의 상태가 'E'인지 'S'인지를 결정한다. T_READ와 READ의 차이는, 해당 캐시 라인이 다른 프로세서 또는 코어에서 활성 트랜잭션에 의해 사용 중인 경우에 드러난다. 이 경우 T_READ 연산은 그냥 실패하며, 어떤 데이터도 전송되지 않는다. T_READ 버스 요청을 발생시킨 트랜잭션은 실패로 표시되고, 연산에서 사용된 값(보통은 단순한 레지스터 로드)은 정의되지 않는다. 예제로 돌아가 보면, 트랜잭션 메모리 연산이 올바르게 사용되는 한 이러한 동작이 문제가 되지 않음을 알 수 있다. 트랜잭션에서 로드된 값을 사용하기 전에 VALIDATE로 검증해야 한다. 이는 거의 모든 경우에 추가 부담이 아니다. 앞서 CAS로 FIFO를 만들려던 시도에서 보았듯, 우리가 추가했던 검사는 락-프리 코드가 동작하게 만들 마지막 빠진 퍼즐 조각이었다.
LTX 연산은 LT와 거의 동일하다. 한 가지 차이는 버스 연산이 T_READ 대신 T_RFO라는 점이다. T_RFO는 일반 RFO 버스 요청과 마찬가지로 캐시 라인의 독점 소유권을 요청한다. 결과 캐시 라인의 상태는 'E'다. T_READ와 마찬가지로 T_RFO도 실패할 수 있으며, 이 경우 사용된 값도 정의되지 않는다. 캐시 라인이 이미 로컬 트랜잭션 캐시에 'M' 또는 'E' 상태로 있다면 아무 것도 할 필요가 없다. 로컬 트랜잭션 캐시의 상태가 'S'라면, 다른 모든 사본을 무효화하기 위해 버스 요청을 내보내야 한다.
ST 연산은 LTX와 비슷하다. 먼저 값을 로컬 트랜잭션 캐시에 독점적으로 확보한다. 그 다음 ST는 값을 캐시의 두 번째 슬롯에 복사하고, 그 항목을 XCOMMIT으로 표시한다. 마지막으로 다른 슬롯을 XABORT로 표시하고, 새 값을 그곳에 쓴다. 트랜잭션이 이미 어보트 상태이거나, 묵시적 LTX가 실패하여 새로 어보트되었다면 아무 것도 쓰지 않는다.
VALIDATE나 COMMIT 연산은 버스 연산을 자동·묵시적으로 생성하지 않는다. 이것이 트랜잭션 메모리가 원자적 연산에 비해 갖는 큰 장점이다. 원자적 연산에서는, 동시성을 확보하기 위해 바뀐 값을 메인 메모리에 되써야 한다. 이 문서를 여기까지 읽은 독자라면 이것이 얼마나 비싼지 알 것이다. 트랜잭션 메모리에서는 메인 메모리 접근이 강제되지 않는다. 캐시에 EMPTY 슬롯이 없으면 현재 내용을 퇴거시켜야 하며, 'M' 상태의 슬롯은 메모리에 써야 한다. 이는 일반 캐시와 다르지 않으며, 라이트백은 특별한 원자성 보장 없이 수행될 수 있다. 캐시 크기가 충분하면 내용은 오래 생존할 수 있다. 같은 메모리 위치에서 트랜잭션이 반복해서 수행되면, 속도 향상은 천문학적일 수 있다. 전자에서는 매 라운드마다 한두 번의 메인 메모리 접근이 필요하지만, 트랜잭션 메모리에서는 모든 접근이 L1d만큼 빠른 트랜잭션 캐시에서 히트하기 때문이다.
어보트된 트랜잭션에 대해 VALIDATE와 COMMIT이 하는 일은, XABORT로 표시된 캐시 슬롯을 비우고 XCOMMIT 슬롯을 NORMAL로 표시하는 것이다. 마찬가지로, COMMIT이 트랜잭션을 성공적으로 끝낼 때는 XCOMMIT 슬롯을 비우고 XABORT 슬롯을 NORMAL로 표시한다. 이는 트랜잭션 캐시에서 매우 빠른 연산이다. 트랜잭션을 수행하려는 다른 프로세서에 대한 명시적 통지는 없다. 그런 프로세서는 그냥 계속 시도해야 한다. 이를 효율적으로 하는 문제는 별개다. 위 예제 코드에서는 적절한 위치에 ...delay...만 두었다. 우리가 유용한 방식의 지연을 지원하는 실제 프로세서 기능을 보게 될지도 모른다.
요약하면, 트랜잭션 메모리 연산은 새 트랜잭션이 시작될 때와, 아직 성공 중인 트랜잭션에 트랜잭션 캐시에 없던 새 캐시 라인이 추가될 때만 버스 연산을 유발한다. 어보트된 트랜잭션의 연산은 버스 연산을 유발하지 않는다. 동일 메모리를 사용하려는 여러 스레드 때문에 캐시 라인이 핑퐁되는 일은 없다.
8.2.5 기타 고려사항
6.4.2절에서, x86 및 x86-64에서 사용 가능한 lock 접두어가 어떤 상황에서는 원자적 연산의 코딩을 피하는 데 쓰일 수 있음을 이미 논의했다. 그러나 이 요령은 동일 메모리를 두고 경쟁하지 않는 여러 스레드가 사용되는 경우에는 미흡하다. 이 경우에도 원자적 연산이 불필요하게 사용된다. 트랜잭션 메모리에서는 이 문제가 사라진다. 비싼 RFO 버스 요청은 메모리가 서로 다른 CPU에서 동시에 또는 연달아 사용될 때만 발생한다. 즉, 필요할 때에만 발생한다. 이보다 더 잘 하기는 거의 불가능하다.
세심한 독자는 지연에 대해 궁금했을 것이다. 최악의 경우는 무엇인가? 활성 트랜잭션을 가진 스레드가 디스케줄되면, 또는 시그널을 받아 종료되거나 siglongjmp로 바깥 스코프로 점프하면 어떻게 되는가? 답은: 트랜잭션은 어보트된다. 스레드가 시스템 콜을 하거나 시그널을 받을 때(즉, 링 레벨 변경이 일어날 때) 언제든 트랜잭션을 어보트할 수 있다. 시스템 콜 수행이나 시그널 처리 시 트랜잭션을 어보트하는 것이 OS의 임무 일부일 수도 있다. 실제 구현이 나와봐야 무엇이 어떻게 이뤄지는지 알 수 있다.
여기서 논의해야 할 트랜잭션 메모리의 마지막 측면은, 오늘날에도 생각해볼 만한 것이다. 트랜잭션 캐시는 다른 캐시처럼 캐시 라인 단위로 동작한다. 트랜잭션 캐시는 배타적 캐시이므로, 같은 캐시 라인을 트랜잭션과 비트랜잭션 연산이 함께 쓰는 것은 문제가 된다. 따라서 다음이 중요하다.
첫 번째 포인트는 새로운 것이 아니다. 오늘날의 원자적 연산에도 동일한 노력이 성과를 낸다. 두 번째는 더 까다롭다. 오늘날 객체는 높은 비용 때문에 캐시 라인 정렬이 거의 이뤄지지 않기 때문이다. 원자적 연산으로 수정되는 단어와 함께 사용되는 데이터가 같은 캐시 라인에 있다면, 필요한 캐시 라인 수가 줄어든다. 이는 상호 배제에는 해당되지 않는다(뮤텍스 객체는 항상 자체 캐시 라인을 가져야 한다). 하지만 원자적 연산이 다른 데이터와 함께 쓰이는 경우를 만들 수는 있다. 트랜잭션 메모리에서는, 캐시 라인을 두 용도로 쓰는 것이 치명적일 가능성이 높다. 데이터에 대한 모든 일반 접근 {문제의 캐시 라인에 한정된다. 임의의 다른 캐시 라인 접근은 트랜잭션에 영향을 주지 않는다.}은 해당 캐시 라인을 트랜잭션 캐시에서 제거하여, 그 과정에서 트랜잭션을 어보트하게 된다. 앞으로는 데이터 객체의 캐시 정렬이 성능 문제일 뿐 아니라, 정합성 문제이기도 할 것이다.
트랜잭션 메모리 구현이 더 정밀한 회계를 사용해, 트랜잭션의 일부인 캐시 라인에 대한 일반 접근으로 인한 문제를 겪지 않게 만들 수도 있다. 그러나 그러려면 훨씬 더 많은 노력이 필요하다. 그 경우 MESI 프로토콜 정보만으로는 충분하지 않기 때문이다.
미래 메모리 기술의 전개에서 거의 확실한 점 하나는 지연(latency)이 계속 슬금슬금 올라갈 것이라는 사실이다. 2.2.4절에서 이미, 다가오는 DDR3 메모리 기술이 현재의 DDR2보다 더 높은 지연을 가질 것임을 논의했다. FB-DRAM도, 만약 도입된다면, 특히 FB-DRAM 모듈을 데이지 체인으로 연결할 경우 잠재적으로 더 높은 지연을 가진다. 요청과 결과를 통과시켜 전달하는 데는 공짜가 없다.
지연의 두 번째 원천은 NUMA의 증가하는 사용이다. AMD의 Opteron은 프로세서가 둘 이상이면 NUMA 머신이다. 각 CPU에는 자체 메모리 컨트롤러가 붙은 로컬 메모리가 있지만, SMP 마더보드에서는 나머지 메모리를 HyperTransport 버스를 통해 접근해야 한다. 인텔의 CSI 기술도 거의 동일한 기술을 사용할 것이다. 프로세서당 대역폭의 한계와, 예컨대 다수의 10Gb/s 이더넷 포트를 지속적으로 바쁘게 유지해야 한다는 요구 때문에, 소켓당 코어 수가 늘더라도 멀티 소켓 마더보드는 사라지지 않을 것이다.
세 번째 지연 원천은 코프로세서다. 1990년대 초 범용 프로세서에서 수치 연산 코프로세서가 더 이상 필요 없게 되면서 코프로세서를 치웠다고 생각했지만, 그들은 다시 돌아오고 있다. 인텔의 Geneseo와 AMD의 Torrenza는 서드파티 하드웨어 개발자가 자사 제품을 마더보드에 통합할 수 있도록 하는 플랫폼 확장이다. 즉, 코프로세서를 PCIe 카드에 꽂을 필요 없이 CPU에 훨씬 가까이 둘 수 있다. 이는 더 높은 대역폭을 준다.
IBM은 다른 길을 택했다(물론 인텔과 AMD의 확장과 같은 방식도 여전히 가능하다). 바로 Cell CPU다. Cell CPU는 PowerPC 코어 외에, 주로 부동소수점 계산을 위한 특화 프로세서인 8개의 SPU(Synergistic Processing Unit)로 구성된다.
코프로세서와 SPU의 공통점은, 실제 프로세서보다 더 느린 메모리 로직을 가질 가능성이 크다는 것이다. 이는 필요한 단순화에서 부분적으로 기인한다. 모든 캐시 처리, 프리패칭 등은 특히 캐시 일관성까지 필요할 때는 복잡하다. 고성능 프로그램은 점점 코프로세서에 의존하게 될 것이다. 성능 차이가 극적일 수 있기 때문이다. Cell CPU의 이론적 피크 성능은 210 GFLOPS로, 하이엔드 CPU의 50~60 GFLOPS에 비해 높다. 오늘날 사용되는 GPU(그래픽 카드의 프로세서)는 더 높은 수치(500 GFLOPS 이상)를 달성하며, 큰 노력 없이도 Geneseo/Torrenza 시스템에 통합될 수 있을 것이다.
이 모든 전개 결과, 프로그래머는 프리패칭이 갈수록 더 중요해질 것이라는 결론에 이르게 된다. 코프로세서에는 절대적으로 중요해질 것이다. 특히 코어 수가 늘어나는 CPU에서는, 요청을 한꺼번에 몰아넣는 대신, 항상 FSB를 바쁘게 유지하는 것이 필요하다. 이를 위해서는 프리패칭 명령을 효율적으로 사용해, 미래 트래픽에 관한 정보를 CPU에 최대한 많이 제공해야 한다.
오늘날 주류 프로세서의 멀티미디어 확장은 제한된 방식으로만 벡터 연산을 구현한다. 벡터 명령의 특징은 많은 수의 연산이 함께 수행된다는 것이다. 스칼라 연산과 비교하면, 멀티미디어 명령도 그렇게 말할 수 있지만, Cray-1 같은 벡터 컴퓨터나 IBM 3090 같은 기계의 벡터 유닛이 하던 것과는 거리가 멀다.
한 번의 명령으로 수행되는 연산 수가 적다는 점을 보완하려면, 주변 루프를 더 자주 실행해야 한다. 9.1절의 예가 이를 명확히 보여준다. 각 캐시 라인은 SM번의 반복을 요구한다.
더 넓은 벡터 레지스터와 연산을 사용하면 루프 반복 횟수를 줄일 수 있다. 이는 단지 명령 디코딩 등의 개선 이상을 의미한다. 여기서 더 관심 있는 것은 메모리 효과다. 단일 명령으로 더 많은 데이터를 로드 또는 저장하면, 프로세서는 애플리케이션의 메모리 사용에 대해 더 나은 그림을 갖게 되며, 개별 명령의 행동으로부터 정보를 억지로 맞춰볼 필요가 줄어든다. 더 나아가, 캐시에 영향을 주지 않는 로드/스토어 명령을 제공하는 것이 더 유용해진다. x86 CPU에서 SSE 레지스터(16바이트 폭)를 로드할 때 언캐시드 로드를 사용하는 것은 좋지 않다. 나중에 같은 캐시 라인에 접근할 때(캐시 미스인 경우) 다시 메모리에서 데이터를 로드해야 하기 때문이다. 반면 벡터 레지스터가 하나 이상의 캐시 라인을 담을 만큼 넓다면, 언캐시드 로드/스토어가 부정적 영향을 주지 않는다. 캐시에 맞지 않는 데이터 집합에 대해 연산을 수행하는 것이 더 실용적이 된다.
큰 벡터 레지스터가 있다고 해서 명령의 지연 시간이 반드시 늘어나는 것은 아니다. 벡터 명령은 모든 데이터가 읽히거나 저장될 때까지 기다릴 필요가 없다. 벡터 유닛은 코드 흐름을 인지할 수 있다면 이미 읽힌 데이터부터 시작할 수 있다. 즉, 예컨대 벡터 레지스터를 로드한 다음 모든 벡터 요소를 스칼라로 곱하는 경우, CPU는 벡터의 첫 부분이 로드되는 즉시 곱셈을 시작할 수 있다. 이는 벡터 유닛의 정교함 문제일 뿐이다. 이로부터, 이론적으로 벡터 레지스터는 매우 넓어질 수 있고, 프로그램도 이를 염두에 두고 오늘 설계될 수 있음을 알 수 있다. 실제로는, 프로세서가 다중 프로세스·다중 스레드 OS에서 사용된다는 사실이 벡터 레지스터 크기에 제한을 둔다. 결과적으로 레지스터 값을 저장·로드하는 컨텍스트 스위치 시간은 중요하다.
더 넓은 벡터 레지스터에서는, 연산의 입력과 출력 데이터가 메모리에 순차적으로 배치될 수 없다는 문제가 생길 수 있다. 이는 행렬이 희소(sparse)이거나, 행이 아닌 열 기준으로 접근하거나, 기타 다양한 요인 때문일 수 있다. 벡터 유닛은 이 경우를 위해 비순차 패턴으로 메모리를 접근하는 방법을 제공한다. 단일 벡터 로드/스토어를 매개변수화하여 주소 공간의 여러 다른 위치에서 데이터를 로드하도록 지시할 수 있다. 오늘날의 멀티미디어 명령만으로는 이런 일이 전혀 불가능하다. 값을 하나하나 명시적으로 로드한 다음, painstakingly하게 하나의 벡터 레지스터로 결합해야 한다.
옛 벡터 유닛은 가장 유용한 접근 패턴을 가능케 하는 다양한 모드를 제공했다.
주류 프로세서의 미래 버전에서 진정한 벡터 연산의 부활을 보게 될지는 불확실하다. 어쩌면 이 작업은 코프로세서로 이관될 것이다. 어느 쪽이든, 벡터 연산에 접근할 수 있다면, 그러한 연산을 수행하는 코드를 올바르게 구성하는 일이 더욱 중요해진다. 코드는 자급자족적이고 교체 가능해야 하며, 인터페이스는 벡터 연산을 효율적으로 적용할 만큼 일반적이어야 한다. 예컨대, 인터페이스는 행, 열, 또는 요소 묶음이 아니라 전체 행렬의 덧셈을 허용해야 한다. 블록이 클수록 벡터 연산을 사용할 가능성이 커진다.
[vectorops]의 저자들은 벡터 연산의 부활을 열정적으로 주장한다. 그들은 많은 장점을 지적하고 여러 신화를 깨려 한다. 그러나 그 그림은 지나치게 단순하다. 앞서 언급했듯, 큰 레지스터 집합은 컨텍스트 스위치 시간이 길다는 뜻이며, 범용 OS에서는 이를 피해야 한다. 컨텍스트 스위치가 빈번한 작업에서 IA-64 프로세서가 겪은 문제를 보라. 벡터 연산의 긴 실행 시간도 인터럽트가 관련되면 문제가 된다. 인터럽트가 발생하면, 프로세서는 현재 작업을 멈추고 인터럽트 처리를 시작해야 하며, 이후 중단된 코드를 다시 실행해야 한다. 일반적으로 명령의 한가운데에서 인터럽트하는 것은 큰 문제다. 불가능하지는 않지만 복잡하다. 장시간 실행되는 명령에서는, 그렇지 않으면 인터럽트 반응 시간이 너무 길어지므로, 실행 도중 인터럽트를 하거나, 명령을 재시작 가능(restartable)한 방식으로 구현해야 한다. 후자는 받아들일 수 없다.
또한 옛 벡터 유닛은 메모리 접근 정렬에 관대했으며, 이는 개발된 알고리즘에 영향을 주었다. 오늘날의 일부 프로세서(특히 RISC)는 엄격한 정렬을 요구하므로, 완전한 벡터 연산으로의 확장은 사소하지 않다. 특히 스트라이딩과 간접 참조가 지원될 때 벡터 연산에는 큰 잠재적 상승 여지가 있으므로, 미래에 이러한 기능을 보게 되길 기대할 수 있다.
부록과 참고문헌 페이지에는, 이 문서에서 사용한 여러 벤치마크 프로그램의 소스 코드, oprofile에 대한 추가 정보, 메모리 유형에 대한 약간의 논의, libNUMA 소개, 그리고 참고문헌이 수록되어 있다.
| 이 글의 색인 항목 |
|---|
| GuestArticles |
