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

송의석,성영락,오하령,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% 정도 통신비용을 감소시켰다.

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

송의석,오하령,성영락,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.

EPC Class-1 Generation-2 규격에 적합한 RFID 리더 시스템 설계

양정규,배성우,송의석,안시영,오하령,성영락,박준석,정명섭,곽호길,Yang, Jung-Kyu,Bae, Sung-Woo,Song, Eui-Seok,Ahn, Si-Young,Oh, Ha-Ryoung,Seong, Yeong-Rak,Park, Jun-Seok,Joung, Myoung-Sub,Kwak, Ho-Kil 한국전자파학회 2007 한국전자파학회논문지 Vol.18 No.8

RFID 기술이 다양한 분야에 적용됨에 따라 각 분야의 특성에 맞게 RFID 리더에 요구되는 기능들도 다양해지고 있다. 그러나 현재 구현된 8051 프로세서를 기반으로 한 시스템은 프로세서의 처리 용량의 한계 및 메모리 크기의 제한 등으로 인하여 다양한 요구 조건들을 충족시키기에 부족하다. 본 논문에서는 다양한 요구 조건들을 충족시키기 위해서 임베디드 시스템에서 많이 사용되고 있는 ARM920T 기반의 프로세서를 이용하여 EPC Class-1 Generation-2 규격을 만족하는 UHF 대역의 RFID 시스템을 설계하였다. As RFID systems are applied to various fields and applications such as supply chain management, asset management, location based applications etc. the requirements becomes diverse. For example, Much higher performance, TCP/IP protocol stack are required in some applications. However, low end processors based systems such as 8051 processor can not meet such requirements due to their low processing capacity and limited size of memory. In this paper a UHF band RFID system which meets the EPC Class-1 Generation-2 specification with ARM920T-based processor is implemented and tested.

시간 지연을 갖는 페이딩 채널의 전력 지연 분포 특성 분석 및 활용

박종현,김재원,송의석,성원진,Park, Jong-Hyun,Kim, Jae-Won,Song, Eui-Seok,Sung, Won-Jin 한국통신학회 2007 韓國通信學會論文誌 Vol.32 No.8c

Applying an appropriate received signal processing algorithm based on the channel characteristics is important to improve the receiver performance. Wireless channels in general exhibit various time-delay characteristics depending on their power delay profile. When the estimated channel power summation is used to determine the amount of time delay, a channel adaptive receiver structure can be implemented. In this paper, we derive a closed-form expression for the error probability of the channel classification when the estimated channel power summation is used to classify channel groups having different time delay characteristics, and present the performance gain utilizing multiple estimation results. 통신 수신기 구현에 있어 채널의 특성을 파악하여 그에 적합한 수신 신호 처리를 수행하는 것은 수신 성능 향상을 위해 매우 중요하다. 무선 채널은 전력 지연 분포(power delay profile)에 따라 다양한 시간 지연 특성을 가지며, 추정된 채널의 전력 합산을 통해 시간 지연 정도를 판별 시, 채널 적응적인 수신 구조 구현이 가능하다. 본 논문에서는 전력 지연 분포의 합산을 통해 시간 지연의 상대적인 크기에 따른 채널 군으로 분류하는 경우에 있어 채널 판별 오류 확률을 closed-form 수식으로 유도하고, 다수 번의 추정 결과를 누적하여 활용 시 얻어지는 성능 이득을 제시한다.

RFID 리더를 위한 중재 알고리즘의 모델링 및 시뮬레이션

류원상 ( Won Sang Ryu ),안시영 ( Si Young Ahn ),김용택 ( Yong Taek Kim ),배성우 ( Sung Woo Bae ),송의석 ( Eui Seok Song ),정명섭 ( Myoung Sub Jeong ),성영락 ( Yeong Rak Seong ),오하령 ( Ha Ryoung Oh ),박준석 ( Jun Seok Park ) 한국정보처리학회 2007 한국정보처리학회 학술대회논문집 Vol.14 No.2

RFID (Radio Frequency IDentification) 리더의 동작 영역은 리더의 감도와 전력이 도달할 수 있는 거리에 의해 제한된다. RFID Shower 는 근접한 리더로부터 전송되는 신호를 증폭하여 리더의 동작 영역을 확장한다. 그러나, RFID Shower의 동작 영역 안에 여러 리더들이 있을 경우 리더들간의 신호충돌이 발생한다. 이를 해결하기 위해 중재 알고리즘이 제안되었다. 본 논문에서는 RFID 리더들을 위한 중재 알고리즘을 DEVS 형식론에 기반하여 모델링하고 시뮬레이션 하여 성능을 측정, 비교하였다.

ISO/IEC 18000-6 Type C 규격에 적합한 리더 펌웨어 개발

양정규 ( Jung-kyu Yang ),오하령 ( Ha-ryoung Oh ),성영락 ( Yeong-rak Seong ),박준석 ( Jun-seok Park ),송의석 ( Eui-seok Song ),정명섭 ( Myoung-sub Joung ),곽호길 ( Ho-kil Kwak ),안시영 ( Si-young Ahn ) 한국정보처리학회 2007 한국정보처리학회 학술대회논문집 Vol.14 No.1

As RFID systems are applied to various fields and applications such as supply chain management, asset management, location based applications etc. the requirements becomes diverse. For example, Much higher performance, TCP/IP protocol stack are required in some applications. However, low end processors based systems such as 8051 processor can not meet such requirements due to their low processing capacity and limited size of memory. In this paper a UHF band RFID system which meets the ISO 18000-6 TYPE C specification with ARM920T-based processor is implemented and tested.

형상에 독립적인 부하 평형 기법

송의석,오하령 국민대학교 생산기술연구소 2004 공학기술논문집 Vol.27 No.-

This paper proposes a heuristic load balancing method for multiprocessor systems. The method 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 method can be employed in various interconnection topologies. In this paper, it is applied to general graph environments. For performance evaluation, simulation studies are performed. The performance of proposed method is compared to those of two well-known algorithms. The results show that the proposed method always balances the loads perfectly. Furthermore, it reduces the communication costs by 13-42% compared to existing algorithms.