초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

저전력 운전을 위해 정렬 알고리즘을 대상으로 알고리즘 복잡도와 에너지 소모 관련성을 분석하고 전력 효율을 향상시키도록 알고리즘을 수정 개발하여 실험하였다. 얻어진 결과는 향후 그린컴퓨팅 실현에 활용하고자 한다.

저전력 운전을 위해 정렬 알고리즘을 대상으로 알고리즘 복잡도와 에너지 소모 관련성을 분석하고 전력 효율을 향상시키도록 알고리즘을 수정 개발하여 실험하였다. 얻어진 결과는 향후 그린컴퓨팅 실현에 활용하고자 한다.

AI 본문요약

엑셀 다운로드 AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

• 연구 주제
• 연구 방법
• 연구 결과

문제 정의

• 컴퓨팅 분야에서도 에너지 사용량을 줄여 녹색 환경을 지키려는 노력의 일원으로 green computing이 강조되면서 종전의 최단시간에 주어진 계산을 완료하는 성능위주의 컴퓨팅 방식에서 저전력 컴퓨팅이 중요 설계 요구사항으로 등장하게 되었다 [1-3] 문헌[4]에 따르면 CPU 외에도 DRAM이 전력소모의 비중이 크고, 데이터 이동/접근의 빈도를 낮추는 것은 프로세서에서 연산횟수를 줄이는 것보다 훨씬 에너지 절감효과가 큰 것으로 알려져 있다. 이를 감안해서 전력 절감 컴퓨팅을 위한 기초연구로 핵심 연산인 정렬 알고리즘에 대한 실행시간 및 에너지/파워 소모와 그 효율을 분석한 연구결과를 보고한다.

제안 방법

• 허나 green computing 측면에서 에너지 소모 면에서 정렬연산의 복잡도 해석에 재검토가 필요하다. 이에 성능이 뛰어나고 복잡도가 O(NlogN)로 동일한 퀵정렬, 머지정렬, 힙정렬(quicksort, mergesort, heapsort)을 대표적으로 분석 실험하고 소요시간 및 소요 에너지를 측정하였다.
• 실험에는 저전력 노트북용에서부터 고사양 멀티코어 프로세서를 탑재한 경우를 포함시켰다. 또한 병렬처리에 의한 정렬 효과를 확인하기 위해 PSRS(parallel sort by regular sampling) [5]을 멀티코어 프로세서에서 실험하였다. 사용한 컴퓨터의 상세사양을 표1에 보인다.
• 퀵정렬은 재귀적 진행과정에서 피봇(pivot)을 기준으로 균등하게 분할(partition)될수록 성능향상 및 에너지 소모가 감소한다. 하지만 적절한 피봇을 찾기 어렵기 때문에 본 연구에서는 PSRS에서의 샘플기법을 도입하여 분할의 균등성을 향상시켰다. 저전력 퀵정렬 (Energry-aware quicksort)은 초기 수 단계 동안 피봇산출에 공들여 다음과 같이 진행된다.
• green computing 실현을 위한 초기연구로 정렬알고리즘을 검토 수정하여 실험하였다. 퀵정렬의 분할과정을 개선하여 절전효과를 얻었고, 그 원리는 일반적인 알고리즘 설계에 적용될 수 있다.

대상 데이터

• 다양한 CPU 플랫폼의 전력소모특성을 확인하기 위해 Intel의 고성능 마이크로프로세서부터 저전력용 넷북 컴퓨터까지 대표적인 CPU에서 실험하였고, 무작위로 생성된 정수를 10M개 (M=2²⁰)부터 주 메모리가 포화될 때 까지(160M) 실험하였다. 실험에는 저전력 노트북용에서부터 고사양 멀티코어 프로세서를 탑재한 경우를 포함시켰다.
• )부터 주 메모리가 포화될 때 까지(160M) 실험하였다. 실험에는 저전력 노트북용에서부터 고사양 멀티코어 프로세서를 탑재한 경우를 포함시켰다. 또한 병렬처리에 의한 정렬 효과를 확인하기 위해 PSRS(parallel sort by regular sampling) [5]을 멀티코어 프로세서에서 실험하였다.
• 특히 고성능프로세서에서는 내부 산술연산 비용/시간에 비해 메모리 접근/(특히 쓰기동작)에 수십내지 수백배의 지연이 있게되어(T_s ≫ T_C)[6], 알고리즘에서 얼마나 많은 계산(산술연산 등)을 줄이는가 보다 swap 횟수를 얼마나 줄이는가가 전체 실행시간과 전력소모량을 절감하는가의 관건이 된다. 실험적으로도 보면, 데이터규모가 커질수록 머지정렬이 퀵정렬에 비해 소요시간이 매우 커지게 되어 퀵정렬의 에너지 절감법을 연구대상으로 한다

성능/효과

• 단 효율 면에서는 사용한 CPU 타입에 따라 각기 다른 특성을 보인다. 동일한 프로세서에서는 퀵정렬, 머지정렬, 힙정렬 순으로 에너지 효율이 좋은 것으로 관측되었고, 데이터 규모가 커질수록 에너지 효율이 증가했다. 비록 최악의 시간 복잡도는 동일하지만 연산횟수는 물론 메모리 사용 정도, 캐쉬 적중률 등이 달라 차이를 보이므로 향후 에너지 최적화에 중요한 고려대상이 된다.
• 실험적으로는 위 방식을 레벨 5까지 적용한 결과 표2와 같이 최대 6% 정도의 실행시간 단축효과와 에너지 절약효과를 얻었다.

후속연구

• 동일한 프로세서에서는 퀵정렬, 머지정렬, 힙정렬 순으로 에너지 효율이 좋은 것으로 관측되었고, 데이터 규모가 커질수록 에너지 효율이 증가했다. 비록 최악의 시간 복잡도는 동일하지만 연산횟수는 물론 메모리 사용 정도, 캐쉬 적중률 등이 달라 차이를 보이므로 향후 에너지 최적화에 중요한 고려대상이 된다. 프로세서별로는 최근의 고성능 CPU일수록 계산성능은 좋아지지만, 에너지 효율 면으로는 노트북/모바일용 CPU 칩을 장착한 시스템이 효율이 높이 관찰되는 것은 예측 가능 한 사실이다.
• 퀵정렬의 분할과정을 개선하여 절전효과를 얻었고, 그 원리는 일반적인 알고리즘 설계에 적용될 수 있다. 한편, 추후 병렬알고리즘으로 확장하여 절감효과를 극대화할 계획이다. 적용 알고리즘의 전력소모에 대한 해석적 모델링이 향후 과제이다.

본문요약 정보가 도움이 되었나요? 예 아니오 제출

이 논문을 인용한 문헌

더보기