Header menu link for other important links
Brief announcement: Efficient cache oblivious algorithms for randomized divide-and-conquer in the multicore model
N. Sharma,
Published in
Pages: 74 - 76
In this paper we present a cache-oblivious framework for randomized divide and conquer algorithms on the multicore model with private cache. We first derive an O( p n log n + log n log log n) expected parallel depth algorithm for sorting n numbers with expected O( B n log M n) cache misses where p,M and B respectively denote the number of processors, the size of an individual cache memory and the block size respectively. Although similar results have been obtained recently for sorting [4], we feel that our approach is simpler and general and we apply it to obtain an algorithm for 3D convex hulls with similar bounds. We also present a simple randomized processor allocation technique without the explicit knowledge of the number of processors that is likely to find additional applications in resource oblivious environments. A longer version of this paper is available at [8]. Copyright is held by the author/owner(s).
About the journal
Published in
Open Access
Impact factor