Overview of some of my research topics

Dr. Claude
Tadonki, HPC researcher

Ecole des Mines de Paris - Centre de Recherche en Informatique (Fontainebleau)

**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

**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

- the emergence of embedded systems.
- the large number of mobile systems that need to provide services with the energy releasable by a battery of limited weight and size;
- the technical feasibility of high-performance computation due to heat extraction;
- concerns about the operating costs of large systems caused by electric power consumption.
- new technology features for explicit power management.

**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).