2012.11.22 성균관대학교 전자전기컴퓨터공학과 오영환, 박효진 Transactional Memory Architectural Support for Lock-Free Data Structures 2012.11.22 성균관대학교 전자전기컴퓨터공학과 오영환, 박효진

목차 기존의 방법론(Lock, Lock-free 등) Transactional Memory(TM) 소개 Implementation of TM Simulation 결과 Conclusion & Limitation

Methodology of Keeping Data Consistency 1.1 페이지 제목 3 / 14 Methodology of Keeping Data Consistency Locking 공유 자원의 Consistency를 유지하기 위해 서로 다른 프로세스의 동시 접근을 배타적으로 막는 방식(Lock, Mutex, Semaphore 등) Lock-Free Algorithm SW 알고리즘을 이용하여 기존의 Locking에서 발생하는 문제점을 해결하기 위해 만들어졌으나, 오히려 알고리즘 자체의 overhead가 늘어나서 실용적으로 쓰이지 못함. Transactional Memory(TM) Lock-Free 알고리즘을 HW적으로 Support하여 overhead 를 낮추고 User 가 프로그램의 구현을 쉽게 하기 위해 고안됨.

Locking 의 문제점 Priority inversion 1.1 페이지 제목 4 / 14 Locking 의 문제점 Priority inversion 낮은 우선순위의 프로세스가 Lock을 잡고 있는 경우에 높은 우선순위의 프로세스에 의해 preempted되는 상황

Locking 의 문제점 Deadlock Convoying 서로 엇갈려서 자원을 요청, 선점하는 교착 상태 1.1 페이지 제목 5 / 14 Locking 의 문제점 자원1 자원2 Process - 2 Process - 1 요청 선점 Deadlock 서로 엇갈려서 자원을 요청, 선점하는 교착 상태 Convoying 하나의 공유자원에 대해 다수의 프로세스가 쌓여있는 현상

Lock-free Algorithm Lock-Free Algorithm이란? 1.1 페이지 제목 6 / 14 Lock-free Algorithm Lock-Free Algorithm이란? CAS 등의 Atomic한 Instruction을 사용하여 Mutex나 Semaphore 등의 Locking을 사용하지 않고, 공유자원의 consistency를 유지. 대표적인 예, CAS : Compare and Swap 주어진 메모리의 값을 읽어서 기존의 값과 Compare하고 일치하면, 메모리에 새로운 값을 Swap한다. 일치하지 않을 때는 성공할 때까지 다시 시도한다. Do{ if( *sharedValue == knownValue ) *sharedValue = newValue; } while(!CAS (&sharedValue, knownValue, newValue));

Transactional Memory Transactional Memory 처리 과정 1.1 페이지 제목 7 / 14 Transactional Memory Transactional Memory 처리 과정 공유 데이터를 접근하는 프로세스가 하나라는 가정하에 일단 Access함. TM 수행의 마지막 단계에서 다른 프로세서에 의해 공유 데이터가 바뀌었는지 확인한다. 프로세스 간의 충돌이 없었으면 바로 메모리에 적용(Commit)하고, 충돌이 있었다면 과정을 취소한(Abort) 뒤, 앞서의 과정을 다시 수행(Rollback)한다. 공유 데이터의 충돌 빈도가 실제론 매우 적을 것이라는 아이디어 (Simulation을 해보니 Rollback하는 경우는 드물다고 함. 오히려 Lock Variable을 관리하는데 쓸데없는 overhead가 발생한다.) Transactional Memory 와 Locking 방식의 차이점 Locking : 잠금 -> 처리 -> 해제 TM : 처리 -> 비교 -> 적용 or 롤백

HW Supported Instruction Set 1.1 페이지 제목 8 / 14 HW Supported Instruction Set 제공하는 명령어 LT : memory to Cache Read LTX : memory to Cache Read with flag setting (수정 예정) VALIDATE : 진행중인 Transaction이 Abort 되었는지 체크 ST : LT/LTX로 읽어들인 데이터를 수정 후 Cache 에 Write COMMIT : Transaction을 모두 수행한 뒤에 consistency 검사 후 TRUE 면 memory 에 write 하고, FALSE 면 ABORT ABORT : 진행중인 Transaction을 무효화 ( Cache 에 flag 만 invalid 해버리면 됨 )

Implementation of TM Cache Protocol TM 캐쉬 Actions 1.1 페이지 제목 9 / 14 Implementation of TM Cache Protocol Non-transactional OP 사용을 고려하여 두가지 타입의 Cache Line을 사용함. TM 캐쉬 Actions LT / LTX XCOMMIT XABORT DATA Commit EMPTY NORMAL DATA Abort NORMAR EMPTY DATA ST(DIRTY) NORMAR XABORT DATA

Implementation of TM : Processor Action 1.1 페이지 제목 10 / 14 Implementation of TM : Processor Action Processor Flag bit TACTIVE(TR in progress) TSTATUS(TR active or aborted) bit CPU에서 연산 시에 Cache Protocol과 상호작용, Consistency 유지 특징적인 점? Intel Haswell : HTM(Restricted), TR 영역을 대괄호로 묶어 표시 TR operation을 위한 몇 가지 HW supported instruction 제 (처음 TR op가 등장하는 구간부터 implicit하게 TR 영역으로) High level 언어에 ST, LTX 등의 Assembly 명령어를 inline으로 껴넣듯이 구현

Example : doubly linked list 1.1 페이지 제목 11 / 14 Example : doubly linked list Part of Doubly-Linked List Benchmark

Implementation of TM : Snoopy Cache 1.1 페이지 제목 12 / 14 Implementation of TM : Snoopy Cache 기반 기술 : Snoopy Cache (Shared memory, Bus system) Goodman’s SCP를 기본으로 Normal Cache 구현, TM Cache를 추가 TM Cache : One-way associative cache Normal Cache : Fully associative cache(상대적으로 작은 크기 때문)

Implementation of TM : Architecture 1.1 페이지 제목 13 / 14 Implementation of TM : Architecture 생각해볼 수 있는 구체적인 Architecture: P P P Cache : With Snooping! Memory(L2 $) Conflicting : Memory Transactional Memory 영역

Simulation Simulator Simulated Architecture 1.1 페이지 제목 14 / 14 Simulation Simulator Proteus simulator(Eric Brewer, Chris Dellarocas, MIT) Simulated Architecture Goodman’s Snoopy protocol with Bus-Based system Chaiken Directory-Based protocol Using 32 multi-processor Compared with various SW/HW schemes i.e. spin lock based(TTS), lock variable queing, LL/SC operation

1.1 페이지 제목 15 / 14 Simulation

Conclusion & Limitation 1.1 페이지 제목 16 / 14 Conclusion & Limitation 쉬우면서도 뛰어난 성능의 멀티 프로그래밍 다른 lock based 알고리즘에 비해 효율적인 시뮬레이션 결과 (Negative -> Positive. 관점을 변화하여 Memory Access를 대폭 줄임) 현재는 특정 영역을 Transaction이라 표시만 해두는 심플함 Transaction의 한계 크기 Cache Size에 영향을 받고, 큰 Transaction에 대해서는 오히려 성능 감소

Reference [1] 멀티코어 강의자료, 한환수 교수님 강의자료 [2]네이버 블로그, 백발의 개발자 1.1 페이지 제목 17 / 14 Reference [1] 멀티코어 강의자료, 한환수 교수님 강의자료 [2]네이버 블로그, 백발의 개발자 http://blog.naver.com/jjoommnn?Redirect=Log&logNo=130038310489 [3]티스토리 블로그, 김민장. 프로그래머가 몰랐던 멀티코어 이야기 저자 http://minjang.egloos.com/2907073 http://minjang.egloos.com/2313699

감사합니다