HIGH THROUGHPUT COMPUTING DUE TO NEAR-OPTIMAL EMERGENT MULTIAGENT COALITIONS FOR LOAD SHARING

Leland Hovey, Mina Jung

2012

Abstract

Grid CPU load-sharing is a subclass of computational grid resource management. Its purpose is to improve grid throughput – High Throughput Computing (HTC). The problem is load-sharing optimization state-space can be quite large. This is because of two factors: the load-sharing optimization problem is NP-complete, and a large volume of CPU-intensive loads can require thousands of Internet connected CPUs. Approximate models can find near-optimal solutions to NP-complete problems. Multiagent coalition formation (MCF) is a particular approximate game theoretic approach for these problems. We propose a new distributed MCF (DMCF) model for Grid CPU load-sharing, DMCF grouping genetic algorithm (DMCF-GGA). This paper presents the model in detail. It also compares this model with our existing model, DMCF-spatial. The comparison consists of a discussion of the models’ similarities and differences, and a comprehensive empirical evalution. The results of this study are the following: The optimization search cost of DMCF-GGA is significantly less than DMCF-spatial. DMCF-GGA has a linear relation between coalition size and search cost (for high throughput). We have found preliminary lower and upper bound estimates for the effective coalition size. We have also found the average job sizes required for the run time of DMCF-GGA to be 1% of the job execution time.

Paper Citation

in Harvard Style

Hovey L. and Jung M. (2012). HIGH THROUGHPUT COMPUTING DUE TO NEAR-OPTIMAL EMERGENT MULTIAGENT COALITIONS FOR LOAD SHARING . In Proceedings of the 4th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART, ISBN 978-989-8425-95-9, pages 295-305. DOI: 10.5220/0003733702950305

in Bibtex Style

@conference{icaart12,
author={Leland Hovey and Mina Jung},
title={HIGH THROUGHPUT COMPUTING DUE TO NEAR-OPTIMAL EMERGENT MULTIAGENT COALITIONS FOR LOAD SHARING},
booktitle={Proceedings of the 4th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,},
year={2012},
pages={295-305},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003733702950305},
isbn={978-989-8425-95-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 4th International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,
TI - HIGH THROUGHPUT COMPUTING DUE TO NEAR-OPTIMAL EMERGENT MULTIAGENT COALITIONS FOR LOAD SHARING
SN - 978-989-8425-95-9
AU - Hovey L.
AU - Jung M.
PY - 2012
SP - 295
EP - 305
DO - 10.5220/0003733702950305