The disk allocation problem examined in this thesis is finding a method to distribute Binary Cartesian Product Files on multiple disks to maximize parallel disk I/O accesses for partial match retrieval. This problem is known to be NP-hard, and heuristic approaches have been applied to obtain suboptimal solutions. Recently, efficient heuristic methods such as Binary Disk Modulo(BDM) and Error Correcting Code(ECC) methods have been proposed along with the restriction that the number of disks in which files are stored should be a power of 2. However, restriction on the number of applied disks causes the problems of economics and spaces, when more disks should be added to extend the size of the file system. Moreover, all of the proposed methods do not consider the data access patterns. In real databases, reflecting a known access pattern on the disk allocation method is very important for improving query access time. The design of a new disk allocation scheme which has no restriction on the number of disks and reflects the data access patterns, is the main theme of this thesis.
As a first step of designing a new disk allocation method, a bucketvector and a disk mapping function have been defined. A bucketvector is a permutation of buckets which will be allocated to the disks. The disk mapping function maps the buckets to the disks only by using the position indexes of buckets in the bucketvector and no restriction is assumed on the number of disks. Thus, if the bucket permutations are different, the different results of bucket mappings are obtained. Then, the disk allocation problem is translated into a searching problem to find a best bucketvector among many candidates. The most distinctive feature of the proposed method is in the searching mechanism, in which the fitness values of a group of solutions searched in the past are fed back to the searching mechanism as an input parameters for future searching, thus the searching proceeds toward the direction determined by the fitness values, adaptively. These fitness values are calculated by the objective function we set, thus we can control the searching direction by feeding the objective function to the searching mechanism. A design objective of reflecting the data access patterns to the disk allocation method can be achieved by applying the objective function which calculates the response time for the partial match queries having the given access patterns. As an efficient adaptive searching method, we use genetic algorithm. In this thesis, a new Disk Allocation method based on Genetic Algorithm(DAGA) and a Parallel implementation of the DAGA(ParaDAGA) are proposed.
The genetic operators such as crossover, mutation, and reproduction are proposed for the DAGA and it is also proven that the DAGA can realize a near-optimal solution with high probability by comparing the effects of genetic operators on the bucketvectors to the schema theory. Comparing the quality of solution derived by the DAGA with the General Disk Modulo(GDM), BDM, and ECC methods through the simulation, shows that 1) the DAGA is superior to the GDM method in all the cases, 2) with the restrictions being placed on the number of disks, the average response time of the DAGA is always less than that of the BDM method and greater than that of the ECC method in the absence of data skew, and 3) when data skew is considered, the DAGA performs better than both BDM and ECC methods, even when restrictions on the number of disks are enforced.
With an ultimate goal of comparing the solution quality obtained from the parallel genetic algorithm to the sequential genetic algorithm, a parallel genetic algorithm called ParaDAGA is considered and simulated on a single processor platform. The ParaDAGA is based on a distributed population structure, where each subpopulation is concurrently evolved by the DAGA and an exchange of individuals(known as migration) takes place periodically. As a part of the presented experimental analysis, the impacts of varying the ParaDAGA parameters - the number of subpopulation, the size of subpopulation, migration interval, migrant selection strategy, the number of migrants, and the number of neighbors - are investigated. The results of simulation for quality comparison show that the ParaDAGA consistently provides the better quality of solution than a sequential genetic algorithms when applied to the disk allocation problem.'
본 논문에서 고찰하는 디스크 데이타 배치 문제는 다중의 디스크에 이진 Cartesian Product 파일 시스템을 구성할 때, 단위 데이타 블록인 버킷들을 다중의 디스크들에 배치하는 방식을 찾는 문제로서, 궁극적인 설계 목표는 부분일치 질의어에 대한 데이타 처리시에 디스크 입출력 처리의 병렬성을 최대화하여 질의어 처리시간을 최소화하는 것이다.
이 문제는 NP-hard의 부류에 속하는 문제로 알려져 있기 때문에 제안된 대부분의 방식들은 휴리스틱 접근 방식을 적용하고 있다. 그런데, 최근에 발표된 대부분의 효율적인 방식들은 적용되는 디스크의 수가 2의 지수승이어야 한다는 제약을 가지고 있어서, 시스템 확장시 가격과 공간의 측면에서 문제가 있다. 또한 지금까지 제안된 모든 방식들은 특정 어트리뷰트에 대한 요구빈도의 편향성으로 인하여 발생되는 디스크 부하 불균형에 대한 고려를 하지 않았다. 실제 데이타베이스 응용 환경에서는 어트리뷰트들에 대한 요구가 불균등하게 이루어지는 경우가 흔히 발견되기 때문에 질의어 처리시간을 개선하기 위해서는 디스크 데이타 배치 방식에 이를 고려하는 것이 매우 중요하다.
본 논문에서는 우수한 성능을 제공하면서도 적용되는 디스크의 수에 제약이 없으며, 불균일한 어트리뷰트 요구 현상에 대한 고려가 반영된 새로운 디스크 데이타 배치 방식인 DAGA를 제안한다.
제안된 방식의 설계 개념은 버킷벡터와 디스크 사상함수의 정의로부터 시작된다. 버킷벡터는 디스크에 배치될 모든 버킷들을 임의의 순서대로 배열한 버킷 순열이며, 디스크 사상함수는 버킷벡터내의 각 버킷을 특정 디스크에 배치시키는 함수이다. DAGA의 디스크 사상함수는 각 버킷을 버킷벡터에서 위치하는 위치값만을 이용하여 사상될 디스크를 정하는 방식을 택하여 디스크의 수에 대한 제약을 두지 않는다. 디스크 사상함수를 서로 다른 순열의 버킷벡터에 적용하면, 서로 다른 버킷 배치의 결과가 되어 디스크 데이타 배치 문제는 많은 버킷벡터들 중에서 최적의 버킷벡터를 찾아내는 탐색 문제로 변환된다. DAGA의 가장 두드러진 특징은 버킷벡터의 탐색 방식인데, 지금까지 탐색된 버킷벡터들의 판별값을 계산하여 새로운 버킷벡터를 탐색하는데 필요한 입력 변수로 이용함으로써, 판별값에 의해 탐색 방향이 제어되는 적응 탐색 방식이다. 이 판별값은 목적 함수에 의해서 계산되기 때문에, 목적 함수를 통하여 찾고자 하는 최적의 결과를 제어할 수 있다. 따라서, 목적 함수를 특정 어트리뷰트의 요구빈도의 편향성이 있는 조건에서의 응답시간을 계산하도록 정하면 적응 탐색방식에 의해 불균일한 어트리뷰트 요구 현상을 반영한 버킷벡터를 찾아낼 수 있다. DAGA에서는 이러한 효율적인 적응 탐색 방식으로서 유전자 알고리즘을 이용한다.
디스크 데이타 배치 문제를 유전자 알고리즘에 적용하기 위하여 버킷벡터를 정의하여 디스크 데이타 배치 문제를 유한 길이의 스트링으로 표현하였고, 버킷벡터에 대한 유전자 교배, 돌연변이, 세대 재생성 등과 같은 유전자 오퍼레이터를 설계하였다. 또한, 스키마 이론을 이용하여 DAGA의 수렴성을 수학적으로 증명하여 제안된 방식이 최적의 데이타 배치 방식을 찾아낼 가능성이 확률적으로 매우 높음을 보였다. 기존의 제안된 방식들과의 우위성 비교실험으로부터 디스크의 수에 대한 제약이 없는 조건에서 DAGA는 GDM 방식보다 항상 우수한 결과를 제공함을 알 수 있었고, 디스크의 수가 2의 지수승이라는 조건에서는 어트리뷰트에 대한 요구가 균일한 경우에는 DAGA는 BDM 보다는 우수하고, ECC 방식에는 미치지 못함을 알 수 있었다. 그러나 불균일한 어트리뷰트 요구에대한 실험 결과는 DAGA 방식이 BDM, ECC 방식들보다 우수한 데이타 배치 방식을 찾아냄을 보여 주었다.
그리고, 본 논문에서는 DAGA를 병렬처리 컴퓨터에서 수행하기 위하여 병렬화한 ParaDAGA를 제안하였다. ParaDAGA는 객체군을 여러개의 소객체군으로 나누어 병렬처리 컴퓨터의 각 노드에서 분산 처리하는 방식이다. 각 노드에서는 노드에 할당된 소객체군에 대하여 DAGA를 적용하여 객체들을 진화시키고, 주기적으로 인접한 노드들간에 일정량의 객체를 상호 교환한다. 인접한 노드로부터 이전된 객채는 각 노드가 가지고 있던 객체와 합쳐져서 새로운 소객체군을 생성하고 이 객체군에 대하여 다시 DAGA가 적용되어 객체가 진화된다. 이러한 방식은 병렬화를 통한 시뮬레이션 시간 단축의 효과와 더불어 DAGA 방식보다 양질의 결과를 추구할 수 있는 방식으로서 본 논문에서는 DAGA와 ParaDAGA에서 구해지는 결과의 질을 비교할 목적으로 실험을 수행하였다. 실험 결과는 ParaDAGA가 DAGA보다 항상 더 우수한 결과를 제공함을 보여주고, 각 노드내에 할당될 소객체군의 크기가 적절한 수준으로 설정되면 노드의 수가 증가함에 따라 보다 양질의 버킷 배치 결과가 구해짐을 보여 주었다.
