Dartmouth College Computer Science Technical Report series 
CS home TR home TR search TR listserv 

By author:  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z  
By number:  2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986 
Abstract:
The ability to perform permutations of large data sets in place
reduces the amount of necessary available disk storage. The simplest
way to perform a permutation often is to read the records of a data
set from a source portion of data storage, permute them in memory, and
write them to a separate target portion of the same size. It can be
quite expensive, however, to provide disk storage that is twice the
size of very large data sets. Permuting in place reduces the expense
by using only a small amount of extra disk storage beyond the size of
the data set.
This paper features inplace algorithms for commonly used structured
permutations. We have developed an asymptotically optimal algorithm
for performing BMMC (bitmatrixmultiply/complement) permutations in
place that requires at most $\frac{2N}{BD}\left(
2\ceil{\frac{\rank{\gamma}}{\lg (M/B)}} + \frac{7}{2}\right)$ parallel
disk accesses, as long as $M \geq 2BD$, where $N$ is the number of
records in the data set, $M$ is the number of records that can fit in
memory, $D$ is the number of disks, $B$ is the number of records in a
block, and $\gamma$ is the lower left $\lg (N/B) \times \lg B$
submatrix of the characteristic matrix for the permutation. This
algorithm uses $N+M$ records of disk storage and requires only a
constant factor more parallel disk accesses and insignificant
additional computation than a previously published asymptotically
optimal algorithm that uses $2N$ records of disk storage.
We also give algorithms to perform mesh and torus permutations on a
$d$dimensional mesh. The inplace algorithm for mesh permutations
requires at most $3\ceil{N/BD}$ parallel I/Os and the inplace
algorithm for torus permutations uses at most $4dN/BD$ parallel I/Os.
The algorithms for mesh and torus permutations require no extra disk
space as long as the memory size~$M$ is at least~$3BD$. The torus
algorithm improves upon the previous best algorithm in terms of both
time and space.
Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]
Or copy and paste:
Leonard F. Wisniewski,
"Structured Permuting in Place on Parallel Disk Systems."
Dartmouth Computer Science Technical Report PCSTR95265,
September 1995.
Notify me about new tech reports.
To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu
Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Technical reports collection maintained by David Kotz.