[논문]플래시 디스크 기반 행렬전치 알고리즘 심층 분석 및 성능개선

이형봉; 정태윤

doi:10.14372/iemek.2017.12.6.377

플래시 디스크 기반 행렬전치 알고리즘 심층 분석 및 성능개선
In-depth Analysis and Performance Improvement of a Flash Disk-based Matrix Transposition Algorithm 원문보기

대한임베디드공학회논문지 = IEMEK Journal of embedded systems and applications, v.12 no.6, 2017년, pp.377 - 384

이형봉 (Gangneung-Wonju National University) , 정태윤 (Gangneung-Wonju National University)

Abstract ▼ AI-Helper

The scope of the matrix application is so broad that it can not be limited. A typical matrix application area in computer science is image processing. Particularly, radar scanning equipment implemented on a small embedded system requires real-time matrix transposition for image processing, and since its memory size is small, a general matrix transposition algorithm can not be applied. In this case, matrix transposition must be done in disk space, such as flash disk, using a limited memory buffer. In this paper, we analyze and improve a recently published flash disk-based matrix transposition algorithm named as asymmetric sub-matrix transposition algorithm. The performance analysis shows that the asymmetric sub-matrix transposition algorithm has lower performance than the conventional sub-matrix transposition algorithm, but the improved asymmetric sub-matrix transposition algorithm is superior to the sub-matrix transposition algorithm in 13 of the 16 experimental data.

주제어

AI 본문요약
AI-Helper

문제 정의

이 연구에서는 SSD, USB, HDD 등 블록 저장 장치에 저장된 대규모 정방행렬을 전치하는 알고리즘 [7]을 리눅스 운영체제 환경에서 심층 분석하고 성능 개선을 모색한다. 이를 위하여 Ⅱ 장에서 운영체제의 블록장치 입·출력 관리가 어떻게 이루어지는지를 살펴보고, Ⅲ 장에서 일반적인 디스크 행렬전치 알고리즘들을 고찰한다.

제안 방법

AM 알고리즘의 성능 향상을 위한 또 다른 시도로서 부분행렬 단위를 제외한 나머지 부분을 행 기반으로 하나씩 처리하지 않고, 그림 12와 같이 가상 부분행렬로 확장하여 묶음 처리하는 방안을 제시한다. 이 방안을 따르면 연속된 디스크의 인접 데이터 접근 빈도를 높일 수 있다.
그림 7, 8의 부분행렬 기반 디스크 행렬전치는 대각선상에 위치한 부분행렬 전치 시 한 쪽 버퍼를 활용하지 못하는 단점이 있다. 이를 보완하기 위해[7]은 버퍼를 반으로 나누어 대칭 관계에 있는 두 부분 행렬에 분배하는 대신, 대각선상의 부분행렬에는 전체 버퍼를 할당하는 방안을 제시하였다. 이렇게 하면 대각선상의 부분 행렬들은 버퍼 전체를 모두 활용한다.

대상 데이터

버퍼 단위 묶음 입·출력의 효과를 확인하기 위해 위 세 가지 유형의 알고리즘에 대한 성능을 비교한다. 이 논문의 실험 환경은 표 2와 같고, 디스크로는 USB 메모리 형태의 8GB 이동식 플래시 디스크를 사용하면서 임베디드 리눅스와 유사하게 최소한의 버퍼 캐시를 사용하도록 쓰기 캐싱을 오프 (off)로 설정하였다 [15]. 테스트 데이터로는 1K×1K~8K×8K의 정수 정방 행렬을 n2K2 형태의 표기로 사용하고, 버퍼는 4K ~ 32K의 크기를 사용한다.

데이터처리

버퍼 단위 묶음 입·출력의 효과를 확인하기 위해 위 세 가지 유형의 알고리즘에 대한 성능을 비교한다. 이 논문의 실험 환경은 표 2와 같고, 디스크로는 USB 메모리 형태의 8GB 이동식 플래시 디스크를 사용하면서 임베디드 리눅스와 유사하게 최소한의 버퍼 캐시를 사용하도록 쓰기 캐싱을 오프 (off)로 설정하였다 [15].

이론/모형

원소 기반 접근법은 그림 3과 같이 파일개방 절차를 제외하고는 메모리 행렬전치 알고리즘과 동일하다. 즉, 간단하고 별도의 버퍼를 요구하지는 않지만 운영체제의 버퍼 캐시에 대한 부담이 크다.

성능/효과

그 원인 분석을 토대로, 부분행렬 크기의 짝수화와 부분행렬 단위를 벗어난 나머지 부분에 대한 가상 부분행렬 처리 등 두 가지 개선점을 제시하였다. 그 개선 결과 모든 경우에서 개선 전 비대칭 부분행렬전치 알고리즘보다 우수하고, 16가지 실험 데이터 중 13가지에서 기존의 부분행렬전치 알고리즘보다 우수함을 확인하였다. 향후, 플래시 디스크에 특화된 운영체제 디스크 버퍼 캐시 전략을 고려한 또 다른 개선점을 발견할 수 있을 것으로 기대된다.
그림 10은 표 3에서와 마찬가지로 버퍼 크기 12K일 때 네 가지 정방 디스크 행렬에 대한 부분행렬 기반 (SM: Sub-matrix)과 비대칭 부분행렬기반 (AM: Asymmetric sub-matrix) 알고리즘의 전치 성능 비교인데, 발표된 AM 알고리즘의 성능이 기존의 SM 알고리즘보다 오히려 더 좋지 않음을 보이고 있다.
이 논문에서는 최근에 발표된 디스크 비대칭 부분행렬전치 알고리즘의 성능을 분석하고 개선하였다. 분석결과 비대칭 부분행렬전치 알고리즘은 기존의 부분행렬전치 알고리즘보다 성능이 높지 않다는 의외의 결과가 나타났다. 그 원인 분석을 토대로, 부분행렬 크기의 짝수화와 부분행렬 단위를 벗어난 나머지 부분에 대한 가상 부분행렬 처리 등 두 가지 개선점을 제시하였다.

후속연구

그 개선 결과 모든 경우에서 개선 전 비대칭 부분행렬전치 알고리즘보다 우수하고, 16가지 실험 데이터 중 13가지에서 기존의 부분행렬전치 알고리즘보다 우수함을 확인하였다. 향후, 플래시 디스크에 특화된 운영체제 디스크 버퍼 캐시 전략을 고려한 또 다른 개선점을 발견할 수 있을 것으로 기대된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	일반적인 행렬 연산은 어디에서 이뤄지는가?	일반적인 행렬 연산은 프로그래밍 언어가 지원하는 2차원 배열 즉, 메모리 공간에서 이루어진다. 특히 행렬의 전치는 선형대수의 가장 기본적인 연산 중의 하나로서 응용분야가 넓고 그 기본 알고리즘은 이미 널리 알려져 있다.
	행렬전치가 필요한 연산은 무엇인가?	행렬전치는 이미지 처리를 위한 2차원 디지털 필터 (2D Digital Filter)나 2차원 푸리에 변환(2D-FFT: 2D Fast Fourier Transforms) 등에 필요한 연산이다. 특히 합성 개구 레이더 (SAR:Synthetic Aperture Radar) [4] 나 무인 항공기(UAV: Unmanned Aerial Vehicle) [5], 그리고 기상 예보 영역 [6]에서는 촬영된 대규모 영상 데이터에 대한 실시간 처리가 필수적이어서 효과적인 디스크 전치 알고리즘이 요구된다 [7].
	버퍼 캐시의 가장 큰 문제점인 불결 블록이 존재한 상태에서 발생하는 메모리 미싱 현상을 보완하기 위해 운영체제는 무엇을 하는가?	버퍼 캐시의 가장 큰 문제는 디스크에 업데이트되지 않은 불결 (dirty block) 블록이 존재하는 상태에서 단전 등 시스템 고장이 발생하면 그 때까지의 수정내용이 사라진다는 점이다. 이를 보완하기 위해 운영체제는 기회가 있을 때마다 디스크에 출력하는 지연 쓰기 (delayed write) 전략을 도입한다. 따라서 디스크 입·출력 어플리케이션은 지연 쓰기가 이루어지기 전에 해당 블록에 대한 쓰기를 마치는 것이 성능 관점에서 유리하다.

참고문헌 (15)

R.A. Na'mneh, W.D. Pan, S.M. Yoo, "Efficient Adaptive Algorithms for Transposing Small and Large Matrices on Symmetric Multiprocessors," Informatica, Vol. 17, No. 4, 535. pp. 535-550, 2006.
J.C. Bowman, M. Roberts, "Adaptive Matrix Transpose Algorithms for Distributed Multicore Processors," Proceedings of Applied Mathematics, Modeling and Computational Science, Vol. 117, pp. 97-103, 2015.
S. Huanghui, W. Zhensong1, Z. Weimin, “An Efficient Memory Access Strategy for Transposition and Block Operation in Image Processing,” Journal of Computer Research and Development, Vol. 50, No. 1, pp. 188-196, 2013.
K.Y. Kwak, "Trend of SAR Technology," Journal of the Korean Institute of Electromagnetic Engineering and Science, Vol. 22, No. 6, pp. 4-16, 2011 (in Korean).
K.S. Chung, Y.S. Kim, S.Y. Oh, "Development of a Flood Damage Assessment Technology using UAV," Journal of Korea Water Resources Association, Vol. 48, No. 1, pp. 51-59, 2015 (in Korean).
J.G. Park, "Storage Format of Domestic Weather Radar Raw Data," Proceedings of 2015 Korean Meteorological Society Conference, pp. 34-35, 2012 (in Korean).
S.C. Kim, W.K. Park, B.W On, I. Lee, G.S. Choi, "An Asymmetry Matrix Transposition Scheme Based on NAND Flash Memory," IEMEK J. Embed. Sys. Appl., Vol. 10, No. 21, pp.81-89, 2015 (in Korean).
https://en.wikipedia.org/wiki/Data_buffer, https://en.wikipedia.org/wiki/Cache_(computing)
A. Silberschatz, P. B. Galvin, G. Gagne, "Operating System Concepts," 9th Ed., pp. 565-612, Wiley, 2013.
https://unix.stackexchange.com/questions/253816/restrict-size-of-buffer-cache-in-linux
S.W. Lee, D.J. Park, T.S. Chung, D.-H.Lee, S. Park, H.J. Song, “A log Buffer Based Flash Translation Layer Using Fully Associative Sector Translation,” ACM Transactions on Embedded Computng Systems, Vol. 6, No. 3, pp. 436-453, 2007.
H.S. Lee, H.S. Yun, D.H Lee, “HFTL: Hybrid Flash Translation Layer Based on hot Data Identification for Flash Memory,” IEEE Transactions on Consumer Electronics, Vol. 55, No. 4, pp. 2005-2011, 2009.

상세보기
S. Kim, T. Kim, "A Write Buffer Management Scheme Considering the Command Queue in SSD," Journal of KIISE Vol. 39, No. 1A, pp. 313-315, 2012 (in Korean).
http://standards.ieee.org/develop/wg/POSIX.html
http://www.thewindowsclub.com/enable-disable-disk-write-caching-windows-7-8

저자의 다른 논문 :

원문 URL 링크

DOI : 10.14372/IEMEK.2017.12.6.377 [무료]
대한임베디드공학회 : 저널
Korea Open Access Journals : 저널
AccessON : 저널

*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.

오픈액세스(OA) 유형

BRONZE

출판사/학술단체 등이 한시적으로 특별한 프로모션 또는 일정기간 경과 후 접근을 허용하여, 출판사/학술단체 등의 사이트에서 이용 가능한 논문

이 논문과 함께 이용한 콘텐츠

저작권 관리 안내

내보내기 메뉴

내보내기 구분

파일저장
인쇄
메일전송

구성항목

기본정보
상세정보

관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관

저장형식

Text(ASCII format)
Excel format
RefWorks Direct Export
RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley

메일정보

받는사람 (필수): @
보내는사람 (선택): @
제목
내용: KISTI 검색결과 이메일 서비스

안내

총 건의 자료가 검색되었습니다.

다운받으실 자료의 인덱스를 입력하세요. (1-10,000)

검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다.

데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요)

다운로드 파일은 UTF-8 형태로 저장됩니다.
파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오.

Text(ASCII format)
Excel format

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

AI-Helper ※ AI-Helper는 을 사용합니다.

AI-Helper

안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

연합인증