SMERT: 읽기 전용 트랜잭션에 대한 스케쥴링 기법

김성석,정순영,이상근,황종선 高麗大學校附設 컴퓨터科學技術硏究所 1999 JOURNAL OF COMPUTER SCIENCE & ENGINEERING TECHNOLO Vol.1 No.-

무선 통신 기술이 발달함에 따라, 이동성을 가진 사용자가 무선 채널을 사용하여 다양한 정보 서비스를 받을 수 있게 되었다. 이러한 무선 이동 컴퓨팅 환경은 본래 많은 새로운 특징 및 제약조건을 가지고 있다. 따라서 이전의 분산 컴퓨팅 환경에서 정보 서비스를 제공하기 위해 제안되었던 알고리즘을 수정없이 그대로 적용한다면, 여러 문제점이 생길 수 있다. 이 논문에서는 무선 통신 기능을 가진 이동 컴퓨터에서 읽기 전용 트랜잭션을 제기할 경우, 자신의 캐쉬 데이터를 이용하여 지역적으로 처리할 수 있는 스케쥴링 기법을 제안한다. 이러한 캐쉬 데이터는 데이터 서버의 주기적인 브로드캐스팅 정보를 이용하여 일관성을 유지시킨다. 이렇게 지역적인 수행을 하더라도 트랜잭션의 올바른 수행을 보장하기 위하여, 이 논문에서는 읽기 트랜잭션의 수행 순서를 재순서화 하는 기법을 사용한다. 즉 서버에서 수행되는 쓰기를 포함하며, 읽기 전용 트랜잭션과 충돌이 발생하는 트랜잭션과의 연산 순서를 데이터의 의미를 고려하여 재순서화 하며, 이러한 순서관계를 지킬 수 있도록 트랜잭션의 연산들을 스케쥴링 한다. 또한 제안하는 스케쥴링 알고리즘(SMERT : Scheduing MEthod for Read-only Trasactions)에 의하여 트랜잭션을 수행하면, 트랜잭션의 검증을 완전히 이동 컴퓨터에서 수행할 수 있으므로, 이동 컴퓨터의 자원을 효율적으로 사용할 수 있게 해준다. 제안하는 SMERT에 의한 수행에 영향을 줄 수 있는 인자에 대한 실험 및 그 결과도 분석한다. With the development of wireless communication technology, various information services have been available to users having mobility. Since wireless mobile computing enviroments have their own characteristics and limitations, if we adopt the algorithms developed for distributed computing environments in mobile environments without modification, we may have some problems. In this paper, we propose a new scheduling technique for read-only transactions, which executes and validates them based on its cached data. A mobile computer maintains cache consistency by using periodic broadcast information. In order to provide correct local execution, we use the reordering technique; that means a mobile computer determines conflict orders between operations according to data semantics. A mobile computer executes operations without violating the determined conflict orders. We call this scheduling method SMERT. Because SMERT allows read-only transactions to be terminated without any messages for synchronization, a mobile computer can use its limited resources efficiently. In the last section, we present a simulation study about the relation between response time and various parameters.

A Compact Broadband Beam-Forming Network Design using an Equivalent Phase Delay

Han, Sang-Min,Kwon, Koo Hyung,Kim, Young-Sik 고려대학교 컴퓨터과학기술연구소 2003 JOURNAL OF COMPUTER SCIENCE & ENGINEERING TECHNOLO Vol.5 No.-

New compact, broadband phase shifter and its equivalent phase deay line for the design of beam-forming network are proposed. The phase shifter is able to control a 120˚phase shift continuously, and the phase delay line for a reference phase has a fixed 60˚shifted phase. Both have the low phase error of less than ±3.5˚and the low gain variations of less than 1dB within the 300MHz bandwidth. These can be adequate to form the effcient beam-forming networks with compactness, broadband, less complexity and low cost.

동기적 검사점 기법에서의 쓰레기 처리 기법

정광식,안병주,유헌창,황종선 고려대학교 컴퓨터과학기술연구소 2001 JOURNAL OF COMPUTER SCIENCE & ENGINEERING TECHNOLO Vol.3 No.-

이 논문은 동기적 검사점 기법에서 결함 포용을 목적으로 불안전 저장 장치(volatile storage)에 저장되는 메시지 로그과 안전 저장 장치에 저장되는 검사점의 쓰레기 처리 기법을 제안한다. 기존의 동기적 검사점 기법을 기반으로 한 결함 정보 쓰레기 처리 기법은 가장 최근의 검사점을 제외한 모든 결함 정보를 쓰레기 처리하였다. 하지만 TCP/IP와 같은 신뢰성을 갖는 동기적 검사점 기법이 가장 최근의 검사점만을 복귀 회복 기법에서 사용한다면, 불필요한 복귀(sympathetic rollback)가 발생된다. 이 논문은 동기적 검사점 기법에서 손실 메시지(lost message)를 해결하기 위해 각 프로세스가 동기화된 가장 최근의 검사점외에 검사점이나 메시지 로그를 유지해야 한다는 것을 입증했다. 또한 손실 메시지 해결을 위해 관리되어야 하는 검사점이나 메시지 로그가 쓰레기 처리되어지기 위해 필요한 조건을 새롭게 정의하며, 이 정의를 기반으로 한 검사점과 메시지 로그의 쓰레기 처리 알고리즘을 제안한다. 제시된 조건을 기반으로 한 검사점과 메시지 로그의 쓰레기 처리는 송수신 메시지에 부가된 손실 메시지 관련 프로세스 정보를 이용하므로 쓰레기 처리를 위한 부가적인 메시지를 발생시키지 않는다. 제안된 기법은 일반 메시지가 송수신되기 전까지 쓰레기 처리가 지연되는 '지연 쓰레기 처리 현상(lazy garbage collection)'을 발생시킨다. 하지만 '지연 쓰레기 처리 현상'은 분산 시스템의 일관성을 위배하지 않는다. This paper presents a garbage collection protocol for checkpoints and message logs which are saved on the stable storage or volatile storage for fault tolerancy. The previous works of garbage collections in coordinated checkpointing protocol delete all the checkpoints except for the last checkpoints on each processes. But implemented on top of reliable communication protocol like as TCP/IP, rollback recovery protocol based on only last checkpoints makes sympathetic rollback. We show that the old checkpoints or message logs except for the last checkpoints have to be preserved in order to replay the lost messages. And we define the conditions for garbage collection of checkpoints and message logs for lost messages and present the garbage collection algorithm for checkpoints and message logs in coordinated checkpointing protocol. Since the proposed algorithm uses process information for lost message piggybacked with messages, the additional messages for garbage collection is not needed. The proposed garbage collection algorithm makes 'the lazy garbage collection effect', because relying on the piggybacked checkpoint information in send/receive message. But 'the lazy garbage collection effect' does not break the consistency of the whole systems.

이동 컴퓨팅을 위한 메시지 지향 미들웨어 서비스

백광진,안영아,김태우 高麗大學校附設 컴퓨터科學技術硏究所 1999 JOURNAL OF COMPUTER SCIENCE & ENGINEERING TECHNOLO Vol.1 No.-

MOM(Message Oriented Middleware)은 새로이 주목받고 있는 분산 통신을 위한 개념이다. 기존의 MOM은 이동 컴퓨팅 환경을 위한 기능을 지원하지 않고 있다. 앞으로 이동 컴퓨팅에 대한 요구는 증가할 것이며 이동 컴퓨팅을 위한 보다 동적인 서비스 제공이 필요하다. 본 논문은 기존 MOM 시스템을 기반으로 하여 이동 컴퓨팅 환경을 지원하는 M-MOM(Mobile MOM) 시스템을 제안한다. M-MOM 환경에서 이동 호스트에서 실행되는 응용 프로그램과 고정 호스트에서 실행되는 메시지 큐 관리자는 베이스 스테이션(Base Station)에서 실행되는 메시지 에이전트를 통해 메시지 큐 관리자와 동적으로 연결된다. M-MOM은 M-RPC(Mobile Remote Procedure Call)에서는 제공하지 않는 베이스 스테이션의 결함을 허용하는 능력과 통신 효율면에서 향상된 기능을 제공한다. MOM (Message Oriented Middleware) is distributed communications framework. The Interest in MOM systems is growing rapidly. Existing MOM doesn't provide functions for mobile computing environment. In the future, the requirement for mobile computing will increase and more dynamic service is needed. In this paper, we present M-MOM (Mobile-MOM) that supports mobile computing environment and bases on established MOM system. In M-MOM environment, applications are dynamically connected with Message Queue Managers through Message Agents. M-MOM provides a minimum level of fault-tolerance in BS and improves the performance of communication function.

컴포넌트 커널 프레임워크를 이용한 커널의 동적 확장성

양순섭,고영웅,유혁 고려대학교 컴퓨터과학기술연구소 2001 JOURNAL OF COMPUTER SCIENCE & ENGINEERING TECHNOLO Vol.3 No.-

기존의 커널 구조는 응용프로그램의 요구에 따라 커널의 기능을 고치거나 새로이 추가하는 것이 커널 자체의 복잡성으로 인하여 어려운 점이 많고 커널 내의 기능성들을 모듈화 함으로써 어려움을 극복하고자 하고 있다. 하지만 응용프로그램이 다양화되고 이러한 응용프로그램들의 요구에 따라 커널 내의 기능성이 변경되거나 추가됨으로써 이러한 모듈화는 깨어지고 있다. 즉 변경되거나 새로이 추가될 기능성을 미리 예측하는 것이 불가능하기 때문에 어떠한 모듈을 접근하는데 있어 고정된 1차원적인 인터페이스만으로는 모듈화를 유지하기가 힘들게 되고 특히 멀티미디어와 같은 새로운 응용프로그램들은 기존의 커널에 많은 새로운 기능들의 추가를 요구하고 있어서 상황은 더욱 악화되고 있다. 본 논문에서는 이러한 커널 복잡도를 낮추고 커널 구조를 보다 유연하게 만들기 위한 방안으로서 코어커널(CoreKernel)과 커널컴포넌트(KernelComponent)들의 집합으로서 커널을 구성하는 컴포넌트 커널 프레임워크(Component Kernel Framework)를 제시하고 이에 기반한 커널의 동적 확장 모델을 설계한다. 제시한 컴포넌트 기반 커널 확장 모델을 검증하고자 현재 개발중인 커널 프로토타입 소개하고 시뮬레이션을 통해 제안된 동적 확장 모델을 검증한다. Traditional kernels like UNIX have lots of difficulties in adding and modifying kernel functionalities due to inherent complexities of kernel architecture. They try to solve these problems through modularization. As there come to be a diversity of application programs and they require modification of existing kernel functionalities and addition of new ones, Modularity of kernel tends to be broken. In other words, because it is difficult to expect which functionality should be modified and what functionality should be newly added, To keep modularity of kernel is almost impossible if the modules are accessed only through fixed one-dimensional interface. This situation is likely to happen as multimedia applications that require new kernel functionalities like real-time scheduling and memory reservation become popular. Trying to decrease kernel complexities and to make kernel more modularized, this paper suggests Kernel Component Framework that construct kernel of Corekernel and a set of KernelComponents and then designs dynamic kernel extension model based on Kernel Component Framework. To verify suggested component-based kernel extension model, we introduce kernel prototype now being developed and simulate dynamic extension model.

국부적 향상을 이용한 셀룰러 학습 기반 유전자 알고리즘

고명숙 고려대학교 컴퓨터과학기술연구소 2001 JOURNAL OF COMPUTER SCIENCE & ENGINEERING TECHNOLO Vol.3 No.-

유전자 알고리즘(GA: Genetic Algorithm)은 최적화 문제를 풀기 위해 생물학적 진화(evolution) 과정을 모방한 최적화 알고리즘이다. 유전자 알고리즘은 복잡한 상태 공간에서 최적 해를 찾기 위해 전통적인 최적화 기법과는 달리 유향적 임의 탐색을 행한다. 학습에 해당하는 국부 탐색(local search)을 유전적 탐색과 결합시킨 복합 유전자 알고리즘은 exploration 탐색과 exploitation 탐색의 균형을 유지시켜 줄 수 있는 한 방법이다. 모집단 내의 각 개체가 진화 과정 중에 학습한 유전적 특질들은 그 다음 세대에서 되물림 되며 이러한 학습(learning) 과정을 유전자 알고리즘과 결합시킴으로써 탐색 속도의 향상을 기대할 수 있다. 이 논문에서는 함수 최적화를 위해 학습 속도를 개선한 셀룰러 학습을 기반으로 하는 유전자 알고리즘을 제안한다. 제안하는 셀룰러 학습 전략은 셀룰러 오토마타의 주기성과 수렴성을 기반으로 하며, 유기체가 그 개체의 생명 주기의 한 세대에서 얻게되는 지식과 경험들을 자손에게 전달한다는 이론을 바탕으로 한다. 제안한 셀룰러 학습 전략의 효율을 기존의 복합 유전자 알고리즘에서의 라마키안 진화 및 볼드윈 효과와 비교하였다. 다양한 테스트 베드 함수에 대한 실험을 통하여 셀룰러 학습에 의한 개체의 국부적 향상이 전체적인 성능 향상에 기여함을 알 수 있었고 제안한 학습 전략이 기존의 방법보다 더 빨리 전역 최적 해를 찾을 수 있음을 증명하였다. Genetic Algorithms are optimization algorithm that mimic biological evolution to solve optimization problems. Genetic algorithms provide an alternative to traditional optimization techniques by using directed random searches to locate optimal solutions in complex fitness landscapes. Hybrid genetic algorithm that is combined with local search called learning can sustain the balance between exploration and exploitation. The genetic traits that each individual in the population learns through evolution are transferred back to the next generation, and when this learning is combined with genetic algorithm we can expect the improvement of the search speed. This paper proposes a genetic algorithm based Cellular Learning with accelerated learning capability for function optimization. Proposed Cellular Learning strategy is based on periodic and convergent behaviors in cellular automata, and on the theory of transmitting to offspring the knowledge and experience that organisms acquire in their lifetime. We compared the search efficiency of Cellular Learning strategy with those of Lamarckian and Baldwin Effect in hybrid genetic algorithm. We showed that the local improvement by cellular learning could enhance the global performance higher by evaluating their performance through the experiment of various test bed functions and also showed that proposed learning strategy could find out the better global optima than conventional method.

The displaced subdivision surface reconstruction from unorganized points

Jeong, Won-Ki,Kim, Chang-Hun 고려대학교 컴퓨터과학기술연구소 2001 JOURNAL OF COMPUTER SCIENCE & ENGINEERING TECHNOLO Vol.3 No.-

본 논문은 연결정보가 없는 거리영상으로부터 DSM(Displaced Subdivision Mesh)을 복원하는 기술을 제안한다. DSM은 메쉬의 표면정보를 메쉬 분할법으로 생성한 부드러운 표면과의 차이 값으로 표현할 수 있으므로 메쉬를 표현하는 데이터 크기를 획기적으로 줄일 수 있으며, 거리영상에 근접한 3차원 모델 복원기술에 효율적으로 적용될 수 있다. 제안 알고리즘은 기존 방법에서 사용하던 전역적 에너지 최소화 과정을 기하해석적인 방법으로 대체하여 빠르게 메쉬를 복원할 수 있으며, 복원된 메쉬는 Remeshing을 거치치 않고 바로 다단계 표현으로 변환이 가능하다. 또한 입력 데이터를 고려한 라플라시안을 이용하여 거리영상에 최대한 근접하면서 지역적인 곡률이 최소화 된 DSM을 생성한다. 이렇게 복원된 DSM은 메쉬 편집, 압축, 렌더링, 애니메이션 등 여러 응용분야에서 사용될 수 있다. In this paper we propose a new mesh reconstruction scheme that produces a displaced subdivision surface directly from unorganized points. The displaced subdivision surface is a new mesh representation that defines a detailed mesh with a displacement map over a smooth domain surface, but original displaced subdivision surface algorithm nerds an explicit polygonal mesh since it is not a mesh reconstruction algorithm but a mesh conversion (remeshing) algorithm. The main idea of our approach is that we sample surface detail from unorganized points without any topological information. For this, we predict a virtual triangular face from unorganized points for each sampling ray from a parameteric domain surface. Direct displaced subdivision surface reconstruction from unorganized points has much importance since the output of this algorithm has several important properties: It has compact mesh representation since most vortices can be represented by only a scalar value. Underlying structure of it is piecewise regular so it can be easily transformed into a multiresolution mesh. Smoothness after mesh deformation is automatically preserved. We avoid time-consuming global energy optimization by employing the input data dependant mesh smoothing, so we can get a good quality displaced subdivision surface quickly.

Application-controlled Multimedia Scheduling

Ko, Young Woong,Yoo, Chuck 고려대학교 컴퓨터과학기술연구소 2002 JOURNAL OF COMPUTER SCIENCE & ENGINEERING TECHNOLO Vol.4 No.-

Real-time scheduling algorithms such as Rate Monotonic and Earliest Deadline First are a basis for many multimedia scheduling algorithms. However, real-time scheduling mechanisms have drawbacks to multimedia applications. One of them is that multimedia application such as digital video has a large variation in execution time, which makes real-time scheduling algorithms very inefficient in terms of resource utilization. To improve the resource utilization, this paper introduces an application-controlled approach. A task passes scheduling information to the scheduler so that the scheduler dynamically changes the priority of the task. In addition, an advantage of our approach is that multimedia tasks are scheduled based on priority only. Therefore, multimedia tasks do not penalize time-sharing tasks. We implement the new scheduler on Linux kernel and present the experiment results with Berkeley MPEG-1 video decoder.

Corpus-based Query Translation and Query Expansion for English-Korean Cross-Language Information Retrieval

Seo, Hee-Cheol,Rim, Hae-Chang 고려대학교 컴퓨터과학기술연구소 2003 JOURNAL OF COMPUTER SCIENCE & ENGINEERING TECHNOLO Vol.5 No.-

This paper describes corpus-based query translation and query expansion for English-Korean cross-language information retrieval. The bilingual dictionary and the document language corpus are used for the query translation. To automatically transliterate some proper nouns such as Korean person names, Korean place names, and Korean company names, we have constructed the bilingual biographical dictionary, and collected the corresponding translations of Korean place names and Korean company names. And we investigate whether query expansion based on the corpus in document language is useful in English-Korean cross-language information retrieval as other cross-language information retrieval. Experiments show that the performance of our system is 83.02% of monolingual information retrieval system and query expansion is useful in English-Korean cross-language information retrieval. In addition, Korean query which consists of the best translation equivalents for English query terms is more effective the that consisting of two or more translation equivalents and including English acronyms and initial words in Korean query is helpful to retrieve Korean documents.

디지털 상품 정품 인증 프로토콜 설계

김지균,강영일 高麗大學校附設 컴퓨터科學技術硏究所 1999 JOURNAL OF COMPUTER SCIENCE & ENGINEERING TECHNOLO Vol.2 No.-

인터넷의 대중화에 따라 인터넷 웹을 기반으로 전자상거래가 활발해지고 있으며, 인터넷을 통한 전자파일 형태의 상품 즉, 디지털 상품의 구매는 상품의 검색, 조건 비교, 구매, 지불 및 배송 측면에서 사용자에게 편이성을 제공하기 때문에 전자상거래 매출에 있어서 중요한 부분으로 인식되고 있다 특히 디지털 상품의 정품 판매와 정품 구입에 대한 증명은 지적 재산권 및 소프트웨어 유통 측면에서 필수적인 부분을 차지하고 있다 본 논문에서는 인터넷 전자상거래시 디지털 상품의 정품을 증명하고 불법복제를 확인하여 지적 재산권 소유권자, 구매자 및 판매자간의 신용 있는 전자상거래를 위한 범용성 있는 인증 프로토콜 설계 및 개발의 연구를 수행한다. As an internet become public, the electric commerce based on the internet web increases rapidly and a purchase of digital product, the one in the form of electronic files through the internet, is recognized as an important part of electric commerce because it provides convenience to users in terms of search, conditional comparison, purchase, payment, and delivery of the products. Especially, the verification about purchase and selling of licensed product plays an essential role in the intelligent property and software circulation. In this paper, we describe the design of authentication protocol having general purpose for confidential electric commerce between copyrighter of intelligent property, purchaser, and seller by verifying digital product as licensed product and certifying illegal copy.