Matching물체를 비교해서 동일한지 비교하는 것을 매칭이라고 한다.보통 두 오브젝트 사이의 유사도 거리를 비교한다. 만약 3개 이상의 매칭 페어가 발견되면, 그 물체의 위치와 방향을 결정할 수 있다. 일반적인 매칭 과정은 간단하다.특징점들 (관심 포인트) 사이의 유사도를 계산한 뒤, 가장 큰 값을 갖는 것을 대응 쌍으로 결정한다.또는 일치하는 관심 포인트 사이의 거리를 계산하여 가장 작은 거리를 갖는 것을 대응쌍으로 결정할 수도 있다. 하지만 매칭과정에서 현실적인 문제가 있다.예를 들어 서로 다른 특징을 매칭쌍으로 결정하거나 (false-positive), 유사도 점수가 낮아 동일한 객체의 특징이 매칭되지 않을 수도 있다. (false-negative) 이 경우, 전형적인 해결책은 많은 매칭 쌍을 찾..
1. hazard 고려하지 않은 회로도 내부에 파이프라인 레지스터만 그려두었다. 1. Fetch branch, jump 는 고려하지 않았다. (사실 파이프라인 회로도에서는 점프를 고려하지 않은 회로도만 있다.)PC + 4, 명령어 주소값을 IF/ID 파이프라인 레지스터로 전달한다.(instruction memory는 실수로 뺐다... 맨 뒤에 추가될 예정이다. 원래 이 단계에서 그리는 것이 맞다.) 2. Decode 우선 R-Format만 고려하여 위와 같이 작성하였다.위 부분에서 잘못된 부분이 아직은 많다. 1. RegWrite은 나중에 파이프라인으로 넘겼다가 나중에 받아와야 하고2. write address 는 rd로 받는게 아니라 rd/rt 중에 골라야 하는데3. 이것도 MEM/WB까지 넘겼다가 받..
Local Feature Extraction서로 다른 이미지에서 물체를 매칭하기 위해서, 각 물체의 '특징'을 추출해야 한다.현대에는 특징점 추출 연산으로 SIFT, SURF 와 같은 연산자를 사용하며, 이들은 스케일 (크기 변봐) , 방향, 밝기 변화에도 불구하고 같은 특징을 갖는 (불변한 값을 갖는) 특징점을 찾는 것을 목표로 한다. 사실 이미지의 특징으로 사용할 수 있는 것 중에 지난 글에서 정리한 방법대로 검출했던 '엣지' 가 있다.하지만 엣지가 제공하는 정보는 강도와 방향, 2가지에 한정된다.보다 다양한 정보를 특징으로 사용하기 위해 엣지대신 gray scale 이미지로부터 추출되는 local feature 를 사용하는 방법이 등장했다. 이 이미지는 같은 물체를 서로 다른 방향에서 찍은 이미지..
Distance VectorBellman-FordDistance Vector 는 벨만포드 알고리즘 기반의 라우팅 알고리즘이다. 벨만포드 알고리즘은 DP 기반의 알고리즘인데, 위와 같은 점화식을 사용한다.나(x)로부터 목적지(y)까지 가는데, 필요한 최단 경로는 나의 이웃 노드 v가 알려준 Dv(y) 값들과 내가 알고있는 v까지의 거리 Cx,v 로부터 최소값을 계산해서 얻는다는 아이디어다.(이때 기존의 Dx(y) 값은 사용하지 않는다. 링크의 비용이 증가하는 쪽으로 갱신되어 최소값도 증가했다면, 증가한 것으로 계산해야 되기 때문이다.) Link State 에서 사용했던 예제 그림에 벨만포드를 그대로 적용해보자.u에서 z로 가는 최단 경로를 찾고자 한다. u와 인접한 v, x, w 로 부터 각각 그 노드(..
Link State링크 스테이트 방식은 말 그대로 각 라우터가 자신이 알고있는 '링크 정보' = '링크 스태이트' 를 모두 공유해서 같은 네트워크 맵을 보는 상태를 만들고, 이 맵을 input으로 다익스트라 알고리즘을 돌려서 최단 경로를 얻는 방법이다. 다익스트라 알고리즘은, 시작점이 고정되어있을 때, 그 시작점으로부터 다른 모든 목적지까지의 최단경로를 구하는 알고리즘이다.따라서 각각의 라우터는 자신을 시작점으로 해서 다익스트라를 돌리면 다른 모든 라우터까지의 최단 경로를 알 수 있다.이를 통해 포워딩 테이블을 만든다. LS 알고리즘을 설명할 때 위와 같은 노테이션을 사용한다.Cxy는 x에서 y로 가는 비용을 말하며, 직접 연결된 링크가 없으면 무한대 값을 갖는다.D(v)는 현재 측정한 v까지 가는 최..
Network Control Plane컨트롤 플레인에는 전통적인 라우팅 알고리즘 (하지만 여전히 자주 쓰인다. 포워딩 테이블을 만드는데 사용한다.) 과 SDN 컨트롤러에 대한 내용을 다룬다.또 network 관리와 설정하는 것도 control plane 영역에서 다룬다. 실제 인터넷에서 널리 사용하는 라우팅 프로토콜로 OSPF 와 BGP가 있다.두 프로토콜이 적용되는 영역이 달라서 두 프로토콜 모두 중요하게 사용된다.상술한 전통적인 라우팅 알고리즘 내용과 관련있다. SDN 컨트롤러 개념을 구현한 프로토콜로는 OpenFlow, ODL, ONOS 컨트롤러 등이 있다.각각은 모두 특정 브랜드 이름이고, OpenFlow는 지난 글에서 정리했듯 공개된 표준이고, ODL과 ONOS은 일종의 OS이다. 네트워크를 관..
lw $1, 8($0)8번 virtual address 에서 레지스터로 데이터를 가져올 때 일어나는 과정1. virtual address 를 physical address로 변환하기1. TLB 에 접근8번 주소를 분해한다.만약 주소의 길이가 32bit 라면 4KB 페이지 크기를 고려하여 12bit 를 떼고,TLB 인덱스의 개수가 8개라면 3bit 를 index bit 로서 추가로 떼어내, 남은 17 bit 를 tag 로서 TLB 에서 PA를 찾는다. 1-1. TLB HitTLB Hit 라면 바로 Physical Address 를 가져온다.이때 TLB에 기록된 dirty bit, ref bit는 신경쓸 필요가 없는걸까? 1-2. TLB Miss메인 메모리에 있는 Page Table에 직접 접근한다. (Pa..
TLB가상 메모리를 사용할 때 참고하는 page table 이 메모리에 있기 때문에, page를 읽으려고 할 때마다 접근하는 시간이 오래 걸린다. (메모리에 대한 접근을 매우 느리게 만든다.)메모리의 특정 부분에서 데이터를 읽기 위해서 2번의 메모리 접근이 필요한 것이다. 첫번째는 VA를 PA로 변환하기 위해 page table에 접근하면서 1번 메모리에 접근하고,두번째는 이렇게 얻어온 PA를 가지고 데이터/명령어를 읽어오기 위해 메모리에 한번 더 접근한다. 그래서 이 문제를 해결하기 위해 하드웨어 지원을 추가하는 방법을 고민했다.page table에 대한 접근은 그래도 spatial locality가 꽤 좋다.명령어의 크기가 4byte인 것에 비해 4KB라는 페이지 크기는 매우 넉넉해서 한번 페이지를 ..
Middlebox미들박스는 source host로부터 목적지 호스트로 가는 데이터 경로상의 IP 라우터를 제외한 모든 다른 네트워킹 장치를 일컫는다.IP 라우터는 normal (인터넷 설계 초기부터 매우 중요한 설계 요소) 인데, 인터넷 설계 초기에는 고려하지 않았던, 새롭게 등장한 장치들을 모두 미들박스라고 한다. 대표적으로 NAT 가 있다.만약 IP주소가 넉넉해서 모든 IP주소를 항상 원하는 단체, 기관, 개인에게 공급할 수 있었다면 NAT는 등장하지 않았겠지만, IP주소가 부족한 문제가 발생해서 NAT가 source - destination 경로 사이에서 IP라우터가 하는 일 이외의 다른 일을 하기위해 등장했다. 이런 장치를 미들박스라고 한다. Middlebox 종류1. NAT 2. Firewall..
Edge Detection의 기본 원리어떤 물체의 내부, 또는 그 물체의 배경에 대해 변화가 작다면, 배경과 물체 사이의 경계 주위에서는 큰 변화가 있을 것이다.이 관찰에 기반해서, Edge detection 알고리즘은 밝기, 색상, 텍스쳐 등의 변화량을 측정하고, 큰 변화가 발생한 위치를 edge로 인식한다. 이 작업을 수행하기 위한 가장 간단한 방법은, 각 픽셀에서 gray level의 gradient vector를 계산하는 것이다.이미지를 흑백으로 바꾼 뒤, 밝기의 차이만 보는 것이다. 그 값은 위와 같이 계산할 수 있다.또한 절대적인 변화량은 이렇게 절댓값을 씌워서 얻을 수 있다.그리고 이 변화량은 마치 수학에서 두 점 사이의 변화량을 보는 것과 같이 그 변화의 뱡향을 따질 수 있다.이때 변화의 ..
