동질의 트리 구조에서의 효율적인 태스크 할당 알고리즘

서경룡(Kyung-Ryong Seo),이철훈(Cheol-Hoon Lee),박규호(Kyu-Ho Park) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.2

We study the assignment problem of assigning the interacting task modules of a program to the processors of a multiple computer system such that the sum of execution and communication costs is minimized. If all processors in the system are functionally identical, i.e., a homogeneous network, total execution cost caused by an assignment is constant. Therfore, the task assignment problem in homogeneous network problem is the problem of finding an assignment with the minimum communication casts. The task assignment problem in homogeneous networks is intrinsically hard. There is no known polynomial algorithm to find an optimal assignment in the general homogeneous network with N processors for N≥3. Recently, some optimal algorithm has been suggested for the problem assigning tasks into a restricted homogeneous system like linear array of tree. We introduce a modeling technique that transforms the assignment problem in a homogeneous networks into a network flow problem. The main idea of the technique is to design a network flow graph for the assignment problem in such a way that every feasible assignment is represented by a set of cuts each of which is on an appropriately defined network flow graph, and that the total weight of the cuts is equal to the total communication cost of the assignment. In order to solve this problem efficiently, we suggests a constructing method of a cut tree of the system graph. The knowledge of cut tree is shown to be useful not only in developing an efficient algorithm of the task assignment problem but also in showing optimality of the task assignment algorithm. 본 논문에서는 분산 시스템 상에서 수행되는 일들의 수행비용과 통신비용을 최소화하는 일의 할당을 구하는 문제를 다룬다. 일반적인 경우 일의 최적할당을 구하는 문제는 다항식(polynomial) 복잡도의 해가 존재하지 않는 어려운 문제로 분류된다. 본 논문에서는 트리 구조를 가지며, 프로세스들의 계산능력이 동일한 분산 시스템 상에 최적의 할당을 구하는 효율적인 알고리즘을 제시한다. 이 방식은 일의 할당문제를 네트웍 플로우의 문제로 변환하여 할당에 대응하는 최소 비용의 분할을 일련의 순서대로 구한다. 이때 알고리즘의 복잡도는 네트웍 플로우 알고리즘의 적용횟수에 좌우되는 데 이를 줄일 수 있도록 분산 시스템의 구성형식에 따른 분할 트리(cut tree)를 제안한다. 이때 네트웍 플로우 알고리즘의 적용횟수는 분할트리의 높이와 동일하며, 이를 이용하여 빠른 시간에 최적의 할당을 구한다.

이종의 다중컴퓨터에서 태스크 할당을 위한 효율적인 알고리즘

서경룡(Seo Kyung ryong),여정모(Yeo Jeong mo) 한국정보처리학회 1998 정보처리학회논문지 Vol.5 No.5

In this paper, we are considering a heterogeneous processor system in which each processor may have different performance and reliability characteristics. In other to fully utilize this diversity of processing power it is advantageous to assign the program modules of a distributed program to the processors in such a way that the execution time of the entire program is minimized. This assignment of tasks to processors to maximize performance is commonly called load balancing, since the overloaded processors can perform their own processing with the performance degradation. For the task assignment problem, we propose a new objective function which formulates this imbalancing cost. Thus the task assignment problem is to be carried out so that each module is assigned to a processor whose capabilities are most appropriate for the module, and the total cost is minimized that sum of inter-processor communication cost and execution cost and imbalance cost of the assignment. To find optimal assignment is known to be NP-hard, and thus we proposed an efficient heuristic algorithm with time complexity O(n^2m) in case of m task modules and n processors.

EMFG의 개선된 동작해석 알고리즘

김희정,여정모,서경룡,Kim, Hee-Jung,Yeo, Jeong-Mo,Seo, Kyung-Ryong 한국정보처리학회 2002 정보처리학회논문지 A Vol.9 No.3

EMFG(Extended Mark Flow Graph)는 이산시스템을 표현하는데 유용한 그래프 도구로 알려져 있다. 본 연구에서는 EMFG에서 각 트랜지션이 점화하였을 때의 입출력 박스의 마크 변화량을 입출력 행렬로 표현하였고, 이를 사용하여 EMFG의 접속행렬을 구하였다. 점화가능벡터를 구하기 위하여 각 트랜지션의 점화조건을 점화조건행렬로 표현하였으며, 각 트랜지션의 점화완료 상태를 판단하기 위하여 점화완료벡터를 도입하였다. 이들을 사용하여 EMFG의 모든 동작과정이 수학적으로 해석될 수 있도록 EMFG의 동작해석 알고리즘을 개선하였다. 제안된 알고리즘을 정회전과 역회전을 반복하는 시스템에 적용하여 알고리즘이 올바르게 동작하는 것을 확인하였다. 제안된 알고리즘은 다양한 이산 시스템을 분석하는데 유용하다. The EMFG (Extended Mark Flow Graph) is known as a graph model for representing the discrete event systems. In this paper, we introduce input/output matrixes representing the marking variance of input/output boxes when each transition fires in an EMFG, and compute an incidence matrix. We represent firing conditions of transitions to a firing condition matrix for computing a firable vector, and introduce the firing completion vector to decide completion of each transition’s firing. By using them, we improve an analysis algorithm of the EMFG’s operation to be represented all the process of EMFG’s operation mathematically. We apply the proposed algorithm to the system repeating the forward and reverse revolution, and then confirm that it is valid. The proposed algorithm is useful to analysis the variant discrete event systems.

계수기반의 ACK FEC를 통한 무선링크에서의 전통적인 FEC의 성능 개선 방안

이병길(Bung-gil Lee),서경룡(Kyung-ryong Seo) 한국정보과학회 영남지부 2003 한국정보과학회 영남지부 학술발표논문집 Vol.11 No.1

분산 비디오 스트리밍을 위한 FEC(Forward Error Correction)제어기법

이병길 ( Bung-kil Lee ),이석주 ( Suk-ju Lee ),서경룡 ( Kyung-ryong Seo ) 한국정보처리학회 2004 한국정보처리학회 학술대회논문집 Vol.11 No.1

인터넷은 best-effort network를 근간으로 하기 때문에 대용량의 비디오 스트리밍을 제공하기에는 대역폭의 제한과 패킷 손실과 같은 다양한 문제가 발생한다. 이러한 문제를 해결하기 위해 다양한 방법들이 제안 되었는데, 본 논문에서는 다수의 송신측이 하나의 수신측으로 FEC를 이용하여 비디오 스트리밍을 제공할 때, 수신측의 ACK에 부가정보를 추가하여 FEC의 성능 개선과 분산 스트리밍 제어가 가능한 기법을 제안한다.

고속 스트림 암호 MS64

김길호(Gil-Ho Kim),김윤도(Yoon-Do Kim),김종남(Jong-Nam Kim),서경룡(Kyung-Ryong Seo),조경연(Gyeong-Yeon Cho) 한국멀티미디어학회 2010 한국멀티미디어학회 학술발표논문집 Vol.2010 No.2

최근 스마트폰 사용의 급속한 증가 등으로 모바일 단말이 PC 기능을 대체해 가고 있다. 모바일 단말들은 무선통신 사용으로 보안에 취약하여 정보 보호를 위한 암호화가 요구된다. 그러나 자원이 제한된 모바일 환경에서 암호 알고리즘들은 안전성을 만족하지 못하거나 수행 속도가 느리다. 이에 따라 모바일 환경에서도 시스템에 제약 없이 안전하면서 빠른 암호 개발이 절실히 요구된다. 본 논문에서는 소프트웨어로 구현하기 쉽고 안전하면서 빠른 모바일용 고속 스트림 암호 MS64를 제안한다. 제안한 알고리즘은 산술 쉬프트 레지스트(ASR)을 이용한 213비트 LFSR(Linear Feedback Shifter Register)로 디자인 하였으며, 비선형 변환에서는 워드별 간단한 논리연산으로 64비트 스트림 암호를 출력한다. MS64는 SSC2, Salsa20 보다 수행 속도에서 빠른 결과를 보여주고 있으며, 128비트 키를 지원하고 현대 암호 알고리즘이 필요로 하는 안전성을 만족하고 있다. 제안한 MS64는 모바일 단말의 무선 인터넷이나 스트리밍 컨텐츠 암호화, DRM(Digital Right Management) 등과 같은 고속 암호처리가 필요한 분야에 사용 가능하다.

모바일 단말에 적합한 고속 스트림 암호 MS64

김윤도(Yoon-Do Kim),김길호(Gil-Ho Kim),조경연(Gyeong-Yeon Cho),서경룡(Kyung_ryong Seo) 한국멀티미디어학회 2011 멀티미디어학회논문지 Vol.14 No.6

그래프의 다중분할을 위한 효율적인 알고리듬

서경룡 釜山工業大學校 1993 論文集 Vol.35 No.-

본 논문에서는 VLSI의 설계과정에서 광범위하게 활용되는 그래프의 다중분할 방식을 제안하였다. 이는 최근 발표된 ratio cut 분할방식??이 주어진 그래프를 2분한 것에 비하여 일반적인 k 개의 부분으로 분할할수 있도록 확장한 것이다. 2분할의 문제를 k 분할의 문제로 확장하기위하여 그래프의 분할에 필요한 비용함수를 에지비용과 크기비용의 함수로 새롭게 정의하였으며, 분할에 따른 에지의 비용과 크기비용간의 절충은 균형상수를 도입하여 해결하였다. 제안된 방식은 그래프를 특정비율로 분할하는데도 쉽게 적용된다. 최적의 분할을 구하는 문제는 NP-hard의 범주에 속하므로 빠른시간에 좋은 분할을 구할 수 있는 휴리스틱 알고리듬을 제안하였다. 제안된 알고리듬의 성능을 측정하기 위하여 많은 데아타에 대하여 시믈레이션이 병행되었다. In this paper, we propose the new multiple way partition problem which devides the given graphs into the highly connencted k component with predefined cost value. This problem is called graph partition problem anddose have numerous applications such as placement of components du-ring VLSI layout. This is an extension of the Cheng's ratio cut??which devides the given graph into two subset with minimum ratio value. For the algorithm, not only the edge cost and the size cost of the partition but also trade-off factor which compromize between edge cost and size cost are newly proposed. Finding the optimal k-way partition is know as NP-hard. Thus, we propose an efficient heuristic algorithm, and execute a large numbers of simulations on a variety of graphs.

CSMA/CD의 성능개선을 위한 채널예약방법에 관한 연구

서경룡 釜慶大學校 2001 釜慶大學校 論文集 Vol.6 No.-

This paper proposes an reservation method to enhance the performance of the carrier sence multiple access with collision detection(CSMA/CD). The CSMA/CD protocol is a collision-based technique and is not works well on the heavy load for the collisions. The proposed method give reservation facility to the CSMA/CD in order to reduce the collisions. The performance of the protocol is studied by simulations under several realistic traffic conditions and compared to the traditional CSMA/CD.

하이퍼 큐브 그래프의 위상적 특성

서경룡 釜山工業大學校 1992 論文集 Vol.34 No.-

n-차원 하이퍼 큐브는 이진 n-큐브 형태를 가지는 병렬처리가 가능한 다중 프로세스 시스템이다. 하이퍼 큐브의 구조를 가지는 병렬 컴퓨터는 그 연결 방식이 다른 방식에 비교하여 매우 우수함이 이론적으로 밝혀져 있다. 본 논문에서는 하이브 큐브의 기본 성질을 규명하고 하이퍼 큐브를 인식하는데 필요한 이론적 배경을 제안한다. 제안된 방식은 기존의 방식에 비하여 이해하기 매우 쉬우며 하이퍼 큐브를 인식하는 속도 또한 빠르다. The n-dimansional hypercube is a highly concurrent loosely coupled multiprocessor based on the binary n-cube topology. Machines based on the hypercube topology have been adbocated as ideal parallel architectures for their powerful interconnection features. In this paper, we study the topological properties of the hypercubes and propose a theorem that will describe an n-cube. Using the theorem, an n-cube is recognized in a quite effcient way.