루프의 파이프라이닝 스케쥴을 위한 알고리즘 = A Pipelining Scheduling for Algorithm Loops

국문 초록 (Abstract)

본 논문에서는 루프의 병렬화를 위해 루프의 기능한 병렬성을 탐지하고 스케쥴하는 문제를 다룬다. 최근에 집적회로 기술의 급격한 발달로 한 칩안에 파이프라이닝 연산이 이루어지도록 하는 것이 가능하며 VLIW나 슈퍼스칼라 컴퓨터에서는 파이프라이닝의 스케쥴링 문제가 발생한다. 여기에서는 고수준 언어로 표현된 루프를 데이타 종속그래프로 나타내고 이로부터 루프의 병렬성을 파악하여 그 병렬성을 나타내는 파이프라이닝 형태의 스케쥴을 얻고자 한다. 특히 단순 루프에 있는 최대한의 병렬성을 얻는 최적의 알고리즘을 제시하고자 한다. 이 알고리즘에서는 데이타 종속 그래프상의 근접한 노드 사이의 지역적 시간관계를 이용하여 이를 결합함으로써 전체적인 스케줄을 얻는 방법을 사용하였다. 제시된 알고리즘은 다항 시간의 복잡도를 가지며 최소의 지연간격을 갖는 파이프라이닝 스케쥴의 패턴을 생성한다.

다국어 초록 (Multilingual Abstract)

This paper deals with the problem of detecting and scheduling parallelism existing in loops for loop parallelization. Recently the tremendous development in VLSI technology makes it possible that a pipelining operation is to be performed in a single chip processors and the pipelining scheduling problem arises in VLIW or superscalar machines. Here we represent the loops of high-level programs as data dependence graphs, and from them we are to perceive parallelism in the loops, and to obtain the schedules in pipelining form which represents maximal parallelism. Especially an optimal algorithm for obtaining maximal parllelism In simple loops will be presented. The method to be used in this algorithm combines local schedules using local timing relations between adjacent nodes in its dependence graph to obtain an overall schedule. The algorithm has polynomial time complexity and produces the pattern of pipelining schedule with minimal delaying distance.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 프로그램의 표현
• 3. 최적 패턴 찾기
• 4. 결론
• 참고문헌
• 저자소개