Reconfigurable elements in the design and validation of multiprocessors (ACCUSE)

Sponsors:

Hungarian-German Bilateral Scientific and Technology Development Cooperation Agreement

Period:

1997-1999

Participants:

Department of Computer Structures, University of Erlangen, Germany
Department of Measurement and Information Systems, Budapest University of Technology and Economics, Hungary

Project aim:

Different abstract mathematical models, like dataflow networks, Petri-nets, process algebra are used in the
functional and dependability validation of digital systems. These modeling paradigms share the very same key problem of state reachability analysis for instance to decide, whether a system will enter into an unsafe state.
Potential performance bottlenecks in the handling of large scale systems during the verification can be identified. Monoprocessor algorithms require either radical model (over) simplifications or long run times in the case of complex target systems.
Although the computational power of modern computing equipment increases rapidly even accompanied by a radical drop in the price/performance ratio, the huge processing capacity is insufficient for many practical applications.
The traditional solutions to overcome this performance bottleneck can be grouped into the following typical categories:

• In multiprocessors the task to be performed is distributed between different general purpose processing elements according to a structural or functional problem decomposition (e.g. massively parallel and distributed systems).

• Co-processors are application dependent dedicated hardware subunits performing some elementary operations typically by about one order of magnitude faster, than a program running on the CPU itself. These co-processors offer an efficient solution, if the dominating portion of the computations in the particular application consists of some simple, but frequently executed operations with a high data locality.

• Another promising, but still unexplored possibility is the use of accelerators, which are well-proven solutions in hardware emulation. In contrary to the co-processor approach, where only some parts of the algorithm are mapped to silicon, in accelerators some complete parts of the problem are realized on the FPGA. This way, additionally to a part of the solution algorithm, some data structures corresponding to the actual data are realized on the FPGA as well. Note, that a basic requirement for the use of the accelerator principle is, that the actual data have to be known at the time of configuration generation additionally to the solution algorithm. This way the estimation of the FPGA configuration needs the data parameters of the actual task as well.

All of the above mentioned solution alternatives are favorite candidates for the use in modeling and validation of digital systems, as the underlying mathematical models are hierarchically composed of very simple components like transition and places in Petri-nets.

These technologies are examined in the framework of the projects. The results are compared against those with the realization by mono- and multiprocessor systems.

Publications:

I. Majzik, Gy. Csertán, A. Pataricza, and S. C. Allmaier.
Support of Formal Verification by FPGA Based Accelerators.
Technical report 5-1997, IMMD3, University of Erlangen, Germany, 1997.

G. Héja and I. Majzik.
Design of an XC6216 based watch-dog processor.
In Proc. Scientific Conference for Students, Technical University of Budapest, 1997.

S. C. Allmaier, Gy. Csertán, S. Dalibor, and D. Kreische.
Parallel Reachability Graph Generation in Stochastic Modeling on Shared and Distributed Memory Multiprocessors.
Technical report 4-1997, IMMD3, University of Erlangen, Germany, 1997.

S. C. Allmaier, S. Dalibor, and D. Kreische.
Parallel Graph Generation Algorithms for Shared and Distributed Memory Machines.
In Proc. Parallel Computing Conference ParCo'97, Bonn, Germany, 1997.

Gy. Csertán, I. Majzik, A. Pataricza, and S. C. Allmaier.
Reachabiliy Analysis of Petri-nets by FPGA Based Accelerators.
In Proceedings of Design and Diagnostics of Elecronic Circuits and Systems Workshop, DDECS98
pages 307-312, Szczyrk, Poland, 1998.

Gy. Csertán, I. Majzik, A. Pataricza, S. C. Allmaier, and W. Hohl.
Harware Accelerators for Petri-net Analysis.
In Proceedings of Distributed and Parallel Systems, DAPSYS98, pages 99--104, Budapest, Hungary, 1998.

S. Allmaier and D. Kreische.
Parallel Approaches to the Numerical Transient Analysis of Stochastic Reward Nets.
In Application and Theory of Petri Nets 1999, S. Donatelli and J. Kleijn (editors), Springer, LNCS 1639, 1999.

S. Allmaier.
Parallele Lösungen für die Stochastische Modellierung.
PhD. Thesis, IMMD3, University of Erlangen, Germany, 1999. (In German)

Further information:

András Pataricza, Ph.D.