Find results with:

Add another field

Search by date

to

Searching collections:

Dartmouth Dissertations

Add or remove collections

Home Dartmouth Dissertations Page 1

Reference URL

To link to the entire object, paste this link in email, IM or document

To embed the entire object, paste this HTML in website

To link to this page, paste this link in email, IM or document

To embed this page, paste this HTML in website

Efficient design and implementation of permutation algorithms on the memory hierarchy.

you wish to report:

Your comment:

Your Name:

Submit

Cancel

...

Back to top

Powered by CONTENTdm®

Call No.	QA76.9.A43 W57 1996
Author	Wisniewski, Leonard F.
Title	Efficient design and implementation of permutation algorithms on the memory hierarchy.
Date	1996
Abstract	For many scientific applications, the data set cannot entirely fit in main memory. The data must reside out-of-core, i.e., on parallel disks. For many basic data-movement operations such as permuting, if the programmer does not design efficient algorithms for accessing data on the parallel disks, the penalty can be quite severe. As processor speeds increase more rapidly than disk speeds, additional disk accesses become even more costly in a relative sense. In this thesis, we focus on efficiently performing the data movement for permutations when the data reside out-of-core. We present a unified approach for performing bit-matrix-multiply/complement (BMMC) permutations at different levels of the memory hierarchy. Our unified approach uses a linear-algebraic technique to decompose an arbitrary BMMC permutation into a number of permutations which we know how to perform efficiently. We show that this technique is flexible enough to apply at the following levels of memory abstraction: parallel disk access, interprocessor communication on distributed memory multiprocessors (with the processors connected by either a mesh or a multistage network), uniprocessor memory access, and the design of combinational circuits. The BMMC permutations include commonly used permutations such as matrix transposition, bit-reversal permutations (used in performing FFTs), vector-reversal permutations, hypercube permutations, matrix reblocking, and permutations used by fast cosine transforms (FCTs). This thesis presents additional work at the parallel disk level of abstraction. We define in-place algorithms for permuting out-of-core data and show how to efficiently perform BMMC, mesh, and torus permutations in place. We also define an application user interface (API) for performing parallel data accesses in the manner suggested by Vitter and Shriver's Parallel Disk Model (PDM)."
Description	xiii, 216 leaves : ill. 28 cm
Format	application/pdf
Advisor	Cormen, Thomas H.
Subject	Computer algorithms. Permutations. Memory hierarchy (Computer science). Computer programming.
College	Dartmouth College -- Department of Computer Science.
Issuing Body	Dartmouth Dissertations are made available through the Dartmouth Digital Library.
Degree	Thesis (Ph.D.)--Dartmouth College.
Copyright	All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means without permission in writing from the author.
DOI	http://dx.doi.org/10.1349/ddlp.1439

Title	Page 1
Full Text	Efficient Design and Implementation of Permutation Algorithms on the Memory Hierarchy A Thesis Submitted to the Faculty in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science by Leonard F. Wisniewski Dartmouth College Hanover, New Hampshire March, 1996

Find results with:

Searching collections:

Home Dartmouth Dissertations Page 1

Efficient design and implementation of permutation algorithms on the memory hierarchy.

Object Description

Description

Efficient design and implementation of permutation...

Efficient design and implementation of permutation...

	All
	Pages Enter page numbers or page ranges separated by commas. For example: 1,3,5-12