Implement and Evaluate Advanced Power Efficient Gathering in Sensor Information System (개선된 센서 라우팅 방식 A-PEGASIS 구현 및 성능 평가)

 

정명수               박규영

(Myoungsoo Jung) (Gyuyoung Park)

 

본 기술 문서는 서창진과 양진웅에 의해서 구현된 개선된 센서 라우팅 방식(A-PEGASIS)을 구현하고 TyniOS와 TOSSIM을 이용하여 기존 LEACH 라우팅 방식과의 성능 비교를 위해 작성 되었다. 본 기술 문서에서는 단순히 A-PEGASIS 논문에 제시된 애매한 제한된 스패닝 체인 트리 메소드를 보다 명확히 기술하고 이에 대한 알고리즘과 동작방식을 구체적으로 제시한다. 본 기술 문서의 실험치는 TinyOS와 TOSSIM환경 위에서 구현된 A-PEGASIS 통신 방식은 기준 LEACH에 비해서 에너지 소비량(산술적 평균) 24% 향상, Base station과 통신을 위해 각 노드들의 생존량이 1.85~3배 정도되는 것을 보여 준다.

 

1. INTRODUCTION

최초 계층 구조 알고리즘인 LEACH는 Base station과 통신하기 위해 Figure 1에서처럼 전체 네트워크의 망을 특정한 개수 개의 센서 노드를 가진 클러스터로 나누고 그 중에서 클러스터 헤더 또는 coordinator로 불리는 대표자를 선출하여 이를 통하여 Base station과 통신을 한다. 통신을 할때는 해당 클러스터의 모든 측정값들을 하나의 패킷으로 Fusion하여 통신을 하게 되는데 그 결과 멀리 떨어져 있는 Base station과 집적 통신하는 노드의 수를 줄이고 클러스터 헤더에서 일괄적으로 퓨전하여 전송 되는 에너지 소비를 줄였다.

Figure 1클러스터의 구성 방법과 LEACH의 계층 구조

 

클러스터 헤더를 통한 LEACH의 통신 접근 방법은 무선 선서 네트워크의 가장 간단한 통신방법인Flooding이나 Gossiping 보다 훨씬 효율적인 동작을 수행 하지만 클러스터 헤더를 선출(Selection) 하는 과정에서 비효율적인 문제가 발생한다. 다시 말해서 각각의 클러스터 안에 분산적이며 확률적인 방법으로 선택된 클러스터 헤더의 센서 노드들은 클러스터가 중첩(Overlap)되는 특정 지역이 발생하여 클러스터 헤더가 밀집되는 현상이 발한다. 이러한 현상은 Base Station에게 측정값을 전달하는 토폴로지의 경로가 길어지게 되는 결과를 초래하며 이로 인해 성능 하락을 보이게 된다.

 

이에 반하여, 서창진과 양진웅에 의해서 제안된 A-PEGASIS는 기존 계층 구조 알고리즘들을 계선한 PEGASIS 알고리즘에 약간의 수정을 가하여 좀 더 효율적인 통신 알고리즘을 제안한다. 이 두 논문 다 Coordinator(PEGASIS군에서는 클러스터라는 의미가 존재 하지 않으므로 대표자라는 이름으로 대신하며 이는 클러스터의 헤더와 같은 역할을 한다)가 100% 퓨전을 하는 가정을 기반으로 하였기 때문에 Coordinator수가 하나로 축약된 계층 알고리즘으로 에너지 전달의 소비를 대폭 감소하였다. 다만 PEGASIS에서는 체인을 생성할 당시 Prim Algorithm을 사용하는데 이를 통하여 생성된 체인은 평균 길이가 길고 마지막으로 선정된 링크의 길이가 다른 노드들에 비하여 다소 긴 경향을 가지는 단점을 가지고 있다. 다소 긴 링크를 가지는 노드의 인접 노드들은 전송 에너지가 다른 노드들에 비하여 일찍 고갈 되는 경향이 존재 하는데 A-PEGASIS는 이러한 단점을 극복하기 위하여 Kruskal Algoritm의 유망집합(Promising set)을 사용하고 링크 스와핑 기법을 통해서 이를 조금 더 개선한 알고리즘이다.

 

본 기술 문서는 아래와 같은 순서로 구성되어 있다. 섹션 2에서는 A-PEGASIS를 실제 구현하고 평가 하기 위해서 문제가 되는 것들을 제시하고 이에 대한 해결 방법을 모색해본다. 섹션 3에서는 실제 문제가 되는 애매한 제한된 스패닝 체인 트리의 알고리즘을 명확하게 기술하고 TinyOS와 TOSSIM에서 A-PEGASIS를 구현하기 위한 기타 방법들을 기술한다. 섹션 4는, TinyOS와 TOSSIM위에서 구현된 A-PEGASIS의 Coordinator 선출 과 체인 변경에 실제 예를 제시하며 성능 결과치를 제공한다.

 

2. IMPLEMENTATION CHALLENGES

제안된 A-PEGISIS 알고리즘을 구현 하기 위해서 우리는 아래와 같은 몇 가지 문제를 해결 해야 했다.

1. 슈퍼라운드 변경 시까지 생성된 체인을 모두 동기화 하기 위한 정보 공유.
2. A-PEGASIS에서 제안된 제한된 스패닝 체인을 구성하기 위한 실제 알고리즘의 부재
3. A-PAGASIS에서 사용되는 가중치를 구하기 위한 도출 식들의 가정을 실제 구현에 반영하는 문제
4. 기존 LEACH를 변경 하는 것이 아니라 새로운 모듈을 작성 하는 수준의 구현사항
5. 각 노드들의 위치 정보를 TinyOS가 제공하지 않음으로써 발생하는 환경 정보 가공 문제

 

첫째, TinyOS와 NesC의 구조상, 각 노드들은 하나의 코드를 공유하여 인스턴스를 생성한다. LEACH에 구현된 MHLeachPSM 모듈을 기반으로 구현을 되짚어보면 각 노드들은 다른 노드들의 정보를 하나의 전역 변수에 선언하여 이를 공유하게 되는데 이 정보들을 Advertise라는 커뮤니케이션 방식에 따라서 이를 공유한다. 여기서 공유하게 되는 것은 노드들의 에너지, 노드 주소, 클러스터헤더인지 아닌지, 노드가 살아 있는지 아닌지 정도를 공유하게 된다. A-PEGASIS와 본 기술 문서에서 제시된 변형된 Kruskal의 제한된 스패닝 체인 트리는 각 노드간의 edge정보, 방향성, 그리고 논문의 도출식에 의해서 계산된 가중치 정보들은 튜플 형태의 벡터로 구성되고 완전한 정보를 제공하기 위해 완전 그래프(Complete Graph)형태로 제시 되기 때문에 데이터 사이즈가 커서 advertise와 같은 프로토콜로 공유 될 수 없다. 따라서 TyniOS와 TOSSIM기반의 A-PEGASIS 구현에서는 매 노드에서 이를 공유하는 방법이 하나의 문제점으로 부각된다.

 

둘째, 제시된 A-PEGASIS의 알고리즘은 섹션 3의 구현과 해결책에서 다시 한번 제시 되겠지만 크게 3가지로 프로시저로 분류된다. 가중치 계산을 처음 진행하고 이에 따라 제한된 Kruskal 스패닝 체인 트리를 형성한 뒤 링크간 스와핑의 적용이 가능한 경우 이를 해결 해야 한다. 문제는 토폴로지를 형성에 핵심이 되는 제한된 스패닝 체인 트리의 형성에 있다. 우선적으로 Kruskal 알고리즘은 최소 가중치를 가지는 토폴로지를 형성하기 위해 유망 집합(Promising Set)을 사용하는데 Kruskal에 의해 원래 그래프와 완전이 서로소인 솔루션 유망 집합을 얻고 나면 이를 체인으로 변경하는데 문제가 발생한다. 왜냐하면 트리를 끊어내는 방식으로 체인을 형성하면 그래프간의 단절이 발생하고 이 때문에 하나의 coordinator로 base station과 통신할 수 없는 문제가 발생한다. 이 부분에 대해서 A-PEGASIS는 의사수준의 알고리즘도 제공하고 있지 않다. 이 문제에 대해서는 섹션 3에서 다시 좀 더 구체화 하여 토론 해보도록 하겠다.

 

마지막으로, A-PEGASIS는 가중치 계산과 Coordinator선출에 있어서 각 노드들의 위치를 기반으로 한 거리를 판단 할 수 있어야 하며 에너지 잔량을 측정 할 수 있어야 한다. TyniOS와 TOSSIM기반의 시뮬레이션에서 작성된 A-PEGASIS 모듈은 이러한 환경 정보를 읽어오는데 한계가 있다. 따라서 본 기술 문서의 프로젝트 코드에서는 TOSSIM의 네트워크 형성을 Grid로 가정하고 각 거리를 계산 하였으며 에너지는 모든 노드가 동일하게 가지고 시작하며 스패닝 체인 정보 공유를 위해 Coordinator가 변경 되는 순간에 일괄적으로 이를 반영하는 가정을 포함한다. 또한 본 프로젝트는 원래 LEACH 코드를 이해하고 이를 개선 방법을 공부하는 것과 함께 LEACH를 완전히 대체하는 A-PEGASIS 모듈을 따로 작성하였다.

 

3. DETAILED IMPLEMENTATION AND SOLUTIONS

3.1 Kruskal Spanning Tree

최소 신장 비용 트리(Minimum Spanning Tree)를 위하여 첫 번째로 구현된 Kruskal Algorithms은 구현 된 소스의 A-PEGASIS 모듈의 BuildMST() 인터페이스를 통해 이루어진다. 기존 PEGASIS 논문과 A-PEGASIS 논문에서 제시된 알고리즘은 모두 토폴로지 형성에 있어서 Node Degree와 Adjacent Node가 2인 특수 트리인 체인을 통해서 만들어진다. 기존 PEGASIS의 논문에서는 Prim Algorithms을 통해서 PEGASIS 체인을 형성하지만 서창진과 양진웅에 의해서 구현된 A-PAGASIS는 최소 신장 비용 트리를 형성하는 Kruskal Algorithm에 f가 2d인 제약사항을 가하여 토폴로지를 형성한다.

Table 1 Kruskal 스패닝 트리 구현 알고리즘

Figure 2은 스타를 내포한 육각형 네트워크의 중심에 base station이 있고 설명의 편의를 위하여각 edge마다 에너지와 distance를 고려한 가중치가 숫자로 주어져 있다. Kruskal Algorithms은 Figure 2에서 볼 수 있듯이 우선적으로 가중치가 낮은 순서대로 edge를 소팅하여 가중치가 낮은 edge부터 최소 비용 신장 트리에 삽입을 고려한다. 이때 가중치로만 고려를 하기 때문에 base station을 포함한 edge임은 고려 대상이 아니다. 최소 비용 신장 트리에 삽입 되기전에 Kruskal Algorithms에서는 포리스트(Forest)로 불리는 유망집합(Promising set)들(Figure에는 회색으로 표기된 것들 것 각각의 유망 집합들이다)을 각각 구성하고 최소 가중치를 가진 edge부터 유망 집합에 병합하는 작업을 진행한다.(여기서 유망 집합은 생성 되기 전까지 node개수만큼 많은 독립된 집합으로 형성이 가능하다) 이렇게 유망 집합은 공집합으로 시작하여 Figure 2에 주어진 모든 노드들을 유망 집합에 삽입하고 기존 집합과 서로소가 될 때 이를 종료한다. Table 1는 A-pegasis 모듈을 BuildMST 인터페이스에 구현된 소스의 의사코드를 기술하고 있다.

 

3.2 Limited Spanning Chain Tree

A-PEGASIS에서는 제한된 스패닝 체인 트리를 형성한다. 서창진과 양진웅에 의해서 제시된 스패팅 체인 트리 절차는 대략적으로 아래와 같다.

1. 거리와 남은 에너지를 가지고 각 edge마다 가중치를 계산
2. 가중치를 바탕으로 Kruskal 알고리즘을 통하여 스패닝 트리를 형성
3. 스패닝 트리의 링크 스와핑.

거리와 남은 에너지를 가지고 계산하는 가중치는 A-PEGASIS의 방식을 TyniOS와 TOSSIM에서 사용이 가능한 정보와 가정수준에서 새로 구성하였으며 에너지 도출 식(1,2)은 아래와 같다.

 

Table 2 본 기술문서에서 제시되고 작성된 제한된 스패닝 체인 트리 구성 알고리즘

에너지를 통한 가중치가 계산되면 스패팅 체인 트리를 형성 해야 하는데 여기에는 섹션 2에서 언급되었던 문제가 발생한다. 유망 집합과 원래 입력 그래프의 서로소 상태를 확인 하며 스패닝 트리를 형성한 뒤 다시 제한된 스페닝 체인을 형성하기 위하여 트리를 잘라 체인을 만들면 그래프가 분리되어 하나 이상의 Coordinator가 선출 되는 문제가 발생한다. 이 부분의 기술이 미흡한 관계로 우리는 Table 2에서 제시된 알고리즘 대로 방문 노드와 방문 노드로부터 인접한 노드들의 가중치를 고려하여 다시 스패닝 트리를 작성하였다.

 

Figure 3는 본 기술 문서에서 해결책으로 작성된 제한된 스패닝 체인 트리의 작성 세부 절차를 보여 준다.

4. EVALUATION

 

4.1 Coordinator 변경 실례

우리는 솔루션에 제시되고 논문이 기술 된 바대로 슈퍼 라운드마다 스패닝 체인을 형성하여 coordinator를 재선정한다. Figure XX는 TyniOS와 TOSSIM에서 실제 구현된 결과를 반영하여 슈퍼라운드시 마다 실제 체인 형성이 완전히 새로 구성되며 이를 통하여 새로 선정된 coordinator와 base station간의 통신 상태를 보여준다.

<Figure 4, 새로 생성되는 스패닝 체인과 Coordinator 변경 실례>

 

이러한 체인 재 형성과정과 재 선정된 coordinator는 이론적으로 A-PEGASIS의 100% 퓨전이 가능하다고 가정하면 LEACH에서 발생하는 문제인 특정 영역 밀집 현상과 클러스터마다 클러스터 헤더가 base station과 통신하는 비용 및 이로 인한 에너지 절감 효과가 충분히 가능하다는 사실을 보여준다.

 

4.2 데드 노드 빈도수

성능 결과치를 도출 하기 위해 우리는 각 edge간 거리를 기본 유닛을 1으로 설정하고 최소거리 1, 최대 거리가 3으로 가정하였다. 디스턴스 팩터(Distance Factor)는 거리 1일 때 40, 2일 때 80, 3일 때 120으로 설정하였다. 에너지를 구하는 식은 모든 노드가 초기 1000이라는 값으로 에서 시작을 하고 슈퍼라운드를 결정하는 각 라운드의 이전 노드가 가지고 있던 에너지에서 디스턴스 펙터를 감산한다.

<Figure 5, 데드노드 빈도수 – 1차 시도>

<Figure 6, 데드노드 빈도수 – 2차 시도>

 

 

Figure XX를 통한 결과치는 각각 1차 2차, 3차 시도를 표현하고 있다. LEACH의 경우 클러스터 헤더를 확률적 선택방법에 의존하여 랜덤하게 추출하기 때문에 하기 때문에 재선정 되고 전체 시뮬레이션 기간 동안 각 노드가 처리해야 하는 빈도수가 A-PEGASIS보다 높기 때문에 일찍 죽을 수 있다는 것을 설명한다. 반면에 A-PEGASIS는 coordinator는 클러스터가 아닌 전체 스패닝 체인에 따라 선출 기회가 균등하게 이루어 지기 때문에 시간이 지남에 따라 죽는 빈도가 낮다.

 

4.2 시간대 별 평균 잔존 에너지량.

평균 에너지는 총 노드에 잔존 에너지들의 합을 총 가정 노드 수(6)을 통해 산술적 평균으로 구해진다. Figure XX는 LEACH는 클러스터 헤더들이 A-PEGASIS 보다 많이 선출 되기 때문에 A-PEGASIS비하여 Base station과 통신을 하기 위해 에너지를 많이 소비하게 된다. 반면에 A-PEGASIS는 전체 체인에서 하나의 coordinator 를 균일하게 선출하기 때문에 좀 더 안정적인 결과를 보여준다.

<Figure 7, 시간대별 평균 잔존 에너지량>

 

시간대 별 죽은 노드 개수 - 1차 시도
sec.	0	100	200	300	400
LEACH	0	0	1	2	2
A-PEGASIS	0	0	0	0	1
시간대 별 죽은 노드 개수 - 2차 시도
sec.	0	100	200	300	400
LEACH	0	1	2	2	3
A-PEGASIS	0	0	0	0	1
시간대 별 남은 평균 에너지 양
sec.	0	100	200	300	400
LEACH	6000	5280	4460	3780	3040
A-PEGASIS	6000	5440	4820	4140	3780

<Figure 6, 각 실험 별 통계 수치>

 

5. CONCLUSION

위에 기술한 결과를 통해서 보면 A-PEGASIS가 LEACH보다 모트들의 에너지 특성을 더 효율적으로 고려한다는 것을 알 수 있고더 나은 성능을 보여주었다. LEACH도 역시 WSN의 효율적인 이용을 위해 고안된 프로토콜이긴 하지만 각 클러스터의 헤더를 선출하는 방법에 있어서 Random하게 선출하기에 때문에 각 모트의 에너지 상태를 반영하지 못한다는 한계를 가지고 있다. 즉, 헤더가 자신의 클러스터에 속한 다른 모트들로부터 받은 데이터를 퓨징하여 베이스 스테이션으로 한꺼번에 전달하게 되는데 네트워크의 규모가 커질 수 록 클러스터의 개수가 늘어나게 되고 클러스터의 헤더들은 다른 모트들보다 더 많은 에너지를 소비하게 된다. 이 때 헤더의 선출에 남은 에너지량을 고려하지 않고 Random하게 헤더를 선출하게 되므로 직전 라운드에 헤더였던 노드가 다시 선택된다면 그 모트는 빨리 에너지가 고갈될 수 밖에 없다. 이러한 문제점을 A-PEGASIS가 해결해 주었다는 것을 본 문서의 결과를 통해 알 수 있었다. 네트워크의 체인을 형성하고 헤더를 선출하는 과정에 있어서 각 모트와 베이스 스테이션사이의 거리, 그리고 각 모트의 남은 에너지량을 통해서 가장 베이스 스테이션과의 비용이 적은 모트를 각 라운드마다 선출함으로써 전체적인 모트들의 평균 에너지량을 균일하게 맞출 수 있었고 각 모트들의 수명 또한 더 오래 지속될 수 있었다. 실험치는 TinyOS와 TOSSIM환경 위에서 구현된 A-PEGASIS 통신 방식은 기준 LEACH에 비해서 에너지 소비량(산술적 평균) 24% 향상, Base station과 통신을 위해 각 노드들의 생존량이 1.85~3배 정도되는 것을 보여 준다.

 

6. REFERENCE

[1] 서창진, 양진웅, "개선된 센서 라우팅 방식 : A-PEGASIS (A-PEGASIS : Advanced Power Efficient GAthering in Sensor Information Systems)", 2007 12, 정보 과학회

[2] Stephanie Lindsey, Cauligi S. Raghavendra,, "PEGASIS: Power-Efficient Gathering in Sensor

Information Systems"

[3] D. Estrin, R. Govindan, J. Heidemann, and Satish Kumar. "Next Century Challenges: Scalable Coordination in Sensor Networks. In Proceedings of Mobicom" 99, 1999.

[4] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan." Energy-Efficient Communication Protocol for Wireless Microsensor Networks. In Proceedings of the Hawaii Conference on System Sciences", Jan. 2000.

Rotational Latencies

Rotational Latency는 head가 올바른 track의 위치로 이동된 뒤에 시작 LBA를 찾아 가는데 까지 걸리는 시간을 의미한다. 최악의 경우 드라이브는 시작 LBA를 찾기 위해 full rotation을 하면서 시간을 다 소진 할 수도 있다. Rtoational Latency는 RPM에 의존 하는데 7200 RPM의 HDD의 경우 최악의 시나리오에서 8.3 msec정도를 소비 할 수 있으며 5400 RPM의 HDD는 11.1 msec가 소비되며 10K HDD라면 6 msec정도 소비하게 된다. 랜덤 IO의 경우 일반적으로 최악의 시나리오에서 1/2정도의 시간을 필요로 한다.

msec는 요즘 같은 시대에 매우 극적인 시간이다. 왜냐하면 다수의 스레드나 또는 하이퍼 스레딩에 의한 프로세스들이 워크로드에 관계없이 거의 동시에 같은 드라이브에 접근하여 Data를 요구 하기 때문이다. 물론 높은 RPM을 가진 드라이버는 Rotational Latency를 줄이는 하나의 접근 방법이지만 RPM을 올리기 위해서는 부가적인 비용이 필요하다.

우리는 드라이버의 Rotational Latency를 향상 시키기 위해 두가지의 어프로치가 있다. 하나는 처리해야 할 Command를 re-ordering하는 것이다. 이 최적화는 seek latency를 줄이는 것과 유사한 최적화이지만 다음에 서비스되어야할 Command를 결정하는데 있어서 다른 계정을 가지고 있어야 한다. 두번째는 Out of data로 불리는 Data 전송을 최적화 하는 이슈이다. Out of data라는 것은 head가 시작 LBA로 부터 읽지 않아도 target LBA로 부터 어떤 위치의 data도 읽을 수 있다는 것이다.

Out of data 전송을 할 때 최악의 경우는 완전히 platter의 한번 rotation을 소진 하여 모든 전송을 마칠 수 있는 것에 비해 한번의 rotation에 많은 양의 rotation을 추가적으로 소진하게 될 수 있다.

Benefits of Native Command Queuing

이로서 실행해야 할 Command들이 메커니컬한 오버헤드와 IO Latency 개선을 위하여 Reodering되어야 함은 명백해 졌다. 그럼에두 불구하고 하나의 Queue에 단순히 Command를 모으는 것은 가치 없는 일이다. 최소의 서비스 타입을 가지도록 reordering하는 효율적 알고리즘이 필요하다. 이러한 프로스세는 Seek 와 Rotational latency를 위한 Command최적화와 Tagged Command queue에서 언급 되었었다. Enduarance와 wear에 관한 개선은 Command queuing과 메커니컬 워크로드를 줄이는 스킴의 side effect로서 부가적인 이익을 얻을 수 있다. SATA2는 Nativce Command Queuing이라고 불리는 tagged Command queuing을 효율적인 프로토콜로 제공하고 있다.

Native Command Queing은 효율적인 command의 reodering을 통해서 높은 성능을 얻을 수 있도록 하여 준다. 추가적으로 SATA 프로토콜안에는 NCQ의 성능을 향상 시키기 위해 아래와 같은 3가지의 Capability를 가지고 있다.

•  Race Free Status Return machanism (RFSR)

이 feature는 어떤 Command이든지 아무때나 통신할 수 있는 상태를 허락한다. 여기는 status를 host와 통신하기 위하여 handshake와 같은것이 불필요 하다. 드라이버는 다중 Command를 같은 시간에 처리 하거나 back-to-back하기 위하여 Command 완료를 이슈할 수도 있다

• Interrupt Aggregation

일반적으로 드라이버는 Command를 완료할때 호스트를 매번 Interrupt할 수 있다. 이러한 Interrupt가 많아지면 Host에게는 많은 부하가 걸리게 된다. 하지만 NCQ의 경우 Command는 Interrupt를 averaging 시킬 수 있다. 만약 드라이버가 짧은 시간안에 여러개의 Command를 처리 하게 될 경우 개인적인 Intterupt들은 Aggregation할 수 있게 되고 이렇게 되면 Host controller는 여러개의 Command에 대하여 한번의 Interrupt만 처리 하면 된다.

• First Party DMA(FPDMA)

NCQ는 드라이브가 host의 software의 간섭없이 DMA 동작을 수행하기 위한 메커니즘을 가지고 있다. 이 케머니즘을 FPDMA라고 부른다. 드라이버는 DMA Setup FIS에 DMA Context를 설정하고서 이를 Host Controller로 부른다. 이 DMA를 위한 Command에 붙어 있는 Tag를 FIS는 명세 하고 있다. Tag의 값에 의하여 DMA가 세팅되고 Host에게 보내지고 나면 Host controller는 Commad 수행을 위해서 PRD table에서 pointer를 하나씩 꺼내어 DMA엔진에 넣는다. 그리고 나면 전송은 어떤 Software의 간섭도 필요없이 DMA를 수행하게 된다. 이것은 드라이버에게 큰 의미를 가진다. 생각 해보면 드라이버가 직접 버퍼를 선택하여 전달 할 수 있고 이는 효율적인 Reodering 스킴을 가능하도록 해주고 있다.

Detailed Description of NCQ

 NCQ에는 3가지 중요한 콤포넌트들이 있다.

1. 드라이브 안에서 Command의 Queue를 build하는 것
2. 각각의 Command들을 Transfering하는것
3. Command가 끝이 났을때의 Status를 return하는 것

아래 section들에서 각각의 메커니즘이 어떻게 동작하는지 살펴 볼것이다.

Building a Queue

드라이브는 반드시 드라이버가 특별한 command를 받았을 때 이를 Command를 Queuing할것인지 아니면 즉각적으로 처리 할 것인지를 알아야 한다.  추가적으로 드라이브는 리시브 Command에 대한 프로토콜을 이해하고 있어야 한다. 여기서 받게될 Command는 PIO, DMA, NCQ등이 될 수 있다. 드라이버는 특별한 Command가 issue되었을때 opcode를 통해서 앞에서 말한 정보들을 결정해야 한다. 그래서 Advatage를 가진 NCQ를 지원하기 위해서 NCQ는 두가지의 SATA2에 2개의 NCQ Command를 추가 해두었다. 하나는 Read FPDMA Queued고 다른 하나는 Write FPDMA Queued이다. Read FPDMA는 아래 fig.1에 나와 있다. write FPDMA Queued도 Read FPDMA와 유사한 구조를 가지고 있다. 이 Commnand는 큰 용량의 디바이스를 지원하기 위해 sector 카운트와 확장 LBA를 가지고 있다. 이 Command는 FUA(Force Unit Access)라는 비트를 특정 Applicaion을 위해 가지고 있다. Write FPDMA에서 FUA가 set되어 있다먼 그 드라이브는 Commnad의 Success Status를 return하기 전에 반드시 미디어로 저장되었는지 확인 해야 한다. FUA Bit는 Host가 드라이버의 내부 캐시 에 있지 않은 데이터와 아닌 테이터의 양을 관리 하기 위해 반드시 필요한 비트이다.

register에서 흥미로운 tag 하나가 바로 Sector count이다. Queuing된 각각의 Command는 이와 관련된 tag를 가지고 있어야 하는데 이 tag가 sector count이다. 이 tag는 Host와 드라이브 사이에서 실행 해야 할 Command를 구분 하기 위해서 사용 된다. Tag의 값은 0과 31 사이의 값을 지원 기 때문에 드라이브는 32 미만의 queue depth를 가질 수 밖에 없다. 결국 이 tag의 값은 드라이버가 제공하는 최대 값을 32이하로 제한한다. 모든 Command에 대한 Status를 포함하는 것은 32bi값으로 리포트 할 수 있다. 각각의 실행될 Command들은 unique한 Tag값을 가지고 있어야 한다.

Read와 Write FPDMA Queued Command는 다른 Command들과 같이 이슈된다. 예를 들어 taskfile을 특정 레지스터 값과 함께 write해야 할때 그때는 Command 레지스터는 Command의 OPCODE와 함께 쓰여지게 된다. Non queued command와 queued command 간의 차이는 command가 이슈가 될때 발생한다. 만약 Non queued command라면 드라이브는 Command에 대한 data를 전송하고 Status 레지스터 안에 있는 BSY 비트를 클리어 하여 호스트에게 Command가 완료 된것을 알릴 것이다. 반면 Queued command가 이슈가 되었을때는 호스트에게 어떤 데이터가 전달되기 전에 BSY 비트를 즉각 클리어 시킬 것이다. Queuing중에 BSY비트는 전송을 위해 사용되지 않는다. 대신에 BSY비트는 드라이브가 새로운 Command를 받아 딜을 수 있는 비트로 사용된다. BSY 비트가 클리어 되자 마자 호스트는 다른 Queued Command드를 드라이브에게 이슈 할 수 있다. 이러한 방법으로 Command의 Queue는 드라이브 안에서 빌드 될 수 있다.

Introduction

미디어나 Mass storage와 같은 device는 전체 시스템에 큰 영향을 미친다. 현대의 다른 시스템의 전자적인 요소와 마찬가지로 데이터를 인출하거나 데이터에 접근하는 속도의 제한등에 의한 케머니컬 퍼포먼스는 물리적인 요소들이 개선되어야 한다. 하지만 메너니컬 프로세스의 내부 관리 시퀀스는 좀더 지능적이고 특별한 방법에 의해서 전체 흐름을 변경하여 대단히 많은 부분, 개선을 시킬 수 있다. 여기서 지능적이고 특별하다는 말은, 요구 받은 Command에 대하여 좀 더 높은 퍼포먼스를 내기 위해 내부적으로 적절한 결정을 하는 것을 말한다.

NCQ는 SATA의 Command protocol로 동시간대에 드라이브가 가능한 멀티플 커맨드를 지원한다. 요구받은 Command를 관리 하는 NCQ를 내부적으로 가지고 있는 드라이브들은 동적으로 Rescheduling하거나 또는 re-ordering할 수 있다. 또한 NCQ는 특정 Command가 Data를 seek하고 있는 동안에도 추가적인 Command를 isue하는 것을 하락한다.

Windows나 linux와 같은 OS의 멀티 스레드 소프트웨어나 하이퍼 스레딩 기술을 기반으로 한 프로세서의 경우 더욱 이점을 가질 수 있다 이러한 feature는 높은 잠재적인 요소를 가지는 많은 워크로드를 생성 할 수 있다. NCQ의 Utilization을 통하여 disk의 성능은 상당히 향상 될 수 있다.

Driver basics

Hard drive는 전자적인 장치이기도 하지만 전자적인 요소와 물리적인 요소의 콤포넌트를 모두 가진 하이브리드 장치이다. 물리적인 요소가 하드 드라이브에서 Portion은 포퍼먼스 제안에 치명적인 factor가 될 수 있다. 이러한 물리적 리밋을 이해하기 위해서는 데이타가 어떻게 laid out되는 지 짧은 논의를 해보는 것이 도움이 될 수 있다.

Data가 write될때는 맨 아래의 platter인 disk 0에서 track 0에서 head 0에 의해 read/write의 처음 동작이 실행된다. head 0 위의 track 0에 write가 시작이 완료 되고나면 다음 dksik인 head 1의 track 0가 write된다. 이런식으로 반복 작업을 통하여 마지막 디스크의 마지막 head까지 write를 실행하고 나면  data를 write하기 위해 disk의 동심원쪽으로 좀더 가깝게 head를 이동하여 write를 수행한다. 이런 같은 위치에 존재하는 모든 헤더의 track을 실린더라고 칭한다. 그래서 data는 디스크의 가장 바깥쪽 실린더를 시작으로하여 안쪽으로 배치되게 된다.

그런데 Application들이 실제로 disk에 write하기 위해서 접근한느 경우는 드물다. 더욱이 Application들은 drive의 모든 portion에 대하여 write되는 data를 scatter하여 출력하는 경향이 강하기 때문에 disk의 물리적 위치 이동은 head를 위치 탐색을 위해 회전하는 것이 적도록 적절히 read/write를 재배치 하는 것이 필요하다.

탐색과 회전의 지연시간에 대하여 가장 잘 알려진 알고리즘은 Rotational Position Ordering이다. 이 RPO는 퍼포먼스를 최대화 하고 회전 지연율과 탐색을 최소화 향상 시키기위해 Command를 재비치하여 실행 하는것이 허락 된다. Access시간은 head의 회전을 기다리는 지연시간과 실제 data를 찾는 탐색시간으로 구성된다.

이전에 짧은 시간 탐색을 위한 최단거리 측정 알고리즘은 매우 간단 했다. 그러나 이제는 짧은 seek만이 access time을 결정 할 수 없다. RPO은 디스크의 회전 위치에 대한 고려 뿐만 아니라 Command를 실행하는 순서에 의한 seek disance거리를 고려해야 한다. Command는 성능 향상을 위해 회전 지연시간과 (Rotational Latency time) seek time을 잘 조합하여 짧은 access time을 결정해야 한다.

NCQ는 드라이브가 Re ordering하여 최대 성능을 낼 수 있도록 최적화 하는 Advantage RPO를 쓸 수 있도록 지원한다.

Seek Latency Optimization

Seek Latency는 Read/Write를 위해 head를 적절한 LBA가 포함된 적절한 track으로 옮기는데 걸리는 시간이 원인이다. 모든 target LBA를 엑세스 하기 위한 Command가 Queuing하지 않고서 access가 issued될 수도 있다. 하지만 drive가 적절한 순수에 의해 Command를 최적화 시킬 수 있다면 Command가 같은 시간에 Drive될 수 있다. 이는 Elevator알고리즘과 같다. 만약 버튼을 눌려서 서야 하는 층에 대해서 모두 즉각적으로 반응한다면 이는 매우 비효율 적일 것이다.  Elvator가 타겟에 대한 Re ordering을 이해하고 있다면 좀더 빠른 모드로 오퍼레이션 할 수 있을 것이다. SATA의 경우도 명세된 시작 위치를 re-ordering할 수 잇다 하지만 re-ordering scheme은 다이나믹이어야 한다. 여기서 다이나믹은 어떤 시간에든 Command Queue에 추가적인 Command가 들어 올 수 있다는 것을 의미한다. 이 새로운 Command는 실행중인 스레드에 비협조적인 명령일 수도 있고 다음 실행 명령어에 비협조적인 명령일 수 있지만, 얼마나 효율적인가는 우리가 어떻게 그 새로운 명령어를 어떻게 잘 조절하는가에 달려 있다.

HDD의 테크놀러지에서 이 Re-ordering scheme은 드라이브의 메커니컬한 오버헤드를 줄이는것은 Command를 queuing하는 것과(Elevator의 button을 눌리는것)과 그들을 호스트에 요청에 의한 효율적인 전달을 위해 얼마나 re-ordering하는 것에 달려있다. 하나의 Command를 실행하는 동안에 새로운 Command는 Queuing될 수도 있고 Workload안에서 다른 Command와 통합 될 수도 있다. 만약 새로운 Command가 가장 효율적으로 실행 될 수 있다면 그 Command는 바로 다음번 실행때 완료될 수 있을 것이다.

다만, 명심해야 할 것은 Queuing에 의해서 pending된 Command를 re-ordering하는 것은 마지막 Command가 끝났을때의 LBA의 위치에 있는 head들이 가장 효율적인 솔루션은 아닐 수 있다는 것이다. Elevator가 사람이 버튼을 눌렸을때 그 층을 단지 지나가버리는 것이 효율적이지 못할 수 있는 것과 유사하게 HDD는 다음 서비스에 새로운 Command를 결정하는 복잡한 알고리즘을 사용해야 한다. 가능한 Head의 스위칭과 다른 트랙을 seek하는 time, 그리고 다른 동작 모드에 의해서 알고리즘의 복잡도는 결정된다. 예를 들어 Seek 해야 하는 길이, 방향과 위치등을 고려하여 실행해야 하는 요소들이 파라미터로 들어 갈 수 있을 뿐만 아니라 같은 위치의 IO프로세스에 대한 Cache hit와 miss의 상관 관계, 그리고 write cache에 대한 동작 여부 결정에 의해서도 복잡해진다. 이런 것 이외에도 Command가 더이상 유효하게 되지 않아 제거해야 할때의 공정성도 고려 되어야 한다.