본 논문은 자원제약 조건에서 파이프라인 데이터패스 합성을 위한 스케줄링 방법이며, 우선순위 함수를 사용하여 스케줄할 연산을 선택하는 방법들과는 달리 연산들의 배정가능범위를 점진적으로 축소하여 스케줄한다. 제안방법은 스케줄링 알고리즘과 자원제약 위반을 검출하는 판단알고리즘으로 구성되며, 연산의 배정 가능한 제어단계의 처음 또는 마지막 단계에 임시로 연산을 배정하여 스케줄링 해가 존재하는지를 평가한다. 만약 해를 발견할 수 없다면 이는 자원제약 위반에 의해 연산을 그 제어단계에 배정하는 것이 불가능함을 의미하기 때문에 그 제어단계를 제거하며, 모든 연산에 대하여 배정가능범위 축소가 없을 때까지 이 과정을 반복한다. 벤치마크에 대한 실험결과는 다른 방법들과 비교해서 개선된 스케줄링 결과를 보인다.
This paper presents a scheduling approach for synthesizing pipelined datapaths under resource constraints. Our approach builds up a schedule based on gradual mobility reduction in contrast to other algorithms of previous researches, where an operation being scheduled is selected by using a priority function. The proposed method consists of a scheduling algorithm and a decision algorithm for detecting any violation against resource constraints. Our approach evaluates whether or not a scheduling solution can exist in case an operation temporarily is assigned to the earliest or latest control step among the assignable steps for the operation. If a solution cannot be found, it is impossible to assign the operation to that step due to a violation against resource constraints, and so we can eliminate that control step. This process is iterated until a reduction of mobility for all operations can not be obtained. Experiments on benchmarks show that this approach gains a considerable improvement over those by previous approaches.
