The hardware synthesis task is to take a specification of the behavior required of the hardware and a set of goals and constraints to be satisfied, and to find a register-transfer level structure that implements the behavior while meeting the goals and constraints. The hardware synthesis usually consists of several subtasks. The first task is the compilation of the high-level description into an internal representation. The core subtasks of transforming behavior into structure are the next three tasks: the scheduling which assigns operations into appropriate control steps, the data-path synthesis which allocates, binds and interconnects hardware resources, and the controller synthesis that drives the synthesized data-path part as implied by the behavioral description.
In this theses, new approaches for the core parts of the hardware synthesis are presented. For the scheduling, we propose a new iterative heuristic algorithm having polynomial time complexity. One major feature is that it can escape from local minima and has a tendency to reach the globally optimal solution. Although there is no guarantee for the optimality, optimal results have been obtained for the experimental examples of the earlier works in a very short computation time. A graph model which contains information on the real-world constraints such as multi-cycle operations, chained operations and pipelined data-paths is also proposed as a general model on which our scheduling algorithm is based.
For the data-path synthesis, we developed a new efficient binding algorithm grounded on hardware designer's approaches. The problem of allocating minimal sufficient hardware resources such as registers and fuctional at units has been quite successfully solved by various earlier works. Compared to this, the problem of binding operations and variables to the allocated hardware resources such that total cost of interconnections is minimized is so difficult that exhaustive searching methods such as branch-and-bound were widely used. In this thesis, we present efficient binding algorithms which are developed with and emphasis on the minimization of interconnection cost. Three binding algorithms for operation, variable and multiplexer are described in detail. From the experimental results using examples available from literatures, the proposed binding algorithms were proven to be attractive in terms of computation time and such quality measures as number of multiplexers and multiplexer inputs, etc.
Once the scheduling and the data-paths have been determined, it is necessary to synthesis a controller that will drive the data-paths as required by the scheduling result. The microprogrammed control scheme is adopted for controller synthesis in this thesis. Since the control ROM is the heart of microprogrammed controller, we tried to minimize the microcode width by encoding of the microoperations. We present an exact formulation based on the integer linear programming which results in an optimal solution for small of medium sized problem, and a heuristic algorithm to solve large sized problem. The heuristic algorithm resulted in optimal or near optimal solutions for several large examples.
하드웨어 합성이란 하드웨어에서 수행할 동작과 만족시켜야하는 목표와 조건으로 부터 레지스터 전송 수준의 하드웨어 구조를 자동으로 설계하는 것이다. 이 하드웨어 합성은 몇단계의 일로서 구성되는데 첫번째 단계는 상위단계의 표현을 데이타 종속관계와 제어관계를 나타내는 그래프 형태의 중간 표현으로 변환하는 것이다. 그래프 표현으로부터 하드웨어를 합성하기 위해서는 보통 다음의 3 단계의 일을 순차적으로 수행한다. 즉, 1) 각 연산의 제어 순서를 결정하는 스케쥴링, 2) 하드웨어 자원(레지스터, 연산자 등)을 할당하고 상호 연결하는 데이타 경로부 합성, 3) 데이타 경로부를 스케쥴링된 대로 제어하는 제어부의 합성이 필요하다.
본 논문에서는 위의 3가지 핵심부분에 대한 새로운 알고리듬과 접근방법을 제안한다. 스케쥴링의 경우 FAMOS라는 반복적 휴리스틱 알고리듬을 제안하였으며, 이 알고리듬의 주요 특징은 국부적 최소해를 탈피하여 최적해에 도달하는 경향이 크다는 것이다. 최적해를 보장하지는 못하지만 기존의 예제에 대한 실험에서 최적해를 빠른 시간에 구하였다. 또한 실제적인 설계조건을 간단히 포함할 수 있는 그래프 모델을 제안하였다.
데이터 경로부 합성을 위하여 설계자의 방식을 기초로 한 알고리듬을 개발하였으며, 연산, 변수, multiplexer 각각에 대하여 하드웨어 자원 간의 연결비용이 최소가 되도록 하였다. 제안된 방식은 먼저 필요한 하드웨어 자원을 할당하고 각 연산을 어느 연산자에서 수행할 것인지, 각 변수를 어느 레지스터에 저장할 것인지를 결정하는 것으로 이 과정 중에 항상 연결비용을 최소화하는 데 중점을 두었다. 제안된 방식의 데이타 경로부 합성 결과는 질과 계산 시간 면에서 우수함을 실험결과로 보였다.
또한, microprogram 방식의 제어부를 채택하고 이 제어부의 근간인 제어 ROM의 크기를 최소화하기 위하여 마이크로 연산을 encoding하여 제어 ROM의 폭을 최소화하는 두가지 방법을 제안하였다. 첫째는 정수 선형 프로그래밍을 사용하는 것으로 작은 크기의 문제에 대하여 최적해를 보장한다. 큰 문제를 풀기위한 방법으로 휴리스틱 알고리듬을 제안하였으며 실제 예제에 대하여 최적 또는 준최적 해를 구할 수 있음을 보였다.
