지난 글에서는 분기 최적화에 대해 정리하였다. 분기 최적화를 하는 방법에는 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 문을 제외하면, 건너 뛸지 말지 여부를 결정하기 위한 '조건 체크'가 반드시 필요하다. 조건 체크는 비교 연산자를 사용한다. (!=, ==, , ...등등) 어셈블리의 관점에서 흐름 제어도 마찬가지이다..
지난 글에서는 논리연산 명령어에 대해 정리하였다. 논리 연산 명령어에는 and, or, xor 과 andn orn xnor 이 있었고, 각 명령어마다 cc 를 생성하는 명령어가 따로 있었다. 논리 연산에서 CC 는 N, V 만 사용한다. 합성 명령어로는 not, clr, tst, mov 와 같은 명령어가 있었다. not A = xnor A, %g0, A 로서 특정 비트와 1 의 xor 연산을 통해 0을 1로 1을 0으로 바꾸어 주었다. clr 은 0 과 and 연산을 함으로서 모든 비트를 0으로 초기화 시키고, tst 는 0과 orcc 를 한 값을 %g0 에 저장시키므로서 연산 결과를 버리고 cc 만을 보는 명령어였다. mov A, B 는 or %g0, A, B 연산으로 대체되어 A 를 그대로 B 에 넣..
지난 글까지 직선과 평면의 방정식을 내적과 외적을 이용해 구하는 과정을 정리하였다. 이번 글에서는 직선과 점 사이 최단거리, 직선과 직선 사이 최단거리, 점과 평면사이 최단거리를 구하는 방법을 정리한다. (직선과 평면의 경우, 최단거리가 존재하려면 반드시 직선과 평면이 평행해야하는데, 그 경우 직선 위 임의 점에서 평면과 최단거리를 구하면 되기 때문에 점과 평면사이 최단거리를 구하는 것과 같다.) 직선과 점 사이 최단 거리 우선 2차원에서 직선과 점 사이 최단 거리를 구하는 방법을 생각해보자 직선 밖의 점과 직선 사이의 최단 거리는 그 점에서 직선으로 수선의 발을 내렸을 때, 수선의 발과 해당 점 사이의 거리이다. 직선의 방정식을 내적을 이용하여 표현하면, 직선의 법선벡터를 쉽게 구할 수 있다. 이를 이..
지난 글까지 산술 명령어를 정리하였다. 산술 명령어 (덧셈 뺄셈, 곱셈, 나눗셈, 나머지) 연산 중, 덧셈과 뺄셈은 기계 명령어로 구현되고, 특히 뺄셈은 2의 보수를 이용하여 덧셈 연산되는 것이 특징이었다. 연산 데이터에는 signed integer 와 unsigned integer 가 있었는데, 덧셈 / 뺄셈시 각 데이터 종류별로 연산 결과에서 나오는 CC의 의미가 달라지게 되었다. unsigned 데이터 연산에서는 Carry 가 중요한 의미를 지녔으며, 덧셈시 오버플로우, 뺄셈시 캐리가 존재한다면 A = B 의미를 지니는 것으로 해석하게 되었다. signed 데이터 연산에서는 oVerflow 와 Negative 코드를 통해 연산 결과의 부호를 알아낼 수 있고, 이를 통해 두 수의..
지난 글까지 Array 를 이용한 스택과 큐의 구현에 대해 정리하였고, 지난 글에서는 특히 단순하게 구현한 큐에서 메모리를 제대로 활용하지 못하는 문제를 해결하기 위해 Circular Queue 를 구현하는 과정을 소개하였다. 이번 글에서는 Array 와 다른 Linked List 라는 새로운 자료구조를 정리하고자 한다. Linked List Linked List 는 한국어로 번역하면 '연결리스트' 라고 한다. 말 그대로 선으로 연결하여 나타낸 리스트를 의미하는데, 연결 리스트의 특징은 배열과 달리 데이터와 데이터가 메모리의 연속된 공간에 존재하지 않을 수 있다. 대신 연결된 다음 데이터를 나타낼 그 데이터의 주소를 같이 저장함으로서 데이터와 데이터의 연결관계를 나타내는 특징이 있다. 그림과 같이 저장할..
