BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다.
✔ 프로세서 구조
컴퓨터 구조의 발전
- 인텔 8086 (1981): 5 MHz (IBM PC에 처음 사용됨)
- 인텔 80486 (1989): 25 MHz (숫자를 상표로 사용할 수 없다는 법원 판결 때문에 i486이 됨)
- 펜티엄 (1993): 66 MHz
- 펜티엄 4 (2000): 1.5 GHz (약 30단계의 깊은 파이프라인)
- 펜티엄 D (2005): 3.2 GHz (이후 클럭 속도의 증가가 멈춤)
- 쿼드코어 제온 (2008): 3 GHz (하나의 칩의 코어 수가 성능의 주요 요소)
병렬 알고리즘의 문제점
프로세서는 계산할 데이터를 필요로 하나 SRAM은 4개보다 많은 메모리 요청을 병렬적으로 처리 불가합니다. 그래서 프로세서와 메모리가 타일 구조로 된 형태로 제작됩니다. 프로그램이 실행되는 대부분 동안 프로세서는 로컬 또는 "캐시" 메모리에 접근합니다. 만약 원격 메모리에 접근하려 한다면 다른 프로세서의 다른 스레드와 어떤 데이터를 공유하고 있을 가능성이 있습니다. 이럴 경우 특정한 캐시에 요청을 보낸 후 데이터를 다시 돌려받습니다. 이것을 왕복 접근이라고 합니다.
✔ 연구 주제: 실행 이동
어떤 프로세서에서 실행되는 프로그램이 다른 프로세서의 캐시 메모리에 접근을 필요로 하면, 프로세서는 자신의 "문맥"을 원격 프로세서로 이동시킨 뒤 거기에서 실행됩니다.
편도 데이터 접근
프로그램의 접근 패턴을 알거나 예측할 수 있다고 가정한다면
예)
- p1 p2 p2 p1 p3 p2
- 이동비용(s, d) = 거리(s, d) + L ← 적재 대기시간 L은 문맥 크기의 함수
- 접근비용(s, d) = 2 ∗ 거리(s, d) 만약 s == d이면, 비용은 0 으로 정의
문제 : 총 메모리 비용을 최소화하는 이동 시점을 결정하라.
동적계획법 해법
프로그램의 최초 위치 p1, 프로세서의 수 Q
하위 문제
DP(k, pi) : 프로그램이 p1에서 시작해서 pi에서 끝나는 경우 m1에서 mk까지의 메모리 접근의 prefix에 대한 최적해의 비용으로 정의합니다.
복잡도
✔ Erik의 주요 연구분야
- 계산 기하학
- 기하학적 접기 알고리즘
- 자가 조립 - 자료구조
- 그래프 알고리즘
- 레크리에이션 알고리즘
- 알고리즘적 조형물
👀 이 이후로는 연구분야들과 6.006(이 강의) 이후의 것들에 대한 설명으로 정리하지 않았습니다. 궁금하신 분들은 강의 자료를 확인하시면 됩니다.
'프로그램 개발 > 미분류' 카테고리의 다른 글
| [코딩 인터뷰]자료구조 - 연결리스트 (0) | 2022.12.01 |
|---|---|
| [코딩 인터뷰]자료구조 - 배열과 문자열 (0) | 2022.11.29 |
| [MIT] 파이썬을 이용한 알고리즘 : 계산 복잡도 (0) | 2022.11.21 |
| [MIT] 파이썬을 이용한 알고리즘 : 동적 프로그래밍 4 (0) | 2022.11.17 |
| [MIT] 파이썬을 이용한 알고리즘 : 동적 프로그래밍 3 (0) | 2022.11.16 |