LEDA projects

Laboratory for Electronic Design Automation


See-Grid 2 project

Introduction

The gradual deployment of broadband networks throughout the research community and the fact that network capacity grows with much greater rate than CPU power and storage capacity (Moore's Law vs. storage improvements vs. optical improvements) have led to the creation of a distributing environment for sharing resources known as the Grid paradigm. This integrated networking & middleware environment is also called eInfrastructure. The technologies of the Grid-enabled eInfrastructure, which are being developed around the world, allow new methods of global collaborative research - often referred to as eScience.

SEE-GRID intends to provide specific support actions to pave the way towards the participation of the SE European countries to the Pan-European and worldwide Grid initiatives.

SEE-GRID-2 partnership consists of 13 contractors representing 11 SEE countries

 

Grid Infrastructure

Partnership includes

  • EU member-states (Greece, Hungary, Bulgaria, Romania)
  • Candidate Countries (Croatia, Turkey)
  • Third Countries - Western Balkans (Albania, Bosnia-Herzegovina, Former Yugoslav Republic of Macedonia, Serbia, Montenegro)
  • European Neighborhood Policy countries (Moldova)

Planned Start date:    01/05/2006

Planned Duration: 24 months

Planned Total Budget: 2,002,691 €

 

By using participation in EGEE as reference for a partner’s maturity, three layers can be identified:

LEDA contribution

LEDA is responsible for AEGIS03-ELEF-LEDA site, a part of Academic and Educational Grid Initiative of Serbia (AEGIS). The site is installed in January 2006, and it has been successfully operating as a part of SEE-GRID and AEGIS infrastructure.

The application pAless (Parallel Analogue and Logic Electronic Simulation System) is under the development within the SEE-GRID-2 project. pAless is a grid-enabled, parallel analogue and logic electronic circuits and systems simulator. It enables simulation of electronic circuits and systems characterized as large scale, mixed signal, and mixed mode including non-electrical components and phenomena. The simulation of such circuits and systems is memory and computationally intensive, time consuming process suitable for execution on grid.

About the Grid

The development of low-cost personal computers with high computing power and gigabit LAN network connections in past decade, provided possibility for implementation of inexpensive distributed multiprocessor systems such as clusters (Fig. 1).

BeowulfCluster.jpg
Fig. 1 Organization of the computer cluster

A cluster has many advantages over classic super-computer: it is inexpensive, flexible, easy to use, easy for maintenance and highly stackable. The total price of computer cluster is more than ten times lower then dedicated supercomputer with similar computing power, and after amortization cluster nodes can be used as single personal computers. It usually uses open-source operating system, well documented and well known to programmers and system administrators. A cluster is also highly stackable: it can be easily extended by adding additional node or demoted by subtracting one. One particular version of this approach, involving open source system software and dedicated networks, has acquired the name “Beowulf”.

The development of Internet and WAN links of great capacity led to a new paradigm: the computational grid. The intention was to associate to the electrical power grid. In the same way electrical power could be obtained from power grid, computational power should be obtained on demand from a network of providers, potentially belonging to the en-tire Internet. In the beginning, this paradigm has been strictly scientific and academic; but as the Internet, it became widely accepted and popular. One of the most common definitions says that a computational grid is a hardware and software infrastructure that provides dependable, consistent, pervasive, and inexpensive access to high-end computational capabilities providing on-demand access to computing, data, and services. Basically, grid computing intends to provide access to resources using wide area connections; it can be determined as cooperation of geographically distributed computer systems (clusters) where user jobs can be executed.

The hardware part of computational grid infrastructure can be extremely heterogeneous. It consists of a number of clusters containing various number and types of processors, amounts of memory, LAN and WAN connectivity and mass-storage capacity.

The role of the software components is to provide distributed services for job submission and management, file transfer, database access, data management and monitoring. They also ensure security in multiuser environment using certificates. The software part consists of two layers: operating system and middleware.

Greed Services schematic display
Fig. 2. Grid services

Grid computing is suitable for intensive calculations that require significant processing power, large operating memory and throughput, as well as storage capacity. The simulations of integrated electronic circuits are paradigmatic example of these calculations.

With the rapid growth of electronic systems complexity, the simulation became a crucial step in design flow. Circuit simulation has proven to be one of the most important computer aided design (CAD) methods for the analysis and validation of integrated circuit design.

The Parallel Simulator

Today’s high end integrated circuits contain both analogue and digital components. In addition, non-electric elements are implemented within the electric integrated circuits, e.g. in microelectromechanical systems (MEMS). Complexity of modern electronic circuits has imposed the requirement for enabling the hardware designer to model a design at different levels of abstraction. All these trends have resulted in the development of the mixed-mode simulation domain. This paradigm includes mixed-signal (analogue and digital), mixed domain (electrical and non-electrical) and mixed-level simulation. Obviously, this introduces unique difficulties for the modeler and simulation developer.

In order to simulate a system, it has to be described i.e. modeled. Mixed-mode systems are described using:

1. algebraic equations

2. ordinary differential equations (ODE)

3. partial differential equations (PDE)

4. algorithms

5. logic states

Let us assume that PDEs describe mechanical part of the system. In order to obtain set of ordinary differential equations, space discretization of PDEs is performed, where the system unknowns are the spatial displacements as functions of time. Thus, PDEs introduce new sets of ODEs, whose number is large, depending on a discretization grid.

Thus, one comes down to the problem of formulation and solution of systems of nonlinear algebraic equations, that are to be solved iteratively – with the help of linearization i.e. by application of Newton methods. Evaluation of all derivatives that are necessary for the linearization is the most time consuming part of the simulation process.

So far we have considered analogue/continuous models. Algorithmic description may define behaviour of continuous (analogue, pulse…) as well as for discrete (logic expressions, tables, programs) models. This kind of model’s behaviour description needs to be translated into other kinds of description.

Discrete-event processes define the behaviour of the discrete-event model described by the logic states. The simulation mechanism for discrete-event simulation differs from continuous time simulation. It involves the use of future event tables, containing the information of events to be processed.

In mixed-signal systems, a specific time advancement algorithm has to be implemented in order to synchronize e-vents between analogue and logic part. In addition, specific algorithms are to be implemented in order to convert signals at the digital – analogue meeting points.

To conclude this brief overview of modern simulation techniques, we would like to emphasize that, according to the presented facts, simulation process may be characterized as memory intensive, computationally intensive and algorithmically complex. This leads to long simulation runtimes. Having in mind that every design needs many simulation runs of the same system in order to get optimal solutions with respect to many different requirements, it is obvious that long simulation runtimes lead to delay in design process. One possibility to reduce these runtimes is to divide the circuit into several partitions and to simulate the partitions in parallel.

Barriers to the widespread use of parallelism are in all three of the usual large subdivisions of computing: hardware, algorithms and software. As for the hardware, intercommunication networks that keep up with speed of advanced single processors are still not available. The biggest obstacle is inadequate software. Compilers that automatically parallelize sequential algorithms remain limited in their applicability. Best performance is still obtained when programmer himself supplies the parallel algorithm.

There are number of parallel computational models in use today, such as: data parallelism, shared memory, message-passing, remote memory operations, threads and various combined models.

In our research we focus on message passing model of parallel computation, and in particular the Message Passing Interface (MPI) instantiation of that model. The message-passing model uses a set of processes that have only local memory but are able to communicate with other processes by sending and receiving messages. It is a defining feature of the message-passing model that data transfer from the local memory of one process to the local memory of another requires operations to be performed by both processes. MPI is being widely used and is expected to be around for a long time due to its advantages over other models, which are: universality (it matches the hardware of most today’s parallel supercomputers), expressivity (it is a useful and complete model in which to express parallel algorithms), ease of debugging, and performance. Message passing has become a standard for portability, in both syntax and semantic. The MPI standard was completed in 1997.

During the first phase of the simulator parallelization, we parallelized equation formulation for analogue circuits described by nonlinear ODEs. Also, the appropriate algorithm for parallel solution of the system of linear equations will be included in the parallel simulator as the first next step in further development.

Improvements in parallel simulation of systems modelled by partial differential equations, parallel discrete-event as well as parallel mixed-signal simulation will be implemented in the future versions of the parallel simulator. Also, it will be enabled to perform parallel simulations on the computational grid.

Based upon these principles, in LEDA has been developed pAless - Parallel Analog and Logic Electronic Simulation System, which is a natural extension of previously developed non-parallel simulator Alecsis.