DSP용 코드 생성에서 주소 포인터 할당 성능 향상 기법 = Improvement of Address Pointer Assignment in DSP Code Generation

국문 초록 (Abstract)

DSP에서 제공되는 주소 생성 유닛은 데이터 패스와 병렬적으로 주소 연산을 수행할 수 있게 해 줌으로써, DSP 코드 생성에 중요한 역할을 한다. 프로그램 변수들의 메모리 레이아웃을 결정하는 문제는 주소 생성 유닛의 기능을 이용하여 주소 연산용 명령어를 줄이는 최적화이다. 메모리 레이아웃 생성 단계와 주소 포인터 할당 단계로 구분 되는 이 최적화에서 본 논문은 주소 연산 코드의 수가 최소가 되도록 DSP용 코드 생성의 효과적인 주소 포인터 할당 문제를 다룬다. 제안하는 알고리즘은 고정된 메모리 레이아웃을 가질 때 주소 포인터 할당을 수행하는 기존의 알고리즘의 시간 복잡도를 줄이는 기법이다. 메모리크기와 수행 시간을 줄이기 위해 알고리즘을 수행할 때 핵심적인 요소들만을 고려하도록 강한 가지치기 방법을 사용하였다. 또한 주소 포인터 할당 문제는 메모리 레이아웃에 영향을 크게 받는 문제이기 때문에 본 논문은 주어진 메모리 레이아웃을 갱신하여 반복적으로 성능을 개선하는 방법을 제안한다. 약 3,000여개의 실제 프로그램으로부터 얻은 변수 접근 시퀀스를 제공하는 OffsetStone 벤치마크를 이용한 실험결과를 통해 본 논문에서 제안한 기법과 알고리즘을 테스트 했다. 제안한 방법은 전통적인 방법보다 평균 25.9%의 적은 주소 코드를 생성해 냄을 보인다.

다국어 초록 (Multilingual Abstract)

Exploitation of address generation units which are typically provided in DSPs plays an important role in DSP code generation since that perform fast address computation in parallel to the central data path. Offset assignment is optimization of memory layout for program variables by taking advantage of the capabilities of address generation units, consists of memory layout generation and address pointer assignment steps. In this paper, we propose an effective address pointer assignment method to minimize the number of address calculation instructions in DSP code generation. The proposed approach reduces the time complexity of a conventional address pointer assignment algorithm with fixed memory layouts by using minimum cost-nodes breaking. In order to contract memory size and processing time, we employ a powerful pruning technique. Moreover our proposed approach improves the initial solution iteratively by changing the memory layout for each iteration because the memory layout affects the result of the address pointer assignment algorithm. We applied the proposed approach to about 3,000 sequences of the OffsetStone benchmarks to demonstrate the effectiveness of the our approach. Experimental results with benchmarks show an average improvement of 25.9% in the address codes over previous works.

목차 (Table of Contents)

• 요약
• Abstract
• Ⅰ. 서론
• Ⅱ. 주소 할당 문제
• Ⅲ. 제안하는 알고리즘
• Ⅳ. 실험 결과
• Ⅴ. 결론
• 참고문헌
• 저자소개

참고문헌 (Reference)

• 1 A. Rao, "Storage assignment using expression tree transformation to generate compact and efficient DSP code" 128-138, 1999
• 2 S. Liao, "Storage assignment to decrease code size" 18 (18): 235-253, 1996
• 3 S. Lim, "Scheduling-based code size reduction in processors with indirect addressing mode" 165-169, 2001
• 4 B. Wess, "Optimum address pointer assignment for digital signal processors" 121-124, 2004
• 5 D.H.Bartley, "Optimizing stack frame accesses for processors with restricted addressing modes" 22 (22): 101-110, 1992
• 6 C. Xue, "Optimizing address assignment and scheduling for DSPs with multiple functional units" 53 (53): 976-980, 2006
• 7 R. Leupers, "Offset assignment showdown: Evaluation of DSP address code optimization algorithms" Springer-Verlag 2003
• 8 D. Ottoni, "Improving offset assignment through simultaneous variable coalescing" 2003
• 9 S. Atri, "Improving offset assignment for embedded processors" 158-172, 2000
• 10 C.Gebotys, "DSP address optimization using a minimum cost circulation technique" 100-103, 1997
• 11 G. Araujo, "Code Generation Algorithm for DSP's" Princeton Univ. 1997
• 12 A. Sudarsanam, "Analysis and evaluation of address arithmetic capabilities in custom DSP architectures" 287-292, 1997
• 13 R. Leupers, "Algorithm for address assignment in DSP code generation" 109-112, 1996
• 14 Y. Choi, "Address assignment combined with scheduling in DSP code generation" 225-230, 2002
• 15 R. Leupers, "A uniform optimization technique for offset assignment problem" 3-8, 1998