Name
Abstract | ||
|---|---|---|
In this paper we introduce a model of Hierarchical Memory with Block Transfer (BT for short). It is like a random access machine, except that access to location x takes time f(x), and a block of consecutive locations can be copied from memory to memory, taking one unit of time per element after the initial access time. We first study the model with f(x) = xα for 0 1. Finally, we study the model f(x) = log x and obtain optimal bounds of θ(n log*n) for simple problems mentioned above and of θ(n log n) for sorting, computing an FFT graph, and for some permutations. |
Year | DOI | Venue |
|---|---|---|
1987 | 10.1109/SFCS.1987.31 | FOCS |
Keywords | Field | DocType |
hierarchical memory,fft graph,random access machine,optimal bound,n log,block transfer,initial access time,n log n,simple problem,consecutive location,layout,upper bound,fast fourier transforms,robustness,dictionaries,automata,merging,operating systems,data structure,sorting,computational modeling,registers,ions,data structures,semiconductor memory,silicon,hidden markov models,data models,lower bound,computer architecture,memory management,algorithm design and analysis,sorting algorithm,resource management,tin | Discrete mathematics,Combinatorics,Upper and lower bounds,Computer science,Matrix (mathematics),Permutation,Random-access machine,Sorting,Fast Fourier transform,Time complexity,Sorting algorithm | Conference |
ISBN | Citations | PageRank |
0-8186-0807-2 | 92 | 11.89 |
References | Authors | |
15 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alok Aggarwal | 1 | 1890 | 228.97 |
| Ashok K. Chandra | 2 | 3116 | 1215.02 |
| M. Snir | 3 | 3984 | 520.82 |