가변 임계값을 갖는 JPEG 영상의 양자화 방법

오하령(Ha Ryoung Oh),윤석현(Seok Hyun Yoon),성영락(Yeong Rak Seong) 한국정보처리학회 1999 정보처리학회논문지 Vol.6 No.11

In this paper, VTQM(Variable Threshold Quantization Method) is proposed, which enhances PSNR by composing the advantages of round off and truncation quantization methods. From vast experiments. PSNR's of JPEG image with the method are compared with that of standard JPEG methods. At the boundary which affects the compression ratio. VTQM quantizes with a new threshold to reduce the length of compressed data; otherwise, VTQM employs the round off quantization method to preserve the original image information. As a result, VTQM reduces bit rate while preserving the image quality. The experimental results show that VTQM enhances PSNR by 0.2~0.3%u33C8. 0.4~0.5%u33C8 with the same bit rate those of the traditional truncation and round-off quantization methods, respectively.

서브넷의 동적인 특성에 기초를 둔 페트리넷 축약 방법

오하령(Oh Ha Ryoung),김준형(Kim Jun Hyung) 한국정보과학회 1995 정보과학회논문지 Vol.22 No.4

페트리망은 병열성, 동기화 및 충돌 등을 표현할 수 있는 수학적이고 시각적인 모델로서 여러 분야에서 널리 사용되고 있다. 페트리망의 여러 가지 좋은 특성에도 불구하고 복잡한 시스템 분석의 근본적인 문제점은 도달 가능한 모든 상태를 검토하기에는 너무나 많은 시간 혹은 기억공간을 필요로 한다는 것이며 페트리망의 분석은 일반적으로 지수함수 이상의 복잡도를 갖는 것으로 알려져 있다. 본 논문에는 원시 페트리망의 중요한 정보를 유지하면서 상태공간을 줄일 수 있도록 변환 가능한 서브?을 계층적으로 변환하는 페트리망의 축약 방법이 제시되었다. 제안된 서브?은 Suzuki, Murara의 k-well-behaved module의 개념을 확장한 것이며 서브? 외부와의 작용을 허용하도록 transition의 외향 에지중 일부를 삭제 가능토록 하였다. Petri net has been used widely in various domains, which is a mathematical and graphical model providing a formalism for concurrency, synchronization and conflict. Despite many excellent features of Petri net, the inherent problem with Petri net analysis is that it may be impossible to generate and check all reachable states of Petri net in reasonable time or storage for complex systems. The complexity is known to be at least exponential and may not even be decidable. In this paper a method of hierarchical Petri net abstraction based on the convertible subnet is proposed, which can reduce the state space of complex Petri net while preserving sufficient information of the original net. The proposed subnet is an extension of Suzuki and Murata′s k-well-behaved module and some outgoing edges of transitions can be removed so that the module may have side effects on the rest of the system.

다중 프로세서 환경에서 연결구조에 무관한 휴리스틱 부하평형 알고리즘

송의석,성영락,오하령,Song Eui-Seok,Sung Yeong-Rak,Oh Ha-Ryoung 대한전자공학회 2005 電子工學會論文誌-CI (Computer and Information) Vol.42 No.1

This paper proposes an efficient 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 all neighbor processors. However, real load transfer is collectively done after all load traffic is calculated. This prevents useless traffic and thus reduces the overall load traffic. The proposed algorithm can be employed in various interconnection topologies with slight modifications. In this paper, it is applied to hypercube, mesh, k-ary n-cube and general graph environments. For performance evaluation, simulation studies are performed. The proposed algorithm and the well-known existing algorithms are implemented and compared. The results show that the proposed algorithm always balances the loads perfectly. furthermore, in comparison with the existing algorithms, it reduces the communication costs by 77%, 74% and 73% in the hypercube, the mesh, and k-ary n-cube, respectively. 본 논문에서는 다중 프로세서 시스템을 위한 효율적인 휴리스틱 부하 평형 알고리즘을 제안한다. 제안 알고리즘은 부하이동을 여러 링크로 분산시켜, 사용하지 않는 링크의 수를 최소화하고 그에 따라 통신비용이 감소한다. 각각의 프로세서는 모든 이웃한 프로세서에게 단위부하를 보내거나 받는 과정을 반복적으로 시도한다. 그리나 실제의 부하 이동은 모든 계산이 이루어진 후 수행된다. 이것은 불필요한 부하 이동을 막아 전체적으로 부하이동의 수가 감소한다. 제안된 알고리즘은 약간의 수정만으로 다양한 연결 구조를 갖는 다중 프로세서 시스템에 적용한 수 있다. 본 논문에서는 하이퍼큐브 구조, 메쉬 구조, k-ary n-cube 구조와 일반 그래프 구조에 제안 알고리즘을 적용해 보았다. 알고리즘의 성능평가를 위하여 모의실험을 하였다. 제안된 알고리즘과 잘 알려진 알고리즘을 구현하여 비교하였다. 그 결과 안된 알고리즘은 모든 경우에서 완전한 부하평형에 도달하였다. 또한 기존의 알고리즘과 비교하여 하이퍼큐브 구조에서는 약 77%, 메쉬 구조에서는 약 74%, 또한 k-ary 2,3-cube 구조에서는 약 73% 정도 통신비용을 감소시켰다.

고속 이동체를 위한 확장성 있는 실시간 위치 측정 시스템

안시영,박준석,오하령,성영락,Ahn, Si-Young,Park, Jun-Seok,Oh, Ha-Ryoung,Seong, Yeong-Rak 한국정보처리학회 2012 정보처리학회논문지 A Vol.19 No.2

본 논문에서는 다수의 고속 이동체들의 위치를 측정할 수 있는 확장성 있는 실시간 위치 측정 시스템을 제안한다. 제안된 시스템에서는 위치 서비스가 필요한 영역을 확장 시 기본 단위인 매크로셀이라고 불리는 정사각형의 격자들로 나누고, 한 매크로셀은 $N{\times}N$ 개의 마이크로셀로 나눈다. 마이크로셀의 각 꼭짓점에는 위치 기준 노드가 중앙에는 중재 노드가 설치된다. 위치를 측정하고자 하는 이동체는 우선 중재 노드와의 통신을 통하여 위치 측정을 위한 허가를 받아야 한다. 그러므로 한 마이크로셀내에서는 오직 허가된 하나의 이동 노드만이 위치 기준 노드들과 연속적으로 통신하면서 자신의 위치를 계산할 수 있다. 제안된 시스템의 성능을 측정하기 위하여, 제안된 시스템을 모델링하고 시뮬레이션 하였다. 시뮬레이션 결과 제안된 시스템은 위치 측정을 위한 통신 시간이 짧고 고속 이동체의 위치를 계산할 경우 오차가 적은 것으로 나타났다. In this paper, a highly scalable real-time locating system which can measure location of fast moving targets is proposed. Within the system, the location service area is partitioned into grids with squares which is referred to as a macro-cell. Also, a macro-cell is further partitioned into $N{\times}N$ micro-cells. In a micro-cell, location reference nodes are placed on every vertex and an arbitration node is placed on the center. When a mobile node tries to measure its location, it should first communicate with the arbitration nodes for granting location measurement operation. Therefore, within a micro-cell, only one granted mobile node can calculate its location by a series of communication with location reference nodes. To evaluate performance of the proposed system, the system is modeled and simulated. The simulation result shows that the proposed system requires small communication time for location measurement operation and produces small location calculation error for fast moving targets.

시간지원 데이타베이스에서의 분할에 기초한 시간조인 알고리즘

이재문(Lee Jae Moon),오하령(Oh Ha Ryoung),김준형(Kim Jun Hyoung) 한국정보과학회 1997 정보과학회논문지(B) Vol.24 No.6

시간지원 데이타베이스에서 효율적인 시간조인에 대한 새로운 알고리즘을 제안하였다. 작은 릴레이션은 정렬하고 큰 릴레이션은 분할함으로서 기존의 정렬병합 알고리즘에서의 큰 릴레이션의 정렬 비용을 줄이자는 것이 주개념이다. 제안한 알고리즘의 유용성을 보이기 위하여 보조 기억 장치의 액세스 수에 관하여 비용을 분석하였으며 일반적으로 널리 알려진 정렬병합 방법과 성능 비교를 하였다. 증명을 통하여 제안된 방법이 우수한 조건들을 보였으며, 이러한 조건하에서 제안된 방법이 기존의 정렬병합 방법보다 10~30%의 성능 향상이 있음을 모의 실험을 통하여 보였다. A new algorithm is proposed in this paper which efficiently performs join in the temporal databases. The main idea is to sort the smaller relation and to partition the larger relation, and the proposed algorithm reduces the cost of sorting the larger relation. To show the usefulness of the algorithm, the cost is analyzed with respect to the number of accesses to secondary storage and compared with that of Sort-Merge algorithm. Through the comparisons, we present and verify the conditions under which the proposed algorithm always outperforms the Sort-Merge algorithm. The comparisons show that the proposed algorithm achieves 10-30% gain under those conditions.

범용 내장형 컴퓨터 시스템의 구현

장위식,조병헌,성영락,오하령,Jang, Wee-Sik,Cho, Byeong-Heon,Sung, Yeong-Rak,Oh, Ha-Ryoung 한국정보처리학회 2002 정보처리학회논문지 A Vol.9 No.4

본 논문에서는 범용 내장형 컴퓨터 시스템을 설계하고 구현한다. 범용 내장형 컴퓨터 시스템의 가장 중요한 점은 확장성과 유연성이다. 개발된 시스템은 세 개의 모듈로 나뉘어 구성되며, 소프트웨어는 하드웨어에 독립적인 응용 프로그램 인터페이스를 제공한다. 또한 공개 실시간 운영체제인 uC/OS-II의 기능을 확장하여 개발된 범용 내장형 컴퓨터 시스템에 이식한다. 확장된 uC/OS-II는 여러 프로세스들이 같은 우선순위를 가지는 것을 지원하고, 같은 우선순위의 프로세스들에 대해서는 라운드-로빈 방식으로 스케줄링 된다. In this paper, a general purpose embedded computer system is designed and implemented. The most crucial points of the system are extensibility and flexibility. The hardware of the developed system is composed of three modules and the software provides hardware independent application program interfaces. Moreover, uC/OS-II, a well-known open realtime kernel. is extended and ported onto the system. The extended uC/OS-II supports that multiple processes can have the same priority and such processes are scheduled in a round-robin manner.

분산 처리 : 일관성에 기초한 적응 부하 평형

김준형(Kim Jun Hyung),오하령(Oh Ha Ryoung),이재문(Lee Jae Moon) 한국정보처리학회 1995 정보처리학회논문지 Vol.2 No.3

부하 평형은 과부하 사이트의 부하중 일부를 다른 사이트로 옮김으로써 분산 처리 시스템의 성능 개선을 꾀한다. 본 논문에서는 source-initate와 server-initiate 방식을 모두 지원하며 극단적인 예로서 m/m/1 대기행렬(부하 비평형)과 m/m/n 대기행령(완전한 부하 평형)도 모델화 할 수 있는 부하 평형 방식을 제안하였다. 이 방식은 상태 변수를 각 사이트에 복제하고 각 복사본의 일치성을 완화한다. 그리고 오래된 상태 정보에서 현재의 상태 정보를 유추할 수 있는 완화된 복사본의 일치성 제약을 제안하였다. 또한 스케줄러가 통신을 하지 않고도 부하 평형을 보장할 수 있는 충분조건을 유도하였다. 이 모델을 이용하면 부하 평형의 문제가 상태의 일관성을 유지하는 문제로 바뀌게 되며 기존의 비딩 알고리즘보다 통신량이 적어지게 된다. 이벤트 트레이싱 방법으로 모의 실험하였으며 2개의 극단적인 경우 및 비딩알고리즘과 비교하였다. 그 결과 평균 응답 시간과 통신량에 있어서 비딩알고리즘보다 각각 0~35%. 40~100%의 성능향상을 보였다. 마지막으로 각 시스템 파라미터의 영향을 분석하였다. Load balancing attempts to improve the performance of a distributed computing system by transferring some of the workload of a congested site to others. A load balancing scheme that supports both the source-initiated and the server-initiated load balancing is proposed in this paper. It can model both the m/m/1 queue(no load balancing) and the m/m/n queue(perfect load balancing) as the extreme cases. State variables are replicated into every site, and copy consistency constraints are relaxed more weakly. We propose weak copy consistency constraints which correlate the outdated state information to that of the current state. We also derive sufficient conditions under which each scheduler can guarantee the load balancing without communication. Using this model, the problem of load balancing is converted to that of maintaining the rithm. The scheme is simulated by event tracing, compared to the two extreme cases and the bidding algorithm. The results show that the mean response time and the number of messages are reduced by 0-35% and 40-100% respectively, compared with the bidding algorithm. Finally the effects of some system parameters are described.

DEVS 형식론에 기반한 멀티쓰레드 소프트웨어 개발 과정에서의 쓰레드 수 조절

임정현(Jung Hyun Im),오하령(Ha Ryoung Oh),성영락(Yeong Rak Seong) 한국통신학회 2015 한국통신학회 학술대회논문집 Vol.2015 No.1

ARM 프로세서에 기반한 내장형 시스템의 개발

강찬중(Chan Jung Kang),오하령(Ha Ryoung Oh),성영락(Yeong Rak Seong) 대한전자공학회 2002 대한전자공학회 학술대회 Vol.2002 No.11

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.