### Contribution a l'algorithmique des architectures paralleles : des reseaux point-a-point aux reseaux optiques.

**By:**Pascal Berthome**Number:**PhD1995-01**Date:**January 20, 1995**Abstract:**

- We have studied first, fundamental problems on point-to-point interconnection networks based on Cayley graphs. Tight bounds for some simple problems have not yet been found on some parallel architectures. For example, the time complexity for sorting on hypercubic networks is still an open problem. We have proposed several algorithms for solving problems based on selection on hypercubic networks using the fastest known sorting algorithms. We have also studied several decompositions for Cayley graphs, leading to global communication algorithms that are simple and efficient, such as broadcasting and gossiping on the star graph. Secondly, we have studied networks based on optical interconnections. One of the major problems of point-to-point interconnection networks is the inefficiency of global communication. These operations are useful for a variety of applications. Optical interconnections allow denser networks with higher bandwidth than classical technologies. Using these networks, we have revisited several problems of parallelism. We have studied global communication problems. We also have given scalabilty results for optical networks.

**Keywords:**

- Parallelism, complexity, global communication, optical networks, scalability, selection.

**Availability:**Electronic copy only.**Size:**2+167p**Format:**Compressed PostScript- Get it

### Etude de l'impact des recouvrements calcul/communication sur des algorithmes parallèles de calcul matriciel.

**By:**Makan Pourzandi**Number:**PhD1995-02**Date:**January 1995**Abstract:**

- In this work, we study the overlapping of the communications by the computations and the possible improvements in the final performances of numerical applications. The developers of parallel applications usually consider these applications as separate phases of computation and communication. In this point of view, the only possible improvements are those on the communications or on the computations. The new parallel machines often have dedicated communication processors. In order to achieve the best performances on these machines, it is necessary to overlap the communications by the computations. This allows the use of the computation time to perform the communications simultaneously. This approach gives us a better view of the real performances of our parallel code. This way, one can design the more efficient algorithms by decreasing the communication cost. In this work, we study this approach for several parallel numerical applications : Gaussian elimination, the Jacobi method for finding the eigenvalues of a real symmetric matrix, matrix product. We show improvements in each case. Different approaches to the overlapping are developed. It is useful to design new algorithms which can fully take advantage of the characteristics of parallel machines. We explore a new method for finding the eigenvalues and eigenvectors of a real symmetric matrix. This method is not efficient in sequential but perform well for parallel machines. Finally, we use these different methods to improve the performances of a real parallel application of pollution simulation.

**Keywords:**

- Parallel Algorithms, Multiple Instruction, Multiple Data, Overlapping of Communication and computation, Jacobi Method, Gaussian Elimination, Stochastic Resolution of a Diffusion Equation.

**Availability:**Paper copy available.**Size:**192p**Format:**Compressed PostScript- Get it

### Synthese de preuves de programmes dans le Calcul des Constructions Inductives.

**By:**Catherine Parent**Number:**PhD1995-03**Date:**January 1995**Abstract:**

- This thesis deals with a special approach of functional programs certification. A mathematical constructive proof of a formula pointing out the existence of an object satisfying a given property can be interpreted as an effective method to construct this object. In this point of view, the specification of the program is represented by a logical formula. Developing a program then corresponds to prove this formula. In the state of the art, different methods exist to extract the computational part representing the program from a mathematical proof. The correctness of the program is then certified by construction. This thesis focuses on the problem of inverting the program extraction. Given a specification and a program, the problem is to reconstruct a proof of the specification which algorithmic contents corresponds to the given program. This problem is clearly undecidable. The best we can hope is to generate proof obligations on atomic parts of the program. Such obligations correspond to logical properties to be verified. Even this goal cannot be achieved. Indeed, the proof of the program needs in general to know about the intermediate properties of the subprograms. These ones can be stronger than the initial specification. First, this thesis studies a weak extraction of a program from a proof keeping track of intermediate specifications. From such a program, we prove the determinism of retrieving minimal proof obligations. Then, heuristic methods are proposed to retrieve the proof from a natural program containing only partial annotations. Finally, the thesis presents the implementation of this method as a tactical of the Coq proof assistant. Thanks to this implementation, we proved different examples such as sort programs.

**Keywords:**

- Lambda-calculus, Extraction, Proofs of Programs, Calculus of Constructions.

**Availability:**Electronic copy only.**Size:**2+114p**Format:**Compressed PostScript- Get it

### Utilisation des reseaux de neurones pour la telegestion des reseaux techniques urbains.

**By:**Pascal Bigot**Number:**PhD1995-04**Date:**January 1995**Abstract:**

- Neural networks are used for fault detection on a technical urban network. Methods to find an architecture and to build training samples are discussed. Then, we discuss the effects on generalisation capabilities when reducing the number of used parameter. In the last part, we study relationships between neural network and binary decision trees. This lead us to define learning algorithm with no fixed architecture.

**Keywords:**

- Neural Networks, Fault Detection, Learning Algorithms, Neural Trees.

**Availability:**Out of print. Not available by FTP.**Size:**2+116p

### Parallélisation automatique des programmes à contrôle dynamique.

**By:**Jean-Francois Collard**Number:**PhD1995-05**Date:**January 1995**Abstract:**

- Automatic parallelization of imperative programs has been focused on static control programs, i.e. on programs whose operations set and data dependences can be described precisely at compile-time. Typically, such programs consist of nests of {\tt FOR} (or {\tt DO}) loops. In this case, an elegant framework has been crafted during the last few years, based on the compile-time determination of schedules. The aim of this thesis is to extend this framework to programs whose control flow cannot be handled at compile-time. More precisely, this work is restricted to programs whose dynamic behavior is due to {\tt WHILE} loops and conditional statements. For such programs, the set of operations cannot be predicted, and data dependences cannot be known precisely. The first part of this thesis describes a novel data-flow analysis for dynamic control programs. Moreover, control dependences may hamper the parallelization process; in this case, speculative or eager execution can be brought into play. Thus, schedules have to manage the fuzziness of data dependences and possibly the speculative nature of some executions. Both issues are addressed in the second part. Eventually, Part III addresses (data-parallel) code generation.

**Keywords:**

- Automatic Parallelization, Dynamic Control, WHILE Loops, Dataflow Analysis, Scheduling, Code Generation.

**Availability:**Electronic copy only.**Size:**2+157p**Format:**Compressed PostScript- Get it

### Pavages et Graphes de Cayley Planaires.

**By:**Thomas Chaboud**Number:**PhD1995-06**Date:**February 1995**Abstract:**

- This PhD Thesis deals with planar Cayley graphs and tilings. The first two parts are introductory (Introduction, Chapter 1, and Definitions / Notation, Chapter 2). We then present a generalization of an algorithm by W. Thurston. In a planar graph, the dual of which is regular and bipartite, our algorithm tiles any finite and simply connected region by pairs of adjacent faces (dominoes), in linear time (Chapter 3). Thurston's result was restricted to the infinite square grid and the triangular network, using ideas from J. Conway and the fact that those lattices can be seen as Cayley graphs. In general, this property is not satisfied by graphs in which we obtained our extension to his algorithm. Thus, it is natural to ask which infinite planar graphs can be oriented and coloured so as to become Cayley graphs. We first solve that question for infinite, planar, locally finite graphs, the dual of which is regular, by giving a simple characterization on the graph's degree and codegree (Chapter 4). Then, we enlarge the scope of the tools we introduced in that part, applying them on any (Euclidean or hyperbolic) infinite, planar, locally finite graph. The resulting algorithm lists all the group presentations corresponding to the given graph, if any. Those associated with Euclidean (Archimedean) graphs are given in Annex. We also study several families of planar Cayley graphs that do not belong to the previous class (Chapter 5). Our last part provides an algorithm that, given a horizontally and vertically convex finite simply connected part of the square grid, decides whether it admits an optimal tiling by dominoes. That optimality has the following meaning : if the region is chessboard- like coloured, and if it contains, say, k more black squares than white squares, one cannot tile it leaving less than k squares uncovered. The tiling is optimal if exactly k cells remain uncovered (Chapter 6).

**Keywords:**

- Tilings, Cayley Graphs, Graphs, Algorithms, Combinatorics, Geometry, Complexity.

**Availability:**Electronic copy only.**Size:**2+137p**Format:**Compressed PostScript- Get it

### Conception et analyse d'algorithmes paralleles pour les reseaux neuronaux de kohonen et de fonctions a base radiale (RBF).

**By:**Vladimir Demian**Number:**PhD1995-07**Date:**July 1995**Abstract:**

- In this thesis, we study the design and the implementation of parallel learning algorithms for neural network. Our target machines are MIMD parallel computers. We were particularly interested in two neural networks: Kohonen and RBF models. In the first part of this work, we describe the different parallel tools used. In the next two parts, we explain our parallel implementations of two neural network algorithms : Kohonen and RBF. In the last part, we compare three different implementations, to predict the pollution in industrial environment. In the first part, we compare the different parallel machines used in our implementation: iPSC/860 and Paragon. The different communication and computation libraries are described; these libraries allow to have better efficiencies and portability. In the second part, we explain how implementing Kohonen algorithm on iPSC/860. It includes three chapters. The first presents a general approach to the problem. In the second one, we describe the first parallel implementation with an optimal mapping of the neurons to the target machine. In a last one, we present a new learning algorithm ``Parallel Block Algorithm'' which allows a better adaptation of Kohonen algorithm to the parallel SIMD and MIMD architecture. The third part gathers our different works on parallel implementations of OLS learning algorithm for RBF neural networks. The first chapter describes the RBF neural networks and OLS learning algorithm. The remaining of this part is dedicated to the adaptation of there algorithm to the Intel Paragon and a heterogeneous network of workstations using PVM. We first implement a ``direct'' parallel algorithm which allows us to implement a new parallel version with O(N$^3$) complexity instead of the O(N$^4$) of the ``direct'' version. Defining our strategy to achieve dynamic load balancing, we improve significantly the performances of our implementation. In the fourth part, we use neural networks to predict pollution on industrial environment. Finally, we present our results using the two neural networks described allow: RBF and Kohonen. We compare the results obtained using these two networks with the one obtained by the statistics methods.

**Keywords:**

- Neural Network, Kohonen, RBF, IPSC/860, Paragon.

**Availability:**Paper copy available.**Size:**155p**Format:**Compressed PostScript- Get it

### Semantique des langages a parallelisme de donnees. Applications a la validation et a la compilation.

**By:**Gil Utard**Number:**PhD1995-08**Date:**December 1995**Abstract:**

- This thesis is divided in three parts. First part is the validation of data-parallel application. Second part is the validation of a compilation scheme. The third part is the study and implementation of an automatic load balancing mechanism at the run time of data-parallel programs. In the first part, we define an axiomatic semantics for a small data-parallel language, called L. This semantics allows us to define a proof system for data-parallel programs. We prove its non-trivial completness. We extend this semantics to complex control structure which can be find in real languages. In the second part, we formally prove a compilation optimisation of data-parallel iteration in the language DPC. The proof is done by an extension of axiomatic semantics of usual parallel languages. This leads to a new methodologie in the development of parallel programs. In the third part, we show an implementation of dynamic load balancing mechanism in data-parallel program compiled by virtualization. The main mechanism is virtual processor migration. We show a prototype of C* for network of workstations with PVM.

**Keywords:**

- Parallelism, Data-parallelism, Languages, Semantics, Proof of Programs, Hoare Logics, Compilation, Dynamics Load Balancing.

**Availability:**Paper copy available.**Size:**141p**Format:**Compressed PostScript- Get it