Parallel algorithms for electromagnetic moment method formulations
Date
1991-12
Authors
Davidson, David Bruce
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: This dissertation investigates the moment method solution of electromagnetic
radiation and scattering problems using parallel computers. In particular,
electromagnetically large problems with arbitrary geometries are considered.
Such problems require a large number of unknowns to obtain adequate approximate
solutions, and make great computational demands. This dissertation
considers in detail the efficient exploitation of the potential offered by
parallel computers for solving such problems, and in particular the class of
local memory Multiple Instruction, Multiple Data systems.
A brief history of parallel computing is presented. Methods for quantifying
the efficiency of parallel algorithms are reviewed. The use of pseudo-code
for documenting algorithms is discussed and a pseudo-code notation is defined
that is used in later chapters.
A new parallel conjugate gradient algorithm, suitable for the solution
of general systems of linear equations with complex values, is presented.
A method is described to handle efficiently the Hermitian transpose of the
matrix required by the algorithm. Careful attention is paid to the theoretical
analysis of the algorithm's parallel properties (in particular, speed-up and
efficiency). Pseudo-code is presented for the algorithms. Timing results for a
moment method code, running on a transputer array and using this conjugate
gradient solver, are presented and compared to the theoretical predictions.
A parallel LU algorithm is described and documented in pseudo-code. A
new graphical description of the algorithm is presented that simplifies the
identification of the parallelism and the analysis of the algorithm. The use
of formal methods for extracting parallelism via the use of invariants is presented
and new examples given. The speed-up and efficiency of the algorithm
are analyzed theoretically, using new methods that are simpler than those described
in the literature. Techniques for optimizing the efficiency of parallel
algorithms are introduced, and illustrated with pseudo-code. New parallel
forward and backward substitution algorithms using the data distribution
required for the parallel LV algorithm are described, and documented with
pseudo-code. Results obtained with a Occam 2 moment method code running
on a transputer array using these parallel LU solver and substitution
algorithms are presented and compared with the theoretical predictions.
PARNEC, a new Occam 2 implementation of the thin-wire core of NEC2,
is discussed. The basic 'theory of NEC2 is reviewed. Problems with early attempts
at combining Occam and FORTRAN are reported. Methodologies
for re-coding an old code written in an unstructured language in a. modern
structured language are discussed. Methods of parallelizing the matrix generation
are discussed. The accuracy of large moment method formulations
is investigated, as is the effect of machine precision on the solutions. The use of the biconjugate gradient method to accelerate convergence is briefly
considered and rejected. The increased size of problem that can be handled
by PARNEC, running on a transputer array, is demonstrated.
Conclusions are dra.wn regarding the contributions of this dissertation to
the development of efficient parallel electromagnetic moment method algorithms.
AFRIKAANSE OPSOMMING: Hierdie proefskrif ondersoek die momentmetode oplossing van elektromagnetiese straling- en strooiingprobleme d.m.v. multiverwerkers. In besonder, elektromagneties groot probleme met arbitrere geometriee word beskou. Sulke probleme vereis 'n groot aantal onbekendes om 'n voldoende benaderde oplossing te kry, en stel groot berekenings vereistes. Hierdie proefskrif beskou in detail die doeltreffende benutting van die potensiaal wat multiverwerkers vir sulke problem hied, in besonder die klas van lokale geheue Veelvoudige Instruksie, Veelvoudige Data stelsels. 'n Kort geskiedenis van multiverwerkers word gegee. Metodes vir die kwantifisering van die effektiwiteit van multiverwerkers word hersien. Die . gebruik van pseudokode vir die dokumentering van algoritmes word bespreek en 'n pseudokode notasie word gedefinieer wat gebruik word in latere hoofstukke. 'n Nuwe parallelle toegevoegde helling-algoritme wat geskik is vir die oplossing van algemene stelsels van lineere vergelykings word aangebied. 'n Metode word beskryf om op 'n doeltreffende wyse die Hermitiese transponent van die matriks, wat deur die algoritme benodig word, te hanteer. Sorgvuldige aandag word aan die teoretiese analise van die paralleleienskappe van die algoritme gegee (in die besonder, versnelling en doeltreffendheid). Pseudokode word aangebied vir die algoritmes. Resultate vir die looptyd van 'n momentmetode program, wat op 'n transputerskikking loop, word gegee en vergelyk met die teoretiese voorspellings. 'n Parallelle L U algoritme word beskryf en gedokumenteer in pseudokode. 'n Nuwe grafiese beskrywing van die algoritme, wat die identifikasie van parallelisme en die analise van die algoritme vergemaklik, word gegee. Die gebruik van formele metodes vir die onttrekking van parallelisme d.m.v. invariante word getoon en nuwe voorbeelde word gegee. Die versnelling en doeltreffendheid van die algoritme word teoreties geanaliseer, d.m.v. nuwe metodes wat eenvoudiger is as die wat in die literatuur beskryf word. Tegnieke vir die optimering van die doeltreffendheid van parallelle algoritmes word ingevoer, en gelllustreer met pseudokode. Nuwe parallelle voor- en truwaarts-substitusie algoritmes wat die data verspreiding van die parallelle LU algoritme gebruik word beskryf, en gedokumenteer met pseudokode. Resultate verkry met 'n Occam 2 momentmetode program wat op 'n transputerskikking loop en die parallelle L U en substit'usie algoritmes gebruik, word gegee en vergelyk met teoretiese voorspellings. PARNEC, 'n nuwe Occam 2 implementering van die dun-draad kern van NEC2, word bespreek. Die basiese teorie van NEC2 word opgesom. Verslag word gedoen oor probleme met vroee pogings orh Occam en FORTRAN te kombineer. Metodes om 'n ou program, geskryf in 'n ongestruktureerde taal, in 'n moderne gestruktureerde taal te herskryf word bespreek. Metodes om die matriksopwekking te paralleliseer word bespreek. Die akkuraatheid van groot momentmetode formulerings word ondersoek, asook die effek van masjienpresisie op die oplossings. Die gebruik van die dubbeltoegevoegde helling-metode om konvergensie te versnel word kortliks beskou en verwerp. Die vergrote probleemgrootte, wat met PARNEC op- 'n transputerskikking uitgevoer kan word, word gedemonstreer. Gevolgtrekkings word gemaak rakende die bydraes van hierdie proefskrif tot die ontwikkeling van doeltreffende parallelle elektromagnetiese momentmetode algoritmes.
AFRIKAANSE OPSOMMING: Hierdie proefskrif ondersoek die momentmetode oplossing van elektromagnetiese straling- en strooiingprobleme d.m.v. multiverwerkers. In besonder, elektromagneties groot probleme met arbitrere geometriee word beskou. Sulke probleme vereis 'n groot aantal onbekendes om 'n voldoende benaderde oplossing te kry, en stel groot berekenings vereistes. Hierdie proefskrif beskou in detail die doeltreffende benutting van die potensiaal wat multiverwerkers vir sulke problem hied, in besonder die klas van lokale geheue Veelvoudige Instruksie, Veelvoudige Data stelsels. 'n Kort geskiedenis van multiverwerkers word gegee. Metodes vir die kwantifisering van die effektiwiteit van multiverwerkers word hersien. Die . gebruik van pseudokode vir die dokumentering van algoritmes word bespreek en 'n pseudokode notasie word gedefinieer wat gebruik word in latere hoofstukke. 'n Nuwe parallelle toegevoegde helling-algoritme wat geskik is vir die oplossing van algemene stelsels van lineere vergelykings word aangebied. 'n Metode word beskryf om op 'n doeltreffende wyse die Hermitiese transponent van die matriks, wat deur die algoritme benodig word, te hanteer. Sorgvuldige aandag word aan die teoretiese analise van die paralleleienskappe van die algoritme gegee (in die besonder, versnelling en doeltreffendheid). Pseudokode word aangebied vir die algoritmes. Resultate vir die looptyd van 'n momentmetode program, wat op 'n transputerskikking loop, word gegee en vergelyk met die teoretiese voorspellings. 'n Parallelle L U algoritme word beskryf en gedokumenteer in pseudokode. 'n Nuwe grafiese beskrywing van die algoritme, wat die identifikasie van parallelisme en die analise van die algoritme vergemaklik, word gegee. Die gebruik van formele metodes vir die onttrekking van parallelisme d.m.v. invariante word getoon en nuwe voorbeelde word gegee. Die versnelling en doeltreffendheid van die algoritme word teoreties geanaliseer, d.m.v. nuwe metodes wat eenvoudiger is as die wat in die literatuur beskryf word. Tegnieke vir die optimering van die doeltreffendheid van parallelle algoritmes word ingevoer, en gelllustreer met pseudokode. Nuwe parallelle voor- en truwaarts-substitusie algoritmes wat die data verspreiding van die parallelle LU algoritme gebruik word beskryf, en gedokumenteer met pseudokode. Resultate verkry met 'n Occam 2 momentmetode program wat op 'n transputerskikking loop en die parallelle L U en substit'usie algoritmes gebruik, word gegee en vergelyk met teoretiese voorspellings. PARNEC, 'n nuwe Occam 2 implementering van die dun-draad kern van NEC2, word bespreek. Die basiese teorie van NEC2 word opgesom. Verslag word gedoen oor probleme met vroee pogings orh Occam en FORTRAN te kombineer. Metodes om 'n ou program, geskryf in 'n ongestruktureerde taal, in 'n moderne gestruktureerde taal te herskryf word bespreek. Metodes om die matriksopwekking te paralleliseer word bespreek. Die akkuraatheid van groot momentmetode formulerings word ondersoek, asook die effek van masjienpresisie op die oplossings. Die gebruik van die dubbeltoegevoegde helling-metode om konvergensie te versnel word kortliks beskou en verwerp. Die vergrote probleemgrootte, wat met PARNEC op- 'n transputerskikking uitgevoer kan word, word gedemonstreer. Gevolgtrekkings word gemaak rakende die bydraes van hierdie proefskrif tot die ontwikkeling van doeltreffende parallelle elektromagnetiese momentmetode algoritmes.
Description
Thesis (PhD) -- Stellenbosch University, 1991.
Keywords
Parallel programming (Computer science), Electromagnetic waves -- Scattering -- Data processing, Algorithms, Dissertations -- Engineering