Bilkent University
Department of Computer Engineering
MS THESIS PRESENTATION
A Bipartite Graph Model for Placement, Scheduling and Replication in Data Grids
Burcu Dal
MSc Student
Computer Engineering Department
Bilkent University
Data grids provide geographically distributed resources for applications that generate and utilize large data sets. However, there are some issues that hinder to ensure fast access to data and low turnaround time for the jobs in data grids. To address these issues, several data replication and job scheduling strategies have been introduced to offer high data availability, low bandwidth consumption, and reduced turnaround time for grid systems. We maintain multiple copies of existing data at different locations via data replication. Also, we aim to improve system throughput by scheduling jobs onto the grid effectively.
Data replication strategies are broadly categorized as static and dynamic. In static replication strategies, replication is performed during the system design, and replica decisions are generally based on a cost model that includes data access costs, bandwidth characteristics and storage constraints of the grid system. In dynamic replication strategies, the replication operation is managed at runtime so that the system adapts to the changes in user request patterns dynamically.
Job scheduling strategies fall under two main categories: online mode and batch mode. The online mode scheduler assigns tasks to sites as soon as they arrive. In the batch mode, the complete set of jobs are taken into account and scheduled at the same time by using all the grid information.
We propose a bipartite graph model for tasks and files in the grid system, and then we partition this graph to obtain a data placement and job scheduling strategy. The obtained parts are further refined in order to be assigned to grid sites by using a KL-based heuristic that takes the bandwidth and hop information between sites into account. Replication is achieved by replicating a certain amount of most accessed files chosen prior to the partitioning process. Experimental results indicate that the increase in the partitioning quality reects positively on the mapping quality. Moreover, it is observed that the communication cost is notably decreased when the data replication is applied.
DATE: 11 September, 2012, Tuesday @ 11:00
PLACE: EA409