Title

Techniques to improve algorithm efficiency, from the perspective of memory hierarchies

Date of Award

1998

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Electrical Engineering and Computer Science

Advisor(s)

Sanjay Ranka

Keywords

Algorithm efficiency, Memory hierarchies

Subject Categories

Computer Sciences

Abstract

Processors have become faster at a much quicker rate than memory access time, creating wide gap between processor and memory speeds that is sometimes called the Von Neumann bottleneck. This gap has led to the design of computers with deep memory hierarchies. Effective utilization of these memory hierarchies plays a very important role in the performance of applications on such architectures. Maintaining locality of data reference is necessary to achieve good processor performance. In this thesis we develop models as well as methods for obtaining high performance on architectures with multiple levels of hierarchy. We introduce a simplified memory model (SMM), which is shown to provide a good measure of an algorithm's performance. This model divides the total cost of an algorithm into two parts, the Computation Cost and the Memory Access Cost . The former reflects the computational aspects of the algorithm and corresponds to the normal RAM analysis, while the latter reflects the memory hierarchy access cost. We investigate several high-level techniques such as data reorganization, divide-and-conquer, approximation and focusing to improve locality of access and performance. These techniques have been shown to be useful for a variety of applications such as iterative solvers, particle-in-a-cell simulation, sorting, depth measures, and the Tukey median. Extensive experimental results are presented to validate the performance improvements.

Access

Surface provides description only. Full text is available to ProQuest subscribers. Ask your Librarian for assistance.

http://libezproxy.syr.edu/login?url=http://proquest.umi.com/pqdweb?did=733069361&sid=1&Fmt=2&clientId=3739&RQT=309&VName=PQD

Link to Full Text

Share

COinS