Overview of some of my research topics

Claude Tadonki, HPC researcher
Ecole des Mines de Paris - Centre de Recherche en Informatique (Fontainebleau)

I give here an overview of some of my research topics. I will later provide a list of reference for each of them.


Parallel Computing
Parallel computing is an alternative to achieve a high performance computation. The basic idea is to use several interconnected cpus to solve a given problem. Of course the first step is to design a parallel algorithm. The task is rarely trivial, even for "simple" problems. The reason of this is the dependence exploration task that should be analysed carefully, and the cooperation of computing entities that should be described explicitly (tasks allocation, communications, synchronizations, etc...). The target problem can be specified and analysed using a task graph model, recurrence equations, algebraic modelling, and other. Implementing a parallel algorithm is a delicate task. In a technical point of view, actual parallel computers provide high computing power that can be exploited in order to accomplish complex tasks. A significant step has been also achieved in the direction of languages, compilers, and processors communication management. Reseach activites in the area of parallel computing are particularly active (many research centers, conferences, symposium, workshops, journals).


Combinatorial optimization
Mathematical optimization is a key topic in computer science, applied mathematics, and operation research. There is a wide range of well-known techniques for tackling or solving combinatorial problems. Combinatorial optimization combines techniques from combinatorics, mathematical programming, and the theory of algorithms, to solve optimization problems over discrete structures. There is a long list of combinatorial problems that are subject to intensive researches: Travelling salesman problem, hamiltonian path, scheduling, graph coloring, bin packing, knapsac, maxinum clique, k-median, matching problems, and more. Most of these problems are hard to solve in general. Thus, it is customary to take into account the specificity of some particular and pertinent instances in order to derive solutions that can be used in practice. Current researches continue to improve the impact existing paradigms, bring up new concepts, and propose alternative formulations of challenging problems.


Scientific computing
Scientists and engineers are now involved with more and more challenging computations in their actvities. Writing a sementically correct algorithm is one thing, while providing good performance is another. Modern computational methods should fit the requirement of acceptable time (and/or memory) complexity, whith a special care about the accuracy. There are several domains in which the need of high performance computing is unquestionable. It is the case for numerical mathematics, large scale optimization, image processing, astronomy calculations, meteorolical predictions, nuclear physics, and more. The aim is to provide a real-time processing even if the problem is fundamentally complex and implies a huge amount of data. The computation power of actual supercomputers is a great technical contribution toward this purpose (see Top500 Supercomputer Site). However, never forget that achieving good performance is a conjunction of both the program and the machine.


Algorithm and complexity
Designing efficient algorithms and provide a rigourous analysis of their complexity is a major topic in computer science. Of course the way an algorithm is implemeneted determines its effective efficiency, specially the choice of appropriate data structures. Significant results on the absolute complexity of important problems give the limit of what can be expected. When a given problem is state to be difficult, it is customary to turn to approximation algorithms. In that case, there is a tradeoff between the quality of the solution and the time complexity. Current algorithmic and complexity researches are concerned with sorting, searching, graph problems, number theory, game theory, artificial intelligence, image procesing, geometry, discret optimization, and more.


Energy efficient computation
In recent years, the design tradeoff of performance versus power consumption has received much attention because of

Recent design methodologies and tools have addressed the problem of energy-efficient design, aiming to provide system realization and fast implementation while reducing the power dissipation. Energy/power optimization under performance constraints (and vice versa) is both hard to formulate and solve in general, when considering all degrees of freedom in system design and algorithm synthesis. The topic of energy reduction is being investigated at all levels of system abstraction, from the physical layout to software design. There are three major constituents of hardware that consume energy, namely computation, communication, and storage units. Advanced memory architectures support multiple power states of memory banks, which can be also exploited to reduce energy dissipation in the system. All these features can be taken into account at higher levels including scheduling and precompilation. Data partitioning, storage remapping, explicit I/O management, and algorithmic processing can be separately or jointly consider for energy performance inproving. Energy efficient design is now one of the key points in modern computation.


Wireless Network modelling and algorithms
Recent advancements in wireless communications and electronics have enabled the development of low-cost sensor networks. A sensor is an electronic device that measures some physical quantity and reports it. Emerging technologies such as MicroElectroMechanical Systems (MEMS) have made sensors smaller and cheaper. A sensor network is composed of a large number of sensor nodes that are densely deployed either inside the phenomenon or very close to it. The position of sensor nodes need not to be engineered or predetermined. This allows random deployment in inaccessible terrains or disaster relief operations. The sensor networks can be used for various application areas (health, military, home, environmental, exploration, tracking, and more). For different application areas, there are different technical issues that researchers are currently trying to solve. Sensor networks represent a significant improvement over traditional sensors. Nowadays, we are really surrounded by sensor networks, and this intensive use requires some issues to be revisited for necessary improvements. It is the case of the localization problem, the energy optimization both in computation and communication, and also in the internal operating system of sensors. Existing protocols need to be improved, and new ones are to be developed in oder to fit actual requirements like real-time processing and fault-tolerance. In general, in wireless networks, transmissions are performed in a multi-hop maner. This raises several graph problems that need to be solved, preferably with distributed approaches, for monitoring purposes or related. Another interesting topic is the range assignment problem. Indeed, in a wireless network, each element is a transmitter/receiver, and communication between two elements is possible either directly within their respective ranges, or by multi-hop transmissions otherwise. In the later case, communications can impact serious amount of energy, which is a critical ressources in wireless network. Consequently, energy-efficient protocols are of a particular interest. The problem can be study in a technical point of view, or with combinatorial/geometrical approaches trough the underlying graph models.


Reverse engineering
While or after writing an important set of codes, provide and maintain the corresponding documentation is crucial and quiet helpful. This document helps to understand the program both in its global structure and its internal details. Regardless of the intent of its author, all source code is eventually reused, either directly, or just through the basic need to understand it by other parties. Without documentation, the only way to get the needed information is to make intuitive assumption, analyse the implementation, or interrogate the author. These alternatives are unpractical. There are mainly two ways of producing a documentation from a set of source codes. One way is to write a static and independent documentation, means its content follows from the source codes at a given state. In this case, there is no {\em dynamic link} between the statements in the program and the corresponding items in the documentation. Such static documentation is difficult to maintain, and is not updated as frequently as necessary because of this mechanical aspect of the task. Consequently, as time is going on, the gap between the source codes and the documentation will be so important that this documentation will become obsolete. An efficient way to easily get a detailed and up-to-date documentation is to build a high level document structure and let its items being instantiated automatically. This approach clearly needs a so called {\em automatic source code documentation tool}. Assuming a well documented program, such a tool should be able to extract meaningful source code comments and global structure to create a complete and understanding external documentation. This topic is a fundamental engineering practice critical to efficient software development.


Data analyis in synchrotron crystallography
The interests lie in the improvement of synchrotron X-ray macromolecular (MX) data collection techniques to aid structural biologists in their quest for detailed atomic structures used for understanding biological functions of macromolecules. The Instrumentation Group comprises two teams led by Cipriani and Ravelli. The group develops hardware, software and novel methodologies for data collection and phasing. Members of the group are involved in collaborations on the cell cytoskeleton and leucine-rich repeat proteins. An ongoing development of methods in crystallography has been the characterisation, mitigation and utilisation of radiation damage in MX. The intense undulator synchrotron radiation of 3rd generation synchrotrons rapidly damages the fragile, cryocooled, crystalline macromolecules. Part of our research aims to get an improved understanding as well as a better crystallographic treatment of radiation damage.


Lattice Quantun ChromoDynamic Computing
Quantum chromodynamics (QCD) is the theory of subnuclear physics. All nuclear particles are made of elementary particles called quarks and gluons. The gluons mediate the strong nuclear force that binds the quarks together to form stable nuclear particles. The strong nuclear force is one of the four known physical forces, with the other forces being the electromagnetic force, weak nuclear force, and gravity. The strong nuclear force is also responsible for the interactions of nuclear particles and is, therefore, a fundamental area of study in nuclear physics. Computation studies, throught intensive simulations, try to reproduce the phenoma in a finite discrete cartesian representation of the space. A more finer discretisation involves huge amount of computation that could easily take months to complete (if everything goes well!). Thus, a big hope is in HPC advances to provide fastest computing systems (parallel machines and algorithms).