Contribution à la synthèse des réseaux systoliques
Jean‐Frédéric Myoupo · HAL (Le Centre pour la Communication Scientifique Directe) · 1994
The concept of synchronous architecture was introduced in 1978 by H.T. Kung and C.E. Leiserson with the aim of accelerating the processing of computationally intensive problems. Informally, the authors define a synchronous architecture as a network of specialized processors, locally interconnected and operating in synchronous mode. Their idea is to use this architecture as a peripheral of a conventional host computer. Each cell receives data from its neighbors, performs a simple computation, and then in turn transmits the results to the neighboring cells, one cycle time later. The synchronous model has proven to be a very effective tool for the design of specialized integrated processors. The development of integrated circuits has made it possible to realize low-cost integrated circuits. Consequently, one can, at little cost, design a synchronous architecture intended for a well-defined application. Thus, unlike general-purpose parallel machines, the synchronous model takes advantage of the characteristics of the problems for which it was designed. Therefore, good performances can be achieved. In a synchronous machine, the nodes operate in synchronous mode, in the sense that they evolve in parallel (massive parallelism) under the control of a global clock. This facilitates the implementation of communication protocols. The same data can be transformed several times within the network without being read as many times by the latter. This mode of operation minimizes memory accesses which constitute a bottleneck for machines based on the Von Neumann principle. Moreover, the problems which lend themselves well to the synchronous approach are those which require repetitive treatments on the same variable (regularity principle). Such problems induce networks in which the number of calculations largely takes precedence over that of communications with the host. A synchronous network is modular if the execution time and the number of cells are its only characteristics which depend on the size of the problem. This modularity character is very important because, by keeping the same structure for the basic cell, we can build networks for problems of any size. Our Habilitation thesis presents the various works and promising results that we have obtained in fields of applications including numerical applications and signal processing (matrix arithmetic, dynamic programming, etc., ...) and non-numerical applications (data structures, graphs and geometric algorithms, manipulation of character strings, polynomial algebra, etc., ...).