손상된 하이퍼큐브에서의 All - to - all Broadcasting

원영선(Young Sun Weon),박승진(Seung Jin Park) 한국정보과학회 1994 한국정보과학회 학술발표논문집 Vol.21 No.2B

효율적인 결함 허용 통신 알고리즘은 시스템의 성능을 향상시키는 데 필수적이다. 본 논문은 [n/2] 결함 노드를 갖는 n차원 하이퍼큐브에서의 새로운 all-to-allbroadcasting 알고리즘을 제안한다. 제안된 알고리즘에 의한 총 단계는 최적에 매우 근접하다.

하이퍼큐브 시스템에서 데이타 비대칭성을 고려한 향상된 병렬 결합 알고리즘

원영선(Young Sun Weon),홍만표(Man Pyo Hong) 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.30 No.3·4

본 논문에서는 하이퍼큐브 시스템에서 결합 연산을 효율적으로 처리할 수 있는 향상된 병렬 결합 알고리즘을 제안한다. 새로운 알고리즘은 릴레이션 을 처리함에 있어 하이퍼큐브 구조에 적합한 방송 알고리즘을 사용함으로써 하이퍼큐브 구조에 최적인 병렬 결합 알고리즘을 보이게 된다. 또한 병렬화 성능의 최대 주안점인 부하균등 문제와 데이타 불균형으로 인한 과부하 문제를 완전히 해결하고 결집 효과의 특성을 수용함으로써 전체 성능이 향상된다. 새로운 알고리즘은 해쉬를 기반으로 하는 알고리즘에서 구현하기 어려운 non-equijoin 연산을 쉽게 구현할 수 있다는 장점을 가지며, 비용 모형을 통해 분석한 결과 기존의 병렬 결합 알고리즘들에 비해 보다 나은 성능을 나타냄을 확인한다. In this paper, we propose advanced parallel join algorithm to efficiently process join operation on hypercube systems. This algorithm uses a broadcasting method in processing relationwhich is compatible with hypercube structure. Hence, we can present optimized parallel join algorithm for that hypercube structure. The proposed algorithm has a complete solution of two essential problems - load balancing problem and data skew problem - in parallelization of join operation. In order to solve these problems, we made good use of the characteristics of clustering effect in the algorithm. As a result of this, performance is improved on the whole system than existing algorithms. Moreover, new algorithm has an advantage that can implement non-equijoin operation easily which is difficult to be implemented in hash based algorithm. Finally, according to the cost model analysis, this algorithm showed better performance than existing parallel join algorithms.

하이퍼큐브 구조 시스템에서 향상된 병렬 결합 알고리즘의 성능 분석

원영선(Young Sun Weon),조석봉(Seok Bong Cho),이규옥(Kyu Ok Lee),좌용권(Young Kwon Cha),홍만표(Man Pya Hong) 한국정보과학회 1999 정보과학회논문지 : 시스템 및 이론 Vol.26 No.6

관계형 데이타베이스 시스템에서 결합 연산자는 데이타베이스 질의를 구성하는 연산자들 중 가장 많은 처리시간을 요구한다. 따라서 이러한 결합 연산자를 효율적으로 처리하기 위해 많은 병렬 알고리즘들이 소개되었다. 그 중 하이브리드 해쉬 결합 알고리즘은 가장 우수한 것으로 알려져 왔다. 그러나 이 알고리즘은 여러 노드로 데이타를 분할하는 과정에서 데이타의 편중 문제가 발생하며, 이는 전체 시스템의 성능을 크게 저하시키게 된다. 본 논문에서는 이러한 데이타 편중 문제를 해결한 변형된 하이퍼 퀵 정렬을 이용한 병렬 결합 알고리즘을 non-equijoin을 위한 알고리즘으로 확장하였다. 또한 T805로 연결된 하이퍼큐브 구조 시스템에서 시뮬레이션하여 얻은 결과를 수치 계산적 비용모델의 결과와 비교를 통해 변형된 하이퍼 퀵 정렬을 이용한 병렬 결합 알고리즘의 성능을 분석하고, 비용모델의 타당성을 입증하였다. In the relational database systems, the join operation is one of the most time-consuming query operations. Many parallel join algorithms have been developed to reduce the execution time, and the parallel Hybrid-hash join algorithm is one of the most efficient ones. However, the parallel Hybrid-hash join operation may result in a nonuniform distribution of data tuples on the processing nodes, which affects the performance of the system. In this paper, we develop a join algorithm for non-equijoin of parallel distributive join algorithm which solves handle this nonuniform workload problem by using a modified hyper quicksort operation. In addition, we analyze the performance by simulating the proposed parallel join algorithm using the modified hyperquick sort on T805 machines working in the hypercube interconnection mode and then verify the validity of cost model.

페이지 실행시간 동기화를 이용한 다중 파이프라인 해쉬 결합

이규옥(Kyu-Ock Lee),원영선(Young-Sun Weon),홍만표(Man-Pyo Hong) 한국정보과학회 2000 정보과학회논문지 : 시스템 및 이론 Vol.27 No.7

관계형 데이타베이스 시스템에서 결합 연산자는 데이타베이스 질의를 구성하는 연산자들 중 가장 많은 처리시간을 요구한다. 따라서 이러한 결합 연산자를 효율적으로 처리하기 위해 많은 병렬 알고리즘들이 소개되었다. 그 중 다중 해쉬 결합 질의의 처리를 위해 할당 트리를 이용한 방법이 가장 우수한것으로 알려져 왔다. 그러나 이 방법은 할당 트리의 각 노드에서 필연적인 지연이 발생되는 데 이는 튜플-시험 단계에서 외부 릴레이션을 디스크로부터 페이지 단위로 읽는 비용과 이미 읽는 페이지에 대한 해쉬결합 비용간의 차이에 의해 발생하게 된다. 본 논문에서는 이 비용 차이로 인해 발생되는 전체 시스템의 성능 저하를 방지하기 위해 페이지 실행시간 동기화 기법을 제안하였고 이 기법을 통해 각 노드에서의 처리시간을 줄이고 나아가 전체 시스템의 성능을 향상시켰다. 또한 분석적 비용 모형을 세우고 기존 방식과의 다양한 성능 분석을 통해 비용 모형의 타당성을 입증하였다. In the relational database systems, the join operation is one of the most time-consuming query operations. Many parallel join algorithms have been developed to reduce the execution time. Multiple hash join algorithm using allocation tree is one of most efficient ones. However, it may have some delay on the processing each node of allocation tree, which is occurred in tuple-probing phase by the difference between one page reading time of outer relation and the processing time of already read one. In this paper, to solve the performance degrading problem by the delay, we develop a join algorithm using the concept of 'synchronization of page execution time' for multiple hash joins. We reduce the processing time of each nodes in the allocation tree and improve the total system performance. In addition, we analyze the performance by building the analytical cost model and verify the validity of it by various performance comparison with previous method.

한정된 프로세서 환경에서 페이지 실행시간 동기화를 이용한 효율적인 다중 결합

이규옥(Kyu-Ock Lee),원영선(Young-Sun Weon),홍만표(Man-Pyo Hong) 한국정보과학회 2001 정보과학회논문지 : 데이타베이스 Vol.28 No.4

관계형 데이타베이스 시스템에서 결합 연산자는 데이타베이스 질의를 구성하는 연산자들 중 가장 많은 처리시간을 요구한다. 따라서 이러한 결합 연산자를 효율적으로 처리하기 위해 많은 병렬 알고리즘들이 소개되었다. 그 중 다중 해쉬 결합 질의의 처리를 위해 할당 트리를 이용한 방법이 가장 우수한 것으로 알려져 왔다. 그러나 이 방법은 할당 트리의 각 노드에서 필연적인 지연이 발생되는 데 이는 튜플-시험 단계에서 외부 릴레이션을 디스크로부터 페이지 단위로 읽는 비용과 이미 읽는 페이지에 대한 해쉬 결합 비용간의 실행시간 차이에 의해 발생하게 된다. 이는 페이지 실행시간 동기화 기법을 이용하여 할당 트리 한 노드에서의 실행시간을 줄일 수 있었다. 본 논문에서는 한 노드에서의 성능 개선 효과를 할당 트리 전체로 확장하여 전체 다중 해쉬 결합의 성능 분석을 수행하였으며 한정된 프로세서 환경 하에서 입력릴레이션 수와 할당된 프로세서 수와의 관계에 따른 효율적인 다중 해쉬 결합 알고리즘을 제안하였다. 그리고 분석적 비용 모형을 세워 기존 방식과의 다양한 성능 분석을 통해 비용 모형의 타당성을 입증하였다. In the relational database systems, the join operation is one of the most time-consuming query operations. Many parallel join algorithms have been developed to reduce the execution time. Multiple hash join algorithm using allocation tree is one of the most efficient ones. However, it may have some delay on the processing each node of allocation tree, which is occurred in tuple-probing phase by the difference between one page reading time of outer relation and the processing time of already read one. This delay problem was solved by using the concept of 'synchronization of page execution time' which we had proposed. In this paper, the effects of the performance improvements in each node of the allocation tree are extended to the whole allocation tree and the performance evaluation about that is processed. In addition, we propose an efficient algorithm for multiple hash joins in limited number of processor environments according to the relationship between the number of input relations in the allocation tree and the number of processors allocated to the tree. Finally, we analyze the performance by building the analytical cost model and verify the validity of it by various performance comparison with previous method.

하이퍼 퀵 정렬을 이용한 병렬 결합 알고리즘

조석봉(Seok Bong Cho),원영선(Young Sun Weon),홍만표(Man Pyo Hong) 한국정보과학회 1997 정보과학회논문지(B) Vol.24 No.6

대용량 데이타베이스 처리 시스템에서는 효율적인 자료 처리를 위하여 빠른 응답시간을 요구하며, 이를 위해서는 데이타베이스 시스템의 병렬화가 필수적이다. 특히 결합 연산은 비교적 긴 처리 시간을 요구하며, 각 처리기에 릴레이션을 균등하게 분배하는 방법은 시스템의 성능에 커다란 영향을 끼친다. 본 논문에서는 하이퍼큐브 구조에 적합한 하이퍼 퀵 정렬을 이용하여 정렬 병합 알고리즘의 단점인 많은 오버헤드를 해결함과 동시에 각 처리기에서의 부하 균등을 이룸으로써 전체적인 통신 시간을 줄일 수 있는 효율적인 병렬 결합 알고리즘을 제안한다. 또한 제안한 알고리즘의 분석 모델을 통하여 기존의 병렬 결합 알고리즘에 비해 보다 나은 성능을 나타냄을 보인다. Fast response time is required to process data effectively in very large database processing systems. In doing so, parallelization of the system is a prerequisite. In particular, it takes relatively long time to execute the join operation. The method to distribute the relations equally to each processor influences the performance of the system considerably. The current paper proposes an effective parallel join algorithm which contributes to reduce overall communication time through balancing the loads in each processor as well as solving a demerit of sort merge join algorithm, using hyper quick sort algorithm proper to the hyper cube system. This paper also prove that the algorithm outstrips the present parallel join algorithms in its performance analysis.