Abstract

Dynamic Topology in Distributed Logic Simulation of Digital Systems

Introduction
Review of researches and developments
Main results
1. Research of algorithms for distributed simulation
2. Classification of methods for load balancing in distributed logic simulation
3. Development of the architecture of computer network
4. Development of software system
Conclusions
References

Introduction

1. Relevance

   Digital systems are widely used in various industries, production and management. An important step in digital systems design is the simulating of its behavior. Simulation of large dimension and complex circuits requires enormous expenditures of computing resources. Increased productivity of simulation system can be obtained by using of several computers connected with a network. Simulated system is partitioned into parts, each of which is simulated on a separate computer. The communication channels and simulation processors might not be permanent in some computer networks. Therefore, allowing the distributed logic simulation system to working a computer network with a dynamic topology is relevant.

2. The research goals and tasks

   The research object are methods and algorithms for a dynamic change of the topology of processor graph in distributed simulation systems.

   The research subject is optimal structure and properties of the computer network for distributed logic simulation of digital systems with dynamic topology of processor graph.

   The research goal is organization of computer networks with unreliable processors for distributed logic simulation by using algorithms for a dynamic change of the topology of processors graph.

   The research tasks:

• research of synchronization algorithms for distributed logic simulation of digital systems;
• research and classification of existing methods for load balancing and dynamic topology change of processor graph in a distributed logic simulation system;
• research of a computer network architecture for distributed logic simulation of digital systems;
• development of a program system for distributed logic simulation of digital systems in computer networks with unreliable nodes and communication channels.

3. Probable scientific innovation:

• a new classification method of load balancing is obtained;
• a new modification of algorithm of load balancing based on the use of spheres of influence to dynamically change the processors graph is proposed. This modification allows to increase the speed simulation process by 10%.

4. The practical significance:

The developed program system for distributed logic simulation of digital systems in the computer network allows speeding up the processes of automated design of digital systems by using more computational resources.

Review of researches and developments

   Simulation of systems used at design of many devices. In DonNTU developments related to distributed simulation, produce Skobtsov Y.A., Feldman L.P., Ladyzhenskii Y. V. Also, issues related to distributed logical simulation deals Ph.D. Popoff Y.V.

   In Ukraine simulation of as a scientific direction was investigated at the Institute of Cybernetics of the Academy of Sciences of the USSR Glushkov V.M.

   The researches in the world began in the 70's – 80's XX century. Research conducted next scientists: Chandy K. M., Misra J.,Bryant R.E., Jefferson D., Fersha A., Fujimoto R.M.

Main results

1. Research of algorithms for distributed simulation

   Changes in the simulation system are events. The current values in all nodes of the circuit are states in a given moment of virtual time. The simulation process is performed in a discrete virtual time [1,5,6]. Simulation algorithms are distinguished with order of processing and planning of new events [6] (see Fig. 1).

Figure 1. The classification of simulation algorithms

   A sequential simulation is performed on a single computer. Events are processed one by one order their occurrence in virtual time. A simulation of large systems required large computing resources [2]. The simulation can be accelerated by using of parallel and distributed computing systems. In the very best case simulation on the n computers allows to speed up the simulation process by n times [4].

   When parallel process simulation acceleration is achieved by ensuring that parts algorithm simulation are executed in parallel [1]. In a distributed process simulation using multiple computers connected to the area network. Simulated system is cut into the parts, each of which is modeling on a single computer or simulation processor (SimProc) [3]. With this method of simulation is important to preserve the relationship among parts of the system and synchronization of SimProc [7]. The simplest method synchronizing is to use global virtual time. This algorithm of a distributed simulation is called synchronous [2,5]. At asynchronous simulation algorithm, each SimProc is performed in its local virtual time LVT. Since the LVT is different for all SimProc, the system can be an event whose implementation is impossible. An important stage at organization of a distributed simulation system is the organization of correct processing of events in time [1].

   Conservative simulation algorithm implements events in chronological order [1]. At optimistic algorithms SimProc do not expect permission to the processing of events. Permissible is the emergence of events in the local virtual past, for that system is rolled back to its previous state [2]. SimProc not have to wait for each other [1,3].

2. Classification of methods for load balancing in distributed logic simulation

   Classification of methods for load balancing is shown in Figure 2. When using the static load balancing does not take into account features that significantly affect the overall execution time modeling: changes in the computing environment, changes in available computing power [10].

Figure 2. Classification of methods for load balancing

   For accelerating simulation is necessary to use a dynamic load balancing based on the calculation of the parameters used to decide whether a topology changes. A combined load balancing consists of prior analysis of the simulated system and the load control mechanism [9].

   Changes in the topology on the physical level are the movement of parts of the modeled system with an LP to other. Application of the method described in [9,10]. The structure of the distributed simulation system Triad.Net shown in Figure 3.

Figure 3. Structure of Triad.Net

   In [10] proposed two methods to accelerate the simulation process are: using multiple clusters per simulation process and dynamic load balancing (see Figure 4).

Figure 4. Multiple clusters per simulation process

   Changes in the topology on the logical level are used in the approach described in [8]. In this method, each logical processor performs a simulation of the system in its sphere of influence. Spheres of influence controlled special communication logical processors (CLP). Communications among the LP is missing; information between them can only be transferred through the corresponding CLP.

   Changes in the topology on the logical level are used in the approach described in [8]. In this method, each logical processor performs a simulation of the system in its sphere of influence. Spheres of influence controlled special communication logical processors (CLP). Communications among the LP is missing; information between them can only be transferred through the corresponding CLP.

   As simulation progresses, the CLP performs a dynamic analysis of the pattern and frequency of state accesses and computes an approximation of the agents’spheres of influence. If the load increases to the point that the CLP becomes a bottleneck (e.g., when message traffic exceeds a predefined threshold), the CLP creates one or more new CLPs, to which it assigns those disjoint subsets of the state variables that form the least elements in its approximation of the partial order over the spheres of influence [9]. Those groups of LPs whose events and actions have formulated the new CLP(s) communicate directly with the corresponding new CLP. The process then repeats with the newly created CLP(s) monitoring the load and generating additional CLPs as required to keep the overall simulation load on the CLPs within bounds [8].

   The rank of a variable vj for process pi over the interval [t1; t2], r(vj; pi; [t1; t2]) is the number of events in whose sphere of influence vj lies. The cost of accessing a variable vj for a logical process pi as the rank of vj for pi, r(vj; pi), times the number of CLPs which must be traversed to reach vj during the interval [t1; t2], l(vj; pi), i.e., the cost of accessing variables in the local CLP is 0 [8].

   Then the cost to an LP pi of accessing all the variables in its sphere of influence s(LPi) is (see Formula 1) [8]:

(1)

   The total access cost for all LPs LP1, LP2, .. LPn of a particular decomposition over the interval [t1; t2] is [8]:

(2)

   The optimal decomposition over the interval [t1; t2] is one which minimizes the total access cost [8].

   Load control mechanism is characteristic of dynamic load balancing, and is described in [10]. It is implemented as an algorithm in the global control process (see Figure 5).

Figure 5. Load control mechanism

   In the simulation process calculates certain measurements [10]: virtual time progress and break-even time.

3. Development of the architecture of computer network

   Simulation is performed using several processors, joint in a computer network (see Figure 3).

   The developed system uses a modification of the method proposed in [8] approach to organization modeling system based on spheres of influence management. Simulated system is a class of digital logic circuits.

   In the simulation system exists:

• Process Administrator;
• Logical Processors (LP);
• Communication Logical Processors (CLP).

   Process Administrator intended for control the placement of modeling tasks to simulation processors (LP and CLP) and registration are available for simulation processors.

   Logical processors to simulate part of the circuit within their sphere of influence. LP contains the event list (EVL), virtual clock (VT), structural-functional scheme model (SFSM) and the list of nodes that it must simulate (a sphere of influence).

   Structure of the simulation system is shown in Figure 6.

Figure 6. Simulation process with partitioning

   Structure of simulation system is shown in Figure 7.

Figure 7. Structure of simulation system

   The decision to change the topology of the modeling system is taken under parameters proposed in [2] and described in Section 3.2. Those groups of LPs whose events and actions have formulated the new CLP(s) communicate directly with the corresponding new CLP. The process then repeats with the newly created CLP(s) monitoring the load and generating additional CLPs as required to keep the overall simulation load on the CLPs within bounds (Figure 8).

Figure 8. Redistribution the tree of CLPs

(animation: 7 cadrs, 7 cycles, delay 0,3 s; size 13 K; Adobe Photoshop CS3)

4. Development of software system

   Define the basic requirements for the system as a use case diagrams (see Figure 9).

Figure 9. Use case diagram

   Artists in the system can perform a series of actions designed in the form of precedents. In general operation of the system is reduced to the transmission and receiving of messages of various types.

   We see the class diagram in Figure 10.

Figure 10. Class Diagram

   The class diagram shows the structure of simulating processors in the system (LP and CLP). Communication logical processor contains information about the subordinate processors in an array of structures FProcessors. This information is updated depending on changes in the number of processors available in the method UpdateProcessors. Also under his methods is collecting data on current levels of exchange messaging slave processors.

Conclusions

   A new solution of the actual problems simulation of digital systems in a distributed computing network with dynamic topology, unreliable processors and communication channels is obtained in the master’s work.

   The results of the research:

1. A new classification of methods of load balancing in distribution system logic simulation is obtained.
2. The loading criterions are researched. These criterions base of the change in topology of simulation system.
3. A new method to organize computing network for distributed logic simulation is proposed. This method uses spheres of influence management and communication the logical processors.
4. The method to organize a computer network is used in a practical implementation of the system for distributed logic simulation.

   It is planned to conduct experimental and theoretical research of the properties of a computer networks in the future.

References

1. Ладыженский Ю.В., Попов Ю.В. Программная система для исследования протоколов синхронизации при распределенном событийном логическом моделировании // Материалы научно-практической конференции «Современные технологии проектирования систем на микросхемах программируемой логики».– Харьков: Харьковский национальный университет радиоэлектроники, 2003. – С.44.
2. Ладыженский Ю.В., Попов Ю.В. Система распределенного логического моделирования цифровых устройств с использованием консервативного протокола синхронизации // Наукові праці Донецького національного технічного університету. Серія: інформатика, кібернетика та обчислювальна техніка, випуск 39: – Донецьк: ДонНТУ, 2002.– c. 21-29.
3. Ладыженский Ю.В., Попов Ю.В. Объектно-ориентированная модель протоколов синхронизации при распределенном логическом моделировании цифровых устройств // Наукові праці Донецького національного технічного університету. Серія: Обчислювальна техніка та автоматизація. Випуск 64 – Донецьк: Вид-во ДонНТУ, 2003.– c. 212-221.
4. Fujimoto R.M. Parallel and distributed simulation systems // Winter Simulation Conference 2001.– Arlington, VA, USA: ACM, 2001.– p.147-157.
5. Fersha A. Parallel and Distributed Simulation of Discrete Event Systems // Hardbound of Parallel and Distributed Computing.– McGraw-Hill, 1995.
6. Jefferson D.R. Virtual time //USC Tech. rep. TR-83-213.– Los Angeles: Univ. of Southern California.– 1983.
7. Chandy K.M., Misra J. Asynchronous distributed simulation via a sequence of parallel computations // Communications of The ACM – CACM, vol. 24, no. 4, pp. 198-206, 1981.
8. Theodoropoulos G., Logan B. An approach to interest management and dynamic load balancing in distributed simulation // 2001 European Simulation Interoperability Workshop.– London: University of Westminster, 2001.– p.566-571.
9. Миков А.И., Замятина Е.Б., Осмехин К.А. Метод динамической балансировки процессов имитационного моделирования // Материалы Всероссийской научно-технической конференции «Методы и средства обработки информации МСО-2005».– Москва: МГУ, 2005.– с.472–478.
10. Schlagenhaft R., Ruhwandl M., Sporrer C., Bauer H. Dynamic load balancing of a multi-cluster simulator on a network of workstations // 9th Workshop on Parallel and Distributed Simulation.– New York: Parallel and Distributed Simulation, Workshop on, 1995.– p. 175-180.

Important note

   The master's work is not completed yet. Final completion is on December 1, 2011. Full work text and subject materials can be obtained from the author or her adviser after this date.

Copyright © Baluta Angelika, DonNTU, 2011