하이퍼큐브 환경에서의 DEVS 모델의 병렬 시뮬레이션을 위한 매핑

성영락(Yeong Rak Seong),김탁곤(Tag Gon Kim),박규호(Kyu Ho Park) 한국정보과학회 1995 정보과학회논문지 : 시스템 및 이론 Vol.22 No.10

DEVS(Discrete Event Systems SpecificatIon) 형식론은 이산사건 시스템을 계층적으로 모듈화된 형태로 기술한다. DEVS에서 상태전이는 스케쥴링에 의한 내부사건과 불규칙적으로 도착하는 외부 사건에 의해서 이루어진다. P-DEVSim++는 DEVS 모델들을 위한 병렬 분산 시뮬레이션 환경이다. P-DEVSim++에서는 DEVS의 외부사건 외에 내부사건이 병렬처리 된다. 본 논문에서는 P-DEVSim++을 하이퍼큐브 멀티컴퓨터 환경에서 다중통신 없이 수행할 때 그 병렬성을 이용하기 위한 DEVS 모델의 매핑에 대해서 다룬다. 동시에 발생되는 외부사건에 대해서는 동기화를 위한 오버헤드를 줄이기 위해서 태스크 그래프를 이항트리로 변환하였다. 또 여러 내부사건이 동시에 발생되고 각 내부사건이 여러 외부사건을 야기할 경우에는 전체 하이퍼큐브를 서브큐브들의 집합으로 나누어서 하나의 내부사건과 그에 관련된 외부사건들이 같은 서브큐브에서 처리되도록 하였다. 실험을 통하여 제안된 알고리즘의 성능을 측정하였다. 실험 결과, 파라미터들이 바뀜에 따라, 제안된 매핑 알고리즘은 여러 다양한 매핑을 구하였다. 또, 그 구해진 매핑을 이용하여 계층적으로 모듈화된 이산사건 모델의 분산 시뮬레이션에서의 병렬성을 얻을 수 있었다. The DEVS(Discrete Event System Specification) formalism specifies discrete event systems in a modular, hierarchical manner. Within the formalism, state transition is achieved by scheduled internal events and randomly arrived external events. P-DEVSim++ is a parallel, distributed simulation environment for DEVS models In P-DEVSim++, internal events as well as external events are processed in parallel. This paper addresses mapping of DEVS models to utilize the parallelism of P-DEVSim++ in a hypercube multicomputer environment without multicasting, For simultaneous external events processing, task graphs are transformed into binomial trees to reduce synchronization overhead. Also, when multiple internal events occur simultaneously and each internal event is associated with multiple external events, a hypercube is partitioned into a set of subcubes so that an internal event and the associated external events can be processed in the same subcube. The performance of our algorithm is measured through experimentation The result shows that the proposed mapping algorithm generates diverse mappings against various combinations of system parameters. With the generated mapping, the significant parallelism of distributed simulation of hierarchical, modular discrete event models is achieved.

원소 밀집을 이용한 원소오토마타 모델의 병렬 시뮬레이션

성영락(Seong Yeong Rak) 한국정보처리학회 1998 정보처리학회논문지 Vol.5 No.4

This paper proposes a scheme to exploit SIMD parallelism in the simulation of Cellular Automata models. The basic idea is to increase the utilization of an ALU in the underlying computer and to reduce simulation time by exploiting the parallelism. Thus, several cells are packed into a computer word and transit their state together. To show the performance of the proposed simulation scheme, two Cellular Automata models are simulated under three distinct hardware environments. The results show considerably high simulation speed-up for every case. Especially, the simulation speedup with the proposed simulation scheme reaches nearly 20 times in the best case.

UHF RFID Air Interface 기술 동향

장병준,오하령,성영락,박준석,Jang, Byeong-Jun,O, Ha-Ryeong,Seong, Yeong-Rak,Park, Jun-Seok 한국통신학회 2007 정보와 통신 Vol.24 No.8

최근 UHF 대역에서 동작하는 RFID 시스템이 활발히 연구되고 있으며, 유통물류 분야를 시작으로 다양한 분야에서 활용되고 있다. 특히, 국내에서는 휴대폰과 RFID를 결합한 모바일 RFID 시스템을 도입하고 있으므로 가까운 미래에 RFID의 도입이 크게 확대될 것으로 기대되고 있다. 하지만 UHF RFID 시스템의 경우 Link Unbalance특성에 의해 주파수 간섭 등의 문제가 대두되어 전세계적으로 Dense 모드의 도입 및 기술기준 개정 움직임이 활발하게 진행되고 있다. 본 고에서는 UHF RFID 시스템에서 발생하는 주파수 간섭에 대해 알아보고, 국내외 UHF RFID Air Interface 기술의 최신 동향을 살펴보고자 한다.

LLRP(Low Level Reader Protocol) 서버를 위한 멀티쓰레드 구조의 설계

이태영,김윤호,성영락,오하령,Lee, Tae-Young,Kim, Yun-Ho,Seong, Yeong-Rak,Oh, Ha-Ryoung 한국정보처리학회 2012 정보처리학회논문지 A Vol.19 No.2

LLRP(Low-Level Reader Protocol)는 RFID 리더(LLRP 서버)와 RFID 어플리케이션들(LLRP 클라이언트)간의 인터페이스를 기술하고 있다. LLRP 서버는 여러 기능들을 동시에 수행해야 한다. 본 논문에서는 LLRP 서버를 멀티 쓰레드 구조로 설계한다. 이를 위하여 (i) LLRP 서버와 클라이언트들 간의 동작 절차를 분석하고, (ii) LLRP 서버가 만족해야 할 기능적인 요구조건들을 제시하고, (iii) 그 요구조건들을 만족할 수 있도록 LLRP 서버의 역할을 여러 쓰레드로 나누고, (iv) 쓰레드 수준에서 LLRP 동작 절차를 세분하였다. 설계된 구조를 검증하기 위하여 이산사건 시스템을 계층적이고 모듈화된 방식으로 기술하는 언어인 DEVS 형식론을 이용하여 설계된 내용을 모델링하고 시뮬레이션 하였다. 시뮬레이션 결과, 제안된 구조는 LLRP 표준과 주어진 모든 기능적 요구 조건들을 만족함을 알 수 있었다. LLRP (Low-Level Reader Protocol) specifies an interface between RFID readers and RFID applications, also called LLRP servers and clients respectively. An LLRP server should concurrently execute various functions. This paper designs an LLRP server of a multi-threaded architecture. For that, (i) the operational procedure between LLRP servers and clients is investigated, (ii) the functional requirements of LLRP servers are presented, (iii) the operation of an LLRP server is decomposed into several threads to satisfy those functional requirements, and (iv) the operational procedure is further examined in thread-level. To validate the designed architecture, it is modeled and simulated by using the DEVS formalism which specifies discrete event systems in a hierarchical, modular manner. From the simulation result, we can conclude that the proposed architecture conforms the LLRP standard and satisfies all the given functional requirements.

유전자 알고리즘을 이용한 대전형 액션게임의 지능캐릭터

이면섭,조병헌,성영락,정성훈,오하령,Lee Myun-sub,Cho Byeong-heon,Seong Yeong-rak,Jung Sung-hoon,Oh Ha-ryoung 한국정보처리학회 2005 정보처리학회논문지B Vol.12 No.3

본 논문에서는 유전자 알고리즘을 이용하여 대전형 액션 게임의 캐릭터를 지능화 하는 방법을 제안한다. 초기에 게임 규칙을 전혀 모르는 캐릭터가 학습이 진행되면 세대를 거듭하면서 스스로 게임규칙을 학습하고 기술을 습득하며 진화할 수 있는 지능을 갖추게 된다. 제안한 캐릭터가 환경변화에 잘 적응하는지를 평가하기 위하여 게임 도중에 게임규칙을 바꾸어 규칙 변경 전후의 결과를 비교 검토하였다. 실험결과 게임규칙이 변경된 후에도 빠르게 새로운 규칙에 적응하였다. 본 논문에서 제안한 방법은 대전형 액션게임뿐만 아니라 PC게임이나 인터넷 온라인 게임 등의 캐릭터 구현에도 쉽게 적용가능한 장점이 있다. This paper proposes a method to provide intelligence for characters in fighting action games by using genetic algorithm. The proposed characters without any knowledge on the rules of the game learn the rules and techniques for generations, and have the capability of evolving. To evaluate adaptability for varying circumstances, we changed the rules and compared the results. The experimental results show that the intelligent characters can adapt to the new rules. An advantage of the proposed method is that it can be easily applied to characters for other category of games such as PC games and internet online games.

신경망을 이용한 지능형 게임 캐릭터의 구현

조병현,정성훈,성영락,오하령,Cho Byeong-heon,Jung Sung-hoon,Seong Yeong-rak,Oh Ha-ryoung 한국정보처리학회 2004 정보처리학회논문지B Vol.11 No.7

본 논문에서는 신경망 기반의 지능형 게임 캐릭터를 구현하는 방법을 제안한다. 지능 캐릭터를 구현하는 신경망은 상대방 캐릭터의 행동과 상대방 캐릭터와의 거리를 입력받아 지능 캐릭터의 행동을 결정하여 출력한다 신경망은 두 캐릭터들의 행동으로 인한 점수를 강화 값으로 사용하여 강화 학습된다. 제안한 방법의 효용성을 보이기 위해서 간단한 대전 액션 게임을 구현하고 그 환경에서 여러 가지 실험을 수행하였다. 실험 견과 제안한 지능형 캐릭터가 게임의 규칙을 잘 학습할 수 있음을 보였다. 제안된 방법은 대전 게임뿐만 아니라 대규모 온라인 게임상의 캐릭터 구현에도 적용될 수 있다. In this paper, we propose a scheme to implement intelligent game characters based on neural networks. Neural networks that implement in-telligent game character receive the action of an opponent character and the distance between them, decide intelligent character's action, and output the decision. The neural networks are trained by reinforcement learning using the scores acquired by the actions of two characters as reinforcement values. To show the usefulness of the proposed scheme, a simple fighting action game is implemented and various experiments are performed. Experimental results show that proposed intelligent characters can learn the rule of the game. The proposed scheme can be ap-plied to massively multiple online games as well as fighting action games.

반복적인 부하 이동에 의한 휴리스틱 부하 평형 알고리즘

송의석,오하령,성영락,Song Eui-Seok,Oh Ha-Ryung,Seong Yeong-Rak 한국정보처리학회 2004 정보처리학회논문지 A Vol.11 No.7

본 논문에서는 다중 프로세서 시스템을 위한 휴리스틱 부하 평형 알고리즘을 제안한다. 제안 알고리즘은 부하이동을 여러 링크로 분산시켜 사용하지 않는 링크의 수를 최소화시키고 그에 따라 통신비용을 감소시킨다. 각각의 프로세서는 모든 이웃한 프로세서에게 단위부하를 보내거나 받는 과정을 반복적으로 시도한다. 그러나 실제의 부하 이동은 모든 부하평형 계산이 이루어진 후 수행된다. 이는 불필요한 부하 이동을 최소화시킨다. 제안된 알고리즘은 약간의 수정만으로 다양한 연결 구조를 갖는 다중 프로세서 시스템에 적용할 수 있다. 본 논문에서는 하이퍼큐브 구조와 메쉬 구조에 제안 알고리즘을 적용해 보았다. 알고리즘의 성능평가를 위하여 모의실험을 하였다. 제안된 알고리즘과 잘 알려진 두 가지 종류의 알고리즘의 성능을 비교하였다. 그 결과 제안된 알고리즘은 모든 경우에서 부하평형의 목적을 달성하였다. 또한 기존의 알고리즘과 비교하여 하이퍼큐브 구조에서는 통신비용을 $70{\%}{\~}90{\%}$ 감소시켰다. 메쉬 구조에서도 통신비용은 약 $\75{\%}$ 감소되었다. This paper proposes a heuristic load balancing algorithm for multiprocessor systems. The algorithm minimizes the number of idle links to distribute load traffic and reduces its communication cost. Each processor iteratively tries to transfer unit load to/from every neighbor processors. However, real load transfer is collectively done after complete load traffic calculation to minimize useless traffic. The proposed algorithm can be employed in various interconnection topologies with slight modifications. In this paper, it is applied to both hypercube and mesh environments. For performance evaluation, simulation studies are performed. The performance of proposed algorithm is compared to those of two well-known algorithms. The results show that the proposed algorithm always balances the loads perfectly. Furthermore, it reduces the communication costs by $70{\%}{\~}90{\%}$ in the hypercube ; and it reduces the cost by $\75{\%}$ in the mesh, compared to existing algorithms.

HDTV 데이타 편집을 위한 고속 실시간 대규모 데이타 저장 시스템의 설계

이찬수(Chan-Su Lee),성영락(Yeong-Rak Seong),오하령(Ha-Ryoung Oh) 한국정보과학회 1999 정보과학회 컴퓨팅의 실제 논문지 Vol.5 No.2

본 논문에서는 HDTV 데이타를 입출력할 수 있는 고속 실시간 데이타 저장 세스템을 제안한다. 이 시스템은 i)방대한 크기를 가지는 HDTV 데이타를 고속으로 입출력할 수 있어야 한다; ii)데이타를 연속적으로 입출력할 수 있는 것 외에 데이타를 비선형적으로 랜덤하게 억세스 할 수 있어야 한다; iii)실시간으로 데이타를 재생하기 위해 일정하게 주어진 시스템 입출력 속도를 항상 만족할 수 있어야 한다. 이러한 조건을 만족시키기 위해서 여러 개의 하드디스크 아암의 탐색 동작에 의해 크게 좌우되므로 탐색 동작을 효과적으로 제어할 수 있는 방법이 설계되었다. 제안된 시스템은 주제어부, 데이타 분배부, 종제어부로 나뉘며, 각각의 하드디스크는 독립된 종제어부에 의해 제어된다. 제안된 시스템이 주어진 요구사항을 만족하는지를 확인하기 위하여, 제안된 시스템을 DEVS 형식론을 이용하여 구현하고 시뮬레이션 하였다. DEVS 형식론은 이산사건 시스템을 계층적이고 모듈화된 형태로 기술한다. 시뮬레이션 과정에서 발생된 사건들을 분석하였다. 그 결과 제안된 시스템이 주어진 요구사항을 잘 만족함을 보았다. In this paper, we propose a real-time high-speed data storage system that inputs/outputs HDTV data. The proposed system i) can input/output large scale HDTV data fast; ii) can access data in a nonlinear, random manner as well as in a linear, sequential manner; iii) should guarantee a uniform I/O transfer rate for real-time recording/playing of HDTV data. In order to satisfy such constraints, hard disks are connected in parallel, and data are partitioned and stored in each of hard disks. Since the I/O performance of a hard disk is mainly determined by the seek operation of a hard disk arm, a method to effectively control the operation is designed. The proposed system is decomposed into three units, namely MCU(Master Control Unit), DDU(Data Distribution Unit) and SCU(Slave Control Unit). Each hard disk is controlled by an independent SCU. To verify that the proposed system satisfies the given requirements, the proposed system is implemented and simulated by using the DEVS formalism that specifies discrete event systems in a hierarchical, modular manner. The events that are generated during the simulation runs are analyzed. The result shows that the proposed system satisfies the given requirements well.

PCI-버스 기반 RAID 시스템의 버스 성능 분석

이찬수(Chan-Su Lee),성영락(Yeong-Rak Seong),오하령(Ha-Ryoung Oh) 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.30 No.7·8

단일 PCI 버스 세그먼트 내에는 제한된 수의 디스크만이 연결될 수 있으므로 대규모의 RAID 시스템은 여러 PCI 버스 세그먼트로 구성된다. 본 논문에서는 트랜잭션의 주체와 대상에 따라 RAID 시스템 내의 PCI 버스 트랜잭션들을 분류하고 각 트랜잭션의 데이타 전송 시간을 분석한다. 또한 분석 결과를 이용하여 두 개의 RAID 시스템 구성안에 대해서 읽기 및 쓰기 성능을 분석한다. DEVS 형식론을 이용한 RAID 시스템의 시뮬레이션을 통하여 여러 시스템 파라미터들의 변화에 따른 두 구성안의 성능을 평가하고 분석 결과와 비교한다. A large RAID system may consist of several PCI bus segments since a PCI bus segment can connect only a limited number of disks. In this paper, PCI bus transactions in a RAID system are classified in terms of the initiator and the target of the transaction. Also, the data transfer time of each transaction type is analyzed. By using the analysis results, read and write performance of two RAID system configurations are formulated. From simulation of the RAID system using the DEVS formalism, performance of the configurations are evaluated and compared with the analytical results while changing various system parameters.

쓰레드를 이용한 전계 강도 측정 및 분석 시스템 개발

김현동(Hyun Dong Kim),성영락(Yeong Rak Seong),오하령(Ha Ryoung Oh) 한국정보과학회 1999 한국정보과학회 학술발표논문집 Vol.26 No.1A

기지국을 세우기 전에 모의 기지국을 세워 그 지점에서의 타당성을 검토하는 것이 경제적이기 때문에, 차량에 GPS 수신기와 RX 수신기를 탑재하여 데이터를 측정하고 분석 할 수 있는 시스템이 개발되었다. 그러나, 기존의 시스템은 GPS 위치와 RX 데이터만을 측정하고 오프라인으로 분석하기 때문에 실시간 측정 분석이 불가능하였고 분석 후 이상 데이터 발견 시 다시 그 지역을 나가 확인을 해야만 했다. 그러나, 개발 시스템은 벡터 지도를 이용해 측정 시의 데이터 및 위치를 실시간으로 확인할 수 있다. 사용하고 있는 지도는 벡터 지도로, 비트맵 지도에 비해 이동, 확대, 축소 등이 용이하나 지도를 표출하는데 시간이 많이 걸린다. 따라서, 지도 표출 중에도 데이터를 측정하거나 다른 일을 할 수 있도록 하기 위해 우선 순위를 갖는 멀티 스레드를 이용하여 시스템을 개발한다.