서지주요정보
(An) efficient binding algorithm in data path synthesis utilizing network flow computation = 네트워크-플로우을 이용한 데이타 경로 합성에서의 효율적 배정 알고리즘
서명 / 저자 (An) efficient binding algorithm in data path synthesis utilizing network flow computation = 네트워크-플로우을 이용한 데이타 경로 합성에서의 효율적 배정 알고리즘 / Yoon-Seo Choi.
저자명 Choi, Yoon-Seo ; 최윤서
발행사항 [대전 : 한국과학기술원, 2002].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8013113

소장위치/청구기호

학술문화관(문화관) 보존서고

MCS 02042

SMS전송

도서상태

이용가능

대출가능

반납예정일

등록번호

9008844

소장위치/청구기호

서울 학위논문 서가

MCS 02042 c. 2

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

We propose an efficient binding algorithm for power optimization in behavioral synthesis. In prior work, it has been shown that several binding problems for low-power can be formulated as multi-commodity flow problems (due to an iterative execution of data flow graph) and be solved optimally. However, since the multi-commodity flow problem is NP-hard, the application is limited to a class of small sized problems. To overcome the limitation, we address the problem of how we can effectively make use of the property of efficient flow computations in a network so that it is extensively applicable to practical designs while producing close-to-optimal results. To this end, we propose an efficient two-step algorithm, which (1) it determines a feasible binding solution by partially utilizing the computation steps for finding a maximum flow of minimum cost in a network and then (2) refines it iteratively. Experiments with a set of benchmark examples show that the proposed algorithm saves the run time significantly while maintaining close-to-optimal bindings in most practical designs.

본 논문은 회로의 전력 소모를 최소화 하기 위한 behavioral synthesis level 에서의 binding 알고리즘을 다룬다. 저전력 소모를 위한 binding 알고리즘들은 multi-commodity flow 문제로 공식화될 수 있으며, 이를 풀면 optimal solution을 구할 수 있음이 알려져 있다. 그러나 multi-commodity flow 문제가 NP-hard이기 때문에, 이 방법은 작은 크기의 문제에만 적용될 수 있다는 단점이 있다. 이러한 단점을 극복하기 위해서, 본 논문에서는 실제적인 크기의 문제에도 이용할 수 있도록, flow structure를 효과적으로 이용하는 방법을 다룬다. 이를 위해 효과적인 2단계 알고리즘을 제안한다. 첫번째 단계에서는 network상에서 minimum cost의 maximum flow를 구하는 방법을 부분적으로 이용하여 feasible solution을 구한다. 두번째 단계에서는 network상에서 첫번째 단계에서 구해진 initial solution를 iterative하게 개선시킨다. behavioral synthesis용 benchmark 프로그램을 이용한 실험결과는 제안된 알고리즘이 짧은 시간안에 optimal에 가까운 결과를 내는 것을 보여준다.

서지기타정보

서지기타정보
청구기호 {MCS 02042
형태사항 [ii], 20 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 최윤서
지도교수의 영문표기 : Tae-Whan Kim
지도교수의 한글표기 : 김태환
학위논문 학위논문(석사) - 한국과학기술원 : 전산학전공,
서지주기 Includes reference
주제 network-flow
datapath synthesis
binding
네트워크 플로우
데이타 경로 합성
배정 알고리즘
QR CODE qr code