지난 글에서는 연결리스트가 사용하는 메모리 공간을 어떻게 관리하는지 그 구현을 C언어로 직접 해보았다. 이번 글에서는 트리와 이진트리의 개념을 정리해보고자 한다. 트리 트리는 아래와 같이 정의된다. a tree is a finite set T of nodes such that 1) T has one special node called root 2) the remaining nodes are partitioned into m disjoint sets T1, T2, ... Tm, and each of these sets is turn to a tree. wee call them subtrees of T 트리는 '루트' 라고 불리는 특별한 하나의 노드를 가지고 있고, 나머지 노드들은 m 개의 서브트리를 이루는..
메모리 개요 메모리는 프로그램의 명령어와, 그 명령어가 사용할 데이터가 들어있는 공간이다. (폰 노이만 구조에서는 프로그램의 명령어도 데이터이다.) 저장 단위는 byte 단위이며, 레지스터와 달리 4byte로 고정되지 않고 1, 2, 4, 8 byte 등으로 유동적인 사이즈로 저장할 수 있다. 하지만 레지스터가 한번에 4byte 씩 파악하기 때문에, 명령어의 사이즈는 4byte 로 고정되어있다. 메모리 접근 메모리에 접근하여 데이터를 읽고 쓰는 명령어는 기본적으로 아래와 같은 형태를 띈다. Load, 메모리의 데이터를 불러와(loading) 레지스터에서 읽는 것 ld [메모리주소], 레지스터주소 메모리 -> 레지스터 순서로 읽으면 되니 이해가 간단하다. 메모리주소는 R + A 형태로 표현되고, [ ] 는..
이제 지금까지 배운 내용을 응용해보자 어떤 세 점이 주어질 때, 그 세 점을 삼각형으로 하는 평면을 결정할 수 있다. 임의 지점에서부터 주어진 방향으로 광선을 쏘았을 때, 그 광선이 삼각형에 맞았는지 어떻게 알 수 있을까? 이는 아래와 같은 방법으로 계산할 수 있다. 1. 평면식을 구한다. (세 점으로부터 둘레 벡터 구하고, 둘레벡터의 외적과 세 점중 하나로 평면식 결정) 2. 광선의 직선식을 구한다. 3. 광선의 직선식과 평면식의 교점을 구한다. 4. 교점이 삼각형 내부에 있는지 체크한다. (각 삼각형 선분마다, 그 선분을 포함하고 삼각형평면에 수직인 평면식을 짜고, 그 평면식 위의 임의 점 A 에서 평면식의 법선벡터를 내적했을 때 양수임이 모든 선분에서 확인되면 내부에 있다고 볼 수 있다.) 내적의 ..
지난 글에서는 연결리스트를 이용해 스택과 큐를 구현하였다. 이번 글에서는 연결리스트를 이용하는 과정에서 new(), free() 기능을 사용했는데, 이 기능을 직접 구현해본다. 사실 직접 구현이라고 해서 나도 처음엔 메모리를 직접 다루는 거창한 걸 기대했는데, 그런건 아니다. 그냥 배열을 이용해서 전체 memory pool 을 세팅해두고, 그 세팅된 pool 내 메모리를 주고 받고 하는 방식이다. 메모리 풀은 연결리스트 노드의 데이터 형태로 배열에 세팅해두고, 이를 스택처럼 활용하여 메모리를 주고 받는다. 메모리 풀은 이런 구조로 존재한다. 만약 new 함수로 메모리 공간을 요청하면 top이 가리키는 노드를 제공해준다. 제공을 마친 모습이다. 제공된 메모리는 연결리스트에서 자유롭게 Item 부분에도 값을..
지난 글에서는 분기 최적화에 대해 정리하였다. 분기 최적화를 하는 방법에는 from before, from after, annulled branch 3가지가 있었다. from before 은 분기 명령어 이전에 실행되는 명령어를 가져오는 것으로, 보통 mov 명령어를 이용한 레지스터 값 세팅을 가져올 수 있다. from after 은 분기 명령어 이후에 실행되는 명령어를 가져오는 것으로, 보통 분기 이후 실행되는 명령어 중, 분기 여부에 상관없이 반드시 실행되는 명령어를 당겨올 수 있었다. annulled branch 는 분기를 할 때는 delay slot 명령어를 실행하고, 분기를 하지 않을 때는 delay slot 명령어를 실행하지 않는 분기 명령어로서, 반드시 분기 후 첫 명령어를 delay slo..
지난 글에서는 직선과 점, 직선과 직선, 점과 평면 사이 최단 거리를 구하는 방법을 정리하였다. 직선과 점에서는 직선의 법선벡터를 방향벡터로 하고, 직선밖의 점을 지나는 새로운 직선식을 세운다음, 기존 직선과 교점을 구해 거리를 구하거나, 점의 위치를 원점으로 평행이동시키고, 이동된 직선의 방정식의 법선벡터를 정규화하여 최단 거리를 구할 수도 있었다. 직선과 직선의 경우, 두 직선의 외적을 이용해 한 직선을 지나는 평면식을 세우고, 그 평면식과 다른 직선 위 임의점 사이 최단 거리를 구하였다. 점과 평면사이 최단거리의 경우, 점의 위치를 원점으로 옮기고, 이동된 평면의 방정식의 법선벡터를 정규화하여 최단거리를 구하였다. 이번 글에서는 특정 평면으로 입사된 벡터의 반사벡터를 구하는 방법을 정리하고자 한다...
지난 글에서 Linked List 의 개념과 그 구현에 대해 정리하였다. 이번에는 Array 로 구현했던 Stack 과 Queue를 Linked List 로 구현하는 과정을 살펴보고자 한다. Stack With Linked List 스택을 연결리스트로 구현해보자. 연결리스트에서 데이터를 중간에 삽입할 때는 이전 노드의 주소를 알아야 하기 때문에 아주 복잡했다. 데이터를 맨 처음에 삽입하는 것이 아주 간단하기 때문에, 스택의 데이터 삽입과 삭제가 빈번히 일어나는 top 을 연결리스트의 첫 head로 설정하자. 그림으로 나타내면 이렇게 나타난다. 스택에 데이터를 추가하면 추가된 데이터를 top 이 가리키고, 추가된 데이터가 기존 데이터를 가리키는 방식으로 구현하면 된다. 스택에서 데이터를 뺄 때는 top 의..
지난 글에서는 Branch Delay Slot 이 발생하는 이유를 파이프라이닝 과정을 따라가보며 살펴보았다. 요약해보면, Branching 여부는 E 단계에서 결정되기 때문에, E 단계에서 분기를 하더라도, E 단계 시점의 F 단계에 있던 명령어가 파이프라인에 남아 계속 실행되는 문제 때문에 이를 비워둠으로써 Delay Slot 이 발생하였다. 이번 글에서는 이렇게 Delay Slot 을 비워두지 않고, 다른 명령어로 채워 활용하는 방법. Delay Slot Optimization 에 대해 정리해보고자 한다. 최적화 개요 그렇다면 어떻게 분기 명령어를 쓴 직후, nop 를 넣지 않고 최적화를 할 수 있을까? nop 대신 분기에 (전체 코드 실행에) 영향을 주지 않는 다른 명령어를 넣으면 된다. 즉, de..
지난 글에서는 분기 명령어의 종류와 사용 방법, 그리고 예제들을 살펴보았다. 간단하게 정리하면 분기 명령어 중 조건 분기와 무조건 분기는 CC 코드를 이용해 분기 명령어에 적힌 조건을 파악하기 때문에, 명령어를 실행시키기 전에 반드시 조건식의 CC 코드를 발생시켜 두어야 했다. 그리고 분기 명령어의 실행 직후에는 Branch Delay Slot 이 반드시 발생하였다. 이번 글에서는 Branch Delay Slot 이 발생하는 이유를 실제 명령어의 실행 파이프라인을 따라가보며 정리해보고자 한다. 다음과 같은 명령어를 순차적으로 실행시킨다고 하자. ble next_r - A add R1, R2, R3 - B mov 130, R4 - C ... next_r: - D add R3, R4, R1 set str, ..
지난 글까지 산술 명령어, 논리 명령어, 비트 명령어를 정리하였다. 이번 글부터는 분기 명령어에 대해 정리하고자 한다. Flow Control In Assembly 흐름제어는 한다면 코드가 위에서부터 아래로 한 줄씩 실행되는 것이 아니라, 특정 위치로 건너가 실행하도록 설정하는 것을 의미한다. C언어에서 흐름 제어 키워드를 생각을 해보면 아래와 같은 키워드가 있다. 반복 : for, while, do while 분기 : switch, if, else 기타 : goto, 함수 그리고 강제로 이동하는 goto 문을 제외하면, 건너 뛸지 말지 여부를 결정하기 위한 '조건 체크'가 반드시 필요하다. 조건 체크는 비교 연산자를 사용한다. (!=, ==, , ...등등) 어셈블리의 관점에서 흐름 제어도 마찬가지이다..
