Distributed Shared Memory

http://dsg.kaist.ac.kr/courses/Fall98/cs530/lecture/chap6-1%2C2/JeongtaekKim/chap_6.1-2.html


Chapter 6. Distributed Shared Memory
6.1 introduction


80년대 중반에 접어 들면서 더이상 chip을 발전시켜서는 컴퓨터의 성능 향상을 도모하기 힘든게 아니냐는 생각이 퍼짐.
실제로는 계속 chip만으로 성능이 좋아지고 있음 (ex. Intel 80x86 시리즈.)
* Tale of Two Camps


Hypercube

Multi-Computer (Message Passing 을 이용한다.)
Seity et al
Caltech에서 연구하였다.

장점

각 노드에서 보면 다른 노드로의 연결이 Log N 에 비례함을 알 수 있다.
그리고 latency도 Log N 에 비례한다.
따라서 Scale하다고 이야기 할 수 있다.

Ultracomputer

Multiprocessor (Shared Memory 를 이용한다.)
Gottliele et al
NYU에서 연구하였다.

이쪽 분야의 학생이 이야기 하기를
"They are experimenting with (?). We are still designing chips for (?)."
무슨 이야기 인고 하니, Hypercube 쪽에서는 컴퓨터를 이미 만들어서 성능이 어쩌고 저쩌고 하는데, 아직 Ultracomputer 쪽에서는 들어갈 chip을 디자인이나 하고 있다는 푸념.
Multicomputer

만들기는 쉽고
프로그램 하기는 어렵다.
왜 프로그램을 하기 힘드냐면, 변수가 실제로 어디에 있는지에 따라서 성능이 많이 차이나기 때문에 프로그래머가 이를 다 고려해 주어야 함.(-.-)
"Where do I put variable X?"

Multiprocessor

Multicomputer에 비해 프로그램하기는 쉽고
만들기는 어렵다.
프로그래머가 신경 쓸 것은 줄었지만, Multicomputer에 비해서 CPU 사이의 연관이 많으므로 고려해야 할 것이 매우 늘어남.

그렇다면, 두가지를 모두 쉽게 하는 방법은 없는가?
"Any approach to build systems that are both easy to build and easy to program.?"

Distributed Shared Memory

Kal Li (1986) 라는 사람이 기발한 생각을 해냄.
만들기는 Multicomputer를 만들고
프로그램 하기는 Shared-Memory Multiprocessor 처럼 한다.
다 좋은데, 어떻게 그렇게 하는가?
지금의 상황은 이전에 Memory가 부족해서 Virtual memory를 생각해 낸 때와 상황이 비슷하다.
그럼 이전의 Virtual memory 의 개념을 적용시키면 어떨까?

Virtual Memory

더 커다란 address space가 필요하다.
address space는 disk 처럼 크고
빠르기는 메모리 처럼 빠르다.
이를 해결한 것이 바로 virtual memory.

위의 Kai Li의 제안은 획기적인 것이었다. 이때 Kai Li의 논문의 방법은 문제점이 하나 있었다. 실제로 구현해 봤더니 느리다는 것이다. 성능 향샹만 이루어 지면 된다고 하였다. (남들이 풀 문제를 남겨둔 좋은 논문.) 그럼 이전의 Shared Memory Multiprocessor는 어떻게 이루어 졌나?
Bus-based Multiprocessors

간단하고 실용적으로 Multiprocessor를 구현하는 방법이다.


Bus 는 매우 바쁘고 Processor는 논다.
그렇다면 각 Processor에 cache를 장착하면 어떨까?


Snooping cache (consistency를 유지하는 방법)
cache 들은 모두 Bus를 쳐다보면서 자신의 내용을 적절히 바꾼다. 모든 일은 공유 Bus를 중심으로 이루어 진다.
과연 이것이 돈이 되는가?
Sequent라는 회사는 위와 같은 것을 만들어 먹고 산다.

A Write-Through cache Consistency Protocol
책의 그림 6-3 참조.



문제점이 없는가?
모든 write가 Bus를 통해서 memory로 전달된다. 따라서 Bus traffic이 많다.

An ownership Protocol
각 cache block은 다음의 세가지 상태 중에 한가지 상태를 갖는다.

Invalid (block의 내용이 잘못된 내용이다.)
Clean
block의 내용이 제대로 된 내용이고 똑같은 복사본이 다른 곳에 있을 수 있다.
메모리의 내용은 최근의 내용이다.
Owner (dirty보다 owner의 개념이다.)
block의 내용이 제대로 된 내용이고 유일하게 이 block이 제대로 된 정보를 가지고 있다.
메모리의 내용은 잘못된 정보이다.

모든 문제점이 해결되었나?
아직도 Scalability는 없다. 즉 CPU의 갯수가 증가하면 Bus 가 금방 감당해 내지 못한다.


책의 그림 6-4 참조

Switched Multiprocessors

하나의 공유 Bus로는 64개의 프로세서 이상을 감당해 내지 못한다. (bandwidth가 모자란다.)
여러개의 선을 연결할 필요가 있다. (더이상 공유 Bus가 아니다.)
한개의 선이 여러개의 선으로 바뀌면 어떤 문제가 있나?
이전에는 공유 Bus였으므로 Snooping을 사용할 수 있었으나, 공유 Bus 와 같은 것이 없으므로 더이상 Snooping의 의미가 없다.
Directory를 사용하여 Consistency에 관련된 정보를 저장한다.

책의 그림 6-7 참조

A Directory-Based coherence Protocol

각각의 memory block은 자신의 home이 정해진다. (home cluster) Directory에는 다음과 같은 정보가 들어간다.
어느 cluster가 자신이 가지고 있는 block의 복사본을 가지고 있는지.
각 block의 상태가 어떤지. ( block에 가능한 상태는 다음과 같다. )
Uncached
home에만 제대로 된 정보가 있다.
Clean
memory에는 제대로 된 정보가 있고, 다른 cluster에서 복사본을 가져 갔다.
Dirty
memory에 있는 것은 잘못된 정보이고, 정확한 정보는 하나의 cluster가 가지고 있다.

어느 순간에도, 각각의 block은 유일한 owner가 있다.

책의 그림 6-8 참조

NUMA Multiprocessor (Non Uniform Memory Access)
이것은 Multiprocessor를 구현하기 쉽게 하는 것이다. Multiprocessor를 구현할때 문제가 되는 것은 cache를 유지하는 것인데, cache를 없애고 프로그래머가 memory의 사용 시간이 다르다는 것을 알고 프로그램하도록 하는 것이다.


다른 processor가 가지고 있는 memory를 사용할 수 있다.
다른 processor가 가지고 있는 memory를 사용할때는 자신이 가지고 있는 것을 사용할 때보다 느리다.
cache를 사용하지 않으므로 다른 processor가 가지고 있는 memory를 사용할때는 latency가 있다는 것을 고려해야 한다.
문제점은 없나?


프로그램 code와 같은 읽기 전용 부분만 cache를 사용한다.
Multi-computer와 비슷하게 프로그램하기 어려워진다. 왜냐하면 memory사용 시간이 틀리다는 것을 알고 프로그램해야 하기 때문이다.

책의 그림 6-9 참조

Comparison of Shared Memory Systems

책의 그림 6-10 참조