The authors present a formalism for the specification and analysis of the timing properties of distributed real-time systems. This formalism is based on the real-time logic of F. Jahanian and A. Mok (1986) and it inco...
详细信息
The authors present a formalism for the specification and analysis of the timing properties of distributed real-time systems. This formalism is based on the real-time logic of F. Jahanian and A. Mok (1986) and it incorporates multiple occurrence functions to take care of the multiple unsynchronized clocks in a distributed system. This is a three-level approach to formal specification and verification of the timing properties of a system. In the first level of specification, the system is described in an event-action model. In the second level, this specification is mechanically transformed into a set of DRTL formulas for carrying out the safety analysis in the next level. DRTL is a first-order logic. The fundamental constraints that a distributed real-time system needs to satisfy for the correctness of any formal reasoning about its timing properties are investigated.< >
This paper discusses studies on the performance of a parallel iterative algorithm implemented on an array of transputers connected in a mesh configuration. The iterative algorithm under consideration is the finite dif...
详细信息
This paper discusses studies on the performance of a parallel iterative algorithm implemented on an array of transputers connected in a mesh configuration. The iterative algorithm under consideration is the finite difference method for the solution of partial differential equations. Analytical expressions for the execution times of the various steps of the algorithm are derived by studying its computation and communication characteristics. These expressions are validated by comparing the theoretical results of the performance with the experimental values obtained on a transputer array. Then the analytical model is used to estimate the performance of the algorithm for varying number of transputers in the array and for varying grid sizes. An important objective of this paper is to study the influence of the convergence detection overhead on the performance of the algorithm. We present an approach to minimize the overhead. Convergence detection is one of the dominant factors that affects the performance of the algorithm, since it involves a substantial amount of computation and communication. In order to reduce this overhead, the proposed algorithm checks convergence once in every certain number of iterations, k c . The method of determining an optimal value of k c is given. Further, the time taken for convergence detection is estimated for the best case, worst case, and average case situations.
This paper discusses the parallel implementation of a hypercube-based circuit partitioning scheme. The circuit partitioner is based on a simulated annealing algorithm and is designed to provide near optimal circuit pa...
详细信息
This paper discusses the parallel implementation of a hypercube-based circuit partitioning scheme. The circuit partitioner is based on a simulated annealing algorithm and is designed to provide near optimal circuit partitions for simulating the circuits on a hypercube architecture. The circuit partitioning scheme optimizes multiple criteria such as tight coupling of nodes within a subcircuit, load balancing among processors and communication overheads. Design of a partitioner that obtains near optimal solutions satisfying such multiple criteria is difficult using any simple heuristic techniques other than simulated annealing.
The importance of circuit simulation in the design of VLSI circuits has channelised research work in the direction of finding methods to speedup this highly compute-intensive problem. On one hand, attempts have been m...
详细信息
The importance of circuit simulation in the design of VLSI circuits has channelised research work in the direction of finding methods to speedup this highly compute-intensive problem. On one hand, attempts have been made to find better algorithms and use faster hardware; and on the other hand, to use parallel architectures for accelerating the circuit simulation task. In this paper, we examine the various issues involved in parallelizing two well-known circuit simulation approaches – direct methods and relaxation methods. A number of parallel computer architectures which have been used for this purpose are also surveyed.
Circuit simulation is a highly compute-intensive task as it involves solving thousands of ordinary differential equations (ODEs) describing the VLSI circuit under consideration. This paper describes an effort towards ...
详细信息
Circuit simulation is a highly compute-intensive task as it involves solving thousands of ordinary differential equations (ODEs) describing the VLSI circuit under consideration. This paper describes an effort towards speeding up this task using a hypercube-based architecture. The paper focusses on the design and development of HIRECS (Hypercube Implementation of RElaxation-Based Circuit Simulation). HIRECS is based on the relaxation approach of solving the ODEs describing the circuit. The natural decomposition of the problem makes the relaxation algorithms amenable to parallel implementation. HIRECS employs the Waveform Relaxation (WR) algorithm. The special feature of WR algorithm is that the latency of the circuit can be exploited better, effecting a saving in the total computation time. The concept of ’windowing’ has been incorporated in HIRECS to effect a saving in the memory requirement. Another important feature of HIRECS is a novel synchronization scheme called partial synchronization. HIRECS runs on a DEC-1090 system and is developed using SIMULA. Performance studies of HIRECS based on parameters such as speedup, efficiency, and utilization of processors have been carried out. The performance evaluation of HIRECS in the simulation of some bench mark circuits like inverter chains and multiplexers indicates that a significant speedup, almost linear, can be obtained using a hypercube. For circuits with large number of nodes, such an implementation can result in tremendous saving in the computation time.
暂无评论