MY SCIENTIFIC AND TECHNICAL PRODUCTION

Back to Homepage

1. Claude Tadonki, and Bernard Philippe, Parallel multiplication of a vector by a Kronecker product of matrices, Parallel Distributed Computing Practices PDCP, volume 2(4), 1999.
   Abstract. We provide a parallel algorithm for the Kronecker product of matrices based on a cyclic partition of loops. Our general model unifies one scheme with redundant computations but no communication and an opposite scheme without redundant computation but with interprocessor communications. Both schema can be mixed with a certain balance influenced by the volume of floating point operations and the characteristics of the target architecture. This work has valuated experimental validations ({\small CENJU and INTEL PARAGON}).
2. Claude Tadonki, and Bernard Philippe, Parallel multiplication of a vector by a Kronecker product of matrices (part II), Parallel Distributed Computing Practices PDCP, volume 3(3), 2000.
   Abstract. This paper presents a revised and generalized version of our previous parallel algorithm for the Kronecker product of matrices. We show how to map the computation on any number of processors that is a divisor of the product of the matrices sizes (instead of being a prefix of this product as previously). Moreover, we show that the minimum number of parallel communications with p processors is log(p) whatever the algorithm, and that our algorithm achieves this optimal performance. The work is validated by significant efficiencies obtained from experimental measures on the {\small CRAY} machine.
3. Sanjay Rajopadhye, Tanguy Risset, et Claude Tadonki, Algebraic Path Problem on linear arrays, Techniques et Sciences Informatiques  TSI, 20 (5), 2001.
   Abstract. We seek a linear SPMD implementation of the Warshal algorithm for the Algebraic Path Problem (Unified model of the transitive closure, shortest paths, Gauss elimination, ...). Our parallel algorithm is systolic-like in its original version, and offers the important advantage of being able to run on a shorter number of processors by a natural round- robbing remapping. We derive and validate a blocked version for standard distributed memory parallel machines, as the cost of data communication would be severe otherwise. We show experimental validations on the {\small CRAY} machine.
4. Claude Tadonki, A Recursive Method for Graph Scheduling, Scientific Annals of Cuza University, Vol 11, p.121-131, 2002
   Abstract. This paper presents a recursive graph scheduling method. Our paradigm applies on any acyclic graph that can be partitioned into isomorphic subgraphs. Indeed, many common problem domains are 3D graphs that can be organized as a chain of isomorphic 2D subgraphs. Starting from any valid schedule of the source subgraph of the chain, we use the generic isomorphism to systematically derive a valid global schedule, with a local pipeline between two consecutive subgraphs. Our technique is then characterized by the nature of the partition and the source schedule. We discuss the impact of these characteristics on the complexity on the generated parallel schedules.
5. C. Beltran, C. Tadonki and J.-Ph. Vial, Solving the p-median problem with a semi-Lagrangian relaxation, Computational Optimization and Applications, Volume 35(2), October 2006. (pdf)
   Abstract. This paper deals with operation research and non differentiable optimization. The so-called P-median problem is the problem of locating P "facilities" relative to a set of "customers" such that the sum of the shortest demand weighted distance between "customers" and "facilities" is minimized. Indeed, this a classical combinatorial optimization problem with a huge set of potential solutions. Using a semi-Lagrangian relaxation, we tackle the problem in its associated continuous formulation and report our non-smooth convex optimization engineering results.
6. F. Babonneau, C. Beltran, A. Haurie, C. Tadonki and J.-P. Vial, Proximal-ACCPM: a versatile oracle based optimization method, Computational and Management Science, Volume 9, 2007. (pdf)
   Abstract. Oracle Based Optimization (OBO) conveniently designates an approach to handle a class of convex optimization problems in which the information pertaining to the function to be minimized and/or to the feasible domain takes the form of a linear outer approximation revealed by an oracle. We show how difficult problems can be cast in this format, and then solved within our context. We present our method, so-called Proximal-ACCPM, to trigger the OBO approach and give a snapshot on numerical results. This paper summarizes several contributions with the OBO approach and aims to give, in a single report, enough information on the method and its implementation to facilitate new applications.
7. C. Tadonki, Mathematical and Computational Engineering in X-Ray Crystallography, International Journal of Advanced Computer Engineering, volume 1(2) 2008.
   Abstract. The main purpose of X-Ray Crystallography is to predict a macromolecular structure using from X-Ray synchrotron radiation. Among existing paradigms to achieve this task, analytical approaches come up as good candidates for automation trough mathematical approximations and computational engineering. In addition to the later, statistical processing are required in order to refine the data according to the physical model and the boarding effects of the experiments. We revisit the basis of the problem and focus on a more precise effect, so-called radiation damage, for which it has been also proven that it can be artificially managed to become instructive.
8. T. Saidani, L. Lacassagne, J. Falcou, C. Tadonki, Samir Bouaziz, Parallelization Schemes for Memory Optimization on the Cell Processor : A Case Study on the Harris Corner Detector, Transactions on High-Performance Embedded Architectures and Compilers, volume 3(3) 2008.
   Abstract. The Cell processor is a typical example of heterogeneous multiprocessor on-chip architecture that uses several levels of parallelism to deliver high performance. Although its efficiency potential, the execution mode and part of hardware specificities make it being non trivial to deal with. Indeed, reducing the gap between peak performance and effective performance is the challenge for compiler design and efficient implementations. Image processing and media applications are typical "main stream" applications one could consider while investigating on Cell benchmarks. Our investigations, trough various implementation of the Harris detection algorithm, reveal that the impact of DMA controlled data transfers and synchronizations between SPEs are key points for global performance.
9. C. Tadonki, Integer Programming Heuristic for the Dual Power Setting Problem in Wireless Sensors Networks, Int. Journal of Advanced Research in Computer Engineering, vol 3(1) 2009.
   Abstract. We seek an integer programming based heuristic for solving the dual power management problem in wireless sensor networks. For a given network with two possible transmission powers (low and high), the problem is to find a minimum size subset of nodes such that if they are assigned high transmission power while the others are assigned low transmission power, the network will be strongly connected. The main purpose behind this efficient setting is to minimize the total communication power consumption while maintaining the network connectivity. In a theoretical point of view, the problem is known to be difficult to solve exactly. An approach to approximate the solution is to work with a spanning tree of clusters. Each cluster is a strongly connected component when consider low transmission power. We follow the same approach, and we formulate the node selection problem inside clusters as an integer programming problem which is solved exactly using specialized codes. Experimental results show that our algorithm is efficient both in execution time and solution quality.
10. C. Tadonki, G. Grodidier, O. Pene, An efficient CELL library for lattice quantum chromodynamics, ACM SIGARCH Computer Architecture News, vol 38(4) 2011.
    Abstract. Quantum chromodynamics (QCD) is the theory of subnuclear physics, aiming at modeling the strong nuclear force, which is responsible for the interactions of nuclear particles. Numerical QCD studies are performed through a discrete formalism called LQCD (Lattice Quantum Chromodynamics). Typical simulations involve very large volume of data and numerically sensitive entities, thus the crucial need of high performance computing systems. We propose a set of CELL-accelerated routines for basic LQCD calculations. Our framework is provided as a unified library and is particularly optimized for an iterative use. Each routine is parallelized among the SPUs, and each SPU achieves it task by looping on small chunk of arrays from the main memory. Our SPU implementation is vectorized with double precision data, and the cooperation with the PPU shows a good overlap between data transfers and computations. Moreover, we permanently keep the SPU context and use mailboxes to synchronize between consecutive calls. We validate our library by using it to derive a CELL version of an existing LQCD package (tmLQCD). Experimental results on individual routines show a significant speedup compare to standard processor, 11 times better than a 2.83 GHz INTEL processor for instance (without SSE). This ratio is around 9 (with QS22 blade) when consider a more cooperative context like solving a linear system of equations (usually referred as Wislon-Dirac inversion). Our results clearly demonstrate that the CELL is a very promising way for high-scale LQCD simulations.

1. Claude Tadonki, and Bernard Philippe, Parallel multiplication of a vector by a Kronecker product of matrices, IRISA report n° 1194, 1998.
   Optimal Parallel Algorithm for the Kronecker Product in log(p) communication steps
   
2. Patrice Quinton, Claude Tadonki, et Maurice Tchuente,  Un échéancier systolique et son utilisation dans l'ATM,  IRISA report n° 1348, 2000.
   
3. Claude Tadonki, Synthèse d'ordonnancements parallèles par reproduction canonique, IRISA report n° 1349, also INRIA report n° 3996, 2000.
   
4. David Cachera, Sanjay Rajopadhye, Tanguy Risset, and  Claude Tadonki, Parallelization of the algebraic path problem on linear simd/spmd arrays, IRISA report n° 1409, 2001.
   
5. Claude Tadonki and Jean-Philippe Vial, The linear separation problem revisited with accpm , Cahier de Recherche n° 2002.11, University of Geneva, June 2002. ( get it! )
6. F. Babonneau, C. Beltran, O. du Merle, C. Tadonki and J.-P. Vial, The proximal analytic center cutting plane method, Technical report, Logilab, HEC, University of Geneva, 2003.
7. Cesar Beltran, Claude Tadonki, and Jean-philippe Vial, Semi-Lagrangian relaxation, Technical report, Logilab, HEC, University of Geneva, 2004.

1. Ordonnancement pour l'informatique parallele, A. Moukrim and C. Picouleau (Edt), Hermes, ( details! ).

1. A. Dubois, A. Haurie, C. Tadonki, and D. Zachary, An Operational Energy Modelling System, 2003 ( get it! )
   
2. R. Ndoundam, C. Tadonki, and M. Tchuente, Parallel chip firing game associated with n-cube orientation, 2000 ( get it! ).
   
3. F. Babonneau, C. Beltran, O. du Merle, C. Tadonki, and J.-P. Vial, The proximal analytic center cutting plane method , 2003 ( get it! ).
4. C. Tadonki, Universal Report: A generic reverse engeneering tool, 2003 ( get it! ).
5. C. Tadonki, M. Singh, R. Jose, and V. Prasanna, Combinatorial technic for memory power state scheduling in energy-constrained system, 2003 ( get it! ).
6. D. Cachera, S. Rajopadye, T. Risset, and C. Tadonki,  Algorithmic tiling for efficient parallel APP implementation, 2003 ( get it! ).
7. C. Tadonki and J.-P. Vial,  Portfilio Selection with Cardinality and Bound Constraint, 2003 ( get it! ).
8. C. Tadonki and J. Rolim,  An analytical model for energy minimization, 2003 ( get it! ).
9. C. Tadonki and J. Rolim,  An integer programming heuristic for the dual power management problem in wireless sensor networks, 2004 ( get it! ).

1. Portfolio Selection with Cardinality Constraints
2. Efficient Matrix Computations in Cutting Planes Algorithms
3. Algorithmic Technics of Designing Energy Efficient Algorithms
4. Structural Method for Lower Bounds in Complexity
5. Improved Graph Model for Optical Network of Sensors
6. Dynamic Behavior of Parallel Chip Firing Game on Regular Graphs
7. Chapter of a book on "Parallel Scheduling" published by Hermes
8. Book in "Scientific Computation"

Download my CV in PDF