Results 1 to 10 of about 5,314 (170)
mrsFAST: a cache-oblivious algorithm for short-read mapping. [PDF]
Nat Methods, 2010 In addition to single-nucleotide variations and small insertions-deletions (indels), largersized structural variations (for example, insertions, deletions, inversions, segmental duplications and copy-number polymorphisms) contribute to human genetic diversity.
Hach F +6 more
europepmc +6 more sources
Cache-Oblivious VAT-Algorithms [PDF]
, 2014 The VAT-model (virtual address translation model) extends the EM-model (external memory model) and takes the cost of address translation in virtual memories into account. In this model, the cost of a single memory access may be logarithmic in the largest
Jurkiewicz, Tomasz +2 more
core +5 more sources
Balanced Partitioning of Several Cache-Oblivious Algorithms [PDF]
Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020 Frigo et al. proposed an ideal cache model and a recursive cache-oblivious technique to design sequential cache-efficient algorithms in an oblivious fashion. Ballard et al. pointed out that it is a fundamental open problem to extend the technique to an arbitrary architecture. Ballard et al.
Yuan Tang, Weiguo Gao
+7 more sources
Cache Oblivious Algorithms for Computing the Triplet Distance between Trees [PDF]
ACM Journal of Experimental Algorithmics, 2021 We consider the problem of computing the triplet distance between two rooted unordered trees with n labeled leaves. Introduced by Dobson in 1975, the triplet distance is the number of leaf triples that induce different topologies in the two trees. The current theoretically fastest algorithm is an O( n
Gerth Stølting Brodal +1 more
openalex +7 more sources
Low depth cache-oblivious algorithms [PDF]
Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures, 2010 In this paper we explore a simple and general approach for developing parallel algorithms that lead to good cache complexity on a variety of parallel cache architectures. The approach is to design nested parallel algorithms that have low depth (span, critical path length) and for which the natural sequential evaluation order has low cache complexity in
Guy E. Blelloch +2 more
openalex +3 more sources
Improved Parallel Cache-Oblivious Algorithms for Dynamic Programming and Linear Algebra [PDF]
, 2018 Emerging non-volatile main memory (NVRAM) technologies provide byte-addressability, low idle power, and improved memory-density, and are likely to be a key component in the future memory hierarchy. However, a critical challenge in achieving high performance is in accounting for the asymmetry that NVRAM writes can be significantly more expensive than ...
Guy E. Blleloch, Yan Gu
+5 more sources
SquareSort: a cache-oblivious sorting algorithm [PDF]
In this paper we consider sorting in the cache-oblivious model of Frigo, Leiserson, Prokop, and Ramachandran (1999). We introduce a new simple sorting algorithm in that model which has asymptotically optimal IO complexity $O(\frac{n}{B} \log_{M/B} n)$, where $n$ is the instance size, $M$ size of the cache and $B$ size of a memory block.
Michal Koucký, Joel Matějka
openalex +3 more sources
Cache-Oblivious Priority Queues with Decrease-Key and Applications to Graph Algorithms [PDF]
, 2019 We present priority queues in the cache-oblivious external memory model with block size $B$ and main memory size $M$ that support on $N$ elements, operation \textsc{UPDATE} (combination of \textsc{INSERT} and \textsc{DECREASEKEY}) in $O \left(\frac{1}{B}\log_{\frac {B}} \frac{N}{B}\right)$ amortized I/Os and operations \textsc{EXTRACT-MIN} and \textsc{
John Iacono +2 more
+5 more sources
Matrix Transposition Algorithm Using Cache Oblivious
Journal of Automation, Mobile Robotics and Intelligent SystemsThe Parallel and Distributed Computing group belonging to the Integrated Technological Research Complex (CITI). has been engaged in the creation of general-purpose components that support the processing of large volumes of information that characterize the problems involved in parallel computing.
Samuel Guzmán López +4 more
openalex +3 more sources
Cache-oblivious priority queue and graph algorithm applications [PDF]
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing - STOC '02, 2002 (MATH) In this paper we develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and deletemin operations in O(1 \over B logM/BN \over B) amortized memory transfers, where M and B are the memory and block transfer sizes of any two consecutive levels of a multilevel memory hierarchy.
Lars Arge +4 more
+4 more sources