인간 기억 인출 과정을 응용하여 설계된 ACT-R 기반 페이지 교체 정책

노홍찬,박상현,Roh, Hong-Chan,Park, Sang-Hyun 한국정보처리학회 2011 정보처리학회논문지D Vol.18 No.1

자주 접근되는 데이터에 대해서 빠른 접근을 보장하기 위해 사용되는 임시저장소인 캐쉬는 컴퓨터 시스템 내에서 다양한 계층에 존재하며, 이러한 캐쉬 저장 공간 내에서 효율적으로 데이터를 관리하기 위해 다양한 페이지 교체 알고리즘들이 연구되어 왔다. 대부분의 페이지 교체 알고리즘들은 얼마나 최근에 데이터가 접근 되었는가 또는 얼마나 자주 접근되었는가를 바탕으로 향후 다시 접근될 것 같은 데이터들을 캐쉬 안에 유지하는 휴리스틱 방법을 취하고 있다. 이러한 컴퓨터 내에서의 데이터의 인출 과정은 인간의 기억 인출 과정과 유사하며, 인간의 기억 인출 과정 역시 캐쉬 구조처럼 기억이 얼마나 최근에 그리고 자주 인출되었는가에 의해 그 기억 인출의 확률과 인출속도가 결정된다는 것이 최근 연구에 의해서 밝혀진바 있다. 본 연구에서는 인간의 기억 인출 과정에서의 과거 해당 기억에 대한 인출 기록들의 최근성과 빈도가 인출 확률에 영향을 미치는 관계를 분석하고 이를 페이지 교체 알고리즘에 응용하여 기존의 페이지 교체 알고리즘의 성능을 개선하였다. 또한, 실험을 통해 제안하는 페이지 교체 알고리즘이 기존에 데이터베이스 버퍼 캐쉬에서 가장 좋은 성능을 보이는 것으로 알려진 LRFU보다 파라미터에 민감하지 않고 우수한 성능을 보인다는 것을 입증하였다. The cache structure, which is designed for assuring fast accesses to frequently accessed data, resides on the various levels of computer system hierarchies. Many studies on this cache structure have been conducted and thus many page-replacement algorithms have been proposed. Most of page-replacement algorithms are designed on the basis of heuristic methods by using their own criteria such as how recently pages are accessed and how often they are accessed. This data-retrieval process in computer systems is analogous to human memory retrieval process since the retrieval process of human memory depends on frequency and recency of the retrieval events as well. A recent study regarding human memory cognition revealed that the possibility of the retrieval success and the retrieval latency have a strong correlation with the frequency and recency of the previous retrieval events. In this paper, we propose a novel page-replacement algorithm by utilizing the knowledge from the recent research regarding human memory cognition. Through a set of experiments, we demonstrated that our new method presents better hit-ratio than the LRFU algorithm which has been known as the best performing page-replacement algorithm for DBMS caches.

플래시 메모리 상에서의 효율적인 동작을 위한 수정 B-트리 인덱스

노홍찬(Hongchan Roh),김승우(Seungwoo Kim),김우철(Woo-Cheol Kim),박상현(Sanghyun Park) 한국정보과학회 2006 한국정보과학회 학술발표논문집 Vol.33 No.2C

플래시 메모리는 기술 발전에 따른 빠른 용량 증가와 모바일 환경에 우수한 특성으로 인해 가까운 시일 내에 하드 디스크를 대체할 대용량 저장 장치로서 주목 받고 있다. 이러한 흐름에 따라 플래시 메모리 사용이 증가하고 플래시 메모리에 저장하는 데이터의 양이 점차 많아지면서 플래시 메모리 상의 효율적인 인덱스 구조에 대한 필요성도 함께 증가하고 있다. 하지만 기존의 대표적인 인덱스 중 하나인 B-트리 인덱스를 플래시 메모리에 적용하기 위해서는 하드 디스크와 플래시 메모리 간의 다른 특성들 때문에 플래시 메모리에 맞게 인덱스 구조를 수정하는 작업이 필요하다. 본 연구에서는 이를 해결하기 위한 기존의 연구에 대해 소개하고 기존 연구의 한계점과 이를 개선한 인덱스 구조를 제안한다.

서비스 지향 아키텍처에서의 효율적인 데이터 프레임 워크 구축

노홍찬(Hongchan Roh),여윤구(Yun-gu Yeo),이동현(Donghyun Lee),박상현(Lee Sanghyun Park) 한국정보과학회 2008 한국정보과학회 학술발표논문집 Vol.35 No.1

최근 서비스 지향 아키텍처를 적용한 많은 시스템들이 개발되어 왔고 그에 따라 서비스 지향 아키텍처에 대한 관심도 증가하고 있다. 하지만 여태껏 연구되어왔던 주제들은 전체 아키텍처의 효율적인 구성 및 개발 프로세스 구축에 초점을 맞춘 반면, 데이터 프레임워크를 보다 효율적으로 비즈니스 프레임워크와 분리하는 데 초점을 맞춘 연구는 부족하다. 이에 우리는 실 서비스되고 있는 대용량 서버 관리 서비스를 서비스 지향 아키텍처로 전환하고 그 중 데이터 프레임워크를 보다 추상화시키고 비즈니스 프레임워크와 느슨한 결합을 이룰 수 있도록 하는 연구를 진행하였다. 본 논문에서 제안하는 데이터 프레임워크는 실시간 데이터 전송에 유리한 트리 구조의 데이터를 사용자가 정의한 규칙을 기반으로 비즈니스 프레임워크의 다양한 비즈니스 로직에서 효율적으로 활용할 수 있는 다양한 형태의 데이터로 바꿀 수 있는 계층을 제공한다. 또한 이러한 계층에 대해 실 서비스에서 활용할 수 있는 정의된 제약조건 하에서 실험을 진행하였고 그 결과 만족스러운 성능을 보이는 것으로 나타났다.

플래시 메모리 상에서의 비용 예측 모델

노홍찬(Hongchan Roh),유진희(Jinhee you),박상현(Sanghyun Park) 한국정보과학회 2007 한국정보과학회 학술발표논문집 Vol.34 No.2A

최근 모바일 환경에서 우수한 특성으로 인해 플래시 메모리가 하드 디스크를 대체할 만한 차세대 저장 장치로서 주목을 받고 있다. 하지만 이러한 플래시 메모리는 읽기 속도에 비해 쓰기 속도가 느리고 접근 비용의 비중이 미미한 특징 때문에 하드 디스크 기반에서의 디스크 접근 횟수를 이용한 비용 예측 방법을 그대로 적용할 수 없다. 그러므로 플래시 메모리 기반의 효율적인 인덱스 설계나 질의 처리, 최적화를 위해서는 플래시 메모리에 적합한 비용 예측 방법이 필요하다. 본 논문의 목적은 플래시 메모리를 위한 파일 시스템인 플래시 전환 계층(Flash Translation Layer)을 기반으로 비용 예측 모델을 제시하는 것이다. 플래시 메모리의 저장 공간에서 데이터를 읽는 비용은 플래시 메모리의 하드웨어 특성으로부터 쉽게 유추될 수 있지만, 쓰기 비용의 경우 플래시 메모리에 대한 쓰기 작업이 초래하는 가비지 컬렉션 (Garbage Collection) 때문에 예측하기가 힘들다. 본 논문은 해당 파일 시스템으로부터 전체 플래시 메모리 공간 대비 유효 데이터의 사용률을 얻어낸 후 그 정보를 이용하여 가비지 컬렉션을 포함한 쓰기 비용을 예측하는 모델을 제안한다. 이러한 예측 모델을 사용하면 인덱스를 구성하거나 질의 처리 및 최적화 알고리즘을 구성하는데 있어 플래시 메모리의 특성을 반영한 비용 효율적인 설계를 수행할 수 있다.

PRMS: Page Reallocation Method for SSDs

이동현,노홍찬,박상현,Lee, Dong-Hyun,Roh, Hong-Chan,Park, Sang-Hyun Korea Information Processing Society 2010 정보처리학회논문지D Vol.17 No.6

Solid-State Disks (SSDs)는 빠른 접근 시간, 적은 전력소모, 전기 충격에의 내성과 같은 장점으로 인해 하드 디스크를 대체 할 것으로 기대되고 있다. 그러나 SSDs는 임의 쓰기(random write)로 인한 수명 단축이란 단점이 있으며 이는 SSDs 컨트롤러의 구조와는 별개로 나타나고 있다. SSDs와 관련한 기존 연구는 컨트롤러의 더 나은 디자인과 쓰기 연산의 감소에 주력하였다. 본 연구는 동시에 쓰여지는 경향이 있는 여러 데이터 페이지를 연속적인 블록에 배치하는 방법을 제시한다. 이 방식은 우선 특정 기한 동안 쓰기 연산에 대한 정보를 수집한 후 상기 쓰기 연산에 대한 정보를 트랜잭션화 하여 frequent itemset을 추출하고 이를 연속적인 블록에 재배치하는 과정으로 이루어진다. 또한 본 연구는 frequent itemset의 page를 재배치할 수 있는 알고리즘을 소개한다. TPC-C 기반 실험에 있어 본 연구가 제안한 재배치를 수행한 결과 저장 기기 접근 횟수를 평균 6 % 감소시킬 수 있었다. Solid-State Disks (SSDs) have been currently considered as a promising candidate to replace hard disks, due to their significantly short access time, low power consumption, and shock resistance. SSDs, however, have drawbacks such that their write throughput and life span are decreased by random-writes, nearly regardless of SSDs controller designs. Previous studies have mostly focused on better designs of SSDs controller and reducing the number of write operations to SSDs. We suggest another method that reallocates data pages that tend to be simultaneously written to contiguous blocks. Our method gathers write operations during a period of time and generates write traces. After transforming each trace to a set of transactions, our method mines frequent itemsets from the transactions and reallocates the pages of the frequent itemsets. In addition, we introduce an algorithm that reallocates the pages of the frequent itemsets with moderate time complexity. Experiments using TPC-C workload demonstrated that our method successfully reduce 6% of total logical block access.

임의쓰기 성능향상을 위한 로그블록 기반 FTL의 효율적인 합병연산

이준혁,노홍찬,박상현,Lee, Jun-Hyuk,Roh, Hong-Chan,Park, Sang-Hyun 한국정보처리학회 2012 정보처리학회논문지D Vol.19 No.2

최근 플래시 메모리의 꾸준한 용량 증가와 가격 하락으로 인해 대용량 SSD(Solid State Drive)가 점차 대중화 되고 있다. 하지만, 플래시 메모리는 하드웨어적인 제약사항이 존재하며, 이러한 제약사항을 보완하기 위해 FTL(Flash Translation Layer)이라는 특별한 미들웨어 계층을 필요로 한다. FTL은 플래시 메모리의 하드웨어적인 제약사항을 효율적으로 운용하기 위해 필요한 계층으로서 파일 시스템으로부터의 논리적 섹터 번호(logical sector number)를 플래시 메모리의 물리적 섹터 번호(physical sector number)로 변환해주는 역할을 한다. 특히, 플래시 메모리의 여러 제약사항 중 "쓰기 전 지우기(erase-before-write)"는 플래시 메모리 성능 저하의 주요한 원인이 되고 있으며, 이와 관련하여 로그블록 기반의 여러 연구들이 활발히 진행되어 왔지만, 대용량의 플래시 메모리를 효율적으로 운용하기 위해서는 몇몇 문제점들이 존재한다. 로그블록 기반의 FAST는 넓은 지역에 임의쓰기(random writing)가 빈번하게 발생하면 데이터 블록 내 사용되지 않은 섹터들로 인해 효율적이지 못한 합병 연산이 발생한다. 즉, 효율적이지 못한 블록 쓰레싱(thrashing)이 빈번하게 발생하고, 플래시 메모리의 성능을 저하시킨다. 로그블록은 덮어쓰기(overwriting) 발생 시 일종의 캐쉬처럼 운영되며, 이러한 기법은 플래시 메모리 성능 향상에 많은 발전을 주었다. 본 연구에서는 임의쓰기에 대한 성능 향상을 위해 로그 블록만을 캐쉬처럼 운영하는 것이 아니라 플래시 메모리 전체를 캐쉬처럼 운용하고, 이를위해 별도의 오프셋이라는 매핑 테이블을 운용하여 플래시 메모리 성능 저하의 주요한 원인이 되는 합병연산과 삭제연산을 줄였다. 새로운 FTL은 XAST(eXtensively-Associative Sector Translation)이라 명명하며, XAST에서는 공간지역성과 시간지역성에 대한 기본적인 이론을 바탕으로 오프셋 매핑 테이블을 효율적으로 운용한다. Recently, the flash memory consistently increases the storage capacity while the price of the memory is being cheap. This makes the mass storage SSD(Solid State Drive) popular. The flash memory, however, has a lot of defects. In order that these defects should be complimented, it is needed to use the FTL(Flash Translation Layer) as a special layer. To operate restrictions of the hardware efficiently, the FTL that is essential to work plays a role of transferring from the logical sector number of file systems to the physical sector number of the flash memory. Especially, the poor performance is attributed to Erase-Before-Write among the flash memory's restrictions, and even if there are lots of studies based on the log block, a few problems still exists in order for the mass storage flash memory to be operated. If the FAST based on Log Block-Based Flash often is generated in the wide locality causing the random writing, the merge operation will be occur as the sectors is not used in the data block. In other words, the block thrashing which is not effective occurs and then, the flash memory's performance get worse. If the log-block makes the overwriting caused, the log-block is executed like a cache and this technique contributes to developing the flash memory performance improvement. This study for the improvement of the random writing demonstrates that the log block is operated like not only the cache but also the entire flash memory so that the merge operation and the erase operation are diminished as there are a distinct mapping table called as the offset mapping table for the operation. The new FTL is to be defined as the XAST(extensively-Associative Sector Translation). The XAST manages the offset mapping table with efficiency based on the spatial locality and temporal locality.

SSD 플래시 변환 계층 상에서 논리 주소 매핑의 성능 향상을 위한 HAMM(Hybrid Address Mapping Method)

이지원,노홍찬,박상현,Lee, Ji-Won,Roh, Hong-Chan,Park, Sang-Hyun 한국정보처리학회 2010 정보처리학회논문지D Vol.17 No.6

최근 플래시 메모리 기반 SSD(Solid State Disks)는 데이터 처리 속도가 빠르고, 외부 충격에 강하며 전력소모가 작다는 우수한 특성과 함께 그 용량의 증가와 가격 하락으로 인하여 차세대 저장 매체로 부각되고 있다. 하지만 SSD는 하드디스크와는 달리 읽기, 쓰기 및 지우기의 단위 및 수행 시간이 다르며 덮어쓰기가 불가능하다는 특징이 있다. 이 때문에 SSD는 기존의 하드디스크 기반 시스템 상에서는 그 동작의 효율성이 떨어지며, 이를 보완하기 위해 플래시 변환 계층이 설계되었다. 본 논문에서는 플래시 변환 계층의 역할 중 하나인 논리 주소 매핑 기법을 개선하여 SSD의 성능을 높일 수 있는 HAMM(Hybrid Address Mapping Method)를 제안한다. HAMM은 기존에 존재하는 슈퍼 블록 매핑 기법과 블록 매핑 기법의 단점을 보완하고 장점을 살릴 수 있도록 설계된 논리 주소 매핑 기법이다. SSD 시뮬레이터를 제작하여 실험하였으며, 실험을 통하여 HAMM은 같은 크기의 쓰기 버퍼 상에서 슈퍼 블록 매핑 기법에 비해 SSD의 저장공간을 효율적으로 사용하는 것으로 나타났으며, 또한 블록 매핑 기법에 비해 매핑 테이블을 구성하는데 적은 양의 메모리를 사용하면서 비슷한 성능을 보이는 것으로 나타났다. Flash memory based SSDs are currently being considered as a promising candidate for replacing hard disks due to several superior features such as shorter access time, lower power consumption and better shock resistance. However, SSDs have different characteristics from hard disk such as difference of unit and time for read, write and erase operation and impossibility for over-writing. Because of these reasons, SSDs have disadvantages on hard disk based systems, so FTL(Flash Translation Layer) is designed to increase SSDs' efficiency. In this paper, we propose an advanced logical address mapping method for increasing SSDs' performance, which is named HAMM(Hybrid Address Mapping Method). HAMM addresses drawbacks of previous block-mapping method and super-block-mapping method and takes advantages of them. We experimented our method on our own SSDs simulator. In the experiments, we confirmed that HAMM uses storage area more efficiently than super-block-mapping method, given the same buffer size. In addition, HAMM used smaller memory than block-mapping method to construct mapping table, demonstrating almost same performance.

AS B-트리: SSD를 사용한 B-트리에서 삽입 성능 향상에 관한 연구

김성호,노홍찬,이대욱,박상현,Kim, Sung-Ho,Roh, Hong-Chan,Lee, Dae-Wook,Park, Sang-Hyun 한국정보처리학회 2011 정보처리학회논문지D Vol.18 No.3

최근 플래시 메모리 및 SSD가 노트북이나 PC의 저장장치로 사용되는 것뿐 아니라, 기업용 서버의 차세대 저장장치로 주목 받고 있다. 대용량의 데이터를 처리하는 데이터베이스에서는 삽입, 삭제, 검색을 빠르게 하기 위해 다양한 색인 기법을 사용하는데 그 중B-트리 구조가 대표적인 기법이다. 하지만 플래시 메모리 상에서는 하드디스크와 달리 덮어쓰기(overwrite) 연산을 수행하기 위해서는 먼저 해당 블록(block)에 대하여 플래시 메모리의 연산 중 가장 비용이 많이 요구되는 삭제(erase) 연산을 수행 해야만 한다. 이러한 문제점을 극복하기 위해 플래시 메모리 사이에 위치하는 플래시 변환 계층(Flash memory Translation Layer)을 사용한다. 이 플래시 변환 계층은 수정한 데이터를 동일한 논리 주소에 덮어쓰기를 하더라도 실제로 임의의 다른 물리 주소에 저장하도록 하여 이 문제를 해결할 수 있다. NAND 플래시 메모리를 배열 형태로 포함하고 있는 SSD는 한 개 이상의 플래시 메모리 패키지를 병렬로 접근할 수 있다. 이러한 병렬 접근 방식을 사용하여 쓰기 연산 성능을 향상하기 위해서는 연속한 논리 주소에 쓰기 연산을 요청하는 것이 유리하다. 하지만 B-트리는 구성 노드에 대한 삽입 삭제 연산 시에 대부분 연속되지 않은 논리 주소 공간에 대한 갱신 연산이 일어나게 된다. 따라서 SSD의 병렬 접근 방식을 최대한 활용할 수 없게 된다. 본 논문에서는 수정한 노드를 연속한 논리 주소에 쓰도록 하는 AS B-트리 구조를 제안하여 SSD의 병렬 접근 방식을 최대한 활용할 수 있도록 하였다. 구현 및 실험한 결과 AS B-트리에서의 삽입 시간이 B-트리보다 21% 개선된 것을 확인하였다. Recently flash memory has been being utilized as a main storage device in mobile devices, and flashSSDs are getting popularity as a major storage device in laptop and desktop computers, and even in enterprise-level server machines. Unlike HDDs, on flash memory, the overwrite operation is not able to be performed unless it is preceded by the erase operation to the same block. To address this, FTL(Flash memory Translation Layer) is employed on flash memory. Even though the modified data block is overwritten to the same logical address, FTL writes the updated data block to the different physical address from the previous one, mapping the logical address to the new physical address. This enables flash memory to avoid the high block-erase cost. A flashSSD has an array of NAND flash memory packages so it can access one or more flash memory packages in parallel at once. To take advantage of the internal parallelism of flashSSDs, it is beneficial for DBMSs to request I/O operations on sequential logical addresses. However, the B-tree structure, which is a representative index scheme of current relational DBMSs, produces excessive I/O operations in random order when its node structures are updated. Therefore, the original b-tree is not favorable to SSD. In this paper, we propose AS(Always Sequential) B-tree that writes the updated node contiguously to the previously written node in the logical address for every update operation. In the experiments, AS B-tree enhanced 21% of B-tree's insertion performance.

시간 기반 매크로어레이에서 쇄|일링 및 쉬프팅 패턴을 찾는 새로운 볍

이동현,윤영미,노홍찬,박상현,안재균 한국정보과학회 2008 데이타베이스 연구 Vol.24 No.3

시간 기반 마이크로어레이 데이터는 유전자 집합의 발현 정도를 일정한 시간간격으로 측정하여 수치화한 마이크로어레이 데이터를 뜻한다 시간 기반 마이크로 어레이 데이터를 기반으로 다른 유전자 집합을 활성(activation)화 시카거나 억제(inhihtion)시커는 유전자 집합을 찾아냄으로써 유전자 기능 네트워크를 효과적으로 구축 할 수 있 다. 본 논문에서는 유전자의 증감값을 특정 구간에 대하여 표준화하고 이를 통해 클러스터링과 클러스터 간 관계 도출을 동시에 해결 할 수 있는 알고리즘인PRCluster (Past Relatiγe Cluster)방법을 제시한다 PROuster를 검증하기 위해 효모 유전자의 시간 기반 마이크로어레이에서 클러스터를 생성하고 이 클러스터를 바탕으로 활성 관계 또는 억제 관계를 도출하였다. 실험 결과 찾아낸 클러스터 내 두 객체 간에는 선형적인 함수 관계가 있었다. 또한 마이크로어레이 데이터에 존재하는 오차를 허용함과 동시에 적절한 유사도를 지난 클러스터 간 활성 혹은 억제 관계를 도출함을 확인할 수 있었다 Time-based microarray data is gene expression data generated by measuring the expression value of genes having a certain time span. By means of finding the gene set which activates or inhibits another gene set, the gene function network can be discovered. In this paper, we propose the PR cluster method that clusters the set of genes and mines relations between the found clusters by standardizing gene expression and observing the overall pattern. To verify the PR cluster algorithm, we conducted experiments using time-based yeast microarray data. The experimental results demonstrated that the PR cluster algorithm finds clusters in each of which any two objects have a linear functional relation. Also the experimental results show that the PR cluster algorithm can figure out the relation between clusters with proper similarity and can handle the noise that exists in the microarray data.

그래프 기반 분산처리 시스템 트리니티를 이용한 서열 정렬 알고리즘

이준수,여윤구,노홍찬,윤영미,박상현 한국정보과학회 2014 데이타베이스 연구 Vol.30 No.1

Sequence alignment is one of the widely used tools in genomics. Recently, after NGS(NextGeneration Sequencing) technology was developed, the production of sequence read data increaseddramatically. A number of sequence alignment algorithms have been developed for processing theseNGS data. However, these algorithms are suffered from a trade-off between throughput andalignment quality, because there is a large computation cost for handling the repeat reads andpolymorphism. On the contrary, alignment algorithms with distributed system such as Hadoop andTrinity can obtain better throughput without compromising alignment quality than existingalgorithms on single machine. In this paper, we suggest SAG, sequence alignment algorithm basedon graph with in-memory distributed system, Trinity proposed by Microsoft. We transformedreference sequence into a graph form, and added new edge between adjacent node havingconnection possibility on graph. And we performed combination of sequence fragments in order tocandidates allowing polymorphism. Finally, we performed glocal alignment to find final results forthe obtained candidates. Our experimental results show that SAG better throughput with samequality or better quality than existing algorithms with Hadoop. We have also proved scalability thatwe obtained better throughput by simply adding machines. 유전체학(Genomics)에서 서열정렬은 가장 널리 사용된다. 차세대 시퀀싱(Next Generation Sequencing) 기술이 발전하면서, 최근 서열 리드 데이터의 양이 급격하게 증가했다. 급증한 차세대 시퀀싱 데이터를 처리하기 위한 서열정렬 알고리즘이 많이 개발되었다. 하지만 서열정렬 알고리즘들은 반복서열(repeat), 변이(polymorphism)를 처리하기 위해 많은 계산량을 요구한다. 그렇기 때문에 기존 서열정렬 알고리즘은 처리량(throughput)과 정렬품질(quality)사이에 트레이드오프(trade-off)가 존재한다. 하지만 분산처리 시스템Hadoop, Trinity에서 동작하는 정렬 알고리즘은 기존 싱글에서 동작하는 알고리즘에 비해 정렬 품질을 덜 희생하고, 더 높은 처리량을 얻을 수 있다. 본 논문에서는 Microsoft에서 제안한 그래프 기반 인-메모리(in-memory)분산시스템 트리니티(Trinity)에서 동작하는 서열정렬 알고리즘 SAG(Sequence Alignment Algorithm basedon Graph with Trinity)를 제안한다. 우리는 기존 참조 서열을 그래프 형태의 데이터로 변형 한 뒤, 그래프에서연결 가능한 인접한 노드에 새로운 간선을 추가했다. 그리고 변이(polymorphism)를 허용하는 정렬을 수행하기위해 서열조각들 사이의 조합을 통해 후보를 얻었다. 마지막으로 후보를 대상으로 glocal alignment를 수행해최종적인 결과를 찾았다. 실험을 통해 SAG는 기존 Hadoop에서 동작하는 알고리즘과 비교했을 때 비슷하거나더 좋은 정렬 품질조건과 동시에 상당히 높은 처리량을 얻었다. 또한 머신을 추가함으로써 더 좋은 처리량을 얻는확장성을 입증하였다.