랄뚜기의 코딩일기

Cache Management의 목표는 cache miss의 수를 최소화 하는 것이다. 그렇다면 어떤 기준으로 cache를 설정하면 될까? 이것이 Tracing the Optimal Policy이지만 현실적으로 미래를 알 수 없으므로 불가능하다. FIFO 방식으로하면 Hit rate이 36.4%로 급격히 낮아진다. 0이 계속 들어올 것이지만 제거해버렸기 때문이다. 당연히 cache가 커지면 hit rate가 오를 것이라고 생각하겠지만 FIFO에서는 오히려 줄어들 수 도 있다. ex) 3->4 차라리 Random하게 cache에 저장하는 것이 오히려 효율적 일 수 있다.(약 45%) 때때로는 Random이 optimal처럼 좋을 수도 있다. 위 두 개의 history( recency, frequency )..

Os는 현재 크게 필요하지 않는 주소 공간을 버릴 필요가 있다. 현대 Os system에서는 아래의 규칙을 hard disk drive에 사용한다. Swap Space DRAM에 주소를 담을 공간이 부족하다면, SSD의 Swap Space에 page-sized unit 만큼 저장해 놓아야 하므로, OS는 swap space를 기억할 수 있어야 한다. 따라서 Present Bit를 사용해서 page가 physical memory에 있는지 disk에 있는지 확인한다. Page fault physical memory에 있지 않은, 즉, Swap space에 있는 page에 accessing하는 것을 의미한다. page가 swapped disk에 있다면 OS는 해당 page를 다시 memory로 올려놓아야 한다..

CLR parser SLR parser는 reduce item [A->ɑ·]에 대해서, FOLLOW(A)에는 속하지만 nonterminal A 다음에 나오지는 않는 기호들이 존재할 때 파싱이 불가능해진다.이를 해결하기 위해 Lookahead와 LR(1)을 이용한 CLR parser를 사용해야 한다. Lookahead : 한 state에서 어떤 논터미널 기호 다음에 나올 수 있는 터미널 기호 LR(1) item : LR(0) item에 lookahead 정보를 첨가한 것 LR(1) item set의 Canonical collection C1 CLOSURE 함수와 GOTO 함수가 필요 GOTO 함수는 LR(0) item set의 canonical collection C0를 구할 때와 동일 CLOSURE 함수..

Bottom-up parsing Bottom-up paring(상향식 구문 분석): Input string을 읽어가면서 reduce에 의해 start symbol을 찾아가는 방법 Input string이 start symbol로 reduce되면 올바른 문장이라고 판단, 파스트리 출력 그렇지 않으면 문법에 맞지 않은 문자으로 판단, 에러 메시지를 출력한다. Bottom-up parsing(상향식 구문 분석)은 rightmost derivation(우단 유도)의 역순이다. reduce, handle: S⇒*ɑAw⇒ɑβw의 유도 과정이 존재할 때 reduce(감축) : sentential form ɑβw에서 β를 A로 대체하는 것 handle(핸들) : β. 즉 한 sentential form에서 reduce..

Knapsack Problem 예를 들어 다음과 같은 option이 있고 이에 대한 Cost 와 Expected reach가 있다고 하자. 주어진 예산이 W가 될 것이고, Cost는 정의에서 w가 될 것이고 Expected reach는 p가 된다. Knapsack에서는 정해진 W를 넘지 않은 채로, Expected reach를 최대화 하는 것이 목적이다. 간단히 말하자면 주어진 예산 안에서 사람들이 최대한 많이 볼 수 있게 하는 것이 목적이다. Dynamic programming approach P(i,w)를 maximized profit, A*를 optimal subset이라고 가정하자. 그렇게 되면 위 처럼 두가지로 optimal subset에 포함되는 경우와 포함되지 않는 경우로 모든 경우의 수를 ..

The Gapped Alignment Problem 두개의 문자열이 주어졌을 때, score을 최대화하는 gapped alignment를 구하여라. match라면 1점, mismatch라면 -1점, gap이라면 -2점을 준다. 두개의 문자열이 주어졌을 때, Gapped Alignment가 생성되는 방법의 수는 3가지로 나오게 된다.(문자열 A,B가 있다고 가정) 1. 두 문자를 match하는 경우( 문자가 다를 수도 있음) 2. A의 문자열에 gap을 넣는 경우 3. B의 문자열에 gap을 넣는 경우 위를 식으로 표현하면 다음과 같다. #include #include using namespace std; // function to find out the minimum penalty void getMini..

The Checkerboard Problem cost table이 위와 같이 주어졌을 때, i=1에서 i=5까지 움직일 때, 최솟값을 찾는 문제이다. q(i,j) : the minimum cost to reach squrare(i,j)라고 할 때, 로 식을 짜게 되면 q[i][j]에는 최소값이 선언되게 된다. table P도 만들어서 어디서 왔는지 알려주면 된다. #include #define N 5 #define INFTY 100000 int c[N+1][N+2] = {-1,-1,-1,-1,-1,-1,-1, -1, 7, 3, 5, 6, 1,-1, -1, 2, 6, 7, 0, 2,-1, -1, 3, 5, 7, 8, 2, -1, -1, 7, 6, 1, 1, 4, -1, -1, 6, 7, 4, 7, 8, -..

Read-Only Memory(ROM) ROM은 Read-Only-Memory로 Input Line이 주어지면 정해진 Function에 맞게 값을 도출한다. 일반화 하자면 n개의 input이 주어졌을 때, 2^n개의 word와 2^n*m개의 bit들이 있고 m개의 ouput line이 생긴다. An 8-Word x 4-Bit ROM F 값들이 위와 같이 주어졌을 때, ROM은 위와 같이 나온다. Switch와 와이어의 조합으로 OR연산이 된다는 것을 기억하자! ROM ROM에서는 왼쪽과 같은 표현을 오른쪽과 같이 간략하게 표현한다.\ W(A,B,C,D) = ∑m(3,7,8,9,11,15), X(A,B,C,D) = ∑m(3,4,5,7,10,14,15), Y(A,B,C,D) = ∑m(1,5,7,11,15)을..

Adders/Subtractors Adder는 기존에 우리가 알고 있던 방식으로 A+B 를하면 되고 Subtract은 2's complment를 사용하여 A+B'+1을 해줘서 계산하면 된다. a4,a3,a2,a1의 값에 b4,b3,b2,b1의 값을 a'ls로 더할지 뺄지를 결정한다. Binary decoders 위와 같이 논리회로를 만들면 무엇을 할 수 있을까? a b 0 1 2 3 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 진리표를 작성하면 위와 같은데 2개의 변수로 4개 중 어떤 것을 사용할 지 고를 수 있다. 더 일반화를 하자면 n개의 변수로 2^n개 중 어떤 것을 사용할 지 고를 수 있다는 말이다. active low decoder는 AND gate가 아..

Pros and Cons of Propositional Logic pros 1. Propositional logic은 declaritive(선언형)이다. 행동에 대한 구문으로 이루어져 있다. (명령형 프로그램은 알고리즘을 명시하고 목표는 명시하지 않는 데 반해 선언형 프로그램은 목표를 명시하고 알고리즘을 명시하지 않는 것이다.) 2. Propositional logic은 partial/disjunctive/negated information을 허락한다. 3. Propositional logic은 compositional 하다. B1,1 ∧ P1,2는 B1,1와 P1,2에서 유래 됐다는 것을 의미한다. 4. Propositional logic은 context-independent하다. context에 의존..