The major obstacle in the data path synthesis problem is interactions between synthesis subtasks. Interactions do not allow a foresight of the final synthesis result to estimate an effect of local design decision of any subtask. And the other obstacle is the size of problem space for getting the best implementation with minimum execution time and minimum area. It is so large and thus very hard to search the space efficiently. The conventional techniques such as iterations or heuristics tend to find the local optimum solution.
This thesis describes a delayed binding of design decisions. It did not bind the design decisions at each synthesis subtask but normally defer important design decisions. An efficient method to synthesize the data paths of digital system from behavioral specification is presented. This method is based on path-search algorithm that finds groups of compatible variables(CVGs) which are existing along proper paths in a modified data-dependency graph(MDDG). It does a limited search through the space of the proper paths in MDDG. It is proved that the upper bound on the path number of a MMDG is $O(n^2)$, where n is the number of nodes in MDDG. Thus, searching the proper paths of a MMDG can not be blown-up by the massive path number. The path-search algorithm is also applies to the behavioral specification with conditional statements or loop statements.
The algorithm for incorporating with the results of the path-search algorithm is conflict-analysis phase. During this phase, two types of resource foldings, memory and functional resource folding, are performed simultaneously. This resource folding technique is independent of the number of resources. Finally, the bus-style synthesis algorithm is presented. It is conceptually simple and results in the implementation with low cost and short delay.
The approach taken here has been tested for typical examples which were taken from HAL, Facet, Flamel, and etc. From these results, the proposed method performs comparably well for the selected examples.
본 논문에서는 Pascal과 같은 고급 프로그래밍 언어 형태로 씌어진 설계 사양으로부터 디지탈 시스템의 데이타 경로를 합성하는 문제를 다루고 있다. 이러한 합성 문제는 문제의 성격상 몇개의 부분 작업으로 분할해서 해결하는 것이 일반적이다. 즉, 전체 합성 문제는 자원의 스케쥴링, 기억 자원의 할당, 기능 자원의 할당 및 연결 자원의 할당등 4가지 형태의 부분 작업으로 나눌 수 있다. 그런데, 이들 각 부분 작업들은 상호 밀접하게 연관되어 있기 때문에 어떤 부분 작업에서 행해진 설계 결정이 다음 부분 작업의 결정에 어떠한 영향을 미치게 될지 여부에 대한 예측을 할 수 없으며, 최종 결과에 대한 예측 평가도 불가능하다. 이 문제는 근본적으로 전체 최적화 문제로 볼 수 있으나, 자원의 스케쥴링이 이루어지지 않은 상태에서 최적화란 불가능하다는 것이 이미 증명되었다. 한편, 계산상의 복잡도를 줄이기 위해 검색 공간의 크기를 적절히 제한하는 검색 방법이 필요하다.
위에서 언급한 문제들의 해결을 위해 본 논문에서 제안하는 방법은 설계 결정을 잠정적으로 지연시키는 것이다. 다시 말해서, 어떤 부분 작업에서의 설계 결정을 지연시키되, 해로써 가능한 설계 결정들만을 선택해 다음 부분 작업으로 넘기게 된다. 이때 이들 잠정적인 결정은 다음 부분 작업에 대한 해를 구함에 있어서 중요한 변수로 포함되게끔 하는 것이다.
보다 구체적으로 설명하면, 수정된 형태의 데이타 종속 그래프(MDDG)상에서 제한된 수의 경로만을 검색함으로써 기억 자원(예를 들면, 레지스터)의 공유가 가능한 변수 집함(CVG)들을 구할 수 있다. MDDG의 노드는 코드의 좌변 변수를 나타내며, CVG에 포함된 데이타 변수들은 단일 기억 자원으로 할당할 수 있다.
한편, MDDG상에서 CVG수는 최악의 경우일지라도 $n^2$(여기서 n은 MDDG에서의 노드 수)보다 작다는 것을 입증했다. 따라서, MDDG상에 이러한 경로 검색 알고리즘을 적용시켜 경로를 찾는 경우 엄청난 양의 경로수로 인한 제약이 따르지 않음을 확인할 수 있었다. 또한 조건문(if 문)이나 반복문(for 혹은 do, while 문) 등을 포함하는 설계 사양에 대해서도 경로 검색 알고리즘을 적용시킬 수 있음을 보였다.
전술한 바와 같이 구한 CVG들을 데이타 연산자들을 기능 자원(예를 들면, 가산기등)으로 할당시키기 위한 비용 함수의 변수로 포함시킴으로써 기능 자원 할당이 실행된다. 이와같이 함으로써 두가지 형태의 부분 작업들간의 상호 연관성을 충분히 고려할 수 있으며, 기억 자원에 해당되는 데이타 변수들과 기능 자원에 해당되는 데이타 연산자들이 주어질 경우 국부 연결망에 대한 예측.평가도 행해질 수 있다. 이와 더불어 두가지 형태의 자원 할당이 동시에 일어나게 된다. 대개 자원 할당 문제는, 자원의 수가 어느 한계(예를 들면 50개 이상)를 넘어서면, 계산상의 복잡도로 인해 해결할 수 없게 된다. 그러나 전술한 접근 방식은 자원수에는 거의 무관하며, 단지 스케쥴된 제어 스텝수와 CVG수에 비례하는 복잡도를 갖게된다. 이와 같은 접근 방법에 의해 설계 사양 구현에 필요한 자원 할당이 끝난 경우 버스 형태로 연결하는 알고리즘도 제안되었다.
결과적으로 본 연구의 주된 관점인 각 부분 작업들간의 상호 연관성의 부정확한 측면을 해결하기 위해 설계 결정 지연 방법론에 입각한 접근 방법을 제안하였으며, 이와 관련된 두가지 연관 알고리즘, 즉 경로 검색 알고리즘과 비용 분석 알고리즘을 개발하였다. 다른 기존의 시스템과의 비교 분석을 위해 Flamel, Facet, HAL 및 EMUCS등의 예에 적용ㆍ비교해 본 결과 상대적으로 좋은 결과를 얻음을 확인할 수 있었다.
