kth.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Highly Parallel Banded Systems Solvers
KTH, Skolan för datavetenskap och kommunikation (CSC), Centra, Parallelldatorcentrum, PDC. (Parallelldatorcentrum)
1987 (Engelska)Ingår i: Parallel Computations and Their Impact on Mechanics, ASME Press, 1987, s. 187-208Kapitel i bok, del av antologi (Refereegranskat)
Abstract [en]

We present algorithms for the solution of banded systems of equations on parallel architectures, in particular ensemble architectures, i.e., architectures that have a large number of processing elements. Each processor has its own local storage. The band is considered dense. Concurrent elimination of a single variable yields a linear speed-up for ensembles configured as tori, or Boolean cubes if N>m, with a maximum ensemble size of m(m+R) (or 2m(m+R))  processors for a banded system of N equations, bandwith 2m + 1 and R right hand sides. The minimum attainable computational complexity is of order O(N). Concurrent elimination of multiple variables as well as concurrent elemination of each such variable yields a minimum complexity of O(m+ m log2N/m) for a total of (2m + R)N ensemble nodes.   To attain this complexity the ensemble should be configured as clusters, each in the form of a torus of dimension m by 2m + R, or a Booelan cube of appropiate dimension. Furthermore, corresponding processors in different clusters are assumed to be interconnected to form a binary tree, shuffle-exchange, perfect shuffle, or Boolean cube network. The number of clusters should be of order 0(N/m)  for minimum computational comlpexity

Ort, förlag, år, upplaga, sidor
ASME Press, 1987. s. 187-208
Nationell ämneskategori
Data- och informationsvetenskap
Identifikatorer
URN: urn:nbn:se:kth:diva-74468OAI: oai:DiVA.org:kth-74468DiVA, id: diva2:489709
Anmärkning
NR 20140805Tillgänglig från: 2012-02-03 Skapad: 2012-02-03 Senast uppdaterad: 2022-06-24Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Sök vidare i DiVA

Av författaren/redaktören
Johnsson, Lennart
Av organisationen
Parallelldatorcentrum, PDC
Data- och informationsvetenskap

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 52 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf