TLR (Transactional Lock Removal)

Critical section에 대해 Lock을 걸게 되면
- 지역적으로 static하며 dynamic concurrency하지 못하다.
- OS의 스케줄링에 의해 lock owner가 동작못하면, 모든 wait task에 악영향이다.

따라서 TLR을 쓰자. (TLR = SLE + timestamp )
SLE(Speculative  Lock Elision)처럼 메모리를 읽고 쓰는 일련의 과정을 transaction으로 보고
cache coherency protocol를 사용하고
timestamp를 두어 dynamic lock free가 가능하게 하자.

SLE는 processor가 지원해야함.



http://www.kosen21.org/pls/kosendev/NEWS_ALL_BOARD.contents_view?c_category=&c_subject=ELCO&n_board_seq=20&n_boardseq=43&n_data_seq=157590&n_list_cnt=20&n_program_seq=1&vc_search_keyword=&vc_search_option=TITLE

차세대 프로세서에 추가될 것으로 보이는 기능

반도체 전문가들은 최소한 향후 10년 동안에도 프로세서에 사용되는 트랜지스터 수는 계속 증가할 것으로 보고 있다. 이러한 트랜지스터 수의 증가는 다양한 기능을 추가할 수 있다는 것을 의미하지만 반면에 프로세서를 매우 복잡하게 만든다. 여기에서는 차세대 프로세서에서 이들 트랜지스터를 이용하여 구현될 것으로 보이는 기술들에 대해서 알아본다.

온 칩 디바이스가 매우 작게 되고 많아짐에 따라 이 디바이스를 사용하는 것도 어렵게 된다. 디바이스의 신뢰성(reliability)은 떨어지며, 오동작할 가능성도 높아진다. 또한, 소비 전력도 과도하게 될 가능성도 높다. 더욱이, 프로그래머나 프로그래밍 언어, 컴파일러 등이 디바이스의 특성을 효율적으로 사용하지 못할 가능성도 높다. 현재 이러한 문제점들을 해결하기 위해 많은 연구가 진행되고 있는데, 그 중 몇 가지를 소개하면 다음과 같다.

프로세서 연구자들은 프로세서의 기능을 높이기 위해 병렬 스레드(thread) 개념에 주목하고 있다. 이 기술은 프로세서 내에서 데이터 이동을 감지한다던가 마스터 슬레이브 동작 수행, 스트리밍 등의 동작을 수행하는데, 이들은 기본적으로 SMT(Symmetrical Multiple Thread) 기술처럼 프로세서의 병렬성을 높여준다.

프로세서의 집적도가 높아짐에 따라 신뢰성(reliability)이 중요한 이슈로 부각되고 있기 때문에, 설계자들은 성능 향상보다는 신뢰성 제고에 더욱 많은 노력을 기울여야 할 상황을 맞이하게 될 것이다. 최근 이를 위한 연구로서, 결과 검증 기술과 신뢰성 강화를 위한 부가 스레드 기술, 최소 전력하에서의 프로세서 동작 기술에 대한 연구가 수행되고 있다. 또한, 연구자들은 소프트웨어 디버깅을 지원하는 스레드 기술과 보안 강화 기술도 연구 중이다. 예를 들어, 버퍼 오버플로우를 자동으로 감지하거나 이를 방지하는 하드웨어 기술, 스택 오버플로우 감지 기술, 세밀한 단계에서의 메모리 보호 기술이 이에 속한다. 소프트웨어의 버그나 폴트(fault) 발생을 감지하고 악의적인 공격자를 감지하는 기술 연구도 모두 차세대 프로세서 하드웨어 연구에 있어서 중요한 기능으로 보인다.

지금까지 병렬 프로그래밍의 가장 큰 문제점으로는 병렬 처리를 위해 소프트웨어를 파티션하는 것이 쉽지 않다는 점이었다. 물론, 병렬 처리를 위해서는 컴파일러나 프로그래머 수준에서 효율적인 병렬 처리 기술을 개발하는 것이 더욱 중요하겠지만, 현재 많은 응용 부문에서 병렬 처리 기술을 상위 수준에서 적용하는 것이 어렵기 때문에 프로세서의 하드웨어 복잡도가 허용하는 범위에서 하드웨어 수준에서 병렬 프로그래밍을 지원하는 기술 연구가 활발해 질 것으로 보인다. 예를 들어, 성능 저하없이 프로그래머들이 록(Lock) 기능을 사용할 수 있도록 하는 speculative lock 기술이나 transactional lock removal 기술에 대한 연구가 활발하다.


분야명      전자/전기/통신
정보출처      (IEEE Computer )  
발행일      2004/03/00
발행국가      UNITED STATES
원문언어      English
등록일      2004/03/15
원본파일        

---------------------------

강좌
-------------------------------------------------------------
[PPT] Architectural Support for Efficient Execution of Highly Concurrent ...
http://www.cs.rochester.edu/~garg/Summer2004.ppt

[PPT] A Transactional Memory Primer
http://www.cis.upenn.edu/acg/talks/wddd05_xact_overview_talk.ppt

[PPT] Comp 422: Parallel Programming
http://www.eecg.toronto.edu/~amza/ece1747h/slides/Transactions_short.ppt

TLR (Transactional Lock Removal)
http://www.cs.binghamton.edu/~shadi/cmp/papers/TLR_PPT.ppt

[PDF] Virtualizing Transactional Memory
http://www.cs.brown.edu/people/mph/RajwarLH05/32_rajwar_r.pdf

Transactional Lock Removal (TLR).
http://www.cs.auckland.ac.nz/compsci703s1c/lectures/TM-4up.pdf

[PDF] SPECULATION-BASED TECHNIQUES FOR LOCK- FREE EXECUTION OF LOCK ...
http://bbcr.uwaterloo.ca/~brecht/servers/readings-new/rajwar02speculationbased.pdf


논문들
--------------------------------------------------------------
Transactional Lock-Free Execution of Lock-Based Programs
http://cap.suwon.ac.kr/snusem03-1/p5-rajwar.pdf　
http://portal.acm.org/citation.cfm?id=605399&dl=GUIDE&coll=ACM&CFID=15151515&CFTOKEN=6184618

[PDF] Atomic Transactional Execution in Hardware: A New High-Performance ...
http://www.cs.wisc.edu/~rajwar/papers/hpts03.pdf

http://citeseer.ist.psu.edu/context/2118630/541186




SLE
--------------------------------------------------------------
만일 아래의 코드는
lock(a);
i = a;
unlock(a):
write access가 없거나, 다른 영역을 접근 중일때는 락이 필요없다.

- 동시적으로 변하는 것이 문제
- 메모리 접근이 원자적이라면 락은 생략될 수 있다.
    - 읽어진 데이터가 다른 스레드에 의해 변경되지 않는다면
    - 쓰여진 데이터가 다른 스레드에 의해 읽히지지 않는다면
- 위 조건이 철수되기 전까지 어떤 명령도 위반이 된다.

락 코드를 없애고 speculative write를 validated될때 까지 write buffer에 쓰고
speculative write를 merge한다. Reorder Buffer를 둔다. 레지스터에 체크 포인트를 둔다.
cache coherency로 원자성 위반을 탐지하고 write buffer와 Reorder Buffer를 활용하여 충돌을 해결

Speculative Lock Elision: Enabling Highly Concurrent Multithreaded ...
http://www.cs.wisc.edu/~rajwar/papers/micro01.pdf

Detection of Synchronization Errors through Speculative Lock Elision
http://www.crhc.uiuc.edu/~steve/papers/lumetta-uiuc.dsesle.pdf

Enabling Highly Concurrent Multithreaded Execution
http://www.ee.duke.edu/~sorin/prior-courses/ece259-spring2004/presentations/sle-meixner.ppt


Speculative lock reordering: optimistic out-of-order execution of ...
http://www.ce.chalmers.se/~pers/pub/c53.pdf


Efficient Memory Barrier Implementation
http://www.csl.cornell.edu/~burtscher/VPW2/keynote.ppt