초고속 영상 신호 처리기를 위한 짧은 임계 경로를 가지는 데이터 정렬 알고리즘 (Data Sorting Algorithm with a Short Critical Path for Very High-Speed Image Signal Processor)

서지정보

· 발행기관 : 한국정보기술학회
· 수록지 정보 : 한국정보기술학회논문지 / 12권 / 2호 / 55 ~ 60페이지
· 저자명 : 박현상

초록

거품 정렬 알고리즘은 데이터들을 내림차순으로 정렬하기 위한 것이며, 다양한 영상 처리 알고리즘을 구동하는 영상 처리 신호기에서는 보편적으로 요구되는 기능이다. 특히 특정 영상 영역의 최대값, 최소값, 중간값 등을 동시에 계산할 경우에는 거품 정렬 알고리즘의 적용이 가장 효과적이다. 그러나 거품 정렬은 정렬해야할 데이터 개수가 늘어나면 제곱으로 계산량이 늘어나므로, 영상에 적용할 경우, 효과적인 구현이 용이하지 않다. 또한 순차적인 비교연산이 늘어남에 따라 하드웨어의 임계 경로도 늘어나므로, 초고속 동작에 적합하지 않다. 본 논문에서는 임계 경로를 최소화할 수 있는 새로운 정렬 알고리즘을 제안한다. 제안한 알고리즘은 모든 비교 연산을 동시에 계산하고, 계산된 결과를 효과적으로 활용한다. 5×5 영상 데이터에 대해서 구현된 결과는 84%의 임계경로 감소 및 35%의 하드웨어 비용이 감소를 보였다.

영어초록

Bubble sorting algorithm is to sort the data in a descending order and is popularly used inside image signal processors that drive a variety of image processing algorithms. Most of all to get the maximum, the minium, and the median of an image segment at the same time, it is most desirable to use the bubble sorting algorithm. For image processing applications, however, the larger image segment makes it more difficult to implement it efficiently, since the operations are increased by the squares of the number of data. As the sequential comparison operations are increased and the critical path is also increased, such that it is unsuitable in a very high speed operation. In this paper, we propose a new sorting algorithm to minimize the critical path. The proposed algorithm calculates all necessary comparisons in parallel, and then effectively utilize the results for sorting. The implementation result for 5x5 image segment showed the critical path reduction of 84% and the hardware cost reduction of 35%.

참고자료

· 없음