회로지연을 최소화하는 회로집단화 알고리즘 개발

김정환,이창희 啓明專門大學 産業開發硏究所 1999 啓明硏究論叢 Vol.17 No.2

본 논문에서는 다중칩을 구현하기 위한 회로 분할 문제를 다룬다. 본 논문에서는 회로지연을 감소시킬 수 있는 논리 게이트의 복제를 허용한다. 논리 게이트의 복제를 허용하는 회로 분할을 회로 집단화라고 한다. 본 논문에서는 일반적 지연 모델을 사용해서 영역 및 핀수 제한을 모두 만족하면서 회로지연을 최소화하는 회로 집단화 알고리즘을 제안한다. 이 알고리즘은 영역 제한 혹은 핀수 제한만 있을 때는 최적의 회로지연을 실현하지만, 영역 및 핀수 제한이 모두 주어질 때는 대부분의 경우에 최적의 회로 지연을 실현한다. 제안 알고리즘을 벤치마크회로들에 대해 시험하여 최적 혹은 거의 최적의 회로지연을 가짐을 확인했다. We consider the problem of circuit paritioning for multiple-chip implementation. We allow duplication of logic gates as it would reduce circuit delay. Circuit partitioning with duplication of logic gates is also called circuit clustering. In this paper, we present a circuit clustering algorithm that minimizes circuit delay subject to both area and pm constraints on each chip, using the general delay model. We develop a repeated network cut technique for finding a cluster that is bounded by both area and pin constraints. Our algorithm achieves optimal delay under either the area constraint only or the pm constraint only. Under both area and pin constraints, our algorithm achieves optimal delay m most cases. We tested our algorithm on a set of benchmark circuits and consistently obtained optimal or near-optimal delays.

회로 연결성에 따른 회로 집단화 휴리스틱 연구

김정환 啓明專門大學 産業開發硏究所 2000 啓明硏究論叢 Vol.18 No.2

본 논문에서는 회로 연결성에 근거한 집단화 휴리스틱을 제안한다. 이 방법은 거의 같은 크기의 작은 클러스터를 많이 생성한다. 2 단계 분할 휴리스틱의 1 단계로, 제안한 집단화 휴리스틱을 적용한다. 본래의 회로와 집단화된 회로에 각각 Sanchis의 교환 분할 휴리스틱을 적용하였다. 실험 결과는 본 논문에서 제안한 2 단계 휴리스틱이 집단화를 적용하지 않은 1단계 휴리스틱보다 빠른 시간 내에 분할을 생성함을 보여 준다. In this paper, I propose a clustering heuristic based on circuit connectivity. It produces a large number of small clusters of nearly equal size. I apply proposed clustering heuristic to a two phase partitioning heuristic as first phase. Sanchis' interchange partitioning heuristic is applied to the original circuit and to a clustered circuit. Experimental results demonstrate my two phase heuristic produces better partitions with less computational effort than one phase heuristic.

회로 분할을 위한 어댑티드 유전자 알고리즘 연구

송호정(Ho-Jeong Song),김현기(Hyun-Gi Kim) 한국콘텐츠학회 2021 한국콘텐츠학회논문지 Vol.21 No.7

VLSI 설계에서의 분할(partitioning)은 기능의 최적화를 위하여 설계하고자 하는 회로의 그룹화(grouping)하는 단계로서 레이아웃(layout)에서 면적과 전파지연의 최소화를 위해 함께 배치할 소자를 결정하는 문제이다. 이러한 분할 문제에서 해를 얻기 위해 사용되는 알고리즘은 Kernighan-Lin 알고리즘, Fiduccia Mattheyses heuristic, 시뮬레이티드 어닐링, 유전자 알고리즘 등의 방식이 이용된다. 본 논문에서는 회로 분할 문제에 대하여 유전자 알고리즘과 확률 진화 알고리즘을 결합한 어댑티드 유전자 알고리즘을 이용한 해 공간 탐색(solution space search) 방식을 제안하였으며, 제안한 방식을 유전자 알고리즘 및 시뮬레이티드 어닐링 방식과 비교, 분석하였고, 어댑티드 유전자 알고리즘이 시뮬레이티드 어닐링 및 유전자 알고리즘보다 더 효과적으로 최적해에 근접하는 것을 알 수 있었다. In VLSI design, partitioning is a task of clustering objects into groups so that a given objective circuit is optimized. It is used at the layout level to find strongly connected components that can be placed together in order to minimize the layout area and propagation delay. The most popular algorithms for partitioning include the Kernighan-Lin algorithm, Fiduccia-Mattheyses heuristic and simulated annealing. In this paper, we propose a adapted genetic algorithm searching solution space for the circuit partitioning problem, and then compare it with simulated annealing and genetic algorithm by analyzing the results of implementation. As a result, it was found that an adaptive genetic algorithm approaches the optimal solution more effectively than the simulated annealing and genetic algorithm.

논리 정보를 이용한 회로분할 알고리즘 연구

김정환,장영식,이성준 啓明專門大學 産業開發硏究所 2001 啓明硏究論叢 Vol.19 No.1

일반적으로 분할은 그래프 정보를 이용하여 이루어졌으나 논리 정보의 유용성을 보이기 위한 여러 방법들도 제안되었다. 본 논문에서는 분할된 회로의 절단집합에서, 절단선을 두번 이상 지나는 경로는 개선이 가능하다고 가정하고, 선택된 경로에 논리적 정보를 이용하여 변환함으로써 절단 집합의 크기를 줄일 수 있음을 보이고 있다. 잘 알려진 FM 알고리즘을 이용하여 초기분할을 만들고, 논리정보를 이용하여 선택된 개선 가능 경로를 기능적으로 동일한 회로로 변환하였다. 실험 결과에 따르면, 제안 알고리즘은 약 15%의 절단 집합 축소를 보여준다. Generally, graph information is used for partitioning but, various partitioning method have been proposed to show availability of logic information of circuit. In this paper, we suggest that the path to go through a cut-line more than twice can be improved and show that the size of cut-set is reduced by decomposing the path using logic information. First, we perform initial partitioning for a given circuit using FM algorithm. and then transform into the functionally equivalent circuit for the selected improbable path using logic information. This partitioning algorithm using logic information shows 15% reduction of cut-set size compared to FM algorithm.

네트워크 분할에 의한 역전파 신경회로망의 성능평가 및 그것의 병렬 구현

구탁모 경동전문대학 1995 論文集 Vol.4 No.-

다중 신경회로망을 이용한 SDRE 기반 유도탄 적응 조종루프 설계

이재호,이용우,김유단,문관영,전병을 한국항공우주학회 2014 한국항공우주학회 학술발표회 논문집 Vol.2014 No.11

유도탄이 급격히 가속되는 추진 구간에서는 비선형 공력특성과 급격한 파라미터 변화가 동반될 수 있다. 이때 적절한 조종성능을 보장하기 위해서는 시스템의 비선형성을 고려할 수 있도록 비선형 제어기를 설계해야 할 필요가 있다. 본 연구에서는 SDRE(State Dependent Riccati Equation) 기법을 이용하여 유도탄의 자세각속도 조종루프를 설계하였다. 모델링 오차 및 공력 불확실성에 대한 조종루프의 강건성을 향상시키고자 신경회로망 기반의 보조제어기를 설계하였다. 이 과정에서 분할정복 알고리즘 기반의 다중 신경회로망을 적용하여, 세 개의 독립적인 신경회로망이 불확실성을 모사하는 구조를 설계하였다. 제안된 조종루프의 성능을 검토하기 위하여 수치 시뮬레이션을 수행하였다. Large nonlinearities and rapid change of parameters may degenerate the performance of the missile autopilot during the boost-phase. To guarantee the control performance, an autopilot should be designed considering the nonlinearities of the missile system. In this study, SDRE(State Dependent Riccati Equation) based adaptive controller is designed. In addition to the baseline SDRE controller, neural network based adaptive controller is designed to increase the robustness of the autopilot with respect to modeling error and aerodynamic uncertainties. In particular, a modular neural networks based on the divide-and-conquer algorithm is applied, meanwhile, three independent neural networks are used to estimate those uncertainties. Numerical simulation is performed to demonstrate the performance of the proposed controller.

신경 회로망을 이용한 자궁 경부 세포진 영상의 영역 분할에 관한 연구

김선아,김백섭 대한의용생체공학회 2001 의공학회지 Vol.22 No.3

This paper proposes a region segmenting method for the Pap-smear image. The proposed method uses a pixel classifier based on neural network, which consists of four stages : preprocessing, feature extraction, region segmentation and postprocessing. In the preprocessing stage, brightness value is normalized by histogram stretching. In the feature extraction stage, total 36 features are extracted from $3{\times}3$ or $5{\times}5$ window. In the region segmentation stage, each pixel which is associated with 36 features, is classified into 3 groups : nucleus, cytoplasm and background. The backpropagation network is used for classification. In the postprocessing stage, the pixel, which have been rejected by the above classifier, are re-classified by the relaxation algorithm. It has been shown experimentally that the proposed method finds the nucleus region accurately and it can find the cytoplasm region too.

Exhaustive 테스트 기법을 사용한 효율적 병렬테스팅

김우완 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.30 No.3

In recent years the complexity of digital systems has increased dramatically. Although semiconductor manufacturers try to ensure that their products are reliable, it is almost impossible not to have faults somewhere in a system at any given time. As complexity of circuits increases, the necessity of more efficient organized and automated methods for test generation is growing. But, up to now, most of popular and extensive methods for test generation nay be those which sequentially produce an output for an input pattern. They inevitably require a lot of time to search each fault in a system. In this paper, corresponding test patterns are generated through the partitioning method among those based on the exhaustive method. In addition, the method, which can discovers faults faster than other ones that have been proposed ever by inserting a pattern in parallel, is designed and implemented. 최근 몇 년 동안 디지털 시스템이 복잡성은 아주 빠르게 증가하고 있다. 비록 반도체 제조업자들이 제품에 대한 신뢰성을 높이려고 노력하고 있지만 어느 때에 시스템이 어딘가에서 결함이 발생할 것이라는 것을 알기는 불가능하다. 이렇듯이 회로가 복잡화함에 따라 테스트 생성(test generation)에 대한 잘 정리되어 있고 자동화된 방법이 필요하게 되었다. 하지만 현재 광범위하게 사용하고 있는 방법중 대부분은 한번에 하나씩의 패턴만을 넣어서 처리하는 방식이다. 이는 각각의 결함에 대해서 탐색하는데 많은 시간을 낭비하게 된다. 본 논문에서는 Exhaustive 방법을 사용하는 테스트 패턴 생성 방법 중에서 분할 기법을 적용하여 테스트 패턴을 생성한다. 또한 이 패턴을 이용하여 병렬로 패턴을 삽입함으로써 더욱 빠르게 결함을 발견할 수 있는 방법을 설계 및 구현한다.

비교사 블록-기반 군집에 의한 다중 텍스쳐 영상 인식

이우범,김욱현,Lee, Woo-Beom,Kim, Wook-Hyun 한국정보처리학회 2002 정보처리학회논문지B Vol.9 No.3

Texture analysis is an important technique in many image understanding areas, such as perception of surface, object, shape and depth. But the previous works are intend to the issue of only texture segment, that is not capable of acquiring recognition information. No unsupervised method is basased on the recognition of texture in image. we propose a novel approach for efficient texture image analysis that uses unsupervised learning schemes for the texture recognition. The self-organization neural network for multiple texture image identification is based on block-based clustering and merging. The texture features used are the angle and magnitude in orientation-field that might be different from the sample textures. In order to show the performance of the proposed system, After we have attempted to build a various texture images. The final segmentation is achieved by using efficient edge detection algorithm applying to block-based dilation. The experimental results show that the performance of the system Is very successful. 텍스쳐 분석은 표면, 물체, 모양, 깊이 인식 등의 많은 영상 이해 분야에서 활용되는 가장 중요한 인식 기술 중의 하나이다. 그러나 기존의 방법들은 다중 텍스쳐 영상에 내재된 텍스쳐 성분의 인식 정보를 활용할 수 없는 분할만을 목적으로 하고 있으며, 내재된 텍스쳐 인식을 기반으로 하는 비교사적인 방법에 관한 연구는 거의 이루어지고 있지 않은 실정이다. 따라서 본 논문에서는 텍스쳐 성분을 방향장(orientation-field) 특징 정보인 방향각과 방향강도로 정의하고 블록-기반 자기조직화 신경회로망에 의해서 비교사적으로 영상 내에 존재하는 텍스쳐 영역을 군화(clustering) 및 통합(merging) 처리에 의해서 식별한다. 또한 제안된 알고리즘의 성능 평가를 위해서는 다양한 형태의 다중 텍스쳐 영상을 생성하여 블록 기반의 불림(dilation) 및 윤곽 검출 과정을 통해서 영상에 내재하는 텍스쳐 영역을 분할함으로써 그 유효성을 보인다.

전기자동차를 위한 무선전력전송 시스템의 효율증가

이승규(Seunggyu Lee),Hoang Minh Huy,변영재(Franklin Bien),김영수(Youngsu Kim) 한국자동차공학회 2011 한국자동차공학회 지부 학술대회 논문집 Vol.2011 No.10-2

본 연구에서는 전기자동차에 무선으로 전력을 전송하는 방법과 그에 대한 효율을 증가 시킬 수 있는 방식을 제안하였다. 자기공명형 무선전력전송 방식에서 등가적 회로분석 방식을 통하여 주파수 분할 현상을 증명하였는데 이는 두 개의 공진기가 일정 이하의 거리에서는 공진 주파수의 변화를 통하여 효율의 보상할 수 있는 가능성을 보였으며 두 공진기의 기구적 불일치 상황에서 임피던스 정합희로를 사 용함으로 전송효율의 개선을 보였다. 10.14MHz의 공진 주파수에서 50%의 기구적 불일치를 가질 때 측정 결과, 50%의 효율 보상을 얻을 수 있음을 확인하였다.