디지털 라이브러리[ 검색결과 ]
매니코어 파티셔닝을 위한 동적 코어 친화도
http://doi.org/10.5626/JOK.2020.47.12.1111
기존 운영체제는 NUMA 기반 컴퓨터 시스템에서 코어 수가 점점 많아지면서 확장성 문제를 보이고 있다. 매니코어 시스템이 보이는 확장성 문제의 원인으로는 캐시 미스, 캐시 일관성 활동, 동기화 등이 있고, 이를 해결하기 위해 시스템 호출과 이벤트 핸들러에 친화도를 적용하여 특정 코어 집합 에서 동작하도록 만드는 연구들이 진행되었다. 하지만 코어 파티셔닝과 같은 기존 연구들에서 친화도를 적용하는 코어의 수는 경험적인 값으로 결정되고, 한번 결정된 코어 집합은 응용이나 시스템이 달라져도 변하지 않는다는 한계가 존재한다. 이러한 한계 때문에 기존 연구들은 해당 코어들의 사용량이 적거나 많을 때 코어 자원을 비 효율적으로 사용하게 된다. 본 논문에서는 이러한 한계를 극복하고자 동적 코어 친화도 기법을 제안하고 기존 연구와 비교한다.
Effective Parallel LiDAR Triangulated Irregular Network Construction Method Using Convex Boundary Triangle
Permata Nur Rizki, Sangyoon Oh
http://doi.org/10.5626/JOK.2018.45.8.761
TIN(Triangulated Irregular Network) 모델은 연속 삼각형들로 정보를 표현하는 모델로서, 측정된 점 데이터로부터 지표면을 표현하는데 보편적으로 사용되는 그리드 모델 대비 해상도와 유연성 측면에서 강점을 가지고 있어서 최근 다양한 디지털 지도를 생성하는데 사용되고 있다. 그러나, TIN 모델을 생성하기 위해서는 많은 양의 반복 계산이 필요하며, 따라서 LiDAR 데이터와 같이 대용량 센싱 정보로부터 TIN을 생성하는 데에는 일반적인 순차방식 대비 보다 효과적인 처리 방안이 필요하다. 본 연구에서는 Convex Boundary Triangle을 사용하여 병렬 처리를 위한 효과적인 data decomposition을 수행하고, MapReduce 병렬 처리 방식을 사용해서 TIN을 생성하는 방안을 소개한다. 본 제안방식은 convex boundary 정보에 따른 데이터분할, Delaunay 특성 만족 검증, 그리고 merge 단계로 이루어져 있으며, 제안 방식의 성능 검증을 위해서 Apache Spark 플랫폼 기반으로 알고리즘을 구현하였다. 처리 성능과 확장성 관련 실험을 통해 본 제안 방식이 기존 방식 대비 merging 처리 시간을 평균 16.2% 줄였음을 확인하였다.
주제 추출을 위한 맵리듀스 기반의 사전확률 최적화 알고리즘
http://doi.org/10.5626/JOK.2018.45.5.478
대용량 테스트 문서에서 의미 있는 정보를 찾기 위한 다양한 주제 추출 알고리즘이 사용되고 있다. 주제 추출 알고리즘은 베이지안(Bayes) 확률 모델을 사용하기 때문에 사전확률 α와 β가 입력으로 주어져야 한다. 기존에는 주제 추출 알고리즘을 사용하기 위해 기본(default) 사전확률을 사용하거나, 주관적으로 그 값을 결정하였다. 본 연구에서는 주제 추출 알고리즘의 사전확률을 자동으로 결정해주는 맵리듀스 기반의 알고리즘을 제안하고 대용량 데이터에 대한 성능과 정확도를 크게 향상시켰다. 기존의 단일 쓰레드 알고리즘과 다르게, 제안된 맵리듀스 알고리즘은 입력된 데이터에 적합한 사전확률을 빠르게 찾고 주제 추출 알고리즘을 실행하여 정확한 주제를 추출할 수 있다. 본 연구의 실험 결과에 따르면, 제안 방안은 주제일관성과 성능 측면에서 기존 방안보다 우수함을 나타낸다.
2-계층 그리드 블록을 이용한 효과적인 맵리듀스 기반 스카이라인 질의 처리 기법
http://doi.org/10.5626/JOK.2017.44.6.613
스카이라인 질의는 사용자들의 다양한 기준을 만족하는 데이터를 찾기 때문에 의사 결정 문제 등에서 폭넓게 사용되고 있다. 최근의 스카이라인 질의는 대용량 데이터베이스 처리를 위해 맵리듀스 프레임워크를 사용하는 연구들이 많이 진행되었으며 특히 맵리듀스에 기존의 색인 구조를 적용하는 방식으로 연구가 활발히 진행되고 있다. 스카이라인의 특징 중 하나는 원점에서 가까운 데이터일수록 더 많은 영역을 지배한다는 점이다. 하지만 기존의 색인 구조는 이와 같은 스카이라인의 특징을 반영하지 못하는 단점이 있었다. 본 논문에서는 그리드의 셀들을 스카이라인의 특징을 고려하여 묶는 그리드 블록 구조와 원점과 가까운 데이터가 없을 때도 사용 가능한 2계층 그리드 블록 구조, 그리고 2계층 그리드 블록 구조를 사용한 효율적인 스카이라인 질의 기법을 제안하였다.
분산 테라스케일 텐서 생성기
많은 종류의 데이터들은 텐서로 표현될 수 있다. 텐서란 다차원 배열을 의미하며, 그 예로 (사용자, 사용자, 시간)으로 이루어진 소셜 네트워크 데이터가 있다. 이러한 다차원 데이터 분석에 있어서 텐서 생성기는 시뮬레이션, 다차원 데이터 모델링 및 이해, 샘플링/외삽법 등 다양한 응용이 가능하다. 하지만, 존재하는 텐서 생성기들은 실제 세계의 텐서처럼 멱 법칙을 따르는 특성과 희박성을 갖는 텐서를 생성할 수 없다. 또한, 처리가능한 텐서 크기에 한계가 존재하고, 분산시스템에서 추가 분석을 하려면 텐서를 분산시스템에 업로드 하는 추가비용이 든다. 본 논문은 분산 테라스케일 텐서 생성기(TeT)를 제안함으로써 이러한 문제를 해결하고자 한다. TeT는 희박성을 갖는 랜덤 텐서와 희박성과 멱 법칙을 따르는 특성을 갖는 Recursive-MATrix 텐서, 크로네커 텐서를 크기 제한없이 생성할 수 있다. 또한, TeT에서 생성된 텐서는 같은 분산 시스템에서 추가적인 텐서분석이 가능하다. TeT는 효율적인 설계로 인해 거의 선형적인 머신확장성을 보인다.
클라우드에서 SPARQL 질의 처리를 위한 조인 성능 향상
최근 LOD 데이터의 급격한 증가로 인해 기존의 싱글 머신 시스템을 통한 대량의 LOD 처리는 성능의 한계를 가진다. 이러한 문제를 해결하기 위해 최근 연구들은 분산, 병렬 프레임워크인 맵리듀스를 활용한다. 하지만 맵리듀스를 통해 SPARQL 질의를 처리하기 위해서는 다수의 맵리듀스 잡이 필요하고, 이로 인해 추가적인 비용이 발생하게 된다. 또한, 조인을 위해 불필요한 데이터를 처리해야 하는 문제가 있다. 본 논문에서는 이를 해결하기 위해 SPARQL 질의 처리 시 발생하는 맵리듀스 잡의 개수를 줄이고 Bitmap을 기반으로 조인 인덱스를 작성 후 이용하여 불필요한 데이터 처리를 최소화 하는 방법을 제안한다.
그리디 알고리즘을 이용한 맵리듀스 세타조인 M-Bucket-I 휴리스틱의 개선
세타조인은 데이터베이스에 있어서 가장 기본적이면서도 중요한 질의 중 하나이다. 최근 처리해야 하는 데이터의 양이 증가함에 따라, 맵리듀스와 같은 분산 병렬 처리 프레임워크를 사용한 데이터베이스의 질의처리가 많이 연구되고 있다. 대표적인 연구로 M-Bucket-I 휴리스틱을 이용한 세타조인이 있으나, 이 알고리즘은 수행시간이 입력 데이터의 크기를 n이라 할 때, 각 레코드를 rmax개의 리듀서 중 어느 리듀서로 보낼지 정하는 리듀서맵핑을 구하는데 O(n) 의 시간이 걸려 쉽게 사용할 수 없다는 문제가 있다. 본 논문에서는 기존의 M-Bucket-I 휴리스틱을 개선하여, 같은 리듀서 매핑 결과를 내놓더라도 수행시간이 O(r maxlogn으로 보다 짧은 새로운 알고리즘을 제시한다. 다양한 실험을 통하여 기존의 맵리듀스를 이용한 세타조인보다 성능을 10% 정도 향상시킬 수 있음을 보였다.
MapReduce 기반 분산 이미지 특징점 추출을 활용한 빠르고 확장성 있는 이미지 검색 알고리즘
IoT 시대를 맞아 모바일 기기의 급격한 성능 향상에 힘입어 폭발적으로 증가하는 멀티미디어 빅데이터의 빠른 처리가 요구되고 있다. 하지만, 이런 환경의 대격변 속에서도 이미지 검색 연구 분야에서는 정확도 향상에 주로 초점을 맞춘 나머지, 고해상도 멀티미디어 데이터 Query에 대한 빠른 처리 측면에서는 제대로 대응하지 못하고 있다. 이에 우리는 이미지 검색만을 분산화한 선행연구와 달리 MapReduce 기반 분산 이미지 특징점 추출 기법을 활용하여 정확도는 유지하면서 빠른 응답시간을 확보하며, BIRCH 인덱싱을 기반으로 메모리 확장성까지 해결한 새로운 분산 이미지 검색 알고리즘을 제안한다. 그리고 제안하는 분산 이미지 검색 알고리즘의 정확도, 처리시간, 확장성에 대한 실험을 통해 뛰어난 성능을 확인한다.
맵리듀스를 이용한 그리드 기반 인덱스 생성 및 k-NN 조인 질의 처리 알고리즘
맵리듀스는 대용량 데이터 처리를 위한 시스템 안정성과 유용성을 제공한다. 맵리듀스 기반 k-최근접점 조인 질의처리 알고리즘은 두 데이터 집합 R과 S를 기반으로 R의 모든 레코드에 대해 S의 데이터 중 가장 인접한 k개의 레코드를 탐색하는 알고리즘으로써, 대용량 데이터 분석을 위한 중요한 질의 처리 알고리즘이다. 그러나 기존 k-최근접점 조인 질의처리 알고리즘은 높은 인덱스 구축비용 문제로 인해 대용량 데이터 처리에 적합하지 않은 문제점을 지닌다. 따라서, 본 논문에서는 그리드 기반 인덱스 생성 및 k-최근접점 질의 처리 알고리즘을 제안한다. 제안하는 기법은 질의 셀로부터 인접한 데이터만을 찾아 맵리듀스 테스크에 전송함으로써 데이터 전송 및 k-최근접점 연산 오버헤드를 줄인다. 성능평가를 통해, 제안하는 기법이 정확 매칭 질의를 제공하는 동시에 기존 기법에 비해 질의 처리 시간 측면에서 최대 7배의 성능을 개선함을 보인다.
분산 메모리 시스템에서의 SPARQL 질의 처리
본 논문에서는 functional 프로그래밍과 분산 메모리 환경인 Spark를 통해 SPARQL 질의문 처리의 오버헤드를 줄일 수 있는 방법을 제안한다. 최근 몇 년간 시멘팁웹의 RDF 온톨로지 데이터는 폭발적으로 증가하고 있기 때문에, 대용량 온톨로지 데이터에 대한 질의문을 효율적으로 처리할 수 있는 방법이 주요 쟁점으로 떠오르고 있다. SPARQL 질의문 처리에 대한 기존의 연구들은 하둡의 맵리듀스 프레임워크에 초점을 맞추고 있다. 그러나 하둡은 분산 파일 처리를 기반의 작업을 수행하므로 성능 저하가 발생할 수 있다. 따라서 질의문 처리 속도를 향상 시키기 위해 본 논문에서는 분산 메모리 시스템을 통해 질의문을 처리할 수 있는 방법을 제안한다. 또한 SPARQL 질의어 사이의 Binding 값을 Propagation하기 위해서 Spark의 Join방식, Functional 프로그램의 Map, Filter 방식, Spark의 캐시 기능을 활용 하는 방식을 제안하고 있다. 본 논문의 실험 결과는 다른 기법들과 비교하여 높은 성능을 얻었다. 특히 현재 가장 빠른 성능을 보이는 SPARQL 질의 엔진인 Sempala와 유사하다는 결과를 얻었다.
