In these days, many dynamically reconfigurable architectures have been introduced to fill the gap between ASICs and software-programmed processors such as GPPs and DSPs. These reconfigurable architectures have shown to achieve higher performance compared to software-programmed processors. However, the current reconfigurable architectures suffer from a significant reconfiguration overhead so that it severely degrade the overall performance of reconfigurable architectures. In order to deal with this reconfigurable verhead, there had been intensive research on hardware and software techniques such as configuration compression, configuration prefetching, configuration sharing, multi-context switching, and partial reconfiguration. Among these techniques, many commercial and academic reconfigurable architectures provide the partial reconfiguration. When compiling applications written in high-level languages for these reconfigurable architectures with partial reconfiguration, compilers or synthesis tools should split into the temporal partitions using temporal partitioning. And then, each temporal partition is executed on these reconfigurable architectures through three stages: fetch, configuration, and computation. Therefore, it is important to split applications overlapping of the execution stages on different temporal partitions such that the reconfiguration overheads are minimized.
In this dissertation, the temporal partitioning methodology are introduced to cope with partial reconfiguration. The proposed temporal partitioning methodology splits the application into several temporal partitions such that the reconfiguration overhead of each temporal partition can be overlapped with a computation time of the previous temporal partition. Therefore, the proposed temporal partitioning are able to amortize the reconfiguration overhead at high-level synthesis phase or compilation time. Also, temporal partitions inside a loop can be locally iterated by using a intra-partition scheduling in order to completely hide the reconfiguration time of the subsequent partition. Finally, to demonstrate the effectiveness of the proposed methodology, results on real benchmarks will be presented.
최근 몇 년 동안 주문형 집적회로(ASIC)와 디지털 신호 처리장치(DSP)와 같은 범용 프로세서의 틈을 메우기 위해 많은 동적 재구성 아키텍처들이 발표되어 왔다. 이러한 동적 재구성 아키텍처는 주문형 집적회로의 성능과 범용 프로세서의 유연성(flexibility)을 동시에 취할 수 있다는 장점을 가지고 있다. 하지만 기존의 FPGA와 같은 정적 재구성 아키텍처들이 프로세서의 동작 전에 한번의 재구성만으로 많은 수의 데이터를 반복 처리함으로써 재구성 오버헤드를 숨길 수 있는 것과는 달리, 동적 재구성 아키텍처에서는 실행 중간에 재구성이 이루어짐으로써 재구성 오버헤드가 성능에 미치는 영향이 커지게 되었다. 따라서 이러한 재구성 오버헤드를 줄이기 위해 구성 정보 압축 기술(configuration compression), 구성 공유(configuration sharing)와 같은 많은 재구성 오버헤드 관리 기법들이 연구되어 왔다. 그 중에서 많은 상업적, 연구적으로 발표된 동적 재구성 아키텍처들이 부분 재구성(partial reconfiguration)과 같은 구조적인 기법을 제공하고 있다. 이러한 부분 재구성을 제공하는 아키텍처에서는 각각의 구성 정보들이 구성 메모리까지로의 이동(fetch), 재구성(configuration), 실행(computation)의 세 단계를 통해서 실행된다. 또한, 하나의 구성 정보들이 실행하고 있는 동안, 사용되지 않은 재구성 아키텍처의 재구성 요소(reconfigurable cell)들을 다른 구성 정보들이 재구성 될 수 있는 특징을 가지고 있다. 따라서 이러한 부분 재구성의 특징을 잘 이용하면 재구성 오버헤드를 크게 줄일 수 있게 된다. 본 논문에서는 부분 재구성을 잘 이용하여 재구성 오버헤드를 줄이기 위한 시간적 분할 기법(temporal partitioning)을 제안하고 있다. 이러한 시간적 분할 기법은 응용 프로그램을 시간적 부분(temporal partition)들로 분할하게 된다. 또한 기존의 시간적 분할 기법과는 달리 분할된 시간적 부분들의 재구성되는 시간들이 앞서 실행 중인 시간적 부분들의 실행 시간들과 최대한 겹쳐지게 함으로써 재구성 오버헤드를 최대한 줄일 수 있도록 해준다. 이러한 분할이 가능 할 수 있도록 시간적 분할 기법은 처음에는 응용 프로그램을 하나의 재구성 요소들로 할당(mapping)될 수 있는 재구성 단위들의 제어/데이터 흐름 그래프(CDFG)로 변환한다. 그 다음 단계로, 이러한 재구성 단위들을 프로그램의 구조적 순서를 바탕으로 방문하면서 보다 큰 시간적 부분으로 점진적으로 병합(merging)해 나가게 된다. 이러한 과정은 모든 재구성 단위들에 대해서 방문이 완료되면 시간적 분할이 완료되게 된다. 또한 병합 과정마다 병합되어 변경된 시간적 부분들에 대해서 재구성 시간 및 실행 시간 등을 추산하여 전체적인 성능 향상이 이루어졌는지 판단함으로써 재구성 오버헤드를 최대한 줄일 수 있는 재구성 부분들로 분할할 수 있게 된다. 이러한 병합 과정 중, 루프(loop)에 포함된 시간적 부분의 경우에는 루프의 전체적인 반복 횟수(the number of loop iterations)를 루프에 포함된 시간적 부분들이 지역적으로 반복 수행하게 함으로써 시간적 부분들의 실행 시간을 늘려서 뒤이은 시간적 부분들의 재구성 오버헤드를 숨길 수 있도록 한다. 이러한 루프 내의 시간적 부분들이 지역적으로 반복 수행하게 되는 횟수를 부분간 스케쥴링(intra-partition scheduling) 기법에서 찾을 수 있다.
이러한 시간적 분할 기법과 부분간 스케쥴링 기법의 효율성을 보여주기 위해 동적 재구성 아키텍처를 대상으로 하는 소프트웨어/하드웨어 동시설계 프레임워크를 구축하고, 시간적 분할 기법과 스케쥴링 기법을 구현하였다. 실험 결과에서는 제안된 시간적 분할과 부분간 스케쥴링 기법에 의해 만들어진 시간적 부분들의 실행 시간과 재구성 시간이 겹침으로써 재구성 시간이 숨겨지는 것을 볼 수 있었다. 따라서, 이러한 효과를 통해 전반적인 재구성 오버헤드를 줄이고 전체 수행 시간을 줄이는 효과가 있음을 보일 수 있었다.
