Reconfigurable architectures are becoming one of the most promising solutions in computing domains. Reconfigurable architectures` reconfigurability and hard-wired logic pursuit two important goals of flexibility and performance. However, applications of reconfigurable architectures are sometimes limited due to a reconfiguration overhead, for which many hardware supports and software translation techniques are proposed. Among those techniques, an architectural support called a partial reconfigurability that reconfigures only a required portion of a device as applications change is the hot issue to reduce the run-time reconfiguration overhead in recent commercial and academic reconfigurable architectures. Many exploits the partial reconfigurability with a time-multiplexing scheme that implements multiple temporal partitions at one time and selects one of them. In the time-multiplexing, the common resources are reused again and again in multiple temporal partitions. To maximize the amount of common resources, many resource sharing techniques have been proposed. However, the time-multiplexing requires relatively large area to maintain all temporal partitions and to control multiple datapaths with multiplexers.
This dissertation proposes another way to employ the partial reconfigurability to reduce the reconfiguration overhead. The key idea is to share configurations between consecutive temporal partitions and to reduce the size of configuration bitstreams. Compared to the time-multiplexing, the proposed scheme repeatedly loads configurations, and only keeps one configuration at a time, which results smaller area. The introduced configuration sharing is divided into two sub-problems of a resource sharing and a placement and routing. For the first sub-problem, this dissertation proposes a novel graph model for interconnection and operation sharing, and a resource sharing algorithm that is based on a traditional graph isomorphism. To effectively reuse resources which the sharing algorithm figures out, a min-cut placer and a negotiation-based router are enhanced. An entire framework including the sharing algorithm, the placement and routing, and a reconfigurable architecture simulator are developed, and several experiments on the sharing algorithm itself and on the reconfiguration overhead reduction with the configuration sharing are conducted.
재구성 아키텍처에서의 재구성 오버헤드는 아키텍처를 사용하기 위해 필요한 구성을 읽어들이는 과정에 필요한 시간으로, 재구성이 빈번하게 요구되는 경우에는 전체 수행시간에서 상당 부분을 차지하게 된다. 본 논문은 재구성 아키텍처에서 재구성 오버헤드를 줄이기 위해 구성 공유라는 기법을 제안하고 있다. 구성 공유는 연속적으로 필요한 구성 간의 공통의 부분을 찾아내고, 이를 실제 구성을 읽어들이는 과정에서 제외시킴으로서 재구성 오버헤드를 줄이는 방식이다. 따라서 구성 공유는 크게 자원 공유의 문제와, 이렇게 공유된 자원으로부터 실제 구성 공유를 유도하기 위한 배치 및 라우팅 의 문제로 분리된다.
자원 공유를 해결하기 위해서 본 논문에서는 우선 자원 공유를 위한 그래프 모델 및 공유 알고리즘을 제안하고 있다. 그래프 모델은 그래프 간에 연산 및 연산간의 연결을 효율적으로 나타내어 자원 공유를 최대화 하기 위해 고안되었다. 그래프 모델은 연산이 서로 공유 가능한지를 나타내는 호환선에 기반을 두며, 호환선을 이용하여 연산 공유와 연결 공유를 균일하게 표현하고 있다. 자원 공유는 이 호환선을 선택하는 것으로 표현되며, 그래프 동일성에 기반을 둔 알고리즘을 이용하여 자원 공유를 찾게 된다.
이렇게 공유 가능한 것으로 찾은 자원은, 아키텍처에서 하드웨어 자원에 할당되는 방식에 따라서 구성 공유가 가능할 수도 가능하지 않을 수도 있다. 연산 및 연결을 하드웨어에 할당 하는 것은 배치 및 라우팅 문제가 되며, 보다 효율적인 구성 공유를 위해 기존의 최소 커트 배치와 협상 기반 라우팅을 개선하였다. 우선 다수의 구성에 필요한 연산을 동시에 할당하며, 또한 연산의 공유를 최대화 하기 위해, 기존의 최소 커트 배치를 다수의 구성에 적용 가능하도록 확장하였다. 또한 라우팅 시에 공유 불가능한 연결이 공유 가능한 자원을 지나가며 구성 공유를 방해하지 않도록 공유되는 구성에 대한 비용을 정의하고 협상 기반 라우팅을 개선하여 최대한 구성 공유를 가능하게 하였다.
이러한 자원 공유 및 구성 공유를 위한 배치 및 라우팅 문제를 해결하기 위해, 본 연구에서는 소프트웨어/하드웨어 동시설계 프레임워크를 구현하고, 그 내부에 제안된 공유 알고리즘과 배치 및 라우팅 알고리즘을 구현하였다. 생성된 하드웨어 구성은 사이클 정확도의 재구성 아키텍처 시뮬레이터에서 수행되며, 전체적인 수행 시간을 구할 수 있다. 실험에 따르면, 제안된 구성 공유의 기법을 사용할 경우, 필요한 연결이 최단거리 위주로 라우팅이 되는 것이 아니라 공유되는 구성을 거쳐가는 것을 피하기 위해 보다 긴 거리를 통해 라우팅이 됨으로서 연산 시간이 다소 늘어나는 것으로 밝혀졌다. 하지만 구성 공유를 통해 재구성 시간이 줄어들게 되며, 따라서 반복적인 재구성을 요구하는 경우에 전체적인 수행시간은 줄어들게 되는 것을 보일 수 있었다.
