성능지향 FPGA 배선방법에 관한 연구

임종석(Chong Suck Rim) 한국정보과학회 1998 정보과학회논문지 : 시스템 및 이론 Vol.25 No.6

본 논문에서는 FPGA 설계중 배선을 위한 두 단계 배선 방법을 제안한다. 두 단계 배선이란 개략배선 후 상세배선을 수행하는 배선을 의미한다. 본 논문에서 제안하는 배선방법은 개략배선단계에서 배선밀도, 배선길이 그리고 지연시간 등을 고려하여 배선을 수행하고 이 결과를 토대로 상세배선 단계에서 각 네트의 최종 배선경로를 결정한다. 제안한 배선방법은 일반적으로 그 최적화에 많은 연산이 필요한 사항들을 상세배선단계에 비하여 그 자료량이 매우 적은 개략배선단계에서 처리하도록 하여 효율적이며 여러 밴치마크 회로에 대한 실험결과도 기존의 방법에 비하여 비교할만하다. 배선에서 지연시간 계산은 Elmore 지연시간 모델을 사용하였으며 LBA(Limit Bumping Algorithm)을 사용하여 각 커넥션에 대한 지연시간의 상한값을 계산하여 이를 만족시킬 수 있도록 배선을 수행하였다. In this paper, we propose a two-step routing method for FPGAs. Two-step routing is a routing method which performs detailed routing after global routing, The proposed routing method first finds global routing patterns considering routing density, length and delay in the global routing stage, and then finds the detailed routing path for each net based on the global routing results. Since all the optimizations are doing in the global routing stage in which the size of data is relatively smaller than that of detailed routing stage, the proposed routing method is efficient and the experimental results are very comparable to other previous results. The routing delay is considered by Elmore delay model and LBA(Limit Bumping Algorithm) is used for calculating delay upper bounds for the connections. and the routing is done to satisfy the upper bounds.

1-Steiner 트리 알고리즘을 응용한 시간 지향 배선 방법

심호,임종석,Shim, Ho,Rim, Chong-Suck 대한전자공학회 2002 電子工學會論文誌-SD (Semiconductor and devices) Vol.39 No.3

본 논문에서는 1-Steiner 휴리스틱 알고리즘을 응용하여 단일 소스 네트와 다중 소스 네트를 배선하는 두 가지 시간 지향(timing-driven) 배선 방법을 제안한다. 이 방법은1-Steiner 휴리스틱 알고리즘의 계산값 (cost)을 지연시간으로 수정한 것으로 이 방법의 특징은 모든 터미널이 임계터미널인 경우와 또 임계터미널이 부분적으로 존재하는 경우의 단일 소스 네트와 다중 소스 네트를 배선하는 데 동시 적용할 수 있다는 점이다. 실험결과 단일 소스를 배선하는 알고리즘은 기존의 SERT와 SERT-C에 비해 지연시간이 각각 평균 2.1%, 10.6% 감소하는 성능을 보였다. 그리고 다중 소스를 배선하는 알고리즘은 기존의 MCMD A-tree 알고리즘과 비교했을 때 모든 소스, 터미널 쌍이 임계쌍(critical pair)일 경우는 최대 지연 시간이 평균 2.7% 증가했지만 부분적인 임계쌍이 존재할 때는 최대 지연 시간이 평균 1.4% 감소하는 유사한 결과를 도출한다. In this paper, we propose two timing-driven routing algorithms for single-source net and multi-source net as applications of 1-Steiner heuristic algorithm. Using the method of substituting the cost of 1-Steiner heuristic algorithms with interconnection delay, our routing algorithms can route both single-source net and multi-source net which have all critical source-terminal pairs or one critical pair efficiently Our single-source net routing algorithm reduced the average maximum interconnection delay by up to 2.1% as compared with previous single-source routing algorithm, SERT, and 10.6% as compared with SERT-C. and Our multi-source net routing algorithm increased the average maximum interconnection delay by up to 2.7% as compared with MCMD A-tree, but outperforms it by up to average 1.4% when the signal net has only subset of critical node pairs.

접속 각도 조정을 통한 신뢰성 있는 저 손실 현장조립 광커넥터 설계

박병철(Byung-chul Park),임종석(Chong-Suck Rim),정준호(Jun-ho Jung) 大韓電子工學會 2011 電子工學會論文誌-SD (Semiconductor and devices) Vol.48 No.9

본 논문에서는 장거리, 저 손실 FTTH 구성에 필요한 현장조립 광커넥터(FIOC)의 접속 신뢰성과 성능 향상을 위한 방법을 제시한다. 이를 위해 FIOC의 내부 광섬유(inner fiber)와 외부 광섬유(field fiber)의 접속 면 각도를 최적화하여 별도의 각도 맞춤 툴과 광섬유 유각 절단기(fiber angled cleaver) 없이 조립하여도 저 손실 접속이 가능하도록 하였다. FIOC의 내부 광섬유(inner fiber)의 각도를 angled cleaver를 이용해 2˚로 고정하고, 외부 광섬유(field fiber)는 일반 광섬유 절단기를 이용해 오차를 포함해서 0˚~1˚의 각도로 서로 접속하여 삽입손실은 0.3㏈ 이내로 줄이고, 반사손실은 -60㏈ 이하를 유지 할 수 있도록 하였다. In this paper, we propose a design method for a reliable and improved field-installable optical connectors(FIOC) which are needed for long-distance and low loss FTTH configuration. To this end, we optimize the angle of splicing between the inner fiber and the field fiber of the FIOC, so that the low loss connection of optical fibers is possible without using any angle alignment tools as well as angled cleavers. More precisely, we set the cutting angle of the inner filber and the field fiber to be 2˚ by using an angled cleaver and 0˚~1˚ by using a general fiber cutter, respectively. Splicing these two optical fibers without any further adjustment, we can keep the insertion loss within 0.3㏈ and the reflection loss within -60㏈.

전원 잡음을 줄이기 위한 평면계획 단계에서의 Decoupling Capacitance 할당

허창룡,임종석,Heo Chang-Ryong,Rim Chong-Suck 대한전자공학회 2005 電子工學會論文誌-SD (Semiconductor and devices) Vol.42 No.9

본 논문에서는 평면계획 단계에서 모듈의 전원 잡음을 줄이기 위해 필요한 decoupling capacitance를 효과적으로 할당하는 방법을 제시한다. 먼저, 각 모듈의 decoupling capacitance가 과대평가되고 추가 면적 삽입으로 모듈의 전원 잡음이 변하는 기존 접근 방법의 문제점을 살펴보고, 이를 해결할 수 있는 새로운 방법을 제시한다. 또한, 선형프로그래밍 방법보다 빠른 시간 내에 decoupling capacitance 면적을 위한 빈 공간을 할당하는 간단한 휴리스틱 방법을 제안한다. 실험결과에서 제시된 방법은 Zhao[4]의 방법과 비교하여 decoupling capacitance 면적이 평균 $7.9\%$ 감소하고, 이로 인해 평면계획 결과의 전체 면적과 와이어 길이가 감소하였다. 또한, 추가 면적 삽입으로 인한 모듈의 전원 잡음 문제를 잘 해결하고 있음을 확인하였다. 수행시간 비교에서는 평균 $11.6\%$의 향상을 보였다. This paper proposes a method which efficiently allocates decoupling capacitance to reduce power supply noise at the floorplan level. We observe problems of previous approach that the decoupling capacitance of each module was overestimated and the power supply noises of modules were changed by inserting additional area for decoupling capacitance, and then suggest a new approach. And, we also present a simple heuristic method which can effectively allocate white space modules for decoupling capacitance area within more faster time instead of LP technique. Experimental results show that our approach can reduce the area of decoupling capacitance to average 7.9 percent compared with Zhao's approach in [4]. Therefore both total area and wire length of nniflm result are decreased. Also, we confirm that our approach solves well the problem caused by inserting additional area. In execution time comparison, our approach shows average 11.6 percent improvement.

다중칩 모듈 설계를 위한 Gridless 배선기

이태선,임종석,Lee, Tae-Sun,Rim, Chong-Suck 대한전자공학회 1999 電子工學會論文誌, C Vol.c36 No.9

본 논문에서는 다중칩 모듈 설계를 위한 gridless 배선 방법을 제안한다. 제안하는 배선 방법에서는 배선상태를 표현하기 위해 배선격자 (grid) 대신 corner stitching 자료구조를 사용함으로써 핀들의 위치 제한을 없애고, 네트의 특성에 맞는 와이어 폭을 선택할 수 있다. 또한 비아보다 그 폭이 작은 와이어들로 인해 남는 공간을 다른 네트의 배선에 이용하여 배선영역을 최대한 낭비 없이 이용한다. 배선격자를 사용하지 않는 배선방법은 배선격자를 기반으로 하는 배선 방법에 배해 복잡하고 어렵다. 더구나 다중칩 모듈과 같이 배선 영역이 크고 배선층의 갯수가 많은 배선 문제일 경우 배선 속도는 배선 가능성을 결정하는 중요한 요소가 된다. 그러나 제안하는 배선 방법은 빠른 속도가 증명된 SEGRA의 배선 알고리즘과 효율적인 자료구조의 특성을 적절히 이용함으로써 배선격자를 기반으로 하는 배선 방법 보다 빠른 속도와 그리 떨어지지 않는 배선 결과를 보인다. In this paper, we present a gridless router for MultiChip Modules (MCM). Because our router uses corner stitching data structures, not a routing grid, to represent the routings status, it allows arbitrary location of pins, and routes variable-width wires, without a considerable waste of area from bulky vias. A routing speed is a very important factor because a gridless routing approach is known its computation is hard and complex, and MCM routing problem has so large routing area and layers. Our router completes the routing faster than the most of previously reported grid-based routers, with comparable routing result, by using SEGRAs routing algorithm whose very fast speed is proved, and the characteristics of the effective data structure.

Marjolin´s Ulcer 2예

임수덕,허충림,우종설,서웅석,윤재일,지형인 대한피부과학회 1982 大韓皮膚科學會誌 Vol.20 No.6

Marjolin's ulcer seated upon an old cicatrix, especially old burn scar, which may chiefly degenerated into a squamous cell carcinoma with propensity for metastasis. We are experienced two cases of Marjolins ulcer recently. A 54-year-old male who had a Marjolins ulcer(15±×40cm) on his left lower extremity. He was experienced burn at the age of eight and rice sized ulcer was developed at the site of burn scar about 21 years ago. The ulcer progressively enlarged in size to reach 15x40cm for 21 years. The pathologic diagnosia was squamous cell carcinoma grade 1, but cancer cells invaded to deep dermie and subcutaneous tissues. Severe skin lesion and irreversible osteoporotic degeneration on knee joint of affected limb were present. So he was treated by high above knee amputation. Another 58-year-old female who had a Marjolins ulcer(10x20cm) on her right lower extremity. She was experienced burn at the age of forty eight and bean sized ulcer was developed at the site of burn scar about 1 year ago. The pathological diagnosis was squamous cell carcinoma grade 1 and invasian of cancer cells was limited upper dermis. On lymph node biopsy, the histological diagnosis was within normal limit. So she was treated radical surgical excision with split thickness skin graft(Mesh).

처리량 기반 평면계획을 위한 처리량 계산 방법

강민성(Min-Sung Kang),임종석(Chong-Suck Rim) 대한전자공학회 2007 電子工學會論文誌-SD (Semiconductor and devices) Vol.44 No.12

반도체 공정 기술의 발전으로 인한 개략 배선 지연시간의 증가는 고성능 시스템의 설계를 어렵게 하고 있다. 이 문제를 해결하기 위해 배선에 파이프라인 요소를 삽입하는 방법이 있으나 시스템의 타이밍을 변화시켜 시스템의 기능성을 보장할 수 없다. LIP(Latency Insensitive Protocol)는 임의의 파이프라인 요소의 삽입에 대해 기능성을 보장하지만 처리량이 저하된다. 처리량 저하를 줄이기 위해서는 평면계획 단계에서 처리량을 고려하여 블록을 배치하여야 한다. 이러한 평면계획을 가능하게 하기 위해서 새로운 처리량 계산 방법을 제안하고 평면계획의 비용함수에 적용하였다. 실험 결과, 기존의 휴리스틱 처리량 평가 방법을 적용한 평면계획에 비해 처리량이 평균 16.97% 향상되었다. As VLSI technology scales to nano-meter order, relatively increasing global wire-delay has added complexity to system design. Global wire-delay could be reduced by inserting pipeline-elements onto wire but it should be coupled with LIP(Latency Intensive Protocol) to have correct system timing. This combination however, drops the throughput although it ensures system functionality. In this paper, we propose a computation method useful for minimizing throughput deterioration when pipeline-elements are inserted to reduce global wire-delay. We apply this method while placing blocks in the floorplanning stage. When the necessary for this computation is reflected on the floorplanning cost function, the throughput increases by 16.97% on the average when compared with the floorplanning that uses the conventional heuristic throughput-evaluation-method.

터미날이 내장된 채널에서의 단층 채널 배선

최연경(Choi Thon Kyong),임종석(Rim Chong Suck) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.7

본 논문에서는 게이트 어레이 또는 sea-of-gates 레이아웃 형태에서의 기능 셀 자동 생성에 적용할 수 있는 디퓨션 채널 배선 문제를 소개하고 이 문제에 대한 복잡도 분석 결과 및 그 해결 방안을 기술한다. 디퓨션 채널 배선 문제는 기존의 채널 배선 문제와는 달리 터미날이 채널의 위, 아래 뿐 아니라 채널의 내부에도 존재하는 채널에서의 단층 배선 문제이다. 본 논문에서는 먼저 주어진 각 네트를 단 하나의 수평 세그먼트를 존재하는 채널에서의 단층 배선 문제이다. 본 논문에서는 먼저 주어진 각 네트를 단 하나의 수평 세그먼트를 사용하여 배선하도록 제한을 가할 경우 소개한 디퓨션 채널 배선 문제가 NP-hard 임을 보인다. 이러한 결과를 볼 때 디퓨션 채널 배선 문제를 다항 시간 내에 해결하기가 대단히 어렵고 따라서 이 문제를 해결하기 위한 효율적인 휴리스틱 알고리즘을 제안한다. 제안한 알고리즘을 구현하여 임의로 생성한 다수의 시험 데이타에 대하여 실험한 결과, 대부분의 경우에 최적의 배선 결과를 얻었다. In this paper we first introduce the so called diffusion channel routing problem which may arise in the functional cell generation in the gate array or the sea-of-gates layout styles The diffusion channel routing problem is a single layer routing problem for the channel which has terminals inside the channel as well as on the top and bottom of the channel. We then show that the diffusion channel routing problem is NP-hard if only one horizontal segment is allowed in the routing of each net. Therefore, we may conclude that it is unlikely to find an optimal solution in polynomial time and hence we propose a heuristic algorithm for the diffusion channel routing problem. For more than twenty randomly generated test examples. the algorithm routed with the minimum number of horizontal tracks for most of them.

방향 그래프에서의 최소 컷 선형 배열 및 최소 컷 이분할 문제의 복잡도 분석

최연경(Yhon Kyong Choi),임종석(Chong Suck Rim) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.10

무방향 그래프 G=(V, E)에서 최소 컷 선형 배열 문제는 V의 정점들을 수평선상에 배열하되 두 인접한 정점간에 수직선을 그렸을 때 그를 지나는 에지 비용의 합의 최대값을 최소화하는 문제이며, 최소 컷 이분할 문제는 정점의 집합 V를 그들간에 연결된 에지 비용의 합을 최소화하도록 두 부분으로 균등하게 분할하는 문제이다. 이들 두 문제는 일반적으로 NP-hard로 잘 알려져 있다. 본 논문에서는 이러한 두 문제를 방향 그래프로 확대하여 정의하고 이들의 복잡도 분석 결과를 기술한다. The minimum-cut linear arrangement and the minimum-cut bipartition problems in undirected graphs are well-known NP-hard problems. In this paper, we extend these problems in directed graphs and present the complexity results for them Namely, we show that the newly defined minimum-cut linear arrangement and minimum-cut bipartition problems are NP-hard in directed graphs.

고정블록을 포함한 CBL 기반 평면계획

강상구(Sang Ku Kang),임종석(Chong Suck Rim) 한국정보과학회 2009 정보과학회논문지 : 시스템 및 이론 Vol.36 No.3

본 논문에서는 고정 블록이 포함된 회로를 대상으로 하는 새로운 CBL 기반 평면계획 방법을 제안한다. 기존의 CBL 기반의 고정블록 평면계획의 문제점을 파악하고 이를 개선하였다. 제안한 방법은 자유 블록 만으로 구성된 CBL에 고정블록을 삽입하여 원래 CBL과 그 위상이 유사하고 패킹이 가능한 새로운 CBL을 만드는 방법으로 이를 시뮬레이티드 어닐링에 적용하여 평면계획을 수행한다. 실험결과는 우리가 제안한 평면계획 방법이 고정블록을 효과적이고 효율적으로 배치할 수 있음을 보여준다. In this paper we propose a new CBL-based floorplan method that accommodates pre-placed blocks. We identify the problem of the previous CBL-based pre-placed block floorplan method, and suggest the solution method of this problem. In our method, CBLs consisting of only free blocks are perturbed and maintained during the simulated annealing. Pre-placed blocks are inserted during packing in such a way that the topology of the CBL after insertion of a pre-placed block resembles the topology before insertion. Thus, even with the inclusion of pre-placed blocks, the searching effort via simulated annealing yields acceptable results. Experimental results show that our floorplan method places pre-placed blocks effectively and efficiently.