# Titelaufnahme

Titel
A Parallel, In-Place, Rectangular Matrix Transpose Algorithm / submitted by Stefan Amberger
AutorInnenAmberger, Stefan
Beurteiler / BeurteilerinPaule, Peter
Betreuer / Betreuerin Schreiner, Wolfgang
ErschienenLinz, 2019
UmfangIV, 62 Blätter : Illustrationen
HochschulschriftUniversität Linz, Masterarbeit, 2019
SpracheEnglisch
DokumenttypMasterarbeit
Schlagwörter (EN) Cilk
URNurn:nbn:at:at-ubl:1-26797
 Zugriffsbeschränkung Das Werk ist gemäß den "Hinweisen für BenützerInnen" verfügbar
 Dateien A Parallel, In-Place, Rectangular Matrix Transpose Algorithm [2.53 mb]
 Links Nachweis Universitätsbibliothek Linz
 Klassifikation
 Zusammenfassung (Englisch) This thesis presents a novel algorithm for Transposing Rectangular matrices In-place and in Parallel (TRIP) including a proof of correctness and an analysis of work, span and parallelism. After almost 60 years since its introduction, the problem of in-place rectangular matrix transposition still does not have a satisfying solution. Increased concurrency in todays computers, and the need for low-overhead algorithms to solve memory-intense challenges are motivating the development of algorithms like TRIP. The algorithm is based on recursive splitting of the matrix into sub-matrices, independent, parallel transposition of these sub-matrices, and subsequent combining of the results by a parallel, perfect shuffle. We prove correctness of the algorithm for different matrix shapes (ratios of dimensions), and analyze work and span: For an $M\times N$ matrix, where $M>N$, and both $M$ and $N$ are powers of two, TRIP has work \[W_1 \trip(M,N)=\Theta\left(MN\log\frac
 Statistik Das PDF-Dokument wurde 7 mal heruntergeladen.