ABSTRACT
A Grid is a virtual computer created through the interconnection of geographically dispersed, and usually heterogeneous, computing and data resources. In this chapter, we focus on the algorithmic issues to be addressed when trying to efficiently deploy one or several applications on a Grid (or, more generally, on a distributed and heterogeneous collection of computing resources). The most obvious problem with Grids is their heterogeneity. For instance, any Grid will contain
processors of different characteristics and the running time of any application will thus depend on processors that have been enrolled to execute it. The obvious pitfall for a parallel computation using processors of different speeds would be to slow down its execution at the pace of the least efficient processor. An intuitive approach to circumvent this problem would be to pick only fast processors or, at least, to pick processors of equivalent processing power. As shown in Section 29.2.2, this intuition can lead to very poor performance. Indeed, in some cases, it is not computing power that matters, but communication capabilities. In a Grid, of course, the communication capabilities of the different entities will be also heterogeneous. Communications in Grids can be even more a problem than in traditional parallel computers because of the irregularity of the interconnection network and also because of longer distance, and thus slower, communication links. In Grids, resources are abundant, but the resources used to solve a problemmust be carefully chosen: resource selection is key to performance.
