Modern digital systems design requires extensive exploration on the large and complex design space to find the best or a set of satisfiable configurations which meet design requirements. However, the forms of all the possible designs are so diverse that any single description has not yet been devised to express them all. Instead of expressing all the architectural design space, previous work used only parameterization method for design space representation. This approach provides simple description on the design space. On the other hand, it has a limitation that it can not express architectural variation.
This thesis proposes a sound semantics for design space representation, with which a designer can express the architectural variation as well as parameterization. We extended the classical AND/OR graph to hold the characteristics of design space of digital system. The main goal of the representation is two folds: representation in formal semantics and expressive power of design alternatives. To meet such a goal, a formalism of attributed AND-OR graph is defined for design space representation. The AND and OR relations in the graph can represent not only a collection of components (AND relation) to form a system but also variants of alternatives (OR relation) to be used for a given component. Moreover, attributes attached at the vertex can represent ranges of parameters and constraints on selection of a set of alternatives located at different sub-modules. Constraints can be a good means to reflect many designers' knowledge base.
Based on Attributed AND/OR Graph, complete design space exploration framework is exemplified by introducing plan-generation-evaluation framework. The plan process implies the construction of a complete design space. Generation is a phase to synthesize a complete simulation model and evaluation is a step to measure the performance index of the generated models.
Attributed AND/OR graph is utilized to implement the plan process. In addition, we divided the design space into two based on the abstraction level. The higher one is a functional design space and the lower one is a structural design space. Each is devised for its own purpose. For example, functional design space exploration tries to find a good algorithm via functional simulation with untimed models. On the other hand, structural design space exploration is based on the cycle-accurate models, with which a designer can measure the performance index more precisely.
Generation consists of two processes: candidate generation and model synthesis. We can consider the attributed AND/OR graph as an encoding scheme for all the possible design candidates. Therefore, we proposed an candidate collection algorithm that works on the design space in attributed AND/OR graph to generate the set of all the possible configurations. Through model synthesis, we can obtain simulatable model. In this thesis, we employed SystemC simulation environment for evaluation, therefore we will show the model synthesis assuming SystemC evaluation environment. Evaluation is performed by SystemC simulation.
Moreover, with the relations that map the vertex set of functional design space to the vertex set of structural design space, we realized the hierarchical pruning that uses the result of functional design space exploration to explore the structural design space.
To show the effectiveness of the proposed work, we specified the design space of processor in attributed AND/OR graph. We implemented the functional design space and structural design space respectively, performed hierarchical pruning and explored the pruned design space. The results and evaluation of the actual design space exploration are given. The experimental results show that the proposed attributed AND/OR graph is an efficient scheme for design space representation.
본 논문은 ASIP의 설계 공간을 표현하기 위한 정형론으로 attributed AND/OR graph를 제안하고 있다. Attributed AND/OR graph는 고전적인 AND/OR graph를 디지털 시스템의 설계 공간을 표현하기 위하여 확장한 것으로 다음과 같은 특징을 갖고 있다. AND-관계를 이용하여 하나의 모델을 다른 여러 가지 모델의 조합으로 구현할 수 있음을 표현한다. OR-관계를 이용하여 하나의 모델을 구현하기 위한 다양한 방법이 있음을 표현한다. 이 두 가지 관계를 이용하면 시스템의 구조적 설계 공간을 모두 표현할 수 있다. 또한 하나의 모델에 붙는 속성(attribute)을 이용하여 파라미터에 의한 설계 공간을 표현할 수 있다. 즉 attributed AND/OR graph의 OR-관계와 속성(attribute)를 이용하여 모든 설계 공간을 표현한다. 또한 설계 공간 탐색 기법을 적용하기 위하여 모델의 입출력, 그리고 각 모델들 사이의 연결 관계를 정형적으로 정의함으로써, 한 시스템을 구현할 수 있는 모든 설계 공간과 실제 모델들이 어떻게 연결되는지 표현할 수 있게 되었다.
Attributed AND/OR graph를 이용한 설계 공간 탐색기를 구현함으로써 본 연구의 유용성을 보였다. 설계 공간 탐색기는 계획, 생성, 그리고 평가, 세 단계를 거치게 된다. 계획 단계에서는 전체 설계 공간을 표현하여 구축하고 생성 단계에서는 구축된 설계 공간으로부터 유효한 설계들을 찾아내고 모델을 생성한다. 마지막으로 평가 단계에서는 찾아진 설계의 성능을 측정함으로써 설계 공간의 탐색을 마치거나 생성 단계를 다시 거침으로써 새로운 설계를 찾아내고 다시 평가하는 작업을 반복하게 된다. 본 논문에서 제안한 attributed AND/OR graph를 계획단계에서 사용하였고 생성 단계를 위해서 attributed AND/OR graph로 표현된 설계 공간으로부터 모든 설계 후보들을 만들어내는 알고리즘을 제안하였다. 마지막으로 평가를 위해서는 SystemC 시뮬레이션 환경을 이용하였다. 예제를 통하여 attributed AND/OR graph가 모든 설계 공간을 쉽게 표현할 수 있음과 설계 공간의 확장이 용이함을 보였다. 또한 이 모든 계획-생성-평가 단계가 완전히 자동으로 수행됨으로써 본 논문에서 제안한 attributed AND/OR graph가 전체 설계 공간 탐색에서 유용하게 사용됨을 보일 수 있었다.
