Change search
ReferencesLink to record
Permanent link

Direct link
A Vector Space Framework for Parallel Stable Permutations
KTH, School of Computer Science and Communication (CSC), Centres, Centre for High Performance Computing, PDC. (Parallelldatorcentrum)
1997 (English)Conference paper (Refereed)
Abstract [en]

We establish a formal foundation for stable permutations in the domain of a parallel model of computation applicable to a customized set of complexity metrics. By means of vector spaces, we develop an algebrao--geometric representation that is expressive, flexible and simple to use, and present a taxonomy categorizing stable permutations into classes of index--digit, linear, translation, affine and polynomial permutations. For each class, we demonstrate its general behavioral properties and then analyze particular examples in each class, where we derive results about its inverse, fixed instances, number of instances local and nonlocal to a processor, as well as its compositional relationships to other permutations. Such examples are bit--reversal, radix-- Q exchange, radix--Q shuffle and unshuffle within the index--digit class, radix--Q butterfly and 1's complement within the translation class, binary--to--Gray and Gray--to--binary within the linear class, and arithmetic add 1, arithm...

Place, publisher, year, edition, pages
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-64547OAI: diva2:483114
In Second International Workshop on Formal Methods for Parallel Programming: Theory and Applications
NR 20140805Available from: 2012-01-24 Created: 2012-01-24Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Johnsson, Lennart
By organisation
Centre for High Performance Computing, PDC
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 15 hits
ReferencesLink to record
Permanent link

Direct link