Multithreaded Maximum Flow Based Optimal Replica Selection Algorithm for Heterogeneous Storage Architectures
- 1 July 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 65 (5) , 1543-1557
Abstract
Efficient retrieval of replicated data from multiple disks is a challenging problem, especially for heterogeneous storage architectures. Recently, maximum flow based optimal replica selection algorithms were proposed guaranteeing the minimum retrieval time in heterogeneous environments. Although optimality of the retrieval schedule is an important property, execution time of the replica selection algorithm is also crucial since it might significantly affect the performance of the storage sub-system. Current replica selection mechanisms achieve the optimal response time retrieval schedule by performing multiple runs of a maximum flow algorithm in a black-box manner. Such black-box usage of a maximum flow algorithm results in unnecessary flow calculations since previously calculated flow values cannot be conserved. In addition, most new generation multi-disk storage architectures are powered with multi-core processors motivating the usage of multithreaded replica selection algorithms. In this paper, we propose multithreaded and integrated maximum flow based optimal replica selection algorithms handling heterogeneous storage architectures. Proposed and existing algorithms are evaluated using various homogeneous and heterogeneous multi-disk storage architectures. Experimental results show that proposed sequential integrated algorithm achieves 5X speed-up in homogeneous systems, and proposed multithreaded integrated algorithm achieves 21X speed-up using 16 threads in heterogeneous systems over the existing sequential black-box algorithm.Keywords
This publication has 28 references indexed in Scilit:
- Generalized Optimal Response Time Retrieval of Replicated Data from Storage ArraysACM Transactions on Storage, 2013
- Integrated Maximum Flow Algorithm for Optimal Response Time Retrieval of Replicated Data2012
- Selective Replicated Declustering for Arbitrary Queries2009
- Multi-Site Retrieval of Declustered Data2008
- Analysis and Comparison of Replicated Declustering SchemesIEEE Transactions on Parallel and Distributed Systems, 2007
- Optimal Distributed Declustering Using Replication2004
- Asynchronous scheduling of redundant disk arraysIEEE Transactions on Computers, 2003
- Random duplicated assignment1997
- LEDA: a platform for combinatorial and geometric computingCommunications of the ACM, 1995
- Maximal Flow Through a NetworkCanadian Journal of Mathematics, 1956