1) Highlights
Our results during the period mainly deal with the design and analysis of parallel and distributed algorithms. Our results concern two main topics: the solution of large scale systems of equations mainly derived from boundary value problems via parallel or distributed asynchronous iterative algorithms and sequential or distributed solution of difficult integer programming problems.

1.1) Distributed asynchronous iterative algorithms
We have been working on this topic for a while. We have considered in particular mathematical modeling and convergence analysis (see [ACL6]), stopping criteria and study of round off errors (see [ACL56] and [ACL502]) and study of performance (see [ACL308]). We have contributed to the design and study of a new class of parallel or distributed iterative algorithms, i.e. Asynchronous Algorithms with Order Intervals, AAOI for short (see [ACL6]). The AAOI class is a general class of parallel or distributed iterative algorithms whereby several processors can perform computations, i.e. updating phases, at their own pace, without any order nor synchronization. One of the main features of this new class of algorithms is that the current value of the components of the iterate vector, i.e. a partial update which is not necessarily labeled by an iteration number can be used in the computation (see Figure 1), whereas only values labeled by an iteration number are used with the classical asynchronous iterative model. This new feature is particularly important in the case of convergence under partial ordering since it permits one to obtain better efficiency of parallel/distributed algorithms. This feature is also attractive when using two stages iterative methods or bloc iterative methods since it is not necessary to wait for the completion of an iteration to get updates. As a consequence, the AAOI model fits new communication mechanisms like RMA and introduces more flexibility in the way data can be used in computations. Convergence results in a contraction context have been established for AAOI in [ACL6].
Several theoretical stopping criteria in relationship with forward, backward or absolute errors have been proposed for perturbed asynchronous fixed point methods in the presence of round-off errors (see [ACL56] and [ACL502]). The last case is particularly interesting since all tests are made within the same macro-iteration. We have studied distributed termination detection in [ACTN5]. In particular, we have proposed a method based on activity graph and messages acknowledgement that tends to minimize the number of exchanged messages.
Issues related to the implementation of asynchronous algorithms on message passing architectures have been studied in details in [ACTI681] with emphasize on communications aspects. Efficiency of synchronous and asynchronous iterative schemes of computation has been studied for nonlinear convection diffusion problems in [ACL308]. In this last paper, computational results on IBM SP4 machines with more than one hundred processors have been analyzed in details for different communication frequencies (see Figure 2) showing the interest of asynchronous algorithms with high communication frequencies.
We have also worked on easiness of use of distributed architectures. Several generic solutions have been proposed for problems linked both to computing and networking in distributed peer to peer applications. These solutions concern initiation and termination of computation, task transparency and routing. A first series of computational results with application to shortest path problems solved via auction algorithms are presented in [ACTI80]. A self adaptive protocol for peer to peer high performance computing has also been proposed in [INV49]. The self adaptive protocol which combines micro protocols is developed in the framework of ANR Project CIP that deals with the design of a decentralized environment for distributed peer to peer computing (see also next Section).

 1.2) Distributed methods for integer programming
Many integer programming problems are very difficult to solve; one speaks of NP-complete problems. As a consequence, the solution of these problems is a great challenge for parallel/distributed computing. Nevertheless, most parallel/distributed solvers are derived from sequential solvers and the attractiveness of a parallel method mainly depends on the sequential method it is derived from. This is why DCA does also some research work on sequential methods for integer programming problems before deriving efficient parallel or distributed algorithms, as we shall see in the sequel.
DCA has concentrated on knapsack problems, e.g. multidimensional knapsack problems and knapsack sharing problems that arise in several practical contexts like cargo loading, capital budgeting, processor allocation and cutting stock problems. We have dealt with complexity issues. We have concentrated in particular on the origin of difficulty and the generation of difficult instances (see [ACTN241] and [TH147]).
DCA has produced a series of works on the solution of multidimensional knapsack problems. Several heuristics that outperform well known heuristics in the literature in time and quality of solution have been proposed in [ACTN178] and [EXT1]. Exact cooperatives methods that combine dynamic programming and branch and bound have been studied in [ACTI1063] and [ACTN189]. Research works have also been done on domain reduction techniques. These studies permit one to precondition problems. We have considered in particular constraint rotation methods (see [ACL551]). Let us note finally that a method based on Lagrangian relaxation has also been proposed for the solution of combinatorial problems with equality constraints (see [ACTN170]).
A parallel dynamic programming algorithm based on lists method with pseudo polynomial complexity has been proposed for knapsack problems (see [ACL2]). Data exchange management plays a prominent part in this parallel method. Several load balancing techniques have been studied in order to obtain efficient parallel methods (see [ACL2] and [ACTI358]).

2) Major Achievements
We would like to put forward first the set of results on asynchronous iterative algorithms quoted in the previous subsection since these results concern all the aspects related to this topic i.e. convergence analysis (see [ACL6]), stopping criteria (see [ACL56] and [ACL502]), implementation and performance analysis (see [ACL308]).
We emphasize also on the organization in LAAS-CNRS of the 16th international conference on Parallel Distributed and network-based Processing, PDP, February 13-15, 2008 (see http://www.pdp2008.org/). Dr Didier El Baz was Chair of the Organizing Committee and Chair of the Program Committee (see [DO12]). This successful conference has received 140 papers from 24 countries; this represents a 40% increase of papers as compared with previous years; 40% of papers have been selected as regular papers for publication in the Proceedings published by IEEE CPS and 120 researchers attended the conference. We have also organized a CUDA tutorial with the help of NVIDIA USA and NVIDIA France (see http://www.pdp2008.org/nvidia.html). This tutorial was also very successful with 40 participants from 8 countries.
Dr Didier El Baz was also Chair of the Program Committee of PDP Weimar, Germany, February 18-20, 2009 (see [DO20] and http://www.pdp2009.org/). Dr Didier El Baz has also organized Special Session: Integer Programming and Industrial Applications at international conference on Computers and Industrial Engineering, CIE39, Troyes, July 6-8, 2009 (see http://www.utt.fr/cie39/SSSS.htm).
We put also forward the results we have obtained on the design and implementation of a decentralized environment for High Performance Peer-to-Peer Distributed Computing, P2PDC. These results were obtained in the framework of ANR Project ANR-07-CIS7-011 coordinated by Dr. Didier El Baz. This work represents our contribution to addressing the challenge of using and programming large scale distributed architectures. The P2PDC decentralized environment aims at providing an economic approach for the solution of large scale numerical simulation problems or difficult optimization problems via distributed iterative methods. The P2PDC environment is based the P2PSAP self-adaptive communication protocol. The P2PSAP protocol relies on a reduced set of communication operations for easiness of programming. The communication mode, e.g.,  synchronous or asynchronous, depends on elements of context at network level like type of communication network, e.g., Infiniband or Ethernet networks and topology, e.g., intra or inter cluster communication; it depends also of elements of context at application level like scheme of computation, e.g., synchronous iterative scheme, asynchronous iterative schemes or hybrid schemes (see Recent Publications).
Finally, we put forward the results we have obtained on GPU Computing and Hybrid Computing for the solution of combinatorial optimization problems and the NVIDIA Academic Partnership obtained by Dr. Didier El Baz in 2010. We note that efficient Branch and Bound hybrid methods and dynamic programming hybrid methods have been proposed (see Recent Publications).


Main References
[ACL2] D. El Baz, M. Elkihel, Load balancing methods and parallel dynamic programming algorithm using dominance technique applied to the 0-1 knapsack problem, Journal of Parallel and Distributed Computing, V. 65, 2005, p. 74-84.
[ACL6] D. El Baz, A. Frommer, P. Spiteri, Asynchronous iterations with flexible communication: Contracting operators, Journal of Computational and Applied Mathematics, Vol. 176, Issue 1, April 2005, p. 91-103.
[ACL56] J.-C. Miellou, P. Spiteri, D. El Baz, Stopping criteria, forward and backward errors for perturbed asynchronous linear fixed point methods in finite precision, IMA Journal of Numerical Analysis, vol. 25, 2005, p. 429-442.
[ACL308] M. Chau, D. El Baz, R. Guivarch, P. Spiteri, MPI implementation of parallel subdomain methods for linear and nonlinear convection-diffusion problems, Journal of Parallel and Distributed Computing, Vol. 67, 2007, p. 581-591.
[ACL502] J.-C. Miellou, P. Spiteri, D. El Baz, A new stopping criterion for linear perturbed asynchronous iterations, Journal of Computational and Applied Mathematics, Vol. 219, Issue 2, October 1, 2008, p. 471-483.
[ACL551] D. El Baz, M. Elkihel, L. Gély, G. Plateau, Improved time and space complexity for Kianfar's inequality rotation algorithm, European Journal for Industrial Engineering, Vol. 3, N° 1, 2009, p. 90-98.
[ACTI80] G. Jourjon, D. El Baz, Some solutions for peer to peer global computing, Proceedings of the 13-th conference on Parallel, Distributed and network-based Processing, PDP 2005, Lugano, Suisse, February 9-11, 2005, IEEE CPS, p. 49-58.
[ACTI681] D. El Baz, Communication study and implementation analysis of parallel asynchronous iterative algorithms on message passing architectures, Proceedings of the 15-th conference on Parallel, Distributed and network-based Processing, Naples, February 7-9, 2007, IEEE CPS, p. 77-83.
[DO12] D. El Baz, J. Bourgeois, F. Spies editors, Proceedings of the 16th conference on Parallel, Distributed and network-based Processing, Toulouse, February 13-15, 2008, IEEE CPS, 670 pages.
[DO20] D. El Baz, F. Spies, T. Gross editors, Proceedings of the 17th conference on Parallel, Distributed and network-based Processing, Weimar, February 18-20, 2009, IEEE CPS, 460 pages.
[INV49] D. El Baz et al. Calcul intensif pair à pair, Forum Ter@tec, 30 Juin-1er Juillet 2009, Supélec.
[EXT1] V. Boyer, M. Elkihel, D. El Baz, Heuristics for the 0-1 multidimensional knapsack problem, European Journal of Operational Research, Special Issue on Cooperative Methods, Vol. 199, N° 3 p. 658-664, 2009.