루프 알고리즘으로부터 정규순환방정식 유도를 위한 자료흐름 분석 = Data Flow Analysis for Deriving Uniform Recurrence Equation from Loop Algorithms

국문 초록 (Abstract)

본 논문에서는 주어진 문제의 루프 알고리즘으로부터 시스톨릭 어레이 구현이 용이한 정규순환 방정식으로의 자동적 유도를 위한 대수적인 방법과 조건을 제시하였다. 이를 위하여 계산점 집합과 순차 정렬 벡터를 구하고, 행렬의 커널을 이용하여 자료 흐름 벡터를 찾았으며, 정규 파이프라이닝 가능성 조건을 제시하였다. 그리고 각 계산점에 대한 배열 원소의 초기 입력 위치를 구하였다. 본 논문에서 제시된 방법을 사용하면 주어진 루프 알고리즘을 정규 순환 방정식으로 자동적으로 유도 할 수 있으며, 주어진 알고리즘이 정규 순환 방정식으로 유도될 수 있는지를 검사 할 수 있다.

다국어 초록 (Multilingual Abstract)

In this paper we present a method of the derivation of a uniform recurrence equation from given sequential loop algorithm. We investigate the algebraic properties of the computation set of loop algorithm and present the uniform pipelinability conditions of array variables. According to these conditions, how to analyze the shift-invariant data flow vectors of array variables is shown. We find data flow vectors using the kernel of the indexing matrix of array variable and the initial positions of input data. These results would be used in the automatic design of systolic arrays from a sequential loop algorithm and in the check of the possibility for deriving uniform recurrence equations from sequential loop algorithims.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 알고리즘 모델
• 3. 자료 흐름 분석
• 4. 초기 입력 위치와 자료 흐름 벡터
• 5. 결론
• 참고문헌
• 저자소개