혼선을 고려한 채널 배선 방법

전주식(Chu Shik Jhon),장경선(Kyoung-Son Jhang),하순희(Soonhoi Ha) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.10

VLSI 공정 기술의 발달로 칩 상에서 전선간 간격이 점점 가까와 지고 있다. 그에 따라 구현된 VLSI 회로가 빠르고 정확하게 동작하도록 하기 위해서 레이아웃 설계 과정에서 인접 전선간의 결합 축전량으로 발생하는 혼선을 줄이는 것을 중요한 요인으로 고려하게 되었다. 설계 과정에서 네트 별로 혼선에 대한 상한치가 주어지는 것이 보통이며, 이를 혼선 제약 조건이라고 한다. 이 논문에서는 혼선 제약 조건을 고려한 그리드 채널 배선 문제를 다룬다. 제안된 방법은 트랙 수 최소화를 목적으로 하는 기존의 채널 배선 방법으로 생성된 초기 배선에 대해 수평 선분들을 재배열하여 혼선 제약 조건을 만족하도록 한다. 이 방법은 주어진 트랙 수 내에서 혼선 제약 조건을 만족하는 해가 없는 경우에는 최소의 트랙 수 증가로 혼선 제약 조건을 만족하는 배선을 찾는다. 실험 결과 이 방법은 트랙 재배치 방법보다 효율적임을 관찰할 수 있었다. The inter-wire spacing in a VLSI chip becomes closer as the VLSI fabrication technology rapidly evolves. Accordingly, it becomes important to consider crosstalk caused by the coupling capacitance between adjacent wires in the layout design for the fast and safe VLSI circuits. The upper bounds of the crosstalk for nets, called crosstalk constraint, are usually given in the design specification. This paper deals with the gridded channel routing problem with crosstalk constraints. In this paper, we present a channel routing technique which generates a routing to satisfy crosstalk constraints from an initial routing generated by conventional routers. The proposed technique is based on the repeated rearrangements of horizontal segments in the initial routing. In addition, the proposed technique tries to find a routing to satisfy crosstalk constraints with the minimum increase of the number of tracks in cases where it cannot find a routing to satisfy crosstalk constraints with the given number of tracks. With experiments, we observed that the presented technique is more effective than the track permutation technique.

32비트 RISC 마이크로 프로세서의 논리 설계

김형식(Hyong Shik Kihm),최종필(Jong PiI Choi),전주식(Chu Shik Jhon) 한국정보과학회 1989 한국정보과학회 학술발표논문집 Vol.16 No.1

본 논문은 최근 수행된 32비트 RISC 마이크로 프로세서의 논리 설계에 대하여 설명한다. 본 프로세서는 SPARC 마이크로 프로세서와의 완전한 호환성을 가지도록 설계되었으며, 논리 시뮬레이터를 사용하여 검증되었다. 따라서 동작성이라는 입장에서는 SPARC 마이크로 프로세서상에서 응용되는 모든 프로그램이 어떤 수정없이도 본 프로세서에서 수행될 수 있다.

다중스레드 프로세싱에서의 프레임 동기화 비용의 최소화

김형식(Hyong Shik Kim),하순회(Soonhoi Ha),전주식(Chu Shik Jhon) 한국정보과학회 1995 정보과학회논문지 : 시스템 및 이론 Vol.22 No.12

다중스레딩 기법은 다른 수행가능한 스레드로의 빠른 전환을 통하여 메모리 혹은 프로세서간 통신으로 인한 지연을 허용하기 때문에, 병렬처리 구조에 적합하다. 대부분의 기존 프로세서들이 load-store 구조를 취한다는 점에서, 프레임 동기화 오버헤드는 다중스레딩 구조, 특히 컴파일러 제어형태의 다중스레딩 구조에서 중요한 성능요소이다. 본 논문에서는 확률적 스레드작업모델을 사용하여 다중스레드 프로그램을 퀀텀 범위에서 분석하고, 새로 도입된 퀀텀 경계 동기화 기법과 원래의 스레드 경계 동기화 기법을 결합하여 다중스레딩에서의 전체 프레임 동기화 비용을 줄이는 방법을 제안한다. 실험결과에 의하면, 동기화 비용은 프로그램의 특성에 따라 최소 11퍼센트에서 최대 68퍼센트가 감소하였다. Multithreading is an attractive alternative for parallel processing because it allows a processor to tolerate long latency due to memory or interprocessor communication by rapidly switching to a ready-to-run thread. Since most current processors are load-store machines, frame synchronization overhead in multithreaded processing is one of major factors affecting overall performance, especially in compiler-controlled multithreading. In this paper, we introduce the quantum-scope analysis on multithreaded programs using the probabilistic threaded work model, and suggest how to reduce the total synchronization cost by combining the new quantum-boundary synchronization with the original thread-boundary synchronization which is generally taken in compiler-controlled synchronization. The experiment results are very encouraging. The synchronization costs are reduced by a significant amount, ranging from 11 percents to 68 percents, depending on program characteristics.

I-구조 데이타 캐쉬가 프레임 기반 다중스레드 모델의 성능에 미치는 영향

김형식(Hyong-Shik Kim),하순회(Soonhoi Ha),전주식(Chu Shik Jhon) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.11

다중스레드 모델에서는 프로세서가 원격 메모리 참조에 필요한 지연시간(latency) 동안 결과를 기다리게 하는 대신 다른 스레드로 제어를 옮겨 수행을 계속하기 때문에, 원격 메모리에 저장된 I-구조 데이타를 캐쉬에 저장할 때 기대할 수 있는 성능 향상의 정도는 일반적인 데이타 캐쉬에 비하여 훨씬 작을 것으로 예상된다. 본 논문에서는 프레임 기반 다중스레드 모델에서 I-구조 데이타의 특성에 적합한 캐쉬 구조와 I-구조 연산의 구현 방법에 대하여 제안하고, 지연시간 감내 성질(latency tolerating property)에도 불구하고 I-구조 데이타 캐쉬가 프로그램 수행 시간을 감소시킬 수 있음을 보인다. 실험 결과의 분석에 의하면, 프레임 기반 다중스레드 모델의 성능에 대한 I-구조 데이타 캐쉬의 영향 중에서 가장 중요한 것은 프레임 병렬성의 향상이다. 이것은 프로세서들에게 지연시간을 감내하는데 필요한 대체 작업을 충분히 공급함으로써 다중스레드 모델의 효율을 증가시키고 수행 시간을 단축시킨다. In multithreaded model, the processor does not wait for the response with a long latency on a remote memory access, but can still continue the computation by rapidly switching to a ready-to-run thread. Therefore, caching I-structure data kept in remote memory is expected to have less beneficial effect on the performance than caching ordinary data. In this paper, we propose an organization and an operation scheme of an I-structure data cache for frame-based multithreading, and show that the proposed I-structure data cache could improve the overall performance in spite of latency tolerating property of multithreaded model. The analysis on the simulation results reveals that the most important effect of I-structure data cache on the performance of frame-based multithreaded model is the enhancement of frame parallelism. That improves the efficiency of the model by supplying alternative works enough to tolerate the latency, and thus reduces the execution time.

A Rule-based Expert System for Mask Layout Problems

Jae Hwang Lee,Chu Shik Jhon 대한전자공학회 1992 대한전자공학회 Conference Vol.1992 No.2

Scheduling Instruction-level Parallelism

Hye Kyung Cha,Chu Shik Jhon 대한전자공학회 1994 JTC-CSCC : Joint Technical Conference on Circuits Vol.- No.-

A Lower Bound Directed Scheduling Algorithm

Ohm, Seong Yong,Jhon, Chu Shik 대한전자공학회 1991 ICVC : International Conference on VLSI and CAD Vol.2 No.1

This paper presents a new approach to the scheduling problem in the high level synthesis. In this approach, a branch-and-bound technique is employed so as to arrive at the scheduling result of the lowest hardware cost under the given timing constraint. This is achieved by improving iteratively As Soon As Possible (ASAP) scheduling result. At each iteration step, only the candidate nodes are selected for rescheduling, and thus reducing run time. In addition, the notion of a lower bound estimation employed in our algorithm helps increase the number of cut-offs in the search space, and thus further reducing run time. It turns out that in many cases, our algorithm is superior to existing scheduling algorithms in both the scheduling result and run time.

루프의 파이프라이닝 스케쥴을 위한 알고리즘

차혜경(Hyekyung Cha),전주식(Chu Shik Jhon) 한국정보과학회 1995 정보과학회논문지 : 시스템 및 이론 Vol.22 No.10

본 논문에서는 루프의 병렬화를 위해 루프의 기능한 병렬성을 탐지하고 스케쥴하는 문제를 다룬다. 최근에 집적회로 기술의 급격한 발달로 한 칩안에 파이프라이닝 연산이 이루어지도록 하는 것이 가능하며 VLIW나 슈퍼스칼라 컴퓨터에서는 파이프라이닝의 스케쥴링 문제가 발생한다. 여기에서는 고수준 언어로 표현된 루프를 데이타 종속그래프로 나타내고 이로부터 루프의 병렬성을 파악하여 그 병렬성을 나타내는 파이프라이닝 형태의 스케쥴을 얻고자 한다. 특히 단순 루프에 있는 최대한의 병렬성을 얻는 최적의 알고리즘을 제시하고자 한다. 이 알고리즘에서는 데이타 종속 그래프상의 근접한 노드 사이의 지역적 시간관계를 이용하여 이를 결합함으로써 전체적인 스케줄을 얻는 방법을 사용하였다. 제시된 알고리즘은 다항 시간의 복잡도를 가지며 최소의 지연간격을 갖는 파이프라이닝 스케쥴의 패턴을 생성한다. This paper deals with the problem of detecting and scheduling parallelism existing in loops for loop parallelization. Recently the tremendous development in VLSI technology makes it possible that a pipelining operation is to be performed in a single chip processors and the pipelining scheduling problem arises in VLIW or superscalar machines. Here we represent the loops of high-level programs as data dependence graphs, and from them we are to perceive parallelism in the loops, and to obtain the schedules in pipelining form which represents maximal parallelism. Especially an optimal algorithm for obtaining maximal parllelism In simple loops will be presented. The method to be used in this algorithm combines local schedules using local timing relations between adjacent nodes in its dependence graph to obtain an overall schedule. The algorithm has polynomial time complexity and produces the pattern of pipelining schedule with minimal delaying distance.

노드 병합에 의한 FPGA 기술 매핑 방법

이강(Kang Yi),전주식(Chu-Shik Jhon) 한국정보과학회 1996 정보과학회논문지 : 시스템 및 이론 Vol.23 No.10

본 논문에서는 FPGA 기술 매핑 문제를 불린네트워크의 각 노드들을 최적으로 병합하는 노드 병합 문제로 모델링한다. 이러한 모델링은 다양한 종류의 FPGA 구조에 대해, 다양한 기준의 최적화를 전역적인 관점에서 고려할 수 있게 한다. 본 논문에서는 이를 구현하기 위해, 먼저 하나의 FPGA 셀에 배정 가능한 노드들의 집합(매핑 클러스터라고 한다)들을 추출하고, 이에 대해 불린네트워크의 모든 노드와 에지를 커버링(covering)하는 최적의 클러스터 부분집합을 찾는다. 실험 결과, 기존의 시스템 가운데 대표적인 MUX-based FPGA 기술 매핑 방법인 mis-pga(new)보다 구현에 필요한 셀의 개수 면에서 평균 4.4% 향상된 결과를 얻었다. We model the FPGA technology mapping problem as an optimal node merging problem for a given boolean network. Such modeling provides a more global view on the optimality and also supports various FPGA architectures such as MUX-based and LUT-based. To solve this problem, we first generate the collection of all the feasible clusters where each cluster contains the nodes that can be assigned to the same FPGA cell, then find an optimal covering set for the cluster that maintains original functionality of input boolean network. We applied our approach to well known benchmarks and got 4.4% improvement over the most well known MUX-based FPGA technology mapping system, mis-pga(new).

회로의 면적 최적화를 위한 효율적인 MUX - based FPGA 기술 매핑

이강(Kang Yi),전주식(Chu Shik Jhon) 한국정보과학회 1996 한국정보과학회 학술발표논문집 Vol.23 No.1A

본 논문에서는 회로의 면적 최소화를 목적으로 한 MUX-based FPGA 기술 매핑 문제를 노드들 간의 최적의 병합 문제로 보고 이를 구현하였다. 이 방법에서는 병합 가능한 인접 노드들의 집합을 클러스터 개념으로 정의하고, FPGA 기술 매핑 문제를 클러스터 단위로 FPGA 기본 셀을 할당하는 문제로 정의함으로써 전역적 면적 최적화의 관점에서 FPGA 기술 매핑을 가능하게 한다. 본 논문에서는 FPGA 기술 매핑을, 구성 가능한 클러스터들을 효율적으로 구하는 문제와 주어진 불린네트워크를 커버하는 클러스터들의 최소 기본의 대표적 MUX-based FPGA 논리 합성 시스템인 mis-pga(new)보다 FPGA 기본 셀 개수 면에서 4.2% 향상된 결과를 보였다.