Microprocessor 를 이용한 계측장치에 관한 연구

김종상(Chong Sang Kim),심원(Won Sim) 대한공업교육학회 1978 대한공업교육학회지 Vol.3 No.1

In this paper, a study was made to realize the digital voltmeter using microprocessor. The DVM was composed of M 6800 microprocessor with simple analog subsystem and software. To achieve analog to digital conversion, successive approximation techniques was used. MC 6820 PIA interfaced the analog subsystem and digital subsystem-microprocessor. The hard wired-logic functions of conventional DVM was substituted by MC 6800 software. The advantages of using microprocessor are to get maximum, minimum and average of iterative measuring data. Also autorange was solved by software.

이기종 간의 분산 화일 시스템 구성에 관한 연구

김종상(Kim Chong Sang),김철기(Kim Choel Kie),문수복(Moon Sue Bok) 한국정보과학회 1988 한국정보과학회 학술발표논문집 Vol.15 No.1

분산 시스템은 단일 집중형 시스템에 비하여 성능의 향상, 확장성, 장애시의 유용성, 자원의 공유 등의 잇점을 지닌다. 본 논문에서는 분산 계층을 통해 사용자 수준에서 처리하는 이기종 간의 분산 화일 시스템을 설계하고, VAX-11/750 UNIX 4 3 BSC 시스템과 Internetworking 소프트웨어인 UNET을 이식한 PC-AT UNIX System V 시스템에 구현하였다.

Tail-Clustering 方法을 利用한 tree 文法의 推論에 관한 연구

김종상(Chong Sang Kim),김동수(Dong Soo Kim) 한국정보과학회 1982 정보과학회논문지 Vol.9 No.1

In this paper the inference method for tree grammar, the tail-clustering method, is considered. Because the expansive tree grammar can be regarded as the generalization of the regular string grammar, the tail-clustering method which is one of the inference methods for the regular string grammar can be applied to the inference of tree grammar. This method has the advantage of not requiring the parameter selection and sublanguage grouping, and can infer the grammar which is exactly the sub grammar of true grammar. 본 논문은 tree 문법의 초론 방법인 tail-clustering 방법에 관한 연구이다. Expansive tree 문법은 regular string 문법의 일반적인 경우라 간주할 수 있으므로 regular sting 문법의 추론 방법의 하나인 tail-clustering 방법을 tree 문법의 추론에 응용할 수 있다. 이 방법은 매개변수 선택이나 sublanguage 조합을 필요로 하지 않으며, 추론하고자 하는 진짜 문법의 부분집합이 되는 문법을 찾아낼 수 있다.

커트세트와 관련된 그래프 알고리즘

김종상(Chong Sang Kim),황희융(Hee Yeung Hwang),조유근(Yoo Kun Cho),표창우(Chang Woo Pyo) 한국정보과학회 1982 정보과학회논문지 Vol.9 No.2

현재 s-t cutset enumeration algorithm의 upper bound는 cutset 당 O(n+m)이다. 여기서 n은 주어진 그래프의 vertex 수이고, m은 edge 수이다. 본 논문에서는 planar graph에서 articulation vertex를 쉽게 찾을 수 있는 data structure와 algorithm을 제시하였고, 이 algorithm을 사용할 경우 planar graph에서 s-t cutset enumeration algorithm은 O(μ · max/zEv{d(z)ℓ_(max)(C(z))})외 time complexity 와 O(n²)의 space complexity를 가짐을 보였다. 여기서 d(1)는 vertex z의 degree이고, ℓ_(max)(C(z))는 vertex z에 incident 한 region 각각을 둘러싸고 있는 cycle들의 length들 중 최대값을 나타내며, μ는 cutset 의 수를 나타낸다. The current upper bound of the s-t cutset enumeration algorithm in an undirected graph is O (μ(n+m)), where n is the number of vertices, m is the number of edges, and μ is the number of s-t cutsets. In this paper well-defined data structures and an algorithm are presented for deciding whether a given vertex v of an undirected planar graph is an articulation vertex or not and if these data structures and algorithm are used for the present cutset enumeration algorithm for a planar graph, its time complexity can be improved to be of O(μ-max{d(i)ℓ_(max) (c(1))}) with the same space complexity of O(n²), where d(i) is the degree of the vertex 1 and ℓ_(max)(c(1)) is the maximal value of the lengths of cycles which are defined by the interior regions incident to the vertex 1 in the given undirected planar graph.

Local ares network의 모델링과 성능평가

김종상(Chong Sang Kim),민상렬(Sang Yul Min),송운호(Woon Ho Song) 한국정보과학회 1984 정보과학회논문지 Vol.11 No.2

본 논문을 실제적이고 해석적으로 풀이가 가능한 Local Area Network의 성능 평가에 대하여 기술하였다. 특히 본 논문에서는 유한 buffer와 resource의 획득에서 발생하는 간섭에 중점을 두었다. 본 논문의 Local area Network는 2개의 host processor, 1개의 IMP, 3개의 disk unit와 여러개의 data link로 구성되어 있다. This paper presents a case study of the development of a realistic, but analytically soluble, model of a local area network. Particular attention was paid to the effect of finite buffer, and to contention and interference effects caused by simultaneous resource possession. The system configuration of this local area network includes two host processors, one IMP, three disk units, and several data links.

RISC 프로세서를 대상으로 한 최악 실행시간 분석의 정확도에 대한 과예측 원인별 영향 분석

김성관(Sung-Kwan Kim),민상렬(Sang Lyul Min),하란(Rhan Ha),김종상(Chong Sang Kim) 한국정보과학회 1999 정보과학회 컴퓨팅의 실제 논문지 Vol.5 No.4

실시간 태스크의 최악 실행시간을 예측할 때 과예측이 발생하는 원인은, 첫째 프로그램의 동적인 최악 실행 행태를 정적으로 분석하는 것이 근본적으로 어렵기 때문이며, 둘째 최근의 RISC 형태 프로세서에 포함되어 있는 파이프라인 실행 구조와 캐쉬 등이 그러한 정적 분석을 더욱 어렵게 만들기 때문이다. 그런데 기존의 연구에서는 각각의 과예측 원인을 해결하기 위한 방법에 대해서만 언급하고 있을 뿐 분석의 정확도에서 각 원인이 차지하는 비중에 대해서는 언급하고 있지 않다. 이에 본 연구에서는 최악 실행시간 예측시 과예측을 유발하는 원인들, 즉 분석 요소들의 영향을 정량적으로 조사함으로써 기존의 최악 실행시간 분석 기법들이 보완해야 할 방향을 제시하고자 한다. 본 연구에서는 실험이 특정 분석 기법에 의존하지 않도록 하기 위하여 시뮬레이션 방법에 기반한다. 이를 위해 분석 요소별 스위치가 포함된 MIPS R3000 프로세서를 위한 시뮬레이터를 구현하였는데, 각 스위치는 해당 분석 요소에 대한 분석의 정확도 수준을 결정한다. 모든 스위치 조합에 대해서 시뮬레이션을 반복 수행한 다음 분산 분석을 수행하여 어떤 분석 요소가 가장 큰 영향을 끼치는지 고찰한다. Existing analysis techniques for estimating the worst case execution time (WCET) of real-time tasks still suffer from significant overestimation due to two types of overestimation sources. First, it is unavoidably difficult to predict dynamic behavior of programs statically. Second, pipelined execution and caching found in recent RISC-style processors even more complicate such a prediction. Although these overestimation sources have been attacked in many existing analysis techniques, we cannot find in the literature any description about questions like which one is most important Thus, in this paper, we quantitatively analyze the Impacts of overestimation sources on the accuracy of the worst case timing analysis. Using the results, we can identify dominant overestimation sources that should be analyzed more accurately to get tighter WCET estimations. To make our method independent of any existing analysis techniques, we use simulation based methodology. We have implemented a MIPS R3000 simulator equipped with several switches, each of which determines the accuracy level of the timing analysis for the corresponding overestimation source. After repeating simulation for all of the switch combinations, we perform the variance analysis and study which factor has the largest impact on the accuracy of the predicted WCETs.

가상 캐쉬의 성능 개선을 위한 가상-물리 캐쉬 구조

김제성(Je Sung Kim),민상렬(Sang Lyul Min),정덕균(Deog-Kyoon Jeong),신현식(Heonshik Shin),김종상(Chong Sang Kim) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.11

고속의 프로세서에서는 캐쉬의 적중시간이 매우 빠를 것이 요구된다. 직접사상 가상 캐쉬는 이러한 요구 사항을 가지는 프로세서에 잘 부합하는데, 그 이유는 접근성공시 TLB접근에 의한 지연 및 부가의 비교기와 멀티플렉서에 의한 지연이 없기 때문이다. 그러나, 가상 캐쉬는 동의어 문제(synonym problem)의 해결책을 필요로 하며, 직접사상 캐쉬는 자주 사용되는 메모리 블록이 같은 집합에 사상될 경우 이들 블록 간의 충돌에 의한 접근실패 때문에 집합연관 캐쉬에 비해 접근실패율이 높다. 본 논문에서는 이와 같은 직접사상 가상 캐쉬의 단점을 개선하기 위한 가상-물리(Virtual-Physical)캐쉬 구조를 제시한다. 이 기법의 핵심을 각 메모리 블록이 자신의 가상 주소 및 물리 주소에 의해 결정되는 두 집합 중 어느 한 곳에 놓일 수 있도록 하는 것이다. 이에 따라 직접사상 캐쉬의 빠른 적중시간을 유지하면서 이원 집합연관 캐쉬의 장점을 취할 수 있다. 또한, 물리 주소에 의해 결정되는 집합에 놓인 블록은 동의어 문제를 발생시키지 않으므로 동의어 배척(anti-aliasing)에 의해 방출되는 캐쉬 블록을 물리 주소에 의해 결정되는 집합에 놓으므로써 캐쉬의 이용률을 개선할 수 있다. 본 논문에서 제시한 가상-물리 캐쉬는 ATUM 추적(trace)을 이용하여 추적 구동 시뮬레이션 하였으며, 그 결과 접근실패율이 최고 25% 개선됨이 입증되었다. In high-performance processors, a fast cache hit time is one of the most important design requirements. Direct-mapped virtual caches would be a nice match with such high-speed processors since they do not require a TLB access on a cache hit and do not suffer from delays due to additional comparators and multiplexors. Virtual caches, however, require an anti-aliasing scheme to solve the well-known synonym problem and direct-mapped caches yield higher miss ratios than set-associative caches with comparables size. This paper presents a novel cache organization, named Virtual-Physical cache organization, to rectify the problems associated with direct-mapped virtual caches. In the proposed scheme, a given memory block can be placed at two different locations in the cache, one based on the virtual address and the other based on the physical address. This provides the benifit of 2-way set-associative caches while preserving the fast hit time of direct-mapped caches. Moreover, the proposed scheme improves the cache storage utilization by remapping the cache blocks evicted from the cache for anti-aliasing purposes. The remapping is valid since cache blocks placed at the locations based on physical addresses are not susceptible to the synonym problem. We show by trace-driven simulations with ATUM traces that the proposed scheme improves miss ratios up to 25%.

효율적인 전진 선인출 기법

김성백(Seong Baeg Kim),박선호(Sunho Park),박명순(Myung Soon Park),김제성(Jesung Kim),민상렬(Sang Lyul Min),정덕균(Deog-Kyoon Jeong),신현식(Heonshik Shin),김종상(Chong Sang Kim) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.6

본 논문에서는 제어 천이에 효과적으로 적응하는 새로운 명령어 선인출 기법을 제안한다. 쓰레드 선인출이라 명명한 이 기법은 제어 흐름이 매번 같은 경로를 따르는 경향이 있다는 점을 이용한 것으로, 과거의 제어 흐름 경로에 따라 명령어 블록을 선인출하여 메모리 참조의 지연을 줄이기 위한 것이다. 이 기법에서 각 명령어 블록은 쓰레드라 불리는 포인터를 가지며, 이 포인터가 과거에 이 블록 다음에 실행되었던 명령어 블록을 가리키게 된다. 본 논문에서 제안한 쓰레드 선인출 기법은 트레이스 구동 시뮬레이션(trace driven simulation)에 의해 성능이 평가되었으며, 그 결과 정확도가 순차적 선인출에 비해 최대 100% 향상됨이 입증되었다. 이 기법은 크기가 작은 캐쉬에서도 정확도 높은 선인출로 좋은 성능을 제공하며 문맥교환에 의한 캐쉬 성능 저하를 막는데도 효과가 있을 것으로 기대된다. We propose and analyze an adaptive instruction prefetch scheme, called threaded prefetching, that makes use of history information to guide the prefetching. Our proposed scheme is based on the observation that control flow paths are likely to repeat themselves. In the proposed scheme, we associate for each instruction block a number of threads that indicate the instruction blocks that have been brought into the cache by the current block. These threads later trigger the prefetching of the indicated instruction blocks once the instruction block containing them are re-accessed by the processor. A quantitative evaluation using SPEC benchmarks shows that the proposed scheme improves the prefetch accuracy by more than 100% on average for 32 Kbyte cache. Also the results from trace-driven simulations show that the proposed scheme significantly improves the CPI due to instruction references over the sequential prefetching when the degree of memory interleaving is greater than two. We expect that by carrying the thread information over context switches, the proposed scheme is also very effective in minimizing the adverse impact of context switches on cache performance.

VAX / VMS에서의 VAX / UNIX와의 컴퓨터 통신을 위한 링크 드라이버의 설계 및 구현

김규호(Kyu Ho Kim),김철기(Cheol Kie Kim),김종상(Chong Sang Kim),민상열(Sang Yul Min) 한국정보과학회 1985 정보과학회논문지 Vol.12 No.3

본 논문에서는 UNET과 4.2BSD의 TCP/IP를 이용하여 구성되는 UNIX 컴퓨터를 기본으로 한 네트워크인 SDN에 VAX/VMS 컴퓨터를 포함시키는 작업을 기술하였다. VAX/VMS에서는 DARPA의 TCP/IP를 기반으로 하는 네트워크 소프트웨어를 RS-232C 통신 선로를 사용할 수 있도록 링크 드라이버를 설계 구현함으로써, SDN에서도 VAX/VMS 컴퓨터를 연결하여 FTP, TELNET 및 SMTP 등을 사용할 수 있게 되었다. This paper describes the procedure which includes VAX/VMS computers in SDN, that is a computer network composed of UNIX machines using UNET and 4.2BSD TCP/IP. The link driver is designed and implemented on VAX/VMS to use the RS-232C line under the network software which is based on TCP/IP, so it is possible to connect VAX/VMS computers in SDN, and as the result, the network application programs such as FTP, TELNET and SMTP can be used with VAX/VMS computers.

순차 참조와 순환 참조들을 고려한 버퍼 캐쉬 관리 기법

김종민(Jong Min Kim),최종무(Jongmoo Choi),김제성(Jesung Kim),이동희(Donghee Lee),노삼혁(Sam H. Noh),민상렬(Sang Lyul Min),조유근(Yookun Cho),김종상(Chong Sang Kim) 한국정보과학회 2001 정보과학회논문지 : 시스템 및 이론 Vol.28 No.1·2

최근 버퍼 캐쉬의 성능을 향상시키기 위한 많은 블록 교체 기법들이 제안되었으며 이 중에서 작업 집합 (working set) 변화에 잘 적응하고 구현이 용이한 Least Recently Used (LRU) 블록 교체 기법이 널리 사용되고 있다. 그러나 LRU 블록 교체 기법은 블록들이 규칙적인 참조 패턴을 보이면서 순차 참조되거나 순환 참조될 때 이 규칙성을 적절히 이용하지 못해 성능이 저하되는 문제점을 가진다. 본 논문에서는 다중 응용 트레이스를 이용하여 LRU 블록 교체 기법의 문제점을 관찰하고, 이 문제점을 해결하는 통합된 형태의 효율적인 버퍼 관리 (Unified Buffer Management, 이하 UBM) 기법을 제안한다. UBM 기법은 순차 참조 및 순환 참조를 자동 검출하여 분리된 공간에 저장하고 이들 참조에 적합한 블록교체 기법으로 이 공간을 관리한다. 또한 순차 참조와 순환 참조를 위한 공간과 나머지 참조를 위한 공간의 비율을 최적으로 할당하기 위해 온라인에서 수집된 정보를 이용하여 계산된 단위 공간 증가당 예상 버퍼 적중 증가율을 이용한다. 다중 응용 트레이스 기반 시뮬레이션 실험에서 UBM 기법의 버퍼 적중률은 LRU 블록 교체 기법에 비해 평균 12%, 최대 28%까지 향상된 결과를 보였다. The Least Recently Used (LRU) block replacement scheme is still widely used due to its simplicity. While simple, it still adapts well to the changes of the working set, and has been shown to be efficient when recently referenced blocks are likely to be re-referenced in the near future. The main drawback of the LRU scheme, however, is that it exhibits performance degradations because it does not make use of reference regularities such as sequential and looping references. In this paper, we present the Unified Buffer Management (UBM) scheme that exploits these regularities and yet, is simple to deploy. The UBM scheme automatically detects sequential and looping references and stores the detected blocks in separate partitions of the buffer cache. These partitions are managed by appropriate replacement schemes based on their detected patterns. The allocation problem among the divided partitions is also tackled with the use of the notion of marginal gains. The performance gains obtained through the use of this scheme are substantial. Trace-driven simulation experiments show that the hit ratios improve by as much as 28% (with an average of 12%) compared to the LRU scheme for the traces we considered.