🖥 Computer Science

🧐 Reduction 어떠한 문제 X와 Y를 가정하도록 하겠습니다. (엄밀한 정의는 아닙니다) 이 때 Y를 해결하는 어떠한 알고리즘이 존재하고, 해당 알고리즘을 이용하여 문제 X를 해결하는 알고리즘을 디자인 할 수 있는 경우, 문제 X에서 Y로의 Reduction이 가능하다고 합니다. (X is reducible to Y) 이를 보통 X $\leq$ Y 로 표현합니다. 즉 X $\leq$ Y 인 경우, X를 해결하는 것은 Y를 해결하는 것보다 절대로 어려울 수 없습니다. 다른 말로는 Y를 해결하는 것은 적어도 X를 해결하는 것 만큼 어렵다고 할 수 있습니다. Reduction은 특정 문제를 해결하는 알고리즘을 디자인하거나, 어떤 문제를 해결하는 알고리즘이 존재하지 않는(혹은 매우 해결하기 힘든) 것을 증..

🧐 Non-Comparison Sort 이전 글에서 Comparison Based Sort는 Lower Bound가 Ω(n log n)이라는 것을 살펴보았습니다. 이번에 살펴볼 알고리즘은 시간 복잡도가 O(n)인 정렬 알고리즘입니다. 이는 Comparison Based Sort가 아니기 때문에 이전에 구한 Lower Bound는 잘못되지 않았음을 미리 밝히고 넘어가겠습니다. 🧐 Counting Sort (계수 정렬) 우선 배열 A[0, ..., n]를 1부터 k 사이의 정수 배열이라 하겠습니다. 계수 정렬은 다음과 같이 이루어집니다. 크기가 k인 Counter 배열 C[0, 1, 2, ..., k]를 정의합니다. 해당 값들을 모두 0으로 초기화합니다. A[0]부터 A[n]까지 읽으면서 $0 \leq i ..

🧐 Lower Bound Upper Bound는 빅오 표기법을 사용해 보였다면 이미 아실 것이라 생각합니다. Lower Bound 역시 이와 비슷합니다. 어떤 문제가 주어졌을 때, `해당 문제를 해결하는 알고리즘의 Lower Bound가 T이다.`의 의미는 다음과 같습니다. (어떤 가정 하에서) 해당 문제를 T 시간보다 더 빨리 해결할 수 없다. 이때 가정은 계산 모델, 추가 사용 공간 등의 여러가지 가정이 있을 수 있습니다. 또한 빅-오메가(Ω) 표기법을 사용하여 표기합니다. 예시를 하나 살펴보겠습니다. 길이 n인 배열에서 최대값을 찾는 알고리즘의 lower bound는 Ω(1)이라고 표현할 수도 있고, Ω(n)이라 표현할 수도 있습니다. 이 경우 Ω(n)으로 나타내는 것이 더 우수한(유용한) Lowe..

🧐 분리 가용 리스트(Segregated free list) 이전 글들에서 살펴본 것과 같이 가용 블록 리스트를 단 한개만 사용하는 할당기는 한 개의 블록을 할당하는 데 블록의 수(혹은 가용 블록의 수)에 비례하는 시간이 필요합니다. 할당 시간을 줄이는 대표적인 방법으로 알려진 분리 저장장치(Segregated Storage)는 다수의 가용 리스트를 유지하며, 각 리스트는 거의 동일한 크기의 블록들을 저장합니다. 기본적인 아이디어는 모든 가능한 블록의 크기를 크기 클래스(size class)라고 하는 동일 클래스의 집합으로 분리하는 것입니다. 크기 클래스를 정의하는 방법에는 여러 가지가 있습니다. 대부분 적은 크기의 블록들은 매 크기마다 클래스를 갖도록 합니다.(2, 3, 4, ...) 크기가 큰 경우에..

🧐 명시적 리스트(Explicit List) 묵시적 리스트 방식을 사용하는 것은 간단하지만, 블록 할당 시간이 전체 힙 블록의 수에 비례하기 때문에 느리다는 단점이 있었습니다. 이 단점을 해결하기 위해서 명시적 리스트를 사용할 수 있습니다. 명시적 리스트 방식은 가용 블록들을 이전 가용 블럭과 다음 가용 블럭을 가리키는 포인터를 가진 일종의 이중 연결 링크드 리스트 자료구조로 구성하는 방법입니다. 가용 블럭은 프로그램에서 사용되지 않기 때문에, 해당 자료구조를 구현하는 포인터들은 가용 블록의 본체 내에 저장될 수 있습니다. 위 그림에서처럼 각 가용 블록 내에 pred(predeccesor)와 succ(successor) 포인터를 포함하는 이중 연결 가용 리스트로 구성될 수 있습니다. 할당된 블록의 구조는..

🧐 캐시 실패의 처리 캐시 실패는 제어 유닛(control unit)이 처리합니다. 제어 유닛은 실패를 탐지해야 하며, 메모리(또는 하위 수준의 캐시)로부터 데이터를 가져와서 실패를 처리해야 합니다. 캐시 적중을 처리할 수 있게 프로세서의 제어 유닛을 수정하는 것은 쉬운 일이지만, 실패의 경우에는 몇 가지 작업이 더 필요합니다. 캐시 실패 처리는 프로세서의 제어 유닛과 별도의 제어기의 공동 작업으로 처리됩니다. 이 제어기는 메모리 접근을 시작하고, 캐시를 채우는 일을 합니다. 예외나 인터럽트는 모든 레지스터의 상태를 저장해야 하지만, 캐시 실패의 처리는 파이프라인 지연(stall)만을 발생시킵니다. 캐시 실패 발생 시에는 임시 레지스터와 프로그래머에게 보이는 레지스터의 내용을 그대로 유지한 채 메모리에서..

🧐 캐시(Cache) 캐시라는 명칭은 최초에는 메인 메모리와 프로세서 사이의 메모리 계층을 나타내기 위해서 사용된 용어입니다. 오늘날에도 이러한 의미로 가장 많이 사용되기는 하지만, 데이터 접근의 지역성(Locality)을 이용해서 관리되는 모든 기억장치를 부르는 데에도 사용됩니다. 처음에는 프로세서는 하나의 워드 단위의 데이터를 필요로 하며, 블록(block) 또한 하나의 워드로 이루어진 단순한 캐시를 살펴보는 것으로 시작하겠습니다. 다음은 캐시에 없는 데이터를 요청하기 전과 후의 캐시 상태를 나타내었습니다. 요청하기 전의 캐시에는 최근에 접근한 $X_1, X_2, ..., X_{n-1}$이 존재하고, 프로세서는 캐시에 없는 워드 $X_n$을 요청하였습니다. 이 요청은 실패(Miss)를 발생시키고, 워..

컴퓨터가 처음 나왔을 때부터 프로그래머들의 꿈은 한없이 큰 빠른 메모리였습니다. 이번에는 위 꿈을 이루기 위한 무한한 크기의 빠른 메모리가 있는 듯한 환상을 만들어내는 방법에 대해 알아보도록 하겠습니다. 🧐 지역성 (Locality) 프로그램은 어떤 특정한 시간에는 주소 공간 내의 비교적 작은 부분만을 사용합니다. 프로그램은 최근에 접근했던 데이터들을 다시 사용하려는 경향을 보이며, 또한 최근에 접근했던 데이터에 인접한 데이터들을 접근하려는 경향을 가집니다. 이를 지역성의 원칙이라 부르며, 다음과 같이 두 종류로 나누어 볼 수 있습니다. 👉 시간적 지역성(Temporal Locality) 한 번 참조된 항목은 가까운 시간 내에 다시 참조될 가능성이 높습니다. 👉 공간적 지역성(Spatial Localit..