W2A-031 High frequency circuits-0.txt
AN OVERVIEW OF THE HIGH FREQUENCY CIRCUIT MODELLING USING CONCURRENT PROCESSING TECHNIQUES in: Silvester, P. P., "Software Applications in Electrical Engineering", Montreal: McGill University, 1993.

V.F. Fusco

Microwave Research Group, Department of Electrical and Electronic Engineering, The Queen's University of Belfast, Belfast, BT9 5AH, UK

ABSTRACT

In modern high frequency electronic design there is often a requirement for interactive CAE tools. The result of the ever increasing demands placed on these tools is that the cpu time required for circuit analysis is often prohibitively long. This paper presents a review of some of the methodologies involving parallel computing techniques that are employed for the solution of CPU intensive high frequency electromagnetic field and circuit problems. The limitations and advantages of these techniques are discussed.

INTRODUCTION

In modern high frequency electronic circuit design problems there is often a requirement for interactive CAE tools. This is increasingly important as circuit functionality or technological implementation becomes more complex. This is particularly true for monolithic microwave integrated circuit, MMIC, design, where the complex parasitic interaction between components has a first order effect on the quantitative prediction of circuit behaviour by computer simulation. The result of the increased demands placed on CAE software by such applications is such that the cpu time required for circuit analysis is often prohibitively long. One way of overcoming this problem is to reduce the total elapsed simulation time by partitioning the computational load through the combined use of CPU efficient concurrent computing algorithms and multiprocessor hardware. This paper presents a review of the application potential that exists for concurrent processing for the solution of typical design problems that are encountered at RF and microwave frequencies.

For example many problems in the area of electromagnetics can be considered as follows: i.a pre-processing stage; where the problem geometry is defined ii. a matrix fill stage; here the mathematical relationships governing individual matrix elements are computed iii. a solve stage; where the primary field elements of interest are computed iv. a postprocessing stage; where secondary field parameters are generated and presentation of data occurs.

As the requirement for more detail in the computer simulation, for example in monolithic microwave integrated circuit design [l] becomes more important or as circuit complexity increases then it is essential that more than one analysis per design be carried out. This is important so that non-recurrent engineering costs at the design phase be reduced. For example in a finite element formulation when performing an analysis, a small change made to an initial design by making a new mesh can be quick and looking at the result even quicker, but intermediate processing time remains constant. Therefore it is desirable to reduce analysis time, and then to minimise the number of analyses made.

The problem then is to identify which parts of the problem could benefit from application of multiprocessor computing techniques and which parts are best done serially. The problem geometry and material definition phase (i) together with the post-processing phases (iv) are usually treated as sequential.

DECOMPOSITION STRATEGIES AND MACHINE TYPES

Problems generally exhibit a wide degree of variability in the amount of parallelism that is evident in the problem itself.

In developing a concurrent program one is faced with the following tasks [3]: (i) being able to express parallelism (ii) having work spread across multiprocessors (iii) reducing cross processor communication (iv) satisfying any real time constraints (this last point will not be further discussed other than implicitly in terms of speedup relative to sequential program variants)

In (i) parallelism in a problem can be domain based. Here the problem is decomposed spatially, the resulting pieces are described and manipulated independently and then the pieces reassembled to form a description for the entire problem. Alternatively the problem could be decomposed on some algorithmic criteria such as the concurrent evaluation of the many independent terms needed to fill a matrix. Points (ii) and (iii) suggest that any algorithm designed will have to reflect the topological constraints imposed by the target hardware. Thus the best algorithm for one type of machine architecture may be totally unsuitable for another.

Parallel Computing Machine architectures may be classified according to Flynns Classification [4]. This classifies a parallel architecture according to a specification of single 'S' or multiple 'M' operations in its instruction stream 'I' and data stream 'D'. This results in the four letter acronyms, SIMD Single Instruction Multiple Data and MIMD Multiple Instruction Multiple Data. The memory in a MIMD machine can be either shared between processors distributed locally to individual processors. Both machine types have inherent characteristics which are important to recognise when developing concurrent algorithms. For example in an SIMD machine if the calculation of a quantity does not rely on the completion of a calculation elsewhere in the hardware array then vector processing can occur at speeds limited only by memory access time. Thus in the limit of zero time per vector operation the throughput of the system will be defined by the sequential, computational requirements that exist within the problem. With MIMD machines more complex operations can occur in parallel. However synchronisation adds a source of efficiency loss due to processor latency. When concurrent techniques are applied to the problems of interest to high frequency problems disappointing results often occur primarily due to the conditions cited above.

APPLICATIONS AND EXPERIENCE

Table 1 presents a review of some applications of concurrent programming methods to electromagnetic field problems. The review presented is in no way definitive, its purpose is to show the diversity of numerical EM field methods that have been mapped into concurrent algorithms. The main topics defined above are repeatedly addressed in this table, i.e. matrix fill, matrix solve, choice of hardware and language and resultant algorithm efficiency. Three broad classes of activity arise on inspection of this table.

The first is parallelization of already established code [5], [6]. This approach generally tends to be disappointing due to the complexity of identifying code sections which can be easily parallelized. The second is coding of techniques in which large matrix fill time is expected due to myriad complex but independent operations being necessitated [7], [8], [9]. This generally tends to be successful due to the localised nature of the computations involved. The third is in the solution of the resultant systems of equations [51, [8], [9], [12], [16], [17], [19], [21] either by direct or by iterative solution methods. The degree of success of this activity depends on the nature of the methods employed. Fourth the variety of hardware options and language derivative available is bewildering. In concurrent algorithms the identification of performance is a difficult proposition. Principally this is due to the subtle nature of the hardware software partitioning effects inherent in the programming task. This makes the ultimate success of concurrent codes in terms of speed advantage extremely critical on choice of hardware and hardware connectivity. The fifth and most dominant feature of Table 1 is the number of workers who have adopted spatial decomposition as the primary strategy for parallelizing specific problems [51], [71], [11], [14], [l8], [19]. The details of the various strategies for algorithmic decomposition are problem specific and will not be further pursued. Finally only very few problems are truly parallel with minimum communication requirements so that linear speedup with processor addition can be attained [20].

SPATIAL DECOMPOSITION

Spatial decomposition appears to be an important theme which occurs in many concurrent algorithms. The principle technique is to reduce a system into its constitutive parts overlapping on their boundaries and to allocate each part to a separate processor. Computational time and memory requirement are improved and additionally subsystems can be individually modified under change of stimulus or structure without the need for global reformulation. With this method the only information to be passed between processors occurs along these spatial boundaries, all other calculations pertaining to each subdomain are computed locally. Eventually a global solution for the problem can be achieved. Krons [2] work suggests a formal method for defining the necessary tears and methods of reassembly. The author has exploited Krons tearing techniques supplemented with Krons circuit analogs of Maxwells equations [27] on arrays of MIMD processors. The resulting method termed the Diakoptics Network Modelling Method [28], has been used very successfully to solve field problems associated with planar microwave MMIC structures in a computationally efficient way. This work suggests that the actual connectivity of individual processors as a tree, pipeline, torus etc. and also the selection of the number of processors used must be done on individual merit. Again this observation suggests that the actual detail of the concurrent algorithms developed will depend to an extent on programmer experience and preference. One interesting and recurrent observation is that for many problem formulations small numbers of MIMD processors work best.

ALGORITHMIC DECOMPOSITION

In algorithmic decomposition the structure inherent within the equations governing the problem or the order in which they are to be solved is exploited. Algorithms like TLM [10], [13] appear to decompose best when the algorithm used is based on mimicking the basic scattering process. Here SIMD machines work at best. Consider now different methods of solving non-linear circuit problems of the type relevant to high frequency circuit designers. Sobhy [29] decomposed the time domain circuit equations prior to solution resulting in a novel scheme whereby any linear or non-linear set of circuit equations can be mapped to four processes. One represents Kirchoffs Current Law, another Kirchoffs Voltage Law, a third the network tree processes, t, () and last the co-tree process, c, (of the form). With this formulation it is (i) theoretically possible to solve a nonlinear problem in the time domain without iteration (in practice some iteration is needed because of loop stabilisation requirements), (ii) optimise the network response without reformulation of the equations. The second point is particularly useful if the circuit approach and electromagnetic field approaches are to combined to form advanced hybrid field/circuit simulation, see next section.

Algorithmic decomposition may also be usefully applied in the design of concurrent circuit analysis programs that use the Harmonic Balance Method [30]. The QUB microwave research group is currently addressing this problem with some interesting findings. The first is that harmonic balance uses independent linear and non-linear circuit evaluations (based on spatial decomposition). In addition the network response to a frequency vector can be independently generated for each frequency. Finally the optimisation procedure used to enforce the interface conditions at linear non-linear circuit partition boundaries has potential for further parallelization.

HYBRID EM FIELD / NON-LINEAR CIRCUIT SIMULATION

If advanced circuit design methods for high frequency electronics are to advance into the regime of 'right first time' design for MMICs such that MMIC custom cell placement effects are to be incorporated in a quantitative fashion; then a new class of circuit simulator is required [32]. Attempts at combining EM field mapping and non-linear circuit elements using conventional methods soon run into computational time and memory usage difficulties [31]. Presently circuit models are used to assist the design/simulation activity with an attendant loss of accuracy (sometimes to the point of losing quantitative prediction). However by exploiting concurrent techniques for circuit simulation with those of electromagnetic field simulation it is conceptually possible to resolve the computational difficulties stated above.

Preliminary work at QUB in this new area of activity appears promising. An interesting outcome has been to show that once the designer is relieved of the difficult tasks of quantification and minimisation of deleterious first order effects such as parasitic component coupling in MMIC design, then the requirement for ultra conservative design be relaxed. In this way confidence to develop new circuit types can be evolved due to the additional simulation support presented by such new concurrent CAE tools.

CONCLUSIONS

It has been demonstrated that high frequency electronic problems can be solved with varying degrees of success using multiprocessor hardware and concurrent extensions of classical high level languages. It is also evident that spatial domain decomposition is a much favoured method for parallelization with algorithmic decomposition generally being more difficult to achieve. Unlike sequential algorithms parallel algorithms are defined by the hardware on which they run. Also the variety of language and hardware types in use make direct comparison of performance difficult. Finally work on concurrent non-linear circuit solvers is less mature than that for EM field solvers and up to now the important class of hybrid non-linear circuit/EM field simulators has remained virtually unexplored.
