Stack Overflow
Stack Overflow

Questions tagged [cache-oblivious]

11 questions
16
votes
1 answer

How to calculate pointers in a binary tree with the van Emde Boas layout

I'd like to implement a cache-oblivious binary tree that is stored in an array using the van Emde Boas layout, using implicit pointers. All items in the tree are 32-bit integers and the tree will get fairly big, so storing the pointers would mean at…
Lukáš Lalinský
  • 40,587
  • 6
  • 104
  • 126
11
votes
3 answers

Cache Oblivious algorithms for parallel programming?

I have read a lot about Cache Oblivious Algorithms and Streaming trees etc. I understand the basics what I am still unable to see is why they are good for parallel programming? I think I saw John Harrop stated that they are revolutionary for that.
user741842
  • 113
  • 4
4
votes
2 answers

What is the intuition behind cache oblivious data structures?

I understand what the expression cache oblivious means. But I was wondering if there is any easy explanation for how data structures can be designed that can use the cache optimally, without knowing the sizes of the cache. Can you please provide…
Muhammad Alkarouri
  • 23,884
  • 19
  • 66
  • 101
3
votes
1 answer

Just as there are cache oblivious and cache optimal algorithms, are there seek optimal algorithms?

Do cache (oblivious|optimal|aware) algorithms typically consider seek time in their model. If not are there examples of models that do consider seek time, and are there analysis of algorithms in this model.
san
  • 4,144
  • 6
  • 32
  • 50
1
vote
1 answer

Divide and Conquer In-place Transpose of a Matrix

I'm working on an implementation of the approach described in the wiki article for the in-place cache-oblivious transposition of a square Matrix. https://en.wikipedia.org/wiki/In-place_matrix_transposition The algorithm basically recursively splits…
MHH
  • 35
  • 1
  • 8
1
vote
2 answers

Run-time efficient transposition of a rectangular matrix of arbitrary size

I am pressed for time to optimize a large piece of C code for speed and I am looking for an algorithm---at the best a C "snippet"---that transposes a rectangular source matrix u[r][c] of arbitrary size (r number of rows, c number of columns) into a…
Martin
  • 23
  • 3
1
vote
0 answers

How to matrix transpose using morton order?

I want to transpose matrix by using morton order for imporve matrix transpose. I found some article about morton order, but i can't understand how to use that. especially, and I want to invert this matrix A = [1 2 3 4; 5 6 7 8; 9 10 11 12; 13 14…
JungHoon
  • 302
  • 1
  • 4
  • 17
1
vote
1 answer

Cache Oblivious Search

Please forgive this stupid question, but I didn't find any hint by googling it. If I have an array (contiguous memory), and I search sequentially for a given pattern (for example build the list of all even numbers), am I using a cache-oblivious…
newbiepp
  • 95
  • 6
1
vote
2 answers

Complexity of cache-oblivious stacks and queues

I have read that a cache oblivious stack can be implemented using a doubling array. Can someone please explain how the analysis makes each push and pop have a 1/B amortized I/O complexity?
Meghana
  • 11
  • 1
0
votes
0 answers

What is the difference between 'Cache Oblivious' and 'Cache agnostic'?

In my studies, I came across these two words and I didn't quite understand what Cache agnostic meant. There is also little information about Cache agnostic online. Please explain what Cache agnostic means and how it differs from Cache Oblivious!
HONG MAO
  • 1
  • 3
0
votes
0 answers

Optimized Out-of-Place Matrix Transposition

my implementation is that i am using the z-order curve to traverse the entries of each matrix block. this implementation is resulting in 3x speedup than the naive approach (see my code below). i want to achieve a better speedup by traversing the…
Zoheir El houari
  • 11
  • 2