Mnemonic

[ Parallel Merge Sort ]OverviewMerge Sort는 대표적인 Divide & Conquer을 이용한 정렬 알고리즘이다.알고리즘의 특성상 Parallel하게 실행하더라도 recursive call이 독립적으로 분할된 영역에 Write를 하므로 Race가 발생하지않을 뿐더러, Serial 알고리즘의 성능과 비교했을 때 점근적으로 동일하므로 Work-Efficient Parallel Algorithm에 속한다.이 글에서는 효율적인 병렬 정렬 알고리즘인 Parallel Merge Sort에 대한 두 가지 방식 및 Work/Span 분석을 진행한다. ReferenceMIT EECS 6.172 - Performance Engineering of Software Systems7. Races ..

[ MIT OpenCourseWare : 14. Caching and Cache-Efficient Algorithms ] https://youtu.be/xDKnMXtZKq8?si=Cf31bew4YkX8qTc8 Fully Associative Cache- 전체 주소에 대한 매핑을 저장- 캐시 전체 검색 필요Direct-Mapped Cache- may trigger Conflict missSet-Associative Cache- Hybrid SolutionTaxonomy of Cache Misses 1. Ideal-Cache Model1. Cache Main memory | 즉, 단순한 Hierarchy 가정2. Cache size : M bytes3. Cache line size : B bytes4. ..

[ MIT OpenCourseWare : Multicore Programming ] https://youtu.be/dx98pqJvZVk?si=2cdZid4RgwTfai_u Part 1. 왜 멀티코어 프로세서가 등장했는가1. Multicore processor의 기본 구조멀티코어 프로세서에서는 여러 개의 core가 같은 chip 위에 배치되어 있고, 이 core들은 shared memory에 접근할 수 있습니다.보통 각 core는 private cache를 가지고 있고, 여러 core가 공유하는 last-level cache도 있습니다. 예를 들어 L3 cache가 여기에 해당합니다. 또한 모든 core는 동일한 memory controller를 통해 메인 메모리에 접근하고, I/O에도 접근할 수 있습니..

[MIT OpenCourseWare] Bently Rules for Optimizing Work https://youtu.be/H-1-X9bkop8?si=XwVJWkN_mL2Pk0LG WorkDefinition.The work of a program (on a give input) is the sum total of all the operations executed by the program.프로그램의 work라는 것은 어떠한 입력이 주어졌을 때, 실행되는 모든 연산의 합. Optimizing Work알고리즘 설계는 문제 해결에 필요한 작업량을 드라마틱하게 줄일 수 있는데, 정렬 알고리즘의 O(n^2)와 O(n lg n)의 차이가 대표적인 예시이다. 하지만, 아래와 같은 컴퓨터 하드웨어의 복잡한 특성때..

[NDC25] MMO 서버에서 태스크 그래프를 활용한 확장성있는 멀티스레드 아키텍처 직접적으로 밝히지는 않았지만, DX의 MMO 서버 구조에 대한 멀티스레드 관리 방식을 간접적으로 볼 수 있음. https://youtu.be/6nYtK7kNiH8?si=OOdbc-UT5n5daXLn Contents1) Introduction- MMO 서버 도전 과제 2) Task Based Parallelism- Task를 이용한 작업 분배 문제 해결 3) Task Graph- Task간의 작업 흐름 관리 4) District ProcessorSeamless World를 위한 정적인 Task Graph 5) Exclusive Task- 공유 자원에 대한 배타적 접근을 보장하는 동적인 Task Graph 6) Limita..

[MIT OpenCourseWare] The Cilk Runtime System https://youtu.be/Z7r4aAZ9Vqo?si=MdOHE_hw456cZ4nE The Cilk Runtime SystemP개의 프로세서에서, Tp - Cilk 스케줄러는 실행중인 프로그램을 프로세서 코어에 런타임에 동적으로 매핑시켜줌.- Cilk의 work-stealing 스케줄링 알고리즘은 효율적임이 입증됨. 핵심1) scheduling2) load balancing - Required Functionality- Performance Considerations- Implementating a Worker Deque- Spawning Computation- Stealing Computation- Synchron..

[MIT OpenCourseWare] Parallel Storage Allocation https://youtu.be/d5e_YJGXXFU?si=OjFtavN5i8PmsMXU Heap Storage in C지난 강의 Storage Allocation에서 다뤘던 부분 복습. mallocmalloc(s) 처럼 size s를 넘기면, 적어도 s bytes 이상을 포함하는 memory block을 할당하고 그 시작 주소를 pointer로 반환하게 된다.중요한 점은, 요청 크기인 s bytes보다 실제 제공 크기가 더 클 수도 있다는 것이다. 즉,요청 크기 = s bytes실제 제공 크기 >= s bytes더 큰 block을 받을 수도 있다. return type은 void*로, 실제 사용하려는 타입에 맞게 캐..

[MIT OpenCourseWare] [1] 1. Introduction and Matrix Multiplication 일부you see once again the mention of "performance" in jobs is going up. and anecdotally, I can tell you, I hand one student who came to me after the spring, after he'd taken 6.172, and he said, "you know, I went and I applied for five jobs. and every job asked me, at every job interview, they asked me a question I couldn't have an..