In this paper, we study the distance-2 broadcast scheduling problem in synchronous wireless networks of known topology.Two constraints are taken under consideration: the schedule must be collision-free and the nodes at distance 2 must be informed by nodes at distance 1.In general graphs, a tight bound of O(log(n) 2 ) slots to complete the broadcast is known, n being the number of nodes at distance 2. We improve this bound to O(log(n)) in unit disk graphs, and to O(1) when the neighbourhoods of the nodes are circular intervals.

The paper deals with the study of the optimisation of the distribution of the download time from a particular video on demand system. This VOD system is based on grid delivery network which is an hybrid architecture based on P2P and grid computing concepts. In this system, the data are shrunk into fixed size blocks which must be replicated on hosts to decrease the total download time. We propose an optimal replication factor to optimise the average download time. We showed that the allocation methods are directly correlated with the variance of response waiting time. We analyse different heuristics to solve these two problems in practice, and validate them through simulation. With our methods, we can guarantee a pre-established waiting response time with an error of approximately 10%.

In this paper, we examine the data replication problem in a particular grid delivery network (GDN). In this system, the data are divided into fixed size blocks which must be replicated on hosts to decrease the total download time. We propose a probabilistic model to optimize the average download time of requests based on the hosts availability and the document size distribution. The objective function induced by this model is a nonlinear integer problem. It can be solved in real values by Lagrangian optimization. We prove that in a particular case, this problem can be reduced to a knapsack problem. We propose approximation algorithms and validate them using simulations with varying characteristics.

The authors study the implementation of dense linear algebra kernels, such as matrix multiplication or linear system solvers, on heterogeneous networks of workstations. The uniform block-cyclic data distribution scheme commonly used for homogeneous collections of processors limits the performance of these linear algebra kernels on heterogeneous grids to the speed of the slowest processor. We present and study more sophisticated data allocation strategies that balance the load on heterogeneous platforms with respect to the performance of the processors. When targeting unidimensional grids, the load-balancing problem can be solved rather easily. When targeting two-dimensional grids, which are the key to scalability and efficiency for numerical kernels, the problem turns out to be surprisingly difficult. We formally state the 2D load-balancing problem and prove its NP-completeness. Next, we introduce a data allocation heuristic, which turns out to be very satisfactory: Its practical usefulness is demonstrated by MPI experiments conducted with a heterogeneous network of workstations.

We address the issue of implementing matrix multiplication on heterogeneous platforms. We target two different classes of heterogeneous computing resources: heterogeneous networks of workstations and collections of heterogeneous clusters. Intuitively, the problem is to load balance the work with different speed resources while minimizing the communication volume. We formally state this problem in a geometric framework and prove its NP-completeness. Next, we introduce a (polynomial) column-based heuristic, which turns out to be very satisfactory: We derive a theoretical performance guarantee for the heuristic and we assess its practical usefulness through MPI experiments.

In this paper, we address the issue of implementing matrix-matrix multiplication on heterogeneous platforms. We target two different classes of heterogeneous computing resources: heterogeneous networks of workstations, and collections of heterogeneous clusters. Intuitively, the problem is to load balance the work with different-speed resources while minimizing the communication volume. We formally state this problem and prove its NP-completeness. Next we introduce a (polynomial) column-based heuristic, which turns out to be very satisfactory: we derive a theoretical performance guarantee for the heuristic, and we assess its practical usefulness through MPI experiments.

We study the implementation of dense linear algebra computations, such as matrix multiplication and linear system solvers, on two-dimensional (2D) grids of heterogeneous processors. For these operations, 2D-grids are the key to scalability and efficiency. The uniform block-cyclic data distribution scheme commonly used for homogeneous collections of processors limits the performance-of-these operations on heterogeneous grids to the speed of the slowest processor. We present and study more sophisticated data allocation strategies that balance the load on heterogeneous 2D-grids with respect to the performance of the processors. The usefulness of these strategies is demonstrated by simulation measurements for a heterogeneous network of workstations.

An efficient algorithm to simultaneously implement array alignment and data/computation distribution is introduced and evaluated. We re-visit previous work of Li and Chen (J. Li and M. Chen, 1990; 1991), and we show that their alignment step should not be conducted without preserving the potential parallelism. In other words, the optimal alignment may well sequentialize computations, whatever the distribution afterwards. We provide an efficient algorithm that handles alignment and data/computation distribution simultaneously. The good news is that several important instances of the whole alignment/distribution problem have polynomial complexity, while alignment itself is NP-complete (J. Li and M. Chen, 1990).