did-you-know? rent-now

Amazon no longer offers textbook rentals. We do!

did-you-know? rent-now

Amazon no longer offers textbook rentals. We do!

We're the #1 textbook rental company. Let us show you why.

9783540008835

Algorithms for Memory Hierarchies : Advanced Lectures

by ; ; ; ; ;
  • ISBN13:

    9783540008835

  • ISBN10:

    3540008837

  • Format: Paperback
  • Copyright: 2003-08-01
  • Publisher: Springer Verlag
  • Purchase Benefits
  • Free Shipping Icon Free Shipping On Orders Over $35!
    Your order must be $35 or more to qualify for free economy shipping. Bulk sales, PO's, Marketplace items, eBooks and apparel do not qualify for this offer.
  • eCampus.com Logo Get Rewarded for Ordering Your Textbooks! Enroll Now
  • Write a Review Icon Write a Review
List Price: $99.00 Save up to $80.44
  • Digital
    $40.22
    Add to Cart

    DURATION
    PRICE

Supplemental Materials

What is included with this book?

Summary

Algorithms that have to process large data sets have to take into account that the cost of memory access depends on where the data is stored. Traditional algorithm design is based on the von Neumann model where accesses to memory have uniform cost. Actual machines increasingly deviate from this model: while waiting for memory access, nowadays, microprocessors can in principle execute 1000 additions of registers; for hard disk access this factor can reach six orders of magnitude.The 16 coherent chapters in this monograph-like tutorial book introduce and survey algorithmic techniques used to achieve high performance on memory hierarchies; emphasis is placed on methods interesting from a theoretical as well as important from a practical point of view.

Table of Contents

1. Memory Hierarchies - Models and Lower Bounds
Peter Sanders
1(13)
1.1 Why Memory Hierarchies
1(1)
1.2 Current Technology
2(3)
1.3 Modeling
5(4)
1.4 Issues in External Memory Algorithm Design
9(1)
1.5 Lower Bounds
10(4)
2. Basic External Memory Data Structures
Rasmus Pagh
14(22)
2.1 Elementary Data Structures
15(2)
2.2 Dictionaries
17(2)
2.3 B-trees
19(8)
2.4 Hashing Based Dictionaries
27(6)
2.5 Dynamization Techniques
33(2)
2.6 Summary
35(1)
3. A Survey of Techniques for Designing I/O-Efficient Algorithms
Anil Maheshwari and Norbert Zeh
36(26)
3.1 Introduction
36(1)
3.2 Basic Techniques
37(7)
3.3 Simulation of Parallel Algorithms in External Memory
44(2)
3.4 Time-Forward Processing
46(2)
3.5 Greedy Graph Algorithms
48(2)
3.6 List Ranking and the Euler Tour Technique
50(4)
3.7 Graph Blocking
54(7)
3.8 Remarks
61(1)
4. Elementary Graph Algorithms in External Memory
Irit Katriel and Ulrich Meyer
62(23)
4.1 Introduction
62(1)
4.2 Graph-Traversal Problems: BFS, DFS, SSSP
63(3)
4.3 Undirected Breadth-First Search
66(4)
4.4 I/O-Efficient Tournament Trees
70(3)
4.5 Undirected SSSP with Tournament Trees
73(1)
4.6 Graph-Traversal in Directed Graphs
74
4.7 Conclusions and Open Problems for Graph Traversal
70(7)
4.8 Graph Connectivity: Undirected CC, BCC, and MSF
77(1)
4.9 Connected Components
78(2)
4.10 Minimum Spanning Forest
80(1)
4.11 Randomized CC and MSF
81(2)
4.12 Biconnected Components
83(1)
4.13 Conclusion for Graph Connectivity
84(1)
5. I/O-Efficient Algorithms for Sparse Graphs
Laura Toma and Norbert Zeh
85(25)
5.1 Introduction
85(2)
5.2 Definitions and Graph Classes
87(2)
5.3 Techniques
89(2)
5.4 Connectivity Problems
91(2)
5.5 Breadth-First Search and Single Source Shortest Paths
93(5)
5.6 Depth-First Search
98(3)
5.7 Graph Partitions
101(4)
5.8 Gathering Structural Information
105(4)
5.9 Conclusions and Open Problems
109(1)
6. External Memory Computational Geometry Revisited
Christian Breimann and Jan Vahrenhold
110(39)
6.1 Introduction
110(2)
6.2 General Methods for Solving Geometric Problems
112(7)
6.3 Problems Involving Sets of Points
119(12)
6.4 Problems Involving Sets of Line Segments
131(13)
6.5 Problems Involving Set of Polygonal Objects
144(4)
6.6 Conclusions
148(1)
7. Full-Text Indexes in External Memory
Juha Kärkkäinen and S. Srinivasa Rao
149(22)
7.1 Introduction
149(1)
7.2 Preliminaries
150(1)
7.3 Basic Techniques
151(4)
7.4 I/O-Efficient Queries
155(6)
7.5 External Construction
161(9)
7.6 Concluding Remarks
170(1)
8. Algorithms for Hardware Caches and TLB
Naila Rahman
171(22)
8.1 Introduction
171(2)
8.2 Caches and TLB
173(3)
8.3 Memory Models
176(5)
8.4 Algorithms for Internal Memory
181(4)
8.5 Cache Misses and Power Consumption
185(1)
8.6 Exploiting Other Memory Models: Advantages and Limitations
186(3)
8.7 Sorting Integers in Internal Memory
189(4)
9. Cache Oblivious Algorithms
Piyush Kumar
193(20)
9.1 Introduction
193(2)
9.2 The Model
195(2)
9.3 Algorithm Design Tools
197(2)
9.4 Matrix Transposition
199(2)
9.5 Matrix Multiplication
201(2)
9.6 Searching Using Van Emde Boas Layout
203(2)
9.7 Sorting
205(4)
9.8 Is the Model an Oversimplification?
209(2)
9.9 Other Results
211(1)
9.10 Open Problems
211(1)
9.11 Acknowledgements
212(1)
10. An Overview of Cache Optimization Techniques and Cache-Aware Numerical Algorithms
Markus Kowarschik and Christian Weiß
213(20)
10.1 Introduction
213(1)
10.2 Architecture and Performance Evaluation of Caches
214(3)
10.3 Basic Techniques for Improving Cache Efficiency
217(8)
10.4 Cache-Aware Algorithms of Numerical Linear Algebra
225(7)
10.5 Conclusions
232(1)
11. Memory Limitations in Artificial Intelligence
Stefan Edelkamp
233(18)
11.1 Introduction
233(1)
11.2 Hierarchical Memory
234(1)
11.3 Single-Agent Search
235(6)
11.4 Action Planning
241(5)
11.5 Game Playing
246(2)
11.6 Other AI Areas
248(1)
11.7 Conclusions
249(2)
12. Algorithmic Approaches for Storage Networks
Kay A. Salzwedel
251(22)
12.1 Introduction
251(3)
12.2 Model
254(2)
12.3 Space and Access Balance
256(2)
12.4 Availability
258(2)
12.5 Heterogeneity
260(9)
12.6 Adaptivity
269(3)
12.7 Conclusions
272(1)
13. An Overview of File System Architectures
Florin Isaila
273(17)
13.1 Introduction
273(1)
13.2 File Access Patterns
274(2)
13.3 File System Duties
276(4)
13.4 Distributed File Systems
280(9)
13.5 Summary
289(1)
14. Exploitation of the Memory Hierarchy in Relational DBMSs
Josep-L. Larriba-Pey
290(30)
14.1 Introduction
290(1)
14.2 What to Expect and What Is Assumed
291(2)
14.3 DBMS Engine Structure
293(4)
14.4 Evidences of Locality in Database Workloads
297(1)
14.5 Basic Techniques for Locality Exploitation
298(2)
14.6 Exploitation of Locality by the Executor
300(7)
14.7 Access Methods
307(4)
14.8 Exploitation of Locality by the Buffer Pool Manager
311(6)
14.9 Hardware Related Issues
317(1)
14.10 Compilation for Locality Exploitation
318(1)
14.11 Summary
318(2)
15. Hierarchical Models and Software Tools for Parallel Programming
Massimo Coppola and Martin Schmollinger
320(35)
15.1 Introduction
320(1)
15.2 Architectural Background
321(6)
15.3 Parallel Computational Models
327(1)
15.4 Parallel Bridging Models
328(10)
15.5 Software Tools
338(14)
15.6 Conclusions
352(3)
16. Case Study: Memory Conscious Parallel Sorting
Dani Jiménez-González, Josep-L. Larriba-Pey, and Juan J. Navarro
355(24)
16.1 Introduction
355(3)
16.2 Architectural Aspects
358(3)
16.3 Sequential and Straight Forward Radix Sort Algorithms
361(10)
16.4 Memory Conscious Algorithms
371(5)
16.5 Conclusions
376(1)
16.6 Acknowledgments
377(2)
Bibliography 379(42)
Index 421

Supplemental Materials

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

Rewards Program