The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
본 논문에서 검토하는 디스크 할당 문제는 디스크 할당 방법을 찾는 것이다. 이진 데카르트 곱 파일 부분 일치 검색을 위해 병렬 디스크 I/O 액세스를 최대화하기 위해 여러 디스크에 저장합니다. 이 문제는 NP-hard로 알려져 있으며 최적이 아닌 솔루션을 얻기 위해 경험적 접근 방식이 적용되었습니다. 최근에는 파일이 저장되는 디스크 수가 2의 거듭제곱이어야 한다는 제한과 함께 BDM(Binary Disk Modulo), ECC(Error Correcting Code) 방식과 같은 효율적인 방식이 제안되고 있다. DAGA(Genetic Algorithm) 기반의 디스크 할당 방법을 제안한다. DAGA는 적용할 디스크 수에 제한을 두지 않으며, 데이터 접근 패턴을 고려하여 적응적으로 디스크를 할당할 수 있습니다. 스키마 이론을 사용하여 DAGA가 높은 확률로 거의 최적의 솔루션을 실현할 수 있음을 입증했습니다. 시뮬레이션을 통해 DAGA로 도출된 솔루션의 품질을 GDM(General Disk Modulo), BDM, ECC 방식과 비교한 결과, 1) 모든 경우에서 DAGA가 GDM 방식보다 우수하고 2) 다음과 같은 제한 사항이 있음을 알 수 있습니다. 디스크 수에 따라 DAGA의 평균 응답 시간은 데이터 스큐가 없는 경우 항상 BDM 방식보다 작고 ECC 방식보다 큽니다. 3) 데이터 스큐를 고려하면 DAGA의 성능이 더 좋습니다. 디스크 수에 대한 제한이 적용되는 경우에도 BDM 및 ECC 방법과 같거나 같습니다.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Dae-Young AHN, Kyu-Ho PARK, "Disk Allocation Methods Using Genetic Algorithm" in IEICE TRANSACTIONS on Information,
vol. E82-D, no. 1, pp. 291-300, January 1999, doi: .
Abstract: The disk allocation problem examined in this paper is finding a method to distribute a Binary Cartesian Product File 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 methods such as Binary Disk Modulo (BDM) and Error Correcting Code (ECC) methods have been proposed along with the restrictions that the number of disks in which files are stored should be a power of 2. In this paper, a new Disk Allocation method based on Genetic Algorithm (DAGA) is proposed. The DAGA does not place restrictions on the number of disks to be applied and it can allocate the disks adaptively by taking into account the data access patterns. Using the schema theory, it is proven that the DAGA can realize a near-optimal solution with high probability. 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 and 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 or equal to both BDM and ECC methods, even when restrictions on the number of disks are enforced.
URL: https://global.ieice.org/en_transactions/information/10.1587/e82-d_1_291/_p
부
@ARTICLE{e82-d_1_291,
author={Dae-Young AHN, Kyu-Ho PARK, },
journal={IEICE TRANSACTIONS on Information},
title={Disk Allocation Methods Using Genetic Algorithm},
year={1999},
volume={E82-D},
number={1},
pages={291-300},
abstract={The disk allocation problem examined in this paper is finding a method to distribute a Binary Cartesian Product File 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 methods such as Binary Disk Modulo (BDM) and Error Correcting Code (ECC) methods have been proposed along with the restrictions that the number of disks in which files are stored should be a power of 2. In this paper, a new Disk Allocation method based on Genetic Algorithm (DAGA) is proposed. The DAGA does not place restrictions on the number of disks to be applied and it can allocate the disks adaptively by taking into account the data access patterns. Using the schema theory, it is proven that the DAGA can realize a near-optimal solution with high probability. 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 and 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 or equal to both BDM and ECC methods, even when restrictions on the number of disks are enforced.},
keywords={},
doi={},
ISSN={},
month={January},}
부
TY - JOUR
TI - Disk Allocation Methods Using Genetic Algorithm
T2 - IEICE TRANSACTIONS on Information
SP - 291
EP - 300
AU - Dae-Young AHN
AU - Kyu-Ho PARK
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E82-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 1999
AB - The disk allocation problem examined in this paper is finding a method to distribute a Binary Cartesian Product File 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 methods such as Binary Disk Modulo (BDM) and Error Correcting Code (ECC) methods have been proposed along with the restrictions that the number of disks in which files are stored should be a power of 2. In this paper, a new Disk Allocation method based on Genetic Algorithm (DAGA) is proposed. The DAGA does not place restrictions on the number of disks to be applied and it can allocate the disks adaptively by taking into account the data access patterns. Using the schema theory, it is proven that the DAGA can realize a near-optimal solution with high probability. 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 and 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 or equal to both BDM and ECC methods, even when restrictions on the number of disks are enforced.
ER -