고성능 저전력 모바일 컴퓨팅 제품을 위한 MTCMOS ASIC 설계 방식

김교선,원효식,Kim Kyosun,Won Hyo-Sig 대한전자공학회 2005 電子工學會論文誌-SD (Semiconductor and devices) Vol.42 No.2

The Multi-Threshold CMOS (MTCMOS) technology provides a solution to the high performance and low power design requirements of mobile computing applications. In this paper, we (i) motivate the post-mask-tooling performance enhancement technique combined with the MTCMOS leakage current suppression technology, and (ii) develop a practical MTCMOS ASIC design methodology which fine-tunes and integrates best-in-class techniques and commercially available tools to fix the new design issues related to the MTCMOS technology. Towards validating the proposed techniques, a Personal Digital Assistant (PDA) processor has been implemented using the methodology, and a 0.18um Process. The fabricated PDA processor operates at 333MHz which has been improved about $23\%$ at no additional cost of redesign and masks, and consumes about 2uW of standby mode leakage power which could have been three orders of magnitude larger if the MTCMOS technology was not applied. 다중 문턱 전압 CMOS (Multi-Threshold voltage CMOS, MTCMOS) 기술은 모바일 컴퓨팅 제품에서 요구되는 고성능 저전력 특성을 제공한다. 본 논문에서는 먼저 MTCMOS의 누설 전류 차단 기술과 이온 주입 농도 조정을 융합한 마스크 제작 사후 성능 향상 기법을 소개한다. 그리고 MTCMOS 기술에 관련하여 발생하는 새로운 설계 이슈들을 해결하는 최신 기술들을 집적하여 개발된 MTCMOS ASIC 설계 방법론을 제시한다. 특히, 현존하는 상업용 소프트웨어로 설계 흐름을 구현하고 있어 실용성이 높다. 제안된 기법들의 효용성을 검증하기 위해 0.18um 기술에 적용하여 PDA 프로세서를 구현하였다. 제작된 PDA 프로세서는 333MHz에서 동작하였다. 이는 재설계 및 마스크 제작비용 없이 단지 이온 주입 농도 조정으로 약 $23\%$의 추가적인 성능 향상 효과를 나타낸 성과이다. 이 때, 대기 시 누설 전력 소모는 2uW를 유지함으로써 MTCMOS 기술 적용 전 대비 수천 배 억제하는 효과를 얻었다.

Field Programmable Stateful Logic Array 패브릭 매핑 및 배치

김교선,Kim, Kyosun 대한전자공학회 2012 전자공학회논문지 Vol.50 No.8

최근 무어의 법칙을 연장시킬 시스템 집적 기술로서 Field Programmable Stateful Logic Array (FPSLA)가 제안되었다. 본 논문은 FPSLA의 설계 자동화 절차를 확립하고 논리 합성, 동기화, 물리적 매핑, 자동 배치 등의 접근 방법을 최초로 제시한다. 특히, 동기화를 통해 배치를 1차원 문제로 축소한 후 비선형 최적화 기법을 개량한 개략 배치 모델 및 하향식 계층적 2분법을 이용한 배치 적법화 알고리즘을 제안하였다. 또한, 제안된 모델 및 알고리즘을 소프트웨어로 구현하여 ACM/SIGDA 벤치 마크 예제에 적용함으로써 그 유효성을 입증하였다. 이 소프트웨어에는 Fanout 수만큼 출력 상태를 같은 단의 멤리스터성 스위치에 복사해야 하는 FPSLA의 특성을 고려하여 최적화 단계 별로 넷을 하이퍼에지로 통합했다가 다시 에지로 분리하는 기법이 제안되었으며 약 18.4%의 추가적 최적화를 이룩했다. FPSLA의 출력 상태 복사는 논리 단 일부에 셀 밀도가 집중되는 문제를 노출했으며 단위 논리 게이트의 Fanin을 제한하는 기법으로 18.5% 감소 효과를 얻었다. FPSLA의 실용성 확보를 위해서는 우선 논리 합성 시 Fanin의 수가 일부 단에 집중되지 않도록 제약하는 방안을 개발하여야 한다. 또한, FPSLA 패브릭 구조를 이식하기 위해 대칭성이 감소된 나노와이어 크로스바가 형성하는 복잡한 그래프 상에서 수행되어야 하는 자동 배선의 효율성 연구도 필요하다. 이러한 툴 개발은 설계 자동화 자체뿐만 아니라 FPSLA의 패브릭 구조 개선에 필요한 실험에 유용한 평가 도구로서도 큰 역할을 할 것이다. Recently, the Field Programmable Stateful Logic Array (FPSLA) was proposed as one of the most promising system integration technologies which will extend the life of the Moore's law. This work is the first proposal of the FPSLA design automation flow, and the approaches to logic synthesis, synchronization, physical mapping, and automatic placement of the FPSLA designs. The synchronization at each gate for pipelining determines the x-coordinates of cells, and reduces the placement to 1-dimensional problems. The objective function and its gradients for the non-linear optimization of the net length and placement density have been remodeled for the reduced global placement problem. Also, a recursive algorithm has been proposed to legalize the placement by relaxing the density overflow of bipartite bin groups in a top-down hierarchical fashion. The proposed model and algorithm are implemented, and validated by applying them to the ACM/SIGDA benchmark designs. The output state of a gate in an FPSLA needs to be duplicated so that each fanout gate can be connected to a dedicated copy. This property has been taken into account by merging the duplicated nets into a hyperedge, and then, splitting the hyperedge into edges as the optimization progresses. This yields additional 18.4% of the cell count reduction in the most dense logic stage. The practicality of the FPSLA can be further enhanced primarily by incorporating into the logic synthesis the constraint to avoid the concentrated fains of gates on some logic stages. In addition, an efficient algorithm needs to be devised for the routing problem which is based on a complicated graph. The graph models the nanowire crossbar which is trimmed to be embedded into the FPSLA fabric, and therefore, asymmetric. These CAD tools can be used to evaluate the fabric efficiency during the architecture enhancement as well as automate the design.

FPGA를 위한 분석적 배치에서 사전 패킹, 조기 배치 고정 및 밀도 분석 다층화

김교선(Kyosun Kim) 대한전자공학회 2014 전자공학회논문지 Vol.51 No.10

기존 학계의 FPGA 툴 연구는 단순한 가상 아키텍처 모델 가정에 의존해 왔다. 이러한 제약을 극복하기 위한 첫걸음으로 분석적 배치 및 배치 적법화의 기본 알고리즘들을 상용 FPGA의 아키텍처에 적용하는 실제 상황에서 발생되는 이슈들을 도출하여 대안을 제시한 후 그 효과를 평가하였다. 먼저, 코어 사용률이 낮은 FPGA에서 배치된 셀들의 무게 중심이 칩 중심에서 벗어나는 현상이 발생할 수 있는데 이 변위를 최소화하는 함수를 분석적 배치의 목적 함수에 추가하였다. 또한 배치 밀도 평가의 정확도를 높이기 위해 셀 종류별로 별도의 밀도 행렬을 사용하는 다층 분석, 그리고 자원이 매우 한정된 블록의 조기 고정 방안을 제안하였다. 그밖에, 슬라이스 내에서 두 개의 플립플롭이 제어 핀들을 공유하기 때문에 발생하는 호환성 문제를 개선하기 위한 플립플롭 사전 패킹도 제안하였다. 제안된 기법은 상용 FPGA 아키텍처를 정확하게 모델링하고 수정 개선할 수 있는 K-FPGA 패브릭 평가 툴킷을 근간으로 구현되었으며 12개의 실용 예제에 적용하여 기존 방식에 비해 평균적으로 배선 길이 22%, 슬라이스 사용량 5%를 감축하는 효과를 확인하였다. 본 연구는 신규 FPGA 아키텍처 개발을 위한 최적화 CAD 툴 개발 연구의 기초가 될 것으로 기대한다. Previous academic research on FPGA tools has relied on simple imaginary models for the targeting architecture. As the first step to overcome such restriction, the issues on analytic placement and legalization which are applied to commercial FPGAs have been brought up, and several techniques to remedy them are presented, and evaluated. First of all, the center of gravity of the placed cells may be far displaced from the center of the chip during analytic placement. A function is proposed to be added to the objective function for minimizing this displacement. And then, the density map is expanded into multiple layers to accurately calculate the density distribution for each of the cell types. Early fixation is also proposed for the memory blocks which can be placed at limited sites in small numbers. Since two flip-flops share control pins in a slice, a compatibility constraint is introduced during legalization. Pre-packing compatible flip-flops is proposed as a proactive step. The proposed techniques are implemented on the K-FPGA fabric evaluation framework in which commercial architectures can be precisely modeled, and modified for enhancement, and validated on twelve industrial strength examples. The placement results show that the proposed techniques have reduced the wire length by 22%, and the slice usage by 5% on average. This research is expected to be a development basis of the optimization CAD tools for new as well as the state-of-the-art FPGA architectures.

K-FPGA 패브릭 구조의 평가 툴킷

김교선(Kyosun Kim) 大韓電子工學會 2012 電子工學會論文誌-SD (Semiconductor and devices) Vol.49 No.4

FPGA용 CAD툴에 대한 학계의 연구는 상용 FPGA에 적용하기에는 단순하고 비효율적인 아키텍처를 가정하고 있기 때문에 실용성 측면에서 뒤처져 왔다. 최근 상용 FPGA 아키텍처의 배치 위치 및 배선 그래프 데이터베이스를 구축하고 인터페이스를 제공함으로써 상용 FPGA에 적용할 수 있는 배치 배선 툴의 개발을 가능하게 하려는 시도가 있었다. 본 논문은 신규 FPGA 아키텍처로 개발되고 있는 K-FPGA의 경쟁력을 벤치마킹 할 수 있는 툴킷 개발에 대해 기술한다. 이는 학계 CAD 툴의 실용성 한계를 한층 더 확장하고 있다. 기존 상용 툴과 매핑, 패킹, 배치, 배선 각 단계 별로 데이터를 교환할 수 있어 세부 툴별 비교 평가가 가능하며 이전 단계의 결과물을 기다리거나 결과의 질에 영향을 받지 않으면서 각 단계를 독립적으로 개발할 수 있는 체계를 구축하였다. 또한, 상용 FPGA의 아키텍처를 추출하여 단위 셀 라이브러리를 구축함으로써 FPGA 아키텍처의 신규 개발 시 참조 설계 역할을 할 뿐만 아니라 상시 벤치마킹 환경을 제공하도록 하였다. 특히, 아키텍처 정보를 툴 내에 하드 코딩하지 않고 하드웨어 설계자에게 익숙한 표준 HDL 형식으로 기술하여 읽어 들일 수 있도록 함으로써 아키텍처에 수시로 다양한 변경을 시도하면서 최적화해도 툴이 유연하게 수용할 수 있는 데이터 구동 방식의 툴 개발을 추구하였다. 실험을 통해 단위 셀 라이브러리 및 툴 기능을 검증하였으며 개발 중에 변경되고 있는 FPGA 아키텍처 상에서 임의의 설계를 매핑해 보고 정상 동작할 지 시뮬레이션으로 검증할 수 있음을 확인하였다. 배치 및 배선 툴이 개발 중이며 이들이 완성되면 실용적이고 다양한 신규 FPGA 아키텍처들을 개발하고 그 경쟁력을 평가할 수 있게 될 뿐만 아니라 신규 아키텍처를 위한 최적화 CAD 툴 개발 연구가 활발해지는 시너지 효과도 기대할 수 있다. The research on the FPGA CAD tools in academia has been lacking practicality due to the underlying FPGA fabric architecture which is too simple and inefficient to be applied for commercial FPGAs. Recently, the database of placement positions and routing graphs on commercial FPGA architectures has been built, and provided for enabling the academic development of placement and routing tools. To extend the limit of academic CAD tools even further, we have developed the evaluation toolkit for the K-FPGA architecture which is under development. By providing interface for exchanging data with a commercial FPGA toolkit at every step of mapping, packing, placement and routing in the tool chain, the toolkit enables individual tools to be developed without waiting for the results of the preceding step, and with no dependency on the quality of the results, and compared in detail with commercial tools at any step. Also, the fabric primitive library is developed by extracting the prototype from a reporting file of a commercial FPGA, restructuring it, and modeling the behavior of basic gates. This library can be used as the benchmarking target, and a reference design for new FPGA architectures. Since the architecture is described in a standard HDL which is familiar with hardware designers, and read in the tools rather than hard coded, the tools are "data-driven", and tolerable with the architectural changes due to the design space exploration. The experiments confirm that the developed library is correct, and the functional correctness of applications implemented on the FPGA fabric can be validated by simulation. The placement and routing tools are under development. The completion of the toolkit will enable the development of practical FPGA architectures which, in return, will synergically animate the research on optimization CAD tools.

타이밍 구동 FPGA 분석적 배치

김교선(Kyosun Kim) 대한전자공학회 2017 전자공학회논문지 Vol.54 No.7

FPGA 배치 툴 연구는 학계에서도 단순한 가상 아키텍처 모델 가정에서 벗어나 상용 툴처럼 캐리체인이나 광폭함수 멀티플렉서, 메모리/승산기 블록 등의 성능 및 밀도를 향상시키는 소자들을 포함하는 현실적인 모델을 적용하기 시작하였다. 이 때 발생하는 실제적 이슈들을 다룬 사전 패킹, 다층 밀도 분석 등의 기법이 초기 분석적 배치 (Analytic Placement)에 적용되어 밀도를 분산시키면서 배선 길이를 효과적으로 최소화한 연구가 앞서 발표된 바 있다. 더 나아가 궁극적으로는 타이밍을 최적화해야하기 때문에 많은 연구에서는 타이밍 제약 조건을 만족시키기 위한 기법들이 제시되고 있다. 그러나 초기 배치 후 진행되는 배치 적법화 및 배치 개선에서 주로 적용될 뿐 분석적 배치에서 이러한 타이밍 기법을 적용한 사례는 거의 없다. 본 논문에서는 사전 패킹 및 다층 밀도 분석 등의 기법이 구현된 기존 분석적 배치에 타이밍 제약 조건 위반을 검출하고 이를 최소화하는 기법을 결합하는 방안을 소개한다. 먼저 정적 타이밍 검증기를 집적하여 배선 길이가 최소화된 기존 배치 결과의 타이밍을 검사해 보았으며 위반을 감소시키기 위해 신호 도착 시간 (Arrival Time)을 최소화하는 함수를 분석적 배치의 목적 함수에 추가하였다. 이 때 각 클록마다 주기가 다를 수 있기 때문에 각 클록별로 함수를 따로 계산해 합산하는 방안이 제안되었다. 또한, 위반이 없는 클록 도메인의 신호 경로들도 불필요하게 단축될 수 있기 때문에 음수 슬랙 (Negative Slack)을 계산하여 이를 최소화하는 함수를 추가로 제안하여 비교하였다. 영역 분할 기법 (Partitioning)을 기반으로 배선 길이를 최소화하는 기존배치 적법화를 그대로 사용한 후 타이밍 검증을 통해 초기 분석적 배치 단계에서 타이밍 개선 효과를 분석하였다. 배치 적법화 시 추가적인 타이밍 최적화 기법이 사용되지 않았기 때문에 타이밍 개선이 있다면 이것은 전적으로 분석적 배치의 목적 함수개선에 의한 효과이다. 12개 실용예제에 대해 실험한 결과, 목적 함수에 도착 시간 함수가 적용되었을 때 그렇지 않았을 때보다 최악 음수 슬랙 (Worst Negative Slack)이 평균 약 15% 정도 감소되었으며 음수 슬랙 함수가 적용되었을 때 이보다 약 6%정도 추가로 더 감소됨을 확인하였다. Practical models for FPGA architectures which include performance- and/or density-enhancing components such as carry chains, wide function multiplexers, and memory/multiplier blocks are being applied to academic FPGA placement tools which used to rely on simple imaginary models. Previously the techniques such as pre-packing and multi-layer density analysis are proposed to remedy issues related to such practical models, and the wire length is effectively minimized during initial analytic placement. Since timing should be optimized rather than wire length, most previous work takes into account the timing constraints. However, instead of the initial analytic placement, the timing-driven techniques are mostly applied to subsequent steps such as placement legalization and iterative improvement. This paper incorporates the timing driven techniques, which check if the placement meets the timing constraints given in the standard SDC format, and minimize the detected violations, with the existing analytic placer which implements pre-packing and multi-layer density analysis. First of all, a static timing analyzer has been used to check the timing of the wire-length minimized placement results. In order to minimize the detected violations, a function to minimize the largest arrival time at end points is added to the objective function of the analytic placer. Since each clock has a different period, the function is proposed to be evaluated for each clock, and added to the objective function. Since this function can unnecessarily reduce the unviolated paths, a new function which calculates and minimizes the largest negative slack at end points is also proposed, and compared. Since the existing legalization which is non-timing driven is used before the timing analysis, any improvement on timing is entirely due to the functions added to the objective function. The experiments on twelve industrial examples show that the minimum arrival time function improves the worst negative slack by 15% on average whereas the minimum worst negative slack function improves the negative slacks by additional 6% on average.

ABC 표준 셀 매핑 면적 회복

김교선(Kyosun Kim) 대한전자공학회 2019 전자공학회논문지 Vol.56 No.1

학계의 논리 합성 툴과 상용 툴 간의 기술 격차를 극복하기 위한 노력으로 먼저 32-비트 RISC 프로세서인 OpenRISC를 대상으로 UC Berkeley 대학의 ABC와 시높시스 디자인 컴파일러의 표준 셀 매핑을 수행해 본 결과 디자인 컴파일러에 비해 ABC의 결과의 면적이 22% 초과되었다. 이 차이를 분석하여 ABC의 면적 회복 기능에서 누락된 기술들을 도출하였다. 먼저, 표준 셀 매핑에서 ABC가 (1) 듀얼 레일 매핑 중 면적 회복을 위해 한 극성을 제거하는 시기가 너무 이른 문제와 (2) 복수의 주 출력이 함수가 등가이어도 게이트 출력을 공유하지 않고 게이트를 복제하는 문제, 그리고 (3) 래치/플립플롭에 반전 출력이 없는 문제를 도출하여 해결함으로써 약 4%의 면적 감소를 얻었다. 또한, MAJ3와 XOR3와 같은 단일 출력 셀 대신에 전가산기 같이 이들 간에 논리를 공유하여 면적 이득을 얻을 수 있는 다 출력 셀을 매핑 할 수 있도록 함으로써 추가적으로 8%의 면적 감소를 달성하였으며 결과적으로 디자인 컴파일러 결과 대비 면적 평균 오차 범위가 10% 이내가 되었다. 이 과정에서 AIG 근간으로 무손실 합성, 슈퍼게이트, 그리고 진리표 해싱 및 N-등가를 이용한 듀얼 레일 매핑 기술이 복잡하게 구성된 표준 셀 매핑 알고리즘에서 기존 기술의 효율성에 손상을 주지 않고 다 출력 셀 매핑 기능을 추가하는 기술을 개발되었다. (1) 게이트 쌍 찾기와 (2) 깊이 우선 탐색을 사용한 캐리 체인 추출, 그리고 (3) 매칭 단계 초기 모드에 캐리 체인 우선 매칭 등을 포함한다. 잔여 오차는 표준 셀 매핑 문제가 아니라 (1) 하드웨어 추론 과정에서 다중 병렬 비트 멀티플렉서를 디코더를 이용한 곱의 합 구조가 아니라 트리 구조를 사용하여 구현한 문제와 (2) 연산기 공유를 위한 상위 수준 최적화 미적용 문제에 기인하는 것으로 분석되었다. 향후 이들이 구현된다면 오차는 수% 이내가 될 것으로 기대된다. Towards mitigating the technology gap between the academic and commercial synthesis tools, standard cells in a library are mapped to a 32-bit RISC processor, OpenRISC by ABC from UC Berkeley, and Design Compiler from Synopsys. The area of the circuit mapped by ABC is 22% larger than that by Design Compiler. The two mapped circuits are analyzed and compared with each other to identify the techniques missed by ABC but exploited by Design Compiler. First of all (i) postponing of dropping one of the polarities until the last mode of Boolean matching in the dual rail mapping, (ii) removing the gate duplication for each of the primary outputs with an equivalent function, and sharing the output of a gate, and (iii) exploiting the inverted outputs of flip-flops/latches has achieved 4% of area reduction. Also, the mapping of gates with multi-outputs such as the full adder which takes advantage of the area gain due to logic sharing between 3-input majority gate and 3-input XOR gate has enabled additional 8% of area reduction. Therefore, the correlation in terms of the average mapped circuit area between the academic and commercial synthesis tools has been achieved within 10% error. In the process, the AIG-based standard cell mapping provided by the lossless synthesis, supergates, and the dual rail mapping enabled by truth table hashing and N-equivalence, has been incorporated with the multi-output cell mapping without loss of the inherent efficiency. The proposed techniques include (i) collection of gate pairs, (ii) carry chain identification by a simple depth first search, and (iii) carry chain injection at an early mode of the Boolean matching step. The remaining area difference is mainly resulted from (i) the employment of the tree structure rather than the structure with a decoder and sums of products in the implementation of parallel multi-bit multiplexers during the hardware inference, and (ii) the missing high-level optimization for sharing arithmetic units. Only a few percent of error can be expected if those techniques are also implemented in the future.

Field Programmable Stateful Logic Array 패브릭 매핑 및 배치

김교선(Kyosun Kim) 대한전자공학회 2012 전자공학회논문지 Vol.49 No.12

최근 무어의 법칙을 연장시킬 시스템 집적 기술로서 Field Programmable Stateful Logic Array (FPSLA)가 제안되었다. 본 논문은 FPSLA의 설계 자동화 절차를 확립하고 논리 합성, 동기화, 물리적 매핑, 자동 배치 등의 접근 방법을 최초로 제시한다. 특히, 동기화를 통해 배치를 1차원 문제로 축소한 후 비선형 최적화 기법을 개량한 개략 배치 모델 및 하향식 계층적 2분법을 이용한 배치 적법화 알고리즘을 제안하였다. 또한, 제안된 모델 및 알고리즘을 소프트웨어로 구현하여 ACM/SIGDA 벤치 마크 예제에 적용함으로써 그 유효성을 입증하였다. 이 소프트웨어에는 Fanout 수만큼 출력 상태를 같은 단의 멤리스터성 스위치에 복사해야 하는 FPSLA의 특성을 고려하여 최적화 단계 별로 넷을 하이퍼에지로 통합했다가 다시 에지로 분리하는 기법이 제안되었으며 약 18.4%의 추가적 최적화를 이룩했다. FPSLA의 출력 상태 복사는 논리 단 일부에 셀 밀도가 집중되는 문제를 노출했으며 단위 논리 게이트의 Fanin을 제한하는 기법으로 18.5% 감소 효과를 얻었다. FPSLA의 실용성 확보를 위해서는 우선 논리 합성 시 Fanin의 수가 일부 단에 집중되지 않도록 제약하는 방안을 개발하여야 한다. 또한, FPSLA 패브릭 구조를 이식하기 위해 대칭성이 감소된 나노와이어 크로스바가 형성하는 복잡한 그래프 상에서 수행되어야 하는 자동 배선의 효율성 연구도 필요하다. 이러한 툴 개발은 설계 자동화 자체뿐만 아니라 FPSLA의 패브릭 구조 개선에 필요한 실험에 유용한 평가 도구로서도 큰 역할을 할 것이다. Recently, the Field Programmable Stateful Logic Array (FPSLA) was proposed as one of the most promising system integration technologies which will extend the life of the Moore’s law. This work is the first proposal of the FPSLA design automation flow, and the approaches to logic synthesis, synchronization, physical mapping, and automatic placement of the FPSLA designs. The synchronization at each gate for pipelining determines the x-coordinates of cells, and reduces the placement to 1-dimensional problems. The objective function and its gradients for the non-linear optimization of the net length and placement density have been remodeled for the reduced global placement problem. Also, a recursive algorithm has been proposed to legalize the placement by relaxing the density overflow of bipartite bin groups in a top-down hierarchical fashion. The proposed model and algorithm are implemented, and validated by applying them to the ACM/SIGDA benchmark designs. The output state of a gate in an FPSLA needs to be duplicated so that each fanout gate can be connected to a dedicated copy. This property has been taken into account by merging the duplicated nets into a hyperedge, and then, splitting the hyperedge into edges as the optimization progresses. This yields additional 18.4% of the cell count reduction in the most dense logic stage. The practicality of the FPSLA can be further enhanced primarily by incorporating into the logic synthesis the constraint to avoid the concentrated fains of gates on some logic stages. In addition, an efficient algorithm needs to be devised for the routing problem which is based on a complicated graph. The graph models the nanowire crossbar which is trimmed to be embedded into the FPSLA fabric, and therefore, asymmetric. These CAD tools can be used to evaluate the fabric efficiency during the architecture enhancement as well as automate the design.

멀티플렉서 트리 합성이 통합된 FPGA 매핑

김교선(Kyosun Kim) 대한전자공학회 2016 전자공학회논문지 Vol.53 No.4

광폭입력함수 전용 멀티플렉서가 슬라이스 구조에 포함되는 상용 FPGA의 현실적 제약 조건을 학계의 대표적 논리 표현방식인 AIG (And-Inverter Graph)를 근간으로 개발된 FPGA 매핑 알고리즘에 적용하였다. AIG를 LUT (Look-Up Table)으로 매핑할 때 중간 구조로서 컷을 열거하는 데 이들 중에서 멀티플렉서를 인식해 낸 후 이들이 매핑될 때 지연 시간 및 면적을 복잡도 증가 없이 계산하도록 하였다. 이 때 트리 형성 전제 조건인 대칭성과 단수 제약 요건도 검사하도록 하였다. 또한, 멀티플렉서 트리의 루트 위치를 RTL 코드에서 찾아내고 이를 보조 출력 형태로 AIG에 추가하도록 하였다. 이 위치에서 섀넌확장을 통해 멀티플렉서 트리 구조를 의도적으로 합성한 후 최적 AIG에 겹치도록 하는 접근 방법을 최초로 제안하였다. 이때 무손실 합성을 가능하게 하는 FRAIG 방식이 응용되었다. 두 가지 프로세서에 대해 제안된 접근 방법과 기법들을 적용하여 약 13∼30%의 면적 감소 및 최대 32%까지의 지연 시간 단축을 달성하였다. AIG 트리에 특정 구조를 의도적으로 주입시키는 접근 방법은 향후 캐리 체인 등에 확장 적용하는 연구가 진행될 것이다. The practical constraints on the commercial FPGAs which contain dedicated wide function multiplexers in their slice structure are incorporated with one of the most advanced FPGA mapping algorithms based on the AIG (And-Inverter Graph), one of the best logic representations in academia. As the first step of the mapping process, cuts are enumerated as intermediate structures. And then, the cuts which can be mapped to the multiplexers are recognized. Without any increased complexity, the delay and area of multiplexers as well as LUTs are calculated after checking the requirements for the tree construction such as symmetry and depth limit against dynamically changing mapping of neighboring nodes. Besides, the root positions of multiplexer trees are identified from the RTL code, and annotated to the AIG as AOs (Auxiliary Outputs). A new AIG embedding the multiplexer tree structures which are intentionally synthesized by Shannon expansion at the AOs, is overlapped with the optimized AIG. The lossless synthesis technique which employs FRAIG (Functionally Reduced AIG) is applied to this approach. The proposed approach and techniques are validated by implementing and applying them to two RISC processor examples, which yielded 13∼30% area reduction, and up to 32% delay reduction. The research will be extended to take into account the constraints on the dedicated hardware for carry chains.

CMOL FPGA 자동 레이아웃 설계

김교선(Kyosun Kim) 대한전자공학회 2007 電子工學會論文誌-SD (Semiconductor and devices) Vol.44 No.11

본 논문은 CMOS-나노 혼성 소자들 중 실현 가능성이 높은 CMOL 회로 설계 자동화 전용 시스템을 최초로 제안한다. CMOL 아키텍처는 NOR 게이트를 이용하여 조합회로의 구현한다. 이 CMOS-나노 혼성 구조는 논리 함수 및 연결 구조가 동일 나노 소자 하드웨어 자원을 공유하는 특징을 가진 새로운 설계 자동화 문제를 제기한다. CMOL의 물리 설계 자동화를 위해 먼저 CMOL 하드웨어 아키텍처 모델을 개발하고 이 CMOL 구조를 위한 배치 배선 문제에서 CMOL만의 특수한 제약조건을 도출하였으며 배치 알고리즘과 게이트 지정 알고리즘을 루프 형태로 조합하여 해를 구하는 접근 방법을 제안하였다. 제안된 접근 방법을 사용하여 CMOL 나노 전자 아키텍처를 위한 전용 설계 자동화 시스템을 개발하였으며 이 시스템을 이용하여 마이크로프로세서 설계에 실제 사용되는 모듈들을 구현함으로써 그 효용성을 증명하였다. We developed the first automatic design system targeting a promising hybrid CMOS-Nanoelectronics Architecture called CMOL. The CMOL architecture uses NOR gates to implement combinational logic. In this hybrid CMOS-nanoelectronics architecture, logical functions and the interconnections share the nanoelectronics hardware resource. Towards automating the CMOL physical design process, we developed a model for the CMOL architecture, formulated the placement and routing problems for the CMOL architecture subject to the unique CMOL specific constraints, and solved it by combining a placement algorithm with a gate assignment algorithm in a loop. We validated the proposed approach by implementing several industrial strength designs.

소형 네트워크 임베디드 시스템에 TinyOS 이식 과정에서의 이슈 및 디버깅 기법

김대남(Daenam Kim),김교선(Kyosun Kim) 대한전자공학회 2008 電子工學會論文誌-CI (Computer and Information) Vol.45 No.6

ZigBee 통신기반의 네트워크 임베디드 시스템을 위한 많은 플랫폼들이 개발되어 왔으며 TinyOS와 같은 소형 운영체제가 탑재되어 다양한 주변장치를 통해 네트워킹, 정보수집, 명령 수행 등 다양한 기능들을 효율적으로 구현할 수 있도록 하고 있다. 새로운 플랫폼에 운영체제를 이식하는 과정에서는 계수기와 같이 중요한 특정 하드웨어 장치가 운영체계에서 요구하는 기능이 부족하다면 소프트웨어 및 다른 하드웨어 장치로 해당 기능을 구현해야 한다. 본 논문은 먼저 계수기에 비교기 인터럽트 기능이 없는 플랫폼에서 운영체계의 요구 기능을 만족하는 다중 시스템 타이머를 구현하는 기법을 제안한다. 또한, 이식과정에서 예측하기 어려운 오류가 주입될 수 있기 때문에 이에 따라 발생하는 수많은 오동작에 대처해야 할 것이다. 불행히도 TinyOS에는 하드웨어의 인터럽트에 의해 구동되는 수많은 비동기 처리가 필요한 반면 새로운 플랫폼에는 탑재된 하드웨어 각각에 대한 모델이 확립되지 않아 시뮬레이터가 미리 제공되지 못한다. 본 논문은 이러한 열악한 상황에서 사용할 수 있는 새로운 디버깅 기법을 제안한다. 이 방법은 레이디오펄스(주)의 MG2400과 MG2455에 TinyOS 2.0을 이식하는 과정에서 발생한 이슈들과 원인을 찾아내는데 사용되어 그 실용성을 입증하였다. Numerous platforms have been developed for ZigBee-based network embedded systems. Also, operating systems like TinyOS have been installed to facilitate efficient implementation of wireless sensor network applications which collect data, and/or execute commands. First of all, porting an operating system on a new platform may need invention of a substitute for a required but unsupported hardware component. This paper presents a multiplexed virtual system timer for a platform without a counter comparator which we have contrived to emulate by using an extra counter. Such porting also injects unexpected faults which cause a variety of painful failures. Unfortunately, TinyOS requires to handle a lot of asynchronous hardware interrupts which are hard to trace during debugging. Besides, simulators are not available for a new platform since the models of hardware on the platform are not usually developed, yet. We propose novel instrumentation techniques which can be used to effectively trace the bugs in such lack of debugging environment. These techniques are used to identify and fix a great deal of nasty issues in porting TinyOS 2.0 on MG2400 and MG2455 platforms made by RadioPulse Inc.