일정한 數의 버텍스를 갖는 서브트리의 리스팅 및 카운팅

조유근(Yookun Cho),표창우(Changwoo Pyo) 한국정보과학회 1982 정보과학회논문지 Vol.9 No.1

순서를 갖는 트리가 주어졌을 경우, 두 종류의 일정한 수의 버텍스 들을 갖는 서브트리들의 나열을 생각할 수 있다. 리스팅, 랭킹 그리고 언랭킹에 대한 알고리즘이 제시되어 있다. 일정한 수의 버텍스들을 갖는 서브트리들의 갯수를 세기 위한 제너레이팅 함수를 제시하였다. Given an ordered three T, two kinds of ordering are defined on the set of subtrees with a fixed number of vertices of T. Algorithms are presented for listing, ranking, and unranking. Generating function for counting subtrees with a fixed number of vertices is given in a recursive formula.

단일행 라우팅을 위한 층배정휴리스틱 알고리즘

조유근(Yookun cho) 한국정보과학회 1986 정보과학회논문지 Vol.13 No.1

본 논문에서는 먼저 주어진 네트를 좌측에서 우측으로 살펴나가면서 단일 층 내에서 배선 순서를 결정하는 단순한 단일행 라우팅 알고리즘을 제시한다. 또한 위의 알고리즘을 사용하여 단일행 배선 라우팅 기법을 사용할 경우 발생하는 층배정 문제를 해결하는 세개의 빠른 알고리즘을 개발하였다. 이들 알고리즘은 모두 각 네트가 2개의 접점을 갖고 상위와 하위의 배선 폭이 임의의 동일한 크기를 가질 경우에 적용 가능하다. 이들 알고리즘은 모두 최적의 층배정을 보장하진 않지만 이들 중 한 알고리즘은 이미 발표된 배선폭이 2인 경우 층 배정을 행하는 알고리즘 보다 나은 층 배정을 함을 실험적으로 보였다. We first present a simple single row routing algorithm that decides the ordering of given nets by scanning them from left to right. Next, we develop three fast algorithms based on above algorithm for the layering problem that arises when the single row routing approach is used to wire layout. All of these algorithms are for the case when the upper and lower street capacities are arbitrary equal and each net has two touch points. While none of these algorithms guarantees to produce optimal layerings, one of the proposed algorithms is empirically shown to produce better layerings than already proposed algorithm for the street capacity of two.

운영체제의 개발동향

조유근(Yookun Cho) 한국정보과학회 2023 정보과학회지 Vol.41 No.4

페이지 선반입 및 선사상을 위한 페이지 부재 궤적 분석

조성제(SungJe Cho),박홍식(HongSik Park),조유근(YooKun Cho) 한국정보과학회 1995 한국정보과학회 학술발표논문집 Vol.22 No.1

페이지 선반입(page prefetcing)은 다음에 참조될 페이지를 디스크로부터 미리 읽어들임으로써 페이지 반입 지연 시간을 줄여 준다. 본 논문에서는 디스크로부터 선반입할 페이지를 결정하기 위해 페이지 부재의 궤적(page fault trace)을 분석하였다. 메모리 부하가 적을때 페이지 부재의 궤적을 분석하여 보면, 총 부재에서 디스크로부터 입력을 필요로하는 페이지 부재의 비율은 응용에 따라 다소 차이는 있지만 7.2~26.1%로 비교적 적은 편이며, 대부분의 부재는 공유 라이브러리 영역이나 sbrk 시스템 호출 수행시 할당받는 heap 영역에서 발생한다. 이는 사용가능한 메모리의 용량이 가상 메모리 요구량보다 클때 페이지 선반입 기법만 사용해서는 많은 성능 향상을 기대할 수 없다는 것을 암시한다. 본 논문에서는 페이지 부재가 발생했을 때 프로세스가 다음에 참조할 페이지가 이미 메모리에 상주하거나 또는 가용 페이지를 할당하여 부재 발생을 예방할 수 있는 경우에는 다음 페이지를 미리 페이지 테이블에 사상(할당)하는 기법도 간략히 소개한다.

선반입과 캐슁 기법을 이용한 이주 프로세스의 효율적인 수행

조성제(Seongje Cho),조유근(Yookun Cho) 한국정보과학회 1996 정보과학회논문지 : 시스템 및 이론 Vol.23 No.8

본 논문에서는 효율적인 부하 균등화를 위하여 페이지 선반입(page prefetch) 기법과 텍스트 세그먼트 캐슁(text segment caching) 기법을 이용하는 새로운 비선점형 프로세스 전송(nonpreemptive process transfer) 정책을 제안한다. 페이지 선반입 기법이란 이주 프로세스에 의해 창조될 다음 페이지를 근원지 노드의 디스크로부터 원격 노드의 메모리로 미리 반입시켜 디스크 접근 지연 시간과 네트워크 전송 지연 시간을 단축시키는 방법이다. 페이지 선반입은 서버 프로세스에 의해 수행되며 이주 프로세스의 전송 지연 시간을 단축시켜 준다. 이 기법은 프로그램의 페이지 이주 순서를 반영하는 페이지 부재 궤적에 기반하여 수행되는데, 이를 위해 본 시스템은 해당 프로그램의 이전 실행 시에 발생된 페이지 부재 궤적을 수집하여 이용한다. 텍스트 세그먼트 캐슁 기법은 목적지 노드로 이주되어 실행이 종결된 프로세스에 대하여 일정 기간동안 텍스트 세그먼트를 목적지 노드의 메모리에 유지함으로써 프로세스 이주시 텍스트 세그먼트를 전송할 필요가 없도록 하여 준다. 텍스트 캐슁 기법 하에서 원격 노드로 이주될 프로세스로 동일한 프로세스가 또다시 선택될 경우, 그 프로세스가 이전에 이주된 적이 있는 노드로 이주시켜 실행시킴으로써 텍스트 세그먼트를 전송할 필요없이 고속 수행할 수 있다. 제시된 두 기법을 적용하여 실험한 결과 이주 프로세스의 응답 시간과 수면 시간이 많이 단축되었다. In distributed computing environment, load balancing has been one of main issues. For efficient load balancing, we propose a new nonpreemptive process transfer policy based on page prefetch and text segment caching schemes. Page prefetch scheme tries to reduce disk access and network transfer latencies by transferring beforehand the predicted pages which a migrated process will reference shortly to memory of a remote node from disk of a source node. Prefetch is performed by server process and reduces process transfer latency. The prefetch is implemented using page fault traces that are obtained at a previous execution of program and reflect the sequence of page migration. Text segment caching scheme tries to eliminate text segment transfer of a migrated process by caching the text segment in the destination node for a period of time after the process has terminated. If the process needs to be migrated again under our text caching scheme, it can be executed rapidly on the node where it has previously been migrated without transferring its text segment. Experimental results show that our schemes induce little overhead and are effective in reducing the response time and the sleep time of migrated processes.

MIXTURE : 분산 프로그램 개발 시스템

조규찬(Kyoochan Cho),조유근(Yookun Cho) 한국정보과학회 1988 한국정보과학회 학술발표논문집 Vol.15 No.2

본 논문에서는 분산 프로그램 개발 시스템, MIXTURE의 설계 내용을 기술하고 있다. MIXTURE는 다중 언어로 작성된 분산 프로그램의 개발을 지원하고, 분산 수행되는 모듈들 사이에 공유 데이타 오브젝트를 제공함으로써, 효율적인 분산 프로그래밍 환경을 지원한다.

분산 시스템 환경을 위한 확장된 UNIX System V IPC

조규찬(Qchan Cho),김길용(Kilyong Kim),조유근(Yookun Cho) 한국정보과학회 1988 한국정보과학회 학술발표논문집 Vol.15 No.1

본 논문에서는 네트워크 환경하에서 분산된 프로세스들 사이의 통신을 효과적으로 지원할 수 있도록 UNIX System V의 프로세스간 메시지 통신 기능을 확장하는 기법에 대하여 기술하고 있다. 분산 IPC의 구현 작업은 Ethernet으로 연결된 다수의 마이크로컴퓨터들을 대상으로 수행되었으며, 기존의 시스템에 대하여 동일한 사용자 인터페이스를 유지하도록 하였다.

스마트 카드 응용 프로그램의 다운로드와 갱신에 대한 효율적인 인증 기법

박용수(Yongsu Park),조유근(Yookun Cho) 한국정보과학회 2004 정보과학회논문지 : 시스템 및 이론 Vol.31 No.1·2

본 논문에서는 스마트 카드에서 응용 프로그램을 다운로드하거나 갱신할 때 응용 프로그램의 위/변조를 효율적으로 검증할 수 있는 인증 기법을 제시한다. 기존 기법은 응용 프로그램을 인증할 때 검증 지연 시간이 길거나, 스마트 카드의 2차 메모리 오버헤드가 많거나, 혹은 많은 양의 1차 메모리를 요구한다. 제안된 기법은 해쉬 체인 기법을 효율적으로 사용한 파라미터화 기법으로서, 응용 블록 수가 n일 때 메모리 오버헤드와 응용 프로그램을 갱신 시 발생하는 검증 지연 시간이 각각 O(k), O(k+n/k)이다. 또한 제안 기법은 1차 메모리 요구량이 O(1)으로 가장 적으며, 응용 프로그램을 다운로드 시 생기는 검증 지연시간도 O(1)으로 가장 적다. In this paper we propose a method for authenticating the application that is to be downloaded or updated in smart cards. Previous works have some drawbacks such as having a long verification delay or requiring a large amount of primary/ secondary storage. We propose an efficient parameterized scheme by using the hash chain technique where the secondary storage requirement and verification delay of updating the application are O(k) and O(k+n/k), respectively. Moreover, both the first storage requirement and verification delay of downloading the application are O(1).

스트림 인증에 적합한 개선된 HORS 기법

박용수(Yongsu Park),조유근(Yookun Cho) 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.30 No.7·8

본 논문에서는 스트림 데이타를 인증하는데 적합한 개선된 HORS 일회용 서명 기법을 제시한다. 스트림 인증에 일회용 서명 기법을 사용할 경우, 가장 큰 문제점은 큰 서명 크기로 인해 네트워크 오버헤드가 많다는 점이다. 제시한 기법은 기존 일회용 서명 기법 중 서명 크기가 가장 작다. 또한, 제시된 기법의 검증 연산량은 매우 작다. 스트림 인증에 적합한 기존 기법과 온라인 서명 연산량을 비교하면, HORS보다는 다소 많지만, BiBa나 Powerball보다 매우 작다. 제시된 기법에서 서명 연산은 쉽게 병렬 처리가 가능하며, 특히 비밀키를 가지지 않는 서버의 도움을 받을 수 있기 때문에, 서명 서버의 부하를 손쉽게 그리고 안전하게 줄일 수 있다. We propose an efficient one-time signature scheme for stream authentication by improving HORS. When one-time signatures are used for authenticating live streams, one of the most serious drawbacks is that its large signature size yields high communication overhead. Compared with the previous one-time signature schemes, proposed scheme has the smallest signature size. Moreover, verification overhead is very low. Compared with the previous schemes for stream authentication, signing overhead of our scheme is larger than that of HORS but much lower than those of BiBa or Powerball. Moreover, signing operation can be trivially parallelized without any additional risk because it does not require sharing of the secret key between distributed servers.

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

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

‘부분은닉서명(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.