직선상에서 최대구간을 찾는 최적 알고리즘

허성우(Sung Woo Hur),좌경룡(Kyung Yong Chwa),신성룡(Sung Yong Shin) 한국정보과학회 1988 한국정보과학회 학술발표논문집 Vol.15 No.2

본 연구에서는 x축상에 실수값의 weight가 부여된 n개의 점이 있을 때 어떤 interval을 찾아 그 interval내에 있는 점들의 weight 합이 최대가 되도록 하는, 즉 maximum interval을 찾는 최적 알고리즘을 제시한다. 또한 이 알고리즘을 이용하면 평면상에 실수값의 weight가 부여된 n개의 점이 있을 때 xy축에 평행한 어떤 직사각형을 찾아 그 직사각형내에 놓여있는 점들의 weight 합이 최대가 되도록 하는, 즉 maximum rectangle을 쉽게 찾을 수 있음을 보였다.

Efficient Algorithms for Cell Placement

허성우(Sung-Woo Hur) 한국정보과학회 영남지부 2000 한국정보과학회 영남지부 학술발표논문집 Vol.8 No.1

보로노이 다이아그램을 위한 동적 알고리즘

허성우(Sung Woo Hur),좌경룡(Kyung Yong Chwa) 한국정보과학회 1989 정보과학회논문지 Vol.16 No.1

본 논문에서는 한정된 평면에서 n개의 점으로 구성된 Voronoi diagram 에 새로운 한 점이 입력될 경우 그 Voronoi diagram을 O(n)시간에 수정할 수 있는 알고리즘을 제시한다. 그 알고리즘은 크게 두 부분으로 구성되는데, 첫째는 새로 입력된 점이 어느 tile 내에 입력되었는지를 O(n)시간에 검색하는 부분이고, 둘째는 Voronoi diagram을 갱신하여 새로운 Voronoi diagram을 얻는 부분인데, 이의 시간복잡도는 O(m)로써, 여기서 m은 새로 입력된 점이 포함된 tile의 꼭지점의 갯수이다. This paper presents an algorithm of O(n) time complexity for finding new Voronoi diagram, when we are given Voronoi diagram on n points and a new input point. The algorithm consists of two parts. One which has time complexity of O(n) is how to find the tile in which the new input point locates. The other is how to update the Voronoi diagram. The time complexity of the latter is O(m), where m is the number of vertics of the tile which encloses the new point.

O-tree 기반 효과적인 평면계획 알고리즘

허성우(Sung-Woo Hur) 한국정보기술학회 2010 한국정보기술학회논문지 Vol.8 No.1

The floorplan algorithm using O-tree is based on a deterministic method. It searches solution space by deleting each module one by one for all modules and inserting it into the best location. It causes such problem that the solution quality depends on the order of deletion and insertion sequence. To overcome this problem, this paper proposes an effective search method of solution space using simulated annealing frame. We use two simple but effective perturbation operations to visit neighbor solutions. First, we select a pair of modules and exchange their locations. Second, we select a module randomly and delete it from the O-tree. Then we insert it into the best location after examining all the possible locations. Proposed method improves the solutions 3% to 20% on average depending on circuits, compared to the results obtained by the original O-tree method.

격자 상에서 순서쌍과 압축 기법을 이용한 평면계획

허성우(Sung-Woo Hur) 한국정보기술학회 2014 한국정보기술학회논문지 Vol.12 No.12

Floorplan is a crucial phase in a VLSI chip design process. Its goal is to optimize an objective function while placing rectangular shaped modules in a plane without overlapping. Possible objective function is either the area of the enclosing rectangle, routability, total wire length, or delay. In this paper, we use an ordering pair and compaction technique on a grid in a simulated annealing frame aiming at minimizing the area of floorplan. For the move operations, we use the information regarding dead space after compaction. Two modules, which are likely to minimize the dead space, are selected and are exchanged in the ordering pair. Experimental results prove that the suggested method is very promising.

Slicing Tree에 압축 기법을 이용한 평면계획 알고리즘

허성우(Sung-Woo Hur) 한국정보기술학회 2011 한국정보기술학회논문지 Vol.9 No.12

Most existing floorplan techniques use variable models based on a non-slicing structure and present algorithms adequate for the models. This paper presents a simulated annealing based algorithm which seems to work on a non-slicing structure by using a slicing binary tree for the slicing structure and the compaction technique. The move operations to perturb the slicing tree are simple but effective. Move operations include exchanging the location of two modules and reversing the cut orientation in the slicing tree. The orientation of each module corresponding to the leaf node of the slicing tree can be determined by applying a dynamic programming method. The dead spaces are reduced as much as possible using the compaction technique. Experimental results prove that the suggested method is very promising.

윤곽지도를 이용한 VLSI 회로 설계를 위한 효과적인 평면계획 기법

허성우(Sung-Woo Hur),오은경(Eun Kyung Oh) 한국정보기술학회 2013 한국정보기술학회논문지 Vol.11 No.2

Most existing floorplan techniques use variable models based on a non-slicing structure and present algorithms adequate for the models. This paper presents an effective floorplan technique which determines the location and the orientation of each module on a non-slicing structure. When determining the location and the orientation of a module we consider both the total utilization and contour utilization. By this, we can accept an intermediate floorplan although its current total utilization is not high since it seems to have possibility of getting better in the furture. Experimental results show that the proposed technique which associates the location decision process of each module and simulated annealing technique is very promising. The experimental results on MCNC benchmark circuits are comparable to those shown in other papers.

표준 셀 배치를 위한 하이브리드 기법

허성우(Hur Sung Woo),오은경(Oh Eun Kyung) 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.30 No.9·10

본 논문은 표준 셀을 효율적으로 배치하는 하이브리드 기법을 제시한다. 제시한 기법에서는 레이아웃 영역을 그리드로 분할하고, 분할된 그리드의 각 빈에 셀을 배치함으로 광역 배치를 얻는다. 광역배치를 얻은 후 Relaxation-Based Local Search (RBLS)라 불리는 해석적 최적 기법[12]을 사용하여 배치를 개선시킨다. 이 기법을 사용하면 배치 전체를 개괄적으로 볼 수 있게 되어 배치가 국부 최적에 빠지지 않도록 할 수 있다. 이 기법의 핵심은 중복을 해결하기 위한 매우 효율적인 적법화 알고리즘이라고 볼 수 있는데, 이에 대해 본 논문은 자세히 설명한다. 광역배치가 더 이상 개선되지 않으면 이를 상세 배치로 변환시킨다. 상세 배치를 얻은 후 “최적 인터리빙”이라 불리는 기법[13]을 사용하여 이를 더욱 개선시킨다. MCNC 벤치마킹 회로에 대한 실험 결과는 [14]에서 보여준 Feng Shui의 결과와 필적할 만하다. This paper presents an efficient hybrid techniques for a standard cell placement. The prototype tool adopts a middle-down methodology in which angrid is imposed over the layout area and cells are assigned to bins forming a global placement. The optimization technique applied in this phase is based on the Relaxation-Based Local Search (RBLS) framework [12] in which a combinatorial search mechanism is driven by an analytical engine. This enables a more global view of the problem and results in complex modifications of the placement in a single search "move." Details of this approach including a novel placement legalization procedure are presented. When a global placement converges, a detailed placement is formed and further optimized by the optimal interleaving technique[13]. Experimental results on MCNC benchmarking circuits are presented and compared with the Feng Shui's results in [14]. Solution qualities are almost the same as the Feng Shui's results

계층 구조를 사용한 차원 분석

허성우(Sung Woo Hur),김종훈(Jong Hoon Kim),김은주(Eun Ju Kim),김명호(Myung Ho Kim) 한국정보과학회 1990 한국정보과학회 학술발표논문집 Vol.17 No.1

차원 속성을 가진 수치 연산을 지원하기 위하여 C++의 derived class와 operator overloading을 활용한 새로운 차원 분석 프로그램을 구현하였다. 여러 종류의 차원은 “차원 - 차원” 계층 관계를 형성하고 있는 것으로 모델링되어 derived class로 구현된다. C++의 derived class를 사용한 구현은 차원에 관련된 정보를 효과적으로 은폐할 수 있다. 또한 operator overloading을 활용함으로써 기존의 수치적 자료형에 적용되는 모든 연산을 차원 속성을 가진 데이타에도 문법적 수정없이 그대로 사용할 수 있다. 본 연구에서는 특히 동일 차원내의 서로 다른 단위의 표현을 쉽게 하기 위하여 “차원 - 단위” 계층 구조를 제시 하였다. 계층 구조에서 임의의 차원에 새로운 단위를 추가하기 위해서는 그 차원의 기본 단위에 대한 scale만 추가로 제공하면 되므로 사용자는 차원 분석 프로그램의 구현에 관한 사항을 전혀 인식할 필요가 없다.

단순 격자 상에서 효과적인 이동 연산을 이용한 평면계획 알고리즘

허성우(Sung-Woo Hur) 한국정보기술학회 2010 한국정보기술학회논문지 Vol.8 No.12

Most existing floorplan techniques use variable models to represent the topology of modules and suggest appropriate algorithms for floorplan on the models. This paper uses a grid model, which is much simpler than any other models, and suggests very effective move operations in the solution space in the simulated annealing frame. The key idea of the suggested effective move operations can be summarized as follows. On the compacted floorplan, it searches floorplan and determines where white (or dead) spaces are. Then, it selects one or two modules around those white spaces and move it to other location in order to change the shape of the white space. Experimental results prove that the suggested technique is comparable with the state-of-the-art techniques.