We present a parallel implementations on GPU of an heuristic for solving the Vehicle Routing Problem (VRP) with single and with multi depot. To our knowledge, this is the first GPU implementation of such class of heuristics. Our solution for the classical VRP computes in parallel an initial solution (tours) and then iteratively it improves the costs of all pairs of neighbor tours. The multi depot case is solved by decomposing the problem in several independent basic VRP that we solve in parallel. Obtained experimental results under CUDA show that the proposed implementations exploit efficiently the parallelism and the power of the GPU.

In this work, we consider the scheduling problem of a set of periodic implicit-deadline and synchronous tasks, on a real-time multiprocessor composed of m identical processors. Our contribution consists in improving the temporal distribution of DP-WRAP algorithm by reducing the number of migrations. Indeed, DP-WRAP algorithm assigns tasks randomly and does not take into account the cost of migrations which can reach (m-1) migrations in the worst case. Note that recent experiments upon real platforms show that the cost of migrations has an influence on global system performance. Instead of randomly assigning tasks, we have proposed a task assignment algorithm that has reduced significantly the number of migrations of the DP-WRAP. The first step of the proposed algorithm, based on the classical bin-packing heuristics, allows minimizing the number of migrant tasks, the second step consists in assigning efficiently the migrant tasks. Experimental simulations show that the number of migrations, compared to DP-WRAP, is significantly reduced. This reduction can reach 60%.

We study the complexity of the parallel Givens factorization of a square matrix of size n on a shared memory architecture composed with p identical processors (coarse grained EREW PRAM).We show how to construct an asymptotically optimal algorithm.We deduce that the time complexity is equal to:and that the minimum number of processors in order to compute the Givens factorization inThese results complete previous analysis presented in the case where the number of processors is unlimited.