새로운 분산회선 교환망의 설계와 지연 특성의 해석

조유근(Yoo Kun Cho),김종상(Chong Sang Kim),김영택(Yung Taek Kim),이석호(Sukho Lee),이정태(Jung Tae lee),이동호(Dong Ho Lee),류광열(Kwang Ryeol Ryu) 한국정보과학회 1985 정보과학회논문지 Vol.12 No.1

본 논문에서는 분산교환망이란 새로운 형태의 통신망을 제안하고 그 성능을 분석하여 실현 가능성을 제시하였다. 분산교환망은 한개의 통신망으로 Packet 및 회선교환기능을 동시에 가질 수 있고, 지연시간은 Packet 교환망과 비슷하며 현재의 통신망보다 훨씬 경제적으로 실현될 수가 있다. In this paper, a new communication network called DSN (Distributed Switching Network) is proposed and its performance is analyzed. The topology of DSN is completely linked full binary tree which is a graph produced by taking a full binary tree, connecting all leaf nodes to their neighbors. Each node of binary tree is a simple 3-way switching element and staged circuit switching protocol proposed by Arango is used as switching technique. Result of performance analysis shows that delay time of DSN is reasonable and investment cost of DSN is much less than that of existing centralized packet and circuit switching network.

메시지에 기반한 커널과 모노리딕 커널의 성능 비교

조유근(Yoo Kun Cho),임성락(Seong Rak Rim),이동희(Dong Hee Lee) 한국정보과학회 1992 정보과학회논문지 Vol.19 No.6

유닉스와 같은 모노리딕 커널은 그 기능이 프로시쥬어들의 집합으로 구현되어 있기 때문에 커널 기능을 변경 혹은 추가하기가 매우 어렵다. 반면, 메시지에 기반한 커널은 그 기능을 태스크들의 집합으로 구조화함으로써 이러한 문제를 해결할 수 있다. 본 논문에서는 위의 두가지 구조로 커널 기능을 설계, 구현하고 시스템 호출 처리시간과 인터럽트 지연시간을 측정, 비교 평가하였다. 그 결과 메시지에 기반한 커널은 그 기능을 독립된 태스크 단위로 구조화함으로써 구현이 매우 용이하지만 메시지 교환과 동기화에 의해 4~7배 정도의 시간이 더 소요됨을 알 수 있었다. 이러한 오버헤드를 줄이기 위하여 공유 기억장소를 이용한 기법을 제시하고 어느 정도의 성능을 향상시킬 수 있는지를 평가하였다. Since kernel functions, as in the case of monolithic kernel like UNIX, are implemented as a set of procedures, it is very difficult to modify these procedures or add new features to them. A way to cope with such a problem is to use message-based kernel which is structured as a modular set of tasks. In this paper, we present a design and implementation of two kernel structures. We then measure the processing time of system call and interrupt latency time. Comparing with monolithic kernel, message-based kernel could be implemented very easily by structuring its function as a set of independant tasks, but it takes about 4~7 more to handle system call due to message exchange and synchronization overhead. Finally, we suggest an alternative mechanism which uses the shared memory to reduce this overhead and show that the performance can be enhanced dramatically.

실시간 오퍼레이팅 시스템의 설계 및 구현

조유근(Yoo Kun Cho),전우직(Wu Jik Jun),이병도(Byung Do Lee) 한국정보과학회 1984 정보과학회논문지 Vol.11 No.2

본 논문에서는 다양한 실시간 응용분야에 사용할 수 있는 실시간 오퍼레이팅 시스템을 구성하는데 필요한 설계목표를 제시하고 이를 바탕으로 하나의 모델 시스템을 설계하고 이를 구현하였다. 본 논문에 제시된 모델시스템은 설계목표를 다중 프로세스 구조화, 이동성, 확장성, 응용의 용이성 등으로 설정하였다. 이를 위해 본 논문에 제시된 모델에서는 프로세스를 근간으로 시스템을 구성하여 수정과 확장을 용이하게 하였고, 각 프로세스는 단일 형태의 메시지 전달방식을 사용하도록 하여 응용분야에 다른 시스템의 재구성이나 변경을 용이하게 하였다. 이러한 구성기법은 다수의 마이크로 프로세서로 구성된 분산처리형 실시간 시스템에도 이 모델을 쉽게 확장적용할 수 있게 한다. 제시된 모델은 기계에 종속적인 부분과 독립적인 부분으로 구분하여 전자는 기계어로 후자는 고급언어로 구성하였으며, 이를 모트롤라사의 MC68000 마이크로 프로세서를 이용한 컴퓨터에 구현하여 응용 예를 보이고 그 성능을 분석하였다. We present and analyze basic requirements for a general purpose real time operating system. We establish design objectives and present a model system based on these criteria. The model presented in this paper was built using multi-process structuring concept and all the interactions between processes are based on message exchange mechanism. Therefore extension and modification of the system can be done easily. This structuring concept makes the model easily extended to the distributed real time environment. The model system divides the system function into machine dependent part and machine independent part. The former was written in machine language and the latter was written in C language. We implemented this model on a single board computer based on MC68000 microprecessor. We also present an application example and analyze performance in terms of response time.

프리엠티브 샵 스케쥴링 문제에 관한 연구

조유근(Yoo Kun Cho),이성기(Sung Kee Lee) 한국정보과학회 1981 정보과학회논문지 Vol.8 No.2

플로우샵(flow shop), 잡샵(job shop) 및 오픈샵(open shop)에 대한 프리엠티브 스케쥴링 문제를 검토하였다. 본 논문에서는 이들 샵(shop)에 부과된 작업(job)들이 작업개시 시간과 작업완료 시간이 주어져 있을 때의 문제를 다루고 있다. 플로우샵과 잡샵의 경우에는 이 문제는 앤피-컴플리트(NP-Complete)문제가 된다. 오픈 샵의 경우 프리엠티브 스케쥴링 문제는 선형계획법(Linear Programming)을 이용할 수 있으나, 여기서는 제한된 조건을 가진 오픈샵의 문제에 대해 효율적인 알고리즘을 제시하고 있다. The problem of preemptive scheduling for a set of n independent jobs on an m processor open shop is discussed. It is assumed that each job has associated with it a release and due time. No job can begin before its release time. All jobs must be completed by their respective due times. It is known that determining the existence of feasible DD-schedules for the flow shops and job shops is NP-complete even when all jobs have the same release and due times. [8, 11]. It is also known that the problem of preemptive scheduling for the open shop can be solved by a linear programming formulation [2, 181. We obtained fast polynomial time algorithms for the open shops under certain restrictions.

페이지 선사상 및 선반입 기법

조성제(Cho Seong Je),조유근(Cho Yoo Kun) 한국정보과학회 1995 정보과학회논문지 : 시스템 및 이론 Vol.22 No.11

페이지 부재 궤적(Page fault trace)을 분석하여 보면 많은 페이지 부재가 디스크 입출력없이 처리될 수 있다는 것을 알 수 있다. 본 논문에서는 이러한 페이지 부재로 인한 오버헤드를 줄일 수 있는 방법으로 페이지 선사상(page premapping) 기법을 제안한다. 페이지 선사상 기법이란 다음에 참조될 페이지를 미리 사상(동적 heap에서 부재가 발생한 경우에는 미리 할당)시켜 페이지 부재의 수를 줄이는 방법이다. 또한 물리적 메모리의 가용 공간이 프로그램 수행에 필요한 가상 메모리 공간보다 클 경우에는 프로그램 수행 초기에 텍스트와 초기화된 데이타 영역에서 발생하는 초기 페이지 부재가 전체 시스템 성능에 큰 영향을 미친다. 이를 위해서는 페이지 반입 지연 시간을 단축시켜 주는 페이지 선반입(page prefetching) 기법도 제안한다. 본 시스템에서는 초기 페이지 부재에 대해서만 선반입 기법을 적용한다. 제안된 선사상과 선반입을 구현하기 위해 페이지 참조 순서를 반영하는 사용자 수준 힌트를 이용하며, 힌트는 프로그램을 미리 수행시켜 그때 발생되는 페이지 부재를 추적하여 수집한다. 제시된 두 기법을 적용하여 실험한 결과에 의하면 프로그램의 응답 시간과 수면 시간이 많이 단축됨을 확인할 수 있다. The analysis of programs' page fault trace shows that a large number of faults can be handled without disk I/O To reduce the overhead of these faults, we propose a page premapping scheme. The premapping scheme tries to decrease the number of page faults by allocating(for the faulted pages of dynamic heap) or mapping in advance page(s) that will be accessed next. If the amount of available physical memory is larger than that of the virtual memory required by a program, the page faults that is caused at the program start time exert a strong influence on its performance. For this case. we also present a page prefetching scheme to reduce pagein delay at the start time of a program. Our prefetching scheme is applied only for the page faults that are incurred at the program start time, Premapping and prefetching are implemented using user level hints that reflect the sequence of page reference Hints are obtained by executing the program in advance and tracing the page faults incurred at that time Experiments show that our schemes are effective in reducing the response time and the sleep time of program.

서명 요청자의 계산량을 감소시키는 RSA에 기반한 개선된 부분은닉서명 알고리즘

권문상,조유근,Kwon, Moon-Sang,Cho, Yoo-Kun 한국정보과학회 2002 정보과학회논문지 : 시스템 및 이론 Vol.29 No.5

'부분은닉서명(Partially Blind Signature)'기법은 전자화폐나 전자투표와 같이 사용자의 프라이버시가 중요시되는 응용에서 사용된다. 본 논문에서는 서명 요청자의 계산량을 줄이는 RSA 알고리즘에 기반한 부분은닉서명 기법을 제안한다. 서명 요청자는 메시지를 은닉하여 서명자에게 전송하고 서명자가 생성한 중간 서명으로부터 최종 서명을 생성하는 과정에서 계산을 필요로 한다. 논문에서 제안하고 있는 기법은 서명 요청자가 적은 계산량을 필요로 하는 모듈러 합과 곱 연산만으로 최종 서명을 계산할 수 있게 하므로 서명 요청자의 계산량을 많이 감소시킨다. 따라서, 이동통신 기기나 스마트카드, 전자지갑 같이 계산능력이 떨어지는 장치들에서 사용하기에 적합하다. Partially blind signature scheme is used in applications such as electronic cash and electronic voting where the privacy of the signature requester is important. This paper proposes an RSA-based enhanced partially blind signature scheme minimizing the amount of computation of the signature requester. The signature requester needs computation in blinding the message to the signer and in generating the final signature using the intermediate signature generated by the signer. Since the proposed scheme enables the signature requester to get the final signature just by using modular additions and multiplications, it decreases computation of the signature requester considerably. So, the proposed partially blind signature scheme is adequate for devices such as mobile device, smart-card, and electronic purse that have relatively low computing power.

객체 지향 기법에 기초한 마이크로 커널의 설계 및 구현

유광현(Kwang-Hyun Yoo),김철민(Cheol-Min Kim),박민규(Min Kyu Park),조유근(Yoo Kun Cho) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.10

운영 체제 커널은 자원 및 서비스를 제공하는 정책(policy) 층과 물리적 하드웨어를 제어하는 기법(mechanism) 층으로 분리될 수 있다. 본 논문은 정책과 기법의 분리에 기반을 둔 운영 체제 구조를 설계하고, 객체 지향 인터페이스를 제공하는 마이크로 커널을 설계 및 구현한 내용을 제시하고 있다. 마이크로 커널은 하드웨어의 기능을 논리적 객체로 상위 수준에 제공하며, 따라서 마이크로 커널은 하드웨어에 대한 제어 기능을 갖는 객체들의 집단으로 간주할 수 있도록 하였다. 각 객체들은 운영 체제가 필요로 하는 하드웨어 기능을 기반으로 하여 설계하였으며, 처리기의 수행 흐름의 제어및 가상 주소 공간 형성에 필요한 기본 함수들과 트랩및 인터럽트등의 사건 처리 기법을 위한 기본 함수들을 도출한 후 이들을 객체화한 인터페이스를 구성하였다. 본 마이크로 커널은 C++언어를 이용하여 구현되었으며, 기존 시스템과의 비교와 성능 측정을 통하여 시스템의 효용성을 입증하고 있다. In this paper, we present the design and implementation of a microkernel based on separation between policy and mechanism in operating system kernel. The microkernel supports the object-oriented interfaces for the computer system hardware as a set of logical objects. The interfaces and roles of microkernel were extracted from the functionality of hardware for operating system kernel. The basic abstraction of microkernel is the flow of control in the processors, primitive functions for composing the virtual address space, handling strategy for event, exception and trap. These are abstracted as objects in microkernel. As a result, the microkernel, called corekernel can be viewed as a collection of objects that control the computer system hardware. We evaluated the performance in order to demonstrate the effectiveness of our microkernel by comparing it with another microkernel-based system.

선형 계산 시간 분할 알고리즘에 의한 표준 셀 배치에 대한 연구

홍성수(Seong Soo Hong),조유근(Yoo Kun Cho),전주식(Chu Shik John) 한국정보과학회 1988 정보과학회논문지 Vol.15 No.5

그래프 분할 문제는 집적회로 설계 과정에서 빈번히 등장하지만 조합적 최적화의 문제로 NP-hard이다. 따라서 heuristic을 이용한 근사 알고리즘이 제안되어 사용되고 있다. 그러나 기존의 heuristic 알고리즘으로는 수행 시간 면에서 만족스러운 결과를 얻을 수 없다. 본 논문에서는 선형적 복잡도를 갖는 새로운 그래프 분할 알고리즘을 제안하고, 이 알고리즘이 기존의 heuristic 알고리즘 보다 시간과 분할 결과에서 우수함을 실험적으로 입증한다. 또한 이 알고리즘을 표준 셀 배치에 적용하여 개선된 분할 배치 알고리즘을 제시하고, 이 알고리즘을 이용하여 표준 셀 자동 배치 시스템(SCAPS)을 구현한 내용을 제시한다. In VLSI tool design process, we frequently face graph partitioning problem, but it is an NP-hard, combinatorial optimization problem. So several heuristic approximation algorithms have been proposed and used. But they are not satisfiable with respect to the time requirement of VLSI design process. In this paper, we propose a new linear time graph partitioning algorithm which is better both in time and in number of cuts produced than already existing algorithms In addition to it, we also propose a standard cell placement algorithm which uses above mentioned graph partitioning algorithm. Finally we present an implementation of a standard cell automatic placement system (SCAPS).

多數의 프로세서를 가진 컴퓨터 시스템에 있어서 Priority Queue를 이용한 병행 스케쥬링 알고리즘

홍영식(Yong-Sik Hong),조유근(Yoo Kun Cho) 한국정보과학회 1985 정보과학회논문지 Vol.12 No.2

In this paper we propose a parallel priority queue in multiprocessing systems which consist of nonidentical processors We develop a parallel scheduling algorithm for non-preemptable tasks of unit length on in processors using parallel priority queues. The shared memory model for parallel computation is used. 본 논문에서는 각 프로세서의 속도가 각각 다른 다중프로세서에서 priority queue를 병행알고리즘으로 구현하고, 이것이 task 처리시간이 단위시간인 task 집합을 스케쥴하기위한 병행 알고리즘 작성에 효과적으로 사용될 수 있음을 보였다. 전제된 다중프로세서는 각 프로세서가 엑세스할 수 있는 공동 기억장치 (Shared memory)를 갖는 계산 모델이다.

단순다각형의 내부점 가시도를 위한 효율적인 RMESH 알고리즘

김홍근(Hong-Geun Kim),조유근(Yoo-Kun Cho) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.11

평면상에 n개의 꼭지점으로 이루어진 단순다각형 P와 그 내부의 한점 z가 주어졌을때, Z로부터 가시적인 P의 경계점을 찾는 문제를 위한 병렬 알고리즘을 제안한다. 병렬처리 모델은 n×n개의 처리기로 구성된 이차원 RMESH이며, 제안된 알고리즘의 시간 복잡도는 O(1)이다. In this paper, we consider the following problem. Given a point z in the interior of a simple polygon P with n vertices, find all the boundary points of P that are visible from z. We present a fast parallel algorithm for this problem on a two dimensional reconfigurable mesh. Our algorithm runs in O(1) time using n×n processors.