[CS] 메모리 계층 구조 / B tree

메모리 계층 구조

https://joooing.tistory.com/entry/cs3

- 메모리 계층 구조: 메모리를 필요에 따라 여러가지 종류로 나누어 둠, 상단으로 갈 수록 CPU가 빠르게 처리, 적은 양의 데이터, 비쌈

- 목적: CPU가 메모리에 더 빨리 접근하기 위함

 

CPU 내부: 레지스터 & 캐시

CPU 외부: RAM(주 메모리), 하드디스크, ...

 

프로세서(CPU)-메모리(RAM) 격차

CPU는 짧은 시간 내 여러 연산을 빠르게 처리함

CPU가 아무리 빨라도, (CPU 외부로 가서) 데이터를 가져오고 저장하는 속도가 느리면 전체 속도는 느려짐

이같은 격차를 줄이기 위해, 메모리에 효율적으로 접근하는 방법을 고민 → RAM이 연산하는 횟수를 최대한 줄이자

→ CPU 내부 레지스터 용량을 늘리지 못해도

→ CPU와 통합될 수 있는 빠른 보조 메모리를 만들자 = L1, L2 캐시 (레지스터와 RAM 사이에 위치, 속도와 용량이 중간.)

 

- L1 캐시; cpu 레지스터의 캐시

- L2 캐시; L1 캐시의 캐시

메모리 계층은 왜 피라미드일까?: 시간, 공간 지역성(Locality)

시간 지역성 (temporal locality) : 어떤 메모리주소에 접근한 경우, 곧 똑같은 주소에 다시 접근할 가능성이 높음
공간 지역성 (spatial locality) : 어떤 메모리주소에 접근한 경우, 곧 근처 주소에 접근할 가능성이 높음

 

- '시간'과 '공간'을 기준으로 이후에 접근할 가능성이 높은 메모리 주소들을 찾아내기 - 각각 for문, array

- 조만간 접근할 가능성이 높은 메모리 주소들을 미리 예측하고, 그 주소들을 CPU 내부에 미리 저장

- 접근 가능성이 더 높은 메모리 주소의 데이터를, CPU의 레지스터와 더욱 가까운 곳에 임시로 저장해 둠

- CPU가 찾는 메모리: 레지스터 > L1 > L2 > RAM... 순으로 찾아봄

 

---

Cycle?

 

 

여기서 'cycle'이 무슨 뜻일까?

- 사이클이란, CPU가 하나의 명령어를 처리하는 데 걸리는 시간

- CPU가 원하는 데이터에 액세스하기 위해 "한 바퀴"를 몇 번 돌아야 하는지

CPU Cycle

| Fetch | 메모리에서 명령어를 가져오는 단계 |
| Decode | 명령어를 해석하는 단계 |
| Execute | 명령어를 실행하는 단계 |
| Write Back | 명령어의 결과를 저장하는 단계 |

 

CPU Cycle을 도서관에서 책을 찾는 과정에 비유하자면...

• Fetch 단계: 책을 찾기 위해 도서관에 들어간다.
• Decode 단계: 책의 제목을 확인한다.
• Execute 단계: 책을 꺼내 읽는다.
• Write Back 단계: 책을 제자리에 꽂는다.

CPU Cycle의 길이는 CPU의 종류, 클럭 속도, 메모리 속도 등 다양한 요인에 따라 달라짐

 

CPU time = Clock cycles x Clock cycle time

CPU time = {명령어 개수(instruction count) x  명령어 당 cycle 횟수(CPI)} x Clock Cycle Time

*명령어의 수와 명령어 당 cycle 수로 표현 → 결국 명령어의 수와 명령어당 cycle 수를 줄이는 게 핵심

 

*Clock(클럭)에 대해 알기 위해서는 우선 회로에 대한 기본적인 이해가 있어야 함

쉽게 비유해 보자면, 사람이 살아가기 위해 심장에서의 펌핑이 필요하듯이 CPU 동작에 필요한 전압이 펌핑되는 것이라 보면 됨.

High-Low 상태가 반복되며 주기적으로 반복되는 이 신호를 이용해 CPU는 연산을 수행할 수 있음.

 

*CPU time이 적을 수록, 짧을 수록 더 성능이 좋음. 푸드 파이터도 더 짧은 기록이 나올 수록 좋음. 그럼 시간을 줄이려면 어떻게 해야 할까? 공식에 비춰서 생각해 보면, clock cycle(씹는 횟수)를 줄이고, clock cycle time(한 번 씹을 때 걸리는 시간)을 줄여야 함. 그러나 이게 실제로 가능할까? 결론은 "쉽지 않다." 이유는 두 가지가 trade off 관계에 있기 때문.

 

출처: https://skyjwoo.tistory.com/entry/컴퓨터-구조-CPU-time [jeongstudy:티스토리]

 

---

B-Tree, B+ Tree의 효용

- 내부 기억장치인 레지스터와 캐시는 CPU와 밀접한 위치에 있어 빠른 속도로 데이터를 처리할 수 있고,

- 외부 기억장치는 대용량 데이터를 효율적으로 저장하고 관리할 수 있는 구조로 설계되어 있음

 

"왜 많은 데이터베이스에서 B tree를 근간으로 사용할까?"

만약 아주 큰 사이즈의 데이터가 들어온다면 (ex. 1TB) 보통의 주요 메모리(RAM)은 8~32GB이므로, 해당 데이터를 레지스터나 캐시나 RAM에서 처리할 수 없음.

 

결국 CPU로부터 더 먼(? 사이클 횟수가 큰, 오래 걸리는) Flash Disk(SSD)나 하드드라이브에 데이터를 저장하게 됨. 이때 하드디스크나 SSD와 같은 외부 기억장치는 블럭(chunk)단위로 파일을 입출력함

이때 발생하는 입출력의 비용은 파일의 크기와는 상관 없이 동일함. (입출력에 있어 1KB짜리 블럭에 1byte짜리 알파벳 하나가 들어가 있어도 1KB가 꽉 차있는 블럭을 입출력하는 것과 차이 없음)

 

이때 하나의 블럭(chunk)에 여러 데이터들을 동시에 저장할 수 있다면 블럭을 보다 효율적으로 사용

=> B-트리, B+트리가 유용한 주요 이유

B+ Tree

 

https://ssocoit.tistory.com/217 [코딩하는 경제학도]
Copyright © SsocoIT

refer to: https://joooing.tistory.com/entry/cs3